C8 策略梯度方法

策略表示：从表格到函数

值函数近似的思想不只可以用于表示 state/action values，还可以应用于策略表示。在本章之前，策略都是通过表格的形式呈现：

在本章中，策略可以被参数化的函数表示为 $\pi(a|s,\theta)$，其中 $\theta\in\mathbb{R}^{m}$ 是参数向量。函数也可以写为 $\pi_{\theta}(a|s)$，$\pi_{\theta}(a,s)$ 或 $\pi(a,s,\theta)$。当策略通过函数表示时，最优策略可以直接通过优化某些特定的 scalar metrics 来获取，这样的方法称为 policy gradient（策略梯度）。例如，设 $J(\theta)$ 是一个 scalar metric，最优策略可以通过梯度上升优化目标函数得到：

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

至此，强化学习的方法从 value-based 转为了 policy-based。

函数的结构既可以是输入状态 $s$ 和动作 $a$，然后输出该状态-动作概率 $\pi(a|s,\theta)$，如下图 (a) 所示；也可以是输入状态 $s$，输出所有动作的概率，如下图 (b) 所示。

下面讨论 policy-gradient 使用什么样的 scalar metrics，如何计算这些 metrics 的梯度，以及如何利用样本来近似这些梯度。

注意：策略函数一旦参数化，最优性就不再是“每个状态都最大化”，而是“整体指标最大化”。这也是这一章的关键词变化。

用于定义最优策略的指标

如果策略是函数，就需要把“好策略”压缩成一个标量来优化。通常有两种指标：平均状态价值 $\bar v_\pi$（基于 state values）和平均奖励 $\bar r_\pi$（基于即时奖励）。

指标 1：平均状态价值

定义

$$\bar v_\pi=\sum_{s\in\mathcal{S}}d(s)v_\pi(s)=\mathbb{E}_{S\sim d}[v_\pi(S)]$$

其中 $d(s)\ge 0$ 且 $\sum_s d(s)=1$，所以 $d$ 可以看作状态分布。

向量形式为

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

其中 $v _ {\pi} = [ \dots , v _ {\pi} (s), \dots ] ^ {T} \in \mathbb {R} ^ {| \mathcal {S} |}$，$d = [ \dots , d (s), \dots ] ^ {T} \in \mathbb {R} ^ {| \mathcal {S} |}$。

分布 $d$ 的选择

关于分布 $d$ 的选择，通常有两种：分布 $d$ 与策略 $\pi$ 无关和有关。

分布 $d$ 与策略 $\pi$ 无关

这是最简单的情形。在这种情况下，记 $d$ 为 $d_0$，$\bar{v}_{\pi}$ 为 $\bar{v}_{\pi}^{0}$，表示分布和策略 $\pi$ 无关（即相互独立）。
关于分布 $d_0$ 的具体情况，常见做法是采用均匀分布：

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

或者只关心某个起始状态 $s_0$（例如 agent 总是从 $s_0$ 出发）：

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

分布 $d$ 与策略 $\pi$ 有关

在这种情况下，通常记 $d$ 为 $d_\pi$，表示策略 $\pi$ 下的平稳分布，它满足

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

其中 $P_{\pi}$ 表示状态转移概率矩阵。使用 $d_{\pi}$ 作为 state values 的权值很直观：长期运行后，哪些状态经常出现，哪些状态就更重要。

等价写法

如果智能体按策略 $\pi(\theta)$ 采样得到的奖励为 $\{R_{t+1}\}_{t=0}^{\infty}$，则常见的目标函数可以写成

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

它实际上就是 $\bar v_\pi$。

证明等价：

$$\begin{align} \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} | S _ {0} = s \right] \\ &= \sum_ {s \in \mathcal {S}} d (s) v _ {\pi} (s) \\ &= \bar {v} _ {\pi}. \\ \end{align}$$

上述公式的第一个等式是全期望公式，第二个等式是 state value 的定义。

指标 2：平均奖励

平均奖励定义为

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

其中 $d_{\pi}$ 表示平稳分布，并且 $r_{\pi}(s)$ 表示状态 $s$ 下的即时奖励期望：

