策略梯度算法 (Policy Gradient)：强化学习中的一种策略优化方法，它直接根据奖励值对策略参数进行梯度上升，从而最大化奖励的期望。

1 问题定义

首先精简表述一下强化学习的流程。

Actor(演员) 对 Environment(环境) 进行 Observation(观察)，根据得到的 Observation 确定下一步的 Action，Action 作用于 Environment 后反馈给 Actor 以 Reward(奖励)。

强化学习的目标就是通过优化从 Observation 到 Action 的策略（实际就是 Actor），从而最大化一整轮动作中得到的 Reward 值。

1.1 Actor

Actor 通过 Observation 得到 Action，因此可以理解为一个函数，记为：

$$\mathrm{Action}=\pi (\mathrm{Observation})$$

这个函数的具体实现可以是多样的，可以是简单的神经网络，或者是更复杂的结构。

例如用参数为 $\theta$ 的神经网络作为这个函数，目标是学习玩某款游戏，那么这个 Actor 的 Observation 输入应当是一个三维张量 $N_{n\times m\times 3}$（彩色二维屏幕），输出 Logits 对应这个游戏中的所有动作 $M_{k\times 1}$：

$$M={\pi }_{\theta }(N)$$

得到 Logits 后，有多种方法确定最终的 Action 取值。最简单的就是直接取最大 Logit 值作为 Action，这种便是固定的选择方式。更好的一种方式是将 Logits 通过 Softmax 后得到概率分布，根据概率来随机选取每个 Action，这种随机的选择方式是更好的。

1.2 Episode

让上述例子的 Actor ${\pi }_{\theta }(\cdot )$ 来游玩一轮游戏，从开始到结束它经历的过程叫做 Episode，一个 Episode 的停止条件不是固定的。

例如对于有生命值的游戏来说，当角色死亡便是 Episode 的停止，对于竞技比赛来说，比赛结束便是 Episode 的结束。

• 初始状态 $s_1$
• 机器采取动作 $a_1$
• 机器获得奖励 $r_1$
• 进入状态 $s_2$
• 机器采取动作 $a_2$
• 机器获得奖励 $r_2$
• $\cdots$
• 进入状态 $s_T$
• 机器采取动作 $a_T$
• 机器获得奖励 $r_T$

这一个 Episode 就可以记为 $\tau =\{s_1,a_1,r_1,s_2,a_2,r_2,\dots ,s_T,a_T,r_T\}$.

1.3 Reward

经过一个 Episode，该 Actor 得到的奖励便是：

$$R_{\theta }=\sum _{t=1}^T{r}_t$$

容易理解的是，$R_{\theta }$ 越大代表这一轮机器的表现更好。但需要注意的是，由于使用的是随机选取的方法来确定 Action，对于同一个 $s_t$，机器是可能采取不同的 Action 的。因此实际上，我们应该用 $R_{\theta }$ 的期望 ${\overline{R}}_{\theta }$ 来评估机器的表现。

1.4 Problem

经过上面的铺垫，强化学习的问题定义便是：

$${\theta }^{\ast }=\arg \underset{\theta }{max}{\overline{R}}_{\theta }$$

即找到一个 ${\theta }^{\ast }$ 使 $R_{\theta }$ 的期望最大。

2 策略梯度

策略梯度算法和神经网络中的反向传播算法非常相似，它们的思路都是直接用 Loss/Reward 对每个参数做微分，得到梯度值来进行更新。

$$\begin{array}{rl}\theta & =[w_1,w_2,\dots ,b_1,b_2,\dots {]}^{\mathrm{T}}\\ \mathrm{\nabla }{\overline{R}}_{\theta }& =[\frac{\partial {\overline{R}}_{\theta }}{\partial w_1},\frac{\partial {\overline{R}}_{\theta }}{\partial w_2},\dots ,\frac{\partial {\overline{R}}_{\theta }}{\partial b_1},\frac{\partial {\overline{R}}_{\theta }}{\partial b_2},\dots {]}^{\mathrm{T}}\\ \Rightarrow {\theta }^{\prime }& =\theta +\eta \mathrm{\nabla }{\overline{R}}_{\theta }\end{array}$$

接下来便是推导公式了，首先确定 $R_{\theta }$ 的期望怎么表示。对于参数 $\theta$ 每一个 Episode $\tau$，它一定是存在一个概率的 $P(\tau \mid \theta )$，那么 $R_{\theta }$ 的期望可以表示为：

$${\overline{R}}_{\theta }=\sum _{\tau }R(\tau )P(\tau \mid \theta )$$

