两年前，伦敦的一家叫DeepMind的小公司在Arxiv上发表了一篇名为“Playing Atari with Deep Reinforcement Learning”的先驱性文章。这篇文章介绍了如何让计算机学习玩Atari游戏。文中计算机的学习方法仅限于观察游戏机屏幕以及分数奖励。由于运行在Atari上的游戏玩法各不相同，目标也不尽一致，这篇文章的过人之处在于采用完全相同的框架玩不同的游戏，并且取得了非常好的成绩。文中提到他们的算法可以玩七种不同的游戏，其中三种甚至好于人类水平。
作为通用人工智能的第一步（具体指同一人工智能程序可以适应不同环境，而非针对某些具体任务设计人工智能程序），这篇文章受到了广泛关注。DeepMind也不出意外地被谷歌公司收购并站在了深度学习研究的前沿。在2015年2月，他们的文章“Human-level control through deep reinforcement learning”被Nature杂志以封面文章的形式发表。在这篇文章中，他们的人工智能程序已经能玩49种不同的游戏了。更激动人心的是，其中半数游戏中的表现已经超越了人类的顶尖选手。
虽然在学术界，深度学习模型已经在监督学习和非监督学习问题上广泛地使用，深度强化学习仍带有神秘的色彩。在这篇文章中，我将试着揭掉它神秘的面纱并将背后的基本原理展示给读者。这篇文章应该非常适合那些具备机器学习以及深度学习基础，但还没花时间仔细研究深度强化学习的读者们。 在进入主题之前，首先简要介绍一下本文的组织方式：
- 强化学习的主要挑战是什么？本节将用功劳分配问题作为例子并且介绍探索-利用困境。
- 如何对强化学习进行数学定义？本节将定义马尔科夫决策过程并用他来定义强化学习。
- 强化学习中如何制定长期决策？本节将定义“打折的未来奖励”，而这一定义是后续部分基础。
- 强化学习中如何估计或者近似未来奖励？本节将介绍一种简单的基于表的Q-learning算法
- 如果状态过多（基于表的方法不可行时）如何估计或者近似未来奖励？本节将介绍如何使用深度学习的方式替换Q表。
- 如何才能从数据中学习模型使其真正工作？本节将介绍一种能够增强模型稳定性的技术——“经验回放技术”。
- 未来工作，文章的最后将介绍一种探索-利用困境的简易解决方案。
强化学习
首先，让我们简单介绍一下Breakout这个游戏。在这个游戏中，你需要控制屏幕底端的一根横杆左右移动，将飞向底端的球反弹回去并清除屏幕上方的砖块。每次你击中并清除了砖块，你的分数都会增加——你获得了奖励。
图1，Atari Breakout游戏，（图片来源：DeepMind）
假设你想教神经网络模型玩这个游戏，模型的输入是游戏机屏幕像素所构成的图片，输出是三种动作：向左，向右以及开火（把球射出）。把这个问题建模为分类问题是很合理的——对于每个屏幕画面，你都需要进行决策：是左移，右移，还是开火。分类的建模方法看起来很直接。不过，你需要大量训练数据训练你的分类模型。传统的做法是找一些专家让他们玩游戏并且记录他们的游戏过程。但人类肯定不是这样玩游戏的。我们不需要有人站在我们背后告诉我们向左还是向右。我们只需要知道在某些情况下我们做了正确的动作并且得分了，其他的依靠我们自身的学习机制完成。 这个问题就是强化学习尝试解决的问题。强化学习处于监督学习与无监督学习的中间地带。在监督学习中，每个训练实例都有一个正确标签；在无监督学习中，训练实例并没有标签。在强化学习中，训练实例有稀疏并延时的标签——奖励。基于奖励，强化学习中的智能体可以学习如何对环境做出正确的反映。
上述的观点看起来很直观，但是实际存在很多挑战。举例来讲，在Breakout这个游戏中，击中砖块并且得分和前一时刻如何移动横杆没有直接关系。最相关的是前面如何将横杆移动到正确位置并反弹球。这个问题叫做信用分配问题（credit assignment problem），即：建模获得奖励之前的哪些动作对获得奖励产生贡献以及贡献的大小。
如果你已经获得了某种策略并且通过它得了不少奖励，你应该继续坚持这种策略还是试试其他的可能获得更高分的策略？仍举Breakout这个游戏为例，在游戏开始时，你把横杆停在左边并把球射出去，如果你不移动横杆，你总是能得10分的（当然得分的下一秒，你就死了）。你满足于这个得分吗，或者你想不想再多得几分？这种现象有一个专门的名词——探索-利用困境（exploration-exploitation dilemma）。决策时应该一直延用现有的策略还是试试其他更好的策略？
强化学习是人类（或者更一般的讲，动物）学习的一种重要模式。父母的鼓励，课程的分数，工作的薪水——这些都是我们生活中的奖励。功劳分配问题以及探索-利用困境在我们日常生活工作中经常发生。这就是我们研究强化学习的原因。而对于强化学习，游戏是尝试新方法的最佳的沙盒。
马尔科夫决策过程
下面，我们的问题是如何形式化定义强化学习问题使其支持推断。最常用的表示方式是马尔科夫决策过程。
假想你是一个智能体（agent），面对某种场景（比如说Breakout游戏）。你所处的环境可以定义为状态（state）（比如横杆的位置，球的位置，球的方向，当前环境中的砖块等等）。智能体能够在环境中采取一些动作（actions）（比如向左或向右移动横杆）。这些动作会导致一些奖励（reward）（比如分数的增加）。智能体采取动作将导致新的环境，也就是新的状态。在新的状态下，智能体能够继续采取动作，循环往复。你采取行动的原则叫做策略（policy）。通常来讲，环境是很复杂的，智能体的下一状态可能带有一定的随机性（比如当你失去一个球发射另一个球时，它的方向是随机的）。
图2：左：强化学习问题，右：马尔科夫决策过程
一系列的状态、动作、以及采取动作的规则构成了一个马尔科夫决策过程（Markov decision process）。一个马尔科夫决策过程（比如一局游戏）由一串有限个数的状态、动作、反馈组成，形式化地表示为：
其中，si表示状态，ai表示动作，ri+1是采取动作后的奖励。当状态序列达到终止状态sn时（比如“Game Over”画面），一个马尔科夫决策过程结束。马尔科夫决策过程服从马尔科夫假设，也就是说，下一状态si+1只与当前状态si和ai有关，与之前的状态或动作无关。
打折的未来奖励
为了在长期决策过程中表现的更好，我们不但要考虑采取一个动作后的即时奖励，也要考虑这个动作的未来奖励。那么问题来了，我们应该如何建模这个未来奖励？
给定一个马尔科夫决策过程，它对应的奖励总和很容易用如下方式计算：
而t时刻的未来奖励可以表示为：
由于智能体所处的环境非常复杂，我们甚至无法确定在两次采取相同动作，智能体能够获得相同的奖励。智能体在未来进行的动作越多，获得的奖励越不相同。所以，我们一般采用一种“打折的未来奖励”作为t时刻未来奖励的代替。
这里，gamma是一个0到1的值。这个gamma值使得我们更少地考虑哪些更长远未来的奖励。数学直觉好的读者可以很快地看出Rt可以用Rt+1来表示，从而将上式写成一种递推的形式，即：
如果gamma是0，我们将会采取一种短视的策略。也就是说，我们只考虑即刻奖励。如果我们希望在即刻奖励与未来奖励之间寻求一种平衡，我们应该使用像0.9这样的参数。如果我们所处的环境对于动作的奖励是固定不变的，也就是说相同的动作总会导致相同的奖励，那么gamma应该等于1。
好的策略应该是：智能体在各种环境下采用最大（打折的）未来奖励的策略。
Q-learning
在Q-learning中，我们定义一个Q(s, a)函数，用来表示智能体在s状态下采用a动作并在之后采取最优动作条件下的打折的未来奖励。
直观讲，Q(s, a)是智能体“在s状态下采取a动作所能获得的最好的未来奖励”。由于这个函数反映了在s状态下采取a动作的质量（Quality），我们称之为Q-函数。
这个定义看起来特别奇怪。我们怎么可能在游戏进行的过程中，只凭一个状态和动作估计出游戏结束时的分数呢？实际上我们并不能估计出这个分数。但我们可以从理论上假设这样函数的存在，并且把重要的事情说三遍，“Q-函数存在，Q-函数存在，Q-函数存在”。Q-函数是否存在呢？（笑）
如果你还不相信，我们可以在假设Q-函数存在的情况下想一想会发生什么。假设智能体处在某个状态并且思考到底应该采用a动作还是b动作，你当然希望选取使游戏结束时分数最大的动作。如果你有那个神奇的Q-函数，你只要选取Q-函数值最大的动作。
上式中，\pi表示在s状态下选取动作的策略。
然后，我们应该如何获得Q-函数呢？首先让我们考虑一个转移<s, a, r, s’>。我们可以采用与打折的未来奖励相同的方式定义这一状态下的Q函数。
这个公式叫贝尔曼公式。如果你再想一想，这个公式实际非常合理。对于某个状态来讲，最大化未来奖励相当于最大化即刻奖励与下一状态最大未来奖励之和。
Q-learning的核心思想是：我们能够通过贝尔曼公式迭代地近似Q-函数。最简单的情况下，我们可以采用一种填表的方式学习Q-函数。这个表包含状态空间大小的行，以及动作个数大小的列。填表的算法伪码如下所示：
其中\alpha是在更新Q[s, a]时，调节旧Q[s, a]与新Q[s, a]比例的学习速率。如果\alpha=1，Q[s, a]就被消掉，而更新方式就完全与贝尔曼公式相同。
使用max_a’ Q[s’, a’]作为未来奖励来更新Q[s, a]只是一种近似。在算法运行的初期，这个未来奖励可能是完全错误的。但是随着算法迭代，Q[s, a]会越来越准（它的收敛性已经被证明）。我们只要不断迭代，终有一天它会收敛到真实的Q函数的。
Deep Q Network
Breakout游戏的状态可以用横杆的位置，球的位置，球的方向或者每个砖块是否存在来进行定义。然而，这些表示游戏状态的直觉只能在一款游戏上发挥作用。我们要问：我们能不能设计一种通用的表示游戏状态的方法呢？最直接的方法是使用游戏机屏幕的像素作为游戏状态的表示。像素可以隐式地表示出球速以及球的方向之外的所有游戏状态的信息。而如果采用连续两个游戏机屏幕的像素，球速和球的方向也可以得到表示。
如果DeepMind的论文采用离散的游戏屏幕作为状态表示，让我们计算一下使用连续四步的屏幕作为状态，可能的状态空间。屏幕大小84*84，每个像素点有256个灰度值，那么就有256^(84*84*4)~10^67970种可能的状态。也就是说，我们的Q-表将要有10^67970行。这个数字甚至多于宇宙中的原子个数！有人会说：有些屏幕状态永远不会出现，或者，能不能只用在学习过程中碰到过的状态作为Q-表的状态呢？即便如此，这种稀疏表示的Q-表里仍包含很多状态，并且需要很长时间收敛。理想的情况是，即便某些状态没有见过，我们的模型也能对它进行比较合理的估计。
在这种情况下，深度学习就进入了我们的视野。深度学习的一大优势是从结构数据中抽取特征（对数据进行很好的表示）。我们可以用一个神经网络对Q-函数进行建模。这个神经网络接收一个状态（连续四步的屏幕）和一个动作，然后输出对应的Q-函数的值。当然，这个网络也可以只接受一个状态作为输入，然后输出所有动作的分数（具体来讲是动作个数大小的向量）。这种做法有一个好处：我们只需要做一次前向过程就可以获得所有动作的分数。
图3：左：朴素的Q-函数网络 右：在DeepMind论文中使用优化的Q网络 DeepMind在论文中使用的网络结构如下：
这个网络是普通的神经网络：从输入开始，三个卷积层，接着两个全连接层。熟悉使用神经网络做物体识别的读者或许会意识到，这个网络没有池化层（pooling layer）。但是细想一下我们就知道，池化层带来位置不变性，会使我们的网络对于物体的位置不敏感，从而无法有效地识别游戏中球的位置。而我们都知道，球的位置对于决定游戏潜在的奖励来讲有非常大的意义，我们不应该丢掉这部分信息。
输入是84x84的灰度图片，输出的是每种可能的动作的Q-值。这个神经网络解决的问题变成了一个典型的回归问题。简单的平方误差可以用作学习目标。
给定一个转移<s, a, r, s’>，Q-表的更新算法只要替换成如下流程就可以学习Q-网络。
- 对于当前状态s，通过前向过程获得所有动作的Q-值
- 对于下一个状态s’，通过前向过程计算Q-值最大的动作max_a’ Q(s’, a’)
- 将r+\gamma max_a’ Q(s’, a’)作为学习目标，对于其他动作，设定第一步获得的Q-值作为学习目标（也就是不会在反向过程中更新参数）
- 使用反向传播算法更新参数。
经验回放
到现在，我们已经知道如何用Q-learning的算法估计未来奖励，并能够用一个卷积神经网络近似Q-函数。但使用Q 值近似非线性的Q-函数可能非常不稳定。你需要很多小技巧才能使这个函数收敛。即使如此，在单GPU上也需要一个星期的时间训练模型。
这其中，最重要的技巧是经验回放（experience replay）。在玩游戏的过程中，所有经历的<s, a, r, s’>都被记录起来。当我们训练神经网络时，我们从这些记录的<s, a, r, s’>中随机选取一些mini-batch作为训练数据训练，而不是按照时序地选取一些连续的<s, a, r, s’>。在后一种做法中，训练实例之间相似性较大，网络很容易收敛到局部最小值。同时，经验回放也使Q-learning算法更像传统监督学习。我们可以收集一些人类玩家的记录，并从这些记录中学习。
探索-利用困境
Q-learning算法尝试解决信用分配问题。通过Q-learning，奖励被回馈到关键的决策时刻。然而，我们还没有解决探索-利用困境。
我们第一个观察是：在游戏开始阶段，Q-表或Q-网络是随机初始化的。它给出的Q-值最高的动作是完全随机的，智能体表现出的是随机的“探索”。当Q-函数收敛时，随机“探索”的情况减少。所以，Q-learning中包含“探索”的成分。但是这种探索是“贪心”的，它只会探索当前模型认为的最好的策略。
对于这个问题，一个简单的修正技巧是使用\epsilon-贪心探索。在学习Q-函数时，这种技巧以\epsilon的概率选取随机的动作做为下一步动作，1-\epsilon的概率选取分数最高的动作。在DeepMind的系统中，\epsilon随着时间从1减少到0.1。这意味着开始时，系统完全随机地探索状态空间，最后以固定的概率探索。
Deep Q-learning算法
最后给出使用经验回放的Deep Q-learning算法
除了上述技巧，DeepMind还使用了一系列其他的技巧，比如：目标网络、误差截断、回馈截断等等。但是这些已经超出本文的范畴了。
最令人惊喜的是这种算法可以应对各种学习问题。在算法的运行初期，Q-函数用来学习模型参数的数据几乎完全是（随机猜测的）垃圾数据，在运行过程中，也只能通过一些偶然的奖励学习参数。这种事情想想就很疯狂，它是怎么学到一个很好的模型呢？但事实上，它确实学到了一个很好的模型。
最后要注意的问题
自从Deep Q-learning提出之后，很多工作尝试对他进行提升，其中包括：Double Q-learning, Prioritized Experience Replay, Dueling Network Architecture, extension to continuous action space等等。如果要跟进最新的研究成果，可以关注NIPS 2015 deep reinforcement learning workshop以及ICLR 2016（用“reinforcement”作为关键词搜索）。有一点需要注意的是Deep Q-learning已经被谷歌申请专利了。
我们常说我们还没搞清楚什么是人工智能。一旦我们搞清其中的工作原理，它看起来就不那么智能。但是深度Q-网络仍在不断地给我带来惊喜。观察Q-learning学习玩一个新游戏的过程就像观察野外的动物。通过不断地与环境交互获得奖励从而成为更强的物种。
原文：Demystifying Deep Reinforcement Learning，译者：哈工大 SCIR 刘一佳
本文来源于哈工大SCIR
