CS294 L09 Advanced Policy Gradients

• 策略梯度法的缺陷
• 策略表现的界
• 自然策略梯度（NPG）
• 信赖域策略优化（TRPO）
• 近端策略优化（PPO）

策略梯度法的缺陷

策略梯度法是on-policy算法，因此数据利用率低。off-policy版本的策略梯度法需要利用重要性抽样，在新的梯度更新公式中存在连乘，会导致梯度消失或梯度爆炸，算法不稳定。

同时，正确选择步长也是非常困难。

策略表现的界

在之前策略梯度法的分析之中，我们总结出了几个关键要素：一个是尽可能有效地利用最近生成出的策略产生的数据，另一个是按照执行策略空间的距离而不是策略参数空间的距离执行梯度步。

已知$J(\pi_\theta):=\mathbf{E}_ {\tau\sim\pi_\theta}\left[\sum_{t=0}^\infty\gamma^tr_t\right]$，可以得到策略迭代恒等式$J(\pi’)-J(\pi)=\mathbf{E}_ {\tau\sim\pi’}\left[\sum_{t=0}^\infty\gamma^tA^\pi(s_t,a_t)\right]$。要使得改进后的策略变好，即$\max_{\pi’}\mathbf{E}_ {\tau\sim\pi’}\left[\sum_{t=0}^\infty\gamma^tA^\pi(s_t,a_t)\right]$。这样好处是这个期望只和新策略与最近期策略的优势函数有关系，因此可以使用当批的数据；但同时问题在于我们是要关于$\pi’$取期望的，而$\pi’$正好是我们要优化的变量。我们考虑定义一个贴现的未来状态分布（discounted future state distribution）$d^\pi(s)=(1-\gamma)\sum_{t=0}^\infty\gamma^tP(s_t=s\vert\pi)$。这样，根据重要性抽样，可以得出

$$\begin{align} J(\pi')-J(\pi) &= \mathbf{E}_ {\tau\sim\pi'}\left[\sum_{t=0}^\infty\gamma^tA^\pi(s_t,a_t)\right] \\ &= \frac{1}{1-\gamma}\mathbf{E}_{s\sim d^{\pi'},a\sim\pi'}[A^\pi(s,a)] \\ &= \frac{1}{1-\gamma}\mathbf{E}_{s\sim d^{\pi'},a\sim\pi}\left[\frac{\pi'(a|s)}{\pi(a|s)}A^\pi(s,a)\right] \\ &\approx \frac{1}{1-\gamma}\mathbf{E}_ {s\sim d^\pi,a\sim\pi}\left[\frac{\pi'(a|s)}{\pi(a|s)}A^\pi(s,a)\right] \text{假设$d^\pi\approx d^{\pi'}$}\\ &:= \mathcal{L}_\pi(\pi') \\ &= \mathbf{E}_ {\tau\sim\pi}\left[\sum_{t=0}^\infty\gamma^t\frac{\pi'(a|s)}{\pi(a|s)}A^\pi(s_t,a_t)\right] \end{align}$$

表达式的推到中引入了$d^\pi\approx d^{\pi’}$，即要求两个策略非常接近。Achiam et al. (2017) 给出了一个策略相对表现的界（relative policy performance bounds），$\vert J(\pi’)-(J(\pi)+\mathcal{L}_ \pi(\pi’))\vert\leq C\sqrt{\mathbf{E}_ {s\sim d^\pi}[D_{\text{KL}}(\pi’\Vert\pi)[s]]}$，给出了这个近似误差的上界。这个形式类似于重要性抽样，但是连乘的形式变成了累和的形式，因此不会出现梯度爆炸或消失。对绝对值拆分，可以得到$J(\pi’)-J(\pi)\geq \mathcal{L}_ \pi(\pi’)-C\sqrt{\mathbf{E}_ {s\sim d^\pi}[D_{\text{KL}}(\pi’\Vert\pi)[s]]}$，于是求解目标变成了$\pi_{k+1}=\arg\max_{\pi’}\left[\mathcal{L}_ {\pi_k}(\pi’)-C\sqrt{\mathbf{E}_ {s\sim d^{\pi_k}}[D_{\text{KL}}(\pi’\Vert\pi_k)[s]]}\right]$。在最优化中通常把这个KL惩罚项放到约束条件里，作为一个信赖域（trust region），通过约束上界来控制最坏情况的数值，即

