强化学习的数学基础 - Chapter 9

赵老师开源的 Github 仓库、赵老师的 B站 课程视频

背景来自 XHS 像素点 Z（如有问题，请在下方评论区留言，侵删）

Overview

上一章我们已经学会用函数来表达 state-value 和 action-value，这一章我们尝试用函数来表示 policy。之前所有方法都称为是 value-based 方法，以 state-value 或 action-value 来策动算法；而 policy-based 方法则是 设置一个关于 policy 的目标函数，通过优化这个目标函数，直接得到 optimal policy。

Outline：

1. policy gradient 的基本思路
2. 基于 metric 的方法
   1. 以 metric 来定义 optimal policy
   2. 如何求 metric 的梯度
   3. 基于 metric 优化（最大化/最小化）
3. 总结

---

策略梯度的基本思路

Lec 43

策略的函数表示

此前，策略一直用表格来表示：

• 所有状态的动作概率都存储在一张表 $\pi(a|s)$ 中。表的每个条目由状态（state）和动作（action）索引。
• 我们可以直接访问或修改表中的某个值。

	$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_1)$	$\pi(a_4|s_1)$	$\pi(a_5|s_1)$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
$s_9$	$\pi(a_1|s_9)$	$\pi(a_2|s_9)$	$\pi(a_3|s_9)$	$\pi(a_4|s_9)$	$\pi(a_5|s_9)$

现在，我们尝试用参数化函数来表示 policy：

$$\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$ 是最优的，当且仅当它能最大化某个标量指标（scalar metric）。

第二，如何获取某个动作的概率？

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

第三，如何更新策略？

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

策略梯度的基本思想很简单：

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

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

尽管 policy gradient 的思想很简单，但当我们试图回答以下问题时，难度就出现了：

• 应该使用什么合适的指标？
• 如何计算这些指标的梯度？
• 如何根据策略梯度进行优化？

---

指标的选取

Lec 44 & 45

主要有两种指标：

• 平均状态值（average state value）
• 平均单步奖励（average one-step reward）

平均状态值

平均状态值（average state value）简称平均值（average value）。 具体地，该指标定义为 state-value 的 加权平均。

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

• $d(s) \ge 0$ 是状态 $s$ 的权重。

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

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

  其中 $S \sim d$.

上面的公式还可以写为向量积形式，

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

其中

$$v_\pi = [\dots, v_\pi(s), \dots]^T \in \mathbb{R}^{|\mathcal{S}|}, \quad d = [\dots, d(s), \dots]^T \in \mathbb{R}^{|\mathcal{S}|}.$$

这个表达式在分析其梯度时特别有用。

如何选择分布 d ？

有两种情况。

• 第一种情况：$d$ 独立于策略 $\pi$。
  • 这种情况相对简单，因为该指标的梯度更容易计算。
  • 在这种情况下，我们特别将 $d$ 记为 $d_0$，将 $\bar{v}_\pi$ 记为 $\bar{v}_\pi^0$。
  • 如何选择 $d_0$？
    • 一种简单的方法是将所有状态视为同等重要，因此选择 $d_0(s) = 1/|\mathcal{S}|$.
    • 另一个重要的情况是，我们只对某个特定状态 $s_0$ 感兴趣。
      • 例如，某些任务中的回合（episodes）总是从相同的状态 $s_0$ 开始（游戏开机界面）。那么，我们只关心从 $s_0$ 开始的长期回报。在这种情况下，

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

• 第二种情况：$d$ 依赖于策略 $\pi$。

  • 一种常见的方法是将 $d$ 选为 $d_\pi(s)$，即在 $\pi$ 下的 平稳分布（stationary distribution）。

    平稳分布的详细内容可以在上一讲和教材中找到。

    • $d_\pi$ 的一个基本性质是它满足

      $$d_\pi^T P_\pi = d_\pi^T,$$

      其中 $P_\pi$ 是状态转移概率矩阵。

    • 选择 $d_\pi$ 的解释如下：

      • 如果一个状态在长期运行中被频繁访问，它就更重要，应该赋予更大的权重。
      • 如果一个状态很少被访问，我们就给它较小的权重。

平均单步奖励

平均单步奖励（average one-step reward）简称平均奖励（average reward）。具体地，该指标为单步即时奖励的 加权平均：

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

其中 $S \sim d_\pi$. 此处，

• 权重 $d_\pi$ 是平稳分布。
• $r_\pi(s) \doteq \sum_{a \in \mathcal{A}} \pi(a|s) r(s,a)$ 是从状态 $s$ 开始可以获得的单步即时奖励的平均值
  • 其中，$r(s,a) = \mathbb{E}[R|s,a] = \sum_{r} r p(r|s,a)$

大致过程（不断求期望）：$r_\pi (s,a) \implies r_\pi(s) \implies r_\pi$

另一个等价形式

• 假设一个 agent 遵循给定的策略并生成一条轨迹，其奖励为 $(R_{t+1}, R_{t+2}, \dots)$。

• 沿这条轨迹的平均单步奖励为

  $$\lim_{n \to \infty} \frac{1}{n} \mathbb{E}\left[ R_{t+1} + R_{t+2} + \dots + R_{t+n} \mid S_t = s_0 \right]= \lim_{n \to \infty} \frac{1}{n} \mathbb{E}\left[ \sum_{k=1}^{n} R_{t+k} \mid S_t = s_0 \right]$$

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

一个重要的性质是：

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

注意：

• 起始状态 $s_0$ 并不重要。
• $\bar{r}_\pi$ 的两种定义是等价的。

补充说明

补充 1：

• 所有这些 metrics 都是策略 $\pi$ 的函数。
• 由于 $\pi$ 由 $\theta$ 参数化，这些 metrics 也是 $\theta$ 的函数。
• 换句话说，不同的 $\theta$ 值会产生不同的 metric values
• 因此，我们可以搜索最优的 $\theta$ 值来最大化这些 metrics

