策略梯度算法（Policy Gradient Methods）

在本文中，我们将从

• 基于价值的方法转向基于策略的方法
• 基于价值函数的方法转向策略函数方法（或称为策略梯度方法）

策略表示：从表格到函数

以前，策略是通过表格表示的：

• 所有状态的动作概率存储在表格$\pi(a|s)$中。表格中的每个条目由状态和动作索引。

	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$
$s_1$	$\pi(a_1	s_1)$	$\pi(a_2	s_1)$	$\pi(a_3
...	...	...	...	...	...
$s_9$	$\pi(a_1	s_9)$	$\pi(a_2	s_9)$	$\pi(a_3

现在，策略可以通过参数化函数表示：

$$\pi(a|s,\theta)$$

其中$\theta \in \mathbb{R}^m$是一个参数向量。

• 该函数可以是一个神经网络，其输入为$s$，输出为采取每个动作的概率，参数为$\theta$。
• 优势：当状态空间较大时，表格表示在存储和泛化效率上较低。
• 函数表示有时也写作$\pi(a,s,\theta)$、$\pi_\theta(a|s)$或$\pi_\theta(a,s)$。

区别

首先，如何定义最优策略？

• 在表格表示的情况下，策略$\pi$是最优的，如果它能最大化每个状态值。
• 在函数表示的情况下，策略$\pi$是最优的，如果它能最大化某些标量指标。

第二，如何访问动作的概率？

• 在表格表示的情况下，采取动作$a$在状态$s$时的概率可以直接通过查表获取。
• 在函数表示的情况下，给定函数结构和参数，我们需要计算函数$\pi(a|s,\theta)$的值。

第三，如何更新策略？

• 在表格表示的情况下，策略$\pi$可以通过直接修改表格中的条目来更新。
• 在函数表示的情况下，策略$\pi$不能再以这种方式更新。相反，它只能通过改变参数$\theta$来更新。

基本思想

• 首先，使用度量（或目标函数）来定义最优策略：$J(\theta)$，它可以定义最优策略。
• 其次，使用基于梯度的优化算法来搜索最优策略：

$$\theta_{t+1} = \theta_t + \alpha \nabla_\theta J(\theta_t)$$

---

目标函数：定义最优策略

目标函数1：平均状态值

第一个指标是平均状态价值，或简称平均价值：

$$\bar{v}_\pi = \sum_{s \in \mathcal{S}} d(s)v_\pi(s)$$

• $\bar{v}_\pi$ 是状态价值的加权平均。
• $d(s) \geq 0$ 是状态 $s$ 的权重。

由于 $\sum_{s \in \mathcal{S}} d(s) = 1$，我们可以将 $d(s)$ 解释为一个概率分布。因此，该指标也可以写作：

$$\bar{v}_\pi = \mathbb{E}_{S \sim d}[v_\pi(S)]$$

如何选择分布 $d$？

情况 1：$d$ 与策略 $\pi$ 无关

• 这种情况相对简单，因为指标的梯度更容易计算：

  $$\nabla_\theta \bar{v}_\pi = d^T \nabla_\theta v_\pi$$

• 在这种情况下，我们特别将 $d$ 记作 $d_0$，将 $\bar{v}_\pi$ 记作 $\bar{v}^0_\pi$。

如何选择 $d_0$？

• 一种简单方法是认为所有状态同等重要，因此选择：

  $$d_0(s) = 1 / |\mathcal{S}|$$

• 另一种重要情况是我们只关注某个特定状态 $s_0$。例如，在某些任务中，每次训练从同一个状态 $s_0$ 开始，此时我们只关注从 $s_0$ 开始的长期回报。这种情况下：

  $$d_0(s_0) = 1, \quad d_0(s \ne s_0) = 0$$

  因此，此时：

  $$\bar{v}_\pi = v_\pi(s_0)$$

情况 2：$d$ 依赖于策略 $\pi$

• 一种常见方式是将 $d$ 选作 $d_\pi(s)$，即策略 $\pi$ 下的平稳分布。平稳分布的细节可以参考上一讲。

• 选择 $d_\pi$ 的含义如下：

  • $d_\pi$ 反映了在策略 $\pi$ 下马尔可夫决策过程的长期行为；
  • 如果某个状态在长期内频繁访问，则说明它更重要，应给予更大权重；
  • 如果某个状态很少被访问，则给予较小权重。

等价表达式

在文献中你经常会看到以下指标：

$$J(\theta) = \lim_{n \to \infty} \mathbb{E} \left[ \sum_{t=0}^n \gamma^t R_{t+1} \right] = \mathbb{E} \left[ \sum_{t=0}^\infty \gamma^t R_{t+1} \right]$$

它们是相同的**，因为：

$$\begin{align*} J(\theta) &= \mathbb{E} \left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \right] \\ &= \sum_{s \in \mathcal{S}} d(s) \mathbb{E} \left[ \sum_{t=0}^{\infty} \gamma^t R_{t+1} \mid S_0 = s \right] \\ &= \sum_{s \in \mathcal{S}} d(s) v_\pi(s) \\ &= \bar{v}_\pi \end{align*}$$

目标函数2：平均奖励

第二个指标是平均一步奖励，或简称平均奖励：

$$\bar{r}_\pi \doteq \sum_{s \in \mathcal{S}} d_\pi(s) r_\pi(s) = \mathbb{E}[r_\pi(S)],$$

其中 $S \sim d_\pi$，

$$\begin{align*} r_\pi(s) &= \sum_{a \in \mathcal{A}} \pi(a|s) r(s, a) \\ r(s, a) &= \mathbb{E}[R \mid s, a] = \sum_r r p(r \mid s, a) \end{align*}$$

备注：

• $\bar{r}_\pi$ 就是即时奖励的加权平均；
• $r_\pi(s)$ 是从状态 $s$ 可获得的平均即时奖励；
• $d_\pi$ 是平稳分布。

等价表达式

• 假设一个智能体遵循某个策略并生成一条轨迹，其奖励序列为 $(R_1, R_2, \dots)$。
• 沿该轨迹的平均单步奖励为：

$$\begin{aligned} &\lim_{n \to \infty} \frac{1}{n} \mathbb{E} \left[ R_1 + R_2 + \cdots + R_n \mid S_0 = s_0 \right] \\ = &\lim_{n \to \infty} \frac{1}{n} \mathbb{E} \left[ \sum_{t=0}^{n-1} R_{t+1} \mid S_0 = s_0 \right] \end{aligned}$$

其中 $s_0$ 是轨迹的起始状态。

一个重要事实是：

$$\begin{align*} \lim_{n \to \infty} \frac{1}{n} \mathbb{E} \left[ \sum_{t=0}^{n-1} R_{t+1} \mid S_0 = s_0 \right] &= \lim_{n \to \infty} \frac{1}{n} \mathbb{E} \left[ \sum_{t=0}^{n-1} R_{t+1} \right] \\ &= \sum_s d_\pi(s) r_\pi(s) \\ &= \bar{r}_\pi \end{align*}$$

备注：

• 重点： 起始状态 $s_0$ 无关紧要；
• 方程的推导过程并不简单，可在我的书中找到详细解释。

总结

指标 (Metric)	表达式 1 (Expression 1)	表达式 2 (Expression 2)	表达式 3 (Expression 3)
$\bar{v}_\pi$	$\sum_{s \in \mathcal{S}} d(s)v_\pi(s)$	$\mathbb{E}_{S \sim d}[v_\pi(S)]$	$\lim_{n \to \infty} \mathbb{E} \left[ \sum_{t=0}^n \gamma^t R_{t+1} \right]$
$\bar{r}_\pi$	$\sum_{s \in \mathcal{S}} d_\pi(s)r_\pi(s)$	$\mathbb{E}_{S \sim d_\pi}[r_\pi(S)]$	$\lim_{n \to \infty} \frac{1}{n} \mathbb{E} \left[ \sum_{t=0}^{n-1} R_{t+1} \right]$

备注 1：

• 所有这些指标都是策略 $\pi$ 的函数。
• 由于策略 $\pi$ 是由参数 $\theta$ 表示的，因此这些指标也是 $\theta$ 的函数。
• 换句话说，不同的 $\theta$ 值可以产生不同的指标值。

因此，我们可以搜索使指标最大的最优的 $\theta$ 值。 这正是策略梯度方法的基本思想。

备注 2：

• 一个复杂之处在于，这些指标可以在折扣情形（$\gamma \in (0, 1)$）或非折扣情形（$\gamma = 1$）下定义；
• 非折扣情形并不简单；
• 本文目前只考虑折扣情形。关于非折扣情形的更多内容，请参阅教材。

备注 3：

• $\bar{r}_\pi$ 和 $\bar{v}_\pi$ 之间是什么关系？

• 这两个指标是等价的（但不相等）。具体来说，在折扣情形 $\gamma < 1$ 时，有：

  $$\bar{r}_\pi = (1 - \gamma)\bar{v}_\pi$$

因此，它们可以同时最大化。

---

目标函数的梯度

给定一个指标，接下来我们将：

• 推导它的梯度；
• 然后，应用基于梯度的方法来优化该指标。

梯度的计算是策略梯度方法中最复杂的部分之一！

这是因为：

• 首先，我们需要区分不同的指标：$\bar{v}_\pi$，$\bar{r}_\pi$，$\bar{v}_\pi^0$；
• 其次，我们需要区分折扣情况和非折扣情况。

梯度表达式

$$\nabla_\theta J(\theta) = \sum_{s \in \mathcal{S}} \eta(s) \sum_{a \in \mathcal{A}} \nabla_\theta \pi(a|s, \theta) q_\pi(s, a)$$

以上是一个统一形式，适用于多种情况：

• $J(\theta)$ 可以是 $\bar{v}_\pi$、$\bar{r}_\pi$ 或 $\bar{v}_\pi^0$；
• 等号 "=" 可以表示严格等于、近似等于或成比例；
• $\eta$ 是状态的分布或权重。

相关信息

这个表达式的推导非常复杂，此处不赘述。 对于大多数读者，掌握这个表达式就足够了。

一个简洁且重要的梯度表达式：

$$\begin{aligned} \nabla_\theta J(\theta) &= \sum_{s \in \mathcal{S}} \eta(s) \sum_{a \in \mathcal{A}} \nabla_\theta \pi(a|s, \theta) q_\pi(s, a) \\ &= \mathbb{E}_{S \sim \eta, A \sim \pi} \left[ \nabla_\theta \ln \pi(A|S, \theta) q_\pi(S, A) \right] \end{aligned}$$

这个表达式为什么有用？

• 因为我们可以用样本来近似这个梯度：

$$\nabla_\theta J \approx \nabla_\theta \ln \pi(a|s, \theta) q_\pi(s, a)$$

其中 $s, a$ 是采样值。这就是随机梯度下降（SGD）的核心思想。

如何证明上面的等式？

证明：考虑函数 $\ln \pi$，其中 $\ln$ 表示自然对数。显然有：

$$\nabla_\theta \ln \pi(a|s, \theta) = \frac{\nabla_\theta \pi(a|s, \theta)}{\pi(a|s, \theta)}$$

因此，

$$\nabla_\theta \pi(a|s, \theta) = \pi(a|s, \theta) \nabla_\theta \ln \pi(a|s, \theta)$$

于是我们有：

$$\begin{align*} \nabla_\theta J &= \sum_s \eta(s) \sum_a \nabla_\theta \pi(a|s, \theta) q_\pi(s, a) \\ &= \sum_s \eta(s) \sum_a \pi(a|s, \theta) \nabla_\theta \ln \pi(a|s, \theta) q_\pi(s, a) \\ &= \mathbb{E}_{S \sim \eta} \left[ \sum_a \pi(a|S, \theta) \nabla_\theta \ln \pi(a|S, \theta) q_\pi(S, a) \right] \\ &= \mathbb{E}_{S \sim \eta, A \sim \pi} \left[ \nabla_\theta \ln \pi(A|S, \theta) q_\pi(S, A) \right] \end{align*}$$

备注

由 $\ln \pi(a|s, \theta)$ 的定义可知，对于所有的 $s, a, \theta$，我们必须有：

$$\pi(a|s, \theta) > 0$$

• 这可以通过使用Softmax 函数来实现，它能够将任意向量从 $(-\infty, +\infty)$ 映射到 $(0, 1)$：

  • 例如，对于任意向量 $x = [x_1, \dots, x_n]^T$：

    $$z_i = \frac{e^{x_i}}{\sum_{j=1}^n e^{x_j}}$$

    其中 $z_i \in (0, 1)$ 且 $\sum_{i=1}^n z_i = 1$。

• 策略函数具体形式为：

  $$\pi(a|s, \theta) = \frac{e^{h(s, a, \theta)}}{\sum_{a' \in \mathcal{A}} e^{h(s, a', \theta)}}$$

  其中 $h(s, a, \theta)$ 是需要学习的另一个函数。

