Jesus Rodriguez作者魔王、杜伟参与

博弈论速成指南:那些融入深度学习的经典想法和新思路

随着人工智能的发展,博弈论迎来了复兴。关于博弈论,数据科学家需要了解哪些经典思想和新思路呢?本文作者就这些问题一一展开了分析。通过此文,相信读者会对博弈论的概念和分类有更清晰的理解。

博弈论是最让人着迷的数学领域之一,它影响了多个不同领域,如经济学、社会科学、生物学,显然还有计算机科学。博弈论的定义有很多,但我认为以下这个定义非常有帮助,尽管它过分简洁:


博弈论是具备激励机制的概率。

游戏在人工智能发展过程中起到关键作用。对于初学者而言,游戏环境在强化学习模仿学习等领域中逐渐成为流行的训练机制。理论上,任何多智能体 AI 系统都要经历玩家之间的游戏化交互。构建游戏原则的数学分支正是博弈论。在人工智能语境和深度学习系统语境下,要想使多智能体环境具备一些必备的重要能力,博弈论必不可少。在多智能体环境中,不同的 AI 程序需要交互或竞争才能达成目标。

博弈论的历史与计算机科学史密不可分。目前博弈论领域中的许多研究可以追溯至阿兰·图灵、冯·诺伊曼这些计算机科学先驱的工作。因电影《美丽心灵》而闻名于世的纳什均衡(Nash equilibrium)是现代系统中很多 AI 交互的基础。但是,利用博弈论原则多次建模 AI 宇宙超出了纳什均衡的范畴。想理解如何利用博弈论构建 AI 系统,最好先理解我们在社会或经济互动中常遇到的博弈类型

我们每天参与数百种基于游戏动态(game dynamics)的交互。但是,游戏化环境的架构与此完全不同,其激励和参与者目的也不相同。如何将这些原则应用到 AI 智能体建模中呢?这个难题推动 AI 研究某些领域的发展,如多智能体强化学习

显然,游戏是博弈论最具可见性的实体,但它远远不是应用博弈论概念的唯一空间。也就是说,还有很多其他领域也受到博弈论和 AI 的共同影响。大多数需要多个「参与者」合作或竞争才能完成任务的场景都可以利用 AI 技术进行游戏化和改进。尽管之前的陈述是一种泛化,但我认为它传达出了一个信息:博弈论和 AI 是一种思考和建模软件系统的方式,而不只是一种技术。

利用博弈论的 AI 场景应包含不止一个参与者。例如,Salesforce Einstein 这类销售预测优化 AI 系统就不是应用博弈论原则的完美场景。但是,在多智能体环境中,博弈论又有明显不同。

在 AI 系统中建构游戏动态需要两步:


  • 参与者设计:博弈论可用来优化参与者的决策,以获得最大效用;

  • 机制设计:逆博弈论(inverse game theory)主要为一组智能参与者设计游戏。拍卖就是机制设计的经典案例。


那么 AI 时代的数据科学家又需要了解哪些博弈呢?这些博弈彼此之间是否存在着联系呢?本文作者、Invector Labs 首席科学家兼执行合伙人 Jesus Rodriguez 对此发表了自己的看法。

本文作者 Jesus Rodriguez。

数据科学家应该知道的 5 种博弈

假设我们正在构建一个需要多个智能体互相合作竞争才能完成特定目标的 AI 系统,即博弈论的经典场景。自 20 世纪 40 年代诞生以来,博弈论专注于建模最常见的交互模式,现在我们每天在多智能体 AI 系统中看到的就是它们。理解环境中不同类型的游戏动态是设计高效游戏化 AI 系统的关键元素。从较高层次来看,五元素标准有助于理解 AI 环境中的游戏动态,即对称 vs 非对称、完美信息 vs 非完美信息、合作 vs 非合作、同时 vs 序列和零和 vs 非零和。下面将一一展开介绍。

作者提出的五元素标准。

对称 vs 非对称

最简单的一种博弈分类方式是根据对称性进行分类。在对称博弈环境里,每个玩家具备同样的目标,结果仅取决于策略。国际象棋就是一种经典的对称博弈。我们在现实世界中遇到的很多场景缺少对称的数学优雅性,因为参与者通常目标不同,甚至还存在冲突。商务谈判则属于非对称博弈,参与各方目标不同,并从不同的角度来评估结果(例如,赢得合同 vs 最小化投资)。

完美信息 vs 不完美信息

另一种重要的博弈分类方式基于可获取信息类型。完美信息博弈指每个玩家都能够看到其他玩家的行动,例如国际象棋。在很多现代交互的环境中,每个玩家的行动是对别人隐藏的,博弈论将这些场景归类为不完美信息博弈从扑克等纸牌游戏到自动驾驶汽车,不完美游戏博弈就在我们身边。

合作 vs 非合作

在合作博弈环境中,不同的参与者可以通过结盟来最大化最终结果。合同谈判通常被认为是合作博弈。在非合作博弈环境中,参与者禁止结盟。战争是非合作博弈的终极案例。

同时 vs 序列