这就是 策略梯度方法（policy gradient methods）的基本思想。

补充 2：

• 一个复杂之处在于，这些指标既可以在 折扣情况（discounted case，其中 $\gamma \in (0,1)$）下定义，也可以在无折扣情况（undiscounted case，其中 $\gamma = 1$）下定义。
  • 这是因为我们只对 immediate reward 感兴趣，并没有设计到 return，因此也无所谓 discount rate。
• 本书到目前为止只考虑折扣情况。关于无折扣情况的细节，具体请参阅教材。

补充 3：

• 直观上，$\bar{r}_\pi$ 更加短视，因为它仅仅考虑即时奖励；而 $\bar{v}_\pi$ 考虑的是所有步骤的总奖励。
• 这两个指标是相互等价的。（证明如下）
• 在折扣情况 $\gamma < 1$ 下，有

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

证明过程在下一小节

练习

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

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

它与我们刚才介绍的指标有什么关系？

答案

首先，澄清并理解这个指标。

• 它从 $S_0 \sim d$ 开始，然后经历 $A_0, R_1, S_1, A_1, R_2, S_2, \dots$
• $A_t \sim \pi(S_t)$，且 $R_{t+1}, S_{t+1} \sim p(R_{t+1}|S_t, A_t), p(S_{t+1}|S_t, A_t)$

那么，我们知道这个指标与平均状态值是相同的，因为

$$\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*}$$

指标的梯度

Lec 46

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

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

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

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

下面小节对应于老师的上课内容，而 9.3.1&2 抄自老师书上的对应章节，为具体证明过程。

梯度结果的总结

梯度结果可以总结为

$$\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$ 是状态的分布或权重。

一些具体结果如下：

$$\color{red}{ \begin{align*} \nabla_\theta \bar{r}_\pi &\simeq \sum_{s} d_\pi(s) \sum_{a} \nabla_\theta \pi(a|s,\theta) q_\pi(s,a), \\ \nabla_\theta \bar{v}_\pi &= \frac{1}{1-\gamma} \nabla_\theta \bar{r}_\pi \\ \nabla_\theta \bar{v}_\pi^0 &= \sum_{s \in \mathcal{S}} \rho_\pi(s) \sum_{a \in \mathcal{A}} \nabla_\theta \pi(a|s,\theta) q_\pi(s,a) \end{align*} }$$

梯度的紧凑且有用的形式

$$\begin{align*} \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}\left[ \nabla_\theta \ln \pi(A|S,\theta) \, q_\pi(S,A) \right] \end{align*}$$

其中 $S \sim \eta$ 且 $A \sim \pi(A|S,\theta)$。

• 为什么这个表达式有用？
  • 因为我们可以用样本来近似梯度！
    • $\nabla_\theta J \approx \nabla_\theta \ln \pi(a|s,\theta) \, q_\pi(s,a)$

如何证明上述等式？

考虑函数 $\ln \pi$，其中 $\ln$ 是自然对数。容易看出

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

于是，我们有

$$\begin{align*} \nabla_\theta J &= \sum_{s} d(s) \sum_{a} \nabla_\theta \pi(a|s,\theta) q_\pi(s,a) \\ &= \sum_{s} d(s) \sum_{a} \pi(a|s,\theta) \nabla_\theta \ln \pi(a|s,\theta) q_\pi(s,a) \\ &= \mathbb{E}_{S \sim d}\left[ \sum_{a} \pi(a|S,\theta) \nabla_\theta \ln \pi(a|S,\theta) q_\pi(S,a) \right] \\ &= \mathbb{E}_{S \sim d, A \sim \pi}\left[ \nabla_\theta \ln \pi(A|S,\theta) q_\pi(S,A) \right] \\ &\doteq \mathbb{E}\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, \ldots, 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。
• 由于对于所有 $a$ 都有 $\pi(a|s, \theta) > 0$，参数化策略是随机的，因此具有探索性。
  • 此外，还存在确定性策略梯度（Deterministic Policy Gradient，DPG）方法。
    • 确定性也是有优势的：如果要输出无穷多个 $\pi(a|s, \theta)$，那么上面的方法就不行了，此时 DPG 是可以工作的.

9.3.1 推导策略梯度：有折扣的情况

下面开始推导目标函数的梯度。首先我们考虑有折扣的情况，即 $\gamma \in (0,1)$，这也是到目前为止本书一直考虑的情况。此时，状态值和动作值的定义是

$$\begin{align*} v_{\pi}(s) &= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s], \\ q_{\pi}(s,a) &= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s, A_t = a]. \end{align*}$$

并且它们满足 $v_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) q_{\pi}(s,a)$。

这一小节分三个部分来说明：

• $\bar{v}_{\pi}(\theta)$ 是与 $\bar{r}_{\pi}(\theta)$ 等价的目标函数

目标函数的等价性

第一，我们证明 $\bar{v}_{\pi}(\theta)$ 是与 $\bar{r}_{\pi}(\theta)$ 等价的目标函数。

引理 9.1： $\bar{v}_\pi(\theta)$ 与 $\bar{r}_\pi(\theta)$ 等价

在有折扣的情况下，即当 $\gamma \in (0,1)$ 时，有

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

因此，$\bar{v}_\pi(\theta)$ 和 $\bar{r}_\pi(\theta)$ 可以被同时最大化。

证明： 注意到

$$\bar{v}_\pi(\theta) = d_\pi^{\mathrm{T}} v_\pi, \quad \bar{r}_\pi(\theta) = d_\pi^{\mathrm{T}} r_\pi$$

其中，$v_\pi, r_\pi$ 满足贝尔曼方程 $v_\pi = r_\pi + \gamma P_\pi v_\pi$。在贝尔曼方程两边同乘以 $d_\pi^{\mathrm{T}}$ 可得

$$\bar{v}_\pi = \bar{r}_\pi + \gamma d_\pi^{\mathrm{T}} P_\pi v_\pi = \bar{r}_\pi + \gamma d_\pi^{\mathrm{T}} v_\pi = \bar{r}_\pi + \gamma \bar{v}_\pi.$$

上式可推出 (9.13)。 $\square$

状态值对策略的梯度

第二，下面的引理给出了任意一个状态值对策略的梯度。

引理 9.2 (状态值的梯度)：在有折扣的情况下，即当 $\gamma \in (0,1)$ 时，对于任意 $s \in \mathcal{S}$ 都有

$$\nabla_{\theta} v_{\pi}(s) = \sum_{s^\prime \in \mathcal{S}} {\Pr}_{\pi}(s^\prime \mid s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s^\prime, \theta) q_{\pi}(s^\prime, a), \tag{9.14}$$

其中，

• ${\Pr}_{\pi} (s^\prime \mid s) \doteq \sum_{k=0}^{\infty} \gamma^k [P_{\pi}^k]_{ss^\prime} = \left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime}$
  是在策略 $\pi$ 下从状态 $s$ 转移到状态 $s^\prime$ 的折扣总概率。
• 这里 $[\cdot]_{ss^\prime}$ 表示矩阵的第 $s$ 行和第 $s^\prime$ 列的元素。
  • $[P_{\pi}^k]_{ss^\prime}$ 等于在策略 $\pi$ 下恰好用 $k$ 步从 $s$ 转移到 $s^\prime$ 的概率。

证明：

首先，对任意 $s \in \mathcal{S}$ 有

$$\begin{align*} \nabla_{\theta} v_{\pi}(s) &= \nabla_{\theta} \left[\sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) q_{\pi}(s, a)\right] \\ &= \sum_{a \in \mathcal{A}} \left[\nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) + \pi(a \mid s, \theta) \nabla_{\theta} q_{\pi}(s, a)\right], \tag{9.15} \end{align*}$$

其中动作值 $q_{\pi}(s,a)$ 的表达式为

$$q_{\pi}(s,a) = r(s,a) + \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) v_{\pi}(s^\prime).$$

在上式两边求对 $\theta$ 的梯度可得

$$\nabla_{\theta} q_{\pi}(s,a) = 0 + \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime).$$

上式中 $r(s,a) = \sum_r r p(r \mid s, a)$ 对 $\theta$ 的梯度等于 $0$，这是因为这一项与 $\theta$ 无关。将上式代入 (9.15) 可得

$$\begin{align*} \nabla_{\theta} v_{\pi}(s) &= \sum_{a \in \mathcal{A}} \left[\nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) + \pi(a \mid s, \theta) \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime)\right] \\ &= \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) + \gamma \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime). \tag{9.16} \end{align*}$$

我们的任务是推导 $\nabla_{\theta} v_{\pi}$ 的表达式，值得注意的是它出现在上式的两边。我们使用基于矩阵-向量形式的方法进行表示。首先，设

$$u(s) \doteq \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a).$$

其次，有

$$\sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime) = \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s) \nabla_{\theta} v_{\pi}(s^\prime) = \sum_{s^\prime \in \mathcal{S}} [P_{\pi}]_{ss^\prime} \nabla_{\theta} v_{\pi}(s^\prime),$$

因此，式 (9.16) 的矩阵-向量形式为

$$\underbrace{\begin{bmatrix} \vdots \\ \nabla_{\theta} v_{\pi}(s) \\ \vdots \end{bmatrix}}_{\nabla_{\theta} v_{\pi} \in \mathbb{R}^{mn}} = \underbrace{\begin{bmatrix} \vdots \\ u(s) \\ \vdots \end{bmatrix}}_{u \in \mathbb{R}^{mn}} + \gamma (P_{\pi} \otimes I_m) \underbrace{\begin{bmatrix} \vdots \\ \nabla_{\theta} v_{\pi}(s^\prime) \\ \vdots \end{bmatrix}}_{\nabla_{\theta} v_{\pi} \in \mathbb{R}^{mn}}.$$

其中，

• $n = |\mathcal{S}|$ 是状态的个数，
• $m$ 是参数向量 $\theta$ 的维度。

上式出现了克罗内克积（Kronecker product）$\otimes$，这是因为 $\nabla_{\theta} v_{\pi}(s)$ 是一个向量。上式可以更简洁地写为

$$\nabla_{\theta} v_{\pi} = u + \gamma (P_{\pi} \otimes I_m) \nabla_{\theta} v_{\pi}.$$

显然上式是关于 $\nabla_{\theta} v_{\pi}$ 的一个线性方程，其解为

$$\begin{align*} \nabla_{\theta} v_{\pi} &= (I_{nm} - \gamma P_{\pi} \otimes I_m)^{-1} u \\ &= (I_n \otimes I_m - \gamma P_{\pi} \otimes I_m)^{-1} u \\ &= \left[(I_n - \gamma P_{\pi})^{-1} \otimes I_m\right] u. \tag{9.17} \end{align*}$$

式 (9.17) 给出了 $\nabla_{\theta} v_{\pi}$ 的向量形式，其针对状态 $s$ 的展开形式为

$$\begin{align*} \nabla_{\theta} v_{\pi}(s) &= \sum_{s^\prime \in \mathcal{S}} \left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime} u(s^\prime) \\ &= \sum_{s^\prime \in \mathcal{S}} \left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime} \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s^\prime, \theta) q_{\pi}(s^\prime, a). \tag{9.18} \end{align*}$$

如何解读上式中的 $\left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime}$ 呢？它的解读如下所示。由于 $(I_n - \gamma P_{\pi})^{-1} = I + \gamma P_{\pi} + \gamma^2 P_{\pi}^2 + \cdots$，我们有

$$\left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime} = [I]_{ss^\prime} + \gamma [P_{\pi}]_{ss^\prime} + \gamma^2 [P_{\pi}^2]_{ss^\prime} + \cdots = \sum_{k=0}^{\infty} \gamma^k [P_{\pi}^k]_{ss^\prime}.$$

