深度解读AlphaGo胜利背后的力量:强化学习

本文是 Adit Deshpande「深度学习研究评论」系列文章的第二期。每两个星期左右,他都会总结并介绍一些有关于深度学习的一些特定子领域的研究论文。在上周,介绍了 生成对抗网络,而本周这篇文章将着重介绍强化学习。

Cover6th.png

强化学习简介

机器学习的三大种类

在介绍相关论文之前,先让我们探讨一下什么是强化学习。机器学习可以被划分为三大领域:

  1. 监督学习

  2. 非监督学习

  3. 强化学习

IRL1.png

首先来看第一类,监督学习。较其它两类而言,多数人更熟悉监督学习。它的基本思想是通过训练特定的数据来获得一个函数,也可以称作模型(model)。我们可以把这些数据称作训练集,每一组数据都包含了相应的输入以及对应的正确的结果。卷积神经网络就是监督学习中一个很好的例子。输入的数据是一些包含了不同物体的照片,比如猫、狗或者其他事物。输出便是这些图片上事物对应的分类。


与监督学习不同,非监督学习不是通过数据来进行学习,而是通过聚类分析(cluster analysis)来实现分类。非监督学习中最著名的算法就是 K-Means(K-均值)算法。


与前两者不同的是,强化学习可以在不同的情景或者环境下学习采取不同的行动,以此来获得一个最佳的强化信号值。监督学习和强化学习之间一个比较有趣的区别是:在强化学习中,通过强化信号你只能知道在一个特定的事件中所采取的方案的实际效果是好还是坏,强化学习不会告诉你一个最佳的方案。就比如说强化学习不会像前文提到的卷积神经网络那样,对于每一张特定输入的图片会给出一个与之对应的分类。强化学习的另一个比较独特的部分在于 agent 的行动将会影响后续接收的数据。比如说当一个 agent 左移而非右移的时候就表明该 agent 下一次在该环境中会接收不同的数据。先让我们看一个例子吧。

强化学习问题

我们先来探讨一下强化学习中出现的问题。我们假设在一个小房间里面有一个微型机器人,我们没有对这台机器人写入程序,也就是说例如移动,或者其他任何的行为都没有被事先设定,它仅仅是呆在原地不动。我们称这个机器人为 agent。

IRL2.png

我们曾经在前面提到过,强化学习是通过尝试做出一些决定或者行动来得到一个最佳的反馈奖励信号 R。这个奖励信号表明了在给定的情景下,agent 采取的行动到底怎么样,也就是说我们可以通过这个反馈信号来得知 agent 的表现如何。agent 在每个时间点和状态下采取的动作叫作动作空间 A,它是一个可以告诉 agent 它当前所采取的行动是否得当的函数。我们用 S 来表示状态空间,它用来描述 agent 当前所在的环境情况状态。我们把不同环境状态和相应行动之间的映射关系叫作策略 P。该函数可以决定一个 agent 在不同的时间和不同的环境下所采取的行动。还有一个价值函数 V,它用来度量当前状态的好坏。这听起来和奖励信号 R 类似,但是又不同于奖励信号,因为奖赏信号是在直接意义上指示了当前情景下所采取的行动是好还是坏,而价值函数更多地是指示在长期的过程中所采取的行动造成的影响的好坏。最后,我们用 M 模型来指代 agent 在当前环境中的表示。这个 agent 的模型表示着环境将会如何发生变化。

IRL3.png

马尔科夫决策过程 MDP

来让我们回到前面的假设,一个微型机器人静止在一个小房间里面。如何去定义奖励函数取决于我们希望这个机器人去完成什么样的工作。就比如说,当我们希望这个机器人可以移动到房间的一个角落去,如果这个机器人成功到达了我们指定的位置,那么它将获得 25 的奖励值。同时,机器人每经过一个步骤,都要消耗 1 的奖励值去完成这个步骤,也就是说奖励值将-1。当然,我们希望机器人能尽可能地到达我们所指定的位置。机器人可以有 4 种行进的方式,分别是往东、南、西、北四个方向运动。机器人的策略也很简单,简单来说就是,策略总是会控制机器人到能使价值函数值更大的地方。那么什么地方价值函数的值会最大呢?当然是机器人正好到达我们所指定的位置(这就是前文所提到的具有长期积累效应的奖励值)。


