【强化学习】PPO的理论推导

jquave

一、前言

PPO(Proximal Policy Optimization) 是一种On Policy强化学习算法，由于其实现简单、易于理解、性能稳定、能同时处理离散\连续动作空间问题、利于大规模训练等优势，近年来收到广泛的关注。
但是如果你去翻PPO的原始论文[1]，你会发现作者对它底层数学体系的介绍几乎是一笔带过。相信很多朋友跟我一样，最开始学习PPO算法的时候，仅停留在了代码如何复现，对于其理论推导几乎一无所知。因此最近花了些时间，将PPO的相关论文系统地研读了一遍，写下此文，以作笔记，亦作分享。水平有限，如有不足，还望指正，谢谢！

Math Warning！本文含有较多的数学推导过程，看着可能会比较辛苦。对于仅想拿代码跑实验的朋友，可以直接去我的Github下载PPO的代码：https://github.com/XinJingHao/RL-Algorithms-by-Pytorch
另外，阅读本文需要对强化学习的基础知识有所了解

二、从Policy Gradient到PPO

PPO本质上是一种PG(Policy Gradient)算法，从1999年PG被Sutton提出至今，一共经历了以下四次演变：



PPO的演变史

对于PG不太熟悉的朋友可以先读一下我的这篇文章（不过不用担心，即使对PG不是很熟悉，应该也能看懂本文后面的内容）：
在正式推导之前，我们先做一些符号上的声明。首先定义强化学习的优化目标：
J(\pi)=\mathbb{E}_{s_0 \sim \rho_{0}}\left[V_{\pi}\left(s_0\right)\right]\\ 上式中， s_0 为初始状态， \rho_0 为初始状态分布， V_{\pi}\left(s_0\right) 为在策略 \pi 下 s_0 的状态价值函数。现在让我们思考一个问题，在学习过程中，每次策略更新后，新策略 \pi_{new} 比旧策略 \pi_{old} 到底好了多少呢？Kakade等人[2]给出了以下答案：
J\left(\pi_{\text {new }}\right)=J\left(\pi_{\text {old }}\right)+\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[\sum_{t=0}^{\infty} \gamma^t A_{\pi_{\text {old }}}\left(s_t, a_t\right)\right]\\ \tag{1}其中， s_0 \sim \rho_0,  a_t \sim \pi_{new}( ·|s_t) ， s_{t+1} \sim P(s_{t+1}|s_t,a_t) , P(s_{t+1}|s_t,a_t) 为环境转移概率, \gamma 为折扣因子， A_{\pi}(s_t,a_t) 是优势函数，其定义为 A_{\pi}(s_t, a_t)=\mathbb{E}_{s_{t+1} \sim P\left(s_{t+1} \mid s_t, a_t\right)}\left[r(s_t)+\gamma V_{\pi}\left(s_{t+1}\right)-V_{\pi}(s_t)\right] ，公式(1)的证明见附录A-1。
公式(1)非常直观地告诉我们，每次策略提升的量=在 \pi_{new} 生成的轨迹上，每一 状态-动作对 折扣优势函数期望之和。同时，个人认为深刻理解公式(1)非常重要，它几乎诠释了所有强化学习算法都在干的一件事：每次策略更新时，只要让\pi_{new}选择 A_{\pi_{old}}(s_t,a_t) \geq 0 的动作，则\pi_{new}一定比 \pi_{old} 好（否则策略已经收敛至最优策略），因为这种情况下 J\left(\pi_{\text {new }}\right)-J\left(\pi_{\text {old }}\right)=\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[\sum_{t=0}^{\infty} \gamma^t A_{\pi_{\text {old }}}\left(s_t, a_t\right)\right] \geq 0 。不妨联想一下Q-learning和DDPG等算法是不是都在做这件事呢？此外，公式(1)也是PPO算法的理论根基，现在让我们继续往下推导。
三、TRPO (Trust Region Policy Optimization)[3]

熟悉PPO算法的朋友应该清楚，PPO的前身是TRPO，因此，笔者觉得很有必要介绍一下TRPO的推导过程，以便加深对PPO算法的理解。不过如果你对TRPO不感兴趣，直接读下一节也是可以的。

