1 算法简介
本节将介绍一种 model-free 的算法，叫做「策略梯度」。该算法不需要像 model-based 的算法一样定义值函数，同时也不需要像 Q-learning 一样定义 Q 函数（Q-learning 也是 model-free 的）。我们将在「有限范围」的假设下介绍策略梯度：定义轨迹
\tau=\left(s_{0}, a_{0}, \dots, s_{T-1}, a_{T-1}, s_{T}\right)，其中
T < \infty 为轨迹的长度。此外，策略梯度仅适用于学习「随机策略」（即用概率表示），我们使用
\pi_{\theta}(a|s) 表示策略
\pi_{\theta} 在状态
s 输出动作
a 的概率。
使用策略梯度的优点在于我们只需要假定我们可以基于转移概率
\left\{P_{s a}\right\} 进行采样，并且可以在状态
s 和
a 处查询到奖励函数
R(s,a) 即可，并不需要去知道转移概率或奖励函数的精确解析形式。我们并不用明确地去学习转移概率和奖励函数。
令
s_0 采样自某个分布
\mu。我们考虑基于参数
\theta 优化策略
\pi_{\theta} 的期望总收益，如下式所示：
\eta(\theta) \triangleq \mathrm{E}\left[\sum_{t=0}^{T-1} \gamma^{t} R\left(s_{t}, a_{t}\right)\right] \tag{1}
其中
s_{t} \sim P_{s_{t-1} a_{t-1}} 以及
a_{t} \sim \pi_{\theta}\left(\cdot \mid s_{t}\right)。注意如果我们忽略有限和无限范围的差别，则
\eta(\theta) = {E}_{s_{0} \sim P}\left[V^{\pi_{\theta}}\left(s_{0}\right)\right]。我们希望使用梯度上升来最大化
\eta(\theta)，但是困难在于我们需要在不知道奖励函数和转移概率具体形式的前提下去计算
\eta(\theta) 的梯度。
我们定义一个变量
\tau，其分布由策略
\pi_{\theta} 生成，记作
P_{\theta}(\tau)。令
f(\tau)=\sum_{t=0}^{T-1} \gamma^{t} R\left(s_{t}, a_{t}\right)。我们可以将
\eta(\theta) 重写为：
\eta(\theta)=\mathrm{E}_{\tau \sim P_{\theta}}[f(\tau)] \tag{2}
上述函数的优化和变分自编码器（VAE）类似，都需要关于一个期望下的变量求解梯度（依赖于
\theta 的分布
P_{\theta}）。在 VAE 中，可以使用重参数化技术解决这一问题，但是在上式中，由于不知道奖励函数的精确形式（但我们可以通过观察奖励的加权和来估计
f），我们无法计算函数
f 的梯度。
策略梯度算法使用另一种方法来估计
\eta(\theta) 的梯度。首先执行如下推导：
\begin{align*}
\nabla_{\theta} \mathrm{E}_{\tau \sim P_{\theta}}[f(\tau)] &=\nabla_{\theta} \int P_{\theta}(\tau) f(\tau) d \tau \\
&=\int \nabla_{\theta}\left(P_{\theta}(\tau) f(\tau)\right) d \tau \quad(\text { swap integration with gradient }) \\
&=\int\left(\nabla_{\theta} P_{\theta}(\tau)\right) f(\tau) d \tau \quad(\text { becaue } f \text { does not depend on } \theta) \\
&=\int P_{\theta}(\tau)\left(\nabla_{\theta} \log P_{\theta}(\tau)\right) f(\tau) d \tau \quad(\text { because } \nabla \log P_{\theta}(\tau)=\frac{\nabla P_{\theta}(\tau)}{P_{\theta}(\tau)}) \\
&= \mathrm{E}_{\tau \sim P_{\theta}}\left[\left(\nabla_{\theta} \log P_{\theta}(\tau)\right) f(\tau)\right] \tag{3}
\end{align*}
现在，我们得到了一个针对
\nabla_{\theta} \mathrm{E}_{\tau \sim P_{\theta}}[f(\tau)] 的基于样本的估计器。令
\tau^{(1)}, \ldots, \tau^{(n)} 表示
n 个采样自
P_{\theta} 的经验样本，这些样本是通过执行策略
\pi_{\theta} n 次，每次
T 步得到的。我们可以通过下式来估计
\eta(\theta) 的梯度：
\begin{align*}
\nabla_{\theta} \mathrm{E}_{\tau \sim P_{\theta}}[f(\tau)] &=\mathrm{E}_{\tau \sim P_{\theta}}\left[\left(\nabla_{\theta} \log P_{\theta}(\tau)\right) f(\tau)\right] \tag{4}\\
& \approx \frac{1}{n} \sum_{i=1}^{n}(\nabla_{\theta} \log P_{\theta}(\tau^{(i)})) f(\tau^{(i)}) \tag{5}
\end{align*}
接下来的问题是：如何去计算
\log P_{\theta}(\tau)。我们推导出了
\log P_{\theta}(\tau) 的解析公式，并计算其关于
\theta 的梯度（使用自动微分）。基于
\tau 的定义，我们有：
P_{\theta}(\tau)=\mu\left(s_{0}\right) \pi_{\theta}\left(a_{0} | s_{0}\right) P_{s_{0} a_{0}}\left(s_{1}\right) \pi_{\theta}\left(a_{1} | s_{1}\right) P_{s_{1} a_{1}}\left(s_{2}\right) \cdots P_{s_{T-1} a_{T-1}}\left(s_{T}\right) \tag{6}
其中
\mu 表示分布
s_0 的密度。等式两边同时取对数，可以得到：
\begin{align*}
\log P_{\theta}(\tau) &=\log \mu\left(s_{0}\right)+\log \pi_{\theta}\left(a_{0}| s_{0}\right)+\log P_{s_{0} a_{0}}\left(s_{1}\right)+\log \pi_{\theta}\left(a_{1}| s_{1}\right) \\
&+\log P_{s_{1} a_{1}}\left(s_{2}\right)+\cdots+\log P_{s_{T-1} a_{T-1}}\left(s_{T}\right) \tag{7}
\end{align*}
关于
\theta 求梯度（导数），可以得到：
\nabla_{\theta} \log P_{\theta}(\tau)=\nabla_{\theta} \log \pi_{\theta}\left(a_{0} | s_{0}\right)+\nabla_{\theta} \log \pi_{\theta}\left(a_{1} | s_{1}\right)+\cdots+\nabla_{\theta} \log \pi_{\theta}\left(a_{T-1} | s_{T-1}\right)
由于转移概率相关的项与
\theta 无关，所以其梯度均为 0（恰好我们也不知道具体的概率是多少）。将上式代入公式
(4)，可以得到：
\begin{align*}
\nabla_{\theta} \eta(\theta)=\nabla_{\theta} \mathrm{E}_{\tau \sim P_{\theta}}[f(\tau)] &=\mathrm{E}_{\tau \sim P_{\theta}}\left[\left(\sum_{t=0}^{T-1} \nabla_{\theta} \log \pi_{\theta}\left(a_{t}|s_{t}\right)\right) \cdot f(\tau)\right] \\
&=\mathrm{E}_{\tau \sim P_{\theta}}\left[\left(\sum_{t=0}^{T-1} \nabla_{\theta} \log \pi_{\theta}\left(a_{t}|s_{t}\right)\right) \cdot\left(\sum_{t=0}^{T-1} \gamma^{t} R\left(s_{t}, a_{t}\right)\right)\right] \tag{8}
\end{align*}
我们可以通过经验样本的轨迹来估计等式的右边，并且该估计是无偏的（估计的期望等于真值的估计称为「无偏估计」）。使用估计的梯度，通过梯度上升迭代式地更新参数，就构成了下文所述的 vanilla 策略梯度算法。
2 对策略梯度公式的改进
对于
\nabla_{\theta} P_{\theta}(\tau)=\sum_{t=0}^{T-1} \nabla_{\theta} \log \pi_{\theta}\left(a_{t}|s_{t}\right)，可以直观地理解为使得轨迹
\tau 更容易发生（即增加选择动作
a_{0}, \dots, a_{t-1} 的概率）的
\theta 的变化方向。而
f(\tau) 则是该轨迹的总收益。因此，通过一个梯度步骤，直观上我们尝试去提升所有观察轨迹的似然性，但是对于每个
\tau 赋予不同的权重（通过
f(\tau)）。如果
\tau 的收益很大，则尝试尽量向增加该轨迹概率的方向移动；如果
\tau 的收益很小，则通过小的权重削弱其影响。
从公式
(3) 我们可以得出一个有趣的事实：
\mathrm{E}_{\tau \sim P_{\theta}}\left[\sum_{t=0}^{T-1} \nabla_{\theta} \log \pi_{\theta}\left(a_{t}| s_{t}\right)\right]=0 \tag{9}
我们令
f(\tau) = 1（即奖励为常数），那么
(8) 式的左边为 0（因为总收益为常数），因此
(8) 式的右边为 0，即
(9) 式。
实际上，我们可以进一步证明对于任意固定的
t 和
s^t，都有
\mathrm{E}_{a_{t} \sim \pi_{\theta}\left(\cdot|s_{t}\right)} \nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right)=0。基于这一事实，我们可以简化公式
(8) 为：
\begin{align*}
\nabla_{\theta} \eta(\theta) &=\sum_{t=0}^{T-1} \mathrm{E}_{\tau \sim P_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) \cdot\left(\sum_{j=0}^{T-1} \gamma^{j} R\left(s_{j}, a_{j}\right)\right)\right] \\
&=\sum_{t=0}^{T-1} \mathrm{E}_{\tau \sim P_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) \cdot\left(\sum_{j \geq t}^{T-1} \gamma^{j} R\left(s_{j}, a_{j}\right)\right)\right] \tag{10}
\end{align*}
其中第二个等式来源于：
\begin{array}{l}
\mathrm{E}_{\tau \sim P_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \cdot\left(\sum_{0 \leq j < t} \gamma^{j} R\left(s_{j}, a_{j}\right)\right)\right] \\
=\mathrm{E}\left[\mathrm{E}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) | s_{0}, a_{0}, \ldots, s_{t-1}, a_{t-1}, s_{t}\right] \cdot\left(\sum_{0 \leq j < t} \gamma^{j} R\left(s_{j}, a_{j}\right)\right)\right] \\
=0 \quad(\text { becaue } \mathrm{E}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) \mid s_{0}, a_{0}, \ldots, s_{t-1}, a_{t-1}, s_{t}\right]=0)
\end{array}
上式的推导基于全期望公式
\mathbb{E}_{\mathrm{Y}}\left\{\mathbb{E}_{\mathrm{X} | \mathrm{Y}}[X | Y]\right\}=\mathbb{E}_{\mathrm{X}}[x] ，因为期望是针对 t 时间以内的，所以要对奖励函数进行分割。第二行中外面的期望关于随机变量
s_{0}, a_{0}, \dots, a_{t-1}, s_{t}，而内部的期望则关于
a_t（以
s_{0}, a_{0}, \dots, a_{t-1}, s_{t} 为条件）。通过上面的推导，我们将估计器进行了简化。
进一步地，基于
\mathrm{E}_{a_{t} \sim \pi_{\theta}\left(\cdot | s_{t}\right)} \nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right)=0，我们可以得出对于任意的值
B(s_t)（其只依赖于
s_t），下式成立：
\begin{array}{l}
\mathrm{E}_{\tau \sim P_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} \mid s_{t}\right) \cdot B\left(s_{t}\right)\right] \\
=\mathrm{E}\left[\mathrm{E}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} s_{t}\right) | s_{0}, a_{0}, \ldots, s_{t-1}, a_{t-1}, s_{t}\right] B\left(s_{t}\right)\right] \\
=0 \quad\left(\text { because } \mathrm{E}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) | s_{0}, a_{0}, \ldots, s_{t-1}, a_{t-1}, s_{t}\right]=0\right)
\end{array}
上式的推导与之前类似，同样基于全期望公式。现在，我们可以对
(11) 式进行如下变化：
\begin{align*}
\nabla_{\theta} \eta(\theta) &=\sum_{t=0}^{T-1} \mathrm{E}_{\tau \sim P_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) \cdot\left(\sum_{j \geq t}^{T-1} \gamma^{j} R\left(s_{j}, a_{j}\right)-\gamma^{t} B\left(s_{t}\right)\right)\right] \\
&=\sum_{t=0}^{T-1} \mathrm{E}_{\tau \sim P_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}\left(a_{t} | s_{t}\right) \cdot \gamma^{t}\left(\sum_{j \geq t}^{T-1} \gamma^{j-t} R\left(s_{j}, a_{j}\right)-B\left(s_{t}\right)\right)\right] \tag{11}
\end{align*}
因此，对于不同选择的
B(\cdot)，我们会得到用于估计
\nabla \eta(\theta) 的不同估计器。引入适当的
B(\cdot) 的好处在于，其可以帮助减少估计器的方差。我们也将
B(\cdot) 称为「基线」。实际上，可以证明
B 的接近最优的选择是未来收益的期望
\mathrm{E}\left[\sum_{j \geq t}^{T-1} \gamma^{j-t} R\left(s_{j}, a_{j}\right) | s_{t}\right]，在忽略有限和无限范围的区别时（之前只有无限范围才有折扣因子）即等同于值函数
V^{\pi_{\theta}}\left(s_{t}\right)。这里我们可以对该值函数进行一个模糊的估计，因为其具体值并不影响估计整体估计器的均值，只影响其方差。将上述方法整合起来，即可得到下面的算法：
注意
(13) 式和
(11) 式稍有不同，去除了折扣因子（以及期望的归一化），经验上来看这可以带来更大的更新，有助于算法收敛。
3 思维导图
