DQN的全称是Deep Q Network，其中的Q就是指Q-Learning。从名字上就能看出，这是一种把Q-Learning和DNN[Deep Neural Network]结合起来的模型构架。

Function Approximation

在之前介绍的强化学习方法，都依赖于对价值函数的计算，无论通过计算状态转移概率和对应奖励还是通过试验和环境交互简介获得，都需要存储价值函数的结果。当遇到的问题相对较小，需要存储的价值函数结果不多的情况下，是可以的，但是在显示环境中多是大规模问题，存储所有的价值函数结果是不现实。所以，更实际的方法是采用价值函数逼近的思想。具体来说，就是获得足够多的最优参数，然后通过这些最优参数，拟合出整个价值函数背后的规律，这样，不需要存储所有的价值函数结果，也可以获得一个近似准确的估计用于计算，只要这个估计值不偏离真实值太多，那得出的策略就足够好。

显然的，函数逼近的过程是一个监督学习的过程，类似，使用一些已知状态$s$，动作$a$，和最后的价值结果$q(s, a)$，然后来拟合一个价值曲线。当获得一个新的状态和动作，就可以通过这个曲线直接获得价值的估计结果。具体来说，对于强化学习，近似函数根据输入和输出的不同，可以有以下三种架构，

DQN with Regression

左图表示输入为状态$s$，输出为这个状态的近似价值[V-function]。中间图表示输入为状态$s$和行为$a$，输出状态行为对的近似价值[Q-function]。右图表示输入为状态$s$，输出为一个向量，向量中的每一个元素是该状态下采取一种可能行为的价值估计。而用于拟合的近似函数常用的是线性回归和神经网络。当然，任何可以进行拟合近似的机器学习算法模型都可以作为近似函数。

Gradient Update

把显式精确存储的价值函数用近似函数来估计，也就是把原来的问题转移到怎么使得近似变得更加的准确的问题，因为一旦估计准确就可以沿用之前的思路求解。如此依赖，跟一般机器学习的套路一样，我们要定义一个目标函数，并对这个目标函数进行优化迭代学习直到收敛，求得最优。但需要注意强化学习里只有即时奖励，没有监督数据。我们要找到能替代状态价值$v_{\pi}(S)$的目标值，以便来使用监督学习的算法学习到近似函数的参数。

我们可以使用机器学习中常见的均方差作为目标函数，然后进行优化找到参数向量$w$，也就是最小化近似函数$\hat{v}(S,w)$与实际函数$v_{\pi}(S,w)$的均方差，如下所示，

\[J(w) = \mathbb{E}[(v_{\pi}(S) - \hat{v}(S,w))^2]\]

可以直接套用常用的随机梯度下降方法进行目标函数更新。如此我们可以对先前的MC方法和TD方法进行改造。

首先MC方法$G_t$表示状态$S_t$对应的return，即奖励值的总和。而之前我们就知道，$G_t$是$v_{\pi}(S_t)$的无偏估计，因此MC方法的标签数据就可以设为$G_t$，而又因为这个label是无偏的估计，所以在梯度下降版本的MC方法中，价值函数估计算法是可以确定找到局部最优解。

MC Gradient Update

对于TD来说，我们用采用bootstrapping得到价值估计值[也就是通过单步采样估计整个episode的，类似resampling，因为一个episode本身就是对全部epsiode的sampling]，那么这个估计值就可以作为label进行训练。但是这里的label和参数是$w_t$不相互独立，因为对于用bootstrapping得到的价值估计值公式为

\[\mathbb{E}_{\pi} [R_{t+1} + \gamma \hat{v}(S_{t+1}, {\color{red} w}) \mid S_t]\]

而恰恰是因为这里的label和参数是相关的，故在代入梯度更新公式后，得到的只是部分梯度的下降，而不是真正的梯度下降，也就是半梯度方法[semi-gradient methods]。

TD Semi-Gradient Update

在更新的时候一般都是采用mini-batch，就像训练深度神经网络模型一样，其好处就是在用python或其他语言编程时，可以用矩阵的形式来进行运算，使得计算效率变高而且有时候还能提高算法的稳定性。

Deep Q Network

Q-Learning是一种off-policy离线学习，它能学习当前经历着的,也能学习过去经历过的, 甚至是学习别人的经历。而DQN，就是在传统Q-Learning的基础上做了三个改进:

  1. DQN利用深度卷积神经网络来逼近值函数，线性逼近不同，这里是用神经网络来进行的非线性逼近，而且用的是强大的深度卷积神经网络，也就是CNN。

  2. DQN利用了经验回放[replay]对强化学习的学习过程进行训练，DQN有一个记忆库用于学习之前的经历。所以每次DQN更新的时候，都可以随机抽取一些之前的经历进行学习. 随机抽取这种做法打乱了经历之间的相关性, 也使得神经网络更新更有效率。

  3. DQN是一个由两个网络组成的模型：主网络和目标网络。主网络负责训练，目标网络负责提供训练用的label。这两个网络结构相同且初始参数相同，但每隔一段时间，目标网络会被和主网络同步参数。这样的方式也能让训练变得更加有效，更具有鲁棒性。

具体算法如下，

DQN

  1. 初始化一个replay memory $D$，大小为$N$。初始化一个参数为$\theta$的主网络[action-value function]$Q$，以及一个参数为$\theta^{-}$的目标网络[target action-value function]$\hat{Q}$。此时两个网络结构和参数一致。

  2. 开始一个$M$次episode的循环，对于每个episode中初始化一个$T$次的循环，每次循环对应于一个step。

  3. 对于每一个step，有$\varepsilon$的概率去做一个随机的动作$a_t$，有$1-\varepsilon$的概率选择动作\(a_t = \operatorname{arg max}_{a}Q(\phi(s_t), a; \theta^{-})\)。之后，执行动作$a_t$，并且获得$r_t$，并进行状态移动，并把每一步以$\{ s_t, a_t, r_{t+1}, s_{t+1} \}$的形式存储在内存里。

  4. 从replay memory $D$中随机抽取一个batch的$\{ s_t, a_t, r_{t+1}, s_{t+1} \}$，并根据$y_i$值[也就是label值]，也就是如果episode结束则$y_j = r_j$，否则，$y_j$由目标网络[Target Action-Value]给出，而不是由主网络[Action-Value]给出。然后使用batch和$y_i$的进行策略评估与更新。

  5. 然后每$C$ step，主网络和目标网络进行参数同步。如此往复，直到遍历所有episode。

DQN首次提出是由DeepMind在2013年NIPS的大会上，当时并没有目标网络的概念。2015年, DeepMind对2013版DQN进行了一次重大的改造，并在Nature上披露了这个模型，目前提到DQN一般指的这个DQN。这次改造对深度强化学习领域的研究有比较深远影响，其首先提出的主网络和目标网络的双网络设计，直到现在都被很多重要的深度强化学习方法所采用。

Reference:

  1. 理解强化学习知识之值函数逼近思想及DQN, https://zhuanlan.zhihu.com/p/32204924
  2. Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
  3. 高扬，叶振斌，白话强化学习与PyTorch