深度学习第10期：基于Q的强化学习（上）

在上一期中，我们介绍了强化学习问题的定义，主要的分类，以及一些基本概况。这一期，我们来集中介绍基于Q的模型。如何建立模型、如何训练模型。

基于Q的模型如果单独出现，则其只适合解决离散动作的强化学习问题。但事实上，常见的强化学习问题基本都是离散动作的，例如下棋，每一步可以走的棋路是有限的，所以它必须是一个离散动作的强化学习问题。对于一些连续动作的强化学习问题，有时候出于性能的考虑，我们也会将其转化为离散动作的强化学习问题。例如在无人车驾驶中，我们如何调整前进的速度、或者以什么角度向左、向右转弯，可以做为连续动作的强化学习问题。但是，我们也可以将其离散化为几个动作，例如左转15°、左转30°，加速等等。如果我们每次决策的时间间隔较短，则其可以和连续动作问题达到差不多的效果。相反，很多的离散动作问题，比如下棋，就是不能化为连续动作问题的。从这个角度来说，离散动作问题（与连续动作问题相比）是RL最为基本的问题。

设我们希望获得最多的Q=Σγkrk（如果此处看不懂，请点击文末链接查看上一期）。基于Q的方法希望我们能够训练出一个函数Q(s,a)，衡量在s下采取a，并且在这一步之后全部都采用最佳策略，所能够获得的Q是多少。这样，对于一个给定的s，我们对比各个a对应的Q(s,a)，就能够得出我们应该采取哪个a是最佳的。

如果这个游戏只用玩一步就结束了，就好像是(s,a)→r，我们只要把Q(s,a)训练得更加接近r就可以了。这就完全等价于一般的监督学习问题。由于r是问题给定的，是“客观”的，所以我们把Q(s,a)训练得接近r，是没有任何风险的。但是，游戏要玩很多步，即(s,a)→r,s（我们用s表示下一个s）。我们假定我们的游戏具有马尔科夫性，即(s,a)带来的“后果”全都包含在s与r中。正是由于(s,a)→r与(s,a)→r,s有很大的不同，所以强化学习和之前我们主要介绍的监督学习有很大的不同。

我们想象，如果有一个“客观”的V函数能够衡量每一个s的价值（即局面的好坏），则我们把Q(s,a)训练得更加接近r+γ V(s)即可。这就又和监督学习问题毫无区别了。可是，我们并没有这个“客观”的V函数，我们仍然只能用自己训练的Q来判断s的价值。我们将其记为Q(s)。一般来说，我们认为Q(s)就是对于所有可能的a，Q(s,a_)能够取得的最大值。这样我们就可以只通过一个Q(s,a)的网络也实现计算Q(s)的功能。

总的来说，(s,a,r,s)就是Q函数训练的最小单位。每一步训练，我们希望让Q(s,a)更加靠近r+γQ(s)（其中，Q(s)用最大的一个Q(s,a)来衡量）。我们希望在训练完毕后，Q(s,a) = r+γ Q(s)对于所有(s,a,r,s)成立。这意味着某种程度上，强化学习的loss如下所示（此处的s’和a’与上面的s和a_是一个意思，符号不同），其中r为reward，

γ为Decay Rate：

下面，我们首先来介绍一种传统的方法：Q-learning。它是在深度学习崛起之前，一种十分具有代表性的、基于Q的方法。

Q-learning

考虑一个s离散有限，a离散有限的问题。一共有四种状态s1-s4，五种动作a1-a5。（此处s1,s2,s3这些是指游戏中可能出现的不同状态，与我们之前用来指不同时间的状态取值的s1,s2,…,sn含义不同）

传统的方法Q-learning做法如下：它生成一张Q表，表格各个位置记录不同的(s,a)对应的Q(s,a)的信息。其更新的方式十分简单，即对于每一条训练集数据(s,a,r,s)，从所有可能的a对应的Q(s,a)中找出最大值作为Q(s)（在Q-learning中，相当于找出Q表中s对应的那一行的最大值）。然后，在Q(s,a)对应位置的值进行修改，使得Q(s,a)更加接近于r+γ Q(s)。这种方法非常简单与直观。举例如下：