• 这种基于 Softmax 的形式可以通过一个神经网络实现，其输入是 $s$，参数是 $\theta$。网络的输出维度是 $|\mathcal{A}|$，每个输出对应一个动作 $a$ 的 $\pi(a|s, \theta)$。输出层的激活函数应为 Softmax。

• 由于 $\pi(a|s, \theta) > 0$ 对所有动作 $a$ 成立，因此该参数化策略是随机的（stochastic），具有一定的探索性（exploratory）。

  • 此外，也存在确定性策略梯度（Deterministic Policy Gradient, DPG）方法。

---

蒙特卡洛策略梯度 （REINFORCE）

Gradient-ascent algorithm 梯度上升算法

算法描述

现在，我们介绍第一个策略梯度算法，用于寻找最优策略！

1）最大化 $J(\theta)$ 的梯度上升算法如下：

$$\begin{align*} \theta_{t+1} &= \theta_t + \alpha \nabla_\theta J(\theta_t) \\ &= \theta_t + \alpha \mathbb{E} \left[ \nabla_\theta \ln \pi(A|S, \theta_t) q_\pi(S, A) \right] \end{align*}$$

2）由于真实梯度不可得，我们用随机版本替代：

$$\theta_{t+1} = \theta_t + \alpha \nabla_\theta \ln \pi(a_t | s_t, \theta_t) q_\pi(s_t, a_t)$$

