强化学习（十三）DQN

传统的强化学习算法会使用表格的形式存储状态价值函数 $V(s)$ 或动作价值函数 $Q(s)$ ，但是这样的方法存在很大的局限性。例如，现实中的强化学习任务所面临的状态空间往往是连续的，存在无穷多个状态，在这种情况下，就不能再使用表格对价值函数进行存储。价值函数近似利用函数直接拟合状态价值函数或动作价值函数，降低了对存储空间的要求，有效地解决了这个问题。

为了在连续的状态和动作空间中计算值函数 $Q_{\pi }(s,a)$，我们可以用一个函数 $Q_{\varphi }(s,a)$ 来表示近似计算，称为价值函数近似（value function approximation）。

$$Q_{\varphi }(s,a)\approx Q_{\pi }(s,a)$$

其中，$s,a$ 分别是状态 $s$ 和动作 $a$ 的向量表示，函数 $Q_{\varphi }(s,a)$ 通常是一个参数为 $\varphi$ 的函数，比如神经网络，其输出为一个实数，称为 Q 网络（Q-network）。

深度Q网络（deep Q-network，DQN）是指基于深度学习的Q学习算法，主要结合了价值函数近似与神经网络技术，并采用目标网络和经历回放的方法进行网络的训练。在 Q学习 中，我们使用表格来存储每个状态 $s$ 下采取动作 $a$ 获得的奖励，即状态-动作值函数 $Q(s,a)$。然而，这种方法在状态量巨大甚至是连续的任务中，会遇到维度灾难问题，往往是不可行的。因此，深度Q网络 采用了价值函数近似的表示方法。

1. 状态价值函数

深度Q网络 是基于价值的算法，在基于价值的算法里面，我们学习的不是策略，而是评论员（critic）。评论员的任务是评价现在的动作有多好或有多不好。假设有一个演员，其要学习一个策略来得到尽量高的回报。评论员就是评价演员的策略 $\pi$ 好还是不好，即策略评估。例如，有一种评论员称为状态价值函数 $V_{\pi }$。状态价值函数是指，假设演员的策略是 $\pi$，用 $\pi$ 与环境交互，假设 $\pi$ 看到了某一个状态 $s$，例如在玩雅达利游戏，状态 $s$ 是某一个画面，$\pi$ 看到某一个画面，接下来一直到游戏结束，期望的累积奖励有多大。如下图 (a) 所示，$V_{\pi }$是一个函数，输入一个状态，它会输出一个标量。这个标量代表演员的策略 $\pi$ 看到状态 $s$ 的时候，预期到游戏结束的时候，它可以获得多大的奖励。例如，假设我们在玩太空侵略者，图 (b) 所示的状态 $s$，这个游戏画面，$V_{\pi }(s)$ 也许会很大，因为这时还有很多的怪兽可以击杀， 所以我们会得到很高的分数。一直到游戏结束的时候，我们仍然有很多的分数可以获得。图 © 所示的情况我们得到的 $V_{\pi }(s)$ 可能就很小，因为剩下的怪兽也不多，并且红色的防护罩已经消失了，所以我们可能很快就会“死掉”。因此接下来得到预期的奖励，就不会太大。

这里需要强调，评论员无法凭空评价一个状态的好坏，它所评价的是在给定某一个状态的时候，如果接下来交互的演员的策略是 $\pi$，我们会得到多少奖励，这个奖励就是我们评价得出的值。因为就算是同样的状态，接下来的 $\pi$ 不一样，得到的奖励也是不一样的。例如，在左边的情况下，假设是一个正常的 $\pi$，它可以击杀很多怪兽；假设它是一个很弱的 $\pi$，它就站在原地不动，马上就被射死了，我们得到的 $V_{\pi }(s)$ 还是很小。所以评论员的输出值取决于状态和演员。评论员其实都要绑定一个演员，它是在衡量某一个演员的好坏，而不是衡量一个状态的好坏。这里要强调一下，评论员的输出是与演员有关的，状态的价值其实取决于演员，当演员改变的时候，状态价值函数的输出其实也是会跟着改变的。

怎么衡量状态价值函数 $V_{\pi }(s)$ 呢？有两种不同的方法：基于蒙特卡洛的方法和基于时序差分的方法。基于蒙特卡洛的方法就是让演员与环境交互，我们要看演员好不好，就让演员与环境交互，让评论员评价。评论员就统计，演员如果看到状态 $s_a$，接下来的累积奖励有多大；如果它看到状态 $s_b$，接下来的累积奖励有多大。但是实际上，我们不可能看到所有的状态。如果我们在玩雅达利游戏，状态是图像，那么无法看到所有的状态。所以实际上 $V_{\pi }(s)$ 是一个网络。对一个网络来说，就算输入状态是从来都没有看过的，它也可以想办法估测一个值。怎么训练这个网络呢？如下图所示，如果在状态 $s_a$，接下来的累积奖励就是 $G_a$。也就是对这个价值函数，如果输入是状态 $s_a$，正确的输出应该是 $G_a$；如果输入状态是 $s_b$，正确的输出应该是 $G_b$。所以在训练的时候， 它就是一个回归问题（regression problem）。网络的输出就是一个值，我们希望在输入 $s_a$ 的时候，输出的值与 $G_a$ 越接近越好；输入 $s_b$ 的时候，输出的值与 $G_b$ 越接近越好。接下来继续训练网络，这是基于蒙特卡洛的方法。

第二个方法是时序差分的方法，即基于时序差分的方法。在基于蒙特卡洛的方法中，每次我们都要计算累积奖励，也就是从某一个状态 $s_a$ 一直到游戏结束的时候，得到的所有奖励的总和。如果我们要使用基于蒙特卡洛的方法，我们必须至少玩到游戏结束。但有些游戏时间非常长，我们要玩到游戏结束才能够更新网络，这花的时间太多了，因此我们会采用基于时序差分的方法。基于时序差分的方法不需要玩到游戏结束，只需要在游戏的某一个状态 $s_t$ 的时候，采取动作 $a_t$ 得到奖励 $r_t$，接下来进入状态 $s_{t+1}$，就可以使用时序差分的方法。我们可以通过式(1)来使用时序差分的方法。