我们可以想象，当我们实现Q(s,a) = r+γ Q(s)对于所有(s,a,r,s)成立时，训练也就自动停止了。但是，当Q(s,a) = r+γ Q(s)对于所有(s,a,r,s)成立时，是否意味着目的达到了呢？要注意的是，这个等式右边的r是“客观”的，而Q(s_)是“主观”的。由于在等式的两边都有“主观”的部分，所以我们训练出来的网络很有可能与事实存在系统性偏差，即对于Q的估计整体偏高或偏低。这也正是强化学习和监督学习的不同之处。监督学习不存在上述的风险，而在强化学习中，我们必须考虑以下的风险。

局部收敛

所有含有Q网络的模型（包括DQN、Actor-Critic等等）都具有局部收敛的风险。局部收敛是一种特别值得我们关注的现象，它常常会导致我们的网络看似训练得完全没有任何问题，而实际的效果却一团糟。所以，我们在讲DQN的方法前，必须先专门花篇幅描述局部收敛的原因与降低其风险的方法。当我们理解了这一点之后，我们才能方便地理解接下来DQN与A3C算法中，为什么我们要采用一些特殊的trick。

我们首先来描述所谓的“局部收敛”究竟是什么情况。

针对一个具体问题，假设有一个客观存在的“最佳策略”。基于Q的方法的目的是能够计算出在“最佳策略”意义下，(s,a)的价值Q(s,a)与s的价值Q(s)（根据“最佳策略”的客观性，我们假设这些值也是客观存在的）。其达到目的的手段是尽量让Q(s,a) = r+γ Q(s)。如果我们真的能够实现目的，即能够计算出“最佳策略”下的Q(s,a)与Q(s)，则Q(s,a) = r+γ Q(s)对于所有(s,a,r,s)自然成立；但反之，当Q(s,a) = r+γ Q(s)对于所有(s,a,r,s_)成立时，训练已经停止，但我们却不能保证我们已经达到了目的，即我们算出来的(s,a)的价值Q(s,a)与s的价值Q(s)很可能与客观存在的“最佳策略”下(s,a)与s的价值不一样。

假设存在一个异于“最佳策略”的“套路”。让agent按照该“套路”进行游戏，能获得不错的Q，但是不如“最佳策略”好。假设在某一个时刻，对于所有的(s,a)与s，我们的Q函数求出的是它们在该“套路”下的Q(s,a)与Q(s)。这也就是说，对于所有(s,a)，Q(s,a)计算的是在s采取a，进入s之后，接着完全按照“套路”来，能够获得的总Q；对于s，Q(s)计算的是，从这个s开始完全按照“套路”来（包括选择当前的a），能够获得的总的Q。则此时，Q(s,a) = r+γ Q(s)对于所有(s,a,r,s_)成立，我们的网络也将停止更新。我们将这种情况称之为“局部收敛”。

用我们的人生做个比喻。当我们已经接受了某种价值观，比如我们相信金钱至上。我们判断所有人的地位高低（s）都按照他有多少钱去评判，所以自己的决策（a）也冲着能够让自己赚更多钱的角度去选择，则我们按照这种价值观也可以过完一生，过得或许还不错，取得了一定的r（快乐）。但是事实上，这未必是能够让我们活得最快乐的活法。我们或许能够活得更加洒脱，能够从帮助他人、从艺术创作、从休闲娱乐获得更多的快乐。但是，由于我们整个价值观已经形成了，对于那些帮助别人却穷困潦倒的人，对于那些风餐露宿的游吟诗人与街头画家，我们用我们的价值观判断他们的s只有很差的Q；对于他们热心帮助别人的行为、或是孜孜不倦地创造的a，我们也判断这些a只会导致更差Q。我们对他们的生活不屑一顾，对他们的所作所为嗤之以鼻，并因此不能从他们吸取什么经验，学会什么以改变自己的思想（取Q(s) = max Q(s,a)的时候，只会取出有关金钱的Q）。我们只是完全按照既有的价值观去生活、去一遍又一遍地重复自己每天做的事情，并且为之深信不疑……这就相当于陷入了局部最优。正如《瓦尔登湖》里面说的那样：“由于闭上了眼睛，神魂颠倒，任凭自己受影子的欺骗，人类才建立了他们日常生活的轨道和习惯，到处遵守它们，其实它们是建筑在纯粹幻想的基础之上的。”

