用于团队合作和 imperfect-recall 均衡计算的高效表示方法

《Artificial Intelligence》：Efficient representations for team and imperfect-recall equilibrium computation

　　卢卡·卡尔米纳蒂（Luca Carminati）| 张辉（Brian Hu Zhang）| 费德里科·卡恰马尼（Federico Cacciamani）| 李俊康（Junkang Li）| 加布里埃莱·法里纳（Gabriele Farina）| 尼古拉·加蒂（Nicola Gatti）| 图奥马斯·桑德霍尔姆（Tuomas Sandholm）
意大利米兰理工大学（Politecnico di Milano），莱昂纳多·达·芬奇广场32号（32 Piazza Leonardo da Vinci），米兰

**摘要**
在具有完美回忆能力的双人零和游戏中寻找平衡状态是一个被广泛研究的话题，这一研究在计算博弈论领域取得了许多突破性成果。本文旨在将这些技术推广到具有不完美回忆能力的（可解决时间的）双人零和游戏，或等价地推广到双人团队零和游戏。在这种情况下，计算混合策略纳什均衡（或等价的具有相关性的团队最大最小均衡）问题被认为是NP难的。我们通过一种称为“信念游戏”（belief game）的新构建方法，将不完美回忆情况与完美回忆情况联系起来。这种信念游戏等价于一个给定的具有不完美回忆能力的（可解决时间的）双人零和游戏。尽管信念游戏可能比原始游戏大很多，但可以使用任何标准方法来解决。然后我们展示了信念游戏中双方的策略空间可以直接表示为一个有向无环图（DAG），从而可能实现指数级的加速。我们称这种表示方法为“团队信念DAG”（Team Belief DAG，简称TB-DAG）。TB-DAG同时具备基本最优的参数化复杂性界限以及高效遗憾最小化技术的优势。在此过程中，我们还证明了在我们考虑的游戏中，寻找混合策略和行为策略的纳什均衡问题是Δ2P完全的（Δ2P-completeness）和Σ2P完全的（Σ2P-completeness）。实验结果表明，当TB-DAG与现有的学习技术结合使用时，在各种基准团队游戏中能够展现出最先进的性能。

**引言**
双人零和不完全信息扩展形式游戏（two-player zero-sum imperfect-information extensive-form games）是博弈论文献中的一个经典研究领域，拥有丰富的研究成果。这些游戏代表了两个对手之间的顺序互动，其中一个玩家获得的任何收益都意味着另一个玩家的损失。一个关键因素是玩家可能拥有不完整的信息，即他们可能无法区分游戏的当前节点和其他节点。在这种情境下，混合策略纳什均衡是模拟理性价值最大化玩家的最自然解决方案。混合策略指定了玩家的行为，表现为纯粹（确定性）策略的分布。然而，这种策略的数量呈指数级增长，使得计算纳什均衡的效率低下。为了解决这个问题，一个关键假设是完美回忆（perfect recall）。在完美回忆游戏中，玩家永远不会忘记之前收到的信息或采取的行动。当这个假设成立时：
1. 库恩定理（Kuhn’s theorem [1]）指出，混合策略等价于行为策略，即可以在每个决策点表示为动作分布的乘积的策略。
2. 策略空间的序列形式表示（sequence-form representation [2], [3]）使得可以通过多种不同的方法高效地计算纳什均衡。特别是，诸如反事实遗憾最小化（counterfactual regret minimization，简称CFR）[4]这样的解耦学习动态，可以通过在策略树的每个决策点使用遗憾最小化器来收敛到纳什均衡。
最近对基于CFR的技术进行了显著的加速改进[5], [6], [7]，并且其他技术也在CFR的基础上构建，例如抽象算法[9], [10]、子游戏求解[11], [12], [13], [14], [15], [16], [17]，进一步增强了可扩展性。在大规模游戏中的显著成果包括扑克[15], [16], [17], [18]、策略游戏（Stratego[19]）和外交游戏（Diplomacy[20]）。

