[人工智能][paper reading] Trust Region Policy Optimization

Trust Region Policy Optimization

https://arxiv.org/pdf/1502.05477.pdf

有保证的单调递增策略梯度

指出问题

没啥问题，直接提出单调递增策略梯度

理论证明

$(\mathcal{S},\mathcal{A},P,r,{\rho }_0,\gamma )$
${\rho }_0$ : 初始状态 $s_0$ 的分布
那么期望折扣回报可以表示为

$$\begin{gathered} \eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }\left[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)\right],\text{where} \\ {s}_0～{\rho }_0,a_t～\pi (a_t|s_t),s_{t+1}～P(s_{t+1}|s_t,a_t) \end{gathered}$$

状态分布表示为

$${\rho }_{\tilde{\pi }}(s)=\sum _{t=0}^{\infty }P(s_t=s|s_0,\pi )$$

[Kakade 2002] 中提到，对于任意两种策略 $\tilde{\pi }$ 和 $\pi$，有

$$\eta (\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\tilde{\pi }}(s)\sum _a\tilde{\pi }(a|s)A_{\pi }(s,a)$$

令 ${\pi }_{old}$ 为当前策略，令 ${\pi }^{\prime }=\underset{{\pi }^{\prime }}{\mathrm{argmax}}{L}_{{\pi }_{old}}({\pi }^{\prime })$. ${\pi }_{new}$ 是一个混合策略（mixture）：

$${\pi }_{new}=(1?\alpha ){\pi }_{old}(a|s)+\alpha {\pi }^{\prime }(a|s)$$

根据 [Kakade 2002] 可知

$$\begin{array}{rl}\eta ({\pi }_{new})?\eta ({\pi }_{old})& =\sum _s{\rho }_{{\pi }_{new}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)\\ & \ge \sum _s{\rho }_{{\pi }_{old}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)?2\alpha ?\left(\frac{1}{1?\gamma }?\frac{1}{1?\gamma (1?\alpha )}\right)\\ & =\sum _s{\rho }_{{\pi }_{old}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)?\frac{2?\gamma }{(1?\gamma {)}^2}{\alpha }^2\\ \text{where?}?& =\underset{s}{\max }\left|{\mathbb{E}}_{a～{\pi }^{\prime }(a|s)}[A_{\pi }(s,a)]\right|\end{array}$$

这里对下界做了一些调整，更加简洁一点

$$\begin{array}{rl}\frac{1}{1?\gamma }?\frac{1}{1?\gamma (1?\alpha )}& =\frac{1?\gamma (1?\alpha )?(1?\gamma )}{(1?\gamma )[1?\gamma (1?\alpha )]}\\ & =\frac{\alpha \gamma }{(1?\gamma )[1?\gamma (1?\alpha )]}\\ & \ge \frac{\alpha \gamma }{(1?\gamma {)}^2}\end{array}$$

${\pi }_{new}$ 是一个混合策略，$\alpha$ 是混合系数，但是实际上混合策略很少被使用，导致上述公式难以解决实际问题。于是，使用总变化散度（total variation divergence）$D_{TV}(p||q)=\frac{1}{2}{\sum }_i|p_i?q_i|$ 来取代 $\alpha$，其中 $pq$ 是离散概率分布。把 $D_{TV}^{\max }(\pi ,\tilde{\pi })$ 定义为

$$D_{TV}^{\max }(\pi ,\tilde{\pi })=\underset{s}{\max }{D}_{TV}(\pi (?|s)||\tilde{\pi }(?|s))$$

Theorem 1. 令 $\alpha =D_{TV}^{\max }(\pi ,\tilde{\pi })$。下界依旧成立：

$$\begin{gathered} \eta ({\pi }_{new})?\eta ({\pi }_{old})\ge \sum _s{\rho }_{{\pi }_{old}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)?\frac{4?\gamma }{(1?\gamma {)}^2}{\alpha }^2 \\ \text{where?}?=\underset{s,a}{\max }\left|A_{\pi }(s,a)\right| \end{gathered}$$

