目录

• • DQN算法
  • • • 价值函数的近似表示
      • • 提出背景：
        • 近似表示：
        • • 状态价值函数
          • 动作价值函数
      • 概述
      • • • 经验回放（experience replay）
      • 算法流程
      • 小结
  • Nature DQN算法
  • • • 概述
      • • • Nature DQN的优化点：
          • Nature DQN 建模——双网络结构：
      • 算法流程
      • 小结
  • Double DQN算法
  • • • 概述
      • • • DDQN的优化点：
          • DDQN建模——Q值与动作解耦:
      • 算法流程
  • Prioritized Replay DQN算法
  • • • 概述
      • • • Prioritized Replay DQN的优化点：
          • Prioritized Replay DQN建模:
      • 算法流程（集成了DDQN）
  • Dueling DQN算法
  • • • 概述
      • • • Dueling DQN的优化点：
          • Dueling DQN网络结构:
  • 总结

DQN算法

价值函数的近似表示

提出背景：

​ 动态规划DP、蒙特卡罗MC、时序差分TD这些求解MDP问题的算法，使用的状态都是有限个离散状态，问题规模小时易求解。而 当问题规模庞大，或者状态是连续的且离散化后依然规模庞大时，无法将Q表存在有限的内存中。因此用价值函数的近似表示来修改模 型。

​

近似表示：

状态价值函数

​ ，其中w是参数

动作价值函数

​ ，其中w是参数

​ 具体的近似有很多，比如：线性表示法、决策树、最近邻、傅里叶变换等，但是最常用的是神经网络（DNN、CNN、RNN）。

​ 对于状态价值函数，神经网络的输入是状态s的特征向量，输出是状态价值v(s,w)。

​ 对于动作价值函数，有两种方法，一种是输入状态s的特征向量和动作a，输出对应的动作价值q(s,a,w)，另一种是只输入状态s的特征 向量，动作集合有多少个动作就有多少个输出q(s,ai,w)。这里隐示了动作是有限个的离散动作。

概述

​ 基本思路来源于Q-Learning，但是和Q-Learning不同的地方在于，它的Q值的计算不是直接通过状态值S 和动作A 来计算，而是通过上面讲到的Q网络来计算的，这个Q网络是一个神经网络。

经验回放（experience replay）

​ 将每次和环境交互得到的奖励与状态更新情况都保存起来，用于后面目标Q值的更新。Q-Learning是有一张Q表来保存所有的Q 值的当前结果的，而DQN在做动作价值函数更新时靠的就是经验回放。从经验池查询得到的S、A用神经网络结合公式计算得到的目 标Q值和直接通过Q网络直接计算得到的Q估计值肯定是不等的（经验池里的是之前神经网络算出来的，其网络参数与当前网络的不 同，这个差值作为神经网络的损失函数Loss Function，那么可以通过梯度的反向传播来更新神经网络的参数w，当w收敛后就得到的 近似的Q值计算方法，进而贪婪策略也就求出来了。

算法流程

输入：迭代轮数T、状态特征维度n、动作集A、步长α、衰减因子γ、探索率ϵ、Q网络结构、批量梯度下降的样本数m

输出：Q网络参数w

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

​ 2. for i in [ 1, T ]：

​ a）初始化S为当前状态序列的第一个状态，拿到其特征向量ϕ(S)

​ b）把ϕ(S)输入Q网络，得到所有动作对应的Q值输出，用ε-greedy策略从中选择出动作A

​ c）执行动作A，由环境得到新状态S‘ 对应的特征向量ϕ(S‘)、奖励R’、终止标志is_end

​ d）将 { ϕ(S)，A，R，ϕ(S‘)，is_end } 这个五元组存入经验池D

​ e）前进一步：S = S’

​ f）从经验池中采集m个样本 { ϕ(Sj)，Aj，Rj，ϕ(Sj‘)，is_endj }，j = 1,2,3…，把S‘ 和A’ 输入神经网络结合贪婪策略计算当前目标Q 值 yj：

​

​ g）把S‘ 和A’ 输入Q网络直接求Q估计值，由目标Q值和Q估计值求损失函数Loss Function，然后梯度反向传播更新Q网络参数w

​ h）if S’是终止状态，break；else 跳回步骤b

​ （注意，f步和g步的Q值计算都需要用到Q网络。另外，实际应用中为了算法较好的收敛，探索率ϵ需要随着迭代的进行而变小 ）