公式(1)是在时间层面对 \gamma^t A_{\pi_{\text {old }}}(s_t,a_t) 进行求和的，我们也可以在状态空间层面对其进行求和，此时有以下形式：
J(\pi_{new})=J\left(\pi_{\text {old }}\right)+\sum_s \rho_{\pi_{\text {new }}}(s) \sum_a \pi_{\text {new }}(a \mid s) A_{\pi_{\text {old }}}(s, a) \\ \tag{2} 其中 \rho_{\pi}(s)=\sum_{t=0}^{\infty}\gamma^tPr(s_t=s|\pi) 称作 (unnormalized) discounted visitation frequencies，公式(2)的证明见附录A-2。从公式(2)同样可以看出策略改进定理(Policy Improvement Theorem)，即只要让\pi_{new}选择 A_{\pi_{old}}(s,a) \geq 0 的动作，则\pi_{new}一定比 \pi_{old} 好（否则策略已经收敛至最优策略）。不过，TRPO的作者Schulman等人[3]认为，由于以下两个因素，我们很难利用公式(2)来直接优化我们的策略：

• 在实际算法中，由于估计误差(estimation error)和拟合误差(approximation error)的存在，优势函数 A_{\pi}(s,a) 的估计是不准确的。因此，当我们根据估计的优势函数 \hat{A}_{\pi}(s,a) 来改进策略时，可能存在 \hat{A}_{\pi}(s,a)\geq0 而 A_{\pi}(s,a)\leq0 的情况，所以不一定能保证策略提升。
  
• 由于 \pi_{new} 和 \rho_{\pi_{new}}(s) 存在复杂的耦合关系，公式(2)很难直接优化。
  

一些讨论：我认为第一个因素是有说服力的，比如DDQN[4]就是从减小过拟合的角度出发，改进了DQN算法，又如TD3[5]就是从减小函数拟合误差的角度出发，改进了DDPG算法。两者都是在尽力减少优势函数(或者动作价值函数)估计的误差以提高策略提升的有效性。但个人觉得第二个因素不是太站得住脚，因为即使 \rho_{\pi_{new}}(s) 难以获得，但 \rho_{\pi_{new}}(s)\geq0 是肯定的，因此，只要保证每次策略改进 \sum_a \pi_{\text {new }}(a \mid s) A_{\pi_{\text {old }}}(s, a)\geq0 就能保证 \sum_s \rho_{\pi_{\text {new }}}(s) \sum_a \pi_{\text {new }}(a \mid s) A_{\pi_{\text {old }}}(s, a)\geq0 ，只是说具体改进了多少我们无法计算。但只要一直策略改进下去，理论上策略最终都会收敛至最优策略。

TRPO尝试从第二个因素着手，保证策略提升的有效性。它首先构造了 J(\pi_{new}) 在初始点 \pi_{old} 处的局部拟合值:
L_{\pi_{old}}(\pi_{new})=J\left(\pi_{\text {old }}\right)+\sum_s \rho_{\pi_{\text {old }}}(s) \sum_a \pi_{\text {new }}(a \mid s) A_{\pi_{\text {old }}}(s, a) \\ \tag{3}构造 L_{\pi_{old}}(\pi_{new}) 有两个好处。首先，公式(3)中的状态分布使用的 \rho_{\pi_{old}}(s) ，因此我们可以直接在 \pi_{old} 收集的数据上做优化，避免了公式(2)中 \pi_{new} 和 \rho_{\pi_{new}}(s) 的复杂耦合关系。其次，如果策略是参数化的 \pi_{\theta} ，则 L_\pi 和 J 一阶近似等价（证明见Kakade等人的论文[2]），即
\begin{aligned} L_{\pi_{\theta_0}}\left(\pi_{\theta_0}\right) &=J\left(\pi_{\theta_0}\right) \\ \left.\nabla_\theta L_{\pi_{\theta_0}}\left(\pi_\theta\right)\right|_{\theta=\theta_0} &=\left.\nabla_\theta J\left(\pi_\theta\right)\right|_{\theta=\theta_0} \end{aligned} \\ \tag{4}公式(4)告诉我们，对于一次足够小的更新 \pi_{\theta_0}\rightarrow\pi_{new} ，如果能够提升L_\pi，则同样能提升 J ，但并未明确给出多小的更新够小。为解决这一问题，Kakade等人[2]提出了CPI(Conservative Policy Iteration)。在CPI中，我们以\pi_{old}表示当前策略，假设我们能解决 \pi'={\underset{\pi'}{argmax} L_{\pi_{old}}(\pi')} 即 \pi'(a|s)=\underset{a}{argmax} A_{\pi_{old}}(s,a) , 则新策略为以下混合策略:\pi_{\text {new }}(a \mid s)=(1-\alpha) \pi_{\mathrm{old}}(a \mid s)+\alpha \pi^{\prime}(a \mid s) \\ \tag{5}使用CPI的更新方式，Kakade等人[2]给出了以下结果
J\left(\pi_{\text {new }}\right) \geq L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma(1-\alpha))(1-\gamma)} \alpha^2 \\ \tag{6} 其中， \epsilon=\underset{s}{max }\left|\mathbb{E}_{a \sim \pi^{\prime}(a \mid s)}\left[A_{\pi_{old}} (s, a)\right]\right| ，结合下图能够更好地理解公式(6)


