DQN 原理解析

发表于 2023-10-01 分类于人工智能，文章精读阅读次数：本文字数： 5.8k 阅读时长 ≈ 19 分钟

本篇博客是对 DQN 原始论文 Playing Atari with Deep Reinforcement Learning 的详细解读。

背景

在强化学习（RL）领域，直接从高维的原始输入（例如图像和声音）中学习以控制代理（agents）是一个比较大的挑战。大部分成功的 RL 算法都依赖于人工提取的特征结合线性的值函数或策略表示，因此系统的表现很大程度上取决于特征提取的质量。近年来，深度学习（DL）的发展使得我们可以直接从复杂的原始输入中捕获特征，而无需手工提取。然而，深度学习和强化学习又存在着一些差别，导致难以直接将深度神经网络应用于 RL：

DL 通常基于大量的人工标注训练数据进行训练，而 RL 则是基于可能存在延时的奖励进行学习，很难通过标准的网络结构将输入直接与奖励进行关联
大部分 DL 算法都假定数据样本之间相互独立，而 RL 则一般应用于高度相关的状态序列
在 RL 中当算法学习到新的行为后，数据分布可能发生改变，而 DL 通常假设数据分布是不变的

这篇论文提出了一种卷积神经网络（CNN）以解决上述挑战，在复杂的 RL 环境中直接通过视频数据生成控制策略。该网络基于 Q-learning 算法的变种进行训练，通过随机梯度下降来更新权重。为了缓解数据相关性以及分布的不稳定性，作者使用了一种经验回放机制（experience replay mechanism）来随机采样之前的状态转移，以平滑训练数据的分布。

该方法被用于多款 Atari 2600 游戏的训练，其输入为 60Hz 的 \(210\times160\) RGB 视频流。原文旨在通过单个网络来学习尽可能多的游戏，即不提供游戏特定的信息以及手工设计的特征，使用完全和人类玩家同等的视频信号、动作集以及奖励来训练代理，且网络的结构与超参数在训练不同的游戏时保持不变。结果表明，该网络在总共七款游戏中有六款的表现超越了之前的 RL 算法，且在其中三款中击败了专业的人类玩家。下图展示了用于训练的五款游戏的截图。

理论基础

在本研究中，代理基于一系列的动作、观察与奖励和环境 \(\mathcal{E}\) （即 Atari 模拟器）进行交互。在每一个时间步，代理从合法的游戏动作集 \(\mathcal{A}=\{1, \ldots, K\}\) 中选择一个动作 \(a_t\)，模拟器接收到该动作并修改其内在状态，反映到游戏得分上。一般情况下，环境 \(\mathcal{E}\) 可能是随机生成的，代理无法观察到模拟器的内部状态，只能观察到来自模拟器的图像 \(x_{t} \in \mathbb{R}^{d}\)，其是一个表示当前屏幕的原始像素值向量。此外，代理接收到一个奖励 \(r_t\) 表示游戏得分的变化。一般情况下，游戏得分可能依赖于整个先前的动作与观察序列，一个动作的反馈可能在很多时间步之后才会体现。

由于代理只能观测到当前屏幕的图像，无法获取模拟器的内部状态，即该任务是部分观测的，因此我们考虑基于当前时间 \(t\) 前的整个动作与观察序列 \(s_t = x_1, a_1, x_2, \ldots, a_{t-1}, x_t\) 来学习策略。模拟器中的所有序列都假定可以在有限时间步内终止。基于上述假设，我们可以将整个过程理解为一个有限马尔可夫决策过程（MDP），其中每个时间点对应的序列为一个状态 \(s_t\)，这样就将原始任务转化为一个可以使用标准强化学习算法的 MDP 场景。

