强化学习-理解Q-learning，DQN，全在这里~

本文简要地介绍强化学习（RL）基本概念，Q-learning， 到Deep Q network（DQN），文章内容主要来源于Tambet Matiisen撰写的博客，以及DeepMind在2013年的文章“Playing Atari with Deep Reinforcement Learning”。

叙述思路如下：

1. RL有什么用？主要挑战在哪里？（以小游戏引出的信用分配问题(credit assignment problem)为例，并介绍exploration-exploitation）
2. RL问题的基本概念。（介绍Markov Decision Process，RL的要素）
3. RL的目标：长期策略（引入贴现因子（discount factor），贴现的未来奖励）
4. 怎样估计未来奖励呢？（Q-learning）
5. 状态空间太大，Q-learning不足怎么办？（DQN）
6. 实现过程中的问题怎么解决？

----------------------------------------下面开始啦-------------------------------------------

强化学习（RL）

看一个叫Breakout的小游戏，我们通过控制屏幕下方横板的位置，将球弹回屏幕上方，每当弹回的球清除了上方的砖头，我们就得一些分数，也就是奖励。

Fig 1： Breakout游戏，来自DeepMind文章

如果用一个神经网络来玩这个游戏，一般要这样实现：用某一时刻的游戏界面图片作为输入，输出应该执行的动作。动作有三种：左移，右移，重新发球（重新开始游戏）。这可以看成一个分类问题，但麻烦的是，要训练这样一个神经网络，我们将会需要大量的图片，而且，我们需要专业的玩家在每个时刻做出正确的动作，才能获得标签（label）。这样太麻烦了！我们“人”学习一个游戏，并不需要另一个人告诉我们每种可能的游戏界面下分别做什么动作，我们需要的只是偶尔的反馈：告诉我们现在做的是对的，能得分，技巧我们可以自然地找到。

这就是RL擅长的事。 RL是介于监督学习与非监督学习之间的一种方法，监督学习是每个训练样本都有标签，非监督学习是都没有标签，二RL则是稀疏（有的有，有的没有）且有延迟的标签，这种标签就是奖励（我们的得分）。只基于这些奖励，一个玩家就能学习怎样在环境中做出适当的行为。

这种方法很好理解，但现实中它有很多的难点。例如，当某一时刻球击中了砖头，我们获得了奖励，但这个奖励并不是击中砖头那一时刻的动作导致的，而是我们之前就把横板移动到了正确的位置，球才能弹回去。也就是说，关键动作在得分前早就完成了。这就是信用分配问题(credit assignment problem)，我们获得的奖励，究竟应该归功于之前的哪些动作呢？那些动作分别有多少功劳呢？

还有另一个难点：如果我们找到了一个好的策略，让我们陆续拿到一些分，这时我们应该维持这个策略，还是尝试一些新的方法冲击更高的分数呢？在上面的Breakout游戏中，最简单的策略是把横板移到最左边，因为每次重新发球，球都大概率从往左边飞，我们把横板放在左边不动，很容易拿到大约10分，然后game over。显然，正常人不会满足于此，我们还想再多得一些分，这就是探索or利用困境（explore-exploit dilemma）：我们应该更侧重于利用已知的策略，还是探索新的可能更好的策略呢？

其实，RL也是我们人类（或者说动物）学习东西的重要方式。来自父母的夸奖，在学校的成绩，工作的薪水，都是一种奖励，信用分配问题（credit assignment problem)和探索or利用困境（explore-exploit dilemma）也是我们天天都会遇到的。所以研究RL问题对我们就很重要了。

RL基本概念（Markov Decision Process+RL的要素）

我们怎样描述一个RL问题呢? 最常用的方法是用一个马尔科夫决策过程（Markov Decision Process）来描述：

假如我是agent（一个能做出行为的个体），处于一个环境（environment）中，比如Fig.1中Breakout游戏。这个环境在一个时刻有特定的状态（state），比如横板的位置、球的位置和移动方向，砖头的位置等等。agent在环境中做出动作（action），比如左移横板，这些动作有时会带来奖励（reward），比如分数。同时动作又改变了环境的状态，导致新的状态，在新的态下agent又采取新的动作，如此持续下去。在整个过程中，我们按什么样的规则和规律选择动作，形成了我们的策略（policy）。agent，environment，state，action，reward，policy这些就是描述一个RL问题的要素。