注意，$[P_{\pi}^k]_{ss^\prime}$ 是从 $s$ 出发恰好用 $k$ 步转移到 $s^\prime$ 的概率（见方框 8.1）。因此，$\left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime}$ 是从 $s$ 转移到 $s^\prime$ 的总概率。通过令 $\left[(I_n - \gamma P_{\pi})^{-1}\right]_{ss^\prime} \doteq {\Pr}_{\pi}(s^\prime \mid s)$，方程 (9.18) 变为 (9.14)。

$\bar{v}_{\pi}^0$ 的梯度

基于引理 9.2，下面推导 $\bar{v}_{\pi}^0$ 的梯度。正如前面提到的，这里的上标 “$0$” 表示该目标函数中的状态概率分布与策略 $\pi$ 无关。

定理 9.2 (有折扣的情况下 $\bar{v}_{\pi}^0$ 的梯度)。

在有折扣的情况下，即当 $\gamma \in (0,1)$ 时，$\bar{v}_{\pi}^0 = d_0^{\mathrm{T}} v_{\pi}$ 的梯度是

$$\color{lightblue}{\nabla_{\theta} \bar{v}_{\pi}^0 = \mathbb{E}\left[\nabla_{\theta} \ln \pi(A \mid S, \theta) q_{\pi}(S, A)\right],}$$

其中，$S \sim \rho_{\pi}, A \sim \pi(S, \theta)$ 而且

$$\rho_{\pi}(s) = \sum_{s^\prime \in \mathcal{S}} d_0(s^\prime) {\Pr}_{\pi}(s \mid s^\prime), \qquad s \in \mathcal{S}, \tag{9.19}$$

其中 ${\Pr}_{\pi}(s \mid s^\prime) = \sum_{k=0}^{\infty} \gamma^k [P_{\pi}^k]_{s^\prime s} = \left[(I - \gamma P_{\pi})^{-1}\right]_{s^\prime s}$ 是在策略 $\pi$ 下从 $s^\prime$ 到 $s$ 的折扣总概率。

证明：

对 $\bar{v}_{\pi}^0 = d_0^{\mathrm{T}} v_{\pi}$ 两边求梯度。由于 $d_0(s)$ 与 $\pi$ 无关，可得

$$\nabla_{\theta} \bar{v}_{\pi}^0 = \nabla_{\theta} \sum_{s \in \mathcal{S}} d_0(s) v_{\pi}(s) = \sum_{s \in \mathcal{S}} d_0(s) \nabla_{\theta} v_{\pi}(s).$$

将引理 9.2 中 $\nabla_{\theta} v_{\pi}(s)$ 的表达式代入上式可得

$$\begin{align*} \nabla_{\theta} \bar{v}_{\pi}^0 &= \sum_{s \in \mathcal{S}} d_0(s) \nabla_{\theta} v_{\pi}(s) = \sum_{s \in \mathcal{S}} d_0(s) \sum_{s^\prime \in \mathcal{S}} {\Pr}_{\pi}(s^\prime \mid s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s^\prime, \theta) q_{\pi}(s^\prime, a) \\ &= \sum_{s^\prime \in \mathcal{S}} \left(\sum_{s \in \mathcal{S}} d_0(s) {\Pr}_{\pi}(s^\prime \mid s)\right) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s^\prime, \theta) q_{\pi}(s^\prime, a) \\ &\doteq \sum_{s^\prime \in \mathcal{S}} \rho_{\pi}(s^\prime) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s^\prime, \theta) q_{\pi}(s^\prime, a) \\ &= \sum_{s \in \mathcal{S}} \rho_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) \qquad (\text{将 } s^\prime \text{ 换为 } s) \\ &= \sum_{s \in \mathcal{S}} \rho_{\pi}(s) \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) \nabla_{\theta} \ln \pi(a \mid s, \theta) q_{\pi}(s, a) \\ &= \mathbb{E}\left[\nabla_{\theta} \ln \pi(A \mid S, \theta) q_{\pi}(S, A)\right], \end{align*}$$

其中 $S \sim \rho_{\pi}, A \sim \pi(S, \theta)$。证明完毕。

$\bar{v}_{\pi}$ 和 $\bar{r}_{\pi}$ 的梯度

根据引理 9.1 和引理 9.2，我们可以推导出 $\bar{v}_{\pi}$ 和 $\bar{r}_{\pi}$ 的梯度。与定理 9.2 不同，下面定理中目标函数的状态概率分布与策略 $\pi$ 相关。

定理 9.3 (有折扣的情况下 $\bar{v}_{\pi}$ 和 $\bar{r}_{\pi}$ 的梯度)。

在有折扣的情况下，即当 $\gamma \in (0,1)$ 时，$\bar{v}_{\pi}$ 和 $\bar{r}_{\pi}$ 的梯度为

$$\color{lightblue}{\begin{align*} \nabla_{\theta} \bar{r}_{\pi} = (1-\gamma) \nabla_{\theta} \bar{v}_{\pi} &\approx \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) \\ &= \mathbb{E}\left[\nabla_{\theta} \ln \pi(A \mid S, \theta) q_{\pi}(S, A)\right], \end{align*}}$$

其中 $S \sim d_{\pi}, A \sim \pi(S, \theta)$。当 $\gamma$ 接近 $1$ 时，上面的近似更加准确。

证明：

对 $\bar{v}_{\pi} = \sum_{s \in \mathcal{S}} d_{\pi}(s) v_{\pi}(s)$ 两边求梯度可得

$$\begin{align*} \nabla_{\theta} \bar{v}_{\pi} &= \nabla_{\theta} \sum_{s \in \mathcal{S}} d_{\pi}(s) v_{\pi}(s) \\ &= \sum_{s \in \mathcal{S}} \nabla_{\theta} d_{\pi}(s) v_{\pi}(s) + \sum_{s \in \mathcal{S}} d_{\pi}(s) \nabla_{\theta} v_{\pi}(s). \tag{9.20} \end{align*}$$

