深度强化学习前沿算法总结，从Markov决策过程下的经典算法值迭代和策略迭代出发，进而推导出DQN、DDPG、 Policy Gradient、A3C、PPO、DPO。

整理自 UCB CS285, instrusted by Sergey Levine.

RL with Simulators

考虑一个经典的表格设定下的Markov Decision Process (MDP)，由五个元素组成：分别为状态空间 $\mathcal{S}$, 动作空间 $\mathcal{A}$, horizon $T$, 转移概率矩阵 $P(s’ | s,a)$, 以及回报函数 $R(s,a)$. 强化学习的目标是寻找到一个策略 $\pi$, 使得从这个策略中采样的轨迹 $\tau = (s_1,a_1,r_1\cdots, s_T,a_T,r_T)$ 可以最大化如下的期望累积折扣回报:

其中折扣参数 $\gamma \in (0,1)$ 衡量了当下与未来回报的权衡。

转移概率矩阵 $P(s’| s,a)$ 已知的时候 （也称为可以访问模拟器的设定）， 并且动作、状态都为有限的离散值的时候，这个MDP存在着精确求解的算法，即下面所介绍的值迭代 (Value Iteration) 以及策略迭代 (Policy Iteration) 两个经典算法。

Value Iteration

我们定义如下的值函数以及Q函数，分别表示从状态 $s$ 开始，执行策略 $\pi$ 得到的期望总回报:

以及从状态 $s$ 出发，执行动作 $a$, 然后执行策略 $\pi$ 所得到的期望总回报:

对于最优的策略 $\pi^\ast$, 我们相应地将其对应的值函数以及Q函数记作为 $V^\ast$ 以及 $Q^\ast$. 我们知道事实上最优的值函数以及最优策略可以由 $Q^\ast$ 决定：

并且我们证明最优值函数以及Q函数分别满足如下的贝尔曼方程 (Bellman Equation):

根据上面的关系式，值迭代不断地运行如下算法流程：

可以证明，将值函数 $V$ 堪称一个向量，上述迭代过程相当于对于一个收缩算子进行不动点迭代，因此上述迭代总是收敛的。

Policy Iteration

值迭代的每一步需要枚举所有的 $(s,a,a’)$ 元组，因此每次迭代复杂度为 $\mathcal{O}( |\mathcal{S}|^2 |\mathcal{A}| )$. 下面我们介绍称为策略迭代的算法，交替地执行策略评估以及策略改进，其中策略评估的单次迭代复杂度可以将为 $\mathcal{O}(|\mathcal{S}|^2)$，在实际中可能具有更好地效果。

对于给定的确定性策略 $\pi$, 我们知道成立关系式 $V^\pi(s,a) = Q^\pi(s,\pi(s))$, 相应的贝尔曼方程为：

上述方程由于策略是给定的，并不需要取max操作，只是一个简单的线性方程，也可以通过在V值上进行简单的不动点迭代求解，而每次迭代的复杂度仅仅需要 $\mathcal{O}(|\mathcal{S}|^2)$. 由于线性方程的求解技术非常成熟，策略评估在实际上可能只需要很低的代价。如果采用不动点迭代， 对于策略 $\pi^k$, 迭代式子为:

得到策略 $\pi$ 的值函数以及 Q-函数后，可以根据Q-函数进行策略改进：

如果策略改进后价值函数不变，那么说明算法收敛，已经找到了最优策略。反之，可以证明新的策略 $\pi^{k+1}$ 一定严格由于旧的策略 $\pi^k$。由于总策略空间为 $|\mathcal{A}|^{|\mathcal{S}|}$, 我们知道整个算法一定会在有限步收敛。

有意思的是，可以看到值迭代算法实际上是策略迭代算法中的策略评估只进行一步的特例。

RL without Simulators

在本节我们关注于转移概率未知的情况，这也是强化学习中的一个核心设定。此时智能体需要在与环境的交互过程中获得样本，并且根据已有的样本来改进策略。

VI $\rightarrow$ DQN

回顾值迭代基于如下的贝尔曼方程进行不动点迭代：