现在,我们用马尔科夫决策过程来描述整个强化学习环境。对于在这之前没有听说过马尔科夫决策过程的人,我们会简单介绍下它的相关内容。马尔科夫决策过程可以充当一个 agent 做决策的过程框架。它包含一组有限的状态(对于这些状态,我们用一个价值函数来评判它们的价值)、一组有限的行动集、一个策略函数和一个奖励函数。其中,我们把价值函数分类两个小项:

  1. 状态价值函数(state-value function)V:在状态 S 下,并且遵循给定了的策略 π,该函数计算在未来的各个阶段的奖励总和来得到一个价值。(其中用 gamma 来表示每一个步骤的权值因子,举个例子来说就是接下来的一步操作肯定比第 10 步的权重大)。

    IRL4.png

  2. 动作价值函数 (action-value function)Q:在状态 S 下,并且遵循给定了的策略 π,同时采取行动 a,该函数计算出一个价值并且返回它(和上面的等式相比,除了添加了一个额外的行动变量 a,其他条件与上面的函数完全一致)。

到目前为止,我们了解了马尔科夫决策过程的相关组件,可是我们用它来做什么呢?现在就让我们来解决这个问题。通过解决一个马尔科夫问题,我们就可以找到一个最佳的策略。这个策略的目的是让 agent 可以获取当前环境下的每个状态的奖励的最大值。

解决马尔科夫决策过程

我们可以通过使用动态编程(dynamic programming),特别是通过使用策略迭代(还有另一种称为值迭代的技术,但现在不会用到)来解决 MDP 并获得最优策略。其主要思想是我们采取一些初始的策略 π1 同时也计算出该策略的价值函数。我们可以通过贝尔曼期望方程来实现上述思想。

IRL5.png

简单来说,这个等式表示,在遵循策略 π 的条件下,我们的价值函数可以被分解成所我们所期望的立即奖励 Rt+1 和下一个状态 St+1 的价值函数值求和形式。如果你仔细想想,你就会发现,这个等式的定义就是我们在前文中所用到的价值函数。这个函数就是我们策略评估的一部分。为了获取更好的策略,我们使用了一个策略改进步骤,在这个步骤中,我们只对价值函数采取了一种贪心的模式,换句话说,agent 只采取能让价值最佳化的行动。

IRL6.png

为了得到一个最佳的策略,我们将重复这两个步骤,不停地循环,直到我们收敛到了最优策略 π*。

如果没有一个可用的 MDP 怎么办

迭代策略要获得很好的结果有且仅当我们拥有给定可用的 MDP。MDP 在本质上告诉了你这整个环境是如何工作的,但是在现实生活中,这显然是不可能给定一个已经可用的 MDP 的。当我们没有一个给定的 MDP 的时候,可以使用免费的模型方法直接从 agent 的经验和相互作用以及价值函数和策略的环境中获得策略。所以,即使在没有 MDP 的情况下,我们仍然可以采取与策略评估以及策略改进相同的步骤。


我们并没有通过优化价值函数来改进我们的策略来达到上述目的,我们是通过动作价值函数 Q 来优化策略。还记得在前面我们将状态价值函数分解为立即奖励函数和下一个状态的价值函数的和的形式吗?我们可以对 Q 函数做同样的事情。

IRL7.png

现在,我们将重复上述过程。在这里,我们除了把价值函数 V 换成价值函数 Q 以外,策略评估以及策略改进过程都与前文所讲的步骤完全相同。所以,我们现在跳过评估和改进的步骤。如果想要了解没有 MDP 评估和改进方法,如蒙特卡罗强化学习、时间差异化学习以及 包含了它们所有相关知识的 SARSA(如果你对此感兴趣,请听听 David Silver 的课程 Lecture 4Lecture 5)。现在,我要前进到价值函数近似以及 AlphaGo 和 Atari 论文中讨论的方法,希望让你了解一下现代强化学习技术。