在序列博弈环境中,每个玩家了解对手之前的动作。棋盘游戏本质上最具序列博弈属性。在同时博弈场景中,双方可以同时行动,例如证券交易。

零和 vs 非零和

零和游戏指一方有得其他方必有失,例如棋盘游戏。非零和游戏中,多个玩家可以从其他玩家的动作中获益。经济交互中多个参与者合作扩大市场规模就是非零和博弈

纳什均衡

对称博弈统治 AI 世界,其中大多数基于 20 世纪最著名的数学理论之一:纳什均衡纳什均衡以美国数学家 John Forbes Nash 命名。本质上,纳什均衡描述了这样的场景:每个玩家选择一个策略,当一个玩家不改变策略时,没有玩家能从改变策略中获益。

已故美国数学家、经济学家 John Nash。

纳什均衡是一个优美且强大的数学模型,它可以解决很多博弈论问题,但在一些对称博弈环境中捉襟见肘。对于初学者而言,纳什方法假设玩家具备无限的计算能力,而现实环境中几乎不存在这种情况。

此外,很多纳什均衡模型无法解释风险概念(常见于大多数非对称博弈场景,如经济市场)。因此,很多非对称博弈场景很难利用纳什均衡实现。在多智能体 AI 系统中这一点尤为重要,这需要在解决方案的数学优雅性和实现的可行性中找到合适的平衡。

博弈论中正在影响机器学习的新想法

多智能体 AI 系统是 AI 生态系统中最让人着迷的领域之一多智能体系统等领域的近期进展扩展了博弈论的边界,它依赖该领域中最复杂的思想。作者在下文又列举了出现在现代机器学习中的博弈论子领域的示例。

平均场博弈

平均场博弈(Mean Field-Games,MFG)是博弈论中比较新的领域。MFG 理论诞生于 2006 年,是 Minyi Huang、Roland Malhamé、Peter Caines、Jean-Michel Lasry 和菲尔兹奖得主 Pierre-Louis Lions 发表的一系列独立论文中的一篇。

从概念上看,MFG 包含的方法和技术用于研究由「理性博弈方」组成的大群体下的微分博弈。这些智能体不光对自己的状态(如财富、资产)有偏好,对群体中其他智能体的分布也存在偏好。MFG 理论为这些系统研究泛化纳什均衡

经典的案例是如何让几个鱼群以比较协调的方式沿相同方向游动。理论上,这种现象很难解释,不过它基于这一事实:鱼对最邻近鱼群的行为有反应。具体而言,每条鱼并不关心其他鱼,但是它关心附近作为一个整体统一移动的鱼群。如果我们用数学术语表述的话,鱼对鱼群的反应是哈密顿-雅可比-贝尔曼方程(Hamilton-Jacobi-Bellman equation,简称 HJB 方程)。而整个鱼群的行动是所有鱼的动作集合,这对应了福克-普朗克方程(Fokker-Planck-Kolmogorov equation)。平均场博弈理论是这两个公式的结合体。

平均场博弈中的鱼群统一游动经典案例。

随机博弈

随机博弈可以追溯至 1950 年代,由诺贝尔经济学奖获得者 Lloyd Shapley 提出。从概念上来看,随机博弈由有限数量的玩家在有限状态空间中执行,在每个状态中,每个玩家从有限多的动作中选择一个;最终动作组合决定了每个玩家的奖励和下一个状态的概率分布

已故数学家、随机博弈概念提出者 Lloyd Shapley。

随机博弈的经典形式是哲学家晚餐问题:有 n + 1 位哲学家 (n ≥ 1) 坐在圆桌旁,圆桌中间有一碗米饭,任意两位相邻的哲学家之间有一根筷子,筷子在两人可及范围内。由于桌子是圆的,因此筷子的数量与哲学家人数一样。为了吃到碗中的米饭,每位哲学家需要拿到可及范围内的两根筷子。如果一位科学家吃到了,那么他的两位邻座就不能同时吃到。哲学家的生活很简单,只有思考和吃饭,为了生存,哲学家必须一次次地思考和吃饭。该任务就是设计一个使所有哲学家生存下去的机制。

随机博弈中的哲学家晚餐经典案例。

演化博弈

演化博弈论(Evolutionary Game Theory,EGT)从达尔文进化论中获得灵感。EGT 的起源可以追溯至 1973 年的 John Maynard Smith 和 George R. Price,也可以作为策略来分析,该数学标准可用于预测竞争策略的结果。

从概念上看,EGT 是博弈论概念在如下场景中的应用:通过选择和复制的进化过程,随着时间的变化,智能体群体使用不同策略来创建稳定的解决方案。EGT 的主要思想是很多行为涉及群体中多个智能体的交互,任意一个智能体的成果都离不开其策略与其他智能体策略之间的交互。经典博弈论专注于静态策略(即策略不随时间变化),而演化博弈论专注于策略随时间的变化,以及在进化过程中最成功的动态策略。

EGT 的经典案例是鹰鸽博弈,即让鹰和鸽子围绕可共用资源竞赛。在该游戏中,每位选手严格遵循以下策略中的一个或全部:

  • 鹰:发起攻击行为,在受伤或对手后退之前绝不停下。

  • 鸽:如果对手发起攻击行为,直接撤退。


