深入理解TRPO和PPO算法

2022-02-23 本文已影响0人金色暗影

最近在整理电脑文件，看到一份当初给同事讲解TRPO算法原理时写的PPT，感觉要比先前那篇写的更加清楚明白，加之这几天刚好在复习RL相关的知识，然后便将PPT的内容加上我比当时更加深入的理解，整理成了这篇文章，分享给大家。

策略梯度方法及其缺点

相对于Value Based的方法，基于策略梯度的强化学习方法的很明显的优势是它可以直接去学习Policy本身，这样学习速度会更快，并且更关键的是它可以用于连续动作空间的情况。
它的基本思想是通过最大化状态价值来更新策略函数的参数，即最大化目标函数 $J(\theta) = \mathbb{E}_S[V_\pi(s)]$ ,其中 $\theta$ 为策略函数的参数，具体的优化过程如下：

agent观察到一个环境状态 $s_t$
可以计算 $J(\theta)$ 关于策略函数参数 $\theta$ 的梯度 $g(\theta)$
$g(\theta) = \frac{\partial V_\pi(s_t)}{\partial \theta} =\frac{\partial \mathbb{E}_A[\pi_\theta(A|s_t)Q_\pi(s_t,A)] }{\partial \theta} = \mathbb{E}[\frac{\partial log\pi_\theta(A|s_t)}{\partial \theta} Q_\pi(s_t,A)] = \mathbb{E}[\frac{\partial log\pi_\theta(A|s_t)}{\partial \theta} (Q_\pi(s_t,A) - V_\pi(s_t))]$
基于策略 $\pi_\theta$ 随机采样一个动作 a,求随机梯度
$g(\theta) = \frac{\partial log\pi_\theta(a|s)}{\partial \theta} (Q_\pi(s_t,a) - V_\pi(s_t))$
当然，上式子中的 $Q_\pi(s_t,a)$ 和 $V_\pi(s_t)$ 是未知的，我们可以使用一个参数为 $w$ 的神经网络 $v_w(s)$ 来近似 $V_\pi(s)$ ，而 $Q_\pi(s,a)$ 我们可以使用走完一整个episode后的真实回报 $G_t$ ，或者使用 $r_t + v_w(s_{t+1})$ 来近似，这样我们就得到了随机梯度 $g(\theta)$
在通过梯度上升最大化 $J(\theta)$ 的参数 $\theta$ , 其中 $\alpha$ 为学习率
$\theta \leftarrow \theta + \alpha g(\theta)$
这种方法的缺点也是显而易见的，因为强化学习环境的变化往往非常大，也导致Value的方差比普通的深度学习数据要大的多，很难选择到一个合适的学习率 $\alpha$ 可以保障更新参数之后的价值比现在的好，一旦选择了这个更不好的策略进行采样学习，再次更新的参数会更差，因此很容易导致越学越差，一直无法收敛。
价值崩溃

对于怎么选择这个合适的学习率是一个相当棘手的问题，然而不愧是Shulman博士，并没有纠结于表面上的学习率，而是从问题的本质出发，从而另辟蹊径给出了TRPO的解决方案。（P.S. 这就是马斯克所谓的第一性原理的实践案例吧~）

Trust Region Policy Optimization

TRPO算法尽量通过能提高状态价值的方式来更新策略。它通过在新旧策略之间增加约束，将整个参数空间的变化限制在一个小范围之内，从而避免了错误决策导致Value的崩塌，尽可能的保持快速而单调的提升。

我们用 $\pi_\theta$ 来表示参数为 $\theta$ 的策略函数，那么TRPO的参数更新方式可以表示为：
$\theta_{k+1} = \argmax_\theta\mathcal{L}(\theta_k ~,\theta) \\ ~~ ~~ ~~ ~~ ~~ ~~~~ ~~ ~~~~ ~~ ~~~ ~~~~ s.t. ~\overline{D}_{KL}(\theta || \theta_k) \leq\delta$
这里的 $\mathcal{L}(\theta_k , \theta)$ 是原始策略梯度最大化目标 $J(\theta)$ 在 $\overline{D}_{KL}(\theta || \theta_k) \leq\delta$ 限制范围内的近似:
$\mathcal{L}{(\theta_k ， \theta)} = \mathbb{E}[\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} A_{\pi_{\theta_k}}(s,a)]$
其中 $A_{\pi_{\theta_k}}(s,a)$ 是优势函数，表示选择动作 $a$ 所带来的优势，直观上看，如果 $A< 0$ 说明动作 $a$ 不好，应该降低 $a$ 的概率，于是应该减小动作 $a$ 的概率，那么 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 应该小于1，越接近0越好，正好符合 $\mathcal{L}{(\theta_k , \theta)}$ 的最大化，反之亦成立，因此从直观上看，这个替代的目标函数是符合要求的。但是这个替代函数到底是怎么来的呢？
其实非常简单，我们只需要对 $J(\theta)$ 做一点微小的变换：
$\begin{align} J(\theta) = \mathbb{E}_s[V_\pi(s)] &= \mathbb{E}_s[\mathbb{E}_a[Q_\pi(s,a)]] \\ &= \mathbb{E}_s[ \sum_{a\sim\theta_k}\pi_\theta(a|s)Q_{\pi_{\theta_k}}(s,a)] \\ &= \mathbb{E}_s[ \sum_{a\sim\theta_k} \pi_{\theta_k}(a|s) \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}Q_{\pi_{\theta_k}}(s,~a)] \\ &= \mathbb{E}_{s,a}[ \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}Q_{\pi_{\theta_k}}(s,a)] \\ 引入优势函数A \\ &= \mathbb{E}_{s,a}[ \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}A_{\pi_{\theta_k}}(s,a)] = \mathcal{L}{(\theta_k , \theta)} \end{align}$
虽然推出了优化目标，但是要怎么来解这个带约束的优化问题呢？其实就是参考了 Trust Region 算法的求解过程，这也是TRPO这个算法名字的由来。