$$\begin{array}{c}{V}_{\pi }(s_t)=V_{\pi }(s_{t+1})+r_t\end{array}$$

假设我们现在用的是某一个策略 $\pi$，在状态 $s_t$ 时，它会采取动作 $a_t$，得到奖励 $r_t$，接下来进入 $s_{t+1}$ 。状态 $s_{t+1}$ 的值与状态 $s_t$ 的值，它们的中间差了一项 $r_t$，这是因为我们把 $s_{t+1}$ 的值加上得到的奖励 $r_t$ 就可以 得到 $s_t$ 的值。有了式(1)，在训练的时候，我们并不是直接估测 $V_{\pi }$，而是希望得到的结果 $V_{\pi }$ 可以满足式(1)。我们是这样训练的，如图3 所示，我们把 $s_t$ 输入网络，因为把 $s_t$ 输入网络会得到 $V_{\pi }(s_t)$，把 $s_{t+1}$ 输入网络会得到 $V_{\pi }(s_{t+1})$， $V_{\pi }(s_t)$ 减 $V_{\pi }(s_{t+1})$ 的值应该是 $r_t$。我们希望它们相减的损失与 $r_t$ 接近，训练下去，更新 $V_{\pi }$ 的参数，我们就可以把 $V_{\pi }$ 函数学习出来了。

蒙特卡洛方法与时序差分方法有什么差别呢？如图4 所示，蒙特卡洛方法最大的问题就是方差很大。因为我们在玩游戏的时候，游戏本身是有随机性的，所以我们可以把 $G_a$ 看成一个随机变量。因为我们每次到 $s_a$ 的时候，最后得到的 $G_a$ 其实是不一样的。我们看到同样的状态 $s_a$，最后到游戏结束的时候，因为游戏本身是有随机性的，玩游戏的模型可能也有随机性，所以我们每次得到的 $G_a$ 是不一样的，每一次得到的 $G_a$ 的差别其实会很大。为什么会很大呢？因为 $G_a$ 是很多个不同的步骤的奖励的和。假设我们每一个步骤都会得到一个奖励，$G_a$ 是从状态 $s_a$开始一直到游戏结束，每一个步骤的奖励的和。

通过式(2)，我们知道 $G_a$ 的方差相较于某一个状态的奖励，它是比较大的。

$$\begin{array}{c}Var[kX]=k^{2}Var[X]\end{array}$$

其中，Var 是指方差（variance）。

如果用时序差分的方法，我们要去最小化

$$\begin{array}{c}{V}_{\pi }(s_t)\leftrightarrow r+V_{\pi }(s_{t+1})\end{array}$$

其中，$r$ 具有随机性。因为即使我们在 $s_t$ 采取同一个动作，得到的奖励也不一定是一样的，所以 $r$ 是一个随机变量。但 $r$ 的方差比 $G_a$ 要小，因为 $G_a$ 是很多 $r$ 的加和，时序差分只是某一个 $r$ 而已。$G_a$ 的方差会比较大，$r$ 的方差会比较小。但是这里我们会遇到的一个问题是 $V_{\pi }$ 的估计不一定准确。假设 $V_{\pi }$ 的估计不准确，我们使用式(3)学习出来的结果也会是不准确的。所以蒙特卡洛方法与时序差分方法各有优劣。其实时序差分方法是比较常用的，蒙特卡洛方法其实是比较少用的。

图5 所示为时序差分方法与蒙特卡洛方法的差别。假设有某一个评论员，它去观察某一个策略 $\pi$ 与环境交互 8 个回合的结果。有一个策略 $\pi$ 与环境交互了8 次，得到了 8 次玩游戏的结果。接下来这个评论员去估测状态的值。

我们先计算 $s_b$ 的值。 状态 $s_b$ 在 8 场游戏里都存在，其中有 6 场得到奖励 1，有 2 场得到奖励 0。所以如果我们要计算期望值，只算智能体看到状态 $s_b$ 以后得到的奖励。智能体一直玩到游戏结束的时候得到的累积奖励期望值是 3/4，计算过程为

$$\frac{6\times 1+2\times 0}{8}=\frac{6}{8}=\frac{3}{4}$$

但 $s_a$ 期望的奖励到底应该是多少呢？这里其实有两个可能的答案：0 和 3/4。为什么有两个可能的答案呢？这取决于我们用蒙特卡洛方法还是时序差分方法。用 蒙特卡洛方法与用 时序差分方法 算出来的结果是不一样的。

假如我们用蒙特卡洛方法，$s_a$ 就出现一次，看到状态 $s_a$ ，接下来累积奖励就是 0，所以 $s_a$ 期望奖励就是 0。但时序差分方法在计算的时候，需要更新：

$$V_{\pi }(s_a)=V_{\pi }(s_b)+r$$

因为我们在状态 $s_a$ 得到奖励 $r=0$ 以后，进入状态 $s_b$，所以状态 $s_a$ 的奖励等于状态 $s_b$ 的奖励加上从状态 $s_a$ 进入状态 $s_b$ 的时候可能得到的奖励 $r$。而得到的奖励 $r$ 的值是 0，$s_b$ 期望奖励是 3/4，那么 $s_a$ 的奖励应该是 3/4。

用蒙特卡洛方法与时序差分方法估出来的结果很有可能是不一样的。就算评论员观察到一样的训练数据，它最后估出来的结果也不一定是一样的。为什么会这样呢？哪一个结果比较对呢？其实都对。因为在第一个轨迹中，$s_a$ 得到奖励 0 以后，再进入 $s_b$ 也得到奖励 0。这里有两个可能。

