100行的神经网络增强学习游戏实践

在之前的两篇文章中,我简单的介绍了Q-Learning和Multi Arm Bandit问题,这两个问题一方面状态比较简单,FrozenLake只有十六种状态;另一方面动作和反馈比较直接,Multi Arm Bandit每次动作都会立刻返回奖励。

今天我们来介绍一下这些问题的更严肃的形式,Markov Decision Processes(马尔科夫决策过程)。

马尔科夫决策过程

一个马尔科夫决策过程可以由一个四元组M=(S,A,P,R)组成:

  • S (States): 表示状态集合。
  • A (Actions): 表示动作集合。
  • P: 表示状态转移概率,比方在状态s时执行动作a,转移到状态s’时的转移概率就是p(s’|s,a)
  • R: 表示回报函数,在进行状态转移的时候我们可以得到一定的回报r(s’|s,a)
  • γ: 折扣因子,用来权衡未来回报和当前回报。

马尔科夫决策过程的问题核心就是找到一个策略(policy): 函数π将状态映射到一个动作。一旦我们把状态和动作通过策略联系起来,就得到了一个马尔科夫链。

我们的目标就是选择一个策略π,最优化现在和未来得到的回报总和。

马尔科夫决策过程看似简单,但其实我们生活中的每一个任务都可以被描述成马尔科夫决策过程。比方说,你感受到的一切都是状态,每一个状态下你可以做不同的动作,得到不同的回报。打开大门你可以去看美丽的风景,吃甜食可以奖励自己的胃,努力工作可以赚钱。

马尔科夫决策过程的回报可以写作Value Function,然后通过迭代和动态规划来求得最优结果。但是由于很多问题的状态数过多,计算量很容易随着状态数的增长到达一个无法控制的量级,所以人们发明了很多技术来对回报进行估计,或者对应该做的行为进行猜测,这也就引出了今天要讲的简单的基于Neural Network的增强学习实现。

Cart-Pole Task

为了更好的使用Neural Network,我们需要一个比之前提到的赌博机更复杂一点的问题。这次我们从OpenAI提供的经典问题Cart-Pole入手,该任务的目标是控制cart的移动,使在cart上面的连接杆保持垂直不倒,OpenAI将任务简化到只有两个离散动作,向左用力和向右用力。

在解决问题之前,我们需要知道这个任务的状态,动作,和回报是什么。

状态: 一个四元组,形容当前连接杆的重心以及角度,这个四元组就是我们决策神经网络的输入。

动作: 一个二维向量,代表向左用力还是向右用力,根据输出进行采样。

有了状态和动作,我们就可以定义出一个神经网络(这里我仅仅添加了一层隐藏层),通过当前的状态输入计算出不同的输出动作概率。再反向优化的时候,我们需要根据实际动作actual_action,得到选择该动作的计算值actual_output,最后优化选择的损失函数-log(output)*reward

回报: 我们的任务目标是尽可能的让连接杆在空中保持平衡,换句话说我们需要维持对当前和未来都有利的移动方式。为了实现这一点,我们用一个time decay函数对回报进行折扣。除此之外,因为我们需要考虑不止一次的经验,所以需要一个缓冲区收集状态和进行的动作,然后批量的对神经网络进行修改。

最后,这是我们的主要过程:

实现效果:

小结

在实现这个问题的过程中,我也看到了很多不同的文章,有的文章提到用Deep Q Network来解决问题,有的则是采用基于Neural Network的Policy Gradients。我曾一度纠结于Q-Learning和Policy Gradients的区别,终于在看了一些分析文章后略知一二了。

Q-Learning是一种旨在逼近回报函数Q的学习方法,参见下图,目标优化(y-Q(s,a|θ))²,每次动作采取argmax Q(s,a|θ)。而Policy Gradients是直接预测接下来要进行的动作,采取的动作是根据输出得到的softmax函数进行采样(具体参见上一章节的程序部分)。

通常我们认为Policy Gradients可以应用到更多的问题上,因为很多问题的Q函数是非常复杂的,但是Policy Gradients仍然可以直接在策略空间上进行优化。与此同时,Policy Gradients在很多时候会比Q-Learning收敛的更快(但有可能是局部最优)。最后,Policy Gradients可以很好地学习动作概率分布,但是Q-Learning则要经过复杂的离散化过程。

说来说去,看起来Policy Gradients要比Q-Learning好很多,为什么我们不直接采用Policy Gradients解决所有的增强学习问题呢?这就和我上文提到的局部最优解有关了,Policy Gradients方法估计的梯度和结果方差很大,我们每次需要观测一系列任务状态<s,a,r,s’>,这种方法也被成为Monte Carlo方法,估计结果会有比较多的噪音,导致结果不稳定。相反,Q-Learning稳定性和效率可能会更好。

空谈无用,以后有机会我们就来对比一下两种方法吧。

推荐:

Google发表的Deep Q Network论文。

一篇很好的对比Q Learning,DQN,和Policy Gradients的文章。

马尔科夫决策过程和一些额外的资料。

用Tensorflow实现简单的基于Neural Network的Policy Gradients算法。

同一个任务基于DQN的实现方法。

Source: Deep Learning on Medium