代理的目标是通过与模拟器的交互来选择动作，使得未来的奖励最大化。这里假定未来奖励会随着时间步而衰减，衰减因子为 \(\gamma\)，则在 \(t\) 时刻未来的奖励和为： \[ R_{t}=\sum_{t^{\prime}=t}^{T} \gamma^{t^{\prime}-t} r_{t^{\prime}} \] 我们定义最优动作-价值函数 \(Q^{*}(s, a)\) 为在观测到某个序列 \(s\) 并执行动作 \(a\) 后，通过后续的任意策略所能达到的奖励最大期望： \[ Q^{*}(s, a)=\max _{\pi} \mathbb{E}\left[R_{t} \mid s_{t}=s, a_{t}=a, \pi\right] \] 其中 \(\pi\) 是一个策略，将状态（这里指序列）映射为动作（或动作的分布）。最优动作-价值函数满足贝尔曼等式： \[ Q^{*}(s, a)=\mathbb{E}_{s^{\prime} \sim \mathcal{E}}\left[r+\gamma \max _{a^{\prime}} Q^{*}\left(s^{\prime}, a^{\prime}\right) \mid s, a\right] \tag{1} \] 即目标期望由即时奖励和下一个时间步的折扣奖励的最大期望组成。很多强化学习算法的基本思想即使用贝尔曼等式进行迭代更新来估计动作-价值函数，直到收敛至最优值。在实践中，这种基于值迭代的方法并不好用，因为动作-价值函数是针对每个序列分别计算的，不具有推广性，难以应对复杂情况（如状态连续）。一种常用的解决方法是使用一个函数近似器来估计动作-价值函数： \[ Q(s, a ; \theta) \approx Q^{*}(s, a) \] 在强化学习社区一般使用线性函数近似器，有时也可以使用诸如神经网络的非线性近似。本研究中使用了一个权重为 \(\theta\) 的神经网络函数近似器，称为 Q-网络。Q-网络通过在每一次迭代 \(i\) 最小化损失函数 \(L_{i}\left(\theta_{i}\right)\) 进行训练： \[ L_{i}\left(\theta_{i}\right)=\mathbb{E}_{s, a \sim \rho(\cdot)}\left[\left(y_{i}-Q\left(s, a ; \theta_{i}\right)\right)^{2}\right] \tag{2} \] 其中 \(y_{i}=\mathbb{E}_{s^{\prime} \sim \mathcal{E}}\left[r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} ; \theta_{i-1}\right) \mid s, a\right]\) 为当前迭代 \(i\) 的目标，\(\rho(s, a)\) 是一个关于序列 \(s\) 和动作 \(a\) 的概率分布，我们称之为行为分布（behaviour distribution）。来自上一次迭代的参数 \(\theta_{i-1}\) 在优化损失函数 \(L_{i}\left(\theta_{i}\right)\) 时保持不变，用于计算当前迭代下的最优价值函数。注意在 Q-网络中目标值是依赖于网络权重的，而普通监督学习中目标值（标签）通常是在学习开始前确定好的。将损失函数关于权重求导可得到如下梯度： \[ \nabla_{\theta_{i}} L_{i}\left(\theta_{i}\right)=\mathbb{E}_{s, a \sim \rho(\cdot) ; s^{\prime} \sim \mathcal{E}}\left[\left(r+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime} ; \theta_{i-1}\right)-Q\left(s, a ; \theta_{i}\right)\right) \nabla_{\theta_{i}} Q\left(s, a ; \theta_{i}\right)\right] \tag{3} \] 相比较直接计算上述梯度中的期望，为了计算效率我们可以通过随机梯度下降来优化损失函数。每次分别基于行为分布 \(\rho\) 和模拟器 \(\mathcal{E}\) 采样单个样本作为期望，用来更新权重（注意在实际算法中为基于经验回放的小批量更新）。这种做法类似于经典的 Q-learning 算法。

