理论基础

马尔可夫性

​ 深度强化学习算法的基础是问题具有马尔可夫性（无后效性），也就是问题得建模成 MDP。

​ 在离散状态空间中，只需要状态空间满足所有状态可达、不可约、非周期三个条件就可以推出马尔可夫性，在状态空间的随机游走一定会收敛到平稳分布。于是就可以将一整条 non-iid 的 trajectory $ \tau = (s_0, a_0, s_1, a_1, …, s_T, a_T)$ 拆分成 $ (s_t, a_t, r_t)$ 三元组，以构建 batch 传入模型中训练。

​ 基于马尔可夫性，可以通过稳态分布 $d^{\pi}(s)$ 将目标函数写为：

$$J(\pi)=\int_{\mathcal{S}} d^{\pi}(s) \mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty} \gamma^{t} R_{t+1}\right] d s$$

​ 上述目标函数和常用的略有不同，因为该函数比较研究，在值函数的基础上考虑了初始状态分布，在满足马尔可夫性的情况下，实际上只需要保证最大化值函数就行了（这也是后面目标函数的表示方法）。当不满足马尔可夫性时，前面的行为会影响到当前状态的行为选择，往往意味着环境状态转移的不稳定（当前状态下的行为选择需要考虑之前的一系列状态），难以使用值函数来作为优化目标（这种情况是否用序贯来做更好？）。

​ 同时，强化学习中的很多推导过程都是基于马尔可夫性的，比如 TD 方法、优化目标的简化表示，前者或许可以用蒙特卡洛等方法替代，后者则直接影响了策略梯度的推导，基于 policy 的一系列算法都需要针对这时遇到的具体问题重新推导梯度。

数学方法

对数梯度

​ 对于一个梯度，经常将它变成带 log 梯度的形式：

$$p_{\theta}(\tau) \nabla_{\theta} \log p_{\theta}(\tau)=p_{\theta}(\tau) \frac{\nabla_{\theta} p_{\theta}(\tau)}{p_{\theta}(\tau)}$$

策略采样

​ 强化学习中，采样指的是使用当前策略 $\theta$ 进行 N 轮决策，每轮得到一个 trajectory ，使用以下近似即可计算优化目标：

$$J(\theta)=E_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t} r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right] \approx \frac{1}{N} \sum_{i} \sum_{t} r\left(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}\right)$$

重要性采样

​ 当缺少某个已知分布的样本时，可以用另一个分布的样本来近似；或当样本的分布不方便使用时，可以用一个已知样本来近似这些样本所处的分布。这就是重要性采样，通常在解决 off-policy 中使用。

$$\begin{aligned} E_{x \sim p(x)}[f(x)] &=\int p(x) f(x) d x \\ &=\int \frac{q(x)}{q(x)} p(x) f(x) d x \\ &=\int q(x) \frac{p(x)}{q(x)} f(x) d x \\ &=E_{x \sim q(x)}\left[\frac{p(x)}{q(x)} f(x)\right] \end{aligned}$$

策略梯度

梯度推导

​ 强化学习在一个 trajectory $\tau$ 上的概率 $p_{\theta}(\tau)$ 可以写为：

$$p_{\theta}(\tau)=p_{\theta}\left(\mathbf{s}_{1}, \mathbf{a}_{1}, \ldots, \mathbf{s}_{T}, \mathbf{a}_{T}\right)=p\left(\mathbf{s}_{1}\right) \prod_{t=1}^{T} \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right) p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_{t}, \mathbf{a}_{t}\right)$$

​ 对其取 log 后求导，得到该 trajectory 的概率的对数梯度，只剩下 $\pi_\theta$ 相关项：

$$\nabla_{\theta} \log p_{\theta}(\tau) = \nabla_{\theta} \left[\log p\left(\mathbf{s}_{1}\right)+\sum_{t=1}^{T} \log \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)+\log p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_{t}, \mathbf{a}_{t}\right)\right] = \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)$$

​ 可得目标函数对策略的梯度：

$$\nabla_{\theta} J(\theta) = E_{\tau \sim p_{\theta}(\tau)}\left[ r(\tau) \right] = E_{\tau \sim p_{\theta}(\tau)}\left[ \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right) * r(\tau) \right] \\ = E_{\tau \sim p_{\theta}(\tau)}\left[\left(\sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)\right)\left(\sum_{t=1}^{T} r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right)\right] \\ \approx \frac{1}{N} \sum_{i=1}^{N}\left(\sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)\right)\left(\sum_{t=1}^{T} r\left(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}\right)\right)$$

