强化学习 | TRPO | PPO | 超详细 | 手写笔记(2)

kirin77

• 始于基础，递进学习 Gradient、PG、Natural PG、TRPO、PPO
  
• 注释数学概念，包括梯度、黎曼流形、Conjugate Gradient、Trust Region等30余
  
• 先概述后细节，避免一叶障目。如写TRPO时，首先总结其在目标函数和梯度更新 (基于NPG) 两方面的改进，而后进行细节推导，最后将TRPO套入 "Trust Region Algorithm" 框架中深化理解
  
• 共1.3w字，含大量手写笔记。如有理解错误，欢迎指正
  

• 篇幅过长，分至2篇。第1篇 (介绍梯度Gradient、策略梯度Policy Gradient、自然策略梯度Natural Policy Gradient)：
  

• 此为第2篇，主讲TRPO和PPO
  

<hr/>TRPO

2015 - John Schulman - Trust Region Policy Optimization
TRPO核心概述

TRPO (Trust Region Policy Optimization)，即置信域策略优化。
TRPO分别在目标函数和梯度更新两方面做了改进
<hr/>梯度更新方面的改进
TRPO基于Natural Policy Gradient (即用KL divergence约束policy，避免policy剧烈迭代)，做了以下两点改进：
第一点，为避免求解复杂的Fisher/Hessian逆运算，使用了conjugate gradient
第二点，将学习率换成 α^j * NPG原始的学习率，α∈(0,1)，由大至小线性搜索使目标函数大于0 (即本次迭代比上次好)，且符合KL divergence 的最小整数j值 (防止泰勒展开带来的误差)
即像原文讲的，"TRPO is related to prior methods(e.g.natural policy gradient) but make several changes,most notably by using a fixed KL divergence rather than a fixed penalty coeffificient"
<hr/>目标函数方面的改进
在目标函数中引入Importance Sampling，提升了sample efficiency (原来每次采样完后只能更i性能一次梯度就把样本扔掉。引入IS后，可以多次使用θ'采样得的数据更新θ，即使用一批数据进行多次gradient ascent)。
还有一点有意思的是，作者将新的expeted disconted reward拆成了两部分，即旧的reward+某一部分。思想是，如果，理想情况下，"某一部分"恒为正，则reward是单调不减的，即每次策略都比之前的好。
这之外还有一点特殊的，在推导surrogate function的过程中，作者使用了MM算法，即找了目标函数的下界作为surrogate function
<hr/>

注意，一定要对前面的Natural Policy Gradient有透彻的了解才能看TRPO，否则会在某些细节处很迷惑。因为TRPO的论文中并没有对自然梯度有很多篇幅的介绍，所以要先有自然梯度的先验知识，才能研读TRPO

<hr/>TRPO推导细节

那么对TRPO的行文细节理解一下
目标函数
先推导下目标函数

关于说TRPO单调不减这块我是有点疑惑的。看原文的时候，作者说的大概意思是如果使用deterministic policy的话，确实能保证单调不减，因为 ，只要有一个state-action对的Advantage Function大于0，就会选择它(当然如果大于0的多的话就选最大的)，因为determinstic policy是贪婪的。除非到了Advantage为0，即所有action都是一样好了，是收敛成功，停止了。作者又说，因为"unavoidable estimation and approximation error"，也可能出现 的情况。感觉是因为噪声和建模不太准确吗？还是跟stochastic policy有关系？ 总之，实际中，不一定能保证新策略的reward减旧策略的reward一定大于0，就是说不能保证一直单调递增。但是作者的确用了想单调收敛的思想来拆分目标函数。（可能是大概率会一直单调收敛，偶尔下降？还是有点疑惑）

<hr/>





这其实就是trust region algorithm的图，取自 这篇 ，讲得蛮好的这块

MM (Minorize-Maximization)  MM算法是一个迭代优化，其利用凸函数方法，以便找到他们的最大值或最小值,取决于所需的优化是最大化还是最小化。MM本身不是算法，而是描述如何构造优化算法。

<hr/>

Importance Sampling重要性采样：

好困，现在凌晨三点多了，不想打字了，看链接吧
ps：文章里还有一步，是说KL div的max太难求了，给sampling求平均了。这里不加进去了，只属于细节，不是关键点，怕打断推导思路

<hr/>

好了，目标函数推导出来了！下面就可以计算natural gradient，然后梯度上升了。跟上一part讲的梯度更新思路一样。
（但是好像看伪代码中，还是用的advantage value）
<hr/>
在实际应用中，会用样本平均值表示期望，论文中提到了两种采样方法：


关于vine sampling中的rollout，这篇 解释得蛮清晰。且在vine sampling中，"trunk" 是回合更新的，而 "brank" 是单步更新的
"The vine method gives much better estimates of the advantage values. But the vine method must perform far more calls to the simulator for each these advantage estimates."
"The vine method requires us to generate multiple trajectories from each state in the rollout set ,which limits this algorithm to setting where the system can be reset to an arbitrary state. In contrast,the single path algorithm requires no state reset and can be directly implemented on a physical system."
<hr/>梯度更
接下来看下梯度的更新方程
首先按照Natural Policy Gradient的推导过程，我们得到以下更新方程：

因为目标函数是求最大reward，所以做梯度上升哦

<hr/>TRPO做了两点改进
其一，使用conjugate gradient (CG) 避免求解复杂的Hessian / Fisher矩阵逆运算

CG (共轭梯度法)：

如图，普通的梯度上升法并不是朝着全局最优解前进的，中间可能会出现梯度抵消的现象。如果目标函数是二次函数，我们可以使用共轭梯度法避免这种抵消。即搜索方向是正交的，最大搜索次数是参数的个数。  
ps：CG的目标函数是二次型函数。但对于一般非线性函数，可以通过泰勒定理将其转为近似二次型 论文在附录C详细描述了CG，包括实验得出最佳迭代次数为10等。详细细节见论文  
这篇 讲得蛮清晰的  
还有这篇综述《用共轭梯度法解决最优化问题》：

<hr/>其二，TRPO将学习率换成 α^j * NPG原始的学习率，α∈(0,1)，j∈{0,1,2...}，由大至小线性搜索最小的j使得满足"improvement of the surrogate objective and satisfaction of the KL divergence constraint".

结合指数函数α^j的图像直观理解一下这句话的意思：

从大至小搜索使得目标函数提升且满足KL div的最小j，这时候α^j最大，其实就是在原来的NPG学习率前面乘了个(0,1)的系数，我们既希望满足条件又希望不要对NPG改变太大，所以找"最大"的最靠近1的系数，使NPG尽量不变。  
论文在附录C描述了line search在其中的使用，细节见论文

"Starting with the maximal value of the step length β(即NPG算出来的原始学习率 )" in the previous paragraph,we shrink β exponentially (指数地，即α^j) until the objective improves.
"With this line search,the algorithm occasionally computes large steps that cause a catastrophic degradation of performance"


感觉line search是起到trust region的作用吧，通过这里可以再理解下TRPO将KL div放到约束项而非惩罚项的问题
<hr/>贴下Natrual Gradient Algorithm和TRPO的伪代码对比下：




TRPO将KL div放在了约束项中，而非惩罚项，原因是δ好调，不好调且太大。具体看 这篇，这篇 里也提到了这一点
<hr/>看下TRPO更详细的伪代码：


<hr/>Trust Region
好了，最后总结下Trust Region Policy Optimization中的 "Trust Region" 及 "Trust Region Algorithm" (数值优化领域的经典算法)
<hr/>来看下什么是 "Trust Reigon"


<hr/>看懂什么是Trust Region，再看下 Trust Region Algorithm是怎样的
它分为两步，"approximation" 和 "maximization"。
回想一下TRPO的整个流程，还真的是遵循这个大框架，即可以分为这两步，然后反复迭代：




<hr/>PPO

2017 - John Schulman - Proximal Policy Optimization Algorithms
PPO核心概述

PPO同样是OpenAI的作品，它和TRPO是一个作者。PPO延续了TRPO的核心思想，即引入IS提高sample efficiency和约束两个策略间差异不要过大
但是相较TRPO，PPO简化了问题的求解方式，降低了计算复杂度，在实际工程中用得更多

在工程问题中，一般的直觉是，较小的问题用DQN作为baseline (收敛较快、便于训练)，较大、较复杂的问题用PPO作为baseline (效果较好)

PPO有许多version，在最初的论文中只介绍了两种，PPO1和PPO2
PPO1：TRPO之所以将KL div放到约束项而非惩罚项中，就是因为参数β难调。PPO1将KL div放到约束项中，自适应地动态调整KL前的参数，被称为 "Adaptive KL Penalty Coefficient"
PPO2：PPO2同样想使两个策略间差异不要过大，但是未使用KL约束，而是通过clip，巧妙设置新旧策略比值的范围

实验中，PPO2的效果强于PPO1

其实有NPG和TRPO的基础后，PPO就很好理解了。PPO与TRPO相同的部分将不再描述
<hr/>PPO推导细节

PPO1：Adaptive KL Penalty Coefficient
"The theory justifying TRPO actually suggests using a penalty instead of a constraint".但因为权重β难以调整的问题，TRPO没有选择将KL div作为惩罚项放到目标函数进而解决无约束问题，而是将KL div作为hard constraint处理
而PPO1将KL div放到约束项中：


那么KL div前面的权重如何设置呢？
"Experiments show that it is not sufficient to simply choose a fixed penalty cofficient β and optimize the penalized objective with SGD.Additional modifications are required”.简单地设定一个权重值β在实验中表现不佳
所以PPO1中使用了自适应调整权重β的方法
<hr/>步骤
即首先设置一个可接受的KL div最大值 和可接受的KL div最小值
如果一轮优化完后，KL div太大，则说明后面的惩罚项 没有发挥作用，则增大β
如果一轮优化完后，KL div太小，则说明后面的惩罚项 的效果太强了，担忧只优化了后一项，这不是我们想要的，则减小β
即 时，减小β；

时，增大β
<hr/>伪代码


<hr/>PPO2：Clipped Surrogate Objective
首先定义了新旧策略间的比值r(θ)，将L写成  


<hr/>步骤
PPO2的main objective为：


min函数：在两个式子间取最小值
clip函数：
假设ε=2，则clip函数为，
即当  <0.8，则输出0.8；当  >1.2，则输出1.2；当  ∈[0.8,1.2]，则不裁剪，照旧输出  
这样就保证了新旧策略的比值在区间 [0.8,1.2] 内，即两个策略不至于相差太大

PPO采用一阶优化加限制的形式，替代TRPO中的二阶优化，使用CLIP代替复杂的KL div计算，同样使得两个策略间差异不太大

<hr/>PPO2设计得很巧妙的还有一点，就是在clip函数后乘了  

是有正负的啊。当这个动作 "相对好" 的时候，>0；当这个动作 "相对差" 的时候，  <0
那么再搭配上min这个函数，就会有这样较有意思的效果：

实在太困了，我就自己懒得画了，别的博客中有张图，对min、A的正负对  的计算挺清晰的，但是跟上面这张论文里的图配色不太一样，A<0时候坐标轴也没倒过来。注意别看混了：

其中，  是绿色的线， 是蓝色的线。红色的线min取哪部分取决于A的正负

<hr/>直观理解下，当A>0，即该state-action是相对好的，则希望增大这个state-action的概率，但是又不能增得太大导致  太大，即前后策略相差太大，故限制其比例不得大于1+ε
当A<0，即该state-action是相对差的，则希望减小这个state-action得概率，但是又不能减小太多使得  太小，即前后策略相差太大，故限制其比例不得小于1-ε
<hr/>结合一些其它考虑，PPO2最后的objective：



是quared-error，表示为 ，S是entropy bonus

关于entropy bonus： "If using a neural network architecture that shares parameters between the policy and value function, we must use a loss function that combines the policy surrogate and a value function error term. This objective can further be augmented by adding an entropy bonus to ensure sufficient exploration, as suggested in past work [Wil92; Mni+16]"

<hr/>其中，估计advantage value用到了GAE (Generalized Advantage Estimator)：


了解GAE可以看下 这篇 和 这篇
<hr/>伪代码

PPO算法的大致流程，只需要在VPG基础上做较小的改动，即将目标函数换掉，并在每次更新时对该objective多次梯度上升即可

<hr/>

关于学习率，NPG中用了KL-div求的，含有Hessian二阶约束；Trpo在前面又乘了个α^j；但好像在PPO中的学习率不含有Hessian，好像直接用的SGD

<hr/>AC训练过程：


每轮迭代中，并行开N个Actor (θ') 与环境交互，采样N条长度为T的trajectory，即共收集NT个样本
使用GAE估计advantage value，和action probability一起存入buffer
从buffer中采样M (Minibatch Size)个样本，训练K个epoch (K其实是一个样本复用次数)
OpenAI baseline中的一般设置是，K = 3，Minibatch Size = NT / 4，则一轮迭代中，通过 SGD，参数更新12次

NoiseFloor

详细！

Baste

知乎的排版不能调整图片的大小，size不同的图片多了就显得有点乱。还是适应用CSDN写博[捂脸]

ainatipen

[调皮]