博弈论新研究：通用算法胜过专用博弈算法

在博弈论领域，无论是扑克牌对局还是房屋竞价，参与者往往都处于信息不完全的状态。你清楚自己手中的牌，或者自己能承受的最高出价，但对手的底牌或报价上限对你来说始终是个谜。

近日，一篇由麻省理工学院（MIT）研究人员联合撰写的论文在今年4月于里约热内卢举办的国际学习表征会议（ICLR）上发表。该研究针对两名参与者之间的”零和”博弈（即一方所得必为另一方所失）这一经典场景，就信息不完全博弈提供了全新的研究视角。

参与该项目的MIT研究人员包括：麻省理工学院电气工程与计算机科学系（EECS）及信息与决策系统实验室（LIDS）的博士生Sobhan Mohammadpour，以及EECS助理教授、LIDS主要研究员Gabriele Farina。其他合作作者来自德克萨斯大学奥斯汀分校、加州大学伯克利分校、卡内基梅隆大学和纽约大学等多所高校。

该研究的核心议题是：哪类算法更适合训练神经网络参与信息不完全博弈？长期以来，学界普遍认为，基于博弈论原理的专用算法在这一场景下必然优于通用的策略梯度方法。策略梯度方法是一类兴起于20世纪90年代的通用决策算法，其中”策略”即指行动方案，”梯度”则指向变化最大的方向，类似于沿山坡寻找最高点的路径。该类方法通过持续迭代与修正，引导智能体逐步趋近目标。

然而，在多智能体场景下，策略梯度方法的分析难度大幅提升。Farina解释道：”虽然仍然存在可以改善自身处境的方向，但由于对手的行动，这个方向会随着博弈进程不断变化，有时甚至变化极为迅速。”

论文合著者Sokota指出：”此前，学界几乎将专用博弈论算法视为此类场景的不二之选。但我们的研究表明，策略梯度方法的表现可以优于这些专用算法，而专用算法的效果或许并没有人们想象中那么好——这引发了一个有趣的问题：为何这一现象长期未被发现？部分原因在于，该领域此前缺乏对算法进行严格评估的工程实践，导致难以判断究竟哪种方法更有效。”

因此，这项研究的一大核心贡献在于：提供了一套公平客观的评估框架，用于衡量各类能够训练神经网络参与信息不完全博弈的算法。Rudolph说：”我们采取了一种不同的思路。与该领域许多论文不同，我们并非提出一种可以击败其他算法的新算法，而是构建一个能够评估这些算法的基准测试体系。”

简而言之，基准测试是一套用于评估算法性能的软件体系。Farina表示：”我们提供的是一个测试平台，研究人员可以将自己的算法放入其中，针对特定任务进行训练，并观察其表现。”

研究团队采用”可利用度”这一概念来衡量参与者的表现——即在面对”最坏情况下的对手”时，一方能取得怎样的结果。Sokota解释说：”以扑克为例，这个对手不会知道我手中的牌，但会知道在任意一手牌的情况下我将如何行动。”可利用度得分为零代表完美博弈，得分越高则表明策略越次优。

研究团队共进行了五款游戏的实验：两个版本的”暗棋井字棋”（玩家无法观察对手的落子情况）、棋盘游戏Hex的两种信息不完全变体，以及一款名为”骰子谎言”的欺骗性博弈游戏。

研究面临的最大挑战在于：如何将可利用度指标应用于规模如此庞大的博弈场景——某些游戏的状态空间多达300亿个。Mohammadpour解释说：”所谓’状态’，不仅包含所有可能的棋盘布局，还涵盖整场游戏的完整历史，包括每一步的决策与失误。”他补充道，此前研究人员通常只将可利用度指标用于规模缩小约10万倍的游戏。

实验结果表明，在这五款游戏中，使用策略梯度算法训练的神经网络获得了更优（更低）的可利用度评分；在随后进行的直接对抗赛中，策略梯度训练的网络再次击败了基于博弈论算法训练的对手。Rudolph表示：”这些结果令人振奋，因为它们进一步验证了我们基准测试方法的可靠性。”

研究团队已将基准测试软件免费开放，并致力于降低其使用门槛。Mohammadpour说：”不需要超级计算机，普通笔记本电脑就能运行。只需在常用的基准测试软件库OpenSpiel中添加一行代码即可。”

Farina希望将这项研究置于更宏观的视野下加以理解：”‘博弈’这个概念实际上适用于任何多智能体战略互动的场景，因此本研究所得出的结论绝不局限于休闲游戏领域。”

Vinitsky对此表示赞同：”隐藏信息是现实世界的重要属性，它广泛存在于军事行动、交易场景和谈判过程等诸多领域，而这些场景都是在信息不完全的条件下进行的。如果我们能在博弈中取得更好的表现，那么在上述其他场景中同样有望获得改善。”

未参与本研究的谷歌DeepMind计算机科学家及博弈论专家Ian Gemp对上述研究成果表示认可：”这项工作有力地提醒我们，对策略梯度方法等经典工具进行现代化改造，仍是解决复杂战略问题的高效路径。”

Q&A

Q1：策略梯度方法是什么，它在博弈论中起什么作用？

A：策略梯度方法是一类兴起于20世纪90年代的通用决策算法，通过持续迭代与修正，引导智能体逐步趋近目标。在博弈论中，它被用于训练神经网络参与信息不完全博弈。MIT的最新研究表明，这类通用算法的表现甚至可以超越专为博弈设计的专用算法，打破了此前学界的普遍认知。

Q2：可利用度指标是如何衡量博弈中玩家表现的？

A：可利用度衡量的是玩家面对”最坏情况下的对手”时的表现。以扑克为例，这个对手不知道你手中的牌，但了解你在任意一手牌下的行为模式。可利用度得分为零代表完美博弈，分数越高则说明策略越次优。MIT研究团队将这一指标成功应用于状态空间多达300亿个的大规模博弈场景，远超以往研究的规模。

Q3：MIT发布的这套博弈算法基准测试工具有什么特点？

A：这套基准测试工具已免费开放，使用门槛极低，普通笔记本电脑即可运行，无需超级计算机。研究人员只需在常用的基准测试软件库OpenSpiel中添加一行代码即可使用。该工具提供了一个公平的评估平台，可对训练神经网络参与信息不完全博弈的各类算法进行客观比较。