我们首先分析上式中的第二项 $\sum_{s \in \mathcal{S}} d_{\pi}(s) \nabla_{\theta} v_{\pi}(s)$。将式 (9.17) 中的 $\nabla_{\theta} v_{\pi}$ 代入第二项中可得

$$\begin{align*} \sum_{s \in \mathcal{S}} d_{\pi}(s) \nabla_{\theta} v_{\pi}(s) &= (d_{\pi}^{\mathrm{T}} \otimes I_m) \nabla_{\theta} v_{\pi} \\ &= (d_{\pi}^{\mathrm{T}} \otimes I_m) \left[(I_n - \gamma P_{\pi})^{-1} \otimes I_m\right] u \\ &= \left[d_{\pi}^{\mathrm{T}} (I_n - \gamma P_{\pi})^{-1}\right] \otimes I_m u. \tag{9.21} \end{align*}$$

注意到下式成立：

$$d_{\pi}^{\mathrm{T}} (I_n - \gamma P_{\pi})^{-1} = \frac{1}{1-\gamma} d_{\pi}^{\mathrm{T}}.$$

该式可以通过两边乘以 $(I_n - \gamma P_{\pi})$ 得到证明。将上式代入式 (9.21) 可得

$$\begin{align*} \sum_{s \in \mathcal{S}} d_{\pi}(s) \nabla_{\theta} v_{\pi}(s) &= \frac{1}{1-\gamma} d_{\pi}^{\mathrm{T}} \otimes I_m u \\ &= \frac{1}{1-\gamma} \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a). \end{align*}$$

虽然式 (9.20) 有两项，但是由于第二项包含一个缩放因子 $\frac{1}{1-\gamma}$，当 $\gamma \to 1$ 时，第二项起到主导作用，第一项可以忽略。此时，

$$\nabla_{\theta} \bar{v}_{\pi} \approx \frac{1}{1-\gamma} \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a).$$

上述推导过程中的近似要求第一项在 $\gamma \to 1$ 时不会趋向无穷大。另外，根据 $\bar{r}_{\pi} = (1-\gamma)\bar{v}_{\pi}$ 可知

$$\begin{align*} \nabla_{\theta} \bar{r}_{\pi} = (1-\gamma) \nabla_{\theta} \bar{v}_{\pi} &\approx \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) \\ &= \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) \nabla_{\theta} \ln \pi(a \mid s, \theta) q_{\pi}(s, a) \\ &= \mathbb{E}\left[\nabla_{\theta} \ln \pi(A \mid S, \theta) q_{\pi}(S, A)\right]. \end{align*}$$

证明完毕。

9.3.2 推导策略梯度：无折扣的情况

下面继续介绍目标函数梯度的推导，不过这次我们考虑无折扣的情况，即 $\gamma = 1$。到目前为止，本书只考虑了有折扣的情况，为什么现在突然开始考虑无折扣的情况呢？目标函数 $\bar{r}_{\pi}$ 的定义对有折扣和无折扣的情况都是成立的。在有折扣的情况下，$\bar{r}_{\pi}$ 的梯度是一种近似（定理 9.3）。在无折扣的情况下，我们将看到其梯度的推导更加严格且优美。

状态值和泊松方程

在无折扣的情况下，我们需要重新定义状态值和动作值。由于奖励的直接求和 $\mathbb{E}[R_{t+1} + R_{t+2} + R_{t+3} + \ldots \mid S_t = s]$ 可能发散，因此状态值和动作值需要以一种特殊的方式来定义：

$$\begin{align*} v_{\pi}(s) &\doteq \mathbb{E}[(R_{t+1} - \bar{r}_{\pi}) + (R_{t+2} - \bar{r}_{\pi}) + (R_{t+3} - \bar{r}_{\pi}) + \ldots \mid S_t = s], \\ q_{\pi}(s,a) &\doteq \mathbb{E}[(R_{t+1} - \bar{r}_{\pi}) + (R_{t+2} - \bar{r}_{\pi}) + (R_{t+3} - \bar{r}_{\pi}) + \ldots \mid S_t = s, A_t = a], \end{align*}$$

其中 $\bar{r}_{\pi}$ 是平均奖励。文献中对 $v_{\pi}(s)$ 有不同的称呼，如差分奖励（differential reward）或偏置（bias）。不难验证，上述状态值满足下式：

$$v_{\pi}(s) = \sum_{a} \pi(a \mid s, \theta) \left[\sum_{r} p(r \mid s, a)(r - \bar{r}_{\pi}) + \sum_{s^\prime} p(s^\prime \mid s, a) v_{\pi}(s^\prime)\right]. \tag{9.22}$$

此外，通过对比上式和 $v_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) q_{\pi}(s, a)$，可以得到动作值的表达式为，

$$q_{\pi}(s,a) = \sum_{r} p(r \mid s, a)(r - \bar{r}_{\pi}) + \sum_{s^\prime} p(s^\prime \mid s, a) v_{\pi}(s^\prime)$$

将式 (9.22) 写成矩阵-向量形式可得，

$$v_{\pi} = r_{\pi} - \bar{r}_{\pi} \mathbf{1}_n + P_{\pi} v_{\pi}, \tag{9.23}$$

其中 $\mathbf{1}_n = [1, \ldots, 1]^{\mathrm{T}} \in \mathbb{R}^n$。方程 (9.22) 和 (9.23) 与贝尔曼方程很类似，它们有一个特定的名称叫作 泊松方程（Poisson equation）。

如何从泊松方程中求解 $v_{\pi}$？答案将在下面的定理中给出。

定理 9.4 (泊松方程的解)。令

$$v_{\pi}^* \doteq (I_n - P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}})^{-1} r_{\pi}. \tag{9.24}$$

那么 $v_{\pi}^*$ 是式 (9.23) 中泊松方程的一个解，且泊松方程的任意解具有以下形式：