（1）$s_a$ 是一个标志性的状态，只要看到 $s_a$ 以后，$s_b$ 就不会获得奖励，$s_a$ 可能影响了 $s_b$。如果是使用蒙特卡洛方法，它会把 $s_a$ 影响 $s_b$ 这件事考虑进去。所以看到 $s_a$ 以后，接下来 $s_b$ 就得不到奖励，$s_b$ 期望的奖励是 0。

（2）看到 $s_a$ 以后，$s_b$ 的奖励是 0 这件事只是巧合，并不是 $s_a$ 造成的，而是因为 $s_b$ 有时候就是会得到奖励 0，这只是单纯“运气”的问题。其实平常 $s_b$ 会得到的奖励期望值是 3/4，与 $s_a$ 是完全没有关系的。所以假设 $s_a$ 之后会进入 $s_b$，得到的奖励按照时序差分方法来算应该是 3/4。

不同的方法考虑了不同的假设，所以运算结果不同。

2. 动作价值函数

还有另外一种评论员称为 $Q$ 函数，它又被称为动作价值函数。状态价值函数的输入是一个状态，它根据状态计算出这个状态以后的期望的累积奖励（expected accumulated reward）是多少。动作价值函数的输入是一个状态-动作对，其指在某一个状态采取某一个动作，假设我们都使用策略 $\pi$，得到的累积奖励的期望值有多大。

$Q$ 函数有一个需要注意的问题是，策略 $\pi$ 在看到状态 $s$ 的时候，它采取的动作不一定是 $a$。$Q$ 函数假设在状态 $s$ 强制采取动作 $a$，而不管我们现在考虑的策略 $\pi$ 会不会采取动作 $a$，这并不重要。在状态 $s$ 强制采取动作 $a$。接下来都用策略 $\pi$ 继续玩下去，就只有在状态 $s$，我们才强制一定要采取动作 $a$，接下来就进入自动模式，让策略 $\pi$ 继续玩下去，得到的期望奖励才是 $Q_{\pi }(s,a)$。

$Q$ 函数有两种写法：

（1）如图6 (a) 所示，输入是状态与动作，输出就是一个标量。这种 $Q$ 函数既适用于连续动作（动作是无法穷举的），又适用于离散动作。

（2）如图6 (b) 所示，输入是一个状态，输出就是多个值。这种 $Q$ 函数只适用于离散动作。假设动作是离散的，比如动作就只有 3 个可能：往左、往右或是开火。$Q$ 函数输出的 3 个值就分别代表 $a$ 是往左的时候的 $Q$ 值，$a$ 是往右的时候的 $Q$ 值，还有 $a$ 是开火的时候的 $Q$ 值。

如果我们去估计 $Q$ 函数，看到的结果可能如图7 所示。假设我们有 3 个动作：原地不动、向上、向下。假设在第一个状态，不管采取哪个动作，最后到游戏结束的时候，得到的期望奖励都差不多。因为乒乓球在这个地方时，就算我们向下，接下来我们应该还可以接到乒乓球，所以不管采取哪个动作，都相差不了太多。假设在第二个状态，乒乓球已经反弹到很接近边缘的地方，这个时候我们采取向上的动作，才能接到乒乓球，才能得到正的奖励。如果我们站在原地不动或向下，接下来都会错过这个乒乓球，得到的奖励就会是负的。假设在第三个状态，乒乓球离我们的球拍很近了，所以就要采取向上的动作。假设在第四个状态，乒乓球被反弹回去，这时候采取哪个动作都差不多。这是动作价值函数的例子。

虽然我们学习的 $Q$ 函数只能用来评估某一个策略 $\pi$ 的好坏，但只要有了 $Q$ 函数，我们就可以进行强化学习，就可以决定要采取哪一个动作，就可以进行策略改进。如图 8 所示，假设我们有一个初始的演员，也许一开始很差，随机的也没有关系。初始的演员称为 $\pi$，$\pi$ 与环境交互，会收集数据。接下来我们学习策略 $\pi$ 的 $Q$ 值，去衡量一下 $\pi$ 在某一个状态强制采取某一个动作，接下来会得到的期望奖励，用时序差分方法或蒙特卡洛方法都是可以的。我们学习出一个 $Q$ 函数以后，就可以找到一个新的策略 ${\pi }^{\prime }$，策略 ${\pi }^{\prime }$ 会比原来的策略 $\pi$ 要好（稍后会定义什么是好）。所以假设我们有一个 $Q$ 函数和某一个策略 $\pi$，根据策略 $\pi$ 学习出策略 $\pi$ 的 $Q$ 函数，接下来可以找到一个新的策略 ${\pi }^{\prime }$，它会比 $\pi$ 要好。我们用 ${\pi }^{\prime }$ 取代 $\pi$，再去学习它的 $Q$ 函数，得到新的 $Q$ 函数以后，再去寻找一个更好的策略。这样一直循环下去，策略就会越来越好。

首先要定义的是什么是好。${\pi }^{\prime }$ 一定会比 $\pi$ 要好，什么是好呢？这里的好是指，对所有可能的状态 $s$ 而言，$V_{{\pi }^{\prime }}(s)\ge V_{\pi }(s)$。也就是我们到同一个状态 $s$ 的时候，如果用 $\pi$ 继续与环境交互，我们得到的奖励一定会小于等于用 ${\pi }^{\prime }$ 与环境交互得到的奖励。所以不管在哪一个状态，我们用 ${\pi }^{\prime }$ 与环境交互，得到的期望奖励一定会比较大。所以 ${\pi }^{\prime }$ 是比 $\pi$ 要好的策略。

有了 $Q$ 函数以后，我们把根据式(4)决定动作的策略称为 ${\pi }^{\prime }$，