对于任意的基于Q的算法，其无法真正意义上避免“局部收敛”的风险，因为其训练过程无一例外是设法让Q(s,a)接近r+γ Q(s)。当Q(s,a) = r+γ Q(s)对于一切(s,a,r,s_)成立时，更新自然停止，不以人的意志为转移。

虽然我们没有办法完全避免局部收敛，但是我们可以降低局部收敛的风险。具体的做法基于这样一种思想——我们希望在训练中间状态（即还远没有收敛到“最佳策略”的时候），对不同的s,a计算出的Q(s,a)与Q(s)是在衡量尽可能多种多样的“套路”下，(s,a)与s分别的价值。这样在训练时候，我们寻找Q(s)，即从寻找max Q(s,a)时，我们就可以从多种套路中寻找最佳的，继而能够逐渐综合不同“套路”的优势，以便渐渐找出“最佳策略”；反之，如果在训练的中间状态下，大多数的Q(s,a)都是衡量在同一个“套路”下的价值，则我们最终很有可能就是收敛到这个套路上的。

用上面的Q表举例。假如我们训练进行了一定的步骤时候，Q表中大量位置的Q(s,a)衡量的是“金钱至上”时候的价值观。当我们有训练集(s,a,r,s)时，我们设想Q(s,a)的价值应该接近r+γQ(s)。比如s是现在在读本科，a是选择申请读博士，而s就是进入了博士的生涯。为了确定s的价值，我们会寻找s_对应的那一行最高的价值。可那一行中，大多数的Q值都在在“金钱至上”的人生观下确定的，偶尔有一个别的人生观，比如“追求力量”，但是由于不是那一行最大的，也会被忽略。这也就是说，你对于读博之后下一步做什么，已经完全采取了“金钱至上”的价值观来判断。这样一来，(本科阶段，读博)的价值就会被我们判断得比较低，甚至不如选择读硕士高。但是，如果在中间的阶段里，你的表格有各种丰富的价值观，比如“追求真理”、“攀登科学高峰”，那么你就更加容易找出读博真正的好处。而不是快速地将对于所有s、对于所有a的判断都收敛到“金钱至上”价值观下的判断。

那么，对于Q-learning来说，我们避免局部收敛的关键就在于，要尽量避免表格中过早地有过多的格子显示的是统一“套路”下计算出的Q。事实上，对于DQN也是如此。（不过DQN没有这样的格子，所以不好表述）。

我们该如何避免呢？这就要让我们想我们到底是如何把一个较差的模型训练成较好的模型的——归根结底还是要依靠训练集。我们可以想象，一个“套路”意味着一些特定的关键步骤(s,a,r,s)按照某种顺序出现。而如果用这些(s,a,r,s)按照一定顺序来训练，也自然容易训练出“套路”。比方说，你有关读博的训练集都是说读博以后去找工作，和硕士生、本科生一起争相在赚钱，那么你当然也很容易训练出局部收敛的结果。如果你的训练集丰富一些，比如包含了博士毕业后去找工作的经历，也包含了博士毕业后去高校搞科研、勇攀科学高峰的信息，那么你就相对容易避免局部收敛。这就是说，一切要从训练集上做文章。

2018全国百所院校大数据公益巡讲活动

为普及大数据知识、宣传大数据文化，同时进一步推动数据科学的发展和大数据教学资源共享平台建设，北京大数据研究院博雅大数据学院特发起“2018全国百所院校大数据公益巡讲活动”。欢迎全国院校积极申报！