由于 $R(\tau )$ 和我们的参数无关，不需要可微，因此期望的梯度是：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& =\sum _{\tau }R(\tau )\mathrm{\nabla }P(\tau \mid \theta )\\ & =\sum _{\tau }R(\tau )P(\tau \mid \theta )\frac{\mathrm{\nabla }P(\tau \mid \theta )}{P(\tau \mid \theta )}\\ & =\sum _{\tau }R(\tau )P(\tau \mid \theta )\mathrm{\nabla }\log P(\tau \mid \theta )\end{array}$$

上面第二行到第三行的推导方式（常数省略）：

$$\frac{d\log f(x)}{dx}=\frac{1}{f(x)}\frac{df(x)}{dx}$$

接着继续推导：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& =\sum _{\tau }R(\tau )P(\tau \mid \theta )\mathrm{\nabla }\log P(\tau \mid \theta )\\ & \approx \frac{1}{N}\sum _{i=1}^{N}R({\tau }^i)\mathrm{\nabla }\log P({\tau }^i\mid \theta )\end{array}$$

其中的 ${\tau }^i$ 代表用 ${\pi }_{\theta }$ 玩 $N$ 次该游戏，得到 $N$ 个 episode $\{{\tau }^1,{\tau }^2,\dots ,{\tau }^N\}$.

上面近似变换的原理是蒙特卡洛的直接采样：

$${\overline{R}}_{\theta }=\sum _{\tau }R(\tau )P(\tau \mid \theta )\approx \frac{1}{N}\sum _{i=1}^{N}R({\tau }^i)$$

每一次游戏都能当作一次采样，$P(\tau \mid \theta )$ 大的 $\tau$ 更容易被采样到。因此对 $\tau$ 的 $N$ 次采样取平均，就可以近似原式。

把 $\log P(\tau \mid \theta )$ 展开来：

$$\begin{array}{rl}P(\tau \mid \theta )& =P(s_1)P(a_1\mid s_1,\theta )P(r_1,s_2\mid s_1,a_1)P(a_2\mid s_2,\theta )P(r_2,s_3\mid s_2,a_2)\dots \\ & =P(s_1)\prod _{i=1}^{T}P(a_i\mid s_i,\theta )P(r_i,s_{i+1}\mid s_i,a_i)\end{array}$$

$$\begin{array}{rl}\log P(\tau \mid \theta )& =\log [P(s_1)\prod _{i=1}^{T}P(a_i\mid s_i,\theta )P(r_i,s_{i+1}\mid s_i,a_i)]\\ & =\log P(s_1)+\sum _{i=1}^T\log P(a_i\mid s_i,\theta )+\sum _{i=1}^{T}P(r_i,s_{i+1}\mid s_i,a_i)\end{array}$$

$\mathrm{\nabla }\log P(\tau \mid \theta )$ 的计算只用考虑与参数有关的，因此：

$$\mathrm{\nabla }\log P(\tau \mid \theta )=\sum _{i=1}^T\mathrm{\nabla }\log P(a_i\mid s_i,\theta )$$

综上，我们最后的结果便是：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& \approx \frac{1}{N}\sum _{i=1}^{N}R({\tau }^i)\mathrm{\nabla }\log P({\tau }^i\mid \theta )\\ & =\frac{1}{N}\sum _{i=1}^{N}R({\tau }^i)\sum _{j=1}^{T^{(i)}}\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta )\\ & =\frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{T^{(i)}}R({\tau }^i)\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta )\end{array}$$

3 优化

3.1 添加偏置

由于我们只进行了 $N$ 次采样来近似，对于没有采样到的情况，在学习过程中可能就会使其概率越来越低。为了缓解这个情况，可以将奖励值减去一个偏置，让奖励值有正有负。

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& \approx \frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{T^{(i)}}(R({\tau }^i)\boxed{{\displaystyle -b}})\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta )\end{array}$$

3.2 动态贡献

根据上面的梯度公式，每一个 Action 都乘的是整个 Episode 的 Reward，这会导致一定的不公平性：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& \approx \frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{T^{(i)}}(\boxed{{\displaystyle R({\tau }^i)}}-b)\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta )\end{array}$$

例如对于一个 Episode $\tau =\{s_1,a_1,r_1,s_2,a_2,r_2,s_3,a_3,r_3\}$，它的 $r_1=8,r_2=-1,r_3=-2,R(\tau )=5$.

显然 $r_2,r_3$ 代表 $a_2,a_3$ 并不是好的 Action，但是由于 $R(\tau )=5>0$，它们仍然会被优化增加概率。

根据这个问题，可以使用动态贡献，每个 Action 只认领自己后面得到的 Reward. 例如对于上面的例子，$a_1$ 得到的 Reward 是 $5$，$a_2$ 是 $-3$，$a_3$ 是 $-2$，可以表示为：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& \approx \frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{T^{(i)}}(\boxed{{\displaystyle \sum _{k=j}^{T^{(i)}}{r}_k^{(i)}}}-b)\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta )\end{array}$$