$$v_{\pi} = v_{\pi}^* + c \mathbf{1}_n,$$

其中 $c \in \mathbb{R}$。上述定理表明泊松方程的解可能是不唯一的。

证明：

证明分为三步。

• 第 1 步：证明 $v_{\pi}^*$ 是泊松方程的一个解。

  令

  $$A \doteq I_n - P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}}.$$

  那么 $v_{\pi}^* = A^{-1} r_{\pi}$。$A$ 的可逆性将在第 3 步中证明。将 $v_{\pi}^* = A^{-1} r_{\pi}$ 代入式 (9.23) 可得

  $$A^{-1} r_{\pi} = r_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}} r_{\pi} + P_{\pi} A^{-1} r_{\pi}.$$

  我们只需要证明上式是成立的，从而证明 $v_{\pi}^*$ 是泊松方程的一个解。具体来说，上式等价为 $(-A^{-1} + I_n - \mathbf{1}_n d_{\pi}^{\mathrm{T}} + P_{\pi} A^{-1}) r_{\pi} = 0$。该式可以重写为

  $$(-I_n + A - \mathbf{1}_n d_{\pi}^{\mathrm{T}} A + P_{\pi}) A^{-1} r_{\pi} = 0.$$

  上式是成立的，因为左侧括号内的项等于 $0$，即 $-I_n + A - \mathbf{1}_n d_{\pi}^{\mathrm{T}} A + P_{\pi} = -I_n + (I_n - P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}}) - \mathbf{1}_n d_{\pi}^{\mathrm{T}} (I_n - P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}}) + P_{\pi} = 0$。所以，$v_{\pi}^*$ 是泊松方程的一个解。

• 第 2 步：证明任意解的表达式。

  将 $\bar{r}_{\pi} = d_{\pi}^{\mathrm{T}} r_{\pi}$ 代入式 (9.23) 可得

  $$v_{\pi} = r_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}} r_{\pi} + P_{\pi} v_{\pi}. \tag{9.25}$$

  上式可以化为

  $$(I_n - P_{\pi}) v_{\pi} = (I_n - \mathbf{1}_n d_{\pi}^{\mathrm{T}}) r_{\pi}. \tag{9.26}$$

  注意 $I_n - P_{\pi}$ 是奇异的，这是因为对于任何策略 $\pi$ 都有 $(I_n - P_{\pi}) \mathbf{1}_n = 0$。因此，式 (9.26) 的解不是唯一的：如果 $v_{\pi}^*$ 是一个解，那么对于任意的 $x \in \mathrm{Null}(I_n - P_{\pi})$ 可知 $v_{\pi}^* + x$ 也是一个解。更进一步，如果 $P_{\pi}$ 不可约（irreducible），那么 $\mathrm{Null}(I_n - P_{\pi}) = \mathrm{span}\{\mathbf{1}_n\}$。此时，泊松方程的任意解都可以写成 $v_{\pi}^* + c \mathbf{1}_n$，其中 $c \in \mathbb{R}$ 是任意实数。

• 第 3 步：证明 $A = I_n - P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}}$ 是可逆的。

  前面用到了 $A$ 的可逆性，下面来证明该性质。

引理 9.3: 矩阵 $I_n - P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}}$ 是可逆的，其逆矩阵是

$$\left[I_n - (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})\right]^{-1} = \sum_{k=1}^{\infty} (P_{\pi}^k - \mathbf{1}_n d_{\pi}^{\mathrm{T}}) + I_n.$$

证明： 首先我们不加证明地给出一些基本知识。设 $\rho(M)$ 为矩阵 $M$ 的谱半径。如果 $\rho(M) < 1$，那么 $I - M$ 是可逆的。此外，$\rho(M) < 1$ 当且仅当 $\lim_{k \to \infty} M^k = 0$。

接下来我们展示 $\lim_{k \to \infty} (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})^k \to 0$，进而证明 $I_n - (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})$ 的可逆性。具体来说，注意到

$$(P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})^k = P_{\pi}^k - \mathbf{1}_n d_{\pi}^{\mathrm{T}}, \quad k \geqslant 1. \tag{9.27}$$

上式可以通过归纳法证明。例如，当 $k=1$ 时，很明显等式成立。当 $k=2$ 时，我们有

$$\begin{align*} (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})^2 &= (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})(P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}}) \\ &= P_{\pi}^2 - P_{\pi} \mathbf{1}_n d_{\pi}^{\mathrm{T}} - \mathbf{1}_n d_{\pi}^{\mathrm{T}} P_{\pi} + \mathbf{1}_n d_{\pi}^{\mathrm{T}} \mathbf{1}_n d_{\pi}^{\mathrm{T}} \\ &= P_{\pi}^2 - \mathbf{1}_n d_{\pi}^{\mathrm{T}}, \end{align*}$$

其中最后一个等号是由于 $P_{\pi} \mathbf{1}_n = \mathbf{1}_n, d_{\pi}^{\mathrm{T}} P_{\pi} = d_{\pi}^{\mathrm{T}}, d_{\pi}^{\mathrm{T}} \mathbf{1}_n = 1$。$k \geqslant 3$ 的情况可以类似地证明。

由于 $d_{\pi}$ 是平稳分布，故满足 $\lim_{k \to \infty} P_{\pi}^k = d_{\pi}^{\mathrm{T}} \mathbf{1}_n$（见方框 8.1）。对式 (9.27) 两边求极限可得

$$\lim_{k \to \infty} (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})^k = \lim_{k \to \infty} P_{\pi}^k - d_{\pi}^{\mathrm{T}} \mathbf{1}_n = 0.$$

因此有 $\rho(P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}}) < 1$，进而有 $I_n - (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})$ 是可逆的，且其逆矩阵是

