13、近端策略优化Proximal Policy Optimization (PPO) 算法：从原理到实践

基于LunarLander登陆器的PPO强化学习（含PYTHON工程）

PPO对标的是TRPO算法，改进了其性能。也有学者认为其理论性不强，但实践效果往往不错。

TRPO的缺点：

1. 无法处理大参数矩阵：尽管使用了共轭梯度法，TRPO仍然难以处理大的 Fisher矩阵，即使它们不需要求逆
2. 近似值可能会违反KL约束，从而导致分析得出的步长过大，超出限制要求
3. 我们不能利用一阶随机梯度优化器，例如ADAM
4. TRPO 很复杂：TRPO很难解释、实现和调试。当训练没有产生预期的结果时，确定如何提高性能可能会很麻烦。实际也无法保证每一步都能带来改善。

TRPO的改进：近端策略优化算法（PPO）

其他算法：
07、基于LunarLander登陆器的DQN强化学习案例（含PYTHON工程）

08、基于LunarLander登陆器的DDQN强化学习（含PYTHON工程）

09、基于LunarLander登陆器的Dueling DQN强化学习（含PYTHON工程）

10、基于LunarLander登陆器的Dueling DDQN强化学习（含PYTHON工程）

11、基于LunarLander登陆器的A2C强化学习（含PYTHON工程）

TRPO的LunarLander登陆器强化学习（含PYTHON工程）：
11.1、信赖域策略优化算法TRPO强化学习-从理论到实践
11.2、信赖域策略优化算法TRPO强化学习-约束优化求解
11.3、信赖域策略优化算法TRPO强化学习-运用实践

参考：Proximal Policy Optimization (PPO) 算法理解：从策略梯度开始

0、近端策略优化PPO核心思路

在传统的策略梯度算法中，我们根据目标函数梯度${?}_{\theta }J(\theta )$和步长$\alpha$更新策略权重，这样的更新过程可能会出现两个常见的问题：

1. 过冲（Overshooting）：更新错过了奖励峰值并落入了次优策略区域
2. 下冲（Undershooting）：在梯度方向上采取过小的更新步长会导致收敛缓慢

在监督学习问题中，overshooting并不是什么大问题，因为数据是固定的，我们可以在下一个epoch中重新纠正。

但在强化学习问题中，如果因为overshooting陷入了一个较差的策略区域，则未来的样本批次可能不会提供太多有意义的信息，用较差的数据样本再去更新策略，从而陷入了糟糕的正反馈中无法恢复。较小的学习率可能会解决这个问题，但会导致收敛速度变慢的undershooting问题。

为了避免overshooting带来的严重后果，一种直觉方法是基于KL散度限制每次更新步长的上限：
$$\Delta {\theta }^{?}=\underset{{\mathcal{D}}_{\mathrm{KL}}({\pi }_{\theta }\Vert {\pi }_{\theta +\Delta \theta })\le ?}{\mathrm{argmax}}J(\theta +\Delta \theta )$$

在TRPO中，结合了自然梯度法的思想，KL散度限制条件被实际运用，具体原理可以参考：TRPO的LunarLander登陆器强化学习（含PYTHON工程）：
11.1、信赖域策略优化算法TRPO强化学习-从理论到实践
11.2、信赖域策略优化算法TRPO强化学习-约束优化求解
11.3、信赖域策略优化算法TRPO强化学习-运用实践

如果说，TRPO结合了自然梯度法的思想，并进行KL散度限制。那么PPO实际上是基于普通的A2C与（随机）梯度下降的框架，在此基础上对更新步长进行限制得到的（PPO_v1使用KL散度进行约束，PPO2直接使用clip对步长进行限制）。下面介绍其具体的理论！

1、参数定义

Reward：奖励R，每次（每一步）与环境进行交互都会获得奖励，玩一整局，奖励的和自然是越多越好。

Q(s,a)：动作价值函数，其输入为当前状态和要执行的动作，输出为该动作能带来多大的价值，因此，一种贪心的方法是选择能够使Q(s,a)最大动作执行。
$$Q_{\pi }(s_t,a_t)=\mathbb{E}{s}_{t+1},a_{t+1},\dots \left[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})\right]$$
Q(s,a)的维度等于动作空间的维度。打个简单的比方，假设我现在有两个动作，向北去捡芝麻，向南去捡西瓜。从最终获得的奖励来看，西瓜是大于芝麻的，但是如果芝麻就在我桌上，但是西瓜在20km以外，那可能我还是选择芝麻得了。那么动作价值函数可能就是（1，0.1）。1是捡芝麻的动作价值，0.1是捡西瓜的动作价值，虽说西瓜好吃，但是太远了，所以其动作价值打分特别低。

