本文简要地介绍强化学习(RL)基本概念,Q-learning, 到Deep Q network(DQN),文章内容主要来源于Tambet Matiisen撰写的博客,以及DeepMind在2013年的文章“Playing Atari with Deep Reinforcement Learning”。
叙述思路如下:
----------------------------------------下面开始啦-------------------------------------------
看一个叫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)来描述:
假如我是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)。
为了获得长期的良好表现,我们不仅要考虑眼下的即时的奖励,还要考虑未来的收益。给定一个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值 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:
Q-learning获得Qtable的方法是通过基于Bellman equation不断迭代更新,最终收敛到准确的Q值。算法如下,其中 α
为learning rate。
仍以Breakout游戏为例,我们可以选择横板的位置、球的位置和移动方向,砖头的位置作为状态变量,然而,这样的状态只适用于这个游戏。如何选择更一般、更普遍适用的状态呢?显然,以图片所有像素值作为状态是更好的选择,它包含了这个场景下所有的情况和信息。
这就是DQN要发挥的作用。神经网络(NN)十分擅长从有结构的数据中提取好的特征,因此,我们可以用NN来近似 Q(s,a)
,以状态(如四张图)和动作为输入,输出对应的Q值。或者,另一种方式是,以状态作为输入,输入各种动作下对应的Q值,这种方法的优点是可以方便地从所有输出中找到最高的Q值,从而决定最优的动作。这两种方式的简图如下:
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算法稍后提到。
这一节主要介绍实现过程中的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-充分地探索:
最后,考虑experience replay和explore-exploit dilemma后,DQN算法如下:
写在最后
当然,还有更多的技巧使DQN能够更快更好地收敛,例如target network, error clipping, reward clipping等等。
这些RL方法最精彩的地方在于,一无所知到能够找到有效的策略完成特定的任务。回想我们随机地初始化模型,用这些随机初始的“垃圾”,一步一步学出有意义的内容。听起来不可思议,但RL确实做到了。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文系转载,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。