本工作旨在将这些技术扩展到完美回忆的双人零和游戏之外的情况。特别是，我们专注于在不完美回忆游戏和对抗性团队游戏这两种等价情境下计算混合纳什均衡，已知计算纳什均衡在这两种情况下是NP难的[21]。
双人零和不完全回忆游戏的特征是玩家可能在游戏的某个时刻忘记信息。在这种情况下，混合策略对应于纯粹策略的分布，而行为策略对应于在每个决策点执行独立抽样程序的分布。与完美回忆游戏不同，库恩定理不适用于不完美回忆游戏：混合策略通常比行为策略更具表现力。不完美回忆游戏在文献中被用来通过遗忘来压缩游戏表示（例如一些抽象技术[22], [23], [24]），或者通过考虑具有不完美记忆的人类样代理[25]。
对抗性团队游戏描绘了两支代理团队之间的对抗。每个团队成员的效用与其队友相同，但与对方团队的成员相抵触。在这种情境下，有效的团队协调是一个非平凡的挑战，因为团队成员可能对当前节点有不同的不完整信息，并且在游戏期间没有通信渠道。直观上，由于隐私信息（例如仅向队友透露的私有卡片），玩家无法区分不同的节点。在这种情况下，混合策略对应于在游戏开始前通过预先协调确定的策略，而行为策略代表的是未经协调的策略，即每个代理独立于其他队友选择自己的行动。团队游戏的娱乐和非娱乐示例包括桥牌、有多个防御者和攻击者的安全游戏[26]，以及有勾结代理的扑克。
总体而言，团队游戏比不完美回忆游戏有更常见的应用场景；在均衡计算文献中有许多相关研究，并且提供了更直观的游戏描述。另一方面，不完美回忆游戏提供了更清晰的形式化表述。由于这两种视角对我们的目的来说等价，我们选择在本文的其余部分采用不完美回忆的视角来简化符号表示，同时使用团队游戏来说明一些引入的概念。

本文的主要目标是通过构建一个等价的完美回忆双人零和游戏，为团队/不完美回忆游戏提出一种新的表示方法。这使得可以使用之前为完美回忆双人零和游戏开发的所有解决方法。

**本文的贡献**
我们在第4.1节和4.2节中提出了一种算法，将任何双人零和不完全回忆游戏转换为策略等价的完美回忆游戏，我们称之为信念游戏（belief game）。在第4.3节中，我们正式证明了这两种游戏之间的等价性；在第4.4节中，我们展示了信念游戏大小的最坏情况界限，该界限与原始游戏的历史数量有关。特别是，我们展示了在最坏情况下，信念游戏的歷史数量为O(bdk)，其中b是原始游戏的最大分支因子，d是其深度，k是一个我们引入的参数，称为信息复杂度（information complexity），它直观地衡量了玩家可以忘记的信息量——或者在团队游戏的情况下，衡量团队内玩家之间的信息不对称量。
在第5节中，我们引入了一种DAG形式决策问题的概念（DAG-form decision problems），我们用它来将反事实遗憾最小化（CFR）技术推广到非树形游戏。虽然我们引入它是为了将其应用于不完美回忆游戏，但我们认为它本身也具有独立的学术价值。
在第6节中，我们使用DAG形式决策问题通过一种称为“团队信念DAG”（TB-DAG）的构造方法，高效地表示信念游戏中每个玩家的策略空间。我们展示了不完美回忆游戏的TB-DAG表示形式可以比信念游戏本身小得多，并且可以直接从原始游戏构建，从而在最坏情况下实现指数级的算法加速。这种构造将我们技术的最坏情况效率提高到了O(|H|(b+1)k+1)，其中|H|是原始游戏中的节点数量。我们还证明了这个界限基本上是最优的：在合理的计算假设下（即指数时间假设下），我们证明了不存在一种用于解决不完美回忆单人游戏的算法，其运行时间具有f(k)poly(|H|)的形式（即不依赖于b），对于任何函数f来说都是如此。
在第7节中，我们研究了计算具有不完美回忆的混合纳什均衡的计算复杂性。我们证明了在双方玩家都具有不完美回忆的游戏中，计算混合策略或行为策略的纳什均衡分别是Δ2P完全的（Δ2P-completeness）和Σ2P完全的（Σ2P-completeness）。
在第8节中，我们通过在不完美信息游戏的标准测试床上对我们的构建方法进行了实证评估，并与现有的最佳基线进行了比较。我们发现，当游戏的信息复杂度k较低时，我们的方法允许更快的均衡计算。

**初步介绍**
在以下内容中，我们将介绍游戏、策略和均衡的概念，重点关注策略表示的经典研究成果。我们指出，本文的主要贡献是将这些结果从完美回忆游戏的情境扩展到不完美回忆游戏和对抗性团队游戏。

**相关工作**
本节描述了在计算不完美回忆游戏和团队游戏中寻找纳什均衡方面最重要的相关工作。我们首先回顾了文献中关于不完美回忆游戏的结果。据我们所知，目前还没有专门针对计算不完美回忆和可解决时间游戏中的混合策略纳什均衡的高效算法的研究，而这正是本文的主要目标。Tewolde等人采用了类似的方法。

**基于信念和观察的混合纳什计算**
我们介绍了本文的基本贡献：一种基于构建等价完美回忆双人零和游戏的新技术，用于计算双人零和不完全回忆游戏（或等价地，计算对抗性团队游戏中的TMECor）的混合纳什均衡。
我们的技术通过适当改变玩家可用的信息和他们的行动集来实现完美回忆条件。信念游戏背后的主要直觉是...

**DAG决策问题**
在本节中，我们将发展DAG形式决策问题及其上遗憾最小化的通用理论，类似于第2节中的树形理论。尽管我们对DAG形式决策的主要兴趣在于将其应用于双人不完美回忆游戏（我们将在第6节中发展这一点），但本节中的观察结果也具有更广泛的适用性。例如，自从本文早期版本发布以来，已经出现了...