V(s)：状态价值函数，是Q函数的期望。因为期望的积分动作消去了动作A，因此状态价值函数V可以用来直观的反应一个状态的好坏。其实际上是Q(s,a)对不同a的加权平均。
例如，自家高低三路被破，依据这个状态我们就知道现在的状态打分不太行。状态打分不行的原因是每个动作都不会带来太高的打分（都要输了）。
$$V_{\pi }(s_t)={\mathbb{E}}_{A_t}[Q_{\pi }(s_t,A_t)\mid s_t]$$

A：优势函数，其数值等于动作价值函数减去状态价值函数，相当于动作价值Q(s,a)减去了其baseline：
$$A_{\pi }(s,a)=Q_{\pi }(s,a)?V_{\pi }(s)$$

2、Actor网络构建

2.1 Actor网络基础

Actor网络的核心目的是在一局游戏中获得尽可能多的奖励：
$${\theta }^{?}=\arg \underset{\theta }{\max }\underset{J(\theta )}{\underbrace{E_{\tau ～p_{\theta }(\tau )}\left[\sum _{t}r({\mathbf{s}}_t,{\mathbf{a}}_t)\right]}}$$

虽然目标函数写成了期望的形式，但是在实际的过程中，我们都是使用蒙特卡洛采样获取其近似的数据：
$$J(\theta )=E_{\tau ～p_{\theta }(\tau )}\left[\sum _{t}r({\mathbf{s}}_t,{\mathbf{a}}_t)\right]\approx \frac{1}{N}\sum _i\sum _{t}r({\mathbf{s}}_{i,t},{\mathbf{a}}_{i,t})$$

回到理论的表达式，在此要使用梯度下降法，首先要对目标函数求导。简单的直接求导自然是不行的，因为环境中所有数据的获取都依赖与蒙特卡洛采样获取，因此我们需要将其进行变换写为期望的形式：
$${?}_{\theta }J(\theta )=\int {?}_{\theta }{\pi }_{\theta }(\tau )r(\tau )d\tau =\int {\pi }_{\theta }(\tau ){?}_{\theta }\log {\pi }_{\theta }(\tau )r(\tau )d\tau =E_{\tau ～{\pi }_{\theta }(\tau )}[{?}_{\theta }\log {\pi }_{\theta }(\tau )r(\tau )]$$

关注一下其中的${?}_{\theta }\log {\pi }_{\theta }$的求解过程，实际过程中这一项会直接包含在softmax层的导数之中。这是为啥呢？看一下交叉熵的公式，策略网络$\pi$的输出实际上就是概率分布，当然$r(\tau )$可以作为sample_weight体现在其中。-参考softmax loss详解，softmax与交叉熵的关系：
$$L=?log{p}_{i,Y(i)}$$

2.2 重要性采样

为了提升样本的利用率，利用同一批数据进行多次训练，PPO算法中使用了重要性采样的思路。仔细观察原来的目标函数的梯度式子（很多算法在不一定使用奖励$r(\tau )$，也有使用动作价值函数Q或者动作优势函数A的，但是思路不变）：
$${?}_{\theta }J(\theta )=E_{\tau ～{\pi }_{\theta }(\tau )}[{?}_{\theta }\log {\pi }_{\theta }(\tau )r(\tau )]$$

假设我们利用策略网络${\pi }_{\theta }$与环境进行了交互并得到了一批数据，得到了在策略${\pi }_{\theta }$的轨迹$\tau$，那么我们运用梯度下降的更新式子就可以得到一个更好的策略${\pi }_{\theta }^{\prime }$：
$${\theta }^{\prime }=\theta ?\alpha J^{{}^{\prime }}\left(\theta \right)$$

如果我们需要进行下一次的更新，我们需要用到的策略函数的梯度式子是：
$${?}_{{\theta }^{\prime }}J({\theta }^{\prime })=E_{\tau ～{\pi }_{{\theta }^{\prime }}(\tau )}[{?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )]$$

