RL Algorithm: Proximal Policy Optimization(PPO)

发表于 更新于 分类于

本文介绍强化学习（Reinforcement Learning）目前使用最广泛的一类算法：Policy Gradient Method，并介绍这类算法中的 PPO 算法。

1. 策略梯度法（Policy Gradient Method）

在强化学习中，有两大类算法：一类基于 action-state value，并根据 value function 来选择 action，如 Q-Learning 、 SARSA 等；一类基于参数化的策略（parameterized policy），策略直接根据 observation 输出 action，如 REINFORCE 、 TRPO 以及本文要介绍的 PPO 等。第一类方法多用于动作为离散值的问题，第二类方法则天然适用于动作为连续值的问题。

基于参数化策略的方法通过：1. 运行环境获取数据；2. 根据获取的数据计算梯度；3. 根据梯度上升（或下降，如果是针对损失函数）的方向优化策略的参数这三步来不断优化参数，从而使得策略能够获取更高的奖励函数值或更低的损失函数值。其核心即下列公式：

\[ \theta_{t+1} = \theta_{t} + \alpha \nabla J \left( \theta_{t} \right) \tag{1} \]

其中 \(J\left(\theta\right)\) 即以 \(\theta\) 为参数的奖励函数，策略的目标为最大化该奖励函数。

根据前文提到的三步，就产生了几个问题：1. 策略梯度法的基本理论是什么；2. 该算法需要获取哪些数据；3. 如何根据获取的数据计算或估计梯度。

1.1. 策略梯度法的基本理论

根据主体（agent）与环境的交互是否存在间断，可以将强化学习的任务分为两种类型：连续型任务（continuous task）和回合型任务（episodic task）。不同类型的任务的策略梯度法的具体公式表达会有一定的差异，对无折扣的（\(\gamma = 1\)）的回合型任务，如果选择状态价值函数（\(V(s)\)）作为奖励函数，则奖励函数具体表达式为：

\[ J\left( \theta \right) \doteq v_{\pi_\theta} \left( s_0 \right) = \sum_{\mathbf{a}} \pi \left(a | s \right) q_{\pi} \left( s, a \right) \tag{2} \]

策略梯度法的目标在于通过梯度上升的方法来优化参数 \(\theta\) ，从而实现奖励函数 \(J(\theta)\) 的数值的提高。策略梯度理论（Policy Gradient Theorem）证明了奖励函数的梯度能够仅用 action-state value 和策略 \(\pi\) 的梯度进行表示，从而验证了策略梯度计算的可行性。具体的表达式如公式（3）所示：

\[ \begin{split} \nabla J\left( \theta \right) & = \sum_{x \in \mathcal{S}} \sum^{\infty}_{k = 0} Pr \left( s\rightarrow x, k, \pi \right) \sum_{\mathbf{a}} q_{\pi} \left( s, a \right) \nabla \pi \left( a | s, \mathbf{\theta} \right)\\ &\propto \sum_{\mathbf{s}} \mu \left( s \right) \sum_{\mathbf{a}} q_{\pi} \left( s, a \right) \nabla \pi \left( a | s, \mathbf{\theta} \right) \end{split} \tag{3} \]

其中 \(Pr \left( s\rightarrow x, k, \pi \right)\) 表示在策略 \(\pi\) 下，从状态 s 经过 k 步到达状态 x 的概率，\(\mu\left( s \right)\) 表示在策略 \(\pi\) 下各个状态的概率分布。公式（3）的具体证明在文末的参考文献中有详细的介绍 12，下面给出 Sutton 在 Reinforcement Leanrning: an introduction 中的证明过程。

从公式（3）就能够根据 action-state value 和策略分布的梯度来计算奖励函数关于策略参数的梯度。如何计算 action-state value 就成了不同的 Policy Gradient Method 之间的重要区别。

1.2. 运行环境需要获取哪些数据及如何根据这些数据计算或估计梯度

对于具体的任务而言，action-state value 往往是未知的，所以需要通过各种方式来对 action-state value 进行估计。

如果将公式（3）写成期望的形式，则得到公式（4）