价值函数近似

如果你将我们到现在所学的东西都回想一下的话就会发现我们用了相对简单的方法解决了问题。来看看上面提到的 Q 方程,我们采取了一个特定的状态 S 和一个行动 A,然后用此条件计算出一个值,它基本上可以告诉我们所期待的值是什么。我们假想一下,如果我们的 agent 向右移动一毫米,那么我们就得到了一个新的状态 S',对于这个新的状态,我们同样需要计算相应的 Q 价值。在现实世界中的强化学习问题中,我们有不可计数的状态,所以我们不可能记录下每一个可能状态下的价值。很重要的一点就是要让我们的价值函数去理解一种泛化的思想。这种方法就是使用了价值函数近似策略,它可以推广到未知的状态。


所以,我们需要的就是一个函数,让我们称它为 Qhat,它可以在给定的一些状态 S 和行动 A 的情景下近似价值 Q。

IRL8.png

Qhat 除了需要参数 S 和 A 以外,还需要一个表现良好的权值向量 W(当你看见这个 W,你可能已经猜测到我们将使用梯度下降的方法),它将计算 x(它只是一个表示 S 和 A 的特征向量)和 W 之间的点积。我们改进这个函数的方法是计算正确的 Q 值(让我们假设这个值是给定的)与近似函数的输出之间的差值。

IRL9.png

当我们计算得出了这个差值以后,我们通过迭代来获得该差值的最小值,在这个时候,我们便得到了最优的权值向量。这种函数近似的想法在我们接下来将要看到的论文中是十分关键的。

多说一句

在我们看论文之前,我想再说一说最后一件事。有一个和强化学习相关的有趣的讨论,即:探索与开发(exploration vs exploitation)。开发是指在 agent 的整个过程中采取的行动都是已知的,所以每次采取的行动都能获得最佳的奖励。这听起来还不错吧?agent 将始终根据其当前的知识采取最好的行动。然而,这里的关键之处就是在于当前的知识都是已知的。假设 agent 没有获取到整个状态空间,那么就不能确定它是不是采取了最优的策略。与之相反,探索的主要目的就是去挖掘这些未知的状态。


这种想法可以很容易的与现实世界所关联起来。假设现在你需要选择一个餐厅作为今晚吃饭的场所。你(现在你就是 agent)很喜欢吃墨西哥美食,所以在强化学习系统中,你将采取的最好的行动就是去墨西哥餐厅,因此你将得到一个最优的奖励值,并且这个选择能给你带来很强的幸福感。当然你也可以选择意大利餐厅,不过你从来没有尝试过意大利菜。所以有一种可能就是,它可能比墨西哥菜更美味,或者不如墨西哥菜。所以说,到底是利用以前的知识直接进行选择还是尝试一下新的事物而可能获得更大的奖励值呢?这就是强化学习中的一个主要挑战(这也是我们生活中的挑战)。

强化学习相关的其他学习资源

哇,这里有相当多的信息。当然,这绝不是对该领域的全面概述。如果你想更深入地了解强化学习,我强烈推荐这些资源给你。

  • David Silver(来自 Deepmind)的强化学习资料 Video Lectures

  • Sutton 和 Barto 的 强化学习教科书(如果你决定在这个子领域中有所进步,那么这个资料你不得不看)

  • Andrej Karpathy 的强化学习相关的 博客(如果你想从入门开始,并且想要看到一个在实际中做得很好的例子,那么你就来这里学习吧)

  • 伯克利 CS 188 Lectures 8-11

  • 开放人工智能工具包:当你对强化学习有一定了解,并且想切身实际的去创建你自己的 agent,那你就来使用 Open AI 提供的强化学习工具包吧。

强化学习 DQN(强化学习与 Atari 游戏)