$$\begin{align*} (I_n - (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}}))^{-1} &= \sum_{k=0}^{\infty} (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})^k = I_n + \sum_{k=1}^{\infty} (P_{\pi} - \mathbf{1}_n d_{\pi}^{\mathrm{T}})^k \\ &= I_n + \sum_{k=1}^{\infty} (P_{\pi}^k - \mathbf{1}_n d_{\pi}^{\mathrm{T}}) \\ &= \sum_{k=0}^{\infty} (P_{\pi}^k - \mathbf{1}_n d_{\pi}^{\mathrm{T}}) + \mathbf{1}_n d_{\pi}^{\mathrm{T}}. \end{align*}$$

证明完毕。 $\square$

梯度的推导

虽然定理 9.4 表明在无折扣的情况下 $v_{\pi}$ 的值不是唯一的，但是 $\bar{r}_{\pi}$ 的值是唯一的。具体来说，将 $v_{\pi} = v_{\pi}^* + c \mathbf{1}_n$ 代入泊松方程可得

$$\begin{align*} \bar{r}_{\pi} \mathbf{1}_n &= r_{\pi} + (P_{\pi} - I_n) v_{\pi} \\ &= r_{\pi} + (P_{\pi} - I_n)(v_{\pi}^* + c \mathbf{1}_n) \\ &= r_{\pi} + (P_{\pi} - I_n) v_{\pi}^*. \end{align*}$$

注意其中 $c$ 被抵消了，因此 $\bar{r}_{\pi}$ 的值是唯一的，所以我们可以在无折扣的情况下计算 $\bar{r}_{\pi}$ 的梯度。

定理 9.5 (无折扣情况下 $\bar{r}_{\pi}$ 的梯度)。在无折扣的情况下，平均奖励 $\bar{r}_{\pi}$ 的梯度是

$$\begin{align*} \nabla_{\theta} \bar{r}_{\pi} &= \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) \\ &= \mathbb{E}\left[\nabla_{\theta} \ln \pi(A \mid S, \theta) q_{\pi}(S, A)\right], \tag{9.28} \end{align*}$$

其中 $S \sim d_{\pi}, A \sim \pi(S, \theta)$。

与前面有折扣的情况下的结果相比（定理 9.3），$\bar{r}_{\pi}$ 在无折扣的情况下的梯度在数学上更为优美，这是因为式 (9.28) 是严格成立的。

证明：

首先，对 $v_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) q_{\pi}(s, a)$ 两边求梯度可得

$$\begin{align*} \nabla_{\theta} v_{\pi}(s) &= \nabla_{\theta} \left[\sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) q_{\pi}(s, a)\right] \\ &= \sum_{a \in \mathcal{A}} \left[\nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) + \pi(a \mid s, \theta) \nabla_{\theta} q_{\pi}(s, a)\right], \tag{9.29} \end{align*}$$

其中 $q_{\pi}(s, a)$ 是动作值，满足

$$\begin{align*} q_{\pi}(s, a) &= \sum_{r} p(r \mid s, a)(r - \bar{r}_{\pi}) + \sum_{s^\prime} p(s^\prime \mid s, a) v_{\pi}(s^\prime) \\ &= r(s, a) - \bar{r}_{\pi} + \sum_{s^\prime} p(s^\prime \mid s, a) v_{\pi}(s^\prime). \end{align*}$$

对上式两边求导，由于 $r(s, a) = \sum_{r} r p(r \mid s, a)$ 不依赖于 $\theta$，可得

$$\nabla_{\theta} q_{\pi}(s, a) = 0 - \nabla_{\theta} \bar{r}_{\pi} + \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime).$$

将上式代入式 (9.29) 可得

$$\begin{align*} \nabla_{\theta} v_{\pi}(s) &= \sum_{a \in \mathcal{A}} \left[\nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) + \pi(a \mid s, \theta) \left(-\nabla_{\theta} \bar{r}_{\pi} + \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime)\right)\right] \\ &= \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a) - \nabla_{\theta} \bar{r}_{\pi} + \sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime). \end{align*} \tag{9.30}$$

设

$$u(s) \doteq \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a).$$

由于 $\sum_{a \in \mathcal{A}} \pi(a \mid s, \theta) \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s, a) \nabla_{\theta} v_{\pi}(s^\prime) = \sum_{s^\prime \in \mathcal{S}} p(s^\prime \mid s) \nabla_{\theta} v_{\pi}(s^\prime)$，方程 (9.30) 可以写成矩阵-向量形式：

$$\underbrace{\begin{bmatrix} \vdots \\ \nabla_{\theta} v_{\pi}(s) \\ \vdots \end{bmatrix}}_{\nabla_{\theta} v_{\pi} \in \mathbb{R}^{mn}} = \underbrace{\begin{bmatrix} \vdots \\ u(s) \\ \vdots \end{bmatrix}}_{u \in \mathbb{R}^{mn}} - \mathbf{1}_n \otimes \nabla_{\theta} \bar{r}_{\pi} + (P_{\pi} \otimes I_m) \underbrace{\begin{bmatrix} \vdots \\ \nabla_{\theta} v_{\pi}(s^\prime) \\ \vdots \end{bmatrix}}_{\nabla_{\theta} v_{\pi} \in \mathbb{R}^{mn}},$$

其中 $n = |\mathcal{S}|$，$m$ 是向量 $\theta$ 的维数，$\otimes$ 是克罗内克积。上述方程可以简洁地写为

$$\nabla_{\theta} v_{\pi} = u - \mathbf{1}_n \otimes \nabla_{\theta} \bar{r}_{\pi} + (P_{\pi} \otimes I_m) \nabla_{\theta} v_{\pi},$$

进而可得

$$\mathbf{1}_n \otimes \nabla_{\theta} \bar{r}_{\pi} = u + (P_{\pi} \otimes I_m) \nabla_{\theta} v_{\pi} - \nabla_{\theta} v_{\pi}.$$

在上式两边同时乘以 $d_{\pi}^{\mathrm{T}} \otimes I_m$ 可得

