Paper Deep Q-Network

这篇论文是 Volodymyr Mnih 在 nips2013 上的一篇论文，差不多是 DQN 的开山之作，另一篇是 nature2015 年的论文《Human-level control through deep reinforcement learning》，这两篇论文在强化学习领域也算是一座里程碑，本文将对 nips2013 这篇论文中涉及到的一些开创性思想进行总结。

Abstract

这是第一篇通过深度学习模型利用强化学习来直接从高维传感器输入，学习控制策略的论文。该模型是一个基于 CNN 搭建的，利用 Q-learning 的变体进行学习的模型。输入是原始像素，也就是当前状态，输出则是 Q 值，其实也就是利用神经网络来近似 Q(s,a)函数。这篇论文在 Atari 2600 游戏上进行了实验，在没有对结构和算法进行特殊调整的情况下就取得了很好的效果（比以前的算法和人类表现都要好）

1.Introduction

直接从高维度的传感器数据（语音，图像等）来学习控制策略对于 RL 是一个长期的挑战，大多数成功的 RL 应用都需要手工的特征调整，显然这种应用的效果就严重依赖于特征选取的质量。然而深度学习使得从高维数据中提取特征变得可能，那么这二者的结合应该能取得很好的效果。

然而利用深度学习来做 RL 也有很多挑战，现在的深度学习基本都大量依赖于手工标注的数据，而 RL 并不是这种直接的一对一的关系，而是需要在很多次迭代之后才能得到一个标量的 reward 值，而这个 reward 通常由是稀疏的并且充满噪声的，而且具有很长的延时，在 RL 中得到 reward 之前通常需要上千步的操作，和常规的数据和标记一对一的情况相比显得非常迟钝。另外在深度学习中常要求训练数据之间是相互独立的，然而 RL 中的数据则是高度相互依赖的状态序列，并且 RL 在学习到新的动作的时候数据分布会发生改变，这对于需要固定数据分布的深度学习算法可能会造成病态的效果。主要问题就在于数据相关性/数据分布。

这里提出了一种基于 CNN 的网络结构，通过引入一种 experience replay 的机制来缓解数据相关性和数据分布的问题，experience replay 通过在 Transition 中进行随机采样来对数据的分布进行平滑。在训练过程中，模型得到的数据和人类是一样的，包括视频输入，reward，终止信号，以及可能的操作集。

2.Background

这里使用的雅达利模拟器进行训练，需要注意的是 reward 也就是游戏分数是依赖于先前的动作序列的和观测的，很可能在几千步之后才会得到反馈。然而从单次的屏幕观测并不能完全理解当前的状态，于是需要用一个序列来表示当前状态，即$s_{t}=x_{1},a_{1},x_{2},...,a_{t-1},x_{t}$，利用一个屏幕观测和动作的序列来表示当前状态，然后依赖于这些序列来学习游戏策略。模拟器中的所有序列都假设会在一个有限的时间步内终止，那么可以在这些序列上应用标准的强化学习方法。

另外假设 reward 随着时间步的增加是逐渐减少的，即采用一个衰减因子来对 reward 进行处理，累计 Reward，$R_{t}=\sum^{T}_{t'=t}\gamma^{t'-t}r_{t'}$，其中$T$是游戏终止的时间步。定义$Q^{*}(s,a)$为最优策略下的 Q 值函数，即$Q^{*}(s,a)=max_{\pi}E[R_{t}|s_{t}=s,a_{t}=a,\pi]$，另外最优的 Q 函数遵守贝尔曼方程，其思路如下：如果对于下一个序列$s'$和所有可能的动作$a'$，其$Q(s',a')$是已知的，那么$Q^{*}(s,a)$则是最大化期望$r+\gamma Q^{*}(s',a')$，即

$$Q^{*}(s,a)=E_{s'\sim \varepsilon}[r+\gamma max_{a'}Q^{*}(s',a')|s,a]$$

很多 RL 算法背后的思想都是估计 Q 值函数，如果迭代的利用贝尔曼方程，$Q_{i+1}(s,a)=E[r+\gamma max_{a'}Q_{i}(s',a')|s,a]$那么最后当$i\to\infin$可以收敛到$Q^*$，然而在实际应用中这是不切实际的，因为 Q 函数是对每个序列单独估计的，没有泛化能力。取而代之的是利用一个函数来近似最优 Q 函数，即$Q(s,a;\theta)=Q^*(s,a)$，在这里采用神经网络对其进行估计，即损失函数为：

$$L_{i}(\theta_{i})=E_{s,a\sim p(\cdot)}[(y_{i}-Q(s,a;\theta_{i}))^2]$$

其中$y_{i}=E_{s'\sim \varepsilon}[r+\gamma max_{a'}Q(s',a';\theta_{i-1})|s,a]$，在代码实现中$Q(s,a;\theta_{i})$与$Q(s,a;\theta_{i-1})$通常定义两个不同的网络来进行实现，在 pytorch 的 tutorial 中采用了 policy_net 和 target_net 两种网络来实现。另外在进行动作选择的时候采取一定的概率来平衡”探索“和”利用“，即$\epsilon$-greedy 算法，在训练的开始阶段尽量利用收益大的动作，在后期则更多的进行探索，即$\epsilon$是一个从大到小进行衰减的过程。

3.Related Work

这里暂时先不做过多介绍，等买的书到了再进行补充

4.Deep Reinforcement Learning

这一章主要就是介绍核心的算法，首先需要认识到利用深度学习来提取特征是优于手工进行特征处理的。DQN 的算法框架的伪代码如下

这里再度介绍一下 replay memory 的好处，1.每一次的状态转移都有可能作为网络权重更新的数据。2.由于样本之间的强关联性，直接从连续样本中进行学习是低效的，打破这种关联性而进行随机采样可以减少升级时的偏差。3.在 learning on-policy 的时候，当前的参数产生了下一批用于参数更新的样本，比如当前参数下获得最大 reward 的动作是向左，那么后续将一直得到左边的样本，如果以后的最佳动作变为了向右，那么训练分布也同样会发生改变。很容易就会发现一种恶性循环并且陷入局部最优点。通过 replay 可以将行为分布在多个之前的状态之间进行平均，并且将学习过程进行平滑而避免发散。因此需要 learning off-policy，区别在于产生动作的 policy 和网络参数更新的 policy 是否相同，因为 Q-learning 中更新时的 policy 使用了 max 操作，而产生动作的 policy 并不一定使用 reward 最大的动作，Q-learning 是 off-policy learning 的经典算法。

对于这里的神经网络，采取 state 作为输入，输出的 n 个节点对应于 n 个可能的 action 造成的 reward，这样通过一次计算便可以计算出每个 action 对应的 reward。

对于后面的实验章节，时间比较久了不再赘述。