深入理解TRPO和PPO算法

最近在整理电脑文件，看到一份当初给同事讲解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

最后编辑于：2022.03.01 22:55:06

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,126评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,254评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,445评论 0赞 341
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,185评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,178评论 5赞 371
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,970评论 1赞 284
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,276评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,927评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,400评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,883评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,997评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,646评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,213评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,204评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,423评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,423评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,722评论 2赞 345