**团队游戏中的DAG决策问题**
在第4.5节中，我们发现将算法1的过程应用于算法2生成的信念游戏时，会受到游戏规模的影响，正如第4.4节所示，游戏规模可能会呈指数级增长。在本节中，我们展示了DAG决策问题如何大幅减少先前构造导致的低效率。
主要观察结果是，算法2通过将玩家的序列包含在信息集定义中来强制信念游戏的完美回忆。

**对抗性团队游戏的复杂性**
在这里，我们陈述并证明了在可解决时间的双人零和不完全回忆游戏中寻找各种均衡的几个复杂性结果。表2总结了我们的结果。
在所有情况下，目标都是解决以下承诺问题：给定游戏G、阈值v和误差ε > 0（其中所有数字都是有理数），确定游戏的（混合或行为）价值是否≥v或
**实验**
本节研究了在计算混合纳什均衡时应用tb-dag所带来的实证效益。如第1节和第3节所强调的，团队游戏方面的文献最关心混合纳什的高效计算，不同的工作建立了基准并提出了算法。因此，我们将重点比较我们的方法与那些先前的相关工作。我们的主要结果报告在表3中，该表报告了...

**结论**
本文提出了一种称为“团队信念dag”（team belief dag）的新颖双人零和表示方法，用于计算可解决时间的双人零和不完全回忆游戏中的混合纳什均衡以及对抗性团队游戏中的具有相关性的团队最大最小均衡。我们提出了一种转换机制，可以从完美回忆协调者的角度来理解，该协调者管理所有玩家的战略选择，而无需访问任何注定会被不完美回忆的信息。

**作者贡献声明**
卢卡·卡尔米纳蒂（luca carminati）：写作 - 审阅与编辑、原始草稿撰写、可视化、验证、软件开发、项目管理、方法论、研究、形式分析、概念化。
张辉（brian hu zhang）：写作 - 审阅与编辑、原始草稿撰写、可视化、验证、软件开发、项目管理、方法论、研究、形式分析、概念化。 **实验** 本节研究了在计算混合纳什均衡时应用tb-dag所带来的实证效益。如第1节和第3节所强调的，团队游戏方面的文献最关心混合纳什的高效计算，不同的工作建立了基准并提出了算法。因此，我们将重点比较我们的方法与那些先前的相关工作。我们的主要结果报告在表3中，该表报告了... **结论** 本文提出了一种称为“团队信念dag”（team belief dag）的新颖双人零和表示方法，用于计算可解决时间的双人零和不完全回忆游戏中的混合纳什均衡以及对抗性团队游戏中的具有相关性的团队最大最小均衡。我们提出了一种转换机制，可以从完美回忆协调者的角度来理解，该协调者管理所有玩家的战略选择，而无需访问任何注定会被不完美回忆的信息。 **作者贡献声明** 卢卡·卡尔米纳蒂（luca carminati）：写作 - 审阅与编辑、原始草稿撰写、可视化、验证、软件开发、项目管理、方法论、研究、形式分析、概念化。 张辉（brian hu zhang）：写作 ->
**实验**
本节研究了在计算混合纳什均衡时应用tb-dag所带来的实证效益。如第1节和第3节所强调的，团队游戏方面的文献最关心混合纳什的高效计算，不同的工作建立了基准并提出了算法。因此，我们将重点比较我们的方法与那些先前的相关工作。我们的主要结果报告在表3中，该表报告了...

**结论**
本文提出了一种称为“团队信念dag”（team belief dag）的新颖双人零和表示方法，用于计算可解决时间的双人零和不完全回忆游戏中的混合纳什均衡以及对抗性团队游戏中的具有相关性的团队最大最小均衡。我们提出了一种转换机制，可以从完美回忆协调者的角度来理解，该协调者管理所有玩家的战略选择，而无需访问任何注定会被不完美回忆的信息。

**作者贡献声明**
卢卡·卡尔米纳蒂（luca carminati）：写作 - 审阅与编辑、原始草稿撰写、可视化、验证、软件开发、项目管理、方法论、研究、形式分析、概念化。
张辉（brian hu zhang）：写作 - 审阅与编辑、原始草稿撰写、可视化、验证、软件开发、项目管理、方法论、研究、形式分析、概念化。>费德里科·卡恰马里（Federico Cacciamani）：负责写作（包括审稿和编辑）、调查研究、形式分析与概念构建。

**利益冲突声明**
作者声明存在以下可能被视为潜在利益冲突的财务利益或个人关系：
尼古拉·加蒂（Nicola Gatti）表示获得了意大利政府大学与研究部的财政支持。
图奥马斯·桑德霍尔姆（Tuomas Sandholm）表示获得了美国陆军研究办公室（US Army Research Office）的财政支持，以及国家科学基金会（National Science Foundation）和海军研究办公室（Office of Naval Research）的财政支持。