小结

​ DQN由于对价值函数做了近似表示，因此有了解决大规模强化学习问题的能力。但是DQN有个问题，就是它并不一定能保证Q网络的收敛，也就是说不一定可以得到收敛后的Q网络参数。这会导致训练出的模型效果很差。针对这个问题衍生出了DQN的很多变种，比如Nature DQN(NIPS 2015)、Double DQN、Dueling DQN等。

Nature DQN算法

概述

Nature DQN的优化点：

​ 目标Q值的计算用到了当前要训练的网络参数w：

​

​ 用来计算损失函数的目标Q值和Q估计值，二者相关性太强，不利于算法收敛。因此提出Nature DQN使用两个Q网络来分别计 算目标Q值和Q估计值，从而减少二者间的依赖关系。

Nature DQN 建模——双网络结构：

​ 相较于普通DQN，Nature DQN使用了两个Q网络，当前Q网络用来选择动作，更新模型参数，目标Q网络用于计算目标Q值。 目标Q网络的网络参数不需要迭代更新，而是每隔一段时间从当前Q网络复制过来，即延时更新，这样可以减少目标Q值和当前 Q值的相关性。二者其余部分基本是完全相同的。（要注意的是，两个Q网络的结构是一模一样的。这样才可以复制网络参数 ）

算法流程

输入：迭代轮数T、状态特征维度n、动作集A、步长α、衰减因子γ、探索率ϵ、当前Q网络Q、目标Q网络Q′、批量梯度下降的样本数m、 目标Q网络参数更新频率C

输出：当前Q网络参数（目标Q网络只是辅助工具）

​ 1. 随机初始化所有状态和动作对应的价值Q，随机初始化当前Q网络的所有参数w，初始化目标Q网络Q′的参数w′=w，清空经验池D

​ 2. for i in [ 1, T ]:

​ a）初始化S为当前序列的第一个状态，求其特征向量 ϕ(S)

​ b）把 ϕ(S) 输入当前Q网络，得到所有动作对应的Q值输出，用 ε-greedy 策略从中选择出动作 A

​ c）执行动作 A，由环境得到新状态 S‘ 对应的特征向量 ϕ(S’)、奖励 R、终止标志 is_end

​ d）将 { ϕ(S)，A，R，ϕ(S‘)，is_end } 这个五元组存入经验池 D

​ e）前进一步：S = S’

​ f）从经验池中采集m个样本 { ϕ(Sj)，Aj，Rj，ϕ(Sj‘)，is_endj }，j = 1,2,3…，把S‘ 和A’ 输入目标Q网络结合贪婪策略计算当前目 标Q值 yj：

​ （注意：公式里的是Q’ 不是Q )

​ g）把S‘ 和A’ 输入当前Q网络求Q估计值，由目标Q值和Q估计值求损失函数Loss Function，然后梯度反向传播更新当前Q 网络参数w

​ h）if i%C == 0：更新目标Q网络参数w’ = w

​ i）if S’是终止状态，break；else 跳回步骤b

​ （注意，f步用的是目标Q网络、g步用的是当前Q网络。另外，实际应用中为了算法较好的收敛，探索率ϵ需要随着迭代变小 ）
 

小结

​ Nature DQN 对 普通DQN 做了相关性方面的改进，这个改进虽然不错，但是仍然没有解决DQN的 很多问题，比如：

1） 目标Q值的计算是否准确？全部通过max Q来计算有没有问题？

2） 从经验池随机采样的方法好吗？按道理不同样本的重要性是不一样的。

3） Q值代表状态动作的价值，那么单独动作价值的评估会不会更准确？

第一个问题对应的改进是Double DQN, 第二个问题的改进是Prioritised Replay DQN，第三个问题的改进是Dueling DQN。

Double DQN算法

概述

DDQN的优化点：

​ 在DDQN之前，基本上所有的目标Q值都是通过贪婪法直接得到的，无论是Q-Learning、普通DQN 还是 Nature DQN。比如对 于Nature DQN，虽然用了两个Q网络并使用目标Q网络计算目标Q值，其第 j 个样本的目标Q值的计算还是贪婪法得到的：

​

​ 使用max虽然可以快速让Q值向可能的优化目标靠拢，但是很容易过犹不及，导致过度估计(Over Estimation)。所谓过度估计就 是最终得到的算法模型有很大的偏差(bias)。而DDQN通过解耦目标Q值动作的选择和目标Q值的计算这两步，来达到消除过度估计的 问题。