本研究提出的方法是 model-free 的，即直接基于来自模拟器 \(\mathcal{E}\) 的样本执行学习任务，并不需要对 \(\mathcal{E}\) 进行精细地估计（建模）。本方法同样是 off-policy 的，每次迭代时基于贪婪法 \(a=\max _{a} Q(s, a ; \theta)\) （注意这里实际上用的应该是 \(\theta_{i-1}\)，因为还没有进行梯度更新）生成样本进行学习（该策略与上一步进行梯度下降时的最优策略并不相同，因为参数被更新了），通过行为分布来保证对状态空间的有效探索。在实践中，行为分布通常基于 \(\epsilon\) 贪婪法得到：以 \(1-\epsilon\) 的概率遵循贪婪法，以 \(\epsilon\) 的概率选择一个随机动作。

深度强化学习

算法解读

与之前的类似方法相比，本研究使用了一种称为经验回放（experience replay）的技术，将代理在每一个时间步的体验 \(e_{t}=\left(s_{t}, a_{t}, r_{t}, s_{t+1}\right)\) 存放在数据集 \(\mathcal{D}=e_{1}, \ldots, e_{N}\) 中，通过多个回合积累为一个回放记忆（replay memory）。在算法的内循环中，我们将 Q-learning 更新应用于从存储的记忆中随机采样的小批量经验样本 \(e \sim \mathcal{D}\)。在执行完经验回放后，代理循 \(\epsilon\) 贪婪策略选择并执行一个动作。由于标准神经网络难以处理不定长的输入，所以本研究通过一个函数 \(\phi\) 先将序列状态映射为一个固定长度的表示，再作为 Q-函数的输入。完整的算法称为深度 Q-learning，如下图所示：