Trust Region

我们先来看一下Trust Region算法是怎么来最大化目标函数 $J(\theta)$ 的，TRPO用的也是同样的方法。

第一步，我们定义参数 $\theta_k$ 的邻域 $\mathcal{N}(\theta_k，\theta)$ , $\theta$ 是该邻域内的点，满足 $\theta$ 和 $\theta_k$ 比较接近，常见的方式就是保证：

$|| \theta - \theta_k ||_2 < \delta$
$\overline{D}_{KL}(\theta || \theta_k) < \delta$
然后我们在这个邻域内找到 $J(\theta)$ 的相似函数 $\mathcal{L}(\theta_k , \theta)$
找邻域内的相似函数

第二步，在邻域 $\mathcal{N}(\theta_k，\theta)$ 内求 $\mathcal{L}(\theta_k , \theta)$ 的最大值：
$\theta_{k+1} = \argmax_\theta\mathcal{L}(\theta_k ~,\theta) \\ ~~ ~~ ~~ ~~ ~~ ~~~ ~ ~~ ~~~~ ~~ ~~ ~~ ~~ ~ ~~ s.t. ~\overline{D}_{KL}(\theta || \theta_k) \leq\delta$

领域内求最大值

第三步，重复上面两步，直到收敛：

迭代

TRPO的更新过程

显然TRPO算法的训练过程就是在策略梯度方法的基础上，套用了Trust Region 。

在邻域 $\mathcal{N}(\theta_k,~\theta)$ 内找到 $J(\theta)$ 的近似函数 $\mathcal{L}(\theta_k,\theta)$
我们使⽤蒙特卡洛来作为期望的近似，使⽤当前策略 $\pi_{\theta_k}$ 来和环境交互，除了记录transition之外，还记录每一步的 $\pi(s,a)$ ,就可以得到公式中的 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ ,另外用一个神经网络来近似 $V_\pi$ , 利用TD算法可以求出公式中的Advantage，这样近似函数就找到了，另外我们使用 $\pi_\theta$ 和 $\pi_{\theta_k}$ 的平均KL散度来增加这个约束。
但是从理论上来说，上面所说的TRPO更新十分难求，于是需要做进一步的近似。
我们使用泰勒级数来估计 $\mathcal{L}$ 和 $KL$ 散度的均值，将 $\mathcal{L}$ 展开到一阶，KL散度展开到二阶:
$\mathcal{L}(\theta_k,\theta) \approx g^T(\theta-\theta_k) \\ \overline{D}_{KL}{(\pi_{\theta_k}, \pi_\theta)} \approx \frac{1}{2} (\theta -\theta_k)^T H(\theta-\theta_k)$
就得到了这样一个近似的优化问题：
$\theta_{k+1} = \argmax_\theta g^T(\theta-\theta_k) \\ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ ~~ s.t. \frac{1}{2} (\theta -\theta_k)^T H(\theta-\theta_k)$
最大化
这个近似问题可以⽤拉格朗⽇对偶⽅法解析求解：
$\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g$
如果我们只使用这个结果，算法将精确计算自然策略梯度。但是这样有一个问题，由于泰勒展开式引入了近似误差，可能会导致不满足KL散度的约束，或者实际提高了相应动作的优势，于是TRPO对这个更新规则增加了一个修改，称之为回溯线搜索：
$\theta_{k+1} = \theta_k +\alpha^j \sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g$
其中 $\alpha \in (0, 1)$ 是回溯系数， $j$ 是 $\pi_{\theta_{k+1}}$ 满足KL散度约束并产生正向替代优势的最小非负整数。
另外，当神经网络有数百万个参数时，计算和存储矩阵 $H^{-1}$ 的代价是很大的。TRPO通过使⽤共轭梯度算法计算 $Hx=g$ 来避免求解 $x=H^{-1}g$ .这样我们就可以只⽤⼀个函数来计算 $Hx$ ,从而避免直接存储整个矩阵 .(其实这个⽅法跟梯度下降有点像)。
沿着更新方程迭代直到收敛...

Proximal Policy Optimization