公式(6)中不等式右边部分可以看做按CPI方式更新时 策略改进的下界（图中蓝色曲线），而 -\frac{2 \epsilon \gamma}{(1-\gamma(1-\alpha))(1-\gamma)} \alpha^2 可以理解为惩罚项（图中绿色曲线），可以看到，当 \alpha 足够小时，可以保证 L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma(1-\alpha))(1-\gamma)} \alpha^2 \geq J\left(\pi_{\text {old}}\right)\\再结合公式(6)可知，用CPI方式更新策略时，一个足够小的 \alpha 可以保证策略提升，即 J\left(\pi_{\text {new }}\right) \geq J\left(\pi_{\text {old}}\right) 。同时，由于 \alpha,\gamma\in[0,1] ，可以对公式(6)进一步简化 \begin{align}  J\left(\pi_{\text {new }}\right) & \geq L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma(1-\alpha))(1-\gamma)} \alpha^2 \\  & \geq L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma)^2} \alpha^2   \end{align} \tag{7}
由于实际问题中公式(5)所示的混合策略是难以求解的，因此CPI并不实用。为解决这一问题，Schulman等人[3]对公式(7)进行了进一步拓展，证明了当 \alpha=D^{max}_{TV}(\pi_{old},\pi_{new}) 时，公式(7)依然成立，此时有 J\left(\pi_{\text {new }}\right) \geq L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-CD^{max}_{TV}(\pi_{old},\pi_{new})^2 \\ \tag{8} 其中,  C=\frac{2 \epsilon \gamma}{(1-\gamma)^2}
D^{max}_{TV}(\pi_{old},\pi_{new})=\underset{s}{max } \ D_{TV}(\pi_{old}(\cdot \mid s) \| \pi_{new}(\cdot \mid s))
D_{T V} 是 Total variation divergence，定义为 D_{T V}(p \| q)=\frac{1}{2} \sum_i\left|p_i-q_i\right|
此外，由于Total variation divergence和KL divergence还存在 D_{T V}(p \| q)^2 \leq D_{KL}(p \| q) 的关系[6]，令 D^{max}_{KL}(\pi_{old},\pi_{new})=\underset{s}{max} \ D_{KL}(\pi_{old}(\cdot \mid s) \| \pi_{new}(\cdot \mid s)) ，公式(8)还可进一步改写为： J\left(\pi_{\text {new }}\right) \geq L_{\pi_{\text {old }}}\left(\pi_{\text {new }}\right)-CD^{max}_{KL}(\pi_{old},\pi_{new}) \\ \tag{9}
<hr/>至此，我们可以在理论层面给出一种在 \pi_{old} 生成的轨迹上，通过提高策略改进下界实现策略改进的方法：将每次策略改进前的老策略记为 \pi_{i} ，策略改进后的新策略记为 \pi_{i+1} ，令 M_i(\pi)=L_{\pi_{\text {i}}}\left(\pi\right)-CD^{max}_{KL}(\pi_{i},\pi_{})  ，通过求解 \pi_{i+1}=\underset{\pi}{argmax} M_i(\pi)\\ \tag{10}
可以得到一连串单调递增的策略： J(\pi_0) \leq J(\pi_1) \leq J(\pi_2) \leq J(\pi_3) \leq ...  ，证明见附录A-3。
<hr/>将策略参数化为 \pi_{\theta}(a|s) 的情况下，我们记 D_{KL}(\theta_{old}\|\theta)(s) = D_{KL}(\pi_{\theta_{old}}(·|s)\|\pi_{\theta}(·|s)),  J(\theta)=J(\pi_{\theta}) ， L_{\theta_{old}}(\theta)=L_{\pi_{\theta_{old}}}(\pi_{\theta}) ， 公式(10)可转化为以下优化问题 \underset{\theta}{\operatorname{maximize}}\left[L_{\theta_{\mathrm{old}}}(\theta)-C D_{\mathrm{KL}}^{\max }\left(\theta_{\mathrm{old}}, \theta\right)\right] \\ \tag{11}
Schulman等人[3]认为，在实操中，如果我们使用上面理论中推荐的惩罚系数 C ，则每次策略更新的步长将会很小。一个可以大致保证每次更新有效并拥有更大的更新步长的方式是将公式(11)中带惩罚项的优化问题转换为带约束优化问题：{\underset{\theta}{\operatorname{maximize}}L_{\theta_{\mathrm{old}}}(\theta)\\ s.t. D_{\mathrm{KL}}^{\max }\left(\theta_{\mathrm{old}}, \theta\right)\leq\delta }\\ \tag{12}公式(12)的带约束优化问题中，每一个状态的KL divergence都受到约束。虽然这在理论上是正确的，但由于复杂问题中状态空间巨大，该问题几乎无法求解。因此，Schulman等人[3]对该优化问题进行了近似求解，通过定义 \bar{D}_{\mathrm{KL}}^\rho\left(\theta_1, \theta_2\right):=\mathbb{E}_{s \sim \rho}\left[D_{\mathrm{KL}}\left(\pi_{\theta_1}(\cdot \mid s) \| \pi_{\theta_2}(\cdot \mid s)\right)\right] ，将公式(12)转化为以下优化问题： {\underset{\theta}{\operatorname{maximize}}L_{\theta_{\mathrm{old}}}(\theta)\\ s.t. \bar{D}_{\mathrm{KL}}^{\rho_{\pi_{old}} }\left(\theta_{\mathrm{old}}, \theta\right)\leq\delta }\\ \tag{13}公式(13)揭示了TRPO算法的核心思想：使用 \pi_{old} 与环境互动，获得轨迹 \tau_{old} （ 该轨迹中每一个状态服从 \rho_{\pi_{old}}  分布）, 并利用\tau_{old}将策略改进为\pi_{new}, 同时保证\tau_{old}中所有状态的平均KL divergence小于某个阈值 \delta 。
四、PPO(Proximal Policy Optimization)

