从TRPO到PPO（理论分析与数学证明）_ppo和trpo

本文首发于行者AI

引言

一篇关于强化学习算法的理论推导，或许可以帮助你理解PPO算法背后的原理，从而找到改进PPO算法的灵感…

马尔可夫决策过程由$(S,A,P,r,{\rho }_0,\gamma )$六个元素构成。其中$S$是一个有限的状态空间集合，$A$是一个有限的动作空间集合。$P:S\times A\times S\to \mathbb{R}$ 表示状态转移概率函数，例如$P(s^{\prime }|s,a)=0.6$表示的含义就是在状态$s$处执行动作$a$到达的状态为$s^{\prime }$的概率为0.6。$r:S\to \mathbb{R}$是奖励函数，${\rho }_0:S\to \mathbb{R}$是初始状态分布概率函数，$\gamma \in (0,1)$是折扣因子。

让$\pi$表示一个随机策略函数$\pi :S\times A\to [0,1]$,例如$\pi (s,a)=0.5$表示在状态$s$处选择动作$a$的概率为0.5。令$\eta (\pi )$表示基于策略$\pi$的长期期望折扣奖励：$\eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)]$, 其中$s_0\sim {\rho }_0(s_0),a_t\sim \pi (a_t|s_t),s_{t+1}\sim P(s_{t+1}|s_t,a_t)$。

下面给出状态价值函数、状态动作价值函数、优势函数的定义：

（1）状态动作价值函数：
$$Q_{\pi }(s_t,a_t)={\mathbb{E}}_{s_{t+1},a_{t+1},\dots }[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})]$$
表示的是在状态$s_t$处执行动作$a_t$后获得的长期期望折扣奖励。

（2）状态价值函数:
$$V_{\pi }(s_t)={\mathbb{E}}_{a_t,s_{t+1},\dots }[\sum _{l=0}^{\infty }{\gamma }^{l}r(s_{t+l})]={\mathbb{E}}_{a_t}[Q_{\pi }(s_t,a_t)]$$
表示从状态$s_t$开始获得的长期期望折扣奖励。

（3）优势函数：
$$A_{\pi }(s,a)=Q_{\pi }(s,a)-V_{\pi }(s,a)$$
表示的是在状态$s$处，动作$a$相对于平均水平的高低。

强化学习的目标就是最大化长期期望折扣奖励
$$\eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)]$$
其中策略函数$\pi$可以看作是带有参数$\theta$的随机策略$\pi (s,a)={\pi }_{\theta }(s,a)$。在策略梯度算法(Policy Gradient)中，参数$\theta$的更新公式为
$${\theta }_{new}={\theta }_{old}+\alpha {\nabla }_{\theta }\eta (\theta )$$
这样的更新公式容易导致以下问题：如果步长$\alpha$选取不合适，那么会导致${\theta }_{new}$比${\theta }_{old}$差，当使用${\theta }_{new}$进行采样学习的时候，采取到的样本就是比较差的样本，再继续使用不好的样本对参数进行更新，得到的是更加不好的策略，从而导致恶性循环。TRPO算法解决的问题就是：如何选择一个合适的更新策略，或是如何选择一个合适的步长，使得更新过后的策略${\pi }_{{\theta }_{new}}$一定比更新前的策略${\pi }_{{\theta }_{old}}$好呢？

1.TRPO的理论分析

1.1 不同策略的长期期望折扣奖励之间的关系

先来看一下基于策略$\pi$的长期折扣奖励
$$\eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }[\sum _{t=0}^{\infty }{\gamma }^{t}r(s_t)]$$
对于另一个策略$\tilde{\pi }$,两个策略之间的长期折扣奖励函数$\eta (\tilde{\pi })$与$\eta (\pi )$之间的关系为：
$$\eta (\tilde{\pi })=\eta (\pi )+{\mathbb{E}}_{s_0,a_0,\dots \sim \tilde{\pi }}[\sum _{t=0}^{\infty }{\gamma }^t{A}_{\pi }(s_t,a_t)](3.1)$$
其中$A_{\pi }(s_t,a_t)$为优势函数，$A_{\pi }(s_t,a_t)=Q_{\pi }(s_t,a_t)-V_{\pi }(s_t)$。（证明过程见文章后面附录证明4.1）。

上述公式要注意的点是$s_0,a_0,\dots \sim \tilde{\pi }$表示轨迹中的状态和动作都是基于策略$\tilde{\pi }$采样得到的，而$A_{\pi }(s_t,a_t)$表示的是策略$\pi$的优势函数。
为了方便公式的书写和后续求导的计算，定义
$${\rho }_{\pi }(s)=P(s_0=s)+\gamma P(s_1=s)+{\gamma }^{2}P(s_2=s)+\dots$$
则公式$(3.1)$可以改写为：
$$\eta (\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\tilde{\pi }}(s)\sum _s\tilde{\pi }(a|s)A_{\pi }(s,a)(3.2)$$
证明过程见文章后面附录证明4.2。

1.2 替代函数的建立

再来回顾一下我们在背景中提出的目标：找到一个合适的步长，使得每一个更新得到的新的策略${\pi }_{new}$要比更新前的策略${\pi }_{old}$好,体现在公式上就是要求$\eta ({\pi }_{new})\ge \eta ({\pi }_{old})$。

由于公式$(3.2)$中的${\rho }_{\tilde{\pi }}$对$\tilde{\pi }$有强烈的依赖性，但是在更新之前我们还不知道策略$\tilde{\pi }$的具体形式，所以我们考虑找到一个$\eta (\tilde{\pi })$的替代函数：
$$L_{\pi }(\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\pi }(s)\sum _a\tilde{\pi }(a|s)A_{\pi }(s,a)(3.3)$$
这个替代函数的作用是什么呢，可以帮助我们得到$\eta$函数的哪些性质呢？把策略$\pi$表示为带有参数$\theta$的随机策略$\pi ={\pi }_{\theta }$，给出下面定理：$L_{{\pi }_{{\theta }_0}}({\pi }_{\theta })$与$\eta ({\pi }_{\theta })$在${\theta }_0$处一阶近似，用公式表示为:
{ L π θ 0 ( π θ 0 ) = η ( π θ 0 ) ∇ θ L π θ 0 ( π θ ) ∣ θ = θ 0 = ∇ θ η ( π θ ) ∣ θ = θ 0 \left\{

$$\begin{aligned} L_{\pi_{\theta_0}}(\pi_{\theta_0})& = \eta(\pi_{\theta_0})\\ \nabla_{\theta}L_{\pi_{\theta_0}}(\pi_\theta)|_{\theta=\theta_0}& = \nabla_\theta\eta(\pi_\theta)|_{\theta=\theta_0}\\ \end{aligned}$$ \right. { Lπθ0​​​(πθ0​​)∇θ​Lπθ0​​​(πθ​)∣θ=θ0​​​=η(π