如果我们假设存在如下情况:1)当两个个体都发起攻击行为时,战斗最终走向结束,二者具备同等受伤概率;2)战斗成本将个体的健康度降低了某个常量 C;3)当鹰鸽相遇时,鸽子直接逃跑,鹰获取资源;4)两只鸽子遇到资源并平分资源,则鹰鸽博弈的健康情况如下所示:


博弈论

很多案例不需要优化参与者的策略,而是围绕理智参与者的行为设计游戏,这就是逆博弈论。拍卖被认为是逆博弈论中的主要案例。

总之,随着人工智能的发展,博弈论正在复兴。阿兰·图灵或冯·诺伊曼等计算机科学界传奇人物提出的博弈论原则现在已经是全球某些最智能系统的核心,人工智能近期进展也有助于推动博弈论研究的发展。随着 AI 继续进化,我们将看到更多博弈论新想法找到融入主流深度学习系统的方式。

原文链接:https://towardsdatascience.com/a-crash-course-in-game-theory-for-machine-learning-classic-and-new-ideas-50e33ba2636d
入门深度学习冯诺依曼阿兰·图灵博弈论
4
相关数据
哈密顿人物

William Rowan Hamilton爵士MRIA(1805年8月4日 - 1865年9月2日)是一位爱尔兰数学家,他为经典力学、光学和代数做出了重要贡献。 虽然哈密顿不是物理学家(他认为自己是一个纯粹的数学家)他的工作对物理学起着至关重要的作用,特别是他对牛顿力学的重新定义,现在称为哈密顿力学。 这项工作已被证明是对电磁学等经典场论的现代研究以及量子力学发展的核心。 在纯数学中,他最出名的是四元数的发明者。

纳什均衡技术

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

随机博弈技术

随机博弈(stochastic game)在博弈论中是一类由一个或多个参与者所进行的、具有状态概率转移的动态博弈,由劳埃德·夏普利(Lloyd Shapley)于20世纪50年代初期提出

深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

机器学习技术

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

零和博弈技术

零和博弈,又称零和游戏或零和赛局,与非零和博弈相对,是博弈论的一个概念,属非合作博弈。零和博弈表示所有博弈方的利益之和为零或一个常数,即一方有所得,其他方必有所失。在零和博弈中,博弈各方是不合作的。非零和博弈表示在不同策略组合下各博弈方的得益之和是不确定的变量,故又称之为变和博弈。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

非合作博弈技术

在博弈论中,非合作博弈是一种在个体参与者之间进行竞争的游戏,其中由于缺乏执行合作行为的外部手段(例如合同法),只有自我实施(例如通过可靠的威胁)联盟是可能的, 与合作博弈相反。非合作博弈的关键特征是没有执行规则的外部权限。它主要强调一个人进行自主的决策,而与这个策略环境中其他人无关。

概率分布技术

概率分布(probability distribution)或简称分布,是概率论的一个概念。广义地,它指称随机变量的概率性质--当我们说概率空间中的两个随机变量具有同样的分布(或同分布)时,我们是无法用概率来区别它们的。

数据科学技术

数据科学,又称资料科学,是一门利用数据学习知识的学科,其目标是通过从数据中提取出有价值的部分来生产数据产品。它结合了诸多领域中的理论和技术,包括应用数学、统计、模式识别、机器学习、数据可视化、数据仓库以及高性能计算。数据科学通过运用各种相关的数据来帮助非专业人士理解问题。

自动驾驶汽车技术

自动驾驶汽车,又称为无人驾驶汽车、电脑驾驶汽车或轮式移动机器人,是自动化载具的一种,具有传统汽车的运输能力。作为自动化载具,自动驾驶汽车不需要人为操作即能感测其环境及导航。

哈密顿-雅可比-贝尔曼方程技术

哈密顿-雅可比-贝尔曼方程(Hamilton-Jacobi-Bellman equation,简称HJB方程)是一个偏微分方程,是最佳控制的中心。HJB方程式的解是针对特定动态系统及相关成本函数下,有最小成本的实值函数。

博弈论技术

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

多智能体系统技术

一个多智能体系统,是由一个在一个环境中交互的多个智能体组成的计算系统。多智能体系统也能被用在解决分离的智能体以及单层系统难以解决的问题。智能可以由一些方法,函数,过程,搜索算法或加强学习来实现。尽管存在相当大的重叠,然而一个多智能体系统并不总是一个基于智能体的模型表现一致。

完美信息博弈技术

在经济学中,完全的信息是完美竞争的特征。 随着市场信息的完善,所有消费者和生产者都被假定在对自由市场体系进行理论化和财务政策效应时,对产品的价格,效用,质量和生产方法有完整的认识。

模仿学习技术

模仿学习(Imitation Learning)背后的原理是是通过隐含地给学习器关于这个世界的先验信息,就能执行、学习人类行为。在模仿学习任务中,智能体(agent)为了学习到策略从而尽可能像人类专家那样执行一种行为,它会寻找一种最佳的方式来使用由该专家示范的训练集(输入-输出对)。

强化学习技术

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

暂无评论
暂无评论~