上一节我们介绍了TRPO，实际上求解公式(13)的带约束优化问题计算量巨大，为解决这一问题，Schulman等人[3]又给出了Conjugate gradient + Fisher information matrix的快速近似求解方案，但这也导致TRPO在实现和理解上都有着较大难度。后来Schulman等人又提出了PPO算法[1]，PPO算法在核心思想上和TRPO几乎一致，但更为简单轻便。

由公式(1)出发，我们可以得到（证明见附录A-4）：
J(\pi_{new})-J\left(\pi_{old}\right) \geq \\\frac{1}{1-\gamma} \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)} A^{\pi_{old}}(s, a)\right]-\frac{ \gamma \epsilon}{(1-\gamma)^2} \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\left|\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)}-1\right|\right] \\ \tag{14}公式(14)不等式右侧部分被称作策略改进的下界(Policy improvement lower bound；PILB)，其中第一项为代理目标(surrogate objective；SO)，第二项为惩罚项(penalty term；PT)。每次策略改进时，只要保证每次策略改进的下界为正，即PILB = SO - PT ≥ 0，则可以保证新策略优于旧策略。
通过增大执行 A^{\pi_{old}}(s, a)>0 动作的概率，减小执行 A^{\pi_{old}}(s, a)<0 动作的概率，可以增大SO的数值，但如果新旧策略差异太大（即 |\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)}-1| \gg 0 ），PT的数值也会陡增。为了更好理解，我写了一个简单的脚本[7]，绘制了PILB、SO、PT随策略更新而变化的曲线图：