\[ \begin{split} \nabla J\left( \theta \right) &\propto \sum_{\mathbf{s}} \mu \left( s \right) \sum_{\mathbf{a}} q_{\pi} \left( s, a \right) \nabla \pi \left( a | s, \mathbf{\theta} \right) \\ &=E_\pi \left[ \sum_a q_\pi (S_t, a) \nabla \pi (a|S_t, \theta) \right]\\ &=E_\pi \left[ \sum_a q_\pi (S_t, a) \pi (a|S_t, \theta) \frac{\nabla \pi (a|S_t, \theta)}{\pi (a|S_t, \theta)} \right]\\ &=E_\pi \left[ q_\pi (S_t, A_t) \frac{\nabla \pi (A_t|S_t, \theta)}{\pi (A_t|S_t, \theta)} \right]\\ &=E_\pi \left[ q_\pi (S_t, A_t) \nabla \log \pi (A_t|S_t, \theta) \right]\\ \end{split} \tag{4} \]

其中 \(S_t\) 和 \(A_t\) 对应各个样本的 state 和 action。从公式（4）就得到最基础的从样本来估计策略梯度的方法。

在实际计算时，综合考虑 bias 和 variance，（4）式中的 \(q_\pi (S_t, A_t)\) 可以用以下表达式代替：

\[ \begin{cases} &\sum_{t=0}^{\infty} r_t \quad \text{total reward of the trajectory}\\ &\sum_{t'=t}^{\infty} r_{t'} \quad \text{reward following action } a_t\\ &\sum_{t'=t}^{\infty} (r_{t'} - b(S_t)) \quad \text{reward following action } a_t\text{ (baselined version)}\\ & Q^\pi (S_t, A_t) \quad \text{state-action value function}\\ & A^{\pi}(S_t, A_t) \quad \text{advantage function}\\ & r_t + V^\pi (S_{t + 1}) - V^\pi (S_t) \quad \text{TD residual} \end{cases} \tag{5} \]

其中部分变量定义如下

\[ \begin{split} V^\pi(S_t) &= E_{S_{t + 1:\infty}, A_{t:\infty}} \left[ \sum_{l = 0}^\infty r_{t + l} \right]\\ Q^\pi(S_t) &= E_{S_{t + 1:\infty}, A_{t + 1:\infty}} \left[ \sum_{l = 0}^\infty r_{t + l} \right]\\ A^\pi{S_t} &= Q^\pi(S_t) - V^\pi(S_t) \end{split} \]

（5）式中定义的各个表达式对应的策略梯度都是 unbiased，即估计得到的梯度的期望与实际梯度的期望是相同的：

\[ E\left[ \hat{\nabla J} - \nabla J \right] = 0 \]

常见的 Actor-Critic 算法则是 biased。

从 variance 的角度来看，一般来说，advantage function 方法对应的 variance 是比较小的。更多关于 policy gradient method 中的 bias 和 variance 的描述可以参考文末文献 3 4

在环境运行过程中，获取得到（4）和（5）式中各项的值，就能计算得到估计的策略梯度，从而进行梯度上升，从而对策略进行优化。

2. 为什么需要 PPO，以及该算法的实现

2.1. 一般的策略梯度法的局限

在提出 PPO 算法的文章 5 中，作者指出了以往的策略梯度算法在数据利用效率、优化稳定性和实用性方面的局限

Q-learning (with function approximation) fails on many simple problems1 and is poorly understood, vanilla policy gradient methods have poor data effiency and robustness; and trust region policy optimization (TRPO) is relatively complicated, and is not compatible with architectures that include noise (such as dropout) or parameter sharing (between the policy and value function, or with auxiliary tasks).

2.2. PPO 的具体实现

与 TRPO 算法一样，PPO 通过给出一个代理函数（surrogate function）来取代对原始的目标函数（后称原函数），通过对代理函数的优化来实现对策略本身的优化。代理函数的选取和优化的单调性保证可参考 TRPO 原文 6(关于代理函数的选取详见第五节)。

TRPO 算法通过对更新前后策略的 KL 散度进行硬约束来限制策略的更新幅度，如公式（6）所示

\[ \arg \max_\theta E\left[ \frac{\pi_\theta(a_t | s_t)}{\pi_{\theta_{\text{old}}}(a_t | s_t)} A_t \right]\\ \text{subject to} \quad E_t\left[ KL\left[ \pi_{\theta_{\text{old}}}(\cdot | s_t), \pi_{\theta}(\cdot | s_t) \right] \right] \leq \delta \tag{6} \]

