Geek AI 刘晓坤编译

理性强化学习遭遇瓶颈,进化算法会成为接替者吗?

人工智能和博弈论的交集催生了强化学习,但在博弈论基础上的问题求解通常依赖于理性和完美信息假设。在多智能体博弈环境下,这种条件的满足几乎是不可能的。作者分析了传统强化学习在这方面的局限,并讨论了进化强化学习作为替代方案的可能性。

人工智能(AI)的研究领域充满了无法回答的问题以及无法被分配给正确问题的答案。在过去,人工智能为它坚持「错误」的做法付出了代价,经历了一段时间的停滞,也就是所谓的「人工智能的寒冬」。然而,人工智能的日历刚刚翻入了春天,相关的应用领域正在蓬勃发展。

时至今日,人工智能的一个分支长期以来一直被人忽视,这里说的是强化学习强化学习最近在 AlphaGo 和 Atari 游戏中展示了令人印象深刻的结果。但说实话,这些都不是强化学习的胜利。在这些例子中,发挥更深层作用的是深度神经网络,而不是强化学习强化学习的研究水平仍然维持在它几十年前所达到的深度上。

当人们将强化学习应用到现实生活问题中时,情况就更糟了。如果训练一个机器人使其能在绳子上保持平衡听起来很困难,那么不妨试试训练一队机器人去赢得一场足球比赛,或者训练一队无人机来监视移动的目标。

在我们失去分支(强化学习)甚至是整棵大树(人工智能)前,我们必须提升对这些应用的理解。博弈论是用于研究拥有共同目标的参与者(player)团队在对弈中的应对策略的最常见方法。它能够赋予我们在这样的环境下指引机器学习算法的工具。

但是,需要注意的是这种常见的方法并不是一种与常识相符的方法,我们来看看为什么。

消除错误和建立新真理或事实一样好,甚至有时比它们更好。——Charles Darwin

首先,让我们从了解一些术语和这些领域的基础知识开始探索其奥秘。

博弈论

一些常用术语

  • 博弈:正如人们通常所理解的游戏,它可能是任何环境,其中参与者采取行动,并且博弈的结果取决于行动。

  • 参与者:在博弈中做出决策的人。

  • 策略:在给定一系列可能在博弈中出现的情况下,一个参与者采用的完整的行动方案。

  • 收益:参与者从博弈的特定结果中获得的收益。

  • 均衡:在一场博弈中,参与者都做出了他们的决策并且得到了结果的状态。

  • 纳什均衡:一种如果其它参与者的策略保持不变,任何参与者都不能通过改变他们自己的策略获得收益的均衡状态。

  • 占优均衡:无论一个参与者的对手如何选择策略,该参与者的策略都比其对手好的一种均衡状态。

囚徒困境

这可能是文献中最著名的博弈案例。其收益矩阵如下图所示。对于「收益矩阵」(又名支付矩阵)的介绍可能需要一千字的篇幅。对于一个有经验的人来说,一个收益矩阵就已经足够提供描述一场博弈所必需的所有信息了。现在,让我们稍微了解一下什么是「囚徒困境」。

囚徒困境的收益矩阵

警方逮捕了两名犯罪嫌疑人,嫌疑人 A 和嫌疑人 B。尽管臭名昭著,但由于缺乏证据,这两名嫌疑人不能因正在被调查的犯罪事实而入狱。但他们可以以较轻的罪名被拘留。

他们被囚禁的时间取决于他们将在审讯室中说些什么,而这就恰好引发了一场博弈。每位嫌疑犯(参与者)都有机会对另一名嫌疑犯保持沉默或告密。收益矩阵描述了每一名参与者将根据博弈的结果被囚禁多少年。例如,如果嫌疑人 A 保持沉默,而嫌疑人 B 告发了他们,嫌疑人 A 将服刑 3 年(收益为 -3),嫌疑人 B 则将不用服刑(收益为 0)。

如果你仔细研究这个收益矩阵,你会发现:参与者合理的行动应该是背叛另一个人,或者从博弈论的角度来说,背叛他人是占优策略。然而,如果每个人都选择背叛他人,将导致博弈走向纳什均衡,这意味着每个参与者都会得到 -2 的收益。

不觉得有什么奇怪的吗?是的,或许说至少本来就应该是这样。如果两位参与者都同意保持沉默,他们都会得到更高的奖励「-1」。囚徒困境是说明有时「合理的行动导致的结果比合作更差」的一个博弈的例子。

一些历史上的评价

博弈论起源于经济学,但是时至今日已经发展为一个跨学科的研究领域。博弈论之父,约翰. 冯诺伊曼(你可以看到冯诺伊曼在这个领域有着很好的职业前景)是第一个对「博弈」的一般概念进行严格形式化定义的人。为了便于分析,他把自己对博弈的研究限制在包含两个参与者(player)的情况。

之后,他与 Oskar Morgenstern 合著了一本书,这本书奠定了期望效用理论的基础,并逐渐形成了博弈论的课程。也正是大约在那个时候,John Nash 引入了纳什均衡的概念,这有助于描述博弈的结果。

强化学习

不久后,人们就意识到博弈论可能存在的应用范围是如此广阔:从游戏到生物学、哲学,再到不久后诞生的人工智能。现如今的博弈论与多个参与者通过强化学习进行训练的情况密切相关,这是一个被称为多智能体强化学习的领域。一个在这种情况下的应用实例是:假设我们有一队机器人(参与者),其中的每个机器人(参与者)都必须学会如何做才能有利于它的团队。

一些常用术语

  • 智能体:相当于参与者。

  • 奖励:相当于收益

  • 状态:用于描述智能体所处情况的所需要的全部信息。

  • 动作:相当于博弈中的行动。

  • 策略:与博弈论中的策略相类似,它定义了一个智能体在特定的状态下将采取的动作。

  • 环境:在学习过程中与智能体交互的所有事物。

应用

不妨想象一下如下的场景:一队无人机被释放到森林中,以便尽早预测和定位火灾,让消防员能及时做出反应。无人机是自动控制的,它们必须探索森林、学到可能引起火灾的条件,并且相互合作,这样一来它们就可以在消耗很少的电量并且进行较少的通信的情况下覆盖广阔的森林区域。

该应用属于环境监测领域,其中人工智能将技术的预测能力可以被用于指导人类的干预行为。我们所处的这个世界中的技术正在变得越来越复杂、而物理世界正面临着前所未有的挑战,现在我们可以将 Kipling 的名言「上帝不可能无处不在,所以他创造了母亲」改写为「人类不可能无处不在,所以他创造了无人机」。

去中心化的架构是另一个有趣的应用领域。像物联网区块链这样的技术创造了巨大的网络。信息和处理过程分布在不同的物理实体中,这种架构被公认为能够提供隐私性、高效性和民主性。

无论你想使用传感器来最小化一个国家的家庭能源消耗,还是想更换银行系统,去中心化都是一个新的吸引人的解决方案。

然而,让这些网络变得智能化是具有挑战性的。因为大多数我们引以为傲的算法都缺少训练数据并且渴望更大的计算能力。而强化学习算法正好可以用于高效的数据处理,并且使网络能够适应其环境中的变化。在这种情况下,为了提高整体的效率,研究各个算法如何协作是十分有趣的。

我们该使用深度学习还是集体学习呢?人工智能研究已经将其成果建立在越来越深的网络上,但对于挑战性问题的答案却可能来自于集体知识,而不是基于深度学习的个体。我们错过了一片大森林吗?

不仅仅是博弈

将人工智能问题转化成类似于囚徒困境的简单博弈是很吸引人的。这是测试新技术时常用的方法,因为它提供了一个计算成本低并且直观的测试平台。然而,重要的是不要忽略噪声、延迟、有限的内存等实际的特征对算法的影响。

也许,人工智能研究中最具误导性的假设莫过于与迭代静态博弈的交互表征的假设。例如,假设智能体一直没有经过学习、没有被改变,一个算法可以在每当它想要做出决策和规划时应用囚徒困境博弈。但是学习对智能体的表现又有何影响呢?与其它智能体的互动不会影响它的策略吗?