可以看到，随策略更新，SO呈线性增加趋势，PT呈指数增加趋势，这导致PILB呈现出先增加后减小的趋势。因此，为保证 J(\pi_{new})-J\left(\pi_{old}\right) \geq PILB \geq 0 ，PPO需要在新旧策略差异不大的情况下，提升SO，即： \underset{\pi_{new}}{maximize}\ \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)} A^{\pi_{old}}(s, a)\right]\\ s.t. \ \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\left|\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)}-1\right|\right] \leq \delta \\ \tag{15}上式中， D^{\pi_{old}} 分布无法精确获得，但是可以通过用 \pi_{old} 与环境互动产生的轨迹 \tau_{old} 来近似；同时，将策略参数化为 \pi_{\theta} ，此时公式(15)的优化问题可以通过求解下面优化问题来近似求解： \underset{\theta}{maximize}\ \underset{(s, a) \sim \tau_{old}}{\mathbb{E}}\left[\frac{\pi_{\theta}(a \mid s)}{\pi_{\theta_{old}}(a \mid s)} A^{\pi_{\theta_{old}}}(s, a)\right]\\ s.t. \ \underset{(s, a) \sim \tau_{old}}{\mathbb{E}}\left[\left|\frac{\pi_{\theta}(a \mid s)}{\pi_{\theta_{old}}(a \mid s)}-1\right|\right] \leq \delta \\ \tag{16}公式(16)的优化问题可以进一步转化为极大化以下目标函数来解决： L^{CLIP}(\theta)=\underset{(s, a) \sim \tau_{old}}{\mathbb{E}}[min(\ r(\theta)A,\ clip(r(\theta),1-\epsilon,1+\epsilon)A\ )] \\ \tag{17}其中， r(\theta)=\frac{\pi_{\theta}(a \mid s)}{\pi_{\theta_{old}}(a \mid s)} , A=A^{\pi_{\theta_{old}}}(s, a) ，公式(17)的意义如下图所示：

• A>0 时， Maximize \ \ L^{CLIP}(\theta) \Rightarrow Maximize \ r(\theta) ，但由于Clip原因， r(\theta) 最大增加到 1+\epsilon ，保证了新旧策略差异不大
  
• A<0 时， Maximize \ \ L^{CLIP}(\theta) \Rightarrow Minimize \ r(\theta) ，但由于Clip原因， r(\theta) 最小减小到 1-\epsilon ，保证了新旧策略差异不大
  

另外，到目前为止，我们都假设可以获得正确的优势函数，在实际过程中，优势函数可以用GAE[8]等方法估计。
五、总结

本文介绍了TRPO和PPO的数学原理，两者都是从提升策略改进下界的角度出发，利用当前的旧策略与环境互动生成轨迹来优化策略。由于算法使用旧策略生成的数据学习，具有一次互动，多次更新的优势，很大程度上提升了样本利用率，但同时也需要保证每次更新时新旧策略差异不能太大。另外，PPO在代码实现上有很多细节，感兴趣的朋友可以看一下这篇博客：
附录

A-1：
\begin{aligned} &\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[\sum_{t=0}^{\infty} \gamma^t A_{\pi_{\text {old }}}\left(s_t, a_t\right)\right] \\  &=\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[\sum_{t=0}^{\infty} \gamma^t\left(r\left(s_t\right)+\gamma V_{\pi_{\text {old }}}\left(s_{t+1}\right)-V_{\pi_{\text {old }}}\left(s_t\right)\right)\right] \\  &=\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[-V_{\pi_{\text {old }}}\left(s_0\right)+\sum_{t=0}^{\infty} \gamma^t r\left(s_t\right)\right] \\  &=-\mathbb{E}_{s_0}\left[V_{\pi_{\text {old }}}\left(s_0\right)\right]+\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[\sum_{t=0}^{\infty} \gamma^t r\left(s_t\right)\right] \\  &=-J\left(\pi_{\text {old }}\right)+J\left(\pi_{\text {new }}\right) \end{aligned}

