🤖 machine learning

NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

本文介绍了 NashPG，这是一种可扩展的策略梯度算法，它采用迭代优化的正则化方法，以确保在双人零和不完全信息博弈中收敛至纳什均衡，并在经典基准测试以及无限注德州扑克等大规模领域上优于现有方法。

原作者： Eason Yu, Tzu Hao Liu, Clément L. Canonne, Yunke Wang, Chang Xu, Nguyen H. Tran, Stefano V. Albrecht

发布于 2026-05-01

📖 1 分钟阅读☕ 轻松阅读

原作者： Eason Yu, Tzu Hao Liu, Clément L. Canonne, Yunke Wang, Chang Xu, Nguyen H. Tran, Stefano V. Albrecht

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你正在与一位聪明的对手进行一场高风险的纸牌游戏，但你无法看到对方的手牌。你们双方都希望找到一种完美的策略，使得无论对方采取什么行动，你都不会被欺骗或利用。在博弈论中，这种完美且无法被利用的状态被称为纳什均衡。

在复杂的游戏（如扑克或战舰）中寻找这种“完美平衡”对计算机而言极其困难。本文介绍了一种名为NASHPG（纳什策略梯度）的新方法，旨在帮助计算机学习这些完美策略。

以下是其工作原理的简明故事：

问题：“粘滞”陷阱

此前，研究人员试图通过在训练过程中添加一个“正则化”项来寻找这种完美平衡。可以将正则化想象成一个磁性锚点。它将计算机的策略拉向某个特定的安全点，以防止其过度摇摆。

然而，这里有一个陷阱：

锚点过于强大：如果你将锚点固定在同一个位置，计算机会被困在那里。它会找到一个“安全”的策略，但并非完美的纳什策略。这就像被锚定在河流中央的一块岩石上；你不再随波逐流，但也无法到达目的地。
旧方法笨拙：之前的尝试涉及复杂的数学运算，要求计算机检查游戏树中的每一个可能动作。这就像试图阅读图书馆里的每一本书来寻找一句话；这种方法适用于小型图书馆，但在面对互联网规模的问题时则会失效。

解决方案：“可移动锚点”（IMMD）

作者首先提出了一种理论构想，称为IMMD（迭代磁性镜像下降）。

想象你试图找到一间黑暗房间的中心。

旧方法：你站在一个位置，摸索墙壁，然后停留在那里。
本文的方法：你向中心迈进一步，然后将你的锚点移动到新的位置。接着再迈一步，再次移动锚点。

通过不断将“锚点”移动到刚刚学到的策略上，计算机被迫持续优化其方法。论文从数学上证明，只要持续这样做，你就将严格地越来越接近完美的纳什均衡，而不会停留在某个“足够好”的位置上。

实用工具：NASHPG

虽然“可移动锚点”的构想数学上非常优美，但对于像德州扑克这样的现实游戏来说过于沉重，因为它需要检查每一个可能的动作。

因此，作者构建了一个实用版本，称为NASHPG。

隐喻：想象一位徒步者在雾中试图寻找山峰的顶峰。
- 正则化是一阵轻柔的风，将徒步者推向特定路径，防止他们偏离悬崖。
- NASHPG则是徒步者使用标准、可靠的指南针（如 PPO 等标准“策略梯度”方法）向山顶进发。
- 每走几步，徒步者就会停下，观察当前位置，并更新风的方向，以便从这个新位置继续推动他们。

这使得计算机能够利用标准、快速且经过验证的工具（即“指南针”），同时仍能受益于“移动锚点”的技巧，从而最终找到完美策略。

他们的发现

作者在多种游戏中测试了该方法，从简单的纸牌游戏（Kuhn 扑克）到像战舰和无限注德州扑克这样庞大而复杂的游戏。

行之有效：NASHPG 找到的策略与以往方法一样好，甚至更好。要“利用”（欺骗）NASHPG 玩家非常困难。
可扩展性：与在大型游戏中失效的旧方法不同，NASHPG 有效地处理了德州扑克和战舰的巨大复杂性。
关键秘诀：论文发现，旧方法（如 R-NaD）在大型游戏中失败的原因并非“移动锚点”构想本身，而是它们用来移动的引擎。NASHPG 使用现代、稳健的引擎（PPO），这就是它能在其他方法挣扎的地方取得成功的原因。

核心结论

论文指出：“我们拥有了一种教导 AI 进行完美游戏的新方法。我们利用‘移动锚点’技术引导 AI 走向完美策略，但我们是使用标准、高效的工具来实现这一点的，因此它能够应对像扑克和战舰这样巨大而复杂的游戏。”

这是在复杂的数学理论与能够以人类自己的游戏击败人类的实用、可运行软件之间架起的一座桥梁。

以下是论文《NASHPG：一种用于寻找纳什均衡的具有迭代细化正则化的策略梯度方法》的详细技术总结。

1. 问题陈述

本文探讨了利用**多智能体强化学习（MARL）在双人零和不完美信息博弈（2p0s IIGs）中寻找纳什均衡（NE）**的挑战。