一般来说，环境有一定的随机性（stochastic），导致状态也会有随机性，比如当我们gameover后重新开始游戏，球飞入的方向不是固定的。而且，每当我们采取一些行动，都有一定概率导致某种状态，也有一定的概率导致另一种状态。所有可能的状态和动作的集合，状态之间互相转换的规律，就形成了Markov decision process，见Fig 3。

每一串连续的状态，动作和奖励，叫做一个episode，比如下面的序列：

[公式]

在t时刻，观察到状态s(t)，采取行动 a (t)，后来得到奖励 r(t+1)，新的状态为s(t+1)，直到到达最终状态s(n)（terminal state）。Markov decision process遵从Markov假设：下一个状态只取决于这一步的状态和这一步采取的措施，即s(t+1)只取决于s(t)和a(t)。

贴现的未来奖励（discounted future reward）与长期策略

为了获得长期的良好表现，我们不仅要考虑眼下的即时的奖励，还要考虑未来的收益。给定一个Markov decision process，我们可以轻易地获得一个episode的总奖励:

[公式]

如果限定起始时间，从t时刻之后的总奖励可以表示为:

[公式]

但是由于环境有随机性，我们无法保证下次采取同样的行为还能获得同样的奖励，我们越往未来的时刻看，可能的情况越多，不确定性越大。所以，我们不想考虑太遥远的未来，而常用贴现的未来奖励（discounted future reward），越未来的奖励越贬值:

[公式]

上式中，γ是一个贴现因子，γ∈[0,1] （近年来的一些研究甚至还有γ>1 ），若贴现因子为0，则只考虑当前奖励，意味着采取短视的策略；如果我们希望平衡当前与未来，则将γ设为0到1之间，比如常用0.9。γ取值越大，表示我们将越长远的未来收益考虑到了当前行为产生的价值中，如果γ取值过大，则考虑的过于长远，甚至早已超出当前行为所能能影响的范围，这显然是不合理的。如果一个问题是continual的，选取γ=1将导致奖励值 R(t) 不能收敛，因为我们把无穷远之后的收益也加入了当前的价值中；但若问题是episodal的，理论上可以选择γ=1，也确实有一些人这么做，但同样地，我们需要考虑这种考虑具体的情景下，一个行为的影响力有多远，当前的收益是不是比未来的更重要一些，以及我们是否应该将一个不贬值的总收益作为决定当前行为的标准。

一个好的长期策略，将是一个能最大化贴现未来奖励（discounted future reward）的策略

Q-learning

怎样找到一个好的长期策略呢？我们先定义一个Q值 Q(s,a) ，来表示我们在状态s下，采取某个行为 a，所能得到的最大贴现未来奖励。由于不确定性，这个奖励将是一个期望值：

[公式]

这个Q值可以理解为，在这个s状态下采取了 a 行为后，整个episode最后可能的最大好处。之所以叫做“Q”值，是因为他代表了在s状态下采取了 a 行为的“Quality“。

如果这个Q值存在的话，策略就很简单：只要在每一步都选择那个Q值最大的行为就行了。

但这个Q的存在有点奇怪，如果只有现在的状态和行为，未来的状态和行为尚未发生，如何估计episode结束时的收益Q呢？答案是通过Bellman equation迭代得到！

让我们首先看一次状态变化

[公式]

，我们可以写出状态变化前后Q值之间的迭代关系，也就是Bellman equation：

[公式]

这一Bellman equation可以直观地理解为：当前状态和行为的Q值，等于即时的奖励加上下一个状态可能的最大奖励。

有了以上Q值的定义和关系，Q-learning的目标是估计Q值，获得一个Q-table：

Fig 4：Q值表（Q table）

Q-learning获得Qtable的方法是通过基于Bellman equation不断迭代更新，最终收敛到准确的Q值。算法如下，其中 α

为learning rate。

Fig 5: Q-learning算法

Deep Q Network （DQN）

仍以Breakout游戏为例，我们可以选择横板的位置、球的位置和移动方向，砖头的位置作为状态变量，然而，这样的状态只适用于这个游戏。如何选择更一般、更普遍适用的状态呢？显然，以图片所有像素值作为状态是更好的选择，它包含了这个场景下所有的情况和信息。

这就是DQN要发挥的作用。神经网络（NN）十分擅长从有结构的数据中提取好的特征，因此，我们可以用NN来近似 Q(s,a)