$$\begin{align*} (d_{\pi}^{\mathrm{T}} \mathbf{1}_n) \otimes \nabla_{\theta} \bar{r}_{\pi} &= d_{\pi}^{\mathrm{T}} \otimes I_m u + (d_{\pi}^{\mathrm{T}} P_{\pi}) \otimes I_m \nabla_{\theta} v_{\pi} - d_{\pi}^{\mathrm{T}} \otimes I_m \nabla_{\theta} v_{\pi} \\ &= d_{\pi}^{\mathrm{T}} \otimes I_m u. \end{align*}$$

由于 $d_{\pi}^{\mathrm{T}} \mathbf{1}_n = 1$，由上式可得

$$\begin{align*} \nabla_{\theta} \bar{r}_{\pi} &= d_{\pi}^{\mathrm{T}} \otimes I_m u = \sum_{s \in \mathcal{S}} d_{\pi}(s) u(s) \\ &= \sum_{s \in \mathcal{S}} d_{\pi}(s) \sum_{a \in \mathcal{A}} \nabla_{\theta} \pi(a \mid s, \theta) q_{\pi}(s, a). \end{align*}$$

证明完毕。

最后，由于 $v_{\pi}$ 不是唯一的，因此 $\bar{v}_{\pi}$ 也不是唯一的，所以我们这里不关注 $\bar{v}_{\pi}$ 的梯度。

---

基于梯度的 RL

Lec 47

梯度上升算法

Gradient Ascent

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

最大化 $J(\theta)$ 的梯度上升算法（Gradient-Ascent Algorithm）为

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

• 真实梯度可以被随机梯度替代：

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

• 此外，由于 $q_\pi$ 未知，它可以被近似：

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

有不同的方法来近似 $q_\pi(s_t,a_t)$：

• 在本讲中，采用基于蒙特卡洛的方法，这样可以得到 REINFORCE 算法
• 事实上，还可以采用 TD learning 等等方法，这会在下一节介绍。

补充说明

如何进行采样？

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

• 如何采样 $S$？
  • $S \sim d$，其中分布 $d$ 是在策略 $\pi$ 下的长期行为分布。
    • 在实际当中一般不这么做——因为能得到数据已经非常幸运，不会再为了去求 stationary distribution 而采很久数据。
• 如何采样 $A$？
  • $A \sim \pi(A|S,\theta)$ —— $a_t$ 应该按照 $\pi(\theta_t)$ 在状态 $s_t$ 处采样。
    • 注意到，这一步直接使用 $\pi(\theta_t)$ 进行采样，也就是说 $\pi(\theta_t)$ 既作为 target policy 又作为 behavior policy！因此，策略梯度方法是 on-policy 的。
    • 也可以改造为 off-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*}$$

因此，我们得到该算法的重要表达式：

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

它是一个用于最大化 $\pi(a_t|s_t,\theta)$ 的梯度上升算法，$\alpha \beta_t$ 可以视作是一个步长。

直观理解：当 $\alpha \beta_t$ 足够小时

• 如果 $\beta_t > 0$，选择 $(s_t, a_t)$ 的概率被增强：

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

  $\beta_t$ 越大，增强效果越强（也不能太大，要在合理范围内）
• 如果 $\beta_t < 0$，则 $\pi(a_t|s_t,\theta_{t+1}) < \pi(a_t|s_t,\theta_t)$。

上面结论的数学推导

当 $\theta_{t+1} - \theta_t$ 足够小时，我们有如下一阶 Taylor 展开，

$$\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*}$$

故有，

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

因此，左侧的正负完全取决于 $\beta_t$ 的正负！

系数 $\beta_t$ 可以很好地平衡探索（exploration）和利用（exploitation）。

• 首先，$\beta_t$ 与 $q_t(s_t,a_t)$ 成正比。
  • 如果 $q_t(s_t,a_t)$ 很大，则 $\beta_t$ 很大，则 $\pi(a_t|s_t)$ 变大（$\theta_t \to \theta_{t+1}$）
  • 因此，算法倾向于增强具有更大值的动作。
• 其次，$\beta_t$ 与 $\pi(a_t|s_t,\theta_t)$ 成反比。
  • 如果 $\pi(a_t|s_t,\theta_t)$ 很小，则 $\beta_t$ 很大，则 $\pi(a_t|s_t)$ 变大
  • 因此，算法倾向于探索概率较低的动作。

REINFORCE 算法

回顾：

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

将 $q_\pi(s_t,a_t)$ 替换为 $q_t(s_t,a_t)$ ，有

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

• 如果 $q_\pi(s_t,a_t)$ 通过蒙特卡洛估计来近似，该算法有一个特定的名字，REINFORCE。
• REINFORCE 是最早且最简单的策略梯度算法之一。
• 许多其他策略梯度算法，例如 Actor-Critic 方法（下一讲），都可以通过对 REINFORCE 的扩展得到。

伪代码

伪代码：基于蒙特卡洛的策略梯度（REINFORCE）

• 初始化：参数化函数 $\pi(a|s,\theta)$，折扣因子 $\gamma \in (0,1)$，学习率 $\alpha > 0$。
• 目标：搜索使 $J(\theta)$ 最大化的最优策略。
• 对于第 $k$ 次迭代，执行：
  • 选择初始状态 $s_0$，并按照策略 $\pi(\theta_k)$ 生成一个回合（episode）。假设该回合为 $\{s_0, a_0, r_1, \dots, s_{T-1}, a_{T-1}, r_T\}$。
  • 对于 $t = 0, 1, \dots, T-1$，执行：
    • 值更新： $q_t(s_t, a_t) = \sum_{k=t+1}^{T} \gamma^{k-t-1} r_k$
    • 策略更新： $\theta_{t+1} = \theta_t + \alpha \nabla_\theta \ln \pi(a_t|s_t,\theta_t) \, q_t(s_t,a_t)$
  • $\theta_k = \theta_T$

补充说明：因为 MC 是 off-line 的，所以要先走 $T$ 步之后，再一并生成数据。