$$r_\pi(s)=\sum_{a\in\mathcal A}\pi(a\mid s,\theta)r(s,a) =\mathbb{E}_{A\sim\pi(\cdot\mid s,\theta)}[r(s,A)\mid s],$$

其中

$$r(s,a)=\mathbb{E}[R\mid s,a]=\sum_r r\,p(r\mid s,a).$$

$\bar{r}_{\pi}$ 的向量形式为

$$\bar{r}_{\pi}=d_{\pi}^Tr_{\pi}$$

其中 $r _ {\pi} = [ \dots , r _ {\pi} (s), \dots ] ^ {T} \in \mathbb {R} ^ {| \mathcal {S} |}$，$d _ {\pi} = [ \dots , d _ {\pi} (s), \dots ] ^ {T} \in \mathbb {R} ^ {| \mathcal {S} |}$。

等价写法

如果智能体按策略 $\pi(\theta)$ 采样得到的奖励为 $\{R_{t+1}\}_{t=0}^{\infty}$，则常见的目标函数可以写成

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

它实际上就是 $\bar{r}_{\pi}$。

证明等价：

1. 首先证明对于任意初始状态 $s_0\in\mathcal{S}$，都有

   $$\bar {r} _ {\pi} = \lim _ {n \rightarrow \infty} \frac {1}{n} \mathbb {E} \left[ \sum_ {t = 0} ^ {n - 1} R _ {t + 1} | S _ {0} = s _ {0} \right]$$

   注意到

   $$\begin{align} \lim _ {n \rightarrow \infty} \frac {1}{n} \mathbb {E} \left[ \sum_ {t = 0} ^ {n - 1} R _ {t + 1} \mid S _ {0} = s _ {0} \right] &= \lim _ {n \rightarrow \infty} \frac {1}{n} \sum_ {t = 0} ^ {n - 1} \mathbb {E} \left[ R _ {t + 1} \mid S _ {0} = s _ {0} \right] \\ &= \lim _ {t \rightarrow \infty} \mathbb {E} \left[ R _ {t + 1} \mid S _ {0} = s _ {0} \right], \\ \end{align}$$

   最后一个等式是由于 Cesaro mean（切萨罗均值，也叫切萨罗求和），即若 $\{a_{k}\}_{k=1}^{\infty}$ 是一个收敛序列，它的极限 $\lim_{k\to\infty}a_k$ 存在，则 $\{1/n\sum_{k=1}^na_k\}_{n=1}^{\infty}$ 也是一个收敛序列，且极限为 $\lim _ {n \rightarrow \infty} 1 / n \sum_ {k = 1} ^ {n} a _ {k} = \lim _ {k \rightarrow \infty} a _ {k}$。

   根据全期望公式，有

   $$\begin{align} \mathbb {E} \left[ R _ {t + 1} \mid S _ {0} = s _ {0} \right] &= \sum_ {s \in \mathcal {S}} \mathbb {E} \left[ R _ {t + 1} \mid S _ {t} = s, S _ {0} = s _ {0} \right] p ^ {(t)} \left(s \mid s _ {0}\right) \\ &= \sum_ {s \in \mathcal {S}} \mathbb {E} \left[ R _ {t + 1} \mid S _ {t} = s \right] p ^ {(t)} \left(s \mid s _ {0}\right) \\ &= \sum_ {s \in \mathcal {S}} r _ {\pi} (s) p ^ {(t)} \left(s \mid s _ {0}\right), \\ \end{align}$$

   其中 $p^{(t)}(s\mid s_0)$ 表示从状态 $s_0$ 经过 $t$ 步到达状态 $s$ 的概率。根据平稳分布的定义，有

   $$\lim _ {t \rightarrow \infty} p ^ {(t)} \left(s \mid s _ {0}\right) = d _ {\pi} (s)$$

   因此有

   $$\lim _ {t \rightarrow \infty} \mathbb {E} \left[ R _ {t + 1} \mid S _ {0} = s _ {0} \right] = \lim _ {t \rightarrow \infty} \sum r _ {\pi} (s) p ^ {(t)} \left(s \mid s _ {0}\right) = \sum r _ {\pi} (s) d _ {\pi} (s) = \bar {r} _ {\pi}$$

   从而得证。

