Policy Gradient Algorithms: From REINFORCE to PPO

在阅读本文前，需要了解 Policy Gradient Theorem，主要包括策略梯度的求导，强化学习的目标函数。

Policy Gradient Theorem

策略梯度一般的形式如下：

$$\nabla_{\theta} J(\theta) = \mathbb{E}_{\tau \sim \mathbb{P}(\cdot;\theta)}\Bigg[\sum_{t=0}^{T-1} \Psi_{t} \nabla_{\theta} \ln \pi_{\theta}(a_{t} \mid s_{t})\Bigg]$$

其中，$\Psi_{t}$ 可以有如下取值：

• $G(\tau)$: 整个轨迹上的回报
• $G_{t}$: 自动作 $a_{t}$ 后的回报
• $G_{t}-b(s_{t})$: 自动作 $a_{t}$ 后回报的 baseline 版本
• $Q^{\pi}(s_{t},a_{t})$: 动作价值函数
• $A^{\pi}(s_{t},a_{t}) = Q^{\pi}(s_{t},a_{t}) - V^{\pi}(s_{t})$: 优势函数
• $\delta_{t} = r_{t} + \gamma V^{\pi}(s_{t+1}) - V^{\pi}(s_{t})$: TD Error

后文介绍的各算法都是围绕这个基本形式展开，而这一公式主要在 Policy Gradient Theorem 一文展开详细的推导。

REINFORCE

REINFORCE (Monte-Carlo policy gradient) 通过采集完整的轨迹，并使用轨迹中的实际回报 $G_{t}$ ​来近似策略梯度。算法如下：

1. Initialize the policy parameter $\theta$
   1. Generate an episode $\tau=(s_{0},a_{0},r_{0},s_{1},a_{1},\ldots,s_{T})$ following policy $\pi_{\theta}$
   2. For $t=0,1,\ldots,T-1$:
      1. Value Update: $G_{t}=\sum_{k=t}^{T-1} \gamma^{k-t} r_{k}$
      2. Policy Update: $\theta \gets \theta + \alpha \nabla_{\theta} \ln \pi_{\theta}(a_{t} \mid s_{t}) G_{t}$

REINFORCE 的特点在于无偏与高方差。在介绍之前，通过一个打靶比喻，直观地感受强化学习中的偏差（Bias）与方差（Variance）。

• Low Bias & Low Variance：每次射击都紧密地聚集在靶心。
• High Bias：射击系统性地偏离靶心。每次射击都无法打在靶心。说明瞄准系统（模型）本身就有问题。无论多少射击，都估计不准靶心位置。
• High Variance & Low Bias：射击点平均下来是在靶心周围，但每次射击的位置都非常分散，毫无规律。这说明瞄准过程（估计方法）非常不稳定。但可以通过足够多的射击来估计靶心位置。

接下来，我们详细分析 REINFORCE 的无偏性与高方差。

无偏

REINFORCE 直接使用蒙特卡洛采样得到的 $G_{t}$​ 作为回报的估计。虽然单次采样的 $G_{t}$ 可能与期望值 $Q^{\pi}(s_{t}, a_{t})$ 相差甚远，但只要我们采样足够多的轨迹，$G_{t}$ 的平均值就会收敛到其真实的期望值 $Q^{\pi}(s_{t}, a_{t})$。因此，使用 $G_{t}$ 计算出的梯度在期望上是等于真实梯度的，所以它是无偏的。

高方差

方差的来源在于 $G_{t}$ 的计算方式，这里的 $G_{t}$ 是从时间步 $t$ 到轨迹结束 $T$ 所有奖励的总和：

$$G_{t} = G_{t:T} = R_{t} + \gamma R_{t+1} + \ldots + \gamma^{T-1-t} R_{T-1}$$

$G_{t}$ 的值是一个很长的随机变量序列和，随机性来源包括：

1. 策略的随机性：未来的每个动作 $a_{k}(k \ge t)$ 都是从策略 $\pi_{\theta}(\cdot \mid s_{k})$ 中随机采样的。
2. 环境的随机性：未来的每个状态转移 $s_{k+1} \sim P(\cdot \mid s_{k}, a_{k})$ 也可能是随机的。

