本文禁止转载

原文:Guest Post (Part I): Demystifying Deep Reinforcement Learning

两年前, 一个名叫deepmind的伦敦小公司往Arxiv上传了一篇前沿的论文让深度学习玩Atari游戏. 这篇文章展示了计算机如何仅仅通过观察屏幕上的像素和分数的增加来玩Atari上边的2600个游戏. 成果引人注目, 因为这些游戏和分数都被设计成挑战人类的. 同样的模型, 不需要任何的改动, 就可以用来学习不同的游戏, 而且其中的三个算法的表现甚至比人类要好.

从那时起，它就被誉为通用人工智能的第一步--一种可以在各种环境中生存的人工智能，而不是局限于比如下棋这种严格的领域。毫无悬念Deepmind很快的被Google收购, 而且一直走在深度学习的前列. 2015年2月的论文通过强化学习达到人类的控制水平被<自然>杂志当做特色封面,<自然>杂志是科学界最权威的杂志之一. 这篇文章中, 他们在49款不同的游戏中应用了同样的模型, 在一半的游戏中有着超人的表现.

当深度模型在监督与非监督学习领域在各个社区广泛传播的时候, 深度学习依然保有一定的神秘性, 这篇文章我们将尝试解密这种技术以及其背后的基本原理.本文的受众人群是已经有了机器学习背景且有一点神经网络基础, 却没有时间深入钻研强化学习的人.

以下是大纲:

1. 强化学习的主要挑战有哪些?我们将在这涵盖信度分配问题(credit assignment problem)和探索/利用困境( exploration-exploitation dilemma)
2. 如何用数学形式表达强化学习?我们将定义马尔可夫决策过程(Markov Decision Process)并用它推导强化学习.
3. 如何制定长期策略?我们将定义衰减未来激励(discounted future reward)这将是下一节算法的基础.
4. 如何评估/估计未来的回报?我们将定义和解释简单基于表的Q-learning(Simple table-based Q-learning)算法
5. 如果状态空间过大如何处理?我们将看到如何使用深度神经网络替代Q表.
6. 我们如何让它真正开始运行?我们将在这讨论经验回放技术(Experience replay), 通过神经网络稳定学习.
7. 这就完事儿了?我们最后会讨论探索/利用困境的几个解决方案.

强化学习

回忆一下打砖块游戏(Breakout), 这个游戏里边你控制屏幕底部的一个滑块来回接住并反弹一个小球来把上半块屏幕砖敲碎. 每次敲碎一块砖, 砖块消失且分数增加.

Figure 1: Atari Breakout game. Image credit: DeepMind.

假设要教一个神经网络去学习怎么玩这个游戏. 神经网络的输入就应该是屏幕的图像, 而输出应该就是三种动作之一, 左/右还有发射球. 如果把它当成分类游戏也算有道理 -- 对于每一个屏幕图像, 你需要向左/向右(移动滑块)或者发射(小球).听起来简单明了?这是肯定的, 但后续需要训练大量样本.当然也可以记录骨灰级玩家的游戏过程, 但是我们不会真的像这样去学习.不需要一个一个屏幕图像过并让别人成千上万次告诉我们怎么做. 只需要当它偶尔做了正确行为就给出反馈即可, 这样我们自己就能搞明白怎么做.

这就是强化学习试图去解决的任务.强化学习介于监督学习和非监督学习之间.鉴于监督学习对于每个训练样本都有一个明确的标签, 而非监督学习完全没有标签, 强化学习中则有着稀疏而且延时的标签.被控主体(Agent,以下简称主体)必须根据这些激励在这个环境中去学习去执行动作.

虽然意思已经表达的很直白了, 实际应用中却有着数不清的坑.比如说, 当敲到一个砖块的时候, 在游戏里就会得分, 然而这通常和之前做什么动作没有多大关系. 难做的活早就在把滑块停在正确的位置把球弹出去就干完了.这个难题有个名字就叫信度分配问题(credit assignment problem), 比如, 哪个动作影响了得分, 多大程度影响.