其中${\pi }_{\theta }^{\prime }$我们是已知的，就是期望括号内的内容${?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )$我们并不难获得。但是，我们的轨迹数据$\tau ～{\pi }_{{\theta }^{\prime }}(\tau )$，这就需要我们使用新的策略${\pi }_{\theta }^{\prime }$重新和环境进行交互才能获得，因此我们原来用来训练的数据训练一次就要丢掉了，很浪费有没有。

重要性采样就是争对这一问题进行改进，该问题的核心是期望的分布$\tau ～{\pi }_{\theta }(\tau )$和梯度项${?}_{\theta }\log {\pi }_{\theta }(\tau )$依赖于同一个策略网络。重要性采样的基本公式如下所示（可以更换期望服从的分布）：
$$\begin{array}{rl}{E}_{x～p(x)}[f(x)]& =\int p(x)f(x)dx\\ & =\int \frac{q(x)}{q(x)}p(x)f(x)dx\\ & =\int q(x)\frac{p(x)}{q(x)}f(x)dx\\ & =E_{x～q(x)}\left[\frac{p(x)}{q(x)}f(x)\right]\end{array}$$
由此可得：
$${?}_{{\theta }^{\prime }}J({\theta }^{\prime })=E_{\tau ～{\pi }_{\theta }(\tau )}\left[\frac{{\pi }_{{\theta }^{\prime }}(\tau )}{{\pi }_{\theta }(\tau )}{?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )\right]$$

小伙伴看到这个式子可以还不太理解，在此解释一下下。

1. 假设我们利用策略网络${\pi }_{\theta }$与环境进行了交互并得到了一批数据，得到了在策略${\pi }_{\theta }$的轨迹$\tau$，那么我们运用梯度下降的更新式子就可以得到一个更好的策略${\pi }_{\theta }^{\prime }$。此时使用的式子可以是原来的${?}_{\theta }J(\theta )=E_{\tau ～{\pi }_{\theta }(\tau )}[{?}_{\theta }\log {\pi }_{\theta }(\tau )r(\tau )]$。
2. 使用梯度下降法，我们得到了一个新策略${\pi }_{\theta }^{\prime }$，如果使用原来的公式${?}_{{\theta }^{\prime }}J({\theta }^{\prime })=E_{\tau ～{\pi }_{{\theta }^{\prime }}(\tau )}[{?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )]$，我们会说没有新的策略${\pi }_{\theta }^{\prime }$重新和环境进行交互的轨迹$\tau ～{\pi }_{{\theta }^{\prime }}(\tau )$。此时我们应该使用公式${?}_{{\theta }^{\prime }}J({\theta }^{\prime })=E_{\tau ～{\pi }_{\theta }(\tau )}\left[\frac{{\pi }_{{\theta }^{\prime }}(\tau )}{{\pi }_{\theta }(\tau )}{?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )\right]$，不就万事大吉了。
3. 使用梯度下降法，我们得到了一个更加新的策略${\pi }_{\theta }^{\prime }’$，继续使用${?}_{{\theta }^{\prime \prime }}J({\theta }^{\prime \prime })=E_{\tau ～{\pi }_{\theta }(\tau )}\left[\frac{{\pi }_{{\theta }^{\prime \prime }}(\tau )}{{\pi }_{\theta }(\tau )}{?}_{{\theta }^{\prime \prime }}\log {\pi }_{{\theta }^{\prime \prime }}(\tau )r(\tau )\right]$，就又可以得到${\pi }_{\theta }^{\prime \prime \prime }$了，这样策略网络${\pi }_{\theta }$与环境交互的数据$\tau$就可以被用于训练很多次了。

2.3 PPO Clip

PPO_v1使用KL散度进行约束，PPO2直接使用clip对步长进行限制。此处不介绍PPO_v1了，可以参考Proximal Policy Optimization (PPO) 算法理解：从策略梯度开始。

PPO Clip直接限制策略可以改变的范围。我们重新定义了替代优势：
$$\begin{array}{c}{\mathcal{L}}_{{\pi }_{\theta }}^{CLIP}({\pi }_{{\theta }_k})\\ ={\mathbb{E}}_{\tau ～{\pi }_{\theta }}\left[\sum _{t=0}^T\left[\min ({\rho }_t({\pi }_{\theta },{\pi }_{{\theta }_k})A_t^{{\pi }_{{\theta }_k}},\mathrm{clip}({\rho }_t({\pi }_{\theta },{\pi }_{{\theta }_k}),1??,1+?)A_t^{{\pi }_{{\theta }_k}}\right)\right]\end{array}$$

其中， ${\rho }_t$为重要性采样：
$${\rho }_t(\theta )=\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }^{\prime }}(a_t\mid s_t)}$$

