Deep RL Algorithms

这一节重点介绍几个深度强化学习中非常经典的算法：DQN、Double DQN、A3C 和 PPO。

从整体脉络上看，这几个算法分别代表了几条重要路线：

算法	类型	核心思想
DQN	value-based	用神经网络近似 $Q(s,a)$
Double DQN	value-based	降低 DQN 中 max 带来的 Q 值过估计
A3C	actor-critic	多个 worker 异步采样并更新全局网络
PPO	policy-based / actor-critic	用 clipped objective 稳定更新策略

DQN

在 tabular Q-learning 中，我们可以直接维护一个表 $Q(s,a)$。但是当状态空间非常大，比如 Atari 图像输入时，表格方法就不可行了。

DQN 的核心思想是使用神经网络来近似 Q function：

$$ Q(s,a;\theta) \approx Q^*(s,a) $$

网络输入状态 $s$，输出每个动作的 Q 值：

$$ Q(s,\cdot;\theta) = [Q(s,a_1;\theta), Q(s,a_2;\theta), \dots, Q(s,a_n;\theta)] $$

DQN 的 target 来自 Q-learning：

$$ y = r + \gamma \max_{a'} \textcolor{red}{Q(s',a';\theta^-)} $$

需要注意的就是标红的部分，这里的 $\theta^-$ 是 Target 的网络的参数，从而做到了把优化目标与当前网络解耦

$$ \begin{aligned} \mathcal{L}(\theta) &= \mathbb{E}_{(s,a,r,s')\sim \mathcal{D}} \left[ \left( \textcolor{red}{y} - Q(s,a;\theta) \right)^2 \right] \end{aligned} $$

DQN 算法流程

初始化 online Q 网络 Q(s,a;theta)
初始化 target Q 网络 Q(s,a;theta-) = Q(s,a;theta)
初始化 replay buffer D

for each step:
    用 epsilon-greedy 根据 Q(s,a;theta) 选择动作 a
    与环境交互得到 (s, a, r, s', done)
    将 transition 存入 replay buffer D

    从 D 中随机采样一个 batch
    计算 target:
        y = r + gamma max_a' Q(s',a';theta-)
    最小化:
        (y - Q(s,a;theta))^2
    每隔 C 步:
        theta- <- theta

Experience Replay 的作用

DQN 的一个关键设计是记忆回放，也就是 replay buffer。

在普通在线学习中，样本是按照时间顺序到来的：

(s_1,a_1,r_1,s_2), (s_2,a_2,r_2,s_3), (s_3,a_3,r_3,s_4), ...

这些样本之间强相关。如果直接用连续样本训练神经网络，容易出现两个问题：

样本不满足独立同分布，梯度方向容易震荡
新样本会快速覆盖旧样本，导致学习不稳定

Replay buffer 的做法是把 transition 存起来，然后随机采样 mini-batch：

$$ (s,a,r,s') \sim \textcolor{blue}{\mathcal{D}_{replay}} $$

这样做的作用可以总结为：

作用	解释
打破样本相关性	随机采样让一个 batch 中的样本来自不同时间
提高样本利用率	同一条 transition 可以被训练多次
稳定训练分布	buffer 中同时包含新旧经验，减少策略变化带来的分布突变

所以记忆回放并不是简单地“存数据”，它实际是在把 RL 中高度相关的在线数据，变成更接近 supervised learning 的训练数据。

没有 Target Network 会怎么样

如果不用 target network，DQN 的 target 会变成

$$ y = r + \gamma \max_{a'} Q(s',a';\theta) $$

这里有一个问题：我们一边用 $Q(s,a;\theta)$ 做预测，一边又用同一个网络构造 target。也就是说，目标本身也在快速移动。

这会导致训练过程像是在追一个不断变化的目标，比如前一轮刚学习的 Target 是 10，结果更新后同样的输入网络的 Target 变成了 13，这就很抽象了。

DQN 的两个稳定化技巧

记忆回放解决的是样本相关性和样本利用率问题；target network 解决的是目标函数自身不稳定的问题。

没有 replay buffer，训练数据太相关；没有 target network，Bellman target 太不稳定。

Double DQN

先明确一个概念， Target DQN 并不是 Double DQN，Double DQN 是一个新东西（这个概念我搞混了一整年…）

现在我们已经知道了 Target DQN，那么它还存在什么问题呢？

答案

Target 网络负责的工作太多了，它既负责估计 Q 的值，又负责选择动作。也就是说，Target 网络既参与了 action selection，又参与了 action evaluation。 $$ y = r + \gamma \textcolor{red}{\max_{a'} Q(s',a';\theta^-)} $$

如果每个动作的 Q 估计都有噪声，那么取最大值时更容易选到“因为噪声而偏高”的动作。因此

$$ \mathbb{E}[\max_a \hat{Q}(s,a)] \geq \max_a Q(s,a) $$

Double DQN 的核心思想是把 action selection 和 action evaluation 分开。先用 online network 选动作：

$$ a^* = \arg\max_{a'} Q(s',a';\textcolor{blue}{\theta}) $$

再用 target network 评估这个动作：

$$ y^{DoubleDQN} = r + \gamma Q(s', a^*;\textcolor{red}{\theta^-}) $$

合起来写就是

$$ \begin{aligned} y^{DoubleDQN} &= r + \gamma Q \left( s', \arg\max_{a'} Q(s',a';\textcolor{blue}{\theta}); \textcolor{red}{\theta^-} \right) \end{aligned} $$

Double DQN 算法流程

从 replay buffer 中采样 (s, a, r, s', done)

用 online network 选择 next action:
    a* = argmax_a' Q(s', a'; theta)

用 target network 评估这个 action:
    y = r + gamma Q(s', a*; theta-)

最小化:
    (y - Q(s,a;theta))^2

Double DQN 的改动非常小，但是它减少了 DQN 中 max 操作导致的过估计问题，通常会让 value estimate 更稳。

A3C

A3C 的全称是 Asynchronous Advantage Actor-Critic。

它的结构可以拆成三部分：

名称	含义
Actor	策略网络 $\pi_\theta(a\\|s)$，负责选择动作
Critic	值函数 $V_\omega(s)$，负责评估状态
Asynchronous	多个 worker 并行和不同环境交互，异步更新全局网络

Actor 的目标来自 policy gradient：

$$ \begin{aligned} \nabla_\theta J(\theta) &= \mathbb{E} \left[ \nabla_\theta \log \pi_\theta(a_t|s_t) \textcolor{blue}{A_t} \right] \end{aligned} $$

其中 advantage 表示当前动作比平均水平好多少：

$$ A_t = Q(s_t,a_t) - V(s_t) $$

在 A3C 中常用 n-step return 估计 $Q(s_t,a_t)$：

$$ \begin{aligned} R_t &= r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1}r_{t+n-1} \quad{}+ \gamma^n V(s_{t+n}) \end{aligned} $$

因此 advantage 可以写成

$$ A_t = R_t - V(s_t) $$

Critic 的损失函数是

$$ \mathcal{L}_{critic} = \left(R_t - V_\omega(s_t)\right)^2 $$

Actor 的损失函数常写成

$$ \begin{aligned} \mathcal{L}_{actor} &= -\log \pi_\theta(a_t|s_t) \textcolor{red}{(R_t - V_\omega(s_t))} \end{aligned} $$

为了鼓励探索，还会加入 entropy bonus：避免策略快速收敛到局部最优解，SAC 和它的想法很接近

$$ \begin{aligned} \mathcal{L} &= \mathcal{L}_{actor} \quad{}+ c_v \mathcal{L}_{critic} \quad{}- c_e H(\pi_\theta(\cdot|s_t)) \end{aligned} $$

A3C 算法流程

初始化全局 Actor-Critic 网络
启动多个 worker，每个 worker 有自己的环境副本

每个 worker repeat:
    从全局网络复制参数
    和环境交互 n 步，得到一段 trajectory
    计算 n-step return R_t
    计算 advantage A_t = R_t - V(s_t)
    计算 actor loss 和 critic loss
    将梯度异步更新到全局网络

A3C 的关键点是多个 worker 会探索不同的状态区域，这在一定程度上替代了 replay buffer 的 decorrelation 效果。不同 worker 采到的数据相关性更低，因此训练更稳定。

PPO

在介绍 PPO 之前，先回到 policy gradient 的一个基本问题：我们通常用当前策略 $\pi_\theta$ 采样轨迹，然后用这些轨迹来更新当前策略。

最直接的流程是

用当前策略 pi_theta 采样 trajectory
用这批 trajectory 更新一次策略
丢掉旧数据
再用新策略重新采样

这样做比较符合 on-policy 的设定，但是样本利用率很低。因为环境交互通常是最贵的部分，而每一批 trajectory 只被用来更新一次。

为什么要引入重要性采样

如果我们希望复用旧策略采样得到的数据，就会遇到一个分布不一致的问题。

假设轨迹是由旧策略 $\pi_{\theta_{old}}$ 采样的，但是我们希望优化新策略 $\pi_\theta$。原始 policy gradient 的目标里期望分布应该来自当前策略：

$$ \begin{aligned} J(\theta) &= \mathbb{E}_{\tau \sim \pi_\theta} \left[ R(\tau) \right] \end{aligned} $$

但是手上的数据来自旧策略：

$$ \tau \sim \pi_{\theta_{old}} $$

这时候可以用重要性采样修正分布差异。对于单步 actor-critic 形式，可以写成

$$ \begin{aligned} \mathbb{E}_{a_t \sim \pi_\theta} \left[ A_t \right] &= \mathbb{E}_{a_t \sim \pi_{\theta_{old}}} \left[ \frac{\pi_\theta(a_t|s_t)} {\pi_{\theta_{old}}(a_t|s_t)} A_t \right] \end{aligned} $$

其中

$$ r_t(\theta) = \frac{\pi_\theta(a_t|s_t)} {\pi_{\theta_{old}}(a_t|s_t)} $$

叫做 importance sampling ratio

所以引入重要性采样以后，策略优化目标可以写成

$$ \begin{aligned} \mathcal{L}^{PG}(\theta) &= \mathbb{E}_t \left[ \textcolor{blue}{r_t(\theta)} A_t \right] \end{aligned} $$

这里 $r_t(\theta)$ 的含义很直观：

$r_t(\theta) > 1$：新策略比旧策略更倾向于选择这个动作
$r_t(\theta) < 1$：新策略降低了这个动作的概率
$r_t(\theta) \approx 1$：新旧策略变化不大

有了这个 ratio，同一批旧策略采样的数据就不再只能用一次。我们可以固定 $\pi_{\theta_{old}}$，然后对同一批 trajectory 做多轮 mini-batch 更新。

重要性采样带来的问题

重要性采样虽然让复用旧数据成为可能，但它也带来一个新的问题：如果新旧策略差距太大，ratio 会非常大或者非常小。

比如当 $r_t(\theta) \gg 1$

并且 $A_t > 0$ 时，目标项 $\textcolor{red}{r_t(\theta) A_t}$ 会变得很大，导致策略朝某个方向更新过猛。

反过来，当 $A_t < 0$ 且 $r_t(\theta)$ 变化过大时，策略也可能过度降低某个动作的概率。

因此，单纯使用重要性采样会出现一个核心风险：

$$ \textcolor{green}{\text{策略变化越大，ratio 越不稳定，更新幅度也越不可控}} $$

这也是为什么 policy optimization 不能只考虑“让目标函数变大”，还必须限制每次策略更新的幅度。

TRPO

TRPO 的目标就是解决上面这个问题：既然策略变化太大会让更新不可靠，那就明确限制新策略不能离旧策略太远。

TRPO 最大化的 surrogate objective 是

$$ \max_\theta \mathbb{E}_t \left[ \frac{\pi_\theta(a_t|s_t)} {\pi_{\theta_{old}}(a_t|s_t)} A_t \right] $$

也就是

$$ \max_\theta \mathbb{E}_t \left[ r_t(\theta) A_t \right] $$

但是它额外加入 KL 约束：

$$ \mathbb{E}_t \left[ D_{KL} ( \pi_{\theta_{old}}(\cdot|s_t) \| \pi_\theta(\cdot|s_t) ) \right] \leq \delta $$

这个约束的作用是把新策略限制在旧策略附近。可以理解为：

$$ \text{maximize policy improvement} \quad \textcolor{red}{\text{subject to small policy change}} $$

这就是 trust region 的含义。TRPO 的优点是更新稳定，因为它显式限制 KL divergence，避免策略一步跨太远。

但是 TRPO 在工程上并不方便：

需要处理带约束优化问题
通常要用 conjugate gradient 等近似二阶方法
需要估计 Fisher-vector product
实现复杂，和普通 mini-batch SGD / Adam 的训练方式不够统一

所以 TRPO 的思想很好，但是工程成本偏高。

PPO-Clip

PPO 的目标是保留 TRPO 的核心思想：限制策略更新幅度。但是 PPO 不再显式求解 KL 约束优化，而是直接在目标函数里对 ratio 做裁剪。

PPO clipped objective 写成

$$ \begin{aligned} \mathcal{L}^{CLIP}(\theta) &= \mathbb{E}_t \left[ \min \left( \textcolor{blue}{r_t(\theta) A_t}, \textcolor{red}{\text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) A_t} \right) \right] \end{aligned} $$

其中

$$ \text{clip}(r_t(\theta), 1-\epsilon, 1+\epsilon) $$

会把 ratio 限制在

$$ 1-\epsilon \leq r_t(\theta) \leq 1+\epsilon $$

这个 clip 的直觉是：如果新策略已经比旧策略变化太多，就不再继续给它额外收益。

当 $A_t > 0$ 时，动作比预期更好，我们希望提高它的概率。但是如果

$$ r_t(\theta) > 1+\epsilon $$

说明这个动作概率已经被提高太多了，clip 会截断这个收益。

当 $A_t < 0$ 时，动作比预期更差，我们希望降低它的概率。但是如果

$$ r_t(\theta) < 1-\epsilon $$

说明这个动作概率已经被降低太多了，clip 同样会阻止继续过度更新。

所以 PPO-Clip 可以看作：

$$ \text{TRPO 的 trust region 思想} \quad{}+ \textcolor{red}{\text{clip 限制更新幅度}} $$

PPO 为什么能提高样本利用率

PPO 的样本利用率来自两个设计：

使用重要性采样 ratio，让旧策略采样的数据可以用于新策略更新
使用 clip 限制 ratio 的变化，让同一批数据可以被安全地训练多轮

实际训练时通常是

用旧策略 pi_theta_old 采样一批 trajectory
计算 return 和 advantage A_t

for epoch in K:
    将这批 trajectory 切成多个 mini-batch
    对每个 mini-batch:
        计算 ratio r_t(theta)
        计算 clipped policy objective
        计算 value loss
        计算 entropy bonus
        用 Adam 更新参数

更新 theta_old <- theta
重新采样下一批 trajectory

如果没有 ratio，同一批旧数据无法直接当作当前策略的数据来用；如果没有 clip，多轮更新后 $\pi_\theta$ 会离 $\pi_{\theta_{old}}$ 越来越远，重要性采样的方差会变大，更新会变得不可靠。

因此 PPO 提高样本利用率的关键不是“无限复用旧数据”，而是在一个有限范围内复用：

$$ \textcolor{blue}{\text{reuse old trajectories}} \quad \text{but} \quad \textcolor{blue}{\text{keep the policy close to the old policy}} $$

这也是为什么 PPO 仍然是 on-policy 算法。它可以对一批 trajectory 做多个 epoch 的 mini-batch 更新，但当策略已经变化太多时，这批数据就应该丢弃，然后重新采样。

PPO 完整损失

PPO 实际训练时通常包含三部分：

$$ \begin{aligned} \mathcal{L}^{PPO} &= \mathcal{L}^{CLIP} \quad{}- c_1 \mathcal{L}^{VF} \quad{}+ c_2 H(\pi_\theta) \end{aligned} $$

其中 value loss 是

$$ \mathcal{L}^{VF} = \left(V_\theta(s_t)-R_t\right)^2 $$

entropy bonus $H(\pi_\theta)$ 用来鼓励探索

TRPO 到 PPO 的优势

TRPO 和 PPO 解决的是同一个问题：策略不能一次更新太大。但是它们的实现方式不同：

对比项	TRPO	PPO
限制策略变化	显式 KL 约束	clip ratio
优化方式	约束优化 + 近似二阶方法	普通一阶梯度下降
工程实现	复杂	简单
mini-batch 多轮训练	不自然	很自然
样本复用	有限制	通过多 epoch 更直接
核心直觉	解一个 trust region 问题	用裁剪近似 trust region

所以这条思路可以总结为：

重要性采样:
    让旧策略采样的数据可以被新策略复用

问题:
    新旧策略差距大时 ratio 不稳定，更新幅度可能过大

TRPO:
    用 KL 约束显式限制新旧策略距离
    但是工程实现复杂

PPO:
    用 clip(ratio, 1-epsilon, 1+epsilon) 近似限制策略更新
    保留稳定性，同时更容易实现和调参

小结

这一节的几个算法可以串起来理解：

DQN:
    用神经网络近似 Q function
    replay buffer + target network 稳定训练

Double DQN:
    将 action selection 和 action evaluation 分开
    缓解 Q 值过估计

A3C:
    Actor-Critic + 多 worker 异步采样
    用 advantage 降低 policy gradient 方差

PPO:
    用 clipped objective 限制策略更新幅度
    用多轮 mini-batch 更新提高样本利用率

如果只看核心问题：

算法	主要解决的问题
DQN	大状态空间下如何学习 Q function
Double DQN	DQN 中 max 操作导致的过估计
A3C	policy gradient 方差大、采样相关性强
PPO	策略更新过大导致训练崩溃，同时提升 on-policy 数据利用率

DQN#

DQN 算法流程#

Experience Replay 的作用#

没有 Target Network 会怎么样#

Double DQN#

Double DQN 算法流程#

A3C#

A3C 算法流程#

PPO#

为什么要引入重要性采样#

重要性采样带来的问题#

TRPO#

PPO-Clip#

PPO 为什么能提高样本利用率#

PPO 完整损失#

TRPO 到 PPO 的优势#

小结#

DQN