但是在没有模拟器，也成为无模型 (Model-Free) 的设定中， 我们并不能直接遍历所有的 $a \in \mathcal{A}$ 然后返回 $r(s,a)$, 因此上述值迭代难以直接运行。但幸运的是，我们可以从如下等价的关于 Q函数的方程中得到一个在无模型设定下更容易运行的算法：

在Deep Q Network (DQN) 中，使用一个神经网络对Q函数进行拟合，记作为 $Q_\theta(s,a)$. 而上面期望 $\mathbb{E}_{s’ \sim p(s’|s,a)}$ 的求解我们使用采样的方式估计，这里与值迭代和策略迭代出现一个本质区别：我们并不能直接选择当前Q函数下最优的策略 $\pi^\ast(s) = \arg \max_{a \in \mathcal{A}} Q_\theta(s,a)$, 因此这样子算法会仅仅利用 (exploit) 已经遇到过的动作，而没有遇到过的动作Q函数的估计量为0，因此我们需要对环境进行探索 (explore). 一个经验上可以比较好平衡探索与利用的简单策略是定义如下的 $\epsilon$-贪婪策略: 以概率 $1-\epsilon$ 选择 $\pi^\epsilon(s) = \arg \max_{a \in \mathcal{A}} Q_\theta(s,a)$, 而以概率 $\epsilon$ 随机选择 $\mathcal{A}$ 中的动作.

随着迭代的进行 $\epsilon$ 的值应当越来越小，最终当Q函数的估计收敛，策略也收敛到贪婪策略。对于网络参数 $\theta$ 的更新，我们在贝尔曼方程残差的平方损失下进行梯度下降，不断改进Q函数的估计:

该算法中用来采样的策略是 $\pi^\epsilon$, 但是目标函数的更新使用的是 $\max_{a \in \mathcal{A}} Q_{\theta}(s,a))$, 事实上是用贪婪策略得到了，因此采样和用来优化更新的策略并不一致，这样的算法成为异策略 (off-policy) 算法。这样的异策略算法由于并不要求采样策略与更新策略一致，通常实际中由于可以反复利用已有的样本来提升效率。基于此DQN也采用了经验池回放的思想，维护用过去的经验构成的经验池 $\mathcal{D}$，每次随机从经验池中抽取四元组样本 $(s,a,r,s’) \in \mathcal{D}$ 进行训练：

上述回归问题如果回归目标项 $r(s,a) + \gamma \max_{a’ \in \mathcal{A}} Q_\theta(s’,a’)$ 一直在变化，很容易导致训练不稳定的现象。实际中一个解决方法是冻结这个目标，使用一个用Polyak平均更新的平滑的网络 $\theta’_{k+1} = \tau \theta’_k + (1-\tau) \theta_{k+1}$. 然后把目标函数变为

然后，上述估计仍然有一个缺点。 根据关系式 $\mathbb{E} \max(X_1,X_2) \ge \max(\mathbb{E}X_1, \mathbb{E}X_2)$, 由于我们对 Q函数的估计事实上也是一个随机变量，因此上述迭代很容易造成Q函数高估的问题。Double DQN 提出如下的改进：通过另一个Q函数，把选择动作以及评估动作的策略进行解耦，可以减轻高估Q函数的问题。一个巧妙之处在于为了减低成本，实际并不构造一个新的Q函数，而是直接使用$\theta’$ 对应的Q函数。修正后的目标函数为:

DQN $\rightarrow$ DDPG

DQN 在离散动作空间中取得了很大的成功，但是由于需要枚举所有的动作选择最优，并不能直接适用于连续动作空间。本小节我们将介绍s适用于连续动作的 Deep Deterministic Policy Gradient (DDPG) 算法。DDPG的思想是：虽然不能直接选贪婪策略，我们可以使用一个神经网络拟合这个贪婪策略，记作为 $\mu_\phi(s)$. 网络训练的目标应当使得该策略接近于Q函数的最大值，因此只需要对于Q函数使用梯度上升就可以得到一个这样的近似策略。而有个这个近似策略 $\mu_\phi$ 之后，将他用来替换原来Q函数更新中的显式argmax操作，就可以得到一个可执行的算法，核心更新如下:

其中对于参数 $\theta$ 和 $\phi$ 与DQN的改进相同，分别维护一个Polyak平均版本$\theta’$ 和 $\phi’$，用来计算更稳定的冻结目标 $r(s,a) + \gamma Q_{\theta_k’}(s’,\mu_{\phi_k’}(s’) )$. 类似地，上面介绍的DQN的很多改进策略自然也适用于DDPG。Twin Delayed DDPG (TD3) 算法将这些技巧进行尝试，并且用对于实验效果最为关键的两个技术进行命名：其中 twin 来自于double DQN，用两个Q函数来减缓Q函数高估的问题。具体来说，TD3将Q函数的更新目标设置为

而第二个技巧 delay 说的是用来评估Q函数的参数 $\theta$ 以及用来执行动作的参数 $\phi$ 不要使用相同的更新频率。对于参数 $\phi$ 使用延迟的更新技巧，这样可以在 Q函数更新地更为准确的前提下执行动作。

Policy Gradient $\rightarrow$ A3C

DDPG中参数 $\theta$ 和 $\phi$ 其实扮演者评论家和演员的角色。本节将介绍一个基于这个思想的算法，称为演员-评论家 (Actor-Critic). 主要区别在于评论家的不同计算方式。DDPG依赖于假设策略 $\mu_\phi(s)$ 是一个确定性的函数，这很可能限制了其表达能力，我们可能希望学习到一个随机的策略，可以优于确定性的策略。

使用随机策略的核心困难在于如何进行求导，这需要依赖于如下的策略梯度的引理. 定义 $p_\phi(\tau)$ 为以 $\phi$ 为参数的策略采样出轨迹 $\tau = (s_1,a_1,r_1\cdots, s_T,a_T,r_T)$ 的概率分布，我们希望寻找最优的参数 $\phi$ 使得

策略梯度引理推导的是上述目标函数的一个无偏梯度估计, 使用恒等式 $\nabla_\phi \log z =\frac{1}{z} \nabla_\phi z$, 我们可以得到

这可以看成一个用回报加权的交叉熵损失的梯度。由于对于轨迹的概率有 $p_\phi(\tau) = p(s_0) \prod_{t=0}^{T-1}p(a_t|s_t) p(s_{t+1}| s_t,a_t)$, 我们可以知道上式可以展开为

进一步利用关系式 $G(\tau) = G(\tau_{0:t}) + \gamma^t G(\tau_{t:T})$ 将累积回报分解兵器注意到时刻 $t$ 之前的回报和时刻 $t$ 之后的动作无关，我们进一步得到化简后的式子为

采用上述梯度直接对参数 $\phi$ 进行梯度上升的策略就是策略梯度方法 (Policy Gradient). 该方法的一个实际弊端是上述估计量需要对所有horizon进行求和，会导致一个非常大的方差。REINFORCE算法通过将估计的总回报值减去一个基线的方式来减小方差，在每个时刻 $t$ 下的策略梯度为

通过简单的计算，可以发现只要基线 $b(s_t)$ 与 $a_t$ 无关的话，将策略梯度改变为如下的形式仍然可以得到一个无偏估计

回顾值函数以及Q函数的定义，我们知道 $\mathbb{E}[G(\tau_{t:T}) | s_t,a_t] = Q(s_t,a_t)$，并且可以想到值函数本身就是一个自然的基线。据此，我们定义策略 $\phi$ 诱导的优势函数为

我们希望使用优势函数代替策略梯度中的 $G_{\tau:T}$, 这将得到 Advantage Actor-Critic (A2C) 算法。注意到为了避免拟合 $Q$ 函数以及值函数两个网络的复杂度，A2C 中使用关系式 $Q_\phi(s,a) := \mathbb{E}_{s’ \sim p(s’ |s,a)}[r(s,a) + \gamma V_\phi(s’)]$ 来使得算法只依赖值函数对应的网络。最终得到的算法如下, 对于每次迭代 $k$ 以及每个时刻 $t$, 进行如下更新

A3C (Asynchronous Advantage Actor-Critic) 进一步加入分布式算法的思想，在多个并行的环境里面异步使用A2C算法，来提升算法效率。

A3C $\rightarrow$ PPO