​ 于是就可以通过 N 轮采样，将 reward 函数值与对应 trajectory 上的对数梯度相乘，得到目标函数关于策略的梯度值，就可以更新策略：

$$\theta \leftarrow \theta+\alpha \nabla_{\theta} J(\theta)$$

​ 当环境观测值 $o_{t}$ 只是状态 $s_{t}$ 的一部分时，上述梯度方程只需要将策略选择概率中的相应部分替换成 $o_{t}$ 即可，本质不会发生改变。

高斯策略

​ 对于离散型动作空间，神经网络拟合的是一个多项分布，即执行每种动作的概率。对于连续型动作空间，神经网络拟合的是概率密度函数，动作值服从该概率密度函数对应的分布，神经网络具体拟合的就是其中的主要参数。比较典型的就是用神经网络来拟合高斯分布的概率密度函数的均值 $\mu_\theta$ 和方差 $\sigma_\theta$ ：

$$\pi_\theta(a_t \mid s_t)=\frac{1}{\sqrt{2 \pi} \sigma_\theta(s_t)} \exp \left(-\frac{(a_t - \mu_\theta(s_t))^{2}}{2 \sigma_\theta^{2}(s_\theta)}\right)$$

​ CS 285 中给出的例子是简化版的高斯策略，神经网络仅对均值进行了拟合。实际计算中，只需要根据自己使用的概率密度函数来计算其对数值对策略的导数，然后带入目标函数的梯度表达式中，即可进行策略更新。一般在神经网络中，$\nabla_\theta \mu_\theta$ 和 $\nabla_\theta \sigma_\theta$ 相关项就是神经网络对应部分需要反向传递的梯度值。

方差问题

​ 根据 reward 函数的不同设计，哪怕只是 reward 函数中常数值大小的不同，相同环境下、相同模型训练出的 RL 算法会存在严重的方差。虽然在最后可能会收敛到相近的策略，但是其训练过程却千差万别，尤其在有限的训练过程中，可能不足以训练到接近收敛的状态，此时的模型可能会很差（我们希望的是离收敛状态较远时，也能在一定程度上反应收敛状态下的分布情况，但策略梯度算法的方差导致这是不可能的）。

​ 在现实中，要使用策略梯度算法就必须降低这种方差。

​ 首先，回顾策略梯度的目标，是为了根据一个行为导致的 reward 来
修改选择该行为的策略，基于因果性（causality）当前状态下选择的行为不会影响到以前的 reward。所以不妨将策略梯度公式略作修改，在 reward 的组合式中剔除其所对应的对数导数所在时刻之前的 reward 值，也就是在第 $t$ 个求和项中，仅对 $t \leq t' \leq T$ 的 reward 进行加总（$t$ 时刻状态-行为值函数的估计值），毕竟减少样本量的求和项就会减小方差：

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)\left(\sum_{t^{\prime}=t}^{T} r\left(\mathbf{s}_{i, t^{\prime}}, \mathbf{a}_{i, t^{\prime}}\right)\right)\\ = \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right) \hat{Q}_{i, t}$$

​ 然后，既然 reward 函数的常数项会导致方差的出现（reward 全正的情况下哪怕差的行为在训练不充分的时候也会被鼓励），不妨将 reward 函数进行中心化处理，令一个基准值为 0来标注其他的 reward 值，这样就能在完全不改变梯度的均值的情况下，显著降低其方差。这也称为基准值法（baseline） :

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \nabla_{\theta} \log p_{\theta}(\tau)[r(\tau)-b]$$

​ $b$ 的取值可以有很多种设计，最简单的就是 $b=\frac{1}{N} \sum_{i=1}^{N} r(\tau)$，虽然不是最优的但却是最实用的。通过对上式求方差，然后对方差求导，可以推导出最优的 $b$ 取值：

$$b = \frac{ E\left[g(\tau)^{2} r(\tau)\right]} {E\left[g(\tau)^{2}\right]}$$