如果找到了一个可以得到确定分数的策略, 那么是纠结于此方案还是继续实验可以得到更大激励的策略?在上边的打砖块游戏里边, 一个简单测策略是把滑块一直停在屏幕的最左边等在那. 当发射的时候, 球会更多的向左飞行, 这样很容易就能在游戏结束前得10分. 是就满意如此还是想要更好?这就叫做探索/利用困境( exploration-exploitation dilemma) - 继续利用已知的方案还是探索更好的办法.

强化学习是一个人类如何去学习的重要模型(同样也是动物学习的模型).父母的褒奖, 学校的分数, 工作的工资 -- 这些都是激励的实例.信度分配问题和探索/利用困境在日常商业与人际关系频繁出现. 这就是为什么研究这个问题如此重要, 而游戏给尝试出新方法提供了一个极好的环境.

马尔可夫决策过程

现在的问题是, 如何把强化学习形式化, 使之可以推导? 一种比较普遍的方法是把他用马尔可夫决策过程表示出来.

假设你就是一个主体(Agent), 在一个环境中(比如打砖块游戏), 环境处于一个确定的状态之中(比如滑块的位置, 球的飞行方向, 每个砖块是否存在等等). 主体能在环境中做出特定的行为(比如向左或者向右移动滑块). 这些行为有时会获得激励(比如分数的增加). 行为使环境转化到一个新的状态, 在新的状态下主体可以做新的动作, 如此循环往复.选择行为的方式被称为策略. 环境通常是随机的, 这意味着它的下一个状态某种意义上也是随机的(比如丢了一个球后, 发射新的时候, 它的方向是随机的)

Figure 2: Left: reinforcement learning problem. Right: Markov decision process.

状态和行为的集合与状态的转移规则一起构成了马尔可夫决策过程. 这个过程(比如一个游戏)的一个片段(episode)是一个由状态/行为/激励组成的有限序列:

Markov decision process episode

这里的si ai 和 r(i+1)分别代表了状态,动作和在此状态下执行此动作后的奖励. 片段以终态(terminal)sn (比如"游戏结束"屏幕)结尾. 马尔可夫决策过程依赖于马尔可夫猜想, 即下一个状态 s(i+1) 出现概率由当前状态si与动作ai决定. 而不是由前面那些状态和动作决定.

衰减的未来激励(Discounted Future Reward)

想要在长期表现优秀, 不能仅仅只关注即时激励, 也应当重视将来获得的激励. 如何达到这一点?

运行一个给定的马尔可夫决策过程, 则很容易算出一个片段的总激励(total reward):

Discounted Future Reward total reward

得到了这个, 从t点开始的未来总激励(total future reward)可以表示为:

Discounted Future Reward total future reward

但是由于环境是随机的, 我们永远不能确定下次使用同样的动作会不会得到同样的激励. 未来经历的越多, 结果就越发散.出于这个原因通常使用衰减的未来激励来替代上式:

Discounted Future Reward discounted future reward

这里的 γ 是代间衰减系数, 离我们越遥远, 考虑的就越少.容易看出, 衰减的未来激励在t时的形式可以用t+1时同样的结果表示:

Discounted Future Reward t + 1

如果设置衰减系数 γ=0 , 则使得策略鼠目寸光,只看眼前利益(即时激励), 想要在即时激励与未来的激励之间得到一个平衡, 就应该设置一个衰减系数, 比如γ=0.9, 如果环境是随机的, 而且同样的行为总是得到同样的回报, 则可以设定γ=1
#译者注: 其中蕴含了一个哲理, 未来看的越清楚, 我们就会觉得未来越重要, 这样就有更大的几率获得更高的激励, 我们每个人都应该努力去培养自己看清未来的能力

一个主体的优秀的策略应该总是选择能够最大化(衰减的)未来激励

Q-learning(质量学习)

在Q-learning里边, 我们定义一个函数Q(s, a)来代表当我们在状态s下执行a动作的最大衰减未来激励, 并且从这一点开始一直选取最优.

Q-learning

这个定义听起来可能挺让人迷糊. 如果仅仅知道当前的状态和动作而不知道后来的, 怎么去估计在游戏结束时候的得分? 这真的做不到.但作为一个理论构想, 我们可以假设存在这么一个函数.闭上眼睛默念五遍: "Q(s, a)存在, Q(s, a)存在...". 感受到了(洪荒之力?)?