原文里的证明有点复杂，有时间再看吧…

下面，总变化散度（total variation divergence）和 KL 散度其实是有关系的：$D_{TV}(p||q{)}^2\le D_{KL}(p||q)$。令 $D_{KL}^{\max }(\pi ,\tilde{\pi })={\max }_s{D}_{KL}(\pi (?|s)||\tilde{\pi }(?|s))$，那么下界成立：

$$\eta ({\pi }_{new})?\eta ({\pi }_{old})\ge \sum _s{\rho }_{{\pi }_{old}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)?\frac{4?\gamma }{(1?\gamma {)}^2}{D}_{KL}^{\max }(\pi ,\tilde{\pi })$$

实际上，如果我们使用惩罚系数 C，步长将会变得非常非常小。一种可行的办法是把 KL 那一项作为约束条件：

$$\begin{gathered} {\text{maximize}}_{\theta }\sum _s{\rho }_{{\pi }_{old}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a) \\ \text{subject?to}{D}_{KL}^{\max }(\pi ,\tilde{\pi })\le \delta \end{gathered}$$

由于计算 $D_{KL}^{\max }(\pi ,\tilde{\pi })$ 比较麻烦，可以用平均 KL 散度代替：

$${\overline{D}}_{KL}^{\rho }(\pi ,\tilde{\pi }):={\mathbb{E}}_{s～\rho }[D_{KL}(\pi (?|s)||\tilde{\pi }(?|s))]$$

重要性采样

实际上的数据由蒙特卡洛采样得到，我们使用采样来对公式进行一下替换：

$$\begin{array}{rl}\sum _s{\rho }_{{\pi }_{old}}(s)\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)& ={\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}\sum _a{\pi }_{new}(a|s)A_{{\pi }_{old}}(s,a)\\ & ={\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}\sum _a{\pi }_{old}(a|s)\frac{{\pi }_{new}(a|s)}{{\pi }_{old}(a|s)}{A}_{{\pi }_{old}}(s,a)\\ & ={\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}{\mathbb{E}}_{a～{\pi }_{old}}\frac{{\pi }_{new}(a|s)}{{\pi }_{old}(a|s)}{A}_{{\pi }_{old}}(s,a)\end{array}$$

因此，代理目标（surrogate objective）可以写为：

$$\begin{gathered} {\text{maximize}}_{\theta }{\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}{\mathbb{E}}_{a～{\pi }_{old}}\frac{{\pi }_{new}(a|s)}{{\pi }_{old}(a|s)}{A}_{{\pi }_{old}}(s,a) \\ \text{subject?to}{\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}[D_{KL}({\pi }_{old}(?|s)||{\pi }_{new}(?|s))]\le \delta \end{gathered}$$

然后这里介绍了两种采样方式，分别是单路径（single path）和藤蔓（vine）。单路径法很简单，就是蒙特卡洛法。藤蔓法比较难以理解。

藤蔓法，首先使用蒙特卡洛方法得到一条轨迹，然后在这条轨迹选择一个大小为 $N$ 的状态子集，用 rollout set 表示。对于该状态子集中的每个状态 $s_n$，我们通过 $a_{n,k}～q(?|s_n)$ 采样 $K$ 个动作。实际上发现，对于连续动作问题（如 robotic locomotion），$q(?|s_n)={\pi }_{\theta }(?|s_n)$ 有效果，对于离散动作问题（如 atari），随机分布有效果，因为可以实现更好的探索。

但是由于藤蔓法很麻烦，单单把 gym 环境重置到指定状态就很难做到…所以藤蔓法具体细节这里就不写了。

实用算法

再写一下刚刚提到的代理目标（surrogate objective）：