A-2：
\begin{aligned} J\left(\pi_{\text {new }}\right)&=J\left(\pi_{\text {old }}\right)+\mathbb{E}_{s_0, a_0, s_1, a_1, \ldots}\left[\sum_{t=0}^{\infty} \gamma^t A_{\pi_{\text {old }}}\left(s_t, a_t\right)\right]\\   &=J\left(\pi_{\text {old }}\right)+\sum_{t=0}^{\infty} \gamma^t \sum_{s_t} \operatorname{Pr}\left(s_t \mid \pi_{n e w}\right) \sum_{a_t} \pi_{n e w}\left(a_t \mid s_t\right) A_{\pi_{\text {old }}}\left(s_t, a_t\right)\\   &=J\left(\pi_{\text {old }}\right)+\sum_s \sum_{t=0}^{\infty} \gamma^t \operatorname{Pr}\left(s_t=s \mid \pi_{n e w}\right) \sum_a \pi_{n e w}(a \mid s) A_{\pi_{\text {old }}}(s, a)\\ &=J\left(\pi_{\text {old }}\right)+\sum_s \rho_{\pi_{\text {new }}}(s) \sum_a \pi_{\text {new }}(a \mid s) A_{\pi_{\text {old }}}(s, a) \end{aligned}

A-3:
由公式(9)： J(\pi_{i+1}) \geq M_i(\pi_{i+1})
由公式(10)： M_i(\pi_{i+1})\geq M_i(\pi_{i})
由公式(4)： M_i(\pi_{i}) = J(\pi_{i})
因此， J(\pi_{i+1}) \geq M_i(\pi_{i+1})\geq M_i(\pi_{i}) = J(\pi_{i})