这一长串的随机事件累积起来，导致最终 $\mathrm{Var}(G_{t})$ 非常大，从而使得梯度估计的方差非常高

Actor-Critic

Actor-Critic 算法（更合适的说法是框架）本质上是一个神经网络（或两个共享部分权重的网络）同时学习两个任务：策略（Actor）和价值（Critic）：

• Actor: $\pi_{\theta}(a \mid s)$ 由参数为 $\theta$ 的网络表示，输入状态 $s$，输出一个动作 $a$ 的概率分布。
• Critic: $V_{w}(s)$ 由参数为 $w$ 的网络表示，输入状态 $s$，输出该状态的价值。

在实践中，Actor 和 Critic 网络通常共享大部分底层网络层，只在最后一层分开输出策略和价值，因此参数可以统一表示为 $\theta$（即 $\theta$ 同时包含 Actor 和 Critic 的参数）。这里为了概念清晰，我们暂时分开表示为 $\theta$ 和 $w$。

直观地理解，一个演员（Actor）在台上表演，同时有一个评论家（Critic）在台下评估他的表现。演员根据评论家的反馈来调整自己的表演，而评论家则通过观察演员的表演和观众的反应来提升自己的评判水准。

对于 Actor，我们希望其执行能够获得更高优势的动作。目标函数表示如下：

$$\max_{\theta}J(\theta) = \mathbb{E}_{t}\big[\hat{A}_{t} \ln \pi_{\theta}(a_{t} \mid s_{t})\big]$$

此时的算法称为 A2C (Advantage Actor-Critic)，我们使用 TD Error 来近似单步优势 $\hat{A}_{t}$:

$$\hat{A}_{t} = \delta_{t} = r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t})$$

其中，$r_{t}$ 是采样得到的即时奖励，$V_{w}(\cdot)$ 通过 Critic 网络进行近似。此时，我们将优势 $\hat{A}_{t}$ 视为一个常数，即：不会通过它反向传播梯度到 Critic 网络。这是因为，这是因为 Actor 的职责 " 迎合 " Critic 的评价（即 $\hat{A}_{t}$）来更新自己，而不是 " 改变 " 评价标准，反过来去影响这个信号的计算。

此外，我们使用了单步优势，所以可直接按照单步方法进行更新。式中的 $\mathbb{E}_{t}[\cdot]$ 表示对同一个 batch 中的所有单步数据求期望，这也表明整体算法流程是 " 数据采样 - 参数更新 " 交互进行的。这里我们展开 $\mathbb{E}_{t}[\cdot]$，给出更严谨的目标函数表示：

$$\max_{\theta}J(\theta) = \mathbb{E}_{s_{t+1} \sim P(\cdot \mid s_{t},a_{t}), a_{t} \sim \pi_{\theta}(\cdot \mid s_{t})}\big[\hat{A}_{t} \ln \pi_{\theta}(a_{t} \mid s_{t})\big]$$

对于 Critic，我们希望其尽可能准确地估计状态价值。换句话说，其目标是为了拟合理论上的真实状态价值函数 $V^{\pi}(s)$。标准的监督学习使用均方误差（Mean Squared Error, MSE）损失函数：

$$\min_{\theta}\mathcal{L}(w) = \frac{1}{2} \mathbb{E}_{t}\Big[ \big(V^{\pi}(s_{t}) - V_{w}(s_{t})\big)^{2} \Big]$$

问题在于，我们永远无法知道 $V^{\pi}(s)$ 这个真值。因此，我们必须用一个从真实采样数据中计算出来的 target $\hat{V}^{\pi}(s)$ 来替代它，不同 $\hat{V}^{\pi}(s)$ 的选择就构成了不同的算法。

根据状态价值函数的定义 $V^{\pi}(s) = \mathbb{E}_{\pi}[G_{t} \mid S_{t} = s]$ 可知，$G_{t}$ 是对 $V^{\pi}(s_{t})$ 的一个无偏估计。回顾前面提及的 REINFORCE 算法，虽然蒙特卡洛回报对 $V^{\pi}(s_{t})$ 的估计是无偏的，但是方差较大。

根据 Bellman Equation：

