💻 computer science

GARIP: A Running-Average Moving Reference for Last-Iterate Self-Play in Two-Player Zero-Sum Games

本文介绍了 GARIP，这是一种通过将策略更新锚定到运行平均参考值来独特地最小化参考滞后并确保局部最后迭代收敛的自博弈方法，证明了在各种双人零和博弈中相比于固定或基于快照的基准具有更优越的鲁棒性和稳定性。

原作者： Can Savcı

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Can Savcı

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

想象两个人正在进行一场高风险的剪刀石头布比赛，但他们试图通过不断地自我对弈来学习完美的策略。

在旧的方法中（被称为“幼稚自我博弈”/naive self-play），玩家会陷入一个循环。他们不断地在完美答案周围打转，却始终无法真正抵达，就像一辆在环岛上绕圈行驶的汽车，却始终无法驶离出口。

这篇论文介绍了一种名为 GARIP 的新方法，旨在帮助这些玩家停止绕圈，并真正抵达完美策略。以下是它的工作原理，使用简单的类比来解释。

问题所在：“陈旧”的参考点

为了停止绕圈，现代方法会告诉玩家：“不要只看你的上一步动作；要看过去的一个‘参考’动作，并尝试与它保持接近。” 这个参考点就像一块磁铁，将玩家拉向一个稳定的位置。

然而，这里有一个陷阱：那个参考点有多旧了？

如果参考点太旧（陈旧），玩家会被拖回到很久以前已经放弃的糟糕策略中。
如果参考点太新，它就无法起到阻止绕圈的作用。

两个竞争者：快照 vs. 移动平均

论文对比了两种选择这种“参考点”的方式：

快照法 (R-NaD)： 想象一位教练，他为玩家的策略拍了一张照片，把它装进相框，然后说：“在接下来的 200 步内，请紧跟这张照片。”
- 缺陷： 在前 199 步中，玩家遵循的是一张越来越陈旧的照片。到了第 200 步，照片变得非常“陈旧”。然后，教练再拍一张新照片，循环往复。这产生了一种“锯齿状”模式：参考点很新鲜，然后变得非常陈旧，接着又被重置。论文证明了这种“峰值陈旧度”（即照片变得最旧的时刻）是平均年龄的两倍之恶。
移动平均法 (GARIP)： 想象一位教练，他不断更新一个“心理平均值”，涵盖玩家所做的一切。他不再使用单一的照片，而是说：“请与你至今为止的整个历史平均水平保持接近。”
- 优势： 这个平均值在某种意义上始终是“新鲜”的。它不会出现那种参考点变得极其陈旧的剧烈波动。它具有“平滑”的特性。论文从数学上证明了，在所有观察过去的方式中，这种“平滑”的平均法是防止参考点变得过于陈旧的最有效方式。

重大发现：为什么 GARIP 是更好的默认选择

论文声称，如果调优得当，两种方法都能达到完美策略。然而，GARIP 的容错性更高。

陷阱： 使用“快照”方法时，如果你不小心选择了一个稍微长了一点的重置时间（例如 200 步而不是 100 步），“陈旧”的参考点会变得如此之旧，以至于玩家会崩塌进入一个糟糕的策略。
安全网： 使用 GARIP 时，由于参考点是一个平滑的平均值，它不会产生那些危险的“陈旧峰值”。即使你选择了标准设置，它也能保持安全。

类比：
把“快照”法想象成一个人用绳子拽着一个重物。如果他在把绳子拉回来之前让它放得太长，重物就会剧烈摆动并撞到他。
把 GARIP 想象成一个人用弹簧拽着一个重物。弹簧能平滑地吸收运动。即使他没有拉得完美，弹簧也会防止重物失控摆动。

实验展示了什么

研究人员在以下领域测试了该方法：

简单的数学游戏（矩阵博弈）。
卡牌游戏（扑克）。
棋类游戏（四子棋、奥赛罗/黑白棋）。

结果显示：

巅峰性能： 如果你对两种方法都进行了完美调优，它们的表现几乎一样。
鲁棒性（真正的赢家）： 在现实世界中，你没有时间去完美调优每一个设置，GARIP 胜出了。它失败的次数少得多。
- 在像四子棋这样的棋类游戏中，使用标准设置时，“快照”法有 25% 的失败率，而 GARIP 的失败率为 0%。
- 只有当你把“平均值”更新得极其缓慢时（比如查看 1,000 步之前的历史），GARIP 才会失败，而这并不是一个正常人会选择的设置。

局限性

论文诚实地说明了 GARIP 不起作用 的地方：

