5 策略梯度算法

Note

《动手学强化学习》一书对于该算法的数学理论讲得不是很清楚，不好理解。本节主要参考《Easy RL：强化学习教程》。

Q-learning 以及 DQN 算法等都是基于价值（value-based）的算法。

先与环境交互获得大量数据，用这些数据拟合一个价值函数，再根据此价值函数导出一个策略（一般是贪心的策略）。

还有一支经典算法，基于策略（policy-based）的算法，直接显式学习一个策略。

策略梯度

首先我们建模策略函数：输入某个状态，输出动作的概率分布。在强化学习里一般用神经网络来建模。

我们假设目标策略 \(\pi_{\theta}\) 是一个随机性策略，并且处处可微。 \(\theta\) 是策略函数中的参数。我们强化学习的目标是寻找一个最优策略。

如何评价策略

现在我们遇到的问题是如何评价一个策略 \(\pi_{\theta}\) 的优秀程度。思路其实很简单，就是用期望回报。在这里我们还需要考虑第一个初始状态的随机性。

我们用形式化的语言加以阐述。首先，考虑环境初始状态 \(s_0\) ，智能体遵循策略 \(\pi_\theta\) 选择了动作 \(a_0\) ，与环境交互后，获得奖励 \(r_0\) ，并且使环境状态改变为 \(s_1\) ，智能体又遵循策略 \(\pi_\theta\) 选择了动作 \(a_1\) ，如此往复，直到环境终止。我们把这一整个采样过程所获得的数据称为一条轨迹，用 \(\tau\) 表示：

\[\tau = \{s_0,a_0,r_0,s_1,a_1,r_1,\cdots,s_{T-1},a_{T-1},r_{T-1},s_T,r_T\}\]

这条轨迹的总回报值为 \(R(\tau) = \sum_{t=0}^Tr_t\) . 那么，策略 \(\pi_\theta\) 的期望回报就是在参数 \(\theta\) 下采样到轨迹 \(\tau\) 的概率乘以该轨迹的总回报值，并对所有轨迹求和（或积分）：

\[\begin{aligned} \bar{R}_\theta &= \sum_{\tau}R(\tau)p(\tau|\theta) = \mathbb{E}_{\tau \sim p(\tau|\theta)}[R(\tau)]\\ &\approx \frac{1}{N}\sum_{n=1}^{N}R\left(\tau^{\{n\}}\right) \end{aligned}\]

上式中的 \(n\) 代表被采样轨迹的编号。

如何优化策略

现在我们有办法判断一个策略 \(\pi_\theta\) 有多好，方法就是大量采样数据计算其期望回报 \(\bar R_\theta\) . 那么接下来的问题是，我们怎么优化参数 \(\theta\) 使其变得更好？

一个比较明显的做法是梯度上升，即沿着回报值上升最快的方向更新参数 \(\theta\) ，形式化表示为：

\[\theta \leftarrow \theta + \eta \nabla_{\theta} \bar R_{\theta}\]

这里的 \(\eta\) 被称为学习率（Learning Rate）。

我们现在来看一下，怎么求期望回报相对于 \(\theta\) 的梯度。

\[\begin{aligned} \nabla_{\theta}\bar{R}_{\theta} &= \nabla_{\theta}\left(\sum_{\tau}R(\tau)p(\tau|\theta)\right)\\ &= \sum_{\tau}R(\tau)\nabla_{\theta}p(\tau|\theta)\\ \end{aligned}\]

接下来的问题是如何计算策略 \(\pi_\theta\) 在参数 \(\theta\) 下采样到轨迹 \(\tau\) 的概率 \(p(\tau|\theta)\) 。

理论上，如果我们有足够多的时间，我们可以采样足够多的轨迹 \(\tau_i\) ，统计每种轨迹的出现次数，直接计算该轨迹的出现概率 \(p(\tau_i|\theta)\) 。但实际上，想采样到两条完全一样的轨迹，几乎是不可能的。用此种方式，每条轨迹的 \(p(\tau_i|\theta)\) 几乎都等于 0 ，没有意义。我们需要其它的计算方式。