clip为截断函数，当重要性采样超出规定的上或下限后，函数会返回对应的上或下限。实际上就是限制两次策略${\pi }_{\theta }$和${\pi }_{{\theta }^{\prime }}$不能变化太大。

2.4 使用广义优势函数(GAE)代替$r({\mathbf{s}}_t,{\mathbf{a}}_t)$

注意观察新的更新式子，其中包含每一步环境给出的奖励$r({\mathbf{s}}_t,{\mathbf{a}}_t)$ ：
$${?}_{{\theta }^{\prime }}J({\theta }^{\prime })=E_{\tau ～{\pi }_{\theta }(\tau )}\left[\frac{{\pi }_{{\theta }^{\prime }}(\tau )}{{\pi }_{\theta }(\tau )}{?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )\right]$$

但是在实际过程中，这会给训练带来消极的影响。这点在AC算法的baseline和Dueling DQN中都有提及，其主要原因是奖励 $r({\mathbf{s}}_t,{\mathbf{a}}_t)$的均值不一定为0。解决的办法也非常简单，我们可以使用动作优势函数A或者TD error来进行更新。优势函数A已经在1、参数定义中初步介绍了，而A2C算法中TD error的表达式为(具体的推导过程参考【王树森】深度强化学习(DRL)的P16。)：
$$\begin{array}{lc}\text{TD?target:}& y_t=r_t+\gamma ?\nu (s_{t+1};\mathbf{w}).\\ & \\ \text{TD?error:}& {\delta }_t=y_t?\nu (s_t;\mathbf{w}).\end{array}$$
当然，还有很多其他形式（GAE 广义优势估计）：

而在PPO算法中，我们往往使用广义优势估计Generalized advantage estimation （GAE），GAE方法对这n个k步估计量（k从1到n）进行加权平均，平衡了TD方法和MC方法，同时也平衡了偏差和方差：
$$\begin{array}{rl}{\hat{A}}_t^{\mathrm{GAE}(\gamma ,\lambda )}& :=(1?\lambda )\left({\hat{A}}_t^{(1)}+\lambda {\hat{A}}_t^{(2)}+{\lambda }^2{\hat{A}}_t^{(3)}+\dots \right)\\ & =(1?\lambda )\left({\delta }_t^V+\lambda \left({\delta }_t^V+\gamma {\delta }_{t+1}^V\right)+{\lambda }^2\left({\delta }_t^V+\gamma {\delta }_{t+1}^V+{\gamma }^2{\delta }_{t+2}^V\right)+\dots \right)\\ & =(1?\lambda )({\delta }_t^V\left(1+\lambda +{\lambda }^2+\dots \right)+\gamma {\delta }_{t+1}^V\left(\lambda +{\lambda }^2+{\lambda }^3+\dots \right)\\ & {\gamma }^2{\delta }_{t+2}^V\left({\lambda }^2+{\lambda }^3+{\lambda }^4+\dots \right)+\dots )\\ & =(1?\lambda )\left({\delta }_t^V\left(\frac{1}{1?\lambda }\right)+\gamma {\delta }_{t+1}^V\left(\frac{\lambda }{1?\lambda }\right)+{\gamma }^2{\delta }_{t+2}^V\left(\frac{{\lambda }^2}{1?\lambda }\right)+\dots \right)\\ & =\sum _{l=0}^{\infty }(\gamma \lambda {)}^l{\delta }_{t+l}^V\end{array}$$

当$\lambda =0$时，其会退化为TD Error，可能存在大偏差。当$\lambda =1$，会考虑全局游戏的优势，可能会有大的方差。

3、Critic网络构建

Critic网络的输入往往是状态矢量，输出为状态价值函数V，其中yt是TD Target。在使用广义优势进行估计的情况下，TD Error被GAE函数替换，因此：
$${\hat{A}}_t^{\mathrm{GAE}(\gamma ,\lambda )}=y_t?\nu (s_t;\mathbf{w})$$

此时在代码中，TD Target被称为n_step_targets。其计算公式为：
$$y_t={\hat{A}}_t^{\mathrm{GAE}(\gamma ,\lambda )}+\nu (s_t;\mathbf{w})$$

Critic训练的实质就是让TD Target接近$\nu (s_t;\mathbf{w})$，因此，其使用均方误差函数。

