主题：
- 为何Policy Gradient有效
- 将Policy Gradient视为Policy Iteration
- 对policy gradient进行受限优化
- 自然梯度和trust regions
1. 为何Policy Gradient有效呢？
首先回顾下之前的REINFORCE算法：
其中的梯度可以通过采样进行计算可以表示为：
为了降低variance，引入baseline之后，可以把梯度转换为优势函数的形式。
那么则我们可以把PG的过程看做两步，先根据评估A，然后使用A去更新
。
这个过程和之前的policy iteration算法有些类似：
2. 将Policy Gradient视为Policy Iteration
PG的方法有两个比较重要的问题：一是采样效率，需要引入IS转换为off-policy。第二个问题是来自梯度更新，由于它是在参数空间上做的更新，但是其实参数空间并不等价于policy空间，有时候微小的变化会导致Policy的巨大改变。
所以就有了两个诉求：
- 如何在引入IS的情况下尽可能避免policy差异过大。
- 如何在保证policy不发生突变的情况下进行参数的更新。
这里我们根据引入IS的情况，量化分析下问题的影响程度。如果我们可以将policy gradient转化为policy iteration，那么就可以借助policy iteration中的证明方法得到policy gradient是否可以稳定提升，误差有多少。而这其实就是要计算更新前后的policy是否变好。
所以从policy iteration的角度来看，就需要计算update前后policy的关系，也就是所谓的Relative policy performance identity，具体推导如下：
结论是：
使用IS然后展开：
这里只留下了最外层的的期望，如果可以将这个替换为，那么就可以通过最大化这个Relative policy performance identity来获得新的参数。
3. 分布变化的约束
只要两个policy足够接近，那么两个policy关于某个state的probability就可以足够接近。那么只要policy足够接近，就可以对两个期望做替换。先看看确定性策略的情况：
再证明是任意分布的情况：
在确定性策略与任意分布的情况下，分布的变化都可以被bouding，并且具有同样的形式。
这样我们确实就可以通过最大化Relative policy performance identity来获得新的参数，但是他的条件是两个策略足够得接近。
3.1 使用KL散度约束边界
通过上面的推导，我们知道可以对策略的概率做差的绝对值，但是在实际实施上难以优化。为了有可行性从而引入了KL散度。两个分布之间的KL散度边界以及KL散度的定义为：
即如果我们将KL散度进行约束，那么原始约束函数也就满足，两者存在转化的等价性。所以优化的目标也就转化为如下的形式，约束发生了改变，问题更容易优化了。
4. KL散度约束的实施
KL散度约束的实施可以有几种方法：
4.1 Dual gradient descent
第一种方法叫：Dual gradient descent
可以拉格朗日算子进行求解最优化问题，先将损失转化为拉格朗日乘子的形式，然后进行迭代求解：
从直观上理解，将约束引入目标函数后，乘子 也是一个需要优化的参数。当约束违反程度大的时候，后面拉格朗日项就变成特别大的负项，如果需要最大化这个目标，则需要将乘子变大，反之依然。通过对这个乘子的调节，进而修正约束部分的重要性，从而达到自适应优化的目标。
4.2 策略梯度（policy gradient）
第二种方法是: Policy Gradient
可以尝试对目标函数进行适当的处理，降低优化的难度？我们可以尝试对目标函数进行一阶泰勒展开，我们将原来的目标函数转换为：
由于这里所有操作的前提是与的差距很小，所以在参数对应的位置可以进行整体性的替换替换为。
这个其实也就是policy gradient的梯度公式，那么除了约束的部分，整体也就和policy gradient没有差别了。那么是否可以将它当作一个正常的policy gradient进行操作？Gradient ascent的操作其实可以理解为在parameter space上做一个小的修改，也就是说它相当于在parameter space上做约束的优化；
这种时候，它其实也就是我们常见的gradient ascent方法加一个动态学习率:
从前面的推导过程，我们就把policy iteration带回了policy gradient，policy gradient也就是相当于对参数空间做约束的策略提升的过程。而它的问题也就来自这里，parameter space与policy space是不匹配的。,与,不是一样的。
也就是说这种约束是保证不了Monotonic Improvement Theory的要求的，所以它的优化会比较不稳定。基于这个问题，下面引入了natural gradient去解决这个问题。
4.3 自然策略梯度（Natural Policy Gradient）
第三种方法是: Natural Policy Gradient
我们考虑对KL散度使用二阶的泰勒展开，其中其中F是KL散度的Hessian函数，也被称为Fisher信息矩阵，它可以通过样本进行估计：
所以整体上梯度更新就可以按照如下的形式：
但是这种二阶的 方法计算复杂度过高。
4.4 TRPO（Trust Region Policy Optimization）
TRPO主要针对自然梯度存在的两个问题提出了解决方案：第一个就是求逆矩阵的高复杂度问题，第二个则是对KL散度做的近似中可能存在的约束违反的问题做了预防。
首先就是求逆操作的高复杂度问题，TRPO将它转化为求解线性方程组，并利用共轭梯度算法（conjugate gradient algorithm）进行近似求解（这里有要求inverse matrix是positive definite的，所以在TRPO中有对目标函数的约束）。总体而言，它的过程如下：
其次，针对如何对违反约束做限制，这里用的是exponential decay line search的方式，也就是对于一个样本，如果某次更新违反了约束，那么就把它的系数进行指数衰减，从而减少更新的幅度，直到它不再违反约束或者超过一定次数衰减则抛弃这次的数据。
4.5 PPO（Proximal Policy Optimization）
相比上面使用自然梯度进行KL约束的近似，PPO则另辟蹊径，它并不直接求解这个约束，而是通过一些启发式的方法达到这个目的，论文中主要提出如下两类。
首先是Adaptive KL penalty，它直接将KL散度从约束转化为惩罚项，作为目标函数的一部分，每次更新时候则计算当前迭代对KL散度的违反程度，如果KL值过大，则增大它的系数，强化这个惩罚项的重要程度，反之亦然。
而第二种则是Clipped Surrogate Objective，对目标做裁剪。前面使用到KL散度是要约束策略空间，从而约束trajectory的分布。那么这里则直接对这个概率比值做clip，设置一个阈值，直接从根源上限制策略空间的差异。
原先的目标是如下形式的，其中：
那么clip后的式子也就是如下形式， 是一个比较小的阈值：
基于这两种方式的更新，虽然在理论上没有保证，但是在实践中往往高效且有不错的效果。
