深入理解TRPO和PPO算法

作者: 金色暗影 | 来源:发表于2022-02-23 23:10 被阅读0次

深入理解TRPO和PPO算法
VPG && TRPO && PPO
从TRPO到PPO
20170914——丁酉年七月廿四
TRPO算法解析
深度强化学习--TRPO与PPO实现
PPO算法解析
Trust Region Policy Optimization
从TRPO到PPO（理论分析与数学证明）
RLLAB 中 TRPO 算法

最近在整理电脑文件，看到一份当初给同事讲解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步，再设大一些就会多取几步。

总结

PPO通过on-policy的方式训练随机策略，这意味它通过最新版本的随机策略来对环境进行采样，但是实际分布式采样和训练的时候往往有策略更新的延迟的情况，因此也可以算作是有点off-policy的...

基础实现的代码可以参考我教程中的实现tutorials/ppo ，不过请注意，这个单worker的版本仅用于学习基本的原理，实际并没有什么用，真正有用的请参考进阶版中的多worker实现。

参考

Trust Region Policy Optimization, Schulman et al. 2015
Approximately Optimal Approximate Reinforcement Learning, Kakade and Langford 2002
Proximal Policy Optimization Algorithms, Schulman et al. 2017
High Dimensional Continuous Control Using Generalized Advantage Estimation, Schulman et al. 2016
Emergence of Locomotion Behaviours in Rich Environments, Heess et al. 2017
Trust Region Policy Optimization, spinningup.openai

深入理解TRPO和PPO算法
最近在整理电脑文件，看到一份当初给同事讲解TRPO算法原理时写的PPT，感觉要比先前那篇写的更加清楚明白，加之这几...
VPG && TRPO && PPO
PPO（Proximal Policy Optimization）是一种解决 PG 算法中学习率不好确定的问题的...
从TRPO到PPO
TRPO 引出优化目标新策略的回报函数可以分解为旧策略的回报函数+一些其它项其中A是优势函数，证明过程如下若设...
20170914——丁酉年七月廿四
本周从DQN开始，回顾了DPG、DDPG、TRPO。不得不说，深入去理解每一篇paper，才知道各路大神为什...
TRPO算法解析
这俗话说的好呀，这饭要一口一口吃，酒要一口一口喝，路要一步一步走，步子迈大了，喀，容易扯到蛋。这训练模型呢，也是这...
深度强化学习--TRPO与PPO实现
PPO是2017年由OpenAI提出的一种基于随机策略的DRL算法，它不仅有很好的性能（尤其是对于连续控制问题），...
PPO算法解析
在2017年的时候，无论是openai或者是deepmind，在深度强化学习领域都取得了重大突破，而能带来这个突破...
Trust Region Policy Optimization
本文是自己的TRPO算法学习笔记，在数学原理推导核心部分附有自己的理解与解释。整篇文章逻辑清晰，思路顺畅。有想...
从TRPO到PPO（理论分析与数学证明）
本文首发于行者AI[https://xingzheai.cn/] 引言一篇关于强化学习算法的理论推导，或许可以帮...
RLLAB 中 TRPO 算法
Neil Zhu，简书ID Not_GOD，University AI 创始人 & Chief Scientist...