策略梯度算法 (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\times3}$（彩色二维屏幕），输出 Logits 对应这个游戏中的所有动作 $M_{k\times1}$：

$$ 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$ 的期望 $\bar{R}_{\theta}$ 来评估机器的表现。

1.4 Problem

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

$$ \theta^{*}=\arg\underset{\theta}{\max}\bar{R}_{\theta} $$

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

2 策略梯度

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

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

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

$$ \bar{R}_{\theta}=\sum_{\tau}R(\tau)P(\tau\mid\theta) $$

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

$$ \begin{align} \nabla\bar{R}_{\theta}&=\sum_{\tau}R(\tau)\nabla P(\tau\mid\theta)\\ &=\sum_{\tau}R(\tau)P(\tau\mid\theta)\frac{\nabla P(\tau\mid\theta)}{P(\tau\mid\theta)}\\ &=\sum_{\tau}R(\tau)P(\tau\mid\theta)\nabla\log P(\tau\mid\theta) \end{align} $$

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

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

接着继续推导：

$$ \begin{align} \nabla\bar{R}_{\theta}&=\sum_{\tau}R(\tau)P(\tau\mid\theta)\nabla\log P(\tau\mid\theta)\\ &\approx\frac{1}{N}\sum_{i=1}^{N} R(\tau^i)\nabla\log P(\tau^i\mid\theta) \end{align} $$

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

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

$$ \bar{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{align} 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{align} $$

$$ \begin{align} \log P(\tau\mid\theta)&=\log\left[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)\right]\\ &=\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{align} $$

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

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

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

$$ \begin{align} \nabla\bar{R}_{\theta} &\approx\frac{1}{N}\sum_{i=1}^{N} R(\tau^i)\nabla\log P(\tau^i\mid\theta)\\ &=\frac{1}{N}\sum_{i=1}^{N} R(\tau^i)\sum_{j=1}^{T^{(i)}}\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)\nabla\log P(a_j^{(i)}\mid s_j^{(i)},\theta)\\ \end{align} $$

3 优化

3.1 添加偏置

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

$$ \begin{align} \nabla\bar{R}_{\theta} &\approx\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{T^{(i)}}(R(\tau^i)\boxed{-b})\nabla\log P(a_j^{(i)}\mid s_j^{(i)},\theta)\\ \end{align} $$

3.2 动态贡献

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

$$ \begin{align} \nabla\bar{R}_{\theta} &\approx\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{T^{(i)}}(\boxed{R(\tau^i)}-b)\nabla\log P(a_j^{(i)}\mid s_j^{(i)},\theta)\\ \end{align} $$

例如对于一个 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{align} \nabla\bar{R}_{\theta} &\approx\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{T^{(i)}}(\boxed{\sum_{k=j}^{T^{(i)}}r_k^{(i)}}-b)\nabla\log P(a_j^{(i)}\mid s_j^{(i)},\theta)\\ \end{align} $$

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

$$ \nabla\bar{R}_{\theta} \approx\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{T^{(i)}}(\boxed{\sum_{k=j}^{T^{(i)}}(\gamma^{k-j} r_k^{(i)})}-b)\nabla\log P(a_j^{(i)}\mid s_j^{(i)},\theta)\\ \text{其中}, \gamma<1 $$

3.3 优势函数

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

$$ \begin{align} \nabla\bar{R}_{\theta} &\approx\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{T^{(i)}}A_{\theta}(s_j,a_j)\nabla\log P(a_j^{(i)}\mid s_j^{(i)},\theta)\\ \end{align} $$

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

4 Off-Policy 策略梯度

4.1 On/Off-Policy 的对比

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

$$ J(\theta)=\sum_{\tau\sim\pi_{\theta}}R(\tau)P(\tau\mid\theta)\\ \theta^{*}=\arg\underset{\theta}{\max}J(\theta) $$

需要注意到的是，我们的 $\tau$ 是从 $\pi_{\theta}$ 中采样得来的，而进行一次梯度更新后 $\theta$ 进行了变化，那么采样得到的 $\tau$ 就不能继续使用了，得再从新的 $\pi_{\theta'}$ 中重写采样。这种策略更新方式就叫做 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{align} \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}\left[f(x)\frac{p(x)}{q(x)}\right] \end{align} $$

4.3 结合起来

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

$$ \begin{align} \nabla\bar{R}_{\theta}&=\mathbb{E}_{(s_t,a_t)\sim\pi_\theta}A_{\theta}(s_t,a_t)\nabla\log P_{\theta}(a_t^{(n)}\mid s_t^{(n)})\\ &=\mathbb{E}_{(s_t,a_t)\sim\pi_{\theta'}}\frac{P_{\theta}(s_t,a_t)}{P_{\theta'}(s_t,a_t)}A_{\theta'}(s_t,a_t)\nabla\log P_{\theta}(a_t^{(n)}\mid s_t^{(n)})\\ &=\mathbb{E}_{(s_t,a_t)\sim\pi_{\theta'}}\frac{P_{\theta}(a_t\mid s_t)}{P_{\theta'}(a_t\mid s_t)}\frac{P_{\theta}(s_t)}{P_{\theta'}(s_t)}A_{\theta'}(s_t,a_t)\nabla\log P_{\theta}(a_t^{(n)}\mid s_t^{(n)})\\ &\approx\mathbb{E}_{(s_t,a_t)\sim\pi_{\theta'}}\frac{P_{\theta}(a_t\mid s_t)}{P_{\theta'}(a_t\mid s_t)}\cancel{\frac{P_{\theta}(s_t)}{P_{\theta'}(s_t)}}A_{\theta'}(s_t,a_t)\nabla\log P_{\theta}(a_t^{(n)}\mid s_t^{(n)}) \end{align} $$

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