$$\begin{gathered} {\text{maximize}}_{\theta }{\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}{\mathbb{E}}_{a～{\pi }_{old}}\frac{{\pi }_{new}(a|s)}{{\pi }_{old}(a|s)}{A}_{{\pi }_{old}}(s,a) \\ \text{subject?to}{\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}[D_{KL}({\pi }_{old}(?|s)||{\pi }_{new}(?|s))]\le \delta \end{gathered}$$

我们定义

$$J(\theta )={\mathbb{E}}_{s～{\rho }_{{\pi }_{old}}}{\mathbb{E}}_{a～{\pi }_{old}}\frac{{\pi }_{new}(a|s)}{{\pi }_{old}(a|s)}{A}_{{\pi }_{old}}(s,a)$$

那么 ${\text{maximize}}_{\theta }J(\theta )$ 可以写为 ${\text{maximize}}_{\theta }{?}_{\theta }J(\theta {)}^T\Delta \theta$

我们知道通过 KL 散度的二阶泰勒展开，可以得到和费谢尔矩阵的关系：

$$KL(f(x;\theta )||f(x;\theta +\Delta \theta ))\approx \frac{1}{2}\Delta {\theta }^{T}F\Delta \theta$$

看一下 KL 散度的二阶导数（${\theta }^{?}$ 表示参数为常值）：

这里是参考 https://zhuanlan.zhihu.com/p/106984936，作者讲得好，建议看。

$$\begin{array}{rl}{?}_{\theta }^{2}KL(f(x;{\theta }^{?})||f(x;\theta ))& ={?}_{\theta }^2\left[\int f(x;{\theta }^{?})\log f(x;{\theta }^{?})dx?\int f(x;{\theta }^{?})\log f(x;\theta )dx\right]\\ & =?\int f(x;{\theta }^{?}){?}_{\theta }^2\log f(x;\theta )dx\\ & =?E\left[{?}_{\theta }^2\log f(x;\theta )\right]\\ & =F\end{array}$$

文章中使用 KL 散度的二阶导 $H={?}_{\theta }^{2}KL(?)$ 来作为费谢尔矩阵 $F$ 的估计。

因此，我们可以把代理目标重写为：

$$$$

$$\begin{gathered} {\text{maximize}}_{\theta }{?}_{\theta }J(\theta {)}^T\Delta \theta \\ \text{subject?to?}\frac{1}{2}\Delta {\theta }^{T}H\Delta \theta =? \end{gathered}$$

这是一个简单的约束优化问题，使用拉格朗日乘数法（Lagrange Multiplier Method）来解：

$$f(\theta )={?}_{\theta }J(\theta {)}^T\Delta \theta +\lambda (\frac{1}{2}\Delta {\theta }^{T}H\Delta \theta ??)$$

则有方程组

$$\{\begin{array}{ll}{?}_{\Delta \theta }f(\theta )={?}_{\theta }J(\theta )+\lambda H\Delta \theta =0& (1)\\ \frac{1}{2}\Delta {\theta }^{T}H\Delta \theta ??=0& (2)\end{array}$$

由 $(1)$ 解得 $\Delta \theta =?\frac{1}{\lambda }{H}^{?1}g$，代入 $(2)$ 中得（注意，$H$ 是海森矩阵，是对称的，即 $H^T=H$，其逆矩阵也是对称矩阵）

$$\begin{array}{rl}\frac{1}{2{\lambda }^2}{g}^T(H^{?1}{)}^{T}H{H}^{?1}g& =?\\ \frac{1}{2?}{g}^T{H}^{?1}g& ={\lambda }^2\\ \sqrt{\frac{g^T{H}^{?1}g}{2?}}& =\lambda \end{array}$$

代回得

$$\begin{array}{rl}\Delta \theta & =?\frac{1}{\lambda }{H}^{?1}g\\ & =?\sqrt{\frac{2?}{g^T{H}^{?1}g}}{H}^{?1}g\end{array}$$

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