$$\pi_{k+1}=\arg\max_{\pi'}\mathcal{L}_{\pi_k}(\pi')\qquad \text{s.t.}~\mathbf{E}_{s\sim d^{\pi_k}}[D_{\text{KL}}(\pi'\Vert\pi_k)[s]]\leq\delta$$

这样，目标函数和约束的计算都可以使用前一个策略的数据来估计，效率较高；在约束上，就是控制新策略关于原来策略的KL散度，是控制在策略空间上的某种意义上的距离，和参数空间怎么扭曲没有关系。

自然策略梯度（NPG）

优化问题是

$$\pi_{k+1}=\arg\max_{\pi'}\mathcal{L}_{\pi_k}(\pi') \qquad \text{s.t.}~\bar{D}_{\text{KL}}(\pi'\Vert\pi_k)\leq\delta$$

，使用局部近似进行优化（因为两个策略接近，局部效果会更好）。将目标函数展开到一阶$\mathcal{L}_ {\theta_k}(\theta)\approx\mathcal{L}_ {\theta_k}(\theta_k)+g^\top(\theta-\theta_k)$，其中前一项为常数；对KL散度展开到二阶（因为一阶为零）$\bar{D}_{\text{KL}}(\pi’\Vert\pi_k)\approx\frac{1}{2}(\theta-\theta_k)^\top H(\theta-\theta_k)$。因此近似迭代格式可以写成

$$\theta_{k+1}=\arg\max_\theta g^\top(\theta-\theta_k) \qquad \text{s.t.}~\frac{1}{2}(\theta-\theta_k)^\top H(\theta-\theta_k)\leq\delta$$

这是一个凸的QCQP问题，强对偶成立。最后得到的结果是

$$\theta_{k+1}=\theta_k+\sqrt{\frac{2\delta}{g^\top H^{-1}g}}H^{-1}g$$

其中$g:=\nabla_\theta\mathcal{L}_ {\theta_k}(\theta)\vert_ {\theta_k}$等于策略梯度，我们的方向是$H^{-1}g$，只是左乘一个矩阵重新调整一下，因此被称为自然策略梯度（natural policy gradient, NPG）；Hessian阵$H=\mathbf{E}_ {s,a\sim\theta_k}\left[\nabla_ \theta\log\pi_\theta(a\vert s)\vert_{\theta_k}\nabla_\theta\log\pi_\theta(a\vert s)\vert_{\theta_k}^\top\right]$是半正定的，是一个Fisher信息矩阵。可以证明，矩阵$H$其实就是策略空间里的度量张量（黎曼空间里的概念），从而$H^{-1}g$是关于参数化形式不变的，不管如何参数化，都是在策略空间的同一个方向进行移动。NPG算法从一组的初始策略参数$\theta_0$开始，我们循环迭代$k=0,1,\ldots$执行以下步骤：

1. 使用策略$\pi_k=\pi(\theta_k)$收集轨迹样本$\mathcal{D}_k$；
2. 使用任意的优势估计算法来估计优势$\hat{A}_t^{\pi_k}$；
3. 使用$\hat{A}_t^{\pi_k}$估计目标函数梯度$\hat{g}_k$，根据样本估计Hessian矩阵$\hat{H}_k$；
4. 进行一步NPG更新，$\theta_{k+1}=\theta_k+\sqrt{\frac{2\delta}{\hat g_k^\top \hat H_k^{-1}\hat g_k}}\hat H_k^{-1}\hat g_k$。

Hessian阵会有$O(N^2)$的元素，且进行一步矩阵求逆需要$O(N^3)$，在存储上和计算上都不太可行。一种解决方法是使用共轭梯度法（Conjugate gradient，CG）等间接算法来求解，CG法执行j步后，把$Hg=x$的解投影到Krylov子空间$\text{span}{g,Hg,\ldots,H^{j-1}g}$中，而且每次只需要使用矩阵向量乘法。

信赖域策略优化（TRPO）

NPG算法存在一些问题。1. NPG迭代过程中对于信赖域大小$\delta$其实不鲁棒，有些步中信赖域大小太大可能会降低表现性能。2. 我们对KL散度进行了二阶近似，因此KL散度的限制可能会被违反。信赖域策略优化算法本质上就是TNPG算法加上一个线搜索，搜索的步长指数下降，算法从一组的初始策略参数$\theta_0$开始，循环迭代$k=0,1,\ldots$执行以下步骤：

1. 使用策略$\pi_k=\pi(\theta_k)$收集轨迹样本$\mathcal{D}_k$
2. 使用任意的优势估计算法来估计优势$\hat{A}_t^{\pi_k}$
3. 使用$\hat{A}_t^{\pi_k}$估计目标函数梯度$\hat{g}_k$，根据样本估计Hessian矩阵$\hat{H}_k$并给出函数$f(v)=\hat{H}_kv$
4. 使用$n_{\text{CG}}$步CG算法，得到$x_k\approx\hat{H}_k^{-1}\hat{g}_k$，从而更新向量$\Delta_k\approx\sqrt{\frac{2\delta}{x_k^\top\hat{H}_kx_k}}x_k$
5. 搜索步长，找到一个最小的j使得$\theta_{k+1}=\theta_k+\alpha^j\Delta_k$满足$\mathcal{L}_ {\theta_k}(\theta_{k+1})\geq0$，$\bar{D}_ {\text{KL}}(\theta\Vert\theta_k)\leq\delta$。从而$\theta_{k+1}=\theta_k+\alpha^j\Delta_k$

相比TNPG，TRPO由于有了一个检验手段和线搜索，能承受更大的步长。

近端策略优化（PPO）

另一种不计算自然梯度而的控制KL散度的约束条件的方法叫近端策略优化（Proximal Policy Optimization, PPO）算法。第一种方法是对KL散度加惩罚，如下：

1. 使用策略$\pi_k=\pi(\theta_k)$收集部分轨迹样本$\mathcal{D}_k$
2. 使用任意的优势估计算法来估计优势$\hat{A}_t^{\pi_k}$
3. 固定乘子，执行若干步minibatch SGD更新策略$\theta_{k+1}=\arg\max_\theta\mathcal{L}_ {\theta_k}(\theta)-\beta_k\bar{D}_ {\text{KL}}(\theta\Vert\theta_k)$，步长为ADAM。
4. 启发式地调整乘子，如$\bar{D}_ {\text{KL}}(\theta_{k+1}\Vert\theta_k)\geq 1.5\delta$则$\beta_{k+1}=2\beta_k$，如$\bar{D}_ {\text{KL}}(\theta_{k+1}\Vert\theta_k)\leq \delta/1.5$则$\beta_{k+1}=\beta_k/2$

第二种方法是使用一个截断的目标函数。步骤如下：

1. 使用策略$\pi_k=\pi(\theta_k)$收集部分轨迹样本$\mathcal{D}_k$
2. 使用任意的优势估计算法来估计优势$\hat{A}_t^{\pi_k}$
3. 执行若干步minibatch SGD更新策略$\theta_{k+1}=\arg\max_\theta\mathcal{L}_ {\theta_k}^{\text{CLIP}}(\theta)$，其中$\mathcal{L}^{\text{CLIP}}_ {\theta_k}(\theta)=\mathbf{E}_ {\tau\sim\pi_k}\left[\sum_{t=0}^T[\min(r_t(\theta)\hat{A}_t^{\pi_k},\text{clip}(r_t(\theta),1-\epsilon,1+\epsilon)\hat{A}_t^{\pi_k})]\right]$