IRL10.png

介绍

这篇文章由谷歌 DeepMind 在 2015 年 2 月发布,并且被评选为了世界著名科学周刊 Nature 的封面。这也是第一次将深层神经网络与强化学习相结合的成功的尝试之一(这篇文章是 DeepMind 的原文)。该论文表明,他们的系统能够在 49 种 Atari 游戏上与专业游戏测试者进行同等水平的对战。现在就让我们来看看它是怎么实现的吧。

方法

还记得我们在本文开头介绍的文章中提到的东西吗?我们在前面提到了我们的主要目标就是去优化我们的行动价值函数 Q。Deepmind 的人们通过深度 Q 网络或 DQN 来完成这个任务。这个网络能够得出优化 Q 之后的成功的策略,所有这些策略都来自游戏屏幕上像素和当前分数。

网络架构

来让我们仔细看看 DQN 有哪些输入。考虑到游戏 Breakout,所以选择 4 张游戏中最常用的帧。每一帧一开始都是一张 210 x 160 x 3 的图像(该图像是彩色的,并且其宽度和高度是 210 和 160 个像素)。然后再对这些帧做一些预处理,他们便被压缩到了 84 x 84 了(即使不知道如何做也无所谓,如果想要查看细节请参考论文第 6 页)。现在我们有一个 84 x 84 x 4 的三维卷输入。这个卷将被插入到一个卷积神经网络 (教程) 中然后经过一系列的卷积 和 ReLU 层。网络的输出是一个 18 维向量,其中每个数字都是用户可以采取的可能的动作(上移、下移、左移等)的 Q 值。

IRL11.png

好的,在此之前,先让我们弄明白怎么去训练这个网络才能让它得到一个准确的 Q 值。首先我们先记住我们现在正在尝试优化的东西。

IRL12.png

这与我们之前所提到的 Q 函数的形式相同,在这里我们用 Q * 来表示所有 Q 的最大值。现在让我们思考思考我们该如何获得这个 Q *。现在,我们只需要明白我们需要的是 Q * 的一个近似值,即我们的函数所近似的值(Qhats 函数)。换句话说,我们需要记住这个想法就好了。为了找到最佳的策略,我们可以把它构造成某种监督学习问题,然后把它预测的 Q 函数值与一些预期的 Q 函数值进行比较,然后再不断得往正确的方向进行调整即可。


所以,想要实现上面提到的方法,我们就得需要一组训练集。就比如我们在前文提到例子中,我们需要创建一组经验集来存储 agent 的状态,动作,奖励和每个时间点的下一个状态。让我们更具体的描述一下这个问题。我们用一个元组 D 来表示 agent 在每个步骤时间点的参数集,其形式为(st,at,rt,st + 1)。随着 agent 与环境的交互越来越多,这个数据集将会随着时间的推移而慢慢构建。现在,我们要对这些数据进行随机批处理(假设数据为 64 个时间步长),然后使用损失函数计算每个数据的误差,然后按照梯度下降方法来改进我们的 Q 函数的近似值。

IRL13.png

由此可见,损失函数所做的事情就是优化 Q 网络函数近似值(Q(s,a,theta))与 Q 的学习目标之间的均方误差(MSE)。让我快速解释一下。上面提到的 Q 学习目标是在当前行动 a' 下的奖励值 r 加上最大 Q 值(下一个时间步长的 Q 值)。


当损失函数计算完成以后,就对 θ 值(或 w 向量)取导数。然后就可以通过更新这些值来使损失函数最小化。

总结

这篇论文中最让我喜欢的部分之一就是它对游戏的某些点的值所做的可视化。

IRL14.png

你应该还记得,价值函数基本上是衡量「在特定情况下多好」。如果你看看论文中 #4 的内容,你就会知道,基于球的轨迹和砖的位置,我们必定会遇见很多点,然后它们刚好可以代表高价值函数值。


这 49 款 Atari 游戏都使用了相同的网络架构、算法和超参数,这种让人印象深刻的方法强有力的证明了这种强化学习方法具有很强的鲁棒性。