，以状态（如四张图）和动作为输入，输出对应的Q值。或者，另一种方式是，以状态作为输入，输入各种动作下对应的Q值，这种方法的优点是可以方便地从所有输出中找到最高的Q值，从而决定最优的动作。这两种方式的简图如下：

Fig 6: DQN的两种结构

DeepMind的文章中所使用的正是第二中结构，其architecture为为3个CNN Layer提取特征，加两个fully connecton layer得到输出，具体设置见下图：

值得一提的是，这样的architecture与我们常见的用于图像识别的CNN有所不同：没有pooling layer。 我们知道，pooling layer的作用是获得平移不变性（translation invariance），我们希望不管物体在图像的什么位置，都可以被识别出来。对于像ImageNet这样的分类问题，添加pooling是十分合理的。但是在类似Breakout游戏的RL问题中，位置是十分关键的信息，对应不同的状态和奖励，使用pooling layer将损坏位置信息。

基于以上的分析和所设计的architecture，NN以像素值为输入，输出若干个对应不同动作的实数Q值。这实际是一个用NN实现的regression，可以用简单的误差平方作为损失函数：

[公式]

其中

[公式]

称为target， Q(s,a) 称为prediction。

DQN中Q值的更新的方法变为：

对一次状态变化 <s,a,r,s'> ：
1. forward pass 获得对当前状态和所有动作的Q值，即Q(s,a1)，Q(s,a2)...
2. forward pass 获得对下一状态的最大Q值，即maxQ(s',a')=Q(s',a*)
3. 对动作a，更新target；其他动作target不变
4. backpropagation 依据每个动作的target和prediction，反向传播更新参数

结合experience replay和explore-exploit dilemma的DQN算法稍后提到。

Deep Q learning 的实现

这一节主要介绍实现过程中的experience replay和explore-exploit dilemma的处理。基于上面对DQN的介绍，我们大概知道要如何用CNN更新和估计Q值。但实际上，用一个非线性函数近似Q function并不总是稳定的，我们常常采取一些trick来使算法更好地收敛。

Experience replay-最重要的一个trick：

• 问题：若将观察到的

[公式]

按照发生的时间顺序输入CNN，那么CNN的训练结果将非常受最近的

[公式]

影响，相继输入CNN的样本之间有很大的相似性，导致CNN收敛到一个不好的局部最优解。

• 解决：为了防止这一点，我们将所有经历过的

[公式]

都存入一个replay memory，在训练的过程中，采用小批次随机梯度下降法（mini-batch gradient descent），每次随机抽取replay memory中的一些样本来使用，从而避免上面的问题。

ε-greedy exploration-充分地探索：

• 问题：回顾我们在开头中提到的Explore-exploit dilemma，是利用现有策略还是探索新的策略呢？在Q-learning和DQN中，我们随机初始化Q table或CNN后，用初始化的模型得到的Q值（prediction）也必然是随机的，这是当我们选择Q值最高的动作，我们相当于随机选择了一个动作，此时，我们实际上在探索（explore）。当算法逐渐趋于收敛，Q的估计值越来越稳定，对于每个状态，对应的Q值最高的动作也越来越固定，也就是策略越来越固定，此时，我实际上在利用（exploit）。所以，Q learning本身已经具有一定的“探索”，但是这种“探索”是非常短暂和”贪婪“的，它只在训练初期进行探索，并且在探索到第一个稳定的策略后就不再探索了（收敛了）。
• 解决：解决这一问题的一个简单有效的方法是ε-greedy exploration。每次选取动作时，以一定的概率ε随机挑选一个动作，其他情况下则选择Q值最大的动作。DeepMind文章采用将ε从1递减到0.1的方法，是训练初期大量探索状态空间，后期逐渐稳定到较小的探索比率。

最后，考虑experience replay和explore-exploit dilemma后，DQN算法如下：

Fig 8：DQN算法，考虑experience replay和explore-exploit dilemma

写在最后

当然，还有更多的技巧使DQN能够更快更好地收敛，例如target network, error clipping, reward clipping等等。

这些RL方法最精彩的地方在于，一无所知到能够找到有效的策略完成特定的任务。回想我们随机地初始化模型，用这些随机初始的“垃圾”，一步一步学出有意义的内容。听起来不可思议，但RL确实做到了。