4、关键代码对应

4.1 广义优势函数和n_step_targets计算

$$\begin{array}{rl}{\hat{A}}_t^{\mathrm{GAE}(\gamma ,\lambda )}& =\sum _{l=0}^{\infty }(\gamma \lambda {)}^l{\delta }_{t+l}^V\end{array}$$
其中（如果已经done了，那么第二项为0，也就是没有t+1的状态了）：
$${\delta }_t=y_t?\nu (s_t;\mathbf{w})=r_t+\gamma ?\nu (s_{t+1};\mathbf{w})?\nu (s_t;\mathbf{w})$$

def get_gaes(self, rewards, dones, values, next_values, gamma=0.99, lamda=0.9, normalize=True):
    deltas = [r + gamma * (1 - d) * nv - v for r, d, nv, v in zip(rewards, dones, next_values, values)]
    deltas = np.stack(deltas)
    gaes = copy.deepcopy(deltas)
    for t in reversed(range(len(deltas) - 1)):
        gaes[t] = gaes[t] + (1 - dones[t]) * gamma * lamda * gaes[t + 1]

    target = gaes + values
    if normalize:
        gaes = (gaes - gaes.mean()) / (gaes.std() + 1e-8)
    return np.vstack(gaes), np.vstack(target)

4.2 重要性采样和CLIP

重要性采样公式：
$${?}_{{\theta }^{\prime }}J({\theta }^{\prime })=E_{\tau ～{\pi }_{\theta }(\tau )}\left[\frac{{\pi }_{{\theta }^{\prime }}(\tau )}{{\pi }_{\theta }(\tau )}{?}_{{\theta }^{\prime }}\log {\pi }_{{\theta }^{\prime }}(\tau )r(\tau )\right]$$
PPO Clip直接限制策略可以改变的范围。我们重新定义了替代优势：
$$\begin{array}{c}{\mathcal{L}}_{{\pi }_{\theta }}^{CLIP}({\pi }_{{\theta }_k})\\ ={\mathbb{E}}_{\tau ～{\pi }_{\theta }}\left[\sum _{t=0}^T\left[\min ({\rho }_t({\pi }_{\theta },{\pi }_{{\theta }_k})A_t^{{\pi }_{{\theta }_k}},\mathrm{clip}({\rho }_t({\pi }_{\theta },{\pi }_{{\theta }_k}),1??,1+?)A_t^{{\pi }_{{\theta }_k}}\right)\right]\end{array}$$

其中， ${\rho }_t$为重要性采样：
$${\rho }_t(\theta )=\frac{{\pi }_{\theta }(a_t\mid s_t)}{{\pi }_{{\theta }^{\prime }}(a_t\mid s_t)}$$

def ppo_loss(self, y_true, y_pred):
    # Defined in https://arxiv.org/abs/1707.06347
    advantages, prediction_picks, actions = y_true[:, :1], y_true[:, 1:1 + self.action_space], y_true[:,
                                                                                               1 + self.action_space:]
    LOSS_CLIPPING = 0.2
    ENTROPY_LOSS = 0.001

    prob = actions * y_pred
    old_prob = actions * prediction_picks

    prob = K.clip(prob, 1e-10, 1.0)
    old_prob = K.clip(old_prob, 1e-10, 1.0)

    ratio = K.exp(K.log(prob) - K.log(old_prob))

    p1 = ratio * advantages
    p2 = K.clip(ratio, min_value=1 - LOSS_CLIPPING, max_value=1 + LOSS_CLIPPING) * advantages

    actor_loss = -K.mean(K.minimum(p1, p2))

    entropy = -(y_pred * K.log(y_pred + 1e-10))
    entropy = ENTROPY_LOSS * K.mean(entropy)

    total_loss = actor_loss - entropy
    
    return total_loss

4.3 使用同一批数据多次更新

# 得到1000个数据训练10次
# training Actor and Critic networks
a_loss = self.Actor.Actor.fit(states, y_true, epochs=self.epochs, verbose=0, shuffle=self.shuffle)
c_loss = self.Critic.Critic.fit([states, values], target, epochs=self.epochs, verbose=0, shuffle=self.shuffle)

5、基于LunarLander登陆器的PPO强化学习

代码在最上面链接（来自github，修改一下滴，但是原来链接找不到了），跑个200分比较轻松，比TRPO要好一些吧，训练过程如下所示：

进行测试，效果杠杠的：