我们想到了马尔可夫决策过程（MDP）。基于此思路，概率 \(p(\tau|\theta)\) 可以如下计算：

\[\begin{aligned} p(\tau|\theta) &= p(s_0)\pi_\theta(a_0|s_0)p(s_1|s_0,a_0)\pi_\theta(a_1|s_1)p(s_2|s_1,a_1)\cdots\\ &= p(s_0)\prod_{t=0}^{T}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t) \end{aligned}\]

Note

\(\pi_\theta(a|s)\) 表示策略 \(\pi\) 在 \(\theta\) 参数下，在状态 \(s\) 选择动作 \(a\) 的概率。
初始状态 \(s_0\) 出现的概率 \(p(s_0)\) 以及状态转移概率 \(p(s'|s,a)\) 都与参数 \(\theta\) 无关，完全由环境决定。

我们这就避免了极大量的轨迹采样。因为不同的轨迹数据，其 \(p(s_0)\) 、\(\pi_\theta(a|s)\) 和 \(p(s'|s,a)\) 都是可以通用的。只需要一定数量的轨迹数据，我们就能计算出每条轨迹被采样到的概率。

这里 \(p(\tau|\theta)\) 是一个连乘的形式，很难求梯度。

数学上经常采用对数来处理连乘符号，使其变为求和符号，便于利用某些操作（比如求梯度）的线性性质。

\[\begin{aligned} \log p(\tau|\theta) &= \log \left[p(s_0)\prod_{t=0}^{T}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)\right]\\ &= \log p(s_0) + \sum_{t=0}^{T}\log \pi_\theta(a_t|s_t) + \sum_{t=0}^{T}\log p(s_{t+1}|s_t,a_t) \end{aligned}\]

那么现在的问题是，如何将 \(\nabla p(\tau|\theta)\) 和 \(\log p(\tau|\theta)\) 联系在一起？

Theorem

\[\begin{aligned}\nabla \log f(x) &= \dfrac{1}{f(x)}\nabla f(x)\\ \nabla f(x) &= f(x)\nabla \log f(x)\end{aligned}\]

根据以上补充式，我们有 \(\nabla p(\tau|\theta) = p(\tau|\theta) \nabla \log p(\tau|\theta)\) . 从而有

\[\begin{aligned} \nabla_{\theta}\bar{R}_{\theta} &= \sum_{\tau}R(\tau)\nabla_{\theta}p(\tau|\theta)\\ &= \sum_{\tau}R(\tau)p(\tau|\theta)\nabla_{\theta}\log p(\tau|\theta) \end{aligned}\]

我们注意到上式是一个期望的表达式：

\[\nabla_{\theta}\bar{R}_{\theta} = \mathbb{E}_{\tau \sim p(\tau|\theta)} \left[R(\tau)\nabla_\theta\log p(\tau|\theta)\right]\]

\[\begin{aligned} \nabla_{\theta}\bar{R}_{\theta} &= \sum_{\tau}R(\tau)p(\tau|\theta)\nabla_{\theta}\log p(\tau|\theta)\\ &= \mathbb{E}_{\tau \sim p(\tau|\theta)} \left[R(\tau)\nabla_\theta\log p(\tau|\theta)\right]\\ &\approx \frac{1}{N}\sum_{n=1}^{N}R\left(\tau^{\{n\}}\right)\nabla_\theta \log p\left(\tau^{\{n\}}|\theta\right) \end{aligned}\]

这里的 \(\tau^{\{n\}}\) 代表第 \(n\) 条轨迹。

其中，\(\nabla_{\theta} \log p(\tau|\theta)\) 可以如下计算：

\[\begin{aligned} \nabla_\theta\log p(\tau|\theta) &= \nabla_{\theta}\left\{\log \left[p(s_0)\prod_{t=0}^{T}\pi_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)\right]\right\}\\ &= \nabla_{\theta}\log p(s_0) + \nabla_{\theta}\left[\sum_{t=0}^{T}\log \pi_\theta(a_t|s_t)\right] + \nabla_{\theta}\left[\sum_{t=0}^{T}\log p(s_{t+1}|s_t,a_t)\right]\\ &= 0 + \sum_{t=0}^{T}\nabla_{\theta}\log \pi_{\theta}(a_t|s_t) + 0\\ &= \sum_{t=0}^{T}\nabla_{\theta}\log \pi_{\theta}(a_t|s_t) \end{aligned}\]

所以，期望回报相对于 \(\theta\) 的梯度是

\[\nabla_{\theta}\bar{R}_{\theta} = \frac{1}{N}\sum_{n=1}^{N}R\left(\tau^{\{n\}}\right) \sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\]

综上，策略提升的方式为：

\[\theta \leftarrow \theta + \frac{\eta}{N}\sum_{n=1}^{N}R\left(\tau^{\{n\}}\right) \sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\]

一些优化技巧

我们先来看看怎么理解这个策略提升方式

\[\theta \leftarrow \theta + \frac{\eta}{N}\sum_{n=1}^{N}R\left(\tau^{\{n\}}\right) \sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\]

\(\nabla_{\theta} \log \pi_{\theta}(a_t|s_t)\) 代表在状态 \(s_t\) 选动作 \(a_t\) 的概率提升最大的方向， \(R\left(\tau^{\{n\}}\right)\) 代表轨迹 \(n\) 中所有动作概率 \(\pi_{\theta}(a|s)\) 提升的权重。

具体而言，所谓策略提升，是在修改 \(\pi_{\theta}(a|s)\) . 考虑一条轨迹

\[\tau = \{s_0,a_0,r_0,s_1,a_1,r_1,\cdots,s_{T-1},a_{T-1},r_{T-1},s_T,r_T\}\]

我们用最后的总回报 \(R(\tau)\) 作为提升该轨迹内每个 \(\pi_{\theta}(a_t|s_t)\) 概率的步长，让 \(\theta\) 朝着每个 \(\pi_{\theta}(a_t|s_t)\) 提升的方向走 \(R(\tau)\) 距离。

添加基线 baseline

如果奖励 \(R(\tau)\) 总是正的，理想情况下，所有动作概率 \(\pi_{\theta}(a|s)\) 都会提升，只不过根据所在轨迹的总回报不同，有的动作概率提升得多，有的动作概率提升得少。提升之后，所有动作概率总和大于 1 。这时候我们再做归一化，就完成了一次策略提升。

但以上都是理想情况。如果我们采样的轨迹不够多，恰好遗漏了一个奖励很大的动作 \(a_m\) ，那么在概率提升时，其它动作概率都或多或少提升了，而该动作概率保持不变。归一化之后，该动作的概率反而下降了！

想解决这个问题也很简单，只要让奖励 \(R(\tau)\) 有正有负即可：

\[\theta \leftarrow \theta + \frac{\eta}{N}\sum_{n=1}^{N}\left[\left(R\left(\tau^{\{n\}}\right) - b\right) \sum_{t=0}^T \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\right]\]

这里的 \(b\) 就是所谓的 baseline 。用上 baseline 技巧之后，好的动作概率得到提升，坏的动作概率下降，就不会出现上述情况。

现在还有一个问题，baseline 怎么给？显然，baseline 数值上应该等于 \(\mathbb{E}[R(\tau)]\) . 在编写代码时，我们随着一条条轨迹的读取过程，逐步迭代 baseline

\[b = \frac{1}{N}\sum_{n=1}^{N}R\left(\tau^{\{n\}}\right)\]

Note

回顾一下 Dueling DQN . 这里的 baseline 其实是对于状态价值函数 \(V(s_0)\) 的估计，而 \(R(\tau_n) - b\) 就是 Dueling DQN 里提到的优势函数 \(A(s,a)\) .

更通常的情况下，baseline 是由一个网络估计出来的。

给每个动作分配合适权重

回顾一下

"我们用（一条轨迹）最后的总回报 \(R(\tau)\) 作为提升该轨迹内每个 \(\pi_{\theta}(a_t|s_t)\) 概率的步长"

这个做法明显不合理。一条轨迹总回报可能很高，但不能表明该轨迹内每个动作都是收益很高的动作；反之，就算一条轨迹的总回报很低，轨迹内也可能包含一些高收益的动作。

优化方式是计算某个状态-动作对的奖励时，不使用整条轨迹的总回报，而只计算执行该动作之后得到的奖励。

Question

Q：为什么不直接用 \((s_t, a_t)\) 对应的回报 \(r_t\) ？

A：因为此时的奖励是在估计 \(A^{\pi}(s,a) = Q^{\pi}(s,a)-V^{\pi}(s)\) 中的 \(Q^{\pi}(s,a)\). 具体而言，状态-动作对的奖励不仅要考虑即时奖励，还要考虑未来状态的奖励。

\[\theta \leftarrow \theta + \frac{\eta}{N}\sum_{n=1}^{N} \sum_{t=0}^T\left[\left(\sum_{t'=t}^T \gamma^{t'-t} r^{\{n\}}_{t'} - b\right) \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\right]\]

其中 \(\sum_{t'=t}^T \gamma^{t'-t} r^{\{n\}}_{t'} - b\) 就是对优势函数 \(A^{\pi}(s,a)\) 的估计。

REINFORCE 算法

REINFORCE 算法采取回合更新的方式，即得到一条完整轨迹后更新一次，更新公式中不包含 baseline 优化。

首先，根据当前策略 \(\pi_\theta\) 与环境交互生成一条轨迹

\[\tau = \{s_0,a_0,r_0,s_1,a_1,r_1,\cdots,s_{T-1},a_{T-1},r_{T-1},s_T,r_T\}\]

利用该轨迹数据优化策略 \(\pi_\theta\) . 从后往前，\(t=T-1,T-2,\cdots,1,0\) . 先计算当前状态-动作对的未来总奖励 \(G_t\) ，其初始值为 \(r_T\) ，\(G_{t'} = \gamma G_t + r_{t'}\) . 利用计算所得 \(G_t\) ，更新一次策略 \(\pi_\theta\) ， \(\theta \leftarrow \theta + \alpha G_{t}\nabla_{\theta}\log \pi_{\theta}(a_t|s_t)\) .

当该轨迹使用完之后，再用新策略与环境交互，重复以上过程。

举个例子，\(G_T = r_T\) ，\(G_{T-1} = \gamma G_T + r_{T-1} = \gamma r_T + r_{T-1}\) . 更新策略 \(\theta \leftarrow \theta + \alpha G_{T-1} \nabla_{\theta}\log\pi_{\theta}(a_{T-1}|s_{T-1})\) . 接下来 \(G_{T-2} = \gamma G_{T-1} + r_{T-2}\) ，重复以上过程……

Note

这里的 \(\alpha\) 是学习率，也即上文理论推导过程中的 \(\dfrac{\eta}{N}\) . 实际编程中， \(N\) 的准确性没有那么重要。

编程细节

策略梯度算法的参数更新为

\[\theta \leftarrow \theta + \frac{\eta}{N}\sum_{n=1}^{N} \sum_{t=0}^T\left[\left(\sum_{t'=t}^T \gamma^{t'-t} r^{\{n\}}_{t'} - b\right) \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\right]\]

实际上，每次更新只更新其中的一小步，即

\[\theta \leftarrow \theta +\alpha \cdot \left(\sum_{t'=t}^T \gamma^{t'-t} r^{\{n\}}_{t'} - b\right) \nabla_\theta \log \pi_\theta\left(a^{\{n\}}_t|s^{\{n\}}_t\right)\]

那么，上式如何编程实现呢？

编程实现时，我们用一个神经网络表示策略 \(\pi_\theta\) ，\(\theta\) 表示的是神经网络中的所有参数。这些参数的更新方式是大名鼎鼎的反向传播。

定义神经网络输出的损失函数 Loss Function 和学习率 \(\alpha\)，神经网络通过反向传播更新参数的过程可以表示为

\[\theta \leftarrow \theta - \alpha \cdot \nabla_{\theta}Loss\]

因此，在编程时，我们只需要如下定义神经网络的损失函数，再利用 Pytorch 等提供的反向传播方法更新神经网络即可。

\[Loss = -\left(\sum_{t'=t}^{T}\gamma^{t'-t}r_{t'}^{\{n\}}-b\right)\log\pi_{\theta}\left(a_t^{\{n\}}|s_t^{\{n\}}\right)\]