基础（Q-Learning）

Q即为Q（s,a），就是在某一时刻的 s 状态下，采取动作a动作能够获得奖励的期望。环境会根据智能体的动作反馈相应的奖励 r。算法的主要思想就是将状态（state）与动作（action）构建成一张Q-table来存储Q值，然后根据Q值来选取能够获得最大的收益的动作。Q-Learning的算法如下：

DQN

DQN将卷积神经网络（CNN）和Q-Learning结合起来，CNN的输入是原始图像数据（作为状态State），输出则是每个动作Action对应的值函数（Q值）。DQN（Deep Q Network）是深度强化学习的开山之作。

深度学习与强化学习结合的问题：

  1. 强化学习没有标签，只有reward返回值，且伴随噪声、延迟（一段时间后返回）、稀疏（很多State的reward是0）等问题。
  2. 深度学习的样本独立，强化学习前后的state相关。
  3. 深度学习目标分布固定；强化学习的分布一直变化，比如一个游戏，一个关卡和下一个关卡的状态分布是不同的，所以训练好了前一个关卡，下一个关卡又要重新训练。
  4. 过往的研究表明，使用非线性网络表示值函数时出现不稳定等问题。

解决方法：

  1. 通过Q-Learning使用reward构造标签。
  2. 通过experience replay（经验回放）的方法来解决相关性及非静态分布问题。具体做法是把每个时间步agent与环境交互得到的转移样本 (st,at,rt,st+1) 储存到回放记忆单元，训练时随机拿出一些batch来训练，避免相关性的问题。
  3. 使用一个CNN（MainNet）产生当前Q值，使用另外一个CNN（TargetNet）产生Target Q值。开始时TargetNet的参数固定，只更新MainNet的参数，每经过N轮迭代，将MainNet的参数复制给TargetNet。引入TargetNet后，可使一段时间内Target Q值保持不变，一定程度降低了当前Q值和目标Q值的相关性，提高了算法稳定性。
  4. 实验使用多个Atari 2600 游戏（Breakout、Galaxy Invaders等）做基准测试。

**优点：**算法采用端到端的训练方式，无需人工提取feature。通过不断训练，可以实时生成无尽的样本用于有监督训练。

**缺点：**由于输入的状态是短时的，所以只适用于处理短期记忆的问题，无法处理需要长时间经验的问题。使用CNN训练不一定能收敛，需要对网络的参数进行精良的设置。

**可改进方向：**设计更好的CNN网络，LSTM（用于长期记忆），Q值算法改进，采样方法改进

Mnih V, Kavukcuoglu K, Silver D, et al. Playing atari with deep reinforcement learning[J]. arXiv preprint arXiv:1312.5602, 2013.

Mnih V, Kavukcuoglu K, Silver D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529.

Double DQN

问题提出：

Double DQN是DQN的一种改进，旨在解决DQN训练过程中存在的过估计（Over estimating）问题。在训练过程中，DQN会直接选取目标网络（Target Q Network）中下一个State各个Action对应的Q值最大的那一个，由于Target也是由网络估计而来，所以存在过估计问题。

解决方法：

DDQN通过解耦目标Q值动作的选择和目标Q值的计算这两步，来达到消除过度估计的问题。DQN与Double DQN的Target计算方式比较如下：

DQN中，Target中Action的Q值由目标网络计算，而在Double DQN中，Target中Action的Q值由预测网络（Predict Q Network）计算，选取最大的那个Q值对应的Action，然后再使用目标网络计算Q值。这两个网络起到一个制衡的作用，即使预测网络高估了某一个action的Q值，再经过目标网络的Q值计算后也可予以平衡，反之亦然。这种方法提高了训练DQN的稳定性和速度，降低Q 值的评估误差。

Van Hasselt H, Guez A, Silver D. Deep reinforcement learning with double q-learning[C]//Thirtieth AAAI conference on artificial intelligence. 2016.

Prioritized experience replay

问题提出：

experience replay（经验回放）采用均匀采样，对所有样本一视同仁。但直觉上来说，各个样本的重要性应是不同的，有的样本“信息量”较大，有的样本则没什么用。以下图的环境（n个状态，2个动作，初始状态为1）为例，沿绿色箭头的reward是1，其余情况reward均为0。假如采用随机策略从初始状态开始走n步，我们能够获得有用的信息（reward非0）的可能性为很低。这样的话学习效率就会很低。

解决方法：

使用experience replay可以在两个层面上进行设计：存储哪些样例以及回放哪些样例（以及如何操作），论文使用后者的优化方法。具体来说，抽样时按照样本优先级来抽，优先级排序用的是TD-error（时序差分误差）来进行衡量，也就是 目标Q值和估计Q值之差。如果 TD-error越大, 就代表预测精度还有很多上升空间, 那么这个样本就越需要被学习, 也就是优先级越高。

Schaul T, Quan J, Antonoglou I, et al. Prioritized experience replay[J]. arXiv preprint arXiv:1511.05952, 2015.

Dueling DQN

问题提出：

在许多基于视觉感知的深度强化学习任务中，不同的状态动作对的值函数是不同的。但是在某些状态下，值函数的大小与动作无关。所以对于许多状态，没有必要预测每一个 action的 value。

解决方法：

DQN和Dueling DQN的网络结构比较如上图所示。上部分为传统的DQN网络图，下部分为Dueling DQN。Dueling DQN将卷积层提取的抽象特征分流到两个支路中，一路代表状态值函数 V(s)，表示静态的状态环境本身具有的价值；另一路代表依赖状态的动作优势函数 A(s, a)（Advantage Function），表示选择某个动作的Advantage价值。最后两路合在一起得到每个动作的Q值。

为什么有效果？

Dueling DQN结构的主要优势在于：可以更有效地学习到状态值函数。对于原始的DQN网络，每次更新Q-value时，仅更新其中的一个 action 对应的value，其他 action 对应的 value 保持不变。而在Dueling DQN中，每次更新Q value，V都会随着之更新。这种更加频繁的更新 V 的做法分配了更多的资源给V，所以可以更好的估计状态值。

Dueling-DQN在action的选择较多时优势明显，因为V(s)学习到了许多类似 action的共享的一个 general 的value，当出现许多相似值的action时，能得到更好的策略评估，使得收敛速度更快。

Wang Z, Schaul T, Hessel M, et al. Dueling network architectures for deep reinforcement learning[J]. arXiv preprint arXiv:1511.06581, 2015.