强化学习（策略梯度法）
本文介绍了强化学习的策略梯度法（Policy Gradient）。
1. 回顾
基于价值函数的强化学习方法
- 动态规划方法（Dynamic Programming, DP）
- 蒙特卡洛方法（Monte Carlo, MC）
- 时序差分方法（Temporal-Difference, TD）
这三种方法存在共同特点：
- 在求解强化学习任务时，最终目标是求解满足规则的最优策略 $\pi$。但以上三种方法并 没有直接求解 策略 $\pi$ 这个变量，而是先计算状态价值函数 $V_\pi(s)$ 或状态-动作价值函数 $q_\pi(s,a)$；然后再基于价值函数结果改进策略 $\pi$，是一种间接方式;
- 在策略改进过程中，本质上均选择最优价值函数对应的动作作为新的策略；
- 均为表格式强化学习的代表方法。
特别地，对于 DQN 方法，神经网络的输入是原始的状态信息，如游戏画面，输出是在这种状态下执行各种动作的回报，即价值函数（Q函数）。训练完成之后，神经网络逼近的是最优 Q 函数 $Q(s,a)$。
1
2
3
+----+ ---->Q(s,a1) +----+
s ---> |f(x)| ---->Q(s,a2) or s,ai --->|f(x)| ---->Q(s,ai)
+----+ ---->Q(s,a3) +----+
以 DQN 为代表的基于价值的强化学习方法，虽然在某些问题上取得了成功，但存在以下问题：
-
无法表示随机策略。某些问题的最优策略是随机策略，需要以不同的概率选择不同的动作。而基于价值的强化学习算法在实现时采用了贪心策略，给定一个状态 ，选择的策略是确定性的，显然无法实现这种按照概率执行各种候选动作的要求。比如石头剪刀布的最优策略是以 (1/3, 1/3, 1/3）的概率来选择石头/剪刀/布，基于价值的强化学习无法实现这种策略。
-
无法处理高维动作空间。DQN 要求动作空间是离散的，且只能是有限个，这样才能寻找使动作值函数最大化的动作的操作。但在很多问题特别是物理控制任务中，具有连续实值和高维的动作空间，例如要控制在 x y z 方向的速度、加速度。DQN 不能直接应用。
-
难以收敛。基于价值的强化学习方法输出的价值（如各个动作的最优
Q函数值）的微小改变会导致某一动作被选中或不选中，这种不连续的变化会影响算法的收敛。这很容易理解，假设一个动作a的Q函数值本来在所有动作中是第 2 大的，把它增加 0.0001，就变成第最大的，那这种微小的变化会导致策略完全改变。因为之前它不是最优动作，现在变成最优动作了。 -
存在徘徊。在观察受限的情况下，基于价值的强化学习方法会出现徘徊现象。即出现不同状态导致的观察相同，使得对应相同的 “最佳” 策略，但明显不符合任务实际情况的现象。
2. 策略梯度
2.1. 策略函数
相比之下，策略梯度算法是一种更为直接的方法，它让神经网络直接输出策略函数 $\pi(s)$，即在状态s下应该执行何种动作。对于非确定性策略，输出的是这种状态下执行各种动作的概率值，即如下的条件概率
\[\pi(a\vert s) = p(a\vert s)\]所谓确定性策略，是只在某种状态下要执行的动作是确定即唯一的，而非确定性动作在每种状态下要执行的动作是随机的，可以按照一定的概率值进行选择。这种做法的原理如下图所示。
1
2
3
4
+----+ ---->p(a1|s)
s ---> |f(x)| ---->p(a2|s)
| θ | ---->...
+----+ ---->p(a3|s)
若动作 $a$ 是连续性随机变量，因此此时的策略 $\pi$ 不再是上述概率集合的形式，而是可微函数的形式——动作发生的概率受到某个概率密度函数的控制。假设动作 $a$ 服从某一概率密度函数 $P(a\vert s;\theta)$ (换种思路理解——将动作 $a$ 理解成从概率模型 $P(a\vert s;\theta)$ 产生的样本)。最终目标从求解 $P(a\vert s;\theta)$ 转换成求解策略中的参数 $\theta$。因此，将含参数 $\theta$ 的策略称为策略函数。记作 $\pi(a \vert s;\theta)$，通常情况下可简写成 $\pi_{\theta}$。
2.2. 策略函数的分布形式
- 如果动作 $a$ 是离散型随机变量 $\to$ 使用 $softmax$ 函数将其映射为 指数族分布
这里并不是一定要使用 $softmax$ 函数进行映射 $\to$ 只要能够映射为 ‘指数族分布’ 即可。
将 $h(s,a;\theta)$ 函数定义为 ‘动作偏好值’ $\to$ 将离散型的策略 $\pi(a \vert s;\theta)$ 视为关于 $\theta$ 的一个函数，有 \(\pi(a \vert s;\theta) \rightarrow \frac{e^{h(s,a;\theta)}}{\sum_{a'}e^{h(s,a';\theta)}}\)
- 如果动作 $a$ 是连续型随机变量 $\to$ $a$ 服从的分布可以有很多种，不妨设 $a$ 服从 高斯分布
这里将高斯分布中的 $\mu,\sigma$ 看作参数 $\theta$ 的函数，若 $\theta$ 能够求解， $\mu,\sigma$ 同样也可以被求解，最终求解整个分布
\[\mu=\mu(s;\theta),\sigma=\sigma(s;\theta)\]至此，假设 $a$ 是服从 1 维随机变量的高斯分布，策略函数 $\pi(a \vert s;\theta)$ 表示如下
\[\pi(a \vert s;\theta) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(a-\mu)^2}{2\sigma^2}}\]为了改进策略函数，需要围绕参数 $\theta$ 构建一个目标函数 $J(\theta)$，然后通过梯度下降（上升）的方式更新参数。
在后面我们会发现，最终需要计算目标函数的梯度，相当于计算策略函数的对数的梯度 但通常我们不会直接使用策略函数的对数的梯度，因为可以采用线程的深度学习框架（PyTorch或者TensorFlow）自动求导来完成。
2.3. 策略梯度的概念
- 回顾价值梯度
首先回顾 Q-Learning 的核心思想，即通过一步采样更新 Q 值（即TD方法的思想）
\[Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha[r_{t+1}+\gamma\max_a 𝑄(s_{t+1},a)−Q(s_t,a_t)]\]上述更新过程可以收敛，意味着
\[r_{t+1}+\gamma\max_a 𝑄(s_{t+1},a)−Q(s_t,a_t) \rightarrow 0\]那么我们可以构造一个参数为 $\theta$ 的深度神经网络，用来估计价值函数，即 DQN 方法
\[Q(s,a) = Q(s,a; \theta)\]则训练用的损失函数可设计为
\[L(\theta) = \mathbb{E} \{[r_{t+1}+\gamma\max_a 𝑄(s_{t+1},a; \theta)−Q(s_t,a_t; \theta)]^2\}\]然后，通过梯度下降更新神经网络的参数，使得损失函数 $L(\theta)$ 最小。 \(\theta \leftarrow \theta - \alpha \nabla_{\theta} L(\theta)\)
注意到损失函数中只有最后一项是关于 $\theta$ 的函数，因此损失函数的梯度可以写为
\[\nabla_{\theta} L(\theta) = \alpha[r_{t+1}+\gamma\max_a 𝑄(s_{t+1},a; \theta)−Q(s_t,a_t; \theta)]\nabla_{\theta} Q(s_t,a_t; \theta)\]其中，$\alpha$ 是学习率，$\theta$ 是神经网络的参数。
可以看出，在基于价值的强化学习中，价值函数是我们的学习目标，从而定义出损失函数。通过更新式收敛保证价值函数的最优。
- 策略梯度
类似地，策略梯度算法的核心思想就是通过计算策略函数的梯度，来更新神经网络的参数。对于非确定性策略，神经网络的输出的是这种状态下执行各种动作的概率值，即如下的条件概率
\[\pi(a\vert s) = p(a\vert s)\]那么损失函数的定义必然包含输出的条件概率（这样才能衡量输出于真值之间的误差），对应的参数更新梯度计算式形如
\[\theta \leftarrow \theta + \nabla_\theta J(\pi(a\vert s ; \theta))\]其中 $J(\pi(a\vert s;\theta))$ 可简记为 $J(\theta)$。 上式为何要用梯度上升（即加号）后文再来解释。那么问题就转化为：
- 目标函数（损失函数）是否存在？
- 目标函数（损失函数）的梯度（即策略梯度）是否存在？
- 如何计算策略梯度？
3. 策略梯度的计算
3.1. 基于累计收益的策略梯度
计算策略梯度的目的，是为了更新神经网络的参数，使神经网络产生的能够得到大的奖励的动作的概率变大。回想价值学习的目标是什么？强化学习的目标是使得获得的奖励最大化。
定义神经网络输出的策略为 $\pi:=p(a\vert s;\theta)$，其中 $\theta$ 是神经网络的参数。假设采样一条马尔科夫轨迹如下
\[\tau = {s_1,a_1,r_1,s_2,a_2,r_2,...,s_T,a_T,r_T}\]那么该轨迹发生的概率为
\[p_{\theta}(\tau) = p(s_1)\prod_{t=1}^T p(a_t\vert s_t;\theta)p(s_{t+1}\vert s_t,a_t)\]其中，$p(s_1)$ 为初始状态的概率；$p(s_{t+1}\vert s_t,a_t)$ 为环境转移概率，即在状态 $s_t$ 下执行动作 $a_t$ 后，进入状态 $s_{t+1}$ 的概率。注意这两个概率均与网络参数无关。
不考虑折扣衰减，该轨迹获得的收益为累计回报
\[R(\tau) = \sum_{t=0}^T r_t\]由于马尔科夫链是采样得到的，因此当前策略可获得的期望奖励为
\[\mathbb{E} [R(\tau)] = \sum_{\tau} p_{\theta}(\tau)R(\tau)\]因此我们可以定义目标函数为
\[J(\theta) = \mathbb{E} [R(\tau)]\]定义策略梯度为
\[\nabla_{\theta}J(\theta) = \nabla_{\theta}\mathbb{E} [R(\tau)] = \nabla_{\theta}\sum_{\tau} p_{\theta}(\tau) R(\tau) = \sum_{\tau} \nabla_{\theta}p_{\theta}(\tau) R(\tau)\]注意，强化学习的目的是最大化这个期望奖励，因此需要用梯度上升来更新神经网络参数。
\[\theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)\]- 问题转化为：如何计算 $\nabla_{\theta}p_{\theta}(\tau)$
注意到 $p_{\theta}(\tau)$ 是许多概率连乘的形式，如果直接计算其梯度，势必存在数据下溢（概率都是小于等于 1 的，多个概率连乘后数值会非常小），需要想办法避免。一种直觉思路是通过取对数把连乘转化为连加。
对 $log(f(x))$ 函数求梯度具备如下性质
\[\nabla_{\theta} \ln f(x) = \frac{\nabla_{\theta} f(x)}{f(x)}\]因此有
\[\nabla_{\theta} f(x) = f(x)\nabla_{\theta} \ln f(x)\]将 $p_{\theta}(\tau)$ 带入即可得
\[\nabla_{\theta}p_{\theta}(\tau) = p_{\theta}(\tau)\nabla_{\theta} \ln p_{\theta}(\tau)\]因此有
\[\begin{aligned} \nabla_{\theta}\mathbb{E} [R(\tau)] &= \sum_{\tau} \nabla_{\theta}p_{\theta}(\tau) R(\tau)\\ &= \sum_{\tau} p_{\theta}(\tau)\nabla_{\theta} \ln p_{\theta}(\tau) R(\tau) \\ &=\mathbb{E}_{\tau\sim p_{\theta(\tau)}}[\nabla_{\theta} \ln p_{\theta}(\tau) R(\tau)] \end{aligned}\]- 问题转化为：如何计算 $\nabla_{\theta} \ln p_{\theta}(\tau)$
首先通过蒙特卡洛方法进行 $N$ 次采样来近似估计期望，可将期望式打开得到
\[\begin{aligned} \nabla_{\theta}\mathbb{E} [R(\tau)] &=\mathbb{E}_{\tau\sim p_{\theta(\tau)}}[\nabla_{\theta} \ln p_{\theta}(\tau) R(\tau)]\\ &=\frac{1}{N} \sum_{n=1}^N \nabla_{\theta} \ln p_{\theta}(\tau_n) R(\tau_n) \end{aligned}\]其中，$\tau_n$ 是第 $n$ 次采样得到的轨迹。那么对于这条具体的轨迹有
\[\begin{aligned} \nabla_{\theta} \ln p_{\theta}(\tau_n) &= \nabla_{\theta} \left[\ln p(s_1) + \sum_{t=1}^T \ln p_{\theta}(a_t\vert s_t) +\sum_{t=1}^T \ln p(s_{t+1}\vert s_t,a_t)\right]_n\\ &= \nabla_{\theta}\sum_{t=1}^T\ln p_{\theta}(a_t^n\vert s_t^n) = \sum_{t=1}^T\nabla_{\theta}\ln p_{\theta}(a_t^n\vert s_t^n)\\ \end{aligned}\]上式可以看出，充分利用了对数函数把连乘转为连加的好处。其中第一项和第三项与网络参数 $\theta$ 无关，因此对其求梯度为 0，仅剩第二项。这里 $p_{\theta}(a_t^n\vert s_t^n) = p(a_t^n\vert s_t^n;\theta)$。
最后可得到如下更新式
\[\nabla_{\theta}J(\theta) = \frac{1}{N}\sum_{n=0}^N \sum_{t=0}^T \nabla_{\theta}\ln p_{\theta}(a_t^n\vert s_t^n) R(\tau_n)\] \[\theta \leftarrow \theta + \alpha \nabla_{\theta} J(\theta)\]最后，如果我们重新把策略梯度写为期望的形式，注意到之前定义的 $\pi :=p(a\vert s)$，有
\[\nabla_{\theta}J(\theta)=\mathbb{E}_{\pi(\theta)} [\nabla_{\theta}\ln \pi_{\theta}(a\vert s) R]\]到后面我们可以发现，策略梯度的定义不局限于这一种形式，主要反映在期望括号内后一项的选择上。
3.2. 基于初始状态价值的策略梯度
前面基于累计收益的策略梯度方法存在一个局限，即只适用于蒙特卡洛采样能够采样到终止状态的情况，此时累计收益可以计算得到特定的值。如果采样无法达到终止状态，蒙特卡洛序列就无限延申，就无法计算累计收益了。为了解决这个问题，需要换个角度思考。
之前基于累计收益的策略梯度，并没有考虑折扣因子。如果考虑包含折扣因子的情况，相当于利用初始状态回报的期望，即初始状态的状态价值函数来衡量轨迹的优劣，对应的目标函数为
\[J(\theta) = \mathbb{E} [R(\tau)]= \mathbb{E}[\sum_{t=0}^T \gamma^{t-1} r_t] = V_{\pi(a\vert s ; \theta)}(s_0)\]简化起见，写为
\[J(\theta) = \mathbb{E} [R(\tau)]= V_{\pi}(s)\]那么有
\[\nabla_{\theta}J(\theta) = \nabla_{\theta}V_{\pi}(s)\]3.3. 策略梯度定理
策略梯度定理本质就是求解目标函数 $J(\theta)$ 的梯度。首先使用贝尔曼期望方程对 $V(s)$ 进行展开
\[\nabla_{\theta}V_{\pi}(s) = \nabla_{\theta}\sum_{a\in \mathcal{A(s)}} \pi(a\vert s)q_{\pi}(s,a) = \sum_{a\in \mathcal{A(s)}}\nabla_{\theta}[\pi(a\vert s)q_{\pi}(s,a)]\]注意到求梯度是对网络参数 $\theta$ 进行的，而所有和策略 $\pi$ 有关的项均隐含 $\theta$，所以上述式子需要采用乘法求导的形式展开
\[\begin{aligned} \nabla_{\theta}V_{\pi}(s) &= \sum_{a\in \mathcal{A(s)}}\nabla_{\theta} [\pi(a\vert s)q_{\pi}(s,a)]\\ &= \sum_{a\in \mathcal{A(s)}} [\nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a) + \pi(a\vert s) \nabla_{\theta}q_{\pi}(s,a)]\\ \end{aligned}\]其中第二项
\[\begin{aligned} \nabla q_{\pi} (s,a) &= \nabla \sum_{s^\prime,r} P(s^\prime,r\vert s,a)[r+\gamma V_{\pi}(s^\prime)]\\ &=\nabla \sum_{s^\prime,r}^{s^\prime,r} P(s^\prime,r|s,a) r + \nabla \sum_{s^\prime,r} \gamma P(s^\prime,r|s,a)V_{\pi}(s^\prime)\\ &=\nabla \sum_{s^\prime,r} \gamma P(s^\prime,r|s,a)V_{\pi}(s^\prime)\\ &=\gamma \sum_r P(r\vert s,a)\sum_{s^\prime} P(s^\prime\vert s,a) \nabla V_{\pi}(s^\prime)\\ &=\gamma \sum_{s^\prime} P(s^\prime\vert s,a) \nabla V_{\pi}(s^\prime) \end{aligned}\]带回梯度式子，即
\[\nabla_{\theta}V_{\pi}(s) = \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a) + \sum_{a\in \mathcal{A(s)}} \pi(a\vert s)\gamma \sum_{s^\prime} P(s^\prime\vert s,a) \nabla_{\theta} V_{\pi}(s^\prime)\]可以看出，上式呈现出 $\nabla_{\theta}V_{\pi}(s)$ 的迭代形式。为了更进一步确定迭代关系，再次对 $\nabla_{\theta}V_{\pi}(s^\prime)$ 展开，有
\[\nabla_{\theta}V_{\pi}(s^\prime) = \sum_{a^\prime\in \mathcal{A(s^\prime)}} \nabla_{\theta}\pi(a^\prime\vert s^\prime) q_{\pi}(s^\prime,a^\prime) + \sum_{a^\prime\in \mathcal{A(s^\prime)}} \pi(a^\prime\vert s^\prime)\gamma \sum_{s^{\prime\prime}} P(s^{\prime\prime}\vert s^\prime,a^\prime) \nabla_{\theta} V_{\pi}(s^{\prime\prime})\]带回梯度式子并且完全展开，有
- 第一项
-
第二项
\[\begin{aligned} &\sum_{a\in \mathcal{A(s)}} \pi(a\vert s)\gamma \sum_{s^\prime} P(s^\prime\vert s,a)\cdot \sum_{a^\prime\in \mathcal{A(s^\prime)}} \nabla_{\theta}\pi(a^\prime\vert s^\prime) q_{\pi}(s^\prime,a^\prime) \\ =&\gamma \sum_{s^\prime}\sum_{a\in \mathcal{A(s)}} \pi(a\vert s) P(s^\prime\vert s,a)\cdot \sum_{a^\prime\in \mathcal{A(s^\prime)}} \nabla_{\theta}\pi(a^\prime\vert s^\prime) q_{\pi}(s^\prime,a^\prime) \\ =&\gamma \sum_{s^\prime} \mathcal{P}(s^\prime\vert s)\cdot \sum_{a^\prime\in \mathcal{A(s^\prime)}} \nabla_{\theta}\pi(a^\prime\vert s^\prime) q_{\pi}(s^\prime,a^\prime)\\ \end{aligned}\]上式仅包含前后状态的变量 $s,s^\prime$ 和转移次数常量 $k=1$（$a$ 最终会被求和吸收积分掉），因此可进一步写为通项式：
\[\gamma \sum_{x\in S} \mathcal{P}(s\rightarrow x, k, \pi)\cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert x) q_{\pi}(x,a)\]同时，注意到第一项也符合上述通项式（$k=0,\gamma = 1$）
-
第三项
\(\sum_{a\in \mathcal{A(s)}} \pi(a\vert s)\gamma \sum_{s^\prime} P(s^\prime\vert s,a) \cdot \sum_{a^\prime\in \mathcal{A(s^\prime)}} \pi(a^\prime\vert s^\prime)\gamma \sum_{s^{\prime\prime}} P(s^{\prime\prime}\vert s^\prime,a^\prime) \nabla_{\theta} V_{\pi}(s^{\prime\prime})\) 注意到第三项仍然是个迭代式，可以继续展开，且展开除了最后一项，前面均符合前述通项式。
至此， $\nabla V_\pi(s)$ 的迭代式表示如下
\[\nabla_{\theta}V_{\pi}(s) = \sum_{s\in S} \sum_{k=0}^{\infty} \gamma^{k} \mathcal{P}(s\rightarrow x, k, \pi)\cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert x) q_{\pi}(x,a)\]将公式中所有 $s$ 替换为初始状态 $s_0$，将所有 $x$ 替换为 $s$，我们得到了初始状态价值函数的梯度
\[\nabla_{\theta}V_{\pi}(s_0) = \sum_{s\in S} \sum_{k=0}^{\infty} \gamma^{k} \mathcal{P}(s_0\rightarrow s, k, \pi)\cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a)\]其中，
- $\mathcal{P}(s_0\rightarrow s, k, \pi)$ 表示初始状态 $s_0$ 经过 $k$ 次状态转移最终到达 $s$ 的概率；
- $\sum_{k=0}^{\infty} \mathcal{P}(s_0\rightarrow s, k, \pi)$ 表示在整条轨迹序列中，状态 $s$ 出现的平均次数，将其记为 $\eta(s)$；
- 那么状态 $s$ 出现的概率 $\mu(s)$ 可定义为其出现的平均次数除以所有状态出现的平均次数的和，即 $\mu(s) = {\eta(s)}/{\sum_{s^\prime} \eta(s^\prime)}$
则
\[\begin{aligned} \nabla_{\theta}V_{\pi}(s_0) &= \sum_{s\in S} \gamma^{k} \eta(s) \cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a)\\ &= \sum_{s\in S} \gamma^{k} \mu(s)\sum_{s^\prime} \eta(s^\prime) \cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a)\\ &= \sum_{s^\prime} \eta(s^\prime) \cdot \sum_{s\in S} \gamma^{k} \mu(s) \cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a)\\ \end{aligned}\]其中，第一项为一个常数（归一化因子），$\gamma$ 折扣率也是一个常数，它们只影响梯度的具体数值。我们更关注梯度的方向，因此
\[\nabla_{\theta}V_{\pi}(s_0) \propto \sum_{s\in S} \mu(s) \cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a)\]观察前面策略梯度方向的求解结果，可以发现 $\mu(s)$ 本身是状态 $s$ 出现的概率，因此我们可以其联通前面的求和符号一起表示为某种期望的形式
\[\nabla_{\theta}J(\theta) \propto \sum_{s\in S} \mu(s) \cdot \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a)=\mathbb{E}_{?}\left[ \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a) \right]\]问题转化为，确定期望符号中的概率分布是什么（也即上式中的 ? 部分）。既然是关于状态的概率分布，我们定义这样一个分布符号：$\rho^{\pi_{\theta}}$，使得状态 $s$ 的出现概率服从该分布。该分布不仅和策略函数 $\pi(a\vert s;\theta)$ 相关，还与环境（状态转移概率）相关。
则
\[\nabla_{\theta}J(\theta) \propto \mathbb{E}_{s\sim\rho^{\pi_{\theta}}}\left[ \sum_{a\in \mathcal{A(s)}} \nabla_{\theta}\pi(a\vert s) q_{\pi}(s,a) \right]\]为了使公式规范化
- 将所有状态 $s$ 和动作 $a$ 加上特定时刻 $t$ 下标；
- 将策略函数的参数补充上；
继续观察，上式还存在一个求和符号，因此存在一个想法是将该部分也化为期望的形式。但 $\nabla_{\theta}\pi(a_t\vert s_t;\theta)$ 并不是策略函数，因此需要引入策略函数，借助之前 log 函数梯度的性质，有
将期望的下标进行简化，最终我们得到了基于价值的策略梯度
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) q_{\pi}(s_t,a_t) \right]\\\]那么如何计算 $q_{\pi}(s_t, a_t)$ 呢？有两种思路：
- MC：使用采样的 $G_t$ 来近似估计，对应 REINFORCE 方法，或称为蒙特卡洛策略梯度方法；
- TD：使用 TD 算法，对应 Actor Critic 方法。
4. 基于策略梯度的强化学习
4.1. REINFORCE
前面之所以将 $\nabla_{\theta}J(\theta)$ 化简为期望形式，是因为期望形式就可以通过 蒙特卡洛方法 采样的方式来近似求解。
根据 Q 函数的定义有
\[q_{\pi_{\theta}}(s_t, a_t) = \mathbb{E} [G_t\vert s_t, a_t]\]带入策略梯度定理有
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) G_t \right]\]至此，我们可以通过采样 $\nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) G_t$ 神经网络参数 $\theta$ 进行更新。这就是 REINFORECE 方法。REINFORCE 的本质就是用 $G_t$ 代替 $q_{\pi}(s_t, a_t)$。
用于估计最优策略的REINFORCE算法表示如下（采用增量更新的方式）
- 输入：可微策略函数 $\pi(a \vert s;\theta)$，衰减因子 $\gamma$，学习率 $\alpha$
- 初始化：策略函数的参数 $\theta$
- 训练过程：
- repeat 根据策略函数采样一条轨迹：$s_0, a_0, r_1, s_2, a_2, r_3, \cdots$
- loop $t=T-1, T-2, \cdots, 1,0$
- $\quad G\leftarrow \gamma G + R_{t+1}$
- $\quad \theta \leftarrow \theta + \alpha G \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta)$
根据定义，因为 $G_t$ 是 $Q(s,a)$ 的无偏估计，所以基于蒙特卡洛采样的方式进行参数更新的 REINFORCE 算法，得到的结果就是策略梯度的无偏估计，那么其方差呢？
结论：基于蒙特卡洛采样的方式进行参数更新的 REINFORCE 算法方差很大。通过观察策略梯度式
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) G_t \right]\]我们可以看出，$\nabla_{\theta}\ln\pi(a_t\vert s_t;\theta)$ 相当于 $G$ 的一个系数或者说权重，对于方差而言只起到放缩作用（根据公式 $Var(aX) = a^2Var(X)$），实际方差还是取决于 $G$ 本身。而 $G$ 的方差
\[Var(G_t) = Var(R_{t+1}) + Var(R_{t+2}) + \cdots\]由此可以看出，方差大来源于两个原因：
- 若不同 $s$ 对应的 $R$ 范围相差较大，再加上 MC 的随机性，那么每一步的 $R$ 都会有较大的方差;
- 因为采样轨迹长度的原因，出现方差累积。
相应的解决方法如下：
- 通过添加基线缓解;
- 使用 TD 方法代替 MC 方法，即通过Actor-Critic方法解决。
4.2. REINFORCE with baseline
通过添加基线（baseline）可以减小方差。具体形式如下
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) G_t \right]\]添加基线 $b(s)$ 后，目标函数的梯度变为
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) (G_t-b(s_t)) \right]\]参数更新方式变为
\[\theta \leftarrow \theta + \alpha (G_t - b(s_t)) \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta)\]基线 $b(s)$ 可为任意变量或者函数，只要不与动作 $a$ 有关。因为它并不会改变策略梯度的期望，证明如下
\[\begin{aligned} \nabla_{\theta}J(\theta) &\propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) (G_t-b(s_t)) \right]\\ &\propto \sum_{a}\pi(a\vert s) \nabla_{\theta}\ln \pi(a\vert s;\theta)(G_t-b(s_t))\\ &\propto \sum_{a} \nabla_{\theta}\pi(a\vert s;\theta)(G_t-b(s_t)) \end{aligned}\]因为 $b(s)$ 与动作 $a$ 无关，可以提到求和符号外面，但注意 $G_t$ 不可以提到求和符号外面
\[\begin{aligned} \nabla_{\theta}J(\theta) &\propto \sum_{a} \nabla_{\theta}\pi(a\vert s;\theta)(G_t-b(s_t))\\ &\propto \sum_{a} G_t \nabla_{\theta}\pi(a\vert s;\theta) - b(s_t) \sum_{a} \nabla_{\theta}\pi(a\vert s;\theta)\\ \end{aligned}\]对于后一项，交换梯度符号和求和符号，有
\[b(s_t) \sum_{a} \nabla_{\theta}\pi(a\vert s;\theta) =b(s_t)\nabla_{\theta} \sum_{a} \pi(a\vert s;\theta) = b(s_t)\nabla_{\theta} 1 = 0\]得证。
关于基线的更多内容参考：https://zhuanlan.zhihu.com/p/636907461
为什么引入基线可以减小方差？证明如下：
首先根据方差的定义
\[Var(X) = E(X^2)-E(X)^2\]那么有
\[Var(\nabla_{\theta}J(\theta)) = Var(\nabla_{\theta}^2)-\nabla_{\theta}^2 E(\nabla_{\theta})\]我们又知道引入基线不改变期望，因此方差的第二项取值与是否包含基线无关，则只需要关注第一项即可
\[\begin{aligned} Var \nabla_{\theta}J(\theta)^2 &= E[\nabla_{\theta}\ln\pi_{\theta}(a_t\vert s_t)^2\cdot (G_t - b(s_t))^2] \\ &= E[\nabla_{\theta}\ln\pi_{\theta}(a_t\vert s_t)^2]\cdot E[(G_t - b(s_t))^2] \end{aligned}\]当基线 $b(s_t)=\mathbb{E}[G_t]$ 是 $G_t$ 的期望的某个估计的时候，方差最小，即
\[E[\nabla_{\theta}\ln\pi_{\theta}(a_t\vert s_t)^2]\cdot E[(G_t - \mathbb{E}[G(s_t)])^2] < E[\nabla_{\theta}\ln\pi_{\theta}(a_t\vert s_t)^2]\cdot E[(G_t - 0)^2]\]4.3. Actor-Critic (related to V)
虽然基线 $b(s)$ 可为任意变量或者函数，但实际情况下，一种自然而然的想法是将基线设置为状态价值的估计，即
\[b(s) = {v}(s_t) = \mathbb{E}(G_t \vert s=s_t)\]这样可以使得 $G_t - b(s)$ 更加稳定，随机性更少。更进一步，因为 REINFORCE 本身是基于蒙特卡洛方法，那么自然而然可以同样使用蒙特卡洛方法来学习价值函数，即
\[b(s) = {v}(s_t;{w})\]其中 $w$ 是另一套习得的参数。
到此为止，我们就可以将 REINFORCE 算法转化为 Actor-Critic 算法，其中参数 $\theta$ 对应策略梯度部分的神经网络，扮演 Actor 的角色；而 $w$ 对应价值估计部分的神经网络，扮演 Critic 的角色。此时目标函数的梯度变为
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) (G_t-{v}(s_t;{w})) \right]\]更进一步，类似于基于价值的强化学习方法中，MC 到 TD 方法的逻辑演变，这里我们同样不需要采样完整的一条轨迹，而是仅采样一步，后续通过自举的方式逐步估计完整的轨迹。
此时价值网络的更新形式为
\[\begin{aligned} \delta_t &= R_{t+1}+\gamma v(s_{t+1};\omega)-v(s_t;\omega)\\ J(\omega) &= \frac{1}{2} \delta_t^2\\ \omega &\leftarrow \omega - \alpha_{\omega} \delta_t \nabla_{\omega}v(s;\omega) \end{aligned}\]此时策略网络的更新形式为
\[\begin{aligned} \delta_t &= R_{t+1} + \gamma {v}(s_{t+1};w)-{v}(s_t;{w})\\ \nabla_{\theta}J(\theta) &\propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) \delta_t \right]\\ \theta &\leftarrow \theta + \alpha \delta_t \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) \end{aligned}\]Actor-Critic related to V 算法的训练过程如下
- 输入：
- 可微策略函数 $\pi(a \vert s;\theta)$
- 可微的价值函数 ${v}(s;w)$
- 衰减因子 $\gamma$，学习率 $\alpha_\theta,\alpha_w$
- 初始化：
- 策略函数的参数 $\theta$
- 价值函数的参数 $w$
- 训练过程：
- loop 状态 $s$ 没有结束时
- 根据策略采样：$a\sim \pi(\cdot, s;\theta)$
- 执行动作 $a$， 得到奖励 $R$，转移状态到 $s^\prime$
- $\delta \leftarrow R + \gamma {v}(s^\prime;w) - {v}(s;w)$
- $w \leftarrow w + \alpha_w \delta\nabla_{w}{v}(s;w)$
- $\beta \leftarrow \gamma \delta$
- $\theta \leftarrow \theta + \alpha \beta \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta)$
- loop 状态 $s$ 没有结束时
4.4. Actor-Critic (related to Q)
前面我们采用状态价值函数 $v(s)$ 作为基线函数，我们同样可以采用状态-动作价值函数 $q(s,a)$ 作为基线函数
\[b(s_t) = q(s_t, a_t;\omega)\]由于对于一个状态而言，其状态-动作价值函数有多个取值，我们一般使用其最大值来计算基线，
此时价值网络的更新形式为
\[\begin{aligned} \delta_t &= R_{t+1}+\gamma q(s_t, a_t;\omega)-q(s_t, a_t;\omega)\\ J(\omega) &= \frac{1}{2} \delta_t^2\\ \omega &\leftarrow \omega - \alpha_{\omega} \delta_t \nabla_{\omega}q(s,a;\omega) \end{aligned}\]对于策略网络的目标函数的梯度，应该使用原始的策略网络的目标函数的梯度形式，将其中动作价值函数 $q(s,a)$ 替换为使用了价值网络来的估计值，得到
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) q(s_t,a_t;\omega) \right]\]此时策略网络的更新形式为
\[\begin{aligned} \nabla_{\theta}J(\theta) &\propto \mathbb{E} [ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) q(s_t,a_t;\omega)]\\ \theta &\leftarrow \theta + \alpha_{\theta}{q(s,a;\omega)}\nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) \end{aligned}\]4.5. Advantage Actor-Critic (A2C)
前面介绍 VAC 的时候，我们引入一个基线，即在计算期望的时候用累计奖励 $G_t$ 减去一个 baseline ，这样做的好处是可以让梯度减小，因此梯度下降的步子也就更平缓，从而使训练过程更稳定。进一步，我们讨论了将基线设置为状态价值函数是一个较优的选择。本着这种思想，我们再次回顾策略梯度的原始目标函数梯度式，同样引入状态价值函数 $v_{\pi}(s_t)$ 作为基线，有
\[\nabla_{\theta}J(\theta) \propto \mathbb{E} \left[ \nabla_{\theta}\ln\pi(a_t\vert s_t;\theta) (q_{\pi}(s_t,a_t)-v_{\pi}(s_t)) \right]\]我们称 $A(s_t, a_t) = q_{\pi}(s_t,a_t)-v_{\pi}(s_t)$ 为优势函数。优势函数表示在状态 $s$ 下采取动作 $a$ 相对于平均水平的优势。因此原先用 Critic 网络对 $q$ 函数的估计就可以改成对优势函数的估计，估算每个 $q(s_t,a_t)$ 对相对于平均值 $V(s_t)$ 的优势。这种算法就是 Advantage Actor Critic ，即 A2C。
注意到，A2C 在具体实现的时候需要同时估计 $q(s_t, a_t)$ 和 $v(s_t)$，估计一个价值函数已经会存在误差了，估计两个价值函数误差会更大。但是我们知道 $q(s_t, a_t)$ 和 $v(s_t)$ 之间是存在关系的，在具体采样时，有
\[q(s_t, a_t) = r_{t+1} + \gamma v(s_{t+1})\]此时我们发现，A2C 即前面介绍过的 VAC 算法，价值网络只用估计 $v(s_t)$ 的值就够了。
5. 参考文献
[1] 静静的喝酒. CSDN 策略梯度方法介绍——Value-Based强化学习方法 VS Policy-Based强化学习方法
[2] 静静的喝酒. CSDN 策略梯度方法介绍——策略梯度定理推导过程
[3] 静静的喝酒. 策略梯度方法介绍——蒙特卡洛策略梯度方法(REINFORCE)
[4] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction