这里是普通文章模块栏目内容页
理性强化学习遭遇瓶颈,进化算法会成为接替者吗?
技术沙龙 | 6月30日与多位专家探讨技术高速发展下如何应对运维新挑战!

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

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

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

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

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

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

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

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

——Charles Darwin

 

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

博弈论

1. 一些常用术语

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

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

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

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

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

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

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

2. 囚徒困境

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

囚徒困境的收益矩阵

囚徒困境的收益矩阵

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

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

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

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

3. 一些历史上的评价

#p#分页标题#e#

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

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

二、强化学习

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

1. 一些常用术语

智能体:相当于参与者。

奖励:相当于收益

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

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

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

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

2. 应用

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

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

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

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

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

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

三、不仅仅是博弈

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

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

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

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

#p#分页标题#e#

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

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

四、早期的关注点

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

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

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

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

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

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

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

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

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

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

五、强化学习的关注点

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

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

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

六、进化博弈论

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

#p#分页标题#e#

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

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

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

图片来自于维基百科:(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

【本文是51CTO专栏机构“机器之心”的原创文章,微信公众号“机器之心( id: almosthuman2014)”】

收藏
0
有帮助
0
没帮助
0