​ 其中，g 代表梯度方程中的对数导数项。该最优取值需要针对梯度中的每一个维度单独设置对应的基准值，实际上还是用均值作为基准值更方便。毕竟使用均值作为 baseline，当梯度中的相关项用 Q 来表示时， b 也就是值函数 V，而 Q - b 也就是优势函数 A = Q - V。

off-policy 问题

​ 前面的策略梯度方程是 on-policy 的，意味着每改变一次策略，就需要重新采样出多组 trajectory，以算出当前策略下的梯度，这是非常低效的。于是就可以利用重要性采样来获得 off-policy 下的目标函数：

$$J(\theta)=E_{\tau \sim \bar{p}(\tau)}\left[\frac{p_{\theta}(\tau)}{\bar{p}(\tau)}(\tau)\right]$$

$$p_{\theta}(\tau)=p\left(\mathbf{s}_{1}\right) \prod_{t=1}^{T} \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right) p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_{t}, \mathbf{a}_{t}\right)$$

$$\frac{p_{\theta}(\tau)}{\bar{p}(\tau)}=\frac{\prod_{t=1}^{T} \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)}{\prod_{t=1}^{T} \bar{\pi}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)}$$

​ 这样就能使用旧的或来自其他渠道的经验数据来训练当前的 RL 算法。在已知策略 $\theta$ 的样本上进行策略 $\theta'$ 的重要性采样，然后对 $\theta'$ 求梯度可得：

$$\nabla_{\theta^{\prime}} J\left(\theta^{\prime}\right)=E_{\tau \sim p_{\theta}(\tau)}\left[\frac{\nabla_{\theta^{\prime}} p_{\theta^{\prime}}(\tau)}{p_{\theta}(\tau)} r(\tau)\right]=E_{\tau \sim p_{\theta}(\tau)}\left[\frac{p_{\theta^{\prime}}(\tau)}{p_{\theta}(\tau)} \nabla_{\theta^{\prime}} \log p_{\theta^{\prime}}(\tau) r(\tau)\right]\\ =E_{\tau \sim p_{\theta}(\tau)}\left[\left(\prod_{t=1}^{T} \frac{\pi_{\theta^{\prime}}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)}{\pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)}\right)\left(\sum_{t=1}^{T} \nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)\right)\left(\sum_{t=1}^{T} r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right)\right]\\ \approx E_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t=1}^{T} \nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)\left(\prod_{t^{\prime}=1}^{t} \frac{\pi_{\theta^{\prime}}\left(\mathbf{a}_{t^{\prime}} \mid \mathbf{s}_{t^{\prime}}\right)}{\pi_{\theta}\left(\mathbf{a}_{t^{\prime}} \mid \mathbf{s}_{t^{\prime}}\right)}\right)\left(\sum_{t^{\prime}=t}^{T} r\left(\mathbf{s}_{t^{\prime}}, \mathbf{a}_{t^{\prime}}\right)\left(\prod_{t^{\prime \prime}=t}^{t^{\prime}} \frac{\pi_{\theta^{\prime}}\left(\mathbf{a}_{t^{\prime \prime}} \mid \mathbf{s}_{t^{\prime \prime}}\right)}{\pi_{\theta}\left(\mathbf{a}_{t^{\prime \prime}} \mid \mathbf{s}_{t^{\prime \prime}}\right)}\right)\right)\right]$$

​ 上式中的最后一项是引入了对因果性考量的修改版本，因为未来的行为不会影响以前的结果，所以剔除了旧的 reward，同时因为重要性权重是与 reward 的时间尺度相关的，也对其进行了修改。上式比较复杂，其实可以省去最后一部分关于 reward 的重要性权重，仅保留对数梯度的权重，一样可以保证算法收敛性：

$$\nabla_{\theta^{\prime}} J\left(\theta^{\prime}\right) \approx E_{\tau \sim p_{\theta}(\tau)}\left[\sum_{t=1}^{T} \nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)\left(\prod_{t^{\prime}=1}^{t} \frac{\pi_{\theta^{\prime}}\left(\mathbf{a}_{t^{\prime}} \mid \mathbf{s}_{t^{\prime}}\right)}{\pi_{\theta}\left(\mathbf{a}_{t^{\prime}} \mid \mathbf{s}_{t^{\prime}}\right)}\right)\left(\sum_{t^{\prime}=t}^{T} r\left(\mathbf{s}_{t^{\prime}}, \mathbf{a}_{t^{\prime}}\right)\right)\right]$$