3）此外，$q_\pi$ 不可得，我们再用估计值替代：

$$\theta_{t+1} = \theta_t + \alpha \nabla_\theta \ln \pi(a_t | s_t, \theta_t) \underbrace{q_t(s_t, a_t)}_{\textcolor{blue}{\text{估计值}}}$$

• 如果 $q_\pi(s_t, a_t)$ 由蒙特卡洛估计获得，该算法有一个专属名字：REINFORCE
• REINFORCE 是最早且最简单的策略梯度算法之一。
• 很多其他策略梯度方法（如 actor-critic 方法）都可以视作对 REINFORCE 的扩展。

伪代码

如何进行采样？

$$\mathbb{E}_{S \sim \eta, A \sim \pi} \left[ \nabla_\theta \ln \pi(A|S, \theta_t) q_\pi(S, A) \right] \Rightarrow \nabla_\theta \ln \pi(a|s, \theta_t) q_\pi(s, a)$$

• 如何采样 $S$？

  • $S \sim \eta$，其中 $\eta$ 是策略 $\pi$ 下的长期行为分布；
  • 实际中人们通常不关心它的具体形式。

• 如何采样 $A$？

  • $A \sim \pi(A|S, \theta)$，因此 $a_t$ 应该按照当前策略 $\pi(\theta_t)$ 在 $s_t$ 下采样。
  • 因此，策略梯度方法是 on-policy 的。