A3C 使用异步的方式提升效率，但基于之前DQN以及DDPG的经验，我们知道一个更本质的方法是直接使用异策略算法，在一个经验池中进行多次更新。因此，我们希望将演员-评论家算法修改为异策略算法，给定采样策略 $\pi_{\phi’}$ 对策略 $\pi_\phi$ 进行更新。

注意到评论家只需要评估采样策略 $\pi_{\phi’}$ 的优势函数，因此不需要进行改动。需要改动的方面为演员的策略更新，这可以通过重要性采样实现。可以证明如下的恒等式成立

为了重要性采样会有比较好的效果，我们希望策略 $\phi$ 以及 $\phi’$ 尽可能接近，这可以通过约束两个分布之间的KL散度来实现。在每一步更新过程中，我们试图求解如下约束优化问题:

满足该约束的时候两个策略将很接近，因此 $p_\phi(s_t) \approx p_{\phi’}(s_t)$, 那么根据概率分解式 $p(s_t,a_t) = p(s_t) p (a_t | s_t)$, 我们知道 $p_{\phi}(s_t,a_t)/p_{\phi’}(s_t,a_t) \approx p_{\phi}(a_t|s_t)/p_{\phi’}(a_t|s_t)$, 这也简化了计算, 使得

TRPO (Trust Region Policy Optimization) 利用共轭梯度法实现求逆的自然梯度方法来近似求解上述硬约束问题，但该算法由于较为复杂实际并不常用。现在实际训练中更广泛采用的算法称为PPO (Proximal Policy Optimization), 该算法求解如下的Lagrange问题:

这样的软约束优化问题可以使用梯度下降类型的算法进行求解，并且实际通常效果也相对理想。

PPO的另一个启发式（但实际也经常被使用）的版本直接使用如下的代理损失函数：

上式的含义是，当优势函数 $A_{\phi’}(s_t,a_t)$ 为正值的时候，梯度方向会鼓励 $p_\phi(a_t \vert s_t)$ 增大，但为了稳定性，我们限制增大的幅度不能超过 $p_{\phi’}(a_t \vert s_t)$ 的 $1+\epsilon$ 倍。而当 $A_{\phi’}(s_t,a_t)$ 为负值的时候，梯度方向会鼓励 $p_\phi(a_t \vert s_t)$ 减小，但我们限制其不能超过 $p_{\phi’}(a _t \vert s_t)$ 的 $1-\epsilon$ 倍。

PPO $\rightarrow$ DPO

本节我们特别考虑RLHF (Reinforcement Learning with Human Feedbacks) 的设定。记 $\phi$ 与 $\theta$ 分别为希望优化的策略模型以及回报模型参数，给定一个提示词 $x$, 以及大语言模型 $\phi$ 生成的样本对 $(y_+,y_-) \sim p_\phi(y|x)$. 注意到这里 $y_+$ 表示两者中更符合人类偏好的一个，而$y_-$则是更不符合的另一个。

给定一个由上述这样的正负样本对所生成的数据集$\mathcal{D}$，我们希望训练得到一个模型可以提供一个回报函数 $r_\theta(x,y)$ 可以尽可能地分开正样本和负样本。将其视作一个二元分类问题，令 $\sigma(\,\cdot\,)$ 为logistic 函数，我们定义关于模型 $\theta$ 的损失为

我们希望最小化上述损失函数得到一个好的回报模型。而对于策略模型，我们希望他所生成的样本应当尽可能最大化回报函数，但是与SFT过程中所得到的基础模型 $\theta_{\rm ref}$ 不应该有太多偏离。我们希望 $\phi$ 能优化如下的强化学习问题：

通过求导并且令其为0，可以发现最优的策略模型 $\phi$ 应当满足

因此，在这个模型下， $\phi$ 和 $\theta$ 实际上存在着上面的对应关系，我们用 $\phi$ 来表示 $r_\theta(x,y)$, 得到

其中 $C>0$ 是一个常数。代入关于模型 $\theta$ 的损失，得到最优的回报模型，关于 $\phi$ 需要求解

这就得到了 DPO (Direct Policay Optimization). 通过上述的变换，DPO去掉了PPO中的reward model以及value model，实现上更为简单。