Deep Q-Learning 系列论文漫谈(一) 从Q-Learning到DQN

写在前面的话

这系列博客我以google DeepMind 2013年在NIPS、2015年在Nature发表的 Deep Q-Learning为引子，和大家一起讨论Deep Q-Learning算法和后续改进的文章，本人才疏学浅，能力有限，错误不可避免，希望能和更多热爱Machine Learning的朋友一起交流！

Reinforcement Learning 是 Machine Learnig大家族中很特别的一个成员，它与需要事先准备数据集的监督学习有本质的区别，它强调与环境交互产生的反馈，并且根据反馈自我调节，以获取最大的累积回报。

强化学习在与神经网络结合之前，没有像现在这样收到过关注，虽然之前早有值函数近似方法 (Function Approximation)，而让学者们具有深刻印象的转折点就是2013年Google DeepMind的一个研究小组设计的用深层神经网络去逼近值函数的方法，他们在Atari游戏中，只通过视频图像输入和游戏分数反馈，就取得了人类水平的高分，这一过程并没有经过细致的、针对性的特征设计。此方法一举将强化学习提升到最前沿水平。

（Atari游戏,来自论文 Playing Atari with Deep Reinforcement Learning）

 

他们设计的方法就是 Deep Q-Learning(或者叫DQN，Deep Q-Network)，而后续领域内的大神们各显神通，在此基础上进行魔改强化，让Q-Learning这一经典算法重回大众的视野。Q-Learning的创造者可能也想不到，经过了二十多年，它的后辈们居然在短短四五年内凭借神经网络创造了如此庞大的算法家族：

 

（DQN和后续算法关系图，来自论文 Deep Learning for Video Game Playing）

 

这么多内涵丰富的论文我也看不全，只能是走马观花。其中需要重点关注DQN的三个魔改论文:

• Double DQN
• Dueling DQN
• Prioritized DQN

它们代表了DQN最重要的三个优化方式，我们后面将会一一介绍。

Q-Learning

不那么正式的回顾一下Q-Learning，它在强化学习算法中的分类是:

可以看见Q-Learning是属于值函数近似算法中，蒙特卡洛方法和时间差分法相结合的算法。它在1989年被Watkins提出，可以说一出生就给强化学习带来了重要的突破。它的定义如下：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha[\underbrace{R_{t+1}+\gamma\max_aQ(S_{t+1},a)}_{q*}-Q(S_t,A_t)]$$

这里动作价值Q函数的目标就是逼近最优的$q*$，并且轨迹的行动策略与最终的$q*$是无关的。后面中括号的加和式表示的是 $q*$的贝尔曼最优方程近似形式。

Deep Q-Learning

如果要在连续的状态空间中计算Q函数$Q^{\pi}(s,a)$，使用Q表是不现实的选择，因为连续的状态空间会让Q表的存储空间变得非常大。那么我们可以用一个关于s和a的连续函数$Q_\theta(s,a)$去近似$Q^{\pi}(s,a)$。$Q_\theta(s,a)$ 是一个参数为$\theta$的函数，事已至此，路就很自然走到了神经网络的大门口，近似这种事就是神经网络的老本行。

不管$Q^{\pi}(s,a)$是怎样一个复杂的函数，只要使用Deep Network，就有机会去近似它，说不定还能近似的很好。

如果动作空间A是离散的,共有$m$个动作，$a_1,…,a_m$，那么我们可以定义$Q_\theta$是状态$s$的函数，输出是$m$个向量：

$$Q_\theta(s)=\begin{bmatrix} Q_\theta(s,a_1)\\ \vdots\\ Q_\theta(s,a_m)\\ \end{bmatrix} \approx \begin{bmatrix} Q^\pi(s,a_1)\\ \vdots\\ Q^\pi(s,a_m)\\ \end{bmatrix}$$

神经网络接受状态向量$s$为输入，然后输出的m个向量分别作为真实$Q^\pi$的每一维的近似。

Loss Function

已经确定要使用神经网络近似，我们拿什么作为损失函数来学习它的参数 $\theta$ 呢？既然我们的目标函数$Q^\pi$输出的是连续的数值，就先用平方损失函数写出来：

$$L_i(\theta_i)=E_{s,a\sim\rho(\cdot)}[(y_i-Q(s,a;\theta_i))^2]$$

$L_i(\theta_i)$表示的第$i$次迭代的损失函数。仔细对比Q-Learning的定义，损失函数中的样本真实目标值$y_i$可以写成：

$$y_i=E_{s'\sim E}[r+\gamma\max_{a'}Q(s',a';\theta_{i-1})|s,a]$$

这就是当前时刻状态$s$和动作$a$确定的情况下，执行动作$a$，环境$E$会进入下一个时刻的状态$s’$；然后在$s’$状态下，计算最优动作价值函数$q*$。

以上是2013年论文中的损失函数，我觉得其中有点含混不清的地方是目标值$y_i$中的$\theta_{i-1}$的下标。结合论文的叙述，它的意思是在第$i$次迭代计算$L_i$时，计算目标值使用的$\theta_{i-1}$是上一次迭代更新后的。问题是为什么不用第$i$次的，我查看了Sutton的《Reinforcement Learning》关于TD误差的章节，当前Q值和目标Q值使用的参数都是当前时刻的，并且在论文后面的算法伪代码中也没有关于下标的叙述，于是这个$i-1$下标就成了悬案。

到了2015年，发表在Nature的论文中，增加了Target Net 改进方法，结合经验回放，将损失函数重新写成：

$$L_i(\theta_i)=E_{(s,a,r,s')\sim U(D)}[(r+\gamma\max_{a'}Q(s',a';\theta_{i}^{-})-Q(s,a;\theta_i))^2]$$

其中$(s,a,r,s’)\sim U(D)$表示样本从buffer D中使用统一采样的方式得到。$\theta_i^-$表示Target Net的网络参数，每隔$C$次迭代，就更新为$\theta_i$，并且在两次更新之间它是固定的。这次损失函数的表述更加清晰了。

Target Net / Experience replay

Target Net

2015年的论文中新增了Target Net这一个改进点，目的是为了增加网络训练的稳定性，这个改进点虽然简单，但是要能讲清楚却不容易，涉及到强化学习目前的核心领域：Function Approximation。这个领域目前理论还不完善，有很多开放性问题没有解决，一两句话解释不清楚，但是我们可以通过这个点扩散开，来深入探索Function Approximation中有哪些重要的问题，而且当前的研究进展是怎样的，也是很有意义的。下一章我会尝试讲讲我的理解，望各位朋友指正。

Experience replay

放这个优化点的理由稍微复杂点，作者在论文中写了三个:

1. 让“有用”的样本得到更多的训练次数，提高样本的使用效率。
2. 打破连续采样的样本之间的“correlations”，可以减少训练时的方差。
3. 由于on-policy的学习模式使然(严格来说DQN是 off-policy，但是也是使用自己产生的样本，大致上是一样的)，模型的参数会决定下一时刻的样本分布，这样会让模型陷入比较糟糕的局部最优，使用Experience replay可以减轻这种效应。

相信上面三个理由是不能满足有些朋友的好奇心的，第一条尚可理解，第二条的“correlations”到底是指的什么关系？为什么有关联关系就会引起训练方差大呢？第三条更含糊了，样本分布不同为什么容易陷入局部最优？虽然有简单的例子说明，但是我觉得还不够，还需要深入一些，至少能够说服自己吧。同样的，下一章和Target Net一起说一点我自己的理解。

第二章 Deep Q-Learning 系列论文漫谈(二) 从Target Net和Experience replay聊起

可以参考的文献：

DQN原始论文 Mnih, Volodymyr, et al. “Playing atari with deep reinforcement learning.” NIPS2013

DQN改进版 Mnih, Volodymyr, et al. “Human-level control through deep reinforcement learning.” Nature2015