如何理解该算法？

由于：

$$\nabla_\theta \ln \pi(a_t | s_t, \theta_t) = \frac{\nabla_\theta \pi(a_t | s_t, \theta_t)}{\pi(a_t | s_t, \theta_t)}$$

算法可以重写为：

$$\begin{align*} \theta_{t+1} &= \theta_t + \alpha \nabla_\theta \ln \pi(a_t | s_t, \theta_t) q_t(s_t, a_t) \\ &= \theta_t + \alpha \underbrace{\left( \frac{q_t(s_t, a_t)}{\pi(a_t | s_t, \theta_t)} \right)}_{\beta_t} \nabla_\theta \pi(a_t | s_t, \theta_t) \end{align*}$$

因此，我们有一个重要的算法表达式：

$$\theta_{t+1} = \theta_t + \alpha \beta_t \nabla_\theta \pi(a_t | s_t, \theta_t)$$

假设 $\alpha$ 足够小。

对上述更新的直觉解释如下：

解释：

• 若 $\beta_t > 0$，则选择 $(s_t, a_t)$ 的概率上升：

  $$\pi(a_t | s_t, \theta_{t+1}) > \pi(a_t | s_t, \theta_t)$$

• 若 $\beta_t < 0$，则选择 $(s_t, a_t)$ 的概率下降：

  $$\pi(a_t | s_t, \theta_{t+1}) < \pi(a_t | s_t, \theta_t)$$

数学推导：

当 $\theta_{t+1} - \theta_t$ 足够小时，由微分定义有：

$$\begin{align*} \pi(a_t | s_t, \theta_{t+1}) &\approx \pi(a_t | s_t, \theta_t) + (\nabla_\theta \pi(a_t | s_t, \theta_t))^T (\theta_{t+1} - \theta_t) \\ &= \pi(a_t | s_t, \theta_t) + \alpha \beta_t (\nabla_\theta \pi(a_t | s_t, \theta_t))^T (\nabla_\theta \pi(a_t | s_t, \theta_t)) \\ &= \pi(a_t | s_t, \theta_t) + \alpha \beta_t \left\| \nabla_\theta \pi(a_t | s_t, \theta_t) \right\|^2 \end{align*}$$

$\beta_t$ 平衡探索与利用

原因如下：

• 首先，$\beta_t$ 与 $q_t(s_t, a_t)$ 成正比：

  $$\text{值越大 } q_t(s_t, a_t) \Rightarrow \text{值越大 } \beta_t \Rightarrow \text{值越大 } \pi(a_t | s_t, \theta_{t+1})$$

  因此，算法**倾向于利用（exploit）**高价值的动作。

• 其次，$\beta_t$ 与 $\pi(a_t | s_t, \theta_t)$ 成反比（当 $q_t(s_t, a_t) > 0$）：

  $$\text{值越小 } \pi(a_t | s_t, \theta_t) \Rightarrow \text{值越大 } \beta_t \Rightarrow \text{值越大 } \pi(a_t | s_t, \theta_{t+1})$$

  因此，算法**倾向于探索（explore）**那些原本概率较低的动作。