$$\begin{array}{c}{\pi }^{\prime }(s)=arg\underset{a}{\max }{Q}_{\pi }(s,a)\end{array}$$

$\pi$ 一定比 $\pi$ 好。假设我们已经学习出 $\pi$ 的 $Q$ 函数，在某一个状态 $s$，把所有可能的动作 $a$ 一一代入 $Q$ 函数，看看哪一个 $a$ 可以让 $Q$ 函数的值最大，这个动作就是 ${\pi }^{\prime }$ 会采取的动作。

这里要注意，给定状态 $s$ 和策略 $\pi$ 并不一定会采取动作 $a$。给定某一个状态 $s$ 强制采取动作 $a$，用 $\pi$ 继续交互得到的期望奖励，这才是 $Q$ 函数的定义。所以在状态 $s$ 下不一定会采取动作 $a$。用 ${\pi }^{\prime }$ 在状态 $s$ 采取动作 $a$ 与用 $\pi$ 采取的动作不一定是一样的，${\pi }^{\prime }$ 所采取的动作会让它得到比较大的奖励。所以 ${\pi }^{\prime }$ 是用 $Q$ 函数推出来的，没有另外一个网络决定 ${\pi }^{\prime }$ 怎么与环境交互，有 $Q$ 函数 就可以找出 ${\pi }^{\prime }$。但是在这里要解决一个 argmax 操作的问题，如果 $a$ 是离散的，如 $a$ 只有 3 个选项，将每个动作都代入 $Q$ 函数，看哪个动作的 $Q$ 值最大，这没有问题。但如果 $a$ 是连续的，我们要解决 argmax 操作问题，就不可行。

接下来讲一下为什么用 $Q_{\pi }(s,a)$ 决定的 ${\pi }^{\prime }$ 一定会比 $\pi$ 好。假设有一个策略 ${\pi }^{\prime }$，它是由 $Q_{\pi }$ 决定的。我们要证明对所有的状态 $s$，有 $V_{{\pi }^{\prime }}(s)\ge V_{\pi }(s)$。

怎么证明呢？$V_{\pi }(s)$ 可写为

$$V_{\pi }(s)=Q_{\pi }(s,\pi (s))$$

假设在状态 $s$ 下按照策略 $\pi$，会采取的动作就是 $\pi (s)$，我们算出来的 $Q_{\pi }(s,\pi (s))$ 会等于 $V_{\pi }(s)$。一般而言，$Q_{\pi }(s,\pi (s))$ 不一定等于 $V_{\pi }(s)$，因为动作不一定是 $\pi (s)$。但如果这个动作是 $\pi (s)$，$Q_{\pi }(s,\pi (s))$ 是等于 $V_{\pi }(s)$ 的。

$Q_{\pi }(s,\pi (s))$ 还满足如下的关系：

$$Q_{\pi }(s,\pi (s))\le \underset{a}{\max }{Q}_{\pi }(s,a)$$

因为 $a$ 是所有动作里面可以让 $Q$ 函数取最大值的那个动作，所以 $Q_{\pi }(s,a)$ 一定大于等于 $Q_{\pi }(s,\pi (s))$。$Q_{\pi }(s,a)$ 中的 $a$ 就是 ${\pi }^{\prime }(s)$，因为 ${\pi }^{\prime }(s)$ 输出的 $a$ 可以让 $Q_{\pi }(s,a)$ 最大，所以我们可得

$$\underset{a}{\max }{Q}_{\pi }(s,a)=Q_{\pi }(s,{\pi }^{\prime }(s))$$

于是

$$V_{\pi }(s)\le Q_{\pi }(s,{\pi }^{\prime }(s))$$

也就是在某一个状态，如果我们按照策略 $\pi$ 一直执行下去，得到的奖励一定会小于等于在状态 $s$ 故意不按照 $\pi$ 所指示的方向，而是按照 ${\pi }^{\prime }$ 的方向走一步得到的奖励。但只有第一步是按照 ${\pi }^{\prime }$ 的方向走，只有在状态 $s$，才按照 ${\pi }^{\prime }$ 的指示走，接下来我们就按照 $\pi$ 的指示走。虽然只有一步之差，但我们得到的奖励一定会比完全按照 $\pi$ 得到的奖励要大。

接下来要证

$$Q_{\pi }(s,{\pi }^{\prime }(s))\le V_{{\pi }^{\prime }}(s)$$

也就是，只有一步之差，我们会得到比较大的奖励。但假设每步都是不一样的，每步都按照 ${\pi }^{\prime }$ 而不是 $\pi$，得到的奖励一定会更大，即 $Q_{\pi }(s,{\pi }^{\prime }(s))$ 是指我们在状态 $s_t$ 采取动作 $a_t$，得到奖励 $r_t$，进入状态 $s_{t+1}$，即

$$Q_{\pi }(s,{\pi }^{\prime }(s))=\mathbb{E}[r_t+V_{\pi }(s_{t+1})|s_t=s,a_t={\pi }^{\prime }(s_t)]$$

有的文献上也会说：在状态 $s_t$ 采取动作 $a_t$，得到奖励 $r_{t+1}$。但意思其实都是一样的。在状态 $s$ 按照 ${\pi }^{\prime }$ 采取某一个动作 $a_t$，得到奖励 $r_t$，进入状态 $s_{t+1}$，$V_{\pi }(s_{t+1})$ 是状态 $s_{t+1}$ 根据策略 $\pi$ 所估出来的值。因为在同样的状态采取同样的动作，我们得到的奖励和会进入的状态不一定一样， 所以需要取期望值。

因为 $V_{\pi }(s)\le Q_{\pi }(s,{\pi }^{\prime }(s))$，也就是 $V_{\pi }(s_{t+1})\le Q_{\pi }(s_{t+1},{\pi }^{\prime }(s_{t+1}))$ ，所以我们可得