核心难点：虽然深度强化学习（DRL）在完美信息博弈中取得了成功，但 2p0s IIGs（如扑克）涉及部分可观察性和隐藏信息。
现有方法的局限性：
- 基于群体的方法（如 PSRO、NFSP）：通常需要昂贵的最佳响应计算，且仅保证收敛到平均策略，而非最后一次迭代的策略。在 DRL 设置中提取最终策略并非易事。
- 反事实遗憾最小化（CFR）：需要完整的博弈树枚举（基于模型），使其在大规模领域中不可行。
- 基于正则化的方法（如 R-NaD）：近期方法利用正则化确保最后一次迭代收敛到正则化均衡。然而，这些并不一定是真正的纳什均衡（它们仍可被利用）。此外，现有的实际实现（如 R-NaD）依赖于神经复制动力学（NeuRD），其在基准测试中表现不如标准策略梯度方法。
差距：目前缺乏一种可扩展、无模型、基于策略梯度的算法，能够在大规模不完美信息博弈中证明收敛到精确的纳什均衡。

2. 方法论

作者提出了一种两阶段方法：理论框架（IMMD）和实际算法（NASHPG）。

A. 理论框架：迭代 MMD（IMMD）

作者扩展了磁性镜像下降（MMD），这是一种求解正则化变分不等式（VI）的方法。

正则化 VI：纳什均衡的标准 VI 问题是单调的，但不是强单调的，这使得直接求解变得困难。MMD 添加了一个基于 Bregman 散度的强凸正则化项，以创建一个强单调算子，从而确保解的唯一性。
迭代细化：IMMD 不是求解一个正则化问题，而是求解一系列问题。
1. 从初始策略分布 $\rho$ 开始。
2. 求解正则化 VI 问题 $VI(Z, G_\rho)$ 以找到新策略 $z = M(\rho)$ 。
3. 将此新策略 $z$ 用作下一轮的参考 $\rho$ 。
理论保证：本文证明了该迭代过程会导致到任何纳什均衡的 Bregman 散度严格单调递减。因此，策略序列收敛到真正的纳什均衡。

B. 实际算法：纳什策略梯度（NASHPG）

为了使 IMMD 适用于无法进行完整枚举的大规模博弈，作者推导出了NASHPG：

从混合策略到行为策略：他们用行为策略（RL 中的随机策略）之间的Kullback-Leibler（KL）散度来近似 IMMD 中使用的混合策略 Bregman 散度。
目标函数：该算法优化一个正则化策略目标：
$\text{目标} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$
其中 $\pi$ 是当前策略， $\rho$ 是参考策略（来自上一个外层循环）， $\alpha$ 是正则化强度。
算法结构：
1. 内层循环：执行 $K$ 步标准策略梯度更新（例如使用 PPO），以针对当前参考 $\rho$ 优化正则化目标。
2. 外层循环：在 $K$ 步之后，将参考策略 $\rho$ 更新为当前策略 $\pi$ ，并重复此过程。
模块化：NASHPG 与特定的策略梯度估计器无关。它可以无缝集成到先进的单智能体 RL 算法中，如PPO（近端策略优化）。

3. 主要贡献

理论收敛性：引入了IMMD，这是一个多轮正则化框架，保证在 2p0s 扩展式博弈中 Bregman 散度严格单调递减并收敛到精确的纳什均衡。
实际算法（NASHPG）：开发了一种可扩展的无模型算法，使用标准策略梯度方法（如 PPO）和 KL 正则化来实现 IMMD 框架。
假设验证：提供了实证证据，表明先前正则化方法（如 R-NaD）表现不佳是由于使用了NeuRD作为内部求解器，而非正则化框架本身。在类似框架中用 PPO 替换 NeuRD 显著提高了性能。
可扩展性：展示了求解大规模领域（如战舰、单挑无限注德州扑克）的能力，在这些领域中精确枚举是不可能的。

4. 实验结果

作者在七个游戏中评估了 NASHPG，范围从小型（Kuhn 扑克）到巨型（单挑无限注德州扑克）。

收敛性与稳定性：与某些基线方法不同，NASHPG 表现出稳定的收敛性，即使在较高的正则化强度下也不会发散。
与基线的性能对比：
- 小型游戏：在 Kuhn 扑克、Leduc 扑克、Dark Hex 和 Phantom 井字棋中，NASHPG 实现了与 NFSP、PSRO、MMD 和 R-NaD 相当或更低的可被利用性。
- 大型游戏：在战舰和单挑无限注德州扑克中（精确可被利用性不可行），NASHPG 在与所有基线（NFSP、PSRO、R-NaD、MMD）的一对一比赛中实现了更高的平均收益。
消融研究（R-NaD 与 PPO）：一项受控实验在 R-NaD 框架中用 PPO 替换了 NeuRD（创建了RNaD-PPO）。
- 在小型游戏中，更新规则的影响较小。
- 在大型游戏中，RNaD-PPO显著优于标准 R-NaD，缩小了与 NASHPG 的差距。这证实了**内部优化规则（PPO 与 NeuRD）**是基于样本的多轮正则化中的主要瓶颈。
效率：该实现仅需在标准独立 PPO 基础上进行约 20 行代码的修改，突显了其易用性。

5. 意义

** bridging 理论与实践**：本文成功弥合了理论收敛保证（通常局限于小型、可枚举博弈）与实际可扩展 MARL 算法之间的差距。
MARL 的新范式：它确立了迭代细化正则化参考结合标准策略梯度是寻找纳什均衡的优越方法，优于基于群体的方法或旧的正则化技术。
可及性：通过依赖标准 PPO 和简单的 KL 正则化，NASHPG 降低了从业者的入门门槛，使他们能够在不需要复杂自定义求解器或完整博弈树枚举的情况下应用先进的博弈论收敛保证。
最先进性能：它为不完美信息博弈中的无模型方法设立了新的基准，在小型和大型领域均优于既定基线。