如果你还没整明白, 那就思考下这个函数所包含的含义. 假设你现在在某个状态中, 要么执行a动作, 要么执行b动作. 你想执行一个动作使得你最后得分最高. 一旦你手握这个Q函数, 一切都easy了--选一个能得到最高的Q值的动作即可.

Q-learning π policy

这里的π代表着在每个状态下选择动作的策略.

好, 那如何取得Q函数呢? 让我们回到某个转换<s, a, r, s'>上来. 类似前一节介绍的衰减未来激励, s状态的Q值也可以用s'状态的Q值来表示.

Q-learning Q-s'

这个式子称为贝尔曼方程(Bellman equation), 想一下它还是挺符合逻辑的 -- (总的)未来最大激励等于即时激励加上下一状态的(总的)未来最大激励.

Q-learning的核心是可以迭代使用贝尔曼方程逼近Q函数在最简单的情况下, Q函数是用一个以状态作为行以动作作为列的表表示的. 简单的Q-learning简单到可以用下边的伪代码表示:

Q-learning code

算法里边的α是学习率, 即旧的Q值与新的Q值之差的考虑程度. 尤其当α=1两个Q[s,a]抵消, 更新的值完全和贝尔曼方程一致.

我们用来更新Q[s,a] 的 maxa’ Q[s’,a’]仅仅是一个近似值,而且在早期阶段的学习中, 这个值可能完全就是错的. 但这个近值在迭代的过程中越来越准确, 而且他是收敛的. 因此如果一直这么更新下去, Q函数收敛并代表真正的Q值.

深度Q网络 (Deep Q Network)

打砖块游戏的状态可被认为由滑块的位置,球的位置与方向,每块砖是否存在一起定义. 然而这些直观的表现却是特定游戏的特性. 怎么把它变成更通用的特性, 使它适用与所有的游戏? 一个显而易见的选择是游戏的像素 -- 他们隐含了游戏里边所有关于状态的信息, 除了球的速度和球的方向.如果使用两个连续的图像则会包含这两个信息.

如果把和DeepMind论文一样的模型应用到游戏屏幕中- 取最后四帧图像, 缩放到84×84然后做一个256阶的灰度化 -- 可能会得到 256^(84844)大约10e67970种不同的状态.这意味着Q表将会有10e67970行, 比已知宇宙的原子数量还多!可能有人说有那么多种像素的组合(和因此产生的状态)不可能都发生 -- 可以使用一个稀疏的表, 只记录已经发生的状态. 即使如此, 大部分的状态都极少能访问到, 想要跑满所有情况可能要等到地老天荒.理想的情况是我们希望能对没有见过的状态的Q值做一个不错的推测.

这就正是深度学习踏足的领域. 神经网络非常擅长在高度结构化的数据中找到优良的特性. 可以使用一个神经网络来代表Q函数, 使用状态(连续4帧的屏幕)和动作作为输入, 输出Q值.或者, 只输入游戏屏幕输出每个动作对应的Q值, 这种方法有个优点,当要更新Q值或者选出最大Q值的动作的时候, 需要做的仅仅是一次前向传输,然后就可以立刻得到所有动作的Q值.

Figure 3: Left: Naive formulation of deep Q-network. Right: More optimized architecture of deep Q-network, used in DeepMind paper.

Deepmind使用的神经网络如下:

Deep Q network Deepmind

这是一个拥有三层卷积层和两层全连接层的神经网络. 熟悉识别网络的朋友们应该意识到了这里没有池化层. 但是仔细想一想, 池化层给你带来了转移的不确定性 -- 网络对物体的位置变得不敏感. 虽然池化对于图片分类网络这个是有意义的, 但游戏中球的定位会潜在地决定游戏的激励, 我们并不想丢掉这个信息.

网络的输入是四个84×84的灰度化游戏屏幕图像. 输出是每个动作对应的Q值(Atari有18个不同的动作),Q值可以是任何实数,可以通过简单的平方差损失函数进行回归优化.

Q-learning square loss

给定一个状态转移:< s, a, r, s’ >前边提到的Q表更新算法必须替换如下:

1.把当前状态s进行前向传播, 得到所有动作的Q值.
2.把下一个状态s'进行前向传播在所有的输出中计算max Q(s’, a’).
3.设定此动作的Q值为 r + γmax Q(s’, a’)(使用第二步计算出的结果), 对于所有其他的动作, 设定和第一步的返回一样的Q值, 使得他们的误差为0
4.使用反向传播算法更新权重

经验回放(Experience Replay)

现在我们已经知道了如何在每一种状态下使用Q-learning进行激励的估计, 如何使用卷积神经网络逼近q值.但结果发现使用非线性函数去逼近Q值不是很稳定.想让它收敛你还需要一大堆的技巧. 而且这很耗时, 如果使用单个GPU估计需要一周的时间....

一个重要的技巧叫做经验回放(Experience Replay), 玩游戏的所有经历$lt; s, a, r, s’ $gt;会被保存在一个重放记忆中.训练网络的时候, 回放记忆中随机的小批状态转移用来代替最近的状态转移用来训练. 这样就打破了和后续训练样本的相似性, 否则可能会使得模型陷入一个局部最优.不仅如此, 经验回放会使得任务变得更像监督学习, 简化了算法的调试与检测. 可以先收集人类玩游戏的经验, 然后在这些数据上边训练.

探索/利用(Exploration-Exploitation)

Q-learning尝试解决信度分配问题 -- 当到达让游戏得分的关键性的那一时刻, 网络进行反向传播, 但是到目前还没接触到探索/利用问题..

首先观察, 当Q表和Q网络随机初始化的时候, 它的预测也是随机的.如果选出最高的Q值的的动作, 那这个动作也是随机的而且这个主体做出了一个随便的探索(exploration). 当Q函数收敛时, 返回的Q值更一致而且探索的数量下降. 所以有人说探索是Q-learning算法的一部分. 但是这个探索是"贪婪"的, 它找到一个有效策略之后就不再改变了.

解决上边问题一个简单有效的方法是ε贪婪探索(ε-greedy exploration) 在选取动作时候有ε的可能选取一个随机动作, 不这么做算法就会贪婪的选择最高的Q值.在Deepmin的系统中,ε的值随时间从1减到0.1 -- 在最开始的时候系统总是随机的进行移动去尽可能的探索空间的状态, 而后慢慢的稳定到一个固定的探索比例.

深度Q-learning算法(Deep Q-learning Algorithm)

下边的代码给出了最终的带经验回放的Q-learning算法:

Deep Q-learning Algorithm code

实际上Deepmin公司使用了更多的技巧 -- 比如目标网络(target network), 误差修剪(error clipping), 激励修剪(reward clipping)等等, 但这些不在本文讨论的范围之内.

这个算法最精彩的部分是可以学习任何东西. 你想想看, 由于Q函数是随机初始化的, 最开始的输出完全是垃圾. 而且我们使用这些垃圾(下一个状态的最大Q值)作为网络的最终目标.只是偶尔获得一点点微小的激励. 听起来有点不切实际, 它怎么能学习到任何有意义的东西?实际上, 它确实学到了.

结语

从Q-learning第一次提出开始, 已经提出了很多提高Q-learning的方法 -- 举几个来说: 双Q-learning,有优先级的经验回放, 对抗网络架构和 连续动作空间扩展, 最前沿的进展请看2015深度强化学习专题和ICLR 2016(搜索标题"强化"), 但请注意Q-learning已经被谷歌申请了专利

常言道, 人工智能任重道远. 一旦知道它如何运转, 它看起来也就没有那么"智能"了. 但Q网络还是让我感到惊艳.看他们整明白一个游戏就像观察野外的动物 -- 通过它自己获取激励的过程.

致谢

感谢Ardi Tampuu, Tanel Pärnamaa, Jaan Aru, Ilya Kuzovkin, Arjun Bansal, 还有 Urs Köster对于此文草稿的点评.

(#译者注: 当然这里还要感谢作者Tambet Matiisen)

外链

• David Silver’s lecture about deep reinforcement learning
• Slightly awkward but accessible illustration of Q-learning
• UC Berkley’s course on deep reinforcement learning
• David Silver’s reinforcement learning course
• Nando de Freitas’ course on machine learning (two lectures about reinforcement learning in the end)
• Andrej Karpathy’s course on convolutional neural networks