​ 但是注意到上面的重要性权重项，一旦其中的每一项都大于 1，该权重会以指数级的速度随着 T 的增加迅速膨胀，T 逼近无穷时该权重值也逼近无穷，显然需要找一种方法去换掉这一项。首先让重要性权重不再表示为整个 trajactory，而用 $(s_t, a_t)$ 的联合概率来描述，然后忽略关于状态的边缘概率，就能避免权重随 T 的增加指数爆炸的问题（在策略更新幅度不大时有意义）：

$$\nabla_{\theta^{\prime}} J\left(\theta^{\prime}\right) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \frac{\pi_{\theta^{\prime}}\left(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}\right)}{\pi_{\theta}\left(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}\right)} \nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right) \hat{Q}_{i, t}\\ =\frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \frac{\pi_{\theta^{\prime}}\left(\mathbf{s}_{i, t}\right)}{\pi_{\theta}\left(\mathbf{s}_{i, t}\right)} \frac{\pi_{\theta^{\prime}}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)}{\pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)} \nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right) \hat{Q}_{i, t}\\ \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \frac{\pi_{\theta^{\prime}}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)}{\pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)} \nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right) \hat{Q}_{i, t}$$

​ 至此，策略梯度解决了如何使用 off-policy 的问题，但是重要性采样自身也存在缺陷——当两个分布之间相差太大时，重要性采样结果的方差会很大，必须增加样本数量才能有比较好的效果。

​ 除了 off-policy 外，A3C 从多线程的角度解决了 on-policy 收敛速度过慢的问题。既然 on-policy 问题的原因是样本采集速度不够，不妨使用大量智能体在同一个环境下进行探索，它们的经验共同进行 on-policy 训练，就能弥补单次采样数据不足的问题。

下降方向问题

​ 策略梯度算法存在一个严重的下降步伐问题，即在梯度方向不同的分量上，单位下降步伐对优化目标的影响是不一样的。该问题和凸优化中的最速下降法如出一辙，都是因为只找当前迭代点最优的下降方向，而忽视了下降方向与目标点之间的偏离程度，整个下降轨迹可以看成蜿蜒曲折地到达最优点，走了很多弯路，最终会导致收敛速度非常缓慢。在 RL 中，上述问题又可以被表述为下降方向上的不同分量需要不同的更新步伐（learning rate），如果采用统一的更新步伐就会导致一部分分量还未搜索到最优策略的同时，另一部分分量已经越过最优策略。

​ 凸优化中有不少方法来解决这一下降方向问题（牛顿法、共轭空间法、信赖域方法），而策略梯度的主流解决方案就是其中的信赖域方法，也就是限制两次迭代点之间的距离（限制更新前后策略之间的差异）。最简单的限制更新距离，就是直接要求两个策略之间的欧几里得距离足够小：

$$\theta^{\prime} \leftarrow \arg \max _{\theta^{\prime}}\left(\theta^{\prime}-\theta\right)^{T} \nabla_{\theta} J(\theta) \quad s.t. \left\|\theta^{\prime}-\theta\right\|^{2} \leq \epsilon$$

​ 上述方法本质上并没有给不同分量设置不同的更新步伐，虽然效果不错但还可以继续改进。进一步地，可以使用散度来描述策略间的距离，比如最经典的 KL 散度，我们可以用 FIM （Fiser Information Matrix）去近似它：

$$\theta^{\prime} \leftarrow \arg \max _{\theta^{\prime}}\left(\theta^{\prime}-\theta\right)^{T} \nabla_{\theta} J(\theta) \text { s.t. } D\left(\pi_{\theta^{\prime}}, \pi_{\theta}\right) \leq \epsilon \\ D_{\mathrm{KL}}\left(\pi_{\theta^{\prime}} \| \pi_{\theta}\right)=E_{\pi_{\theta^{\prime}}}\left[\log \pi_{\theta}-\log \pi_{\theta^{\prime}}\right] \approx\left(\theta^{\prime}-\theta\right)^{T} \mathbf{F}\left(\theta^{\prime}-\theta\right)\\ \mathbf{F}=E_{\pi_{\theta}}\left[\nabla_{\theta} \log \pi_{\theta}(\mathbf{a} \mid \mathbf{s}) \nabla_{\theta} \log \pi_{\theta}(\mathbf{a} \mid \mathbf{s})^{T}\right]$$