这一领域的研究集中在合作进化上,Robert Axelrod 曾经研究过囚徒困境的迭代版本中出现的最优策略。Axelrod 组织的锦标赛说明:适应时间和互动的策略(即使听起来和以牙还牙的策略一样简单)是非常有效的。在最近的进展中(https://arxiv.org/abs/1803.00162),人工智能社区研究了在「顺序囚徒困境」下的学习情况,但这方面的研究尚处于起步阶段。

多智能体学习和单智能体学习的区别在于大大提高的复杂性。训练一个深度神经网络已经足够痛苦了,而当我们再加入新的网络作为智能体的一部分时,这个问题的难度就以指数形式增长。

一个不太明显但是更重要的问题是,这类问题缺乏理论性质。单智能体强化学习是一个被充分理解了的研究领域,因为 Richard Bellman 和 Christopher Watkins 已经提出了学习所需的算法并进行了证明。然而,在多智能体学习的情况下,这种证明就失效了。

为了说明出现的一些令人困惑的问题:一个智能体执行一个学习算法去学习如何对它所处的环境做出最佳的反应。在我们提出的例子中,环境包括其他同样执行这个学习算法的智能体。因此,算法必须在它行动之前考虑其动作的影响。

早期的关注点

博弈论创立之初(在经济学中)就产生的关注点。让我们从研究经典博弈论下的系统所做的一些假设开始。

理性:一般在博弈论中,为了达到纳什均衡,假设存在完全的理性。这大致意味着智能体总是以自己的利益为出发点采取行动。

完美信息:每个智能体都了解关于博弈的一切信息,这些信息包括规则、其他的参与者所了解的信息,以及其它参与者的策略是什么。

共同知识:当所有的智能体都知道 P,并且所有的智能体都知道「所有的智能体知道 P」,所有的智能体都知道「所有的智能体知道『所有的智能体知道 P』」... 以此无休止地循环下去,这就是存在的共同知识。有一些有趣的谜题,比如蓝眼睛岛民之谜(http://mesosyn.com/mental1-2.html),描述了共同知识对一个问题的影响。

Kenn Arrow 在 1986 年表达了他对经典博弈论的保留意见。

在本文(http://dieoff.org/_Economics/RationalityOfSelfAndOthersArrow.pdf)中,我希望研究清楚理性假设在经济学理论中使用的一些意义。特别是,我想强调,尽管理性通常以个人形式呈现,但它不仅仅是个人的特性。相反,理性不仅仅聚集它自身的力量,还从它所处的社会环境中聚集了它的意义。在非常理想的条件下,这是最合理的观点。当这些条件不能被满足时,理性假设变得难以成立,甚至可能自相矛盾。

如果你觉得 Arrow 对于经典博弈论的假设有些苛刻的话,你认为你上次购买东西有多理性?或者说,你今天花了多少心思和努力在吃饭上?

但是 Arrow 并不太关心理性的假设本身。他关心的是理性假设所带来的影响。对于一个理性的智能体来说,你需要为它们提供做决策做需要的所有信息。这就需要无所不知的参与者,这样做有两个坏处:首先,它对参与者的信息存储和处理提出了不切实际的要求。其次,由于你可以通过一个中央的控制者的规则来取代所有的参与者的博弈(这哪里有趣呢?),博弈论不再是一个「多方对抗的博弈的理论」。

这个观点中,信息价值是另一个有趣的地方。我们已经讨论过,拥有所有的信息是不可行的。但是如果假设参与者都拥有的是有限的知识,会怎样呢?这样做有帮助吗?

你可以去请教任何涉足这个领域的人,但是一言以蔽之,在不确定性条件下的优化是很困难的。是的,还好我们有古老的纳什均衡。但是问题是,这个过程是无限循环的。博弈论并没有为你提供评价它们的依据。因此,即使你达到了一个纳什均衡,也没有什么大不了的。

强化学习的关注点

在这里,你应该认为人工智能应用比传统的博弈论所涉及的例子要复杂得多。就拿在机器人应用中使用纳什均衡方法的一些障碍来说:想象一下,你现在是机器人世界杯上的一队足球机器人的队长。你的队员和对手有多快、多强、多聪明?对手的队伍会采取什么策略?你该如何奖励你的队员?进球是庆祝的唯一理由吗?还是说表扬一次好的传球也能提升整支队伍的表现呢?显然,仅仅熟悉足球的规则也不会让你赢得比赛。

如果博弈论几十年来一直被争论不休,如果它是建立在不切实际的假设之上处理现实的任务的,如果它提出的解决方案是复杂、难以理解的,那么为什么我们还要继续研究它呢?很明显,这是我们在群体推理中唯一得到的研究成果。如果我们真正了解群体是如何进行交互和合作从而达到它们的目标,那么心理学和政治中的一些问题就会清楚的多。

多智能体强化学习领域的研究人员要么彻底地展开关于他们算法的理论性质的讨论(并且通常展现出好的结果),或者根据传统方法研究纳什均衡的存在。后一种方法似乎在这个领域的年轻研究者眼中,看起来像是一种证明:在严格的、不切实际的假设下,理论上存在的那种无限循环的、本身价值值得怀疑的解决方案,将永远不会在实践中被利用。

进化博弈论

进化博弈论的创立并不是最近发生的事,但是它在人工智能领域的广泛应用却经历了很长时间才被承认。它起源于生物学,在 1973 年由 John M.Smith 和 George R.Price 作为经典博弈论的替代者提出。这种改变是巨大的,我们可以说是讨论了一种全新的方法。

推理的主体不再是参与者本身,而是参与者组成的群体。因此,概率化的策略被定义为做出决策的参与者的百分比,而不是像在经典的博弈论中一个参与者选择一个动作的概率。随着策略进化为行为模式,理性的、无所不知的智能体便不再是必不可少的了。进化的过程类似于达尔文的学说。参与者遵循适者生存和随机突变的原则繁衍,这一过程可以通过一系列微分方程优雅地描述,被称为「复制器动力学」。

在下面的示意图中,我们可以看到这个系统的三个重要组成部分。群体代表智能体的团队,其特征为策略的组合。博弈规则决定了群体的收益,这也可以看作演化算法的适应度的值。最后,复制器规则描述了群体如何根据适应度值和进化过程的数学特性来进化。

图片来自于维基百科:(https://creativecommons.org/licenses/by-sa/3.0)

纳什均衡的概念以及对它的目标被「进化稳定策略」所取代。如果一种策略能抵御遵循另一种策略的群体的入侵(入侵的群体规模很小),它就满足「进化稳定策略」的特性。因此,可以在充分了解的动态系统的稳定性方面对团队行为进行研究,例如「Lyapunov stability」。

达到平衡状态需要一个不平衡的过程。理性行为在不平衡的状态中意味着什么呢?个体在平衡的过程中是否会对平衡状态进行推测?如果他们这样做了,不平衡可以在某种程度上被视为一个高阶均衡过程吗?

在上文中,Arrow 似乎在努力地寻找博弈的动态特性。那么进化博弈论能否给他一个答案呢?

最近,著名的强化学习算法,比如「Q 学习」,在这种新的方法的指导下被研究,并且取得了重要的研究成果。如何使用这种新的工具最终取决于应用场景。

我们可以采用前馈方法,推导出学习算法的动态模型。或者反过来,我们从一些期望得到的动态特性出发,设计一个能体现它们的学习算法。

我们可以描述性地使用复制器动力学,以可视化收敛过程。或者规范地对算法调优,以收敛到最优解。通过消除盲目调参的需要,后者可以极大地减小我们现在为所面对的艰巨任务训练深度网络时所引起的计算复杂度。

结论

追溯博弈论和人工智能何时以及为何交织在一起并不难。然而,不可忽视的是人工智能,尤其是多智能体增强学习在遵循经典博弈论方法时所面临的限制。

进化博弈论的论述听起来十分有前景,它提供了理论工具,具有实践的优势,但我们在自己动手尝试它之前不会真正知道其奥秘。由此看来,策略的进化并不是自然产生的,而是研究团体为了改进而进行的有意识的努力。但这难道不正是进化的本质吗?

摆脱一直推动你前进的思维惯性需要付出巨大的努力。但是,尽管强化学习在人工智能领域取得了广泛的成功,仍然急需得到提升。

原文链接:https://medium.freecodecamp.org/game-theory-and-ai-where-it-all-started-and-where-it-should-all-stop-82f7bd53a3b4

理论强化学习博弈论进化算法
3
相关数据
阿尔法围棋技术
AlphaGo

阿尔法围棋是于2014年开始由英国伦敦Google DeepMind公司开发的人工智能围棋程序。AlphaGo是第一个打败人类职业棋手的计算机程序,也是第一个打败围棋世界冠军的计算机程序,可以说是历史上最强的棋手。 技术上来说,AlphaGo的算法结合了机器学习(machine learning)和树搜索(tree search)技术,并使用了大量的人类、电脑的对弈来进行训练。AlphaGo使用蒙特卡洛树搜索(MCTS:Monte-Carlo Tree Search),以价值网络(value network)和策略网络(policy network)为指导,其中价值网络用于预测游戏的胜利者,策略网络用于选择下一步行动。价值网络和策略网络都是使用深度神经网络技术实现的,神经网络的输入是经过预处理的围棋面板的描述(description of Go board)。

深度神经网络技术
Deep neural network

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

区块链技术
Blockchain

区块链是用分布式数据库识别、传播和记载信息的智能化对等网络, 也称为价值互联网。 中本聪在2008年,于《比特币白皮书》中提出“区块链”概念,并在2009年创立了比特币社会网络,开发出第一个区块,即“创世区块”。

收敛技术
Convergence

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

博弈论技术
Game theory

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

无人机技术
Drones

无人机(Uncrewed vehicle、Unmanned vehicle、Drone)或称无人载具是一种无搭载人员的载具。通常使用遥控、导引或自动驾驶来控制。可在科学研究、军事、休闲娱乐用途上使用。

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

纳什均衡技术
Nash equilibrium

纳什平衡,又称为非合作赛局博弈,是在非合作博弈状况下的一个概念解,在博弈论中有重要地位,以约翰·纳什命名。 如果某情况下无一参与者可以通过独自行动而增加收益,则此策略组合被称为纳什均衡点。

支付矩阵技术
payoff matrix

支付矩阵是指在博弈论中,用来描述两个人或多个参与人的策略和支付的矩阵。不同参与人的利润或效用就是支付。

规划技术
Planning

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

囚徒困境技术
Prisoner's dilemma

囚徒困境(Prisoner's Dilemma)是博弈论的非零和博弈中具代表性的例子,反映個人最佳選擇並非团体最佳選擇。 或者说在一个群体中,个人做出理性选择却往往导致集体的非理性。

强化学习技术
Reinforcement learning

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

机器人技术
Robotics

机器人学(Robotics)研究的是「机器人的设计、制造、运作和应用,以及控制它们的计算机系统、传感反馈和信息处理」 [25] 。 机器人可以分成两大类:固定机器人和移动机器人。固定机器人通常被用于工业生产(比如用于装配线)。常见的移动机器人应用有货运机器人、空中机器人和自动载具。机器人需要不同部件和系统的协作才能实现最优的作业。其中在硬件上包含传感器、反应器和控制器;另外还有能够实现感知能力的软件,比如定位、地图测绘和目标识别。之前章节中提及的技术都可以在机器人上得到应用和集成,这也是人工智能领域最早的终极目标之一。

深度学习技术
Deep learning

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法。观测值(例如一幅图像)可以使用多种方式来表示,如每个像素强度值的向量,或者更抽象地表示成一系列边、特定形状的区域等。而使用某些特定的表示方法更容易从实例中学习任务(例如,人脸识别或面部表情识别)。 近年来监督式深度学习方法(以反馈算法训练CNN、LSTM等)获得了空前的成功,而基于半监督或非监督式的方法(如DBM、DBN、stacked autoencoder)虽然在深度学习兴起阶段起到了重要的启蒙作用,但仍处在研究阶段并已获得不错的进展。在未来,非监督式学习将是深度学习的重要研究方向,因为人和动物的学习大多是非监督式的,我们通过观察来发现世界的构造,而不是被提前告知所有物体的名字。 至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

物联网技术
Internet of Things

物联网(英语:Internet of Things,缩写IoT)是互联网、传统电信网等信息承载体,让所有能行使独立功能的普通物体实现互联互通的网络。物联网一般为无线网,而由于每个人周围的设备可以达到一千至五千个,所以物联网可能要包含500兆至一千兆个物体。在物联网上,每个人都可以应用电子标签将真实的物体上网联结,在物联网上都可以查出它们的具体位置。通过物联网可以用中心计算机对机器、设备、人员进行集中管理、控制,也可以对家庭设备、汽车进行遥控,以及搜索位置、防止物品被盗等,类似自动化操控系统,同时通过收集这些小事的数据,最后可以聚集成大数据,包含重新设计道路以减少车祸、都市更新、灾害预测与犯罪防治、流行病控制等等社会的重大改变,实现物和物相联。

刘晓坤
刘晓坤

机器之心编辑

返回顶部