学术前沿 | 多人随机博弈中纳什均衡计算复杂度为PPAD-Complete

 导读 

本文是北京大学人工智能研究院多智能体中心邓小铁教授团队与杨耀东助理教授团队在National Science Review上发表论文On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games的介绍。

该工作引入了近似马尔科夫完美纳什均衡（Markov Perfect Nash Equilibrium, MPE）作为多人一般和随机博弈（Multi-player General-Sum Stochastic Games）计算问题的解概念，并证明了该解概念的PPAD-Complete复杂度。其解概念保留了马尔科夫性质，为多智能体学习算法由静态双人博弈成功扩展到动态多人随机博弈奠定了计算复杂度理论基础，为分布式人工智能、多智能体系统研究开辟了新的路径与思路。

论文链接：

https://academic.oup.com/nsr/advance-article/doi/10.1093/nsr/nwac256/6840228?searchresult=1

01

博弈论与人工智能

未来的AI是什么样子？牛津大学计算机科学系主任迈克尔·伍尔德里奇（Michael Wooldridge）于2019年在T-EDGE全球创新大会上表示：“人工智能未来发展的趋势会是多智能体，AI之间能实现智能互联。就像人生活在充满丰富社交的社会当中，AI也可以学会人类的社交方式，并与其他智能体达成协同。”多智能体是由多个AI作为个体而构成的有机统一整体。近年来，伴随着深度学习、强化学习算法与大数据技术的发展，多智能体研究领域迎来了新的机遇，尤其是多智能体系统的动态演化更是成为社会、经济、军事等领域重点关注的方向。但多智能体系统中庞大的智能体数量、复杂的交互行为、异构且多样的策略选择为博弈均衡点的求解带来了极大困难。

随机博弈（也称马尔科夫博弈）作为一种重要的博弈形式，是描述多智能体交互的核心数学模型，为研究多智能体学习、博弈与最优决策奠定了理论框架。具体来说，随机博弈是一种由多个参与者进行的具有状态转移概率的动态博弈过程，每个参与者独立地在每一轮博弈中决定自己的策略，根据当前状态与动作获得本轮奖励，下个阶段的状态根据状态转移概率以及所有玩家的动作发生转移，不断重复。在具体场景中，智能体（玩家）通常表现为合作、竞争或合作与竞争相交叠，分别对应于共有奖励函数、零和奖励函数与一般和奖励函数。

如图1所示，随机博弈可以应用于广泛的领域，包括经济学、计算机科学和工程学等。在经济学中，它可用于研究拍卖机制、议价策略等许多涉及竞争和不确定性的问题。在计算机科学中，它可用于研究如何在不确定环境中设计多智能体的决策算法。在工程中，它可用于分析具有随机组件的系统的性能，例如通信网络和智慧电网。

图1.随机博弈的应用场景

02

求解纳什均衡策略

随着时间的推移，所有玩家均存在动态发展到其策略选择稳定的极限状态，此状态下所有玩家都没有动机去通过更改策略选择来获得更大奖励，即达到了纳什均衡。在纳什均衡中，每个参与者都不会认为自己可以通过改变当前策略来改善自己的收益，所以是一种不涉及预测的稳态。因此，建立稳态的描述均衡解的概念对智能体最优策略的选择至关重要。基于此，本文进一步提出了MPE的解概念，该解概念相比于传统纳什均衡的特点是它能有效表达多玩家在一般和随机博弈中的动态行为过程。具体来说，MPE是一种更具体的纳什均衡，适用于这样一种场景：玩家在博弈每个阶段的决策仅取决于博弈的当前状态，也就是玩家的策略必须是“无记忆的”，即不能依赖于博弈的历史决策与状态，而只能依赖于当前状态。这一解概念为研究分布式AI, 多智能体学习算法提供了便利，例如在多智能体强化学习（Multi-agent Reinforcement Learning）中，随机博弈中的MPE解概念能够扩展到包括多智能体多轮策略交互的各类动态场景，可用于研究多人动态博弈中的最优决策与均衡点。

然而，现有对多智能体博弈均衡策略的求解需要较强的假设条件，许多求解算法受限于处理二人零和博弈或多人纯合作博弈，对于一般和博弈，即同时存在竞争与合作的博弈，求解需要较强的额外假设。在面向大规模、且合作与竞争相交叠的动态多智能体交互的场景中，求解均衡策略对智能体建模、准确地选择策略与其他智能体交互协调至关重要，是实现能泛化、可扩展的通用人工智能的关键。

在随机博弈中确定MPE的复杂性是求解均衡策略的基础，由于一般和动态博弈求解具有很高的复杂性，因此求解一般和随机博弈中MPE的计算复杂度同样面临巨大挑战。已有研究表明，在无界 (infinite-horizon)随机博弈中求解MPE至少是PPAD困难的。PPAD（“有向图的多项式校验参数”）在计算机科学中代表了一个复杂度类，它由Christos Papadimitriou于1994年引入，通常被用于刻画博弈论中均衡点计算的复杂度。PPAD是一个介于P和NP当中的复杂度类，PPAD问题是否存在多项式时间解法与P是否等于NP相似，是一个悬而未决的难题。

图2. 复杂度包含关系的大致示意图（不严格）

邓小铁教授曾在2006年证明了单一状态下双人一般博弈(normal-form game)的纳什均衡计算是PPAD-complete。此工作也荣获了当年FOCS的最佳论文奖。而在本工作中，邓小铁教授团队与杨耀东助理教授团队进一步证明了多人随机博弈中纳什均衡的计算“相当于”单一状态双人纳什均衡的计算，如图3所示，即他们证明了多人一般和随机博弈中近似MPE的计算复杂度也是PPAD-complete的。也就是说双人单步纳什均衡的计算与多人随机博弈的MPE计算具有相同的复杂度。

图3.双人一般博弈（左）和多人随机博弈（右）

证明多人随机博弈的纳什均衡计算复杂度具有深远意义。近年来，强化学习领域有多种多人随机博弈的学习与求解算法尝试以单轮一般博弈求解算法作为算法的组成模块。本工作通过揭示多人随机博弈与单轮一般博弈的深刻联系与等价性，为这类算法提供了计算复杂度方向的理论保证，同时启发人们更好地从单轮一般博弈的求解出发设计高效的多智能体强化学习算法。它为研究多智能体动态决策开辟了新的理论保障，对研究多智能体交互与学习机制具有关键价值，是近年来博弈论与多智能体系统研究方向上的重要理论突破。

—   往期发布  —

     点击图片查看原文

点击图片查看原文

学术前沿 | 赋予AI语言理解和场景感知的能力，实现目标导向的室内人体运动生成

点击图片查看原文

—   版权声明  —

本微信公众号所有内容，由北京大学人工智能研究院微信自身创作、收集的文字、图片和音视频资料，版权属北京大学人工智能研究院微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿在本号刊登内容，请及时通知本号，予以删除。