重新整理更新方程，可以得到：

$$\theta \leftarrow \theta+\alpha \mathbf{F}^{-1} \nabla_{\theta} J(\theta)$$

这仅是对梯度下降法法修改的雏形，一些更先进的算法，比如 TRPO 和 PPO 其实都是在针对这一问题提出一些更加高效的解决方案。

方差和偏差之间的抉择

​ 前面使用一整个 trajectory 来计算策略梯度的方法也叫蒙特卡洛方法，其本质是通过状态行为值函数 Q 的一个样本来代替 Q（单一采样作为估计值），因此具有较大的方差（variance）：

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)\left(\sum_{t^{\prime}=1}^{T} r\left(\mathbf{s}_{i, t^{\prime}}, \mathbf{a}_{i, t^{\prime}}\right)-b\right)$$

​ 不妨直接维护一个对 Q 的估计函数，并通过它来构造优势函数（Advantage Function），不过可能因为估计的问题而引入偏差（bias）：

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right) A^{\pi}\left(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}\right)\\ Q^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)=\sum_{t^{\prime}=t}^{T} E_{\pi_{\theta}}\left[r\left(\mathbf{s}_{t^{\prime}}, \mathbf{a}_{t^{\prime}}\right) \mid \mathbf{s}_{t}, \mathbf{a}_{t}\right]\\ V^{\pi}\left(\mathbf{s}_{t}\right)=E_{\mathbf{a}_{t} \sim \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right)}\left[Q^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right]\\ A^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)=Q^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)-V^{\pi}\left(\mathbf{s}_{t}\right)$$

​ 总结，优势函数能够有效降低方差，但会引入偏差；直接使用 Q 值是无偏低，但不论蒙特卡罗还是 TD，我们实际上都是用的 Q 估计值进行梯度计算，这是有方差的。如果不使用 Q 值进行估计，并使用 V 的估计作为 baseline，那么则会得到一个无偏且方差很小的策略梯度算法。

​ 值得一提，实践中并不常用优势方程，直接在梯度中使用 Q 值即可，虽然方差会大点，但在 minibatch 下效果也是很好的，且是无偏低。

Bootstrap 自举

​ 在用训练一个值函数 V 的估计函数时，不妨用该估计函数在下一个状态的值加上当前的 reward 值来训练当前状态的估计函数：

$$y_{i, t} = r(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}) + \hat{V}_{\phi}^{\pi}(\mathbf{s}_{i, t+1})\\ \mathcal{L}(\phi)=\frac{1}{2} \sum_{i}\left\|\hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{i}\right)-y_{i}\right\|^{2}$$

​ 这种思想催生了 TD 算法，在训练上比蒙特卡洛更加高效，但同样可能因为拟合的问题出现一些偏差。

​ 之所以叫做自举，是因为会用到现有的 V 值去估计更新后的 V 值（y 中的第二项 V），这种用自己更新自己（或者说把自己变形成优化目标）的方法就是自举。

Actor-Critc

​ Actor 训练策略，Critic 拟合价值函数：on-policy 拟合 V，off-policy 拟合 Q。

​ 传统的做法是用样本拟合价值函数，然后用价值函数计算策略梯度，主要优势是降低了策略梯度的方差。DDPG 与 DQN 在此框架上将神经网络引入价值函数部分，并采用目标网络的方法进一步解决 off-policy 的问题。

discount factors

​ 基于越近的 reward 越好对观点，引入折现因子 $\gamma$ 对 long-term reward 进行折现。

​ 蒙特卡罗：

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N}\left(\sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)\right)\left(\sum_{t'=t}^{T} \gamma^{t'-t} r\left(\mathbf{s}_{i, t^{\prime}}, \mathbf{a}_{i, t^{\prime}}\right)\right)$$

​ 注意这里的 log 项没有折现因子，这是实际中更加常用的一种，因为这样得到的梯度能够保障之后的每一步都尽可能地优，若加上梯度则智能体将重点关注前几步的结果。

​ Critic：

$$\nabla_{\theta} J(\theta) \approx \frac{1}{N} \sum_{i=1}^{N} \sum_{t=1}^{T} \nabla_{\theta} \log \pi_{\theta}\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right)\left(r\left(\mathbf{s}_{i, t}, \mathbf{a}_{i, t}\right)+\gamma \hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{i, t+1}\right)-\hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{i, t}\right)\right)$$