$$\begin{aligned} V^{\pi}(s) &= \mathbb{E}_{a \sim \pi(\cdot \mid s)} \Big[\mathbb{E}_{s^{\prime} \sim P(\cdot \mid s,a)}\big[ \underbrace{R_{t} + \gamma V^{\pi}(s^{\prime})}_{\text{TD Target}} \big]\Big] \\ &= \mathbb{E}_{t} \big[ R_{t} + \gamma V^{\pi}(s^{\prime}) \big] \end{aligned}$$

TD Target 是理论真值 $V^{\pi}(s)$ 的无偏估计。因此，目标函数可以定义为最小化其当前步预测值 $V_{w}(s_{t})$ 与基于下一步真实情况的新预测值 TD Target $r_{t} + \gamma V_{w}(s_{t+1})$ 之间的差异：

$$\min_{w}\mathcal{L}(w) = \frac{1}{2} \mathbb{E}_{t}\Big[ \big(r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t})\big)^{2} \Big]$$

我们发现，Critic 的目标就是最小化 TD Error $\delta_{t}$ 的平方。因此，当计算完 $\delta_{t}$ 后，不仅能用于近似单步优势 $\hat{A}_{t}$，还能够用于计算 Critic 的损失。与 Actor 类似，依然使用单步数据进行训练。

最后，总结训练步骤如下：

1. Initialize the parameter $\theta$, $w$
2. For $t=0,1,\ldots,T-1$:
   1. Sample the action $a_{t} \sim \pi_{\theta}(a \mid s)$ and then observe $r_{t}$, $s_{t+1}$
   2. Calculate the TD error: $\delta_{t} = r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t})$
   3. Actor (Policy Update): $\theta_{t+1} \gets \theta_{t} + \alpha_{\theta} \hat{A}_{t} \nabla_{\theta} \ln \pi_{\theta_{t}}(a_{t} \mid s_{t})$
   4. Critic (Value Update): $w_{t+1} \gets w_{t} - \alpha_{w} \nabla_{w} \mathcal{L}(w)$

A2C 的特点在于有偏与低方差

低方差

A2C 不再使用完整的未来回报 $G_{t}$，而是使用 TD Error $\delta_{t}$ 来指导 Actor 更新。这个估计值仅依赖于一步的真实奖励 $r_{t}$ 与下一状态 $s_{t+1}$，将未来的期望回报直接使用 $V_{w}(s_{t+1})$ 来近似。因此，A2C 无需经历漫长的随机过程，极大降低了随机性。

有偏

A2C 偏差的来源正是降低方差的 Critic 网络 $V_{w}(s)$，该网络是真实状态价值函数 $V^{\pi}(s)$ 的一个近似。在训练的任何时刻，尤其是早期，$V_{w}(s)$ 几乎不可能是完美的，即 $V_{w}(s) \ne V^{\pi}(s)$。具体来说：

1. 假设 Critic 网络可以准确衡量 $\pi(\cdot \mid s)$ 的价值，即：$V_{w}(s) \approx V^{\pi}(s)$，那么 $\delta_{t}$ 是真实优势函数 $A^{\pi}(s,a)$ 的无偏估计，不会产生系统性的偏差
2. 假设 Critic 网络无法准确衡量 $\pi(\cdot \mid s)$ 的价值，即：$V_{w}(s) \ne V^{\pi}(s)$，那么 $\delta_{t}$ 是真实优势函数 $A^{\pi}(s,a)$ 的有偏估计。尤其是在训练早期，Critic 网络尚未收敛时，$V_{w}(s)$ 对 $V^{\pi}(s)$ 的近似都是偏离真值的，引入了系统性的偏差。

然而，尽管初始时 Critic 是有偏的，但随着训练的进行，Critic 会越来越准，即：$V_{w}(s) \to V^{\pi}(s)$，这个偏差也会越来越小。为了更好地平衡偏差与方差，下节将介绍 GAE (Generalized Advantage Estimation) 来解决这一问题。

Generalized Advantage Estimator (GAE)

在 A2C 中，我们使用 TD Error 来估计单步优势 $\hat{A}_{t}$:

$$\hat{A}_{t} = \delta_{t} = r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t})$$

由于 Critic 网络 $V_{w}(s)$ 对真实状态价值函数 $V^{\pi}(s)$ 的近似可能不准，所以引入了系统性的偏差。