掌握使用强化学习的 AlpahGo

IRL15.png

介绍

4-1。本文记录了 DeepMind 的强化学习 agent 击败了世界上最好的围棋选手之一的李世石的故事。如果你不了解相关的内容,你可以认为围棋是一种策略形式的游戏,游戏双方不停的在棋盘上占领自己的领土。由于它的游戏场景和移动方式多得让人不可思议,所以它也被认为是人工智能史上最难的游戏之一。这篇论文首先比较了围棋与其它普通棋盘游戏之间的差别,比如象棋和跳棋。其他的棋盘游戏都可以通过搜索决策树算法来发动攻击,但是围棋不行,因为在围棋中,大约有 250 的 150 次方种动作序列。所以说,这时候就需要用到强化学习了。让我们来看看 AlphaGo 是如何打败了具有优势的人类。

方法

AlphaGo 决策的基本思想是选择和评估。对于任何强化学习的问题(尤其是在棋盘游戏中),我们都需要一种评估当前环境或者说当前位置的方法。这种方法就是我们的价值网络。同时,我们也需要一种通过策略网络选择行动的方法。对于价值和策略,我想我们已经很熟悉了。

网络架构

让我们先看看,这两个网络的输入值都是什么。在这个游戏中,棋盘被划分成了一个 19 x 19 的网格,我们可以通过一系列的卷积层来构建一个对当前状态较好的表示。首先来看一看我们的监督学习策略网络。这个网络将的输入值是一个棋盘状态的图像,然后它会输出 agent 可以采取的所有动作的概率分布。在游戏开始之前,团队人员就使用 3000 万种不同的棋盘状态对它进行了训练。每一种棋盘状态都标注了在当前状态下棋盘专家可能的举动。除此之外,该团队还训练了一个稍微小一点的网络,不过它可以更快地输出相关的策略。


就目前为止,深度卷积神经网络只能对你当前可能采取的行动进行预测,给出当前棋盘状态的表示。当使用强化学习的时候,我们使用策略梯度的方法来提高了我们的策略网络的能力。还记得在上一篇论文中,我们尝试去优化我们的价值函数 Q 吗?现在,我们将直接去优化我们的策略(我们需要更多的时间与篇幅去介绍策略梯度,David Silver 在 Lecture 7 中就对此做了很好的介绍)。从一个更高级别层面来看,我们通过在之前迭代的网络与当前网络之间模拟游戏来提高策略。如果当前网络赢了就获得+1 的奖励,输了就-1. 这样我们就能通过常规的梯度下降来改善我们的网络了。

IRL16.png

到现在,我们已经有一个很好的策略网络了,它可以告诉我们在哪里落子才是最佳的选择。那么接下来就是价值网络了。

IRL17.png

在行动 S 和使用的策略 P 的条件下,预测出游戏的结果。


为了获得最佳的 V*,我们可以使用以前的带有权值向量 W 的近似值函数。其中权值 W 由价值网络在状态的基础上进行训练所得,所以其结果是成对出现的(和我们在上一篇论文中讨论的相关内容类似)。

在有了这两个网络之后,我们接下来要做的事情就是使用蒙特卡罗树搜索方法把所有的参数部件都组合在一起。蒙特卡罗背后的基本思想是它通过前瞻搜索来选择最佳的动作,其中树中的每条路径都着储动作值 Q,以及访问次数和先验概率。由此可见,蒙特卡罗算法将在当前的状态下选择最佳的行动 A。系统中的这部分内容更多的是运用的传统的人工智能方法而不是强化学习方法。如果你想了解更多的细节,那么就来看这篇论文吧,在论文中我们做了更多的总结。

总结

在最困难的棋盘游戏中,一个计算机系统打败了世界顶级高手,这还需要什么结论吗?


非常感谢 David Silver 对强化学习所制作的优质课程以及各种方程式。

入门强化学习理论综述AlphaGo游戏
返回顶部