并非魔法： 如果游戏过于复杂，导致计算机无法学习（例如在大棋盘上的 Hex 游戏），它并不能让玩家变得无敌。
不需要循环： 如果一个游戏本身就能自然收敛（如一个小型的 Animal Shogi 游戏），添加这种“磁铁”不仅没有帮助，反而可能减慢玩家的速度。
局部成功： 数学证明了它在局部（接近解附近）运行良好，但论文承认，它是否能从任何起点开始都有效仍是一个猜想，尽管实验表明确实如此。

总结

GARIP 是一种 AI 通过不断平均自身过去动作来学习游戏的新方法。从数学上证明，它是最稳定的方法，因为它避免了困扰其他方法的“陈旧峰值”。它是“安全的默认”选择：当调优完美时，它的表现与现有的最佳方法不相上下，但它更不容易出错。

技术摘要：GARIP —— 基于运行平均值的最后迭代自博弈移动参考法

1. 问题陈述

在双人零和博弈中，使用朴素梯度上升（SGA）的标准自博弈（Self-play）无法在最后迭代（Last-iterate）中收敛；相反，其轨迹会在闭合保守场中围绕纳什均衡轨道运动。虽然时间平均策略可以收敛，但现代深度多智能体强化学习（RL）依赖于最终的网络参数，这使得最后迭代的行为变得至关重要。

现有方法试图通过将策略向参考点（“磁铁”）正则化来打破保守旋转，从而恢复最后迭代收敛性：

MMD： 使用固定参考（例如均匀分布）。它收敛到正则化均衡（量化响应均衡），需要对正则化进行退火处理才能达到真实的纳什均衡。
R-NaD： 使用当前策略的周期性快照（每 $K$ 步重置一次）。它无需退火即可达到纳什均衡，并为 DeepNash 等系统提供动力。
虚构博弈（Fictitious Play）： 对平均对手做出最优响应，但缺乏自我锚定。

本文识别了设计空间中的一个空白：一种锚定于策略自身运行平均值（连续更新）而非固定点或离散快照的方法，旨在实现无需退火的最后迭代收敛，同时提高超参数的鲁棒性。

2. 方法论：GARIP

GARIP（生成对抗互惠迭代博弈）是一种结合了乐观梯度步与指向策略运行平均值的 Halpern 锚定的更新规则。

更新机制

对于具有收益矩阵 $A$ 的博弈，设行玩家策略为 $x$ ，对手策略为 $y$ ：

乐观步： 策略执行一个乐观熵上升步（类似于乐观镜像上升），利用当前梯度和前一梯度来预判对手的移动。
Halpern 锚定： 更新后的策略是乐观步与运行平均值 $\bar{x}$ 的凸组合：
$x_{t+1} = (1 - \beta) x_{t+1/2} + \beta \bar{x}_t$
其中 $\beta \in (0, 1)$ 是常数锚定强度（无需退火）。
运行平均值更新： $\bar{x}$ 被连续更新（在矩阵博弈中为累积均值，或在深度强化学习中使用 Polyak 指数移动平均）。

理论动机

该方法受到将零和博弈视为 CycleGAN 的“循环一致性”视角的启发，其中均衡是往返映射 $F \circ G$ 的不动点。锚定到运行平均值强制执行了与这种自我指涉不动点的一致性。从机械层面看，GARIP 是一个由移动 Halpern 锚定的乐观镜像上升，它并不优化循环一致性损失。

3. 核心贡献与理论结果

A. 崩溃的“峰值滞后”机制

论文指出，移动参考方法的失效模式（崩溃）是由参考值相对于当前策略的**峰值滞后（Peak Lag）**驱动的。

陈旧性（Staleness）： 参考值相对于当前策略滞后 $\ell$ 步。在正则化权重 $\lambda$ 下，这会产生一个正比于 $\lambda \cdot \ell$ 的恢复力。如果该力超过了游戏梯度，策略就会崩溃到一个可被利用的、陈旧的状态。
锯齿型 vs 平坦型：
- R-NaD (快照)： 在 $K$ 步内保持参考值固定，产生锯齿状滞后剖面。其峰值滞后为 $K$ ，而平均滞后为 $K/2$ 。因此，峰值 = 2 × 平均值。
- GARIP (运行平均值)： 滞后剖面是平坦的（平稳的）。峰值滞后等于平均滞后。
命题 1： 在所有具有固定平均滞后的因果凸平均值中，运行平均值能唯一地最小化峰值滞后。快照的峰值严格被前者削减了一个因子 2。

B. 收敛性质