Note

这里讨论的偏差，指的是对最终策略梯度 $\nabla_{\theta}J(\theta)$ 估计的偏差，而不是对优势函数 $A^{\pi}(s,a)$ 估计的偏差。因此，对于 $\hat{A}_{t}^{(k)}$，尽管最后一项 $V_{w}(s_{t})$，可能由于 Critic 网络的不准确性，带来优势估计的偏差，但对于最终策略梯度的估计并没有影响。因为 $V_{w}(s_{t})$ 仅依赖当前状态 $s_{t}$，可视为 baseline。我们已经证明 baseline 对策略梯度的期望无影响。

直观上，为了减少这一偏差，我们可以尽可能少地使用 $V_{w}(s)$ 去近似，尽可能多地信任实际采样结果。为此，不妨将 $V_{w}(s_{t+1})$ 递推展开，便可得到以下一系列优势函数的近似：

$$\begin{aligned} \hat{A}_{t}^{(1)} &= r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t}) &= \hat{G}_{t}^{(1)} - V_{w}(s_{t})\\ \hat{A}_{t}^{(2)} &= r_{t} + \gamma r_{t+1} + \gamma^{2} V_{w}(s_{t+2}) - V_{w}(s_{t}) &= \hat{G}_{t}^{(2)} - V_{w}(s_{t})\\ \cdots &= \cdots \\ \hat{A}_{t}^{(k)} &= \sum_{l=0}^{k-1} \gamma^{l} r_{t+l} + \gamma^{k} V_{w}(s_{t+k}) - V_{w}(s_{t}) &= \hat{G}_{t}^{(k)} - V_{w}(s_{t}) \\ \cdots &= \cdots \\ \hat{A}_{t}^{(\infty)} &= r_{t} + \gamma r_{t+1} + \gamma^{2} r_{t+2} + \cdots - V_{w}(s_{t}) \\ &= \sum_{l=0}^{\infty} \gamma^{l} r_{t+l} - V_{w}(s_{t}) &= \hat{G}_{t}^{(\infty)} - V_{w}(s_{t}) \end{aligned}$$

注意到：

1. 当 $k=1$ 时，对应于 A2C 算法，或者称为 $1$-step TD 估计
   • 低方差：只依赖于一步的随机性
   • 高偏差（有偏）：只有 $r_{t}$ 是实际采样得到的客观事实，而绝大部分的未来价值都被压缩在可能不准确的 Critic $V_{w}(s_{t+1})$ 这个主观猜测里
2. 当 $k \to \infty$ 时，对应于 REINFORCE with baseline 算法，或者称为蒙特卡洛估计
   • 高方差：累积了整条轨迹的随机性
   • 低偏差（无偏）：使用真实的奖励序列来近似回报 $\hat{G}_{t}^{(\infty)} = \sum_{l=0}^{\infty} \gamma^{l} r_{t+l}$
3. 当 $k$ 逐渐增加时,
   • 方差逐渐增大：引入的随机变量 $r_{t+l}$ 逐渐增多，因而方差逐渐增大
   • 偏差逐渐减小：回报 $\hat{G}_{t}^{(k)} = \sum_{l=0}^{k-1} \gamma^{l} r_{t+l} + \gamma^{k} V_{w}(s_{t+k})$ 的前 $k$ 步都是实际采样得到的奖励序列，只有在 $k$ 步之后，才使用 $V_{w}(s_{t+k})$ 进行近似

因此，为了更好的平衡偏差与方差，GAE (Generalized Advantage Estimator) 通过引入一个平衡因子 $\lambda \in [0,1]$ 来权衡 bias-variance tradeoff。在正式给出定义前，我们尝试将 $k$-step 优势使用 TD Error 来表示：