DDQN建模——Q值与动作解耦:

​ DDQN 和 Nature DQN一样，也有一样的两个Q网络结构。在 Nature DQN 的基础上，通过解耦目标Q值动作的选择和目标Q值的计算这两步，来消除过度估计的问题。

​ Nature DQN对于非终止状态，其目标Q值的计算式子是：

​

​ 在DDQN这里，不再是直接在目标Q网络里面找各个动作中最大Q值，而是先把S‘ 输入当前Q网络中找出最大Q值对应的动作amax(S′j,w)，即：

​

​ 然后利用这个选择出来的动作amax(S′j,w)在目标网络里面去计算目标Q值。即：

​

​ 综合起来写就是：

​

​ 动作A’ 是在当前Q网络对经验池样本S‘ 的输出中选择，然后用目标Q网络对A‘ 和S’ 算目标Q值。

算法流程

输入：迭代轮数T、状态特征维度n、动作集A、步长α、衰减因子γ、探索率ϵ、当前Q网络、目标Q网络、批量梯度下降的样本数m、目标Q网络参数更新频率C

输出：当前Q网络参数

​ 1. 随机初始化所有状态和动作对应的价值Q，随机初始化当前Q网络的所有参数w，初始化目标Q网络Q′的参数w′=w，清空经验池D

​ 2. for i in [ 1, T ]:

​ a）初始化S为当前状态序列的第一个状态, 拿到其特征向量 ϕ(S)

​ b）把ϕ(S)输入当前Q网络，得到所有动作对应的Q值输出，用ε-greedy策略从中选择出动作 A

​ c）执行动作 A，由环境得到新状态 S‘ 对应的特征向量 ϕ(S’)、奖励 R、终止标志 is_end

​ d）将 { ϕ(S)，A，R，ϕ(S‘)，is_end } 这个五元组存入经验池 D

​ e）前进一步：S = S’

​ f）从经验池中采集m个样本 { ϕ(Sj)，Aj，Rj，ϕ(Sj‘)，is_endj }，j = 1,2,3…，用Q值与动作解耦的思想计算目标Q值：

​

​ g）用当前Q网络求Q估计值，由目标Q值和Q估计值求损失函数 Loss Function，然后梯度反向传播更新当前Q网络参数 w

​ h）if i%C == 0：更新目标Q网络参数w’ = w

​ i）if S’是终止状态，break；else 跳回步骤b

​ （注意，f步两个网络都用了、g步只用到了当前Q网络。另外，实际应用中为了算法较好的收敛，探索率ϵ需要随着迭代变小 ）

Prioritized Replay DQN算法

概述

Prioritized Replay DQN的优化点：

​ 普通DQN、Nature DQN、DDQN等都是通过经验回放来采样，进而做目标Q值的计算的。在采样时经验池里的所有样本都有相 同的被采样概率。但是注意到在经验池里面的不同的样本由于TD误差的不同，对反向传播的作用是不一样的。TD误差越大，对反向 传播的作用越大。而TD误差小的样本对反向梯度的计算影响不大。在Q网络中，TD误差就是目标Q网络计算的目标Q值和当前Q网络 计算的Q值之间的差距。这样如果TD误差的绝对值|δ(t)|较大的样本更容易被采样，则算法会比较容易收敛。

Prioritized Replay DQN建模:

​ 1. 经验池优化：

​ Prioritized Replay DQN的经验池中每个样本的优先级正比于TD误差绝对值|δ(t)|。由于引入了经验回放的优先级，Prioritized Replay DQN的经验池和之前的其他DQN算法的经验池不一样，因为这个优先级大小会影响它被采样的概率。在实际使用中，通常使 用SumTree这样的二叉树结构来做带优先级的经验回放池样本的存储：

​

​ 所有的经验回放样本只保存在最下面的叶子节点上面，一个节点一个样本，内部节点不保存样本数据。叶子节点除了保存数据 以外，还要保存该样本的优先级数值（TD误差）。对于内部节点每个节点只保存自己的儿子节点的优先级值之和。以上面的树结构 为例，根节点是42，如果要采样一个样本，可以在[0,42]之间做均匀采样，采样到哪个区间，就是哪个样本。

​ （注意：当Q网络参数进行了梯度更新后，需要重新计算TD误差，并将TD误差更新到SunTree上面 ）

​ 2. Loss Function优化：

