深度强化学习DQN系算法理解

致谢
进行DQN方法整理时，主要对原文进行了学习，并参考了几位作者的笔记，在此一并表示感谢。索引网页如下：
https://www.jianshu.com/p/6fe18d0d8822
https://www.jianshu.com/p/0fb311d96da4
https://www.cnblogs.com/pinard/p/9797695.html
https://blog.csdn.net/mike112223/article/details/92798121

【Volodymyr Mnih, Koray Kavukcuoglu, David Silver, et al. Playing Atari with Deep Reinforcement Learning. arXiv preprint arXiv:1312.5602, 2013】【Mnih, V., Kavukcuoglu, K., Silver, D. et al. Human-level control through deep reinforcement learning. Nature 518, 529–533 (2015).】【Hado van Hasselt, Arthur Guez, David Silver. Deep Reinforcement Learning with Double Q-learning. arXiv preprint arXiv: 1509.06461, 2015】

1.将原始Q-学习问题转化为深度学习问题

核心是将Q-Table的更新问题变成一个函数拟合问题，使得相近的状态得到相近的输出动作。通过更新参数 θ 使Q函数逼近最优Q值 。DQN就是要设计一个神经网络结构，通过函数来拟合Q值：

2. DL和RL结合的问题与解决方法

存在问题：

①DL需要大量带标签的样本进行监督学习；RL只有reward返回值，而且伴随着噪声、延迟（过了几十毫秒才返回）、稀疏（很多State的reward是0）等问题；

②DL的样本独立；RL前后state状态相关；

③DL目标分布固定；RL的分布一直变化，比如你玩一个游戏，一个关卡和下一个关卡的状态分布是不同的，所以训练好了前一个关卡，下一个关卡又要重新训练；

④使用非线性网络表示值函数时可能过高估计动作价值。计算Q-target值的过程如下，

计算Q-target值与取价值最大动作的网络为同一参数网络，可能导致对动作价值的过高估计（即评价动作价值偏高时，一定会采用评估偏高的动作。）

解决方法：

（1）基于Q-Learning的reward构造标签（对应问题①）

基于Q-Learning来确定Loss Function，使Q-target值和Q-eval值相差越小越好。其中，yi是根据上一个迭代周期或者说target-net网络的参数计算出的Q-target值，跟当前网络结构中的参数无关

（2）通过experience replay（经验池）的方法来解决相关性及非静态分布问题（对应问题②、③）

每个时间步agent与环境交互得到的转移样本 (st,at,rt,st+1) 储存到回放记忆单元形成minibatch，训练时就随机拿出一些来训练。

（3）使用双神经网络结构估计Q值（DDQN）

双网络结构是在Nature 2015年DQN版本中提出的改进，使用两个网络，Target_net用于计算Q-target；Eval_net用于估计Q值，即 。时刻更新Target_net参数，每过C步将Target_net参数赋给Eval_net（对应问题④）。

3.算法框架伪代码

NIPS-2013版DQN

Nature 2015版DDQN

说明：st+1 = st, at, xt+1，是因为此处状态表示为一个序列，即st = x1,a1, x2, a2,…, at-1, xt，所以依据马尔可夫性质，st+1状态只与st相关，有下一时刻序列为当前时刻序列加当前时间动作与观测。

4.DQN深度改进之Prioritised Replay

【Tom Schaul, John Quan, Ioannis Antonoglou and David Silver. PRIORITIZED EXPERIENCE REPLAY. ICLR 2016】

问题介绍：经验回放的功能主要是解决相关性及非静态分布问题。具体做法是把每个时间步agent与环境交互得到的转移样本 (st,at,rt,st+1) 储存到回放记忆单元，要训练时就随机拿出一些（minibatch）来训练。但是在奖励十分少的时候，经验回放学习速度会非常慢。Blind Cliffwalk环境可以说明：设第n个状态才能得到第一个非零反馈，每个状态的转移概率为0.5，则得到第一个非零反馈的概率为2^-n。

解决方法：

不再对minibatch进行随机采样，而是依据TD-error值设定优先级进行采样（TD-error值越大则表示Q-target与Q-evaluator之间的价值评估的差距越大，从而在梯度上更具学习价值，从而避免了对无效转移样本的学习）。

关键技术①——退火偏差

依据优先级来进行采样也带来了新的问题，由于TD-error值是不断更新的，则优先级分布是不断更新，因而产生了系统性偏差。因为，利用随机梯度方法对期望值的估计，要求每步更新必须是建立在同一分布期望的基础之上。为了抵消偏差，引入了重要性采样权重概念：

可见，其中β为重要性权重控制参数，当β=1时等效为无优先级权重，即所有采样权重相同，不对特定优先级采样的权重进行加权，可以完全补偿非归一化的概率值P(i) 对梯度的影响。同时将原有TD-error值加入权重后在每个minibatch中不断累积后用于梯度更新，优先级越高则对于梯度更新的方面回调越大。在实际操作中常常将β定义为指数形式，使其从某一初始值β0一直减少到1。

其中，优先度控制参数α控制了优先度的参考比重，当α=0时退化为随机采样方式，损失函数定义为 ，k为minibatch的采样数，K为经验池的总记录时间步长（每隔K个时长对经验池进行更新，而后按minibatch规模采样），N表示记录的转移样本总数。

关键技术②——SumTree总和二叉树

在通过TD-error 确定优先级p的基础上，如果每次抽样都需要依据p对所有样本排序，这将消耗大量算力。为快速实现依据优先级的采样，提出SumTree方法。

在SumTree中，所有的经验回放样本只保存在最下面的叶子节点上面，一个节点一个样本。内部节点不保存样本数据。而叶子节点除了保存数据以外，还要保存该样本的优先级，就是图中的显示的数字。对于内部节点每个节点只保存自己的儿子节点的优先级值之和，如图中内部节点上显示的数字。

这样保存方便采样。如例，根节点是42，如果要采样一个样本，那么我们可以在[0,42]之间做均匀采样，采样到哪个区间，就是哪个样本。比如我们采样到了26， 在（25-29）这个区间，那么就是第四个叶子节点被采样到。如果要采样多个样本，则抽样时,将 p 的总合除以 batch size, 分成 batch size 个区间, (n=sum§/batch_size). 如上图，所有 node 的 priority 加起来是42，如果抽6个样本，则此时的区间拥有的 priority 可能是这[0-7], [7-14], [14-21], [21-28], [28-35], [35-42]。然后在每个区间里随机选取一个数。例如在第4区间 [21-28] 里选到了24, 就按照这个 24 从最顶上的42开始向下搜索. 首先看到最顶上42下面有两个child nodes，拿着手中的24对比左边的child 29，若左边的child 比自己手中的值大，则走左边这条路，接着再对比29下面的左边那个点13，手中的24比13大，则走右边的路并且将手中的值根据 13 修改变成 24-13 = 11。接着拿着11和13左下角的12比，12 比 11 大，则选 12 当做这次选到priority,并且也选定 12 对应的数据。

5. DQN深度改进之Dueling Network（竞争网络）

【ZiyuWang ZIYU, Tom Schaul SCHAUL, Matteo Hessel MTTHSS, Hado van Hasselt HADO, Marc Lanctot, LANCTOT. Dueling Network Architectures for Deep Reinforcement Learning. arXiv preprint arXiv: 1511.06581, 2015】

Q值可以拆分为状态价值函数与相关状态下特定动作的优势函数之和，其中价值描述的是对某一状态的评估，而优势函数描述的是某一特定动作相较于其他动作价值优势：

两个网络在使用上各有侧重，一个善于观察对状态价值影响的特征，而另一个善于观察对于各动作优势影响的特征。如果能够分别对状态价值与动作优势进行学习，则便能够摆脱动作对价值的影响，并真正学习到哪个状态是有价值的，这样有助于在动作不会对环境产生价值影响的情形下来判断状态的价值。

如上图，在有其他车辆的情形下优势函数更多考虑车辆的影响，在无车情形下价值函数只用考虑道路变化的影响。

但是，直接利用V + A形式计算Q值会出现unidentifiable问题，即一个Q值会同时对应多组V和A值，无法进行学习训练。

为解决以上问题，Q值在传统定义的基础上进一步减去最大优势函数价值：

当动作为最优动作时，Q值与A值均达到最大，且有两A值差为0

下图上侧描述了传统DQN方法网络设计架构，下侧描述了V + A形式网络设计架构。在看完算法思想时，容易误以为单独训练V或者A价值函数后再相加，但实际上DuelingDQN是一个end to end的训练网络，同之前DQN的没有任何区别，两部分隐藏层语义是通过直接训练公式（2）所代表的Q值后，人为分析并定义出来的。

进一步改进可使用优势函数的平均值代替上述的最优值：

虽然如此一来值函数V和优势函数A不再能够在语义上表示完美表示为值函数和优势函数，但是优势函数只需要平均值进行变动，相较于最大值提高了稳定性。