$$\begin{aligned} \hat{A}_{t}^{(1)} &= r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t}) \\ &= \delta_{t} \\ \hat{A}_{t}^{(2)} &= r_{t} + \gamma r_{t+1} + \gamma^{2} V_{w}(s_{t+2}) - V_{w}(s_{t}) \\ &= r_{t} {\color{blue}+\gamma V_{w}(s_{t+1})} - V_{w}(s_{t}) + \gamma r_{t+1} + \gamma^{2} V_{w}(s_{t+2}) {\color{blue}-\gamma V_{w}(s_{t+1})} \\ &= \big(r_{t} + \gamma V_{w}(s_{t+1}) - V_{w}(s_{t})\big) + \gamma \big(r_{t+1} + \gamma V_{w}(s_{t+2}) - V_{w}(s_{t+1})\big) \\ &= \delta_{t} + \gamma \delta_{t+1} \\ \cdots &= \cdots \\ \hat{A}_{t}^{(k)} &= \delta_{t} +\gamma \delta_{t+1} + \ldots + \gamma^{k-1} \delta_{t+k-1} \\ &= \sum_{l=0}^{k-1} \gamma^{l} \delta_{t+l} \\ \cdots &= \cdots \\ \hat{A}_{t}^{(\infty)} &= \sum_{l=0}^{\infty} \gamma^{l} \delta_{t+l} \end{aligned}$$

GAE 被定义为所有 $k$-step 优势估计的指数加权平均：

$$\begin{aligned} \hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)} &= (1-\lambda)\Big(\hat{A}_{t}^{(1)} + \lambda \hat{A}_{t}^{(2)} + \lambda^2 \hat{A}_{t}^{(3)} + \ldots \Big) \\ &= (1-\lambda)\Big(\delta_{t} + \lambda(\delta_{t} + \gamma \delta_{t+1}) + \lambda^{2}(\delta_{t} + \gamma \delta_{t+1} + \gamma^{2} \delta_{t+2})+ \cdots \Big) \\ &= (1-\lambda)\Big( \delta_{t}(1+\lambda+\lambda^{2}+\cdots) + \gamma\delta_{t+1}(\lambda+\lambda^{2}+\ldots) + \ldots \Big) \\ &= (1-\lambda)\bigg(\delta_{t} \frac{1}{1-\lambda} + (\gamma \lambda) \delta_{t+1}\frac{1}{1-\lambda} + \ldots\bigg) \\ &= \sum_{l=0}^{\infty} (\gamma \lambda)^{l} \delta_{t+l} \end{aligned}$$

观察上式可知，

• 当 $\lambda = 0$ 时，$\hat{A}_{t}^{\mathrm{GAE}(\gamma,0)} = \hat{A}_{t}^{(1)} = \delta_{t}$ 退化成 A2C 算法，有偏低方差
• 当 $\lambda = 1$ 时，$\hat{A}_{t}^{\mathrm{GAE}(\gamma,1)} = \hat{A}_{t}^{(\infty)} = \hat{G}_{t}^{(\infty)} - V_{w}(s_{t})$ 退化成 REINFORCE with baseline 算法，无偏高方差

也就是说，$\lambda \to 0$ 时，方差越小，偏差越大；$\lambda \to 1$ 时，方差越大，偏差越小。

为了更深入地探讨 GAE 的本质，我们引入对 $\lambda$-return 的介绍。与 GAE 类似，$\lambda$-return 被定义为所有 $n$-step 回报 $G_{t}^{(n)}$ 的指数加权平均：

$$\begin{aligned} G_{t}^{\lambda} &= (1-\lambda) \Big( G_{t}^{(1)} + \lambda G_{t}^{(2)} + \lambda^{2} G_{t}^{(3)} + \cdots \Big) \\ &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t}^{(n)} \end{aligned}$$

观察上式可知，

• 当 $\lambda = 0$ 时，$\hat{G}_{t}^{\lambda=0} = \hat{G}_{t}^{(1)} = r_{t} + \gamma V_{w}(s_{t+1})$ 退化单步 TD Target
• 当 $\lambda = 1$ 时，$\hat{G}_{t}^{\lambda=1}=\hat{G}_{t}^{(\infty)}$ 退化成蒙特卡洛回报（这里不给出严谨证明）

直观地，我们感觉到 $\hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)} =\hat{G}_{t}^{\lambda} - V_{w}(s_{t})$，GAE 就是用 $\lambda$-return $\hat{G}_{t}^{\lambda}$ 作为价值目标，然后减去 baseline $V_{w}(s_{t})$ 得到的优势函数估计。接下来，我们利用 $\hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)}$ 与 $G_{t}^{\lambda}$ 的定义进行推导：