2. 根据全期望公式，有

   $$\begin{align} \lim _ {n \rightarrow \infty} \frac {1}{n} \mathbb {E} \left[ \sum_ {t = 0} ^ {n - 1} R _ {t + 1} \right] = \lim _ {n \rightarrow \infty} \frac {1}{n} \sum_ {s \in \mathcal {S}} d (s) \mathbb {E} \left[ \sum_ {t = 0} ^ {n - 1} R _ {t + 1} | S _ {0} = s \right] \\ = \sum_ {s \in \mathcal {S}} d (s) \lim _ {n \rightarrow \infty} \frac {1}{n} \mathbb {E} \left[ \sum_ {t = 0} ^ {n - 1} R _ {t + 1} | S _ {0} = s \right] \\ \end{align}$$

   将第 1 步证明的结论带入，得到

   $$\lim _ {n \rightarrow \infty} \frac {1}{n} \mathbb {E} \left[ \sum_ {t = 0} ^ {n - 1} R _ {t + 1} \right] = \sum_ {s \in \mathcal {S}} d (s) \bar {r} _ {\pi} = \bar {r} _ {\pi}.$$

综上，命题得证。

两个指标间的关系

上表是关于两个指标的总结。由于两个指标为 state values 或即时奖励的加权均值，而不同的策略 $\pi_{\theta}$ 产生不同的 state values 和即时奖励，因此可以通过优化指标的值来获得最优的策略（最优的参数 $\theta$）。

此外，在折扣情形 $\gamma\in(0,1)$ 下，这两个指标存在关系

$$\bar r_\pi=(1-\gamma)\bar v_\pi.$$

所以这两个目标是等价的，可以同时最大化。

等式证明：

根据 $\bar{v}_{\pi}$ 和 $\bar{r}_{\pi}$ 的向量形式 $\bar{v}_{\pi}=d_{\pi}^Tv_{\pi}$ 和 $\bar{r}_{\pi}=d_{\pi}^Tr_{\pi}$，以及贝尔曼公式 $v_{\pi}=r_{\pi}+\gamma P_{\pi}v_{\pi}$，将贝尔曼公式两边同时乘 $d_{\pi}$ 得到

$$\bar {v} _ {\pi} = \bar {r} _ {\pi} + \gamma d _ {\pi} ^ {T} P _ {\pi} v _ {\pi} = \bar {r} _ {\pi} + \gamma d _ {\pi} ^ {T} v _ {\pi} = \bar {r} _ {\pi} + \gamma \bar {v} _ {\pi}$$

从而等式 $\bar r_\pi=(1-\gamma)\bar v_\pi$ 成立。

指标的梯度

为了利用上一部分的两个指标去寻找最优策略，需要获取这些指标的梯度。

定理 1：Policy Gradient Theorem

设 $J(\theta)$ 是上一节中的某个标量指标，则有

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

其中 $\eta$ 表示状态分布，不同场景下会不同。上述公式可以写成期望形式：

$$\nabla_\theta J(\theta) =\mathbb{E}_{S\sim\eta,\ A\sim\pi(\cdot\mid S,\theta)} \left[\nabla_\theta\ln\pi(A\mid S,\theta)\,q_\pi(S,A)\right].$$

上述定理是把多个具体情形统一成了一个表达，具体情形包括采用不同的指标、折扣类型和非折扣类型。在具体的情形中上述公式的 $\eta(s)$ 会被替换为具体的分布，并且等号也可能变为近似，后面会一一呈现。

重点关注期望形式的公式，因为它非常适合做 SGD，后面会介绍。

期望形式推导

下面展示如何根据 $\nabla_{\theta}J(\theta)$ 的求和形式得到期望形式。

首先，根据期望的定义，有

$$\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} _ {S \sim \eta} \left[ \sum_ {a \in \mathcal {A}} \nabla_ {\theta} \pi (a | S, \theta) q _ {\pi} (S, a) \right]. \\ \end{align}$$

根据求导结果

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

得到

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

带入 $\nabla_{\theta}J(\theta)$，得到