$$\begin{array}{r}\mathbb{E}\left[r_t+V_{\pi }(s_{t+1})\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ \le \mathbb{E}\left[r_t+Q_{\pi }(s_{t+1},{\pi }^{\prime }(s_{t+1}))\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\end{array}$$

因为 $Q_{\pi }(s_{t+1},{\pi }^{\prime }(s_{t+1}))=r_{t+1}+V_{\pi }(s_{t+2})$，所以我们可得

$$\begin{gathered} \begin{array}{c}\mathbb{E}\left[r_t+Q_{\pi }\left(s_{t+1},{\pi }^{\prime }(s_{t+1})\right)\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right] \\ =\mathbb{E}\left[r_t+r_{t+1}+V_{\pi }(s_{t+2})\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\end{array} \end{gathered}$$

我们再把式(5)代入 $V_{\pi }(s)\le Q_{\pi }(s,{\pi }^{\prime }(s))$，一直算到回合结束，即

$$\begin{array}{rl}{V}^{\pi }(s)& \le Q^{\pi }(s,{\pi }^{\prime }(s))\\ & =\mathbb{E}\left[r_t+V^{\pi }(s_{t+1})\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & \le \mathbb{E}\left[r_t+Q^{\pi }(s_{t+1},{\pi }^{\prime }(s_{t+1}))\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & =\mathbb{E}\left[r_t+r_{t+1}+V^{\pi }(s_{t+2})\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & \le \mathbb{E}\left[r_t+r_{t+1}+Q^{\pi }(s_{t+2},{\pi }^{\prime }(s_{t+2}))\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & =\mathbb{E}\left[r_t+r_{t+1}+r_{t+2}+V^{\pi }(s_{t+3})\mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & \le \cdots \\ & \le \mathbb{E}\left[r_t+r_{t+1}+r_{t+2}+\cdots \mid s_t=s,a_t={\pi }^{\prime }(s_t)\right]\\ & =V^{{\pi }^{\prime }}(s)\end{array}$$

因此

$$V^{\pi }(s)\le V^{{\pi }^{\prime }}(s)$$

我们可以估计某一个策略的 $Q$ 函数，接下来就可以找到另外一个策略 ${\pi }^{\prime }$ 比原来的策略 $\pi$ 还要更好。

3. 目标网络

接下来讲一些在深度 $Q$ 网络里一定会用到的技巧。第一个技巧是目标网络（target network）。我们在学习 $Q$ 函数的时候，也会用到时序差分方法的概念。我们现在收集到一个数据，比如在状态 $s_t$ 采取动作 $a_t$ 以后，得到奖励 $r_t$ ，进入状态 $s_{t+1}$。根据 $Q$ 函数，我们可知

$$Q_{\pi }(s_t,a_t)=r_t+Q_{\pi }(s_{t+1},\pi (s_{t+1}))$$

所以我们在学习的时候，$Q$ 函数输入 $s_t,a_t$ 得到的值，与输入 $s_{t+1},\pi (s_{t+1})$ 得到的值之间，我们希望它们相差 $r_t$， 这与时序差分方法的概念是一样的。但是实际上这样的输入并不好学习，假设这是一个回归问题，如图 9 所示，$Q_{\pi }(s_t,a_t)$ 是网络的输出，$r_t+Q_{\pi }(s_{t+1},\pi (s_{t+1}))$ 是目标，目标是会变动的。当然如果我们要实现这样的训练，其实也没有问题，就是在做反向传播的时候， $Q_{\pi }$ 的参数会被更新，我们会把两个更新的结果加在一起（因为它们是同一个模型 $Q_{\pi }$， 所以两个更新的结果会加在一起）。但这样会导致训练变得不太稳定，因为假设我们把 $Q_{\pi }(s_t,a_t)$ 当作模型的输出， 把 $r_t+Q_{\pi }(s_{t+1},\pi (s_{t+1}))$ 当作目标，我们要去拟合的目标是一直在变动的，这是不太好训练的。

所以我们会把其中一个 $Q$ 网络，通常是把图 9 右边的 $Q$ 网络固定住。在训练的时候，我们只更新左边的 $Q$ 网络的参数，而右边的 $Q$ 网络的参数会被固定。因为右边的 $Q$ 网络负责产生目标，所以被称为目标网络。因为目标网络是固定的，所以现在得到的目标 $r_t+Q_{\pi }(s_{t+1},\pi (s_{t+1}))$ 的值也是固定的。我们只调整左边 $Q$ 网络的参数，它就变成一个回归问题。我们希望模型输出的值与目标越接近越好，这样会最小化它的均方误差（mean square error）。

在实现的时候，我们会把左边的 $Q$ 网络更新多次，再用更新过的 $Q$ 网络替换目标网络。但这两个网络不要一起更新，一起更新，结果会很容易不好。一开始这两个网络是一样的，在训练的时候，我们会把右边的 $Q$ 网络固定住，在做梯度下降的时候，只调整左边 $Q$ 网络的参数。我们可能更新 100 次以后才把参数复制到右边的网络中，把右边网络的参数覆盖，目标值就变了。就好像我们本来在做一个回归问题，训练后把这个回归问题的损失降下去以后，接下来我们把左边网络的参数复制到右边网络，目标值就变了，接下来就要重新训练。

如图10(a) 所示，我们可以通过猫追老鼠的例子来直观地理解固定目标网络的目的。猫是 $Q$ 估计，老鼠是 $Q$ 目标。一开始，猫离老鼠很远，所以我们想让猫追上老鼠。如图10(b) 所示，因为 $Q$ 目标也是与模型参数相关的，所以每次优化后，$Q$ 目标也会动。这就导致一个问题，猫和老鼠都在动。如图10© 所示，猫和老鼠会在优化空间里面到处乱动，这会产生非常奇怪的优化轨迹，使得训练过程十分不稳定。所以我们可以固定 $Q$ 网络，让老鼠动得不那么频繁，可能让它每 5 步动一次，猫则是每一步都在动。如果老鼠每 5 次动一步，猫就有足够的时间来接近老鼠，它们之间的距离会随着优化过程越来越小，最后它们就可以拟合，拟合后就可以得到一个最好的 $Q$ 网络。

4. 探索

第二个技巧是探索。当我们使用 $Q$ 函数的时候，策略完全取决于 $Q$ 函数。给定某一个状态，我们就穷举所有的动作，采取让 $Q$ 值最大的动作，即

$$a=arg\underset{a}{\max }Q(s,a)$$

使用 $Q$ 函数来决定动作与使用策略梯度不一样，策略梯度的输出是随机的，它会输出一个动作的分布，我们根据这个动作的分布去采样，所以在策略梯度里面，我们每次采取的动作是不一样的，是有随机性的。像 $Q$ 函数中，如果我们采取的动作总是固定的，会遇到的问题就是这不是一个好的收集数据的方式。假设我们要估测某一个状态，可以采取动作 $a_1,a_2,a_3$ 。

我们要估测在某一个状态采取某一个动作会得到的 $Q$ 值，一定要在那一个状态采取过那一个动作，才能估测出它的值。如果没有在那个状态采取过那个动作，我们其实是估测不出它的值的。如果 $Q$ 函数是一个网络，这个问题可能没有那么严重。但是一般而言，假设 $Q$ 函数是一个表格，对于没有见过的状态-动作对，它是估不出值的。如果 $Q$ 函数是网络，也会有类似的问题，只是没有那么严重。所以假设我们在某一个状态，动作 $a_1,a_2,a_3$ 都没有采取过，估出来的 $Q(s,a_1),Q(s,a_2),Q(s,a_3)$ 的值可能都是一样的，都是一个初始值，比如 0，即

$$\begin{array}{rl}Q(s,a_1)& =0\\ Q(s,a_2)& =0\\ Q(s,a_3)& =0\end{array}$$

但是如图 11 所示，假设我们在状态 $s$ 采取动作 $a_2$，它得到的值是正的奖励，$Q(s,a_2)$ 就会比其他动作的 $Q$ 值要大。在采取动作的时候，谁的 $Q$ 值 最大就采取谁，所以之后永远都只会采取 $a_2$，其他的动作就再也不会被采取了，这就会有问题。比如我们去一个餐厅吃饭。假设我们点了某一样菜，比如椒麻鸡，我们觉得还可以。接下来我们每次去就都会点椒麻鸡，再也不点别的菜了，那我们就不知道别的菜是不是会比椒麻鸡好吃，这是一样的问题。

如果我们没有好的探索，在训练的时候就会遇到这种问题。例如， 假设我们用深度 $Q$ 网络 来玩 slither.io 网页游戏。 我们有一条蛇，它在环境里面走来走去，吃到星星，就加分。假设游戏一开始，蛇往上走，然后吃到星星，就可以得到分数，它就知道往上走可以得到奖励。接下来它就再也不会采取往上走以外的动作了，以后就会变成每次游戏一开始，它就往上走，然后游戏结束。所以需要有探索的机制，让智能体知道，虽然根据之前采样的结果，$a_2$ 好像是不错的，但我们至少偶尔也试一下 $a_1$ 与 $a_3$，说不定它们更好。

这个问题就是探索-利用窘境（exploration-exploitation dilemma）问题，有两个方法可以解决这个问题：$ϵ$-贪心和玻尔兹曼探索（Boltzmann exploration）。

$ϵ$-贪心是指我们有 $1-ϵ$ 的概率会按照 $Q$ 函数来决定动作，可写为

$$a=\{\begin{array}{ll}\arg \underset{a}{\max }Q(s,a),& \text{有 }1-\epsilon \text{ 的概率}\\ \text{随机},& \text{否则}\end{array}$$

通常将 $ϵ$ 设为一个很小的值，$1-ϵ$ 可能是 0.9，也就是 0.9 的概率会按照 $Q$ 函数来决定动作，但是我们有 0.1 的概率是随机的。通常在实现上 $ϵ$ 会随着时间递减。在最开始的时候，因为不知道哪个动作是比较好的，所以我们会花比较大的力气探索。接下来，随着训练的次数越来越多，我们已经比较确定哪个动作是比较好的。我们就会减少探索，会把 $ϵ$ 的值变小，主要根据 $Q$ 函数来决定动作，比较少随机决定动作，这就是 $ϵ$-贪心。

还有一个方法称为玻尔兹曼探索。在玻尔兹曼探索中，我们假设对于任意的 $s,a$ 都有 $Q(s,a)\ge 0$，因此 $a$ 被选中的概率与 $e^{Q(s,a)/T}$ 呈正比，即

$$\pi (a|s)=\frac{e^{Q(s,a)/T}}{{\sum }_{a^{\prime }\in A}{e}^{Q(s,a^{\prime })/T}}$$

其中，$T>0$ 称为温度系数。如果 $T$ 很大，所有动作几乎以等概率选择（探索）；如果 $T$ 很小，$Q$ 值大的动作更容易被选中（利用）；如果 $T$ 趋于0，我们就只选择最优动作。

5. 经验回放

第三个技巧是经验回放（experience replay）。如图 12 所示，经验回放会构建一个回放缓冲区（replay buffer），回放缓冲区又被称为回放内存（replay memory）。回放缓冲区是指现在有某一个策略 $\pi$ 与环境交互，它会去收集数据，我们把所有的数据放到一个数据缓冲区（buffer）里面，数据缓冲区里面存储了很多数据。比如数据缓冲区可以存储 5 万笔数据，每一笔数据就是记得说，我们之前在某一个状态 $s_t$，采取某一个动作 $a_t$，得到了奖励 $r_t$，进入状态 $s_{t+1}$。

我们用 $\pi$ 去与环境交互多次，把收集到的数据放到回放缓冲区里面。 回放缓冲区里面的经验可能来自不同的策略，我们每次用 $\pi$ 与环境交互的时候，可能只交互 10000 次，接下来我们就更新 $\pi$ 了。但是回放缓冲区里面可以放 5 万笔数据，所以 5 万笔数据可能来自不同的策略。回放缓冲区只有在它装满的时候，才会把旧的数据丢掉。所以回放缓冲区里面其实装了很多不同的策略的经验。

如图 13 所示，有了回放缓冲区以后，我们怎么训练 $Q$ 模型、怎么评估 $Q$ 函数呢？我们会迭代地训练 $Q$ 函数，在每次迭代里面，从回放缓冲区中随机挑一个批量（batch）出来，即与一般的网络训练一样，从训练集里面挑一个批量出来。我们采样该批量出来，里面有一些经验，我们根据这些经验去更新 $Q$ 函数。这与时序差分学习要有一个目标网络是一样的。我们采样一个批量的数据，得到一些经验，再去更新 $Q$ 函数。

如果某个算法使用了经验回放这个技巧，该算法就变成了一个异策略（Off-policy）的算法。因为本来 $Q$ 是要观察 $\pi$ 的经验的，但实际上存储在回放缓冲区里面的这些经验不是通通来自于 $\pi$，有些是过去其他的策略所留下来的经验。因为我们不会用某一个 $\pi$ 就把整个回放缓冲区装满，拿去测 $Q$ 函数，$\pi$ 只是采样一些数据放到回放缓冲区里面，接下来就让 $Q$ 去训练。所以 $Q$ 在采样的时候， 它会采样到过去的一些数据。

这么做有两个好处。第一个好处是，在进行强化学习的时候， 往往最花时间的步骤是与环境交互，训练网络反而是比较快的。因为我们用 GPU 训练其实很快，真正花时间的往往是与环境交互。用回放缓冲区可以减少与环境交互的次数，因为在做训练的时候，经验不需要通通来自于某一个策略。一些过去的策略所得到的经验可以放在回放缓冲区里面被使用很多次，被反复的再利用，这样可以比较高效地采样经验。第二个好处是，在训练网络的时候，其实我们希望一个批量里面的数据越多样（diverse）越好。如果批量里面的数据都是同样性质的，我们训练下去，训练结果是容易不好的。如果批量里面都是一样的数据，训练的时候，性能会比较差。我们希望批量里的数据越多样越好。如果回放缓冲区里面的经验通通来自于不同的策略，我们采样到的一个批量里面的数据会是比较多样的。

Q：我们观察 $\pi$ 的值，发现里面混杂了一些不是 $\pi$ 的经验，这有没有关系？

A：没关系。这并不是因为过去的策略与现在的策略很像， 就算过去的策略与现在的策略不是很像，也是没有关系的。主要的原因是我们并不是去采样一个轨迹，我们只采样了一笔经验，所以与是不是异策略这件事是没有关系的。就算是异策略，就算是这些经验不是来自于 $\pi$，我们还是可以用这些经验来估测 $Q_{\pi }(s,a)$

6. Deep Q-Learning算法思路

Deep Q-Learning算法的基本思路来源于Q-Learning。但是和Q-Learning不同的地方在于，它的Q值的计算不是直接通过状态值s和动作来计算，而是通过Q网络来计算的。这个Q网络是一个神经网络，我们一般简称Deep Q-Learning为DQN。

DQN的输入是我们的状态s对应的状态向量 $\varphi (s)$，输出是所有动作在该状态下的动作价值函数 $Q$。$Q$ 网络可以是DNN，CNN或者RNN，没有具体的网络结构要求。

DQN主要使用的技巧是经验回放（experience replay），即将每次和环境交互得到的奖励与状态更新情况都保存起来，用于后面目标Q值的更新。为什么需要经验回放呢？我们回忆一下Q-Learning，它是有一张Q表来保存所有Q值的当前结果的，但是DQN是没有的，那么在做动作价值函数更新的时候，就需要其他的方法，这个方法就是经验回放。

通过经验回放得到的目标 $Q$ 值和通过 $Q$ 网络计算的 $Q$ 值肯定是有误差的，那么我们可以通过梯度的反向传播来更新神经网络的参数 $w$，当 $w$ 收敛后，我们就得到了近似的Q值计算方法，进而贪婪策略也就求出来了。

下面我们总结下DQN的算法流程，基于NIPS 2013 DQN。

算法输入：迭代轮数 $T$，状态特征维度 $n$，动作集 $A$，步长 $\alpha$，衰减因子 $\gamma$，探索率 $ϵ$，$Q$ 网络结构, 批量梯度下降的样本数 $m$。

输出：$Q$ 网络参数

1. 随机初始化Q网络的所有参数 $w$，基于 $w$ 初始化所有的状态和动作对应的价值 $Q$。清空经验回放的集合 $D$。

2. for i from 1 to T，进行迭代：

   a. 初始化 $S$ 为当前状态序列的第一个状态, 拿到其特征向量 $\varphi (S)$

   b. 在 $Q$ 网络中使用 $\varphi (S)$ 作为输入，得到 $Q$ 网络的所有动作对应的 $Q$ 值输出。用 $ϵ$-贪婪法在当前 $Q$ 值输出中选择对应的动作 $A$

   c. 在状态 $S$ 执行当前动作 $A$，得到新状态 $S^{\prime }$ 对应的特征向量 $\varphi (S^{\prime })$ 和奖励 $R$，是否终止状态is_end

   d. 将 { ϕ ( S ) , A , R , ϕ ( S ′ ) , i s _ e n d } \{\phi(S), A, R, \phi(S'), is\_end\} {ϕ(S),A,R,ϕ(S′),is_end} 这个五元组存入经验回放集合 $D$

   e. $S=S^{\prime }$

   f. 从经验回放集合 $D$ 中采样 $m$ 个样本 { ϕ ( S j ) , A j , R j , ϕ ( S j ′ ) , i s _ e n d j } \{\phi(S_j), A_j, R_j, \phi(S'_j), is\_end_j\} {ϕ(Sj​),Aj​,Rj​,ϕ(Sj′​),is_endj​}，$j=1,2,\cdots ,m$，，计算当前目标 $Q$ 值的 $y_j$：

   $$\begin{array}{c}{y}_j=\{\begin{array}{ll}{R}_j& is\_en{d}_j\text{ is true}\\ R_j+\gamma {\max }_{a^{\prime }}Q(\varphi (S_j^{\prime }),A_j^{\prime },w)& is\_en{d}_j\text{ is false}\end{array}\end{array}$$

   g. 使用均方差损失函数 $\frac{1}{m}{\sum }_{j=1}^m(y_j-Q(\varphi (S_j),A_j,w){)}^2$，通过神经网络的梯度反向传播来更新 $Q$ 网络的所有参数 $w$

   f. 如果 $S^{\prime }$是终止状态，当前轮迭代完毕，否则转到步骤b

   注意，上述第二步的f步和g步的 $Q$ 值计算也都需要通过 $Q$ 网络计算得到。另外，实际应用中，为了算法较好的收敛，探索率 $ϵ$ 需要随着迭代的进行而变小。

7. Deep Q-Learning实例

这里我们用最常见的CartPole 平衡杆环境来做说明，并给出一个简化版的 DQN 实现（用 PyTorch，易于理解）。

环境说明

CartPole 是 OpenAI Gym 中的一个经典环境，目标是通过左右移动一个小车，使得竖直杆子保持直立。

• 状态空间：小车位置、速度、杆子角度、角速度（共 4 个连续值）
• 动作空间：左（0）、右（1）
• 奖励（Reward）：每存活一步获得 +1 奖励，杆子倒地或超出边界则回合结束。
• 终止条件：杆子角度超过 ±12° 或推车位置超出 ±2.4 单位。

DQN 的核心流程

• 用神经网络近似 $Q(s,a)$
• 通过与环境交互收集 $(s,a,r,s’)$，存入经验回放池
• 随机采样小批量 $(s,a,r,s’)$，用贝尔曼方程更新 $Q$ 网络参数
• 用 ε-greedy 策略进行探索

代码实例（PyTorch）

import gym
import torch
import torch.nn as nn
import torch.optim as optim
import random
import numpy as np
from collections import deque

# 1. 定义Q网络
class QNetwork(nn.Module):
    def __init__(self, state_dim, action_dim):
        super(QNetwork, self).__init__()
        self.net = nn.Sequential(
            nn.Linear(state_dim, 128),
            nn.ReLU(),
            nn.Linear(128, action_dim)
        )

    def forward(self, x):
        return self.net(x)

# 2. 经验回放池
class ReplayBuffer:
    def __init__(self, capacity):
        self.buffer = deque(maxlen=capacity)

    def push(self, state, action, reward, next_state, done):
        self.buffer.append((state, action, reward, next_state, done))

    def sample(self, batch_size):
        batch = random.sample(self.buffer, batch_size)
        state, action, reward, next_state, done = map(np.array, zip(*batch))
        return state, action, reward, next_state, done

    def __len__(self):
        return len(self.buffer)

# 3. 主要训练过程
env = gym.make('CartPole-v1')
state_dim = env.observation_space.shape[0]
action_dim = env.action_space.n

q_net = QNetwork(state_dim, action_dim)
target_net = QNetwork(state_dim, action_dim)
target_net.load_state_dict(q_net.state_dict())

optimizer = optim.Adam(q_net.parameters(), lr=1e-3)
buffer = ReplayBuffer(10000)
gamma = 0.99
batch_size = 64
epsilon = 1.0
epsilon_decay = 0.995
epsilon_min = 0.01
target_update_freq = 10

for episode in range(300):
    state = env.reset()
    state = np.array(state)
    episode_reward = 0
    for t in range(200):
        # ε-greedy 策略
        if random.random() < epsilon:
            action = env.action_space.sample()
        else:
            with torch.no_grad():
                q_values = q_net(torch.FloatTensor(state))
                action = q_values.argmax().item()

        next_state, reward, done, _ = env.step(action)
        buffer.push(state, action, reward, next_state, done)
        state = next_state
        episode_reward += reward

        # 更新网络
        if len(buffer) >= batch_size:
            b_state, b_action, b_reward, b_next_state, b_done = buffer.sample(batch_size)
            b_state = torch.FloatTensor(b_state)
            b_action = torch.LongTensor(b_action)
            b_reward = torch.FloatTensor(b_reward)
            b_next_state = torch.FloatTensor(b_next_state)
            b_done = torch.FloatTensor(b_done)

            q = q_net(b_state).gather(1, b_action.unsqueeze(1)).squeeze(1)
            with torch.no_grad():
                q_next = target_net(b_next_state).max(1)[0]
                q_target = b_reward + gamma * q_next * (1 - b_done)
            loss = nn.MSELoss()(q, q_target)

            optimizer.zero_grad()
            loss.backward()
            optimizer.step()

        if done:
            break

    # 更新 target network
    if episode % target_update_freq == 0:
        target_net.load_state_dict(q_net.state_dict())
    epsilon = max(epsilon * epsilon_decay, epsilon_min)
    print(f"Episode {episode}, Reward: {episode_reward}")

env.close()

总结：

• QNetwork 近似 Q 值函数
• 经验回放池让训练更稳定
• 训练时用 Q-learning 的目标更新 Q 网络
• 用目标网络防止目标震荡