$$\begin{aligned} \hat{A}_{t}^{\text{GAE}(\gamma,\lambda)} &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \hat{A}_{t}^{(n)} \\ &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \Big(\hat{G}_{t}^{(n)} - V_{w}(s_{t})\Big) \\ &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \hat{G}_{t}^{(n)} - (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} V_{w}(s_{t}) \\ &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \hat{G}_{t}^{(n)} - V_{w}(s_{t}) \\ &= \hat{G}_{t}^{\lambda} - V_{w}(s_{t}) \end{aligned}$$

这里的推导涉及了几何级数的运算：

$$(1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} = (1-\lambda) \cdot \frac{1}{1-\lambda} = 1$$

具体过程不详细给出。

接下来，我们证明 $\lambda$-return $G_{t}^{\lambda}$ 是对 $V^{\pi}(s_{t})$ 的无偏估计。在前文，我们已经证明了 $n$-step return $G_{t}^{(n)}$ 是对 $V^{\pi}(s_{t})$ 的无偏估计。由 $G_{t}^{\lambda}$ 的定义与期望的线性性质可以推导：

$$\begin{aligned} \mathbb{E}_{\pi} \big[G_{t}^{\lambda} \mid S_{t} = s_{t}\big] &= \mathbb{E}_{\pi} \bigg[ (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t}^{(n)} \mid S_{t} = s_{t} \bigg]\\ &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \mathbb{E}_{\pi} \big[ G_{t}^{(n)} \mid S_{t} = s_{t} \big] \\ &= (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \cdot V^{\pi}(s_{t}) \\ &= V^{\pi}(s_{t}) \cdot \bigg( (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} \bigg)\\ &= V^{\pi}(s_{t}) \cdot 1 \\ &= V^{\pi}(s_{t}) \end{aligned}$$

故 $G_{t}^{\lambda}$ 是对 $V^{\pi}(s_{t})$ 的无偏估计。注意，当使用 $V_{w}(s_{t})$ 进行近似时，$\hat{G}_{t}^{\lambda}$ 对 $V^{\pi}(s_{t})$ 近似的偏差方差变化，与 $\hat{A}_{t}^{\text{GAE}(\gamma,\lambda)}$ 对 $A^{\pi}(s_{t},a_{t})$ 的变化一致：

• $\lambda \to 0$ 时，方差越小，偏差越大；
• $\lambda \to 1$ 时，方差越大，偏差越小。

最后，我们来探讨 GAE 的计算方法。尽管 GAE 的无限求和公式在理论上很完美，但在实际计算中并不可行。幸运的是，它可以被写成一个反向迭代的形式。假设轨迹 $\tau$ 长度为 $T$，GAE 可以从 $t=T-1$ 向前遍历到 $0$ 进行递推计算：

$$\hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)} = \delta_{t} + \gamma \lambda \hat{A}_{t+1}^{\mathrm{GAE}(\gamma,\lambda)}$$

在一次轨迹采样结束后，可以计算所有时间步的 TD Error $\delta_{t}$。关注最后一个时刻 $T-1$，由于回合已经结束，进而未来期望收益 $V_{w}(s_{T})$ 与未来优势 $\hat{A}_{T}^{\mathrm{GAE}(\gamma,\lambda)}$ 均为 $0$，因此 $\delta_{T-1} = r_{T-1} + \gamma V_{w}(s_{T}) - V_{w}(s_{T}) = r_{T} - V_{w}(s_{T-1})$，而 $\hat{A}_{T-1}^{\mathrm{GAE}(\gamma,\lambda)} = \delta_{T-1} + \gamma \lambda \cdot 0 = \delta_{T-1} = r_{T-1} - V_{w}(s_{T-1})$。$r_{T-1}$ 由环境给出，而 $V_{w}(s_{T-1})$ 由 Critic 网络给出，因而 $\hat{A}_{T-1}^{\mathrm{GAE}(\gamma,\lambda)}$ 就可以计算。从后往前扫描一遍，就能计算出所有时间步的 GAE。

当计算完 GAE 后，我们可以根据 GAE 与 $\lambda$-return 的关系，进而计算出 $\lambda$-return:

$$\hat{G}_{t}^{\lambda} = \hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)} + V_{w}(s_{t})$$

后续便可作为 Critic 网络的 target。

Importance Sampling

Note

本文不讨论 on-policy 与 off-policy 的严谨分类，更多关注具体的算法步骤。

此前介绍的算法，如 REINFORCE, A2C 面临一个核心问题：样本利用率低。这些算法要求用于更新策略的样本必须由当前策略 $\pi_{\theta}$ 产生，这意味着每当策略参数 $\theta$ 更新后，之前采集的所有样本都必须被丢弃，Agent 需要使用新的策略重新与环境交互，来收集新的样本。而这一过程在很多应用中时间成本非常高，例如 LLMs 的推理。

为了解决这一问题，我们希望能够复用旧策略 $\pi_{\theta_{old}}$ 采集的数据来更新当前策略 $\pi_{\theta}$，大致步骤如下：

1. 假设某次参数更新后得到策略 $\pi_{\theta_{old}}$
2. 使用策略 $\pi_{\theta_{old}}$ 与环境交互收集数据
3. 将收集到的数据重复使用 $k$ 次，即：$\pi_{\theta_{old}} \to \pi_{\theta_{1}} \to \cdots \to \pi_{\theta_{k}}$
4. $k$ 次更新后，令 $\pi_{\theta_{old}} \gets \pi_{\theta_{k}}$。重复 1-4，直至达到设定的停止条件。

重要性采样允许我们在给定来自一个分布 $p(\cdot)$ 的样本 $x$ 时，估计另一个分布 $q(\cdot)$ 下的某个函数 $f(x)$ 的期望值，基本思想如下：

$$\begin{aligned} \mathbb{E}_{x \sim q(\cdot)}[f(x)] &= \int q(x)f(x) dx \\ &= \int \frac{q(x)}{p(x)} p(x) f(x) dx \\ &= \mathbb{E}_{x \sim p(\cdot)}\bigg[\frac{q(x)}{p(x)}f(x)\bigg] \end{aligned}$$

其中，比值 $q(x)/p(x)$ 称为重要性权重。该权重修正了由于在不同分布 $p(\cdot)$ 上采样而引入的偏差。

接下来，我们将重要性采样应用至 A2C 算法，如下：

$$\nabla_{\theta}J(\theta) = \mathbb{E}_{\tau \sim \pi_{\theta_{old}}} \bigg[ \frac{\pi_{\theta}(a_{t} \mid s_{t})}{\pi_{\theta_{old}}(a_{t} \mid s_{t})} \hat{A}_{t} \nabla_{\theta} \ln \pi_{\theta}(a_{t} \mid s_{t}) \bigg]$$

其中，$\tau \sim \pi_{\theta_{old}}$ 意味着该批次数据由旧策略 $\pi_{\theta_{old}}$ 收集而来。注意，这里我们只给出了 Actor 的梯度更新。

实际上，重要性采样存在一个问题：方差过高。如果重要性权重突然变得非常大，即：新旧策略对某一动作的概率分布差异较大（例如：新策略对某个动作的概率远大于旧策略），那么该样本就会主导整个梯度的计算，导致更新极不稳定。为了解决这一问题，PPO (Proximal Policy Optimization) 算法被提出。

Proximal Policy Optimization (PPO)

PPO 的核心思想在于：限制新旧策略之间的差异，防止重要性权重偏离 $1$ 太远。对于限制方法，PPO 存在两种实现变体：PPO-Clip 与 PPO-Penalty。为了公式表示的简洁，我们引入符号 $r_{t}(\theta)$ 来表示新旧策略概率比率：

$$r_{t}(\theta) = \frac{\pi_{\theta}(a_{t} \mid s_{t})}{\pi_{\theta_{old}}(a_{t} \mid s_{t})}$$

PPO-Clip

损失函数如下：

$$\mathcal{L}^{\text{CLIP}}(\theta) = -\mathbb{E}_{t} \Big[\min\big( r_{t}(\theta) \hat{A}_{t}, \mathrm{clip}\big(r_{t}(\theta),1-\epsilon,1+\epsilon\big)\hat{A}_{t} \big)\Big]$$