再进一步，我们可以设定每一个 Action 认领的 Reward 随自己距离 Reward 的步数来减少。这点很好理解，毕竟在游戏里你做出的一步不可能对未来整个游戏都产生巨大影响，影响力肯定是越来越少的。

$$\begin{gathered} \mathrm{\nabla }{\overline{R}}_{\theta }\approx \frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{T^{(i)}}(\boxed{{\displaystyle \sum _{k=j}^{T^{(i)}}({\gamma }^{k-j}{r}_k^{(i)})}}-b)\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta ) \\ \text{其中},\gamma <1 \end{gathered}$$

3.3 优势函数

上面两小节实际上做的事情都是对奖励值进行优化，因此可以将奖励值直接抽象为一个函数来表示，相当于变成一个黑盒了。公式记作：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& \approx \frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{T^{(i)}}{A}_{\theta }(s_j,a_j)\mathrm{\nabla }\log P(a_j^{(i)}\mid s_j^{(i)},\theta )\end{array}$$

使用优势函数只是更换了一种表示方式，具体得看优势函数的内部实现是什么。

4 Off-Policy 策略梯度

4.1 On/Off-Policy 的对比

我们回看策略梯度算法的目标函数：

$$\begin{gathered} J(\theta )=\sum _{\tau \sim {\pi }_{\theta }}R(\tau )P(\tau \mid \theta ) \\ {\theta }^{\ast }=\arg \underset{\theta }{max}J(\theta ) \end{gathered}$$

需要注意到的是，我们的 $\tau$ 是从 ${\pi }_{\theta }$ 中采样得来的，而进行一次梯度更新后 $\theta$ 进行了变化，那么采样得到的 $\tau$ 就不能继续使用了，得再从新的 ${\pi }_{{\theta }^{\prime }}$ 中重写采样。这种策略更新方式就叫做 On-Policy，下面进行定义：

• On-Policy: 在学习和决策过程中始终使用相同的策略，即在进行策略更新时只考虑当前策略下的经验。例如，一个人在自己下棋来学习策略。
• Off-Policy: 可以利用从其他策略中得到的经验进行学习，即在进行策略更新时可以考虑非当前策略下的经验。例如，一个人看别人下棋来学习策略。

On-Policy 只能利用当前策略下的数据，因此数据利用效率相对较低，而 Off-Policy 能够利用所有数据来学习。下面将 Off-Policy 的思想带入策略梯度算法中。

4.2 重要性采样

在上文讲的 On-Policy 版本策略梯度中，使用的是蒙特卡洛直接采样。

$${\mathbb{E}}_{x\sim p}[f(x)]=\frac{1}{N}\sum _{i=1}^{N}f(x_i)$$

重要性采样是蒙特卡洛采样的另一种采样策略，能在无法采样原始分布时近似对原始分布的采样。

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

4.3 结合起来

我们用重要性采样来做策略梯度：

$$\begin{array}{rl}\mathrm{\nabla }{\overline{R}}_{\theta }& ={\mathbb{E}}_{(s_t,a_t)\sim {\pi }_{\theta }}{A}_{\theta }(s_t,a_t)\mathrm{\nabla }\log P_{\theta }(a_t^{(n)}\mid s_t^{(n)})\\ & ={\mathbb{E}}_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}\frac{P_{\theta }(s_t,a_t)}{P_{{\theta }^{\prime }}(s_t,a_t)}{A}_{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }\log P_{\theta }(a_t^{(n)}\mid s_t^{(n)})\\ & ={\mathbb{E}}_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}\frac{P_{\theta }(a_t\mid s_t)}{P_{{\theta }^{\prime }}(a_t\mid s_t)}\frac{P_{\theta }(s_t)}{P_{{\theta }^{\prime }}(s_t)}{A}_{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }\log P_{\theta }(a_t^{(n)}\mid s_t^{(n)})\\ & \approx {\mathbb{E}}_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}\frac{P_{\theta }(a_t\mid s_t)}{P_{{\theta }^{\prime }}(a_t\mid s_t)}\cancel{\frac{P_{\theta }(s_t)}{P_{{\theta }^{\prime }}(s_t)}}{A}_{{\theta }^{\prime }}(s_t,a_t)\mathrm{\nabla }\log P_{\theta }(a_t^{(n)}\mid s_t^{(n)})\end{array}$$

这里直接忽略 $\frac{P_{\theta }(s_t)}{P_{{\theta }^{\prime }}(s_t)}$ 的原因一是从经验来说这两个概率差别不会太大，二是计算这一项过于复杂，不好计算。