A-4:
由A-2得： J\left(\pi_{\text {new}}\right)-J\left(\pi_{\text {old }}\right)=\sum_s \sum_{t=0}^{\infty} \gamma^t \operatorname{Pr}\left(s_t=s \mid \pi_{n e w}\right) \sum_a \pi_{n e w}(a \mid s) A_{\pi_{\text {old }}}(s, a)\\ \tag{18}
由于 \sum_s \sum_{t=0}^{\infty} \gamma^t \operatorname{Pr}\left(s_t=s \mid \pi_{n e w}\right)=\sum_{t=0}^{\infty} \gamma^t \sum_{s_t} \operatorname{Pr}\left(s_t \mid \pi_{n e w}\right) =\sum_{t=0}^{\infty} \gamma^t=\frac{1}{1-\gamma} \ne 1
公式(18)需要先对 s 的分布归一化才能写成期望的形式：
\begin{align}  J\left(\pi_{\text {new}}\right)-J\left(\pi_{\text {old }}\right) &=\sum_s \sum_{t=0}^{\infty} \gamma^t \operatorname{Pr}\left(s_t=s \mid \pi_{n e w}\right) \sum_a \pi_{n e w}(a \mid s) A_{\pi_{\text {old }}}(s, a)\\  &=\frac{1}{1-\gamma}\sum_s (1-\gamma)\sum_{t=0}^{\infty} \gamma^t \operatorname{Pr}\left(s_t=s \mid \pi_{n e w}\right) \sum_a \pi_{n e w}(a \mid s) A_{\pi_{\text {old }}}(s, a)\\  &=\frac{1}{1-\gamma}\underset{s \sim D^{\pi_{new}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right]  \end{align} \tag{19}
其中， D^{\pi_{new}}=(1-\gamma)\sum_{t=0}^{\infty} \gamma^t \operatorname{Pr}\left(s_t=s \mid \pi_{n e w}\right) 为normalized discounted visitation frequencies，
现在，我们将把公式(19)中的状态-动作分布从 \pi_{new} 换到 \pi_{old} 上：
\begin{align}  J\left(\pi_{\text {new}}\right)-J\left(\pi_{\text {old }}\right) &=\frac{1}{1-\gamma}\underset{s \sim D^{\pi_{new}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right]\\  &= \frac{1}{1-\gamma}\underset{s \sim D^{\pi_{old}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] + \frac{1}{1-\gamma}\left( \underset{s \sim D^{\pi_{new}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] -\underset{s \sim D^{\pi_{old}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] \right)\\  &\geq  \frac{1}{1-\gamma}\underset{s \sim D^{\pi_{old}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] - \frac{1}{1-\gamma}\left| \underset{s \sim D^{\pi_{new}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] -\underset{s \sim D^{\pi_{old}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] \right| \\  &\geq   \frac{1}{1-\gamma}\underset{s \sim D^{\pi_{old}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] -\frac{1}{1-\gamma}\|D^{\pi_{new}}-D^{\pi_{old}}\|_1 \| \underset{a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] \|_{\infty}  \end{align} \tag{20}
(倒数第二步是因为 (A-B)≥-|A-B| ；最后一步由Hlder不等式放缩得来)
由文献[9]：
\begin{align}  \|D^{\pi_{new}}-D^{\pi_{old}}\|_1&= 2 \mathrm{TV}\left(D^{\pi_{new}},D^{\pi_{old}}\right)  \\  &\leq \frac{2 \gamma}{1-\gamma} \underset{s \sim D^{\pi_{old}}}{\mathbb{E}}\left[\mathrm{TV}\left(\pi_{new}, \pi_{old}\right)(s)\right]=\frac{\gamma}{1-\gamma}\underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\left|\frac{\pi(a \mid s)}{\pi_k(a \mid s)}-1\right|\right]  \end{align} \tag{21}
\| \underset{a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] \|_{\infty}=\underset{s\in S}{max}| \underset{a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right] | = \epsilon \tag{22} 最后将(21) (22)带入(20)：
\begin{align}  J(\pi_{new})-J\left(\pi_{old}\right)   \geq& \frac{1}{1-\gamma} \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{new}}{\mathbb{E}}\left[A^{\pi_{old}}(s, a)\right]-\frac{ \gamma \epsilon}{(1-\gamma)^2} \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\left|\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)}-1\right|\right] \\  &= \frac{1}{1-\gamma} \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)} A^{\pi_{old}}(s, a)\right]-\frac{ \gamma \epsilon}{(1-\gamma)^2} \underset{s \sim D^{\pi_{old}}\\a \sim \pi_{old}}{\mathbb{E}}\left[\left|\frac{\pi_{new}(a \mid s)}{\pi_{old}(a \mid s)}-1\right|\right]  \end{align}
参考

• ^abSchulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms[J]. arXiv preprint arXiv:1707.06347, 2017.https://arxiv.org/pdf/1707.06347.pdf
  
• ^abcdKakade S, Langford J. Approximately optimal approximate reinforcement learning[C]//In Proc. 19th International Conference on Machine Learning. 2002.
  
• ^abcdefSchulman J, Levine S, Abbeel P, et al. Trust region policy optimization[C]//International conference on machine learning. PMLR, 2015: 1889-1897.
  
• ^Van Hasselt H, Guez A, Silver D. Deep reinforcement learning with double q-learning[C]//Proceedings of the AAAI conference on artificial intelligence. 2016, 30(1).
  
• ^Fujimoto S, Hoof H, Meger D. Addressing function approximation error in actor-critic methods[C]//International conference on machine learning. PMLR, 2018: 1587-1596.
  
• ^Pollard, David. Asymptopia: an exposition of statistical asymptotic theory. 2000. URL http://www.stat. yale.edu/pollard/Books/Asymptopia.
  
• ^https://github.com/XinJingHao/PPO_LowerBound_plot
  
• ^Schulman J, Moritz P, Levine S, et al. High-dimensional continuous control using generalized advantage estimation[J]. arXiv preprint arXiv:1506.02438, 2015.https://arxiv.org/pdf/1506.02438.pdf
  
• ^Queeney J, Paschalidis Y, Cassandras C G. Generalized proximal policy optimization with sample reuse[J]. Advances in Neural Information Processing Systems, 2021, 34: 11909-11919.