其中，$\mathrm{clip}\big(r_{t}(\theta),1-\epsilon,1+\epsilon\big)$ 是一个裁剪函数，用于将概率比率 $r_{t}(\theta)$ 限制在 $[1-\epsilon,1+\epsilon]$ 的区间内。这里的 $\epsilon$ 是一个超参数，定义信任区域的大小。

接下来，具体分析该目标函数：

1. 当优势 $\hat{A}_{t} > 0$ 时，即 $a_{t}$ 是一个好动作：
   • 目标函数变为 $\min(r_{t}(\theta), 1 + \epsilon) \hat{A}_{t}$。
   • 为了最大化这个目标，我们会希望增大 $r_t(\theta)$，也就是增加选择这个好动作的概率。
   • 但由于裁剪的存在，$r_t(\theta)$ 的上限被限制在 $1 + \epsilon$。这防止了策略更新过猛，尽管这是一个非常好的动作，策略的提升也是有限度的。
2. 当优势 $\hat{A}_{t} < 0$ 时，即 $a_{t}$ 是一个坏动作：
   • 目标函数变为 $\max(r_{t}(\theta), 1 - \epsilon) \hat{A}_{t}$，因为负数乘以一个小于 $1$ 的数会变得更大，所以 $\min$ 操作实际上变成了 $\max$
   • 为了最大化这个目标，我们会希望减小 $r_{t}(\theta)$，也就是降低选择这个坏动作的概率。
   • 同样，由于裁剪，$r_{t}(\theta)$ 的下限被限制在 $1 - \epsilon$。这防止了策略因为一个糟糕的动作而过度 " 惩罚 " 自己。

PPO-Penalty

损失函数如下：

$$\mathcal{L}^{\text{KLPEN}}(\theta) = -\mathbb{E}_{t} \Big[ r_{t}(\theta) \hat{A}_{t} - \beta \mathbb{D}_{\text{KL}}\big( \pi_{\theta_{old}}(\cdot \mid s_{t}) \| \pi_{\theta}(\cdot \mid s_{t}) \big) \Big]$$

其中，$\mathbb{D}_{\text{KL}}\big(\pi_{\theta_{old}}(\cdot \mid s_{t}) \| \pi_{\theta}(\cdot \mid s_{t})$ 表示新旧策略概率分布的 KL 散度，这个值越大，表明策略变化越大。我们希望每次更新时，新旧策略不要变化太大，因此对 KL 散度施加惩罚。$\beta$ 作为超参数，用于控制惩罚的强度。

Critic in PPO

在 Actor-Critic 框架下，PPO Critic 目标函数如下：

$$\mathcal{L}(w) = \frac{1}{2} \mathbb{E}_{t} \Big[ V^{\pi_{\theta_{old}}}(s_{t}) - V_{w}(s_{t})\big)^{2} \Big]$$

$V^{\pi_{\theta_{old}}}(s_{t})$ 这一理论真值我们可以通过 $\lambda$-return $\hat{G}_{t}^{\lambda}$ 近似。在计算完 GAE 后，便可计算得到 $\hat{G}_{t}^{\lambda}$:

$$\hat{G}_{t}^{\lambda} = \hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)} + V_{w_{old}}(s_{t})$$

因此，最终的目标函数如下：

$$\begin{aligned} \mathcal{L}(w) &= \frac{1}{2} \mathbb{E}_{t} \Big[ V^{\pi_{\theta_{old}}}(s_{t}) - V_{w}(s_{t})\big)^{2} \Big] \\ &= \frac{1}{2} \mathbb{E}_{t} \Big[ \big( \hat{G}_{t}^{\lambda} - V_{w}(s_{t})\big)^{2} \Big] \\ &= \frac{1}{2} \mathbb{E}_{t} \Big[ \big( \hat{A}_{t}^{\mathrm{GAE}(\gamma,\lambda)} + V_{w_{old}}(s_{t}) - V_{w}(s_{t})\big)^{2} \Big] \end{aligned}$$

Reference

• GAE 论文原文：[1506.02438] High-Dimensional Continuous Control Using Generalized Advantage Estimation
• GAE 深入解读：Notes on the Generalized Advantage Estimation Paper
• PPO 论文原文：[1707.06347] Proximal Policy Optimization Algorithms