局部最后迭代收敛（命题 3）： 论文证明，对于较小的锚定强度 $\beta$ ，锚定会将基础映射的旋转特征值缩放为 $(1-\beta)$ 。这跨越了稳定性边界，将一个循环（轨道运动）的基础映射转变为收缩映射，从而确保在无需退火的情况下在纳什均衡处实现局部渐近稳定性。
无偏不动点（命题 2）： 与收敛到磁铁正则化均衡的 MMD 不同，GARIP 的自我指涉锚定在任何不动点处都会消失。因此，每个内部不动点都是真实的纳什均衡。
全局收敛： 对于较小的 $\beta$ ，论文推测存在全局收敛。文中提到在较大的 $\beta$ 下存在“过早共识（premature consensus）”失效模式，即锚定迫使策略与平均值过快地在次优点上达成一致，从而阻碍了进展。

C. 鲁棒性主张

GARIP 的主要优势在于超参数鲁棒性，而非峰值性能。

由于 R-NaD 的峰值滞后是其平均滞后的两倍，基于平均滞后直觉选择的常规重置周期 $K$ ，会无意中将峰值滞后设定为一个危险的水平。
GARIP 的平坦剖面确保了在常规参数化下，峰值滞后保持在较低水平。
论文声称，当两者都调优至最佳时，GARIP 的峰值性能可以媲美 R-NaD，但作为默认设置，GARIP 更具优越性，因为其“安全盆地”更宽。

4. 实验结果

矩阵博弈与扑克

矩阵博弈： 在默认设置下，GARIP 在随机 $10\times10$ 和 $12\times6$ 游戏中实现了接近纳什的利用率，而 R-NaD 的默认设置表现显著落后（需要调优才能匹配）。MMD 则停滞在正则化均衡处。
扑克 (Kuhn/Leduc)： GARIP 在默认调优下优于 R-NaD 和 MMD，达到了接近精确最佳响应虚构博弈的利用率。

深度强化学习 (Coin Game & Board Games)

Coin Game： GARIP 与 R-NaD 在峰值性能上持平（两者都远优于固定磁铁和无磁铁基准线）。
棋类游戏 (Connect Four, Othello, Animal Shogi, Hex)：
- 循环类游戏 (Connect Four, Othello)： 移动参考（GARIP/R-NaD）明显比基准线更鲁棒。GARIP 在 Othello 上略微领先于 R-NaD。
- 非循环类游戏 (Animal Shogi)： 朴素自博弈自然收敛。在此情况下，正则化是不必要的且略微阻碍性能，尽管 GARIP 仍是测试方法中表现最好的正则化器。
- 不可学习游戏 (Hex)： 由于 $11\times11$ 棋盘的复杂性，所有方法都无法学习到鲁棒策略，这证实了无搜索学习器的极限。

超参数鲁棒性 (核心发现)

论文进行了超参数扫描，以测量“崩溃率”（无法收敛到鲁棒策略的失败情况）。

全网格测试： 在整个参数空间内，GARIP 和 R-_NaD 的聚合崩溃率统计上没有显著差异（约 25% 对 32%）。如果被推向极端的陈旧性，两者都会失效。
常规参数化： 关键区别在于崩溃边界相对于标准使用的位置。
- GARIP： 仅在非常慢的平均速率（ $\rho \le 0.005$ ）下发生崩溃。在标准的 $\rho = 0.01$ 时，崩溃率为 0/40 个种子。
- R-NaD： 在标准重置周期下发生崩溃。在 $K=200$ 时，崩溃率为 10/40 个种子。
结论： R-NaD 的常规 $K$ 低估了其峰值滞后一个因子 2，使其处于危险区域。GARIP 提供了一个“默认安全”的参数化方案。

5. 意义与主张

论文将 GARIP 定位为非退火自博弈中一种结构上更优的默认方法，而非一种追求更高峰值性能的方法。

结构优势： 运行平均值是最小化因果平均值中峰值滞后的最优参考形状。这使得它在面对困扰快照方法的“陈旧性”失效模式时，天生具有更强的鲁棒性。
实际影响： 用户不需要为了避免崩溃而去专门缩短 R-NaD 的重置周期 $K$ ；GARIP 通过标准参数即可自动实现这种安全性。
局限性：
- 论文明确表示，它并不声称在经过调优的 R-NaD 之上具有更高的峰值性能。
- 全局收敛是一个推测；较大的 $\beta$ 可能会导致过早共识。
- 该方法的优势仅在发生循环行为的博弈中体现；在自然收敛的游戏中，它不提供收益且略有成本。
- 该方法并非免疫崩溃；它只是将崩溃边界移动到了较不常见的参数区间。

论文总结道，对于循环类零和博弈的深度自博弈，运行平均值是更理想的参考方式，它为快照法提供了一个“免费”的安全裕度。