$$\begin{align} \nabla_ {\theta} J (\theta) &= \mathbb {E} \left[ \sum_ {a \in \mathcal {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 (S, \theta)} \left[ \nabla_ {\theta} \ln \pi (A | S, \theta) q _ {\pi} (S, A) \right]. \\ \end{align}$$

这样原本的求和形式就能写成期望形式，进而用样本来估计。

注意上述的推导过程中，要求策略 $\pi(a\mid s,\theta)$ 都是正的，这样 $\ln\pi$ 才有意义。实际中，常用 softmax 来保证这一点，常见的做法是：

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

其中 $h(s,a,\theta)$ 表示动作偏好。如果用神经网络实现，通常把状态 $s$ 输入网络，最后一层接 softmax，输出所有动作的概率。此外，这种策略天然是随机的，所以它自带探索性。

折扣情形

先定义折扣情形下的 state value 和 action value：

$$v_\pi(s)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots\mid S_t=s],$$

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

并且有

$$v_\pi(s)=\sum_a\pi(a\mid s,\theta)q_\pi(s,a).$$

引理 1：$v_\pi(s)$ 的梯度

在折扣情形下，对任意状态 $s$ 都有

$$\nabla_\theta v_\pi(s) =\sum_{s'}\Pr_\pi(s'\mid s)\sum_a\nabla_\theta\pi(a\mid s',\theta)q_\pi(s',a),$$

其中

$$\Pr_\pi(s'\mid s)=\sum_{k=0}^{\infty}\gamma^k[P_\pi^k]_{ss'} =[(I-\gamma P_\pi)^{-1}]_{ss'}$$

表示从 $s$ 到 $s'$ 的折扣总转移概率。

这里的“折扣总转移概率”可以理解成：
走任意步数到达 $s'$ 的所有概率贡献，按 $\gamma^k$ 做了折扣加权。

定理 2：$\bar v_{\pi_0}$ 的梯度

若 $d_0$ 与策略无关，则

$$\nabla_\theta\bar v_{\pi_0} =\mathbb{E}_{S\sim\xi_\pi,\ A\sim\pi(\cdot\mid S,\theta)} \left[\nabla_\theta\ln\pi(A\mid S,\theta)q_\pi(S,A)\right],$$

其中

$$\xi_\pi(s)=\sum_{s_0}d_0(s_0)\Pr_\pi(s\mid s_0).$$

定理 3：折扣情形下 $\bar r_\pi$ 和 $\bar v_\pi$ 的梯度

在折扣情形下，

$$\nabla_\theta\bar r_\pi=(1-\gamma)\nabla_\theta\bar v_\pi \approx \sum_s d_\pi(s)\sum_a\nabla_\theta\pi(a\mid s,\theta)q_\pi(s,a),$$

也可以写成

$$\nabla_\theta\bar r_\pi \approx \mathbb{E}_{S\sim d_\pi,\ A\sim\pi(\cdot\mid S,\theta)} \left[\nabla_\theta\ln\pi(A\mid S,\theta)q_\pi(S,A)\right].$$

当 $\gamma\to1$ 时，这个近似会更准。

---

无折扣情形

在无折扣情形 $\gamma=1$ 下，直接累加奖励往往会发散，所以这里要重新定义 value。

差分定义

$$v_\pi(s)=\mathbb{E}[(R_{t+1}-\bar r_\pi)+(R_{t+2}-\bar r_\pi)+(R_{t+3}-\bar r_\pi)+\cdots\mid S_t=s],$$

$$q_\pi(s,a)=\mathbb{E}[(R_{t+1}-\bar r_\pi)+(R_{t+2}-\bar r_\pi)+(R_{t+3}-\bar r_\pi)+\cdots\mid S_t=s,A_t=a].$$

这类 $v_\pi(s)$ 也常被称为 differential reward 或 bias。

Poisson 方程

无折扣情形下满足

$$v_\pi=r_\pi-\bar r_\pi 1_n + P_\pi v_\pi,$$

其中 $1_n=[1,\dots,1]^T$。

这个方程和 Bellman 方程很像，所以也叫 Poisson equation。

定理 4：Poisson 方程的解

令

$$v_\pi^\star=(I_n-P_\pi+1_nd_\pi^T)^{-1}r_\pi,$$

则 $v_\pi^\star$ 是 Poisson 方程的一个解。并且任意解都可以写成

$$v_\pi=v_\pi^\star+c1_n,\quad c\in\mathbb{R}.$$

也就是说，解不唯一，只差一个常数。

直观理解：
Poisson 方程里 $I-P_\pi$ 本身是奇异的，因为常数向量 $1_n$ 会落在它的零空间里。
加上 $1_nd_\pi^T$ 以后，矩阵才可逆。

定理 5：无折扣情形下平均奖励的梯度

在无折扣情形下，

$$\nabla_\theta\bar r_\pi =\sum_s d_\pi(s)\sum_a\nabla_\theta\pi(a\mid s,\theta)q_\pi(s,a) =\mathbb{E}_{S\sim d_\pi,\ A\sim\pi(\cdot\mid S,\theta)} \left[\nabla_\theta\ln\pi(A\mid S,\theta)q_\pi(S,A)\right].$$

这是一个严格成立的结果，而且状态分布就是平稳分布 $d_\pi$。

Monte Carlo policy gradient（REINFORCE）

有了梯度表达式，下一步就是用它来做优化。

REINFORCE

由定理 1，对 $J(\theta)$ 使用梯度上升的公式为

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

由于真梯度通常不可得，就用随机梯度上升：

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

其中 $q_t(s_t,a_t)$ 是对 $q_{\pi}(s_t,a_t)$ 的估计。如果 $q_t(s_t,a_t)$ 用 Monte Carlo 回报估计，则这个算法就叫 REINFORCE 或者蒙特卡洛策略梯度，是最早也是最简单的一种 policy gradient 方法。

性质分析

因为

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

所以 REINFORCE 公式可以写成

$$\theta_ {t + 1} = \theta_ {t} + \alpha \underbrace {\left(\frac {q _ {t} \left(s _ {t} , a _ {t}\right)}{\pi \left(a _ {t} \mid s _ {t} , \theta_ {t}\right)}\right)} _ {\beta_ {t}} \nabla_ {\theta} \pi \left(a _ {t} \mid s _ {t}, \theta_ {t}\right)$$

令 $\beta_{t}=\frac {q _ {t} \left(s _ {t} , a _ {t}\right)}{\pi \left(a _ {t} \mid s _ {t} , \theta_ {t}\right)}$，可以进一步得到

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

强化

若 $\beta_t>0$，相当于在 $(s_t,a_t)$ 处对 $\pi_{\theta}$ 做梯度上升，从而 $(s_t,a_t)$ 被选择的概率会增大；反之若 $\beta_t<0$，相当于在 $(s_t,a_t)$ 处对 $\pi_{\theta}$ 做梯度下降，从而 $(s_t,a_t)$ 被选择的概率会就越小。而 $\beta_t$ 的正负性与状态 $s_t$ 下某个 action value $q_t(s_t,a_t)$ 相同，这种“表现好就增加概率，表现差就减少概率”的机制，正是算法名称 REINFORCE（强化）的由来。

探索与利用的权衡

当 $q_t(s_t,a_t)>0$ 时，$\beta_t$ 与 $q_t(s_t,a_t)$ 成正比，与 $\pi(a_t\mid s_t,\theta_t)$ 成反比。因此，当 $q_t(s_t,a_t)$ 越大时，它增加的幅度就越大，倾向于 exploitation（利用）；而 $\pi(a_t\mid s_t,\theta_t)$ 越小时，它增加的幅度也越大，说明这个动作原本不常被选中，更新后它可能被更多尝试，倾向于exploration（探索）。

伪代码

关于采样

理论上，梯度 $\mathbb {E} _ {S \sim \eta , A \sim \pi} \left[ \nabla_ {\theta} \ln \pi \left(A | S, \theta_ {t}\right) q _ {\pi} (S, A) \right]$ 里的状态 $S$ 应该服从相应的状态分布 $\eta$，动作 $A$ 应该服从当前采样策略 $\pi(\cdot\mid S,\theta)$。因此 REINFORCE 方法天然是 on-policy 的。