​ 通常使用的损失函数：

​

​ 考虑了样本优先级的损失函数要加上优先权重因子：

​

​ 其中wj是第j个样本的优先级权重，由TD误差|δ(t)|归一化得到
 

算法流程（集成了DDQN）

输入：迭代轮数T、状态特征维度n、动作集A、步长α、采样权重系数β、衰减因子γ、探索率ϵ、当前Q网络、目标Q网络、批量梯度下降的样本数m、目标Q网络参数更新频率C、SumTree的叶子节点数S

输出：当前Q网络参数

​ 1. 随机初始化所有状态和动作对应的价值Q，随机初始化当前Q网络的所有参数w，初始化目标Q网络Q′的参数w′=w

​ 2. 初始化经验池SumTree的默认数据结构，SumTree的S个叶子节点的优先级pj都初始化为1

​ 3. for i in [ 1, T ]:

​ a）初始化S为当前状态序列的第一个状态, 拿到其特征向量 ϕ(S)

​ b）把ϕ(S)输入当前Q网络，得到所有动作对应的Q值输出，用ε-greedy策略从中选择出动作 A

​ c）执行动作 A，由环境得到新状态 S‘ 对应的特征向量 ϕ(S’)、奖励 R、终止标志 is_end

​ d）将 { ϕ(S)，A，R，ϕ(S‘)，is_end } 这个五元组存入SumTree

​ e）前进一步：S = S’

​ f）从SumTree中依概率 P(j) = pj / ∑(pi) 采集m个样本 { ϕ(Sj)，Aj，Rj，ϕ(Sj‘)，is_endj }，j = 1,2,3…，用Q值与动作解耦的 思想计算目标Q值：

​

​ g）用当前Q网络求Q估计值，由目标Q值和Q估计值求带优先权重因子wj的损失函数 Loss Function，然后梯度反向传播更新当 前Q网络参数 w，其中优先权重因子的公式为：

​

​ h）用更新参数后的当前Q网络重新计算经验池中每个样本的Q估计值，然后用目标Q值和新的Q估计值算出新的TD误差作为优先 级更新SumTree

​ i）if i%C == 0：更新目标Q网络参数w’ = w

​ j）if S’是终止状态，break；else 跳回步骤b

​ （注意，f步两个网络都用了、g步只用到了当前Q网络。另外，实际应用中为了算法较好的收敛，探索率ϵ需要随着迭代变小 ）

Dueling DQN算法

概述

Dueling DQN的优化点：

​ DDQN中通过优化目标Q值的计算来优化算法，Prioritized Replay DQN中通过优化经验回放池按权重采样来优化算法，而在 Dueling DQN中通过优化神经网络的结构来优化算法。

Dueling DQN网络结构:

​ Dueling DQN将Q网络分成两部分。第一部分仅与状态S有关，与具体要采用的动作A无关，叫做价值函数部分，记做V(S,w,α)。 第二部分同时与状态状态S和动作A有关，这部分叫做**优势函数(Advantage Function)**部分，记为A(S,A,w,β)。

​

​ 最终价值函数可以重新 表示为：

​

​ （其中，w是公共部分的网络参数，而α是价值函数部分独有的网络参数，β是优势函数部分独有的网络参数 ）

​ 考虑到这个式子无法辨识最终输出里面V(S,w,α)和A(S,A,w,β)各自的作用，为了可以体现这种可辨识性(identifiability),实际使用的 组合公式如下：

​

​ （其实就是对优势函数部分做了中心化的处理 ）

总结

​ 这里一共总结了5种DQN算法：普通DQn、Nature DQN、DDQN、Prioritized Replay DQN、Dueling DQN，目前使用的比较主流的是后面三种算法思路，这三种算法思路也是可以混着一起使用的，相互并不排斥。

​ 当然DQN家族的算法远远不止这些，还有一些其他的DQN算法没有总结，比如使用一些较复杂的CNN和RNN网络来提高DQN的表达能力，又比如改进探索状态空间的方法等，主要是在DQN的基础上持续优化。

​ DQN算是深度强化学习的中的主流流派，代表了Value-Based这一大类深度强化学习算法。但是它也有自己的一些问题，就是绝大多数DQN只能处理离散的动作集合，不能处理连续的动作集合。虽然NAF DQN可以解决这个问题，但是方法过于复杂了。而深度强化学习的另一个主流流派Policy-Based而可以较好的解决这个问题。