而 PPO 则是采用软约束，直接对原函数进行修改，从而限制策略更新的幅度。在原文中给出了两种新的代理函数：1. clipped surrogate objective；2. adaptive KL penalty coefficient。分别可以表示为

1. Clipped surrogate objective

\[ \begin{align} &\arg\max_\theta L^{CLIP}(\theta) = E_t\left[ \min \left( r_t(\theta)A_t, \text{clip}\left( r_t(\theta), 1 - \epsilon, 1 + \epsilon \right) A_t \right) \right]\\ &\text{in which: } r_t(\theta) = \frac{\pi_\theta(a_t | s_t)}{\pi_{\theta_{\text{old}}}(a_t | s_t)} \end{align} \]

2. Adaptive KL penalty coefficient

\[ \begin{align} &\arg\max_\theta K^{KLPEN}(\theta) = E_t \left[ \frac{\pi_{\theta}(a_t | s_t)}{\pi_{\theta_{\text{old}}}(a_t | s_t)} A_t - \beta KL\left[ \pi_{\theta_{\text{old}}}(\cdot | s_t), \pi_{\theta}(\cdot | s_t) \right] \right]\\ &\text{update }\beta \text{ , define: } d = E_t\left[KL\left[ \pi_{\theta_{\text{old}}}(\cdot | s_t), \pi_{\theta}(\cdot | s_t) \right]\right]\\ &\text{if }d < d_{\text{target}} / 1.5 \text{ : } \beta \leftarrow \beta / 2\\ &\text{if }d > d_{\text{target}} \times 1.5 \text{ : } \beta \leftarrow \beta \times 2 \end{align} \]

通过将原梯度下降算法中的奖励函数更换为上述两种代理函数的一种，就实现了 PPO 算法的部署。

3. 其他

上一节介绍了 PPO 的基本算法，但是在实际实现中，纯粹的 PPO 可能无法胜任复杂任务的优化，关于这一点的叙述，可以参考 The 37 Implementation Details of Proximal Policy Optimization7 这篇文章的开头部分。因此，现有的 RL 库（如 stable-baselines， CleanRL 等），在实际实现 PPO 时，都或多或少地运用了一些细节来提高 PPO 算法的稳定性和优化速度。The 37 Implementation Details of Proximal Policy Optimization 这篇文章中，对各个算法实现时采用的细节对最终训练的效果影响，也有较为详细的对比，目前来看，stable-baselines 的 PPO2 算法是目前较为优秀的一个变种。

PPO 的本质是利用代理函数对策略更新的幅度进行限制，因此在实现时相当灵活。关于具体实现时的代理函数的选择，action sample的分布等因素对算法效果的影响，可以参考2020年的一篇文献8，这篇文献中也介绍了一些 failure modes，对理解 PPO 的适用性有一定的帮助。

  1. Sutton, R. S. & Barto, A. G. Reinforcement Learning: an introduction. (MIT Press, 2018).↩︎

  2. Weng, L. Policy Gradient Algorithms. https://lilianweng.github.io/posts/2018-04-08-policy-gradient/ (2018).↩︎

  3. Greensmith, E., Bartlett, P. L. & Baxter, J. Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning. 60.↩︎

  4. Wu, C. et al. Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines. Preprint at http://arxiv.org/abs/1803.07246 (2018).↩︎

  5. Schulman, J., Wolski, F., Dhariwal, P., Radford, A. & Klimov, O. Proximal Policy Optimization Algorithms. arXiv:1707.06347 [cs] (2017).↩︎

  6. Schulman, J., Levine, S., Moritz, P., Jordan, M. I. & Abbeel, P. Trust Region Policy Optimization. arXiv:1502.05477 [cs] (2017).↩︎

  7. The 37 Implementation Details of Proximal Policy Optimization · The ICLR Blog Track. https://iclr-blog-track.github.io/2022/03/25/ppo-implementation-details/.↩︎

  8. Hsu, C. C.-Y., Mendler-Dünner, C. & Hardt, M. Revisiting Design Choices in Proximal Policy Optimization. arXiv:2009.10897 [cs, stat] (2020).↩︎