算法的详细步骤为：首先初始化容量为 \(N\) 的回放记忆 \(\mathcal{D}\) ，以及随机权重的动作价值函数 \(Q\)；然后执行回合迭代（外循环，共 \(M\) 个回合），在每个回合中，先初始化序列 \(s_1 = \{x_1\}\)，并将其预处理为定长 \(\phi_1 = \phi(s_1)\)；再执行时间步迭代（内循环，共 \(T\) 步），在每一步中，先基于 \(\epsilon\) 策略选择动作 \(a_t\)（随机动作或当前最优动作），然后在模拟器中执行 \(a_t\) 观察奖励 \(r_t\) 和图像 \(x_{t+1}\)；设置 \(s_{t+1}=s_{t}, a_{t}, x_{t+1}\) 并执行预处理 \(\phi_{t+1} = \phi(s_{t+1})\)；将当前时间步中得到的转移 \(\left(\phi_{t}, a_{t}, r_{t}, \phi_{t+1}\right)\) 存储到 \(\mathcal{D}\) 中；基于 \(\mathcal{D}\) 随机采样小批量的转移 \(\left(\phi_{j}, a_{j}, r_{j}, \phi_{j+1}\right)\)；根据 \(\phi_{j+1}\) 是否为终止状态，设置 \(y_i\) 为： \[ y_{j}=\left\{\begin{array}{ll} r_{j} & \text { for terminal } \phi_{j+1} \\ r_{j}+\gamma \max _{a^{\prime}} Q\left(\phi_{j+1}, a^{\prime} ; \theta\right) & \text { for non-terminal } \phi_{j+1} \end{array}\right. \] 根据 \((3)\) 式基于损失函数 \(\left(y_{j}-Q\left(\phi_{j}, a_{j} ; \theta\right)\right)^{2}\) 执行梯度下降，更新网络参数。执行上述过程直到达到收敛条件或循环结束。

与标准 Q-learning 相比，本研究提出的方法具有如下几点优势：首先，每一步中获得的经验都可能用于多次权重更新，这样可以提升数据的利用率；其次，由于样本间的强相关性，直接从连续样本中学习是低效的。随机化样本可以打破这种相关性，减少更新的方差；最后，对于 on-policy 式的学习来说，当前的参数决定了下一次训练所需的数据样本，由于执行当前动作后训练的分布会发生变化，因此延用当前策略可能会导致局部最优、参数发散等异常情况的发生；经验回放机制基于多个先前的状态对行为分布进行平均，可以平滑学习过程，避免参数的振荡和发散。同时由于使用了经验回放，梯度更新时的参数（状态）和用于生成样本的参数（状态）并不相同，因此自然需要使用类似 Q-learning 的 off-policy 方法。

在实践中，本算法只在回放记忆中存储最近的 \(N\) 次回放，在执行更新时从 \(\mathcal{D}\) 中均匀采样。这种方式存在着一定的局限性，因为其没有区分出比较重要的转移，只是单纯地用最近产生的转移覆盖之前的转移（受存储空间 \(N\) 的限制）。类似地，均匀采样也为回放记忆中的所有转移赋予了同等的重要性。在之后的研究中，可以对采样方法进行改进，关注能够学习到更多东西的转移。

预处理和模型结构

原始的 Atari 图像为 \(210 \times 160\) 像素，每个像素可选颜色为 128 种。为了减小计算复杂度，本文加入了一个简单的预处理步骤以减少输入的维度。原始图像首先被转化为灰度图像，然后降采样为 \(110\times84\) 像素大小。最后由于本研究使用的 2D 卷积 GPU 实现要求输入为正方形，所以再将图像裁剪为 \(84 \times 84\) 大小，作为最终的输入表示。在本研究的试验中，算法中函数 \(\phi\) 将一个状态序列的最后 4 帧进行上述预处理，并堆叠在一起作为 Q-函数的输入。

关于网络的结构，之前的一些研究将历史状态和动作一起作为网络的输入，这种结构的缺点在于对每一个动作都需要单独进行一次前向传播。本研究中使用的网络结构对于每个可能的动作都提供一个单独的输出（因此动作不能连续），只有状态被作为网络的输入。网络的输出对应输入状态的每一个可能动作的预测 Q 值。这种结构的优点在于其能够仅通过一次前向传播就计算出一个给定状态的所有可能动作的 Q 值。网络的整体结构如下图所示（图片来自另一篇论文）：

上述结构对于所有七款游戏都相同，神经网络的输入为 \(\phi\) 映射的 \(84 \times 84 \times 4\) 的图像，第一层隐藏层为卷积层，包含 16 个 \(8 \times 8\) 的卷积核，步长为 4，激活函数为 ReLU，对应输出为 \(20 \times 20 \times 16\)；第二层隐藏层也为卷积层，包含 32 个 \(4 \times 4\) 的卷积核，步长为 2，激活函数为 ReLU，对应输出为 \(9 \times 9 \times 32\)；最后一层隐藏层为全连接层，包含 256 个整流单元，输出为 \(256 \times 1\)；最终输出层同样为全连接层，输出一个包含每个合法动作 Q 值的向量。参与实验的游戏的合法动作数量为 4 到 18 个不等。本文中使用的卷积神经网络被称为深度 Q 网络（DQN）。

实验

原文的实验共涉及七款游戏，分别是 Beam Rider、Breakout、Enduro、Pong、Q*bert、Seaquest 和 Space Invaders。如之前所述，为了证明模型的鲁棒性，所有游戏使用相同的网络结构、学习算法和超参数设置。与真实游戏反馈相比，实验的唯一不同在于对游戏的奖励进行了修改。由于不同游戏的实际奖励得分差异较大，为了便于训练，将所有的正向奖励置为 1，负向奖励置为 -1，不变则为 0。这种裁剪可以帮助减少训练误差，让不同的游戏可以使用相同的学习率，提升最终的表现。

实验中使用的具体算法和超参数设置如下：

学习率调整：RMSProp 算法
小批量大小： 32
\(\epsilon\) 策略：前 1,000,000 帧画面中 \(\epsilon\) 线性地从 1 到 0.1 下降；之后保持 0.1（测试时使用 0.05）
训练总时长：10,000,000 帧画面
回放记忆：最近的 1,000,000 帧画面

此外，实验中还使用了一个简单的 frame-skipping 技巧。代理只会在每 \(k\) 帧进行观察并选择动作，而不是每一帧，在跳过的帧中重复最近一次选择的动作。由于简单运行模拟器比控制代理选择动作的计算量小很多，所以这一技术可以帮助代理在不显著增加运行时间的前提下玩更多次的游戏。原文中，对于除 Space Invaders 之外的游戏设置了 \(k=4\)，由于该游戏设置为 4 会导致激光无法识别，所以设置 \(k=3\)。

训练和稳定性

在监督学习中，我们可以通过模型在训练集和验证集上的表现对其进行评估。然而在强化学习中，在训练中并没有一个很好的评估标准。本研究首先计算了不同训练回合下代理所获得的总奖励，但发现总奖励的变化趋势波动较大，这可能是因为一个策略权重的微小改变会导致策略所访问状态分布的较大变化。下图中左边两张给出了在两个不同游戏中的平均总奖励随训练回合的变化（平均是指分游戏统计），展示效果不是很理想。第二种评估方式则是基于策略的动作价值函数 Q，其估计了代理在遵循当前策略下所能得到的未来折扣奖励。实践证明该指标要比第一种更加稳定。具体来说，首先在训练开始前执行随机策略，采集一个固定的状态集合，然后跟踪不同训练回合时这些状态对应的最大预测 Q 值（从所有可能的动作中选）的平均值。下图中右边两张展示了平均预测 Q 值的平滑上升趋势，其他五个游戏也展示了类似的平滑曲线，在训练过程中也没有出现任何不收敛的问题。虽然缺乏理论证明，但是本文提出的方法能够使用强化学习信号和随机梯度下降来训练大型的神经网络，并保证收敛。

价值函数可视化

下图给出了在游戏 Seaquest 中学习到的价值函数的可视化展示，三个点分别对应右边的三张画面。可以看到当一个新敌人（绿色的鱼）出现在屏幕中时，预测的价值明显上升（点 A）；而当鱼雷快要攻击到敌人时，价值进一步上升达到峰值（点 B）；当敌人消失后，价值则快速下降至原来的水平。该图表明本文提出的方法能够学习到价值函数如何在复杂的事件序列中进行演变。

主要评估

在本节中，作者首先将 DQN 和之前的一些 RL 方法进行了对比，如下表的前五行所示。表中的数值为以 \(\epsilon\) 策略执行固定步骤后的平均总奖励（执行多个回合取平均）。除去随机策略和人工玩家，共对比了两种方法：Sarsa 和 Contingency。这两种方法都在手工提取特征的同时，将画面中的不同颜色进行分离并标注。人工玩家的奖励为玩游戏两小时后获得的奖励的中位数。下表的后三行比较了 DQN 和两种进化策略搜索方法：HNeat Best 和 HNeat Pixel。HNeat Best 基于人工标注的目标检测算法，输出屏幕上物体的类型和位置；HNeat Pixel 则使用 8 个特别的颜色表示 Atari 游戏中的特定物体类型。这两种方法依赖于找到一个确定的状态序列，不会存在随机扰动，因此对比的是单个回合下的最佳表现。

总的来看，我们的方法在 Breakout、Enduro 和 Pong 这三款游戏上击败了人类玩家；在 Beam Rider 上和人类玩家表现接近。而差距较大的三款游戏需要网络基于更长的时间范围寻找策略，因此挑战性更大。

结论

本文可以说是将深度学习应用于强化学习领域的开山之作，其在 Atari 2600 游戏上展示了深度学习仅基于原始图像即能够掌握复杂控制策略的能力。本研究提出的方法也可以理解为一种在线 Q-learning 的变种，融合了随机小批量更新和经验回放以便于深度网络的训练。在无需额外调整结构和超参数的前提下，本方法在七款游戏中的六款达到了 SOTA 的结果。

后记：在 Human-level control through deep reinforcement learning 中，作者对本文中的算法进行了改进，创建了另一个 Q-网络，其参数只会定期更新，并不会参与完整的迭代。这种方式可以缓解 Q-值的不稳定问题，在 49 个 Atari 游戏中取得了比本文更好的效果。

背景