看了上面的更新过程，我们其实就会发现，当我们使用神经网络来近似策略时，参数非常多，TRPO的二阶解法计算量会非常大，于是就有了后来的PPO算法。它们的动机是完全一样的，就是为了让当前策略上进行有效更新时不至于导致Value的崩溃。PPO算法可以看作时TRPO的一阶近似，它的试用范围更广、计算效率更高、更容易实现，并且从OpenAI的经验上来看，至少效果是不比TRPO差的。PPO也成为了SOTA强化学习算法中最常用的之一。

PPO主要有两种变体：PPO-Penalty 和 PPO-Clip 。

PPO-Penalty修改了KL散度的约束方式，它不再添加硬约束，而是通过在目标函数中加入KL散度的正则项的方式来处理约束问题。
PPO-Clip 则删除了约束，直接使用强制剪裁的暴力方式来让 $\theta$ 的更新保持在一定范围之内。

实践证明，PPO-Clip这种暴力的方式反而更有效，因此现在主流的PPO用的都是PPO-Clip，因此，本文也就只讲PPO-Clip的原理和实现。

PPO-Clip的目标函数可以改写为：
$\mathcal{L}(s, a,\theta_k, \theta) = min(\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} A_{\pi_{\theta_k}}(s,a) , clip( \frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}, 1-\epsilon, 1+ \epsilon) A_{\pi_{\theta_k}}(s,a)))$
这个公式非常复杂，我们将其拆解成两种情况来看...
当优势A大于0：，说明动作a是好的，于是应该让 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ 大于1且范围内越大越好，当 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} > 1 + \epsilon$ 时就截取到 $1 + \epsilon$ , 否则取原值 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ .
当优势A小于等于0：，说明动作a是不好的，于是应该让 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ < 1且范围内越小越好，当 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)} < 1 - \epsilon$ ，则截取到 $1 - \epsilon$ ，否则 $\frac{\pi_\theta(a|s)}{\pi_{\theta_k}(a|s)}$ ，此时应该是取max，但是因为A是负的，于是又变成了取min，这样就刚好对应上面的公式。

然后价值网络和策略网络的设计方式和普通的actor-critic并没有区别，分别用td算法来有优化value网络，用梯度上升来优化policy网络训练即可。

GAE

另外值得一提的还有generalized advantage estimator算法，因为我们一般在实现PPO的时候并不会用最原始的Advantage function，而是GAE，GAE实际上就是multi-step td的Advantage的指数加权移动平均，正如multi-step的td算法比one-step的会好，gae可以让优势估计更加平滑和稳定，因为GAE的效果更好，因此在后期GAE版本的TRPO和PPO才是标准的实现。

参考Multi-step TD target的思想，我们将 $V$ 作为状态价值的近似，折扣系数为 $\gamma$ ,定义 $\delta_t^V=r_t+ \gamma V(s_{t+1}) - V(s_t)$ , 则n步的Adventage的 $\hat{A}_t^{(n)}$ 估计应该是这样的：
$\begin{align} \hat{A}_t^{(1)} &= \delta_t^V = -V(s_t)+r_t+\gamma V(s_{t+1}) \\ \hat{A}_t^{(2)} &= \delta_t^V + \gamma \delta_{t+1}^V = -V(s_t)+r_t+ \gamma r_{t+1} +\gamma^2 V(s_{t+2}) \\ \hat{A}_t^{(3)} &= \delta_t^V + \gamma \delta_{t+1}^V + \gamma^2 \delta_{t+2}^V = -V(s_t)+r_t+ \gamma r_{t+1} + \gamma^2 r_{t+2} +\gamma^3 V(s_{t+3}) \\ ... \\ \hat{A}_t^{(k)} &= \sum^{k-1}_{l=0}\gamma^l\delta_{t+l}^V = -V(s_t)+r_t+\gamma r_{t+1} + ... + \gamma^{k-1}r_{t+k-1}+ \gamma^kV(s_{t+k})\\ \end{align}$
但是我们到底选几步的优势是最好的呢？又是否存在这样一个最好的n呢？
在不知道选哪个预测值的情况下，数值优化算法上有一种很常见的作法，就是取附近值的指数加权移动平均，这便是GAE了，我们将加权系数设置为 $\lambda$ :
$\hat{A}_t^{GAE(\gamma, \lambda)} = (1-\lambda)(\hat{A}_t^{(1)}+ \lambda \hat{A}_t^{(2)} + \lambda^2\hat{A}_t^{(3)}+...)$
当 $\lambda = 0$ 时， $\hat{A}_t = \delta_t$ ，相当于one-step的TD。
当 $\lambda = 1$ 时， $\hat{A}_t = \sum^{\inf}_{l=0}\gamma^l\delta_{t+l}$ ，相当于玩完整局菜更新的Reinforce。
这个权重系数 $\lambda$ 就是用来控制取多少步的，比如 $\lambda =0.5$ , 此时 $\lambda^2 \approx \frac{1}{e} \approx 0.35$ 很小，我们可以认为平均了2步，再设大一些就会多取几步。