经验池的 off-policy

​ 使用经验数据很明显会有 off-policy 问题，传统的做法是重要性采样，但 Actor-Critc 算法可以用其他方法解决该问题。

​ 首先，off-policy 的影响在于经验数据使用的都是旧策略选择的 action，用这些数据更新 V 值不靠谱（s -> r 取决于环境与策略）。但是 Q 值的更新并不考虑策略（s, a -> r 取决于环境），自举中 Q(s’, a’) 的 action 可以用当前策略采样，所以采用基于 Q 的算法能够在 Actor 中解决 off-policy 问题。换而言之，基于 Q 的贝尔曼方程并不关心 action 是如何选择的。其次，在梯度表达式中的 action 也用同样的思路从当前策略中采样得到，并且不再使用优势函数，而是直接使用 Q 来计算梯度。总而言之，这种做法只用到了经验中的 s’ 与 r 来更新 Q 值，并用 Q 和经验的 s 计算梯度。

​ 但这仍然是有偏差的，因为 s 的分布（稳态概率）是来自旧策略的，不过这只相当于在一个更加宽广的分布中找到了最优策略（强化学习的目标可以看作在 $p_\theta(s)$ 下找最优策略）。并且，用 Q 替换 V 会导致 Crtic 结果偏大的问题，体现在 DQN 和 DDPG 中是 Critic 网络输出的 Q 值总是比真实值大，这是因为 Q-Learning 存在最大值偏差问题，本质是因为样本最大值的期望大于等于期望的最大值（Double Q 是最经典的解决方法）。

​ 更新对 Actor-Critic 算法框架如下：

​ 在此基础上，DDPG 引入了目标网络，以解决 Critic 网络自举时的稳定性问题。更进一步，TD3 中用双 Critic 取最小值缓解了 Q 值高估问题（仅在目标网络中求最小），并让 Actor 延迟于 Critic 更新，避免因 Critic 不稳定导致 Actor 浪费算力。TD3 还在更新 Critic 时对目标 Q(s’, a’) 的 action 加上小扰动，在统计意义上将目标 Q 变成了其邻域内的均值，增加了网络的健壮性，让预估结果更精准。

资格迹

​ 蒙特卡罗无偏但方差大（因为单一采样作为估计），TD 方差小但偏差大（因为 V 的估计值不准确，r + V 项引入偏差），二者的关系可以用下图表示：

​ 蒙特卡罗是一条很长的单线，TD 是就近多根线的平均，于是就有了折衷的 n-step returns：

$$\hat{A}_{n}^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)=\sum_{t^{\prime}=t}^{t+n} \gamma^{t^{\prime}-t} r\left(\mathbf{s}_{t^{\prime}}, \mathbf{a}_{t^{\prime}}\right)-\hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{t}\right)+\gamma^{n} \hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{t+n}\right)$$

$$\hat{A}_{\mathrm{GAE}}^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)=\sum_{n=1}^{\infty} w_{n} \hat{A}_{n}^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right) \\ w_{n} \propto \lambda^{n-1}$$

​ 进一步写成：

$$\hat{A}_{\mathrm{GAE}}^{\pi}\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)=\sum_{t^{\prime}=t}^{\infty}(\gamma \lambda)^{t^{\prime}-t} \delta_{t^{\prime}} \\ \delta_{t^{\prime}}=r\left(\mathbf{s}_{t^{\prime}}, \mathbf{a}_{t^{\prime}}\right)+\gamma \hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{t^{\prime}+1}\right)-\hat{V}_{\phi}^{\pi}\left(\mathbf{s}_{t^{\prime}}\right)$$

值函数

​ 值函数是一种典型的确定性算法，以概率 1 采取 Q 值最大的行为作为策略，本质上选取最大 Q 就是在选取最大的优势函数。

值迭代

​ 策略迭代有策略估计与策略提升两个步骤，改为基于 Q 的确定性策略后，直接可以忽略策略提升（毕竟最大 Q 就是策略），这就是值迭代。不论策略迭代还是值迭代，其本质都是在估计+提升，估计始终使用贝尔曼方程，不过值迭代估计的是 Q，并且不需要显式地进行提升过程。