🤖 AI

Regret Minimization with Adaptive Opponents in Repeated Games

本文引入了重复策略遗憾（RP-Regret），这是一种旨在处理重复博弈中自适应对手的新型博弈论度量标准，并提出了旨在最小化这一非凸遗憾度量的算法，从而实现子博弈精炼均衡和更具合作性的结果的学习。

原作者： Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

发布于 2026-06-05

📖 1 分钟阅读☕ 轻松阅读

原作者： Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, Kaiqing Zhang

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

想象一下你正在和朋友玩一场长期的国际象棋、扑克，甚至是一个简单的“剪刀石头布”。在标准的游戏中，你出一招，对方出一招，然后结算得分。但在现实世界中（以及这篇论文研究的“重复博弈”中），你的朋友不是机器人。他们是在观察你的。如果你打得激进，他们可能会变得防守；如果你表现得友好，他们可能会选择合作。他们是具有适应性的：他们会根据你的历史记录来改变策略。

问题在于，计算机科学家衡量“你玩得有多好”的标准方法（称为外部遗憾/External Regret）假设你的对手是一堵静止的墙，根本不在乎你做什么。它问的是：“如果我不管你在做什么，仅仅是针对每一轮都选择那个单一的最佳动作，我会赢更多吗？”

这篇论文认为，对于拥有聪明、具适应性对手的游戏来说，这种标准的衡量方式是失效的。它往往会迫使玩家玩得非常糟糕（比如在“囚徒困境”中总是选择“背叛”），因为它未能考虑到你的行为会改变对手未来的行为。

以下是该论文解决方案的拆解，使用了简单的类比。

1. 新的指标：“重复策略遗憾”（RP-Regret）

作者引入了一种衡量成功的新方法，称为 RP-Regret。

旧方法（外部遗憾）： 想象你在开车。旧的指标问：“如果你每天都开完全相同的路线，完全忽略交通灯和其他车辆，你会节省多少时间？”如果交通灯会根据你的驾驶行为而变化，那么这个问题是毫无意义的。
新方法（RP-Regert）： 这个指标问：“如果你为整个行程选择了一个不同的整体计划（策略），并且预先知道交通灯和其他司机也会针对这个特定的计划做出反应，你会过得更好多少？”

核心区别在于： 在新的指标中，你不仅仅是将当前的动作与单一的“最佳动作”进行比较。你是在将你的整个策略，与一个假设的“更好的策略”进行比较——而在这个假设中，你的对手也会随着那个更好的策略而做出调整。

2. “记忆”问题

论文发现了一个重大障碍：如果玩家拥有完美的、无限的记忆，并且能够对过去的每一个微小细节做出反应，那么在数学上实现这种新遗憾最小化将变得不可能。这就像是在试图解一个谜题，而你移动的每一个碎片都会瞬间改变其他所有碎片的形状。

为了解决这个问题，作者提出了两条“交通规则”（条件），使问题变得可解：

缓慢变化： 你的对手（以及你自己的“假设中”的策略）不应该在一秒钟内发生过于剧烈的变化。
遗忘： 玩家不应该完美地记住一切。他们应该拥有“褪色的记忆”。如果某件事发生在 100 轮之前，现在它几乎就不再重要了。论文称之为指数衰减记忆（Exponential Decay Memory）。这就像你对最近发生的对话记得很清楚，但一年前谈话的细节就会逐渐模糊。

3. 三种变强的途径（算法）

由于计算完美的“RP-Regret”策略非常困难（就像在试图解一个不断变形的迷宫），作者提出了三种工具来接近最佳结果：

工具 1：神奇的预言机（Magic Oracle）。 想象你拥有一个超级计算机，可以瞬间解决任何复杂的非线性谜题。如果你拥有这个“预言机”，你就能找到完美的策略。论文证明了这是可行的，但也承认在现实生活中我们并没有这样的神奇计算机。
工具 2：“局部”捷径。 与其试图改变你整个游戏的完整计划，不如问：“如果我现在只改变一个动作，并保持其他一切不变，会怎样？”它通过观察微小的、局部的变化来简化问题。这让数学计算变得容易得多（将一个崎岖不平的山丘变成一个平滑的斜坡），并允许开发出快速且实用的算法。
工具 3：慢动作游戏。 如果你的对手改变策略的速度非常缓慢，作者展示了你可以将游戏视为一种“马尔可夫博弈”（Markov Game，即未来的状态仅取决于当前状态，而不取决于整个历史）。他们将游戏转化为一种格式，使得标准的优化工具可以很好地运作，实际上是将问题“提升”到了更高的维度，使其变得可解。

4. 结果：合作获胜

这篇论文最令人兴奋的部分是当每个人都使用这些新工具时会发生什么。

在著名的囚徒困境（一个由于人们担心被背叛而往往导致双方互相背叛的游戏）中，旧的方法通常会导致“背叛-背叛”的结果，即双方都遭受损失。然而，论文表明，如果玩家最小化 RP-Regret，他们会自然而然地学会合作。

类比： 想象两个邻居。如果他们只看今天的互动，他们可能会互相偷窃对方的邮件。但如果他们意识到：“如果我今天偷窃，我的邻居明天也会偷窃，那样我们都会损失惨重，”他们就会学会友好相处。新的指标捕捉到了这种长期思考。
实验： 作者在名为**猎鹿博弈（Stag-Hunt）**的游戏上进行了测试（在这种游戏中，你可以独自猎取一只兔子获得小奖赏，或者一起猎取一只鹿获得大奖赏）。当玩家使用新的“局部 RP-Regret”算法时，他们成功地学会了合作并共同猎鹿，获得了比以前高得多的分数。

总结

这篇论文在说：“不要再用对待机器人的方式来衡量玩家。要开始用对待聪明、会做出反应的人类的方式来衡量他们。”通过引入一种考虑了适应性和记忆限制的新指标，并提供计算该指标的算法，作者展示了玩家可以在重复博弈中学习合作，并取得比以往更好的结果。

技术摘要：重复博弈中具有自适应对手的遗憾最小化

问题陈述

本文研究了在重复博弈中进行遗憾最小化（Regret Minimization）的挑战，其中对手是自适应的（adaptive），即他们可以根据博弈的历史记录来调整自身的策略。作者认为，在线学习中的标准指标——外部遗憾（External Regret）在这一设定下是不充分的。外部遗憾假设损失序列仅是时间的函数，这在隐含意义上将对手视为非自适应的。然而，在博弈论设定中，对手对玩家行动的反应会改变未来的损失。因此，在重复博弈中最小化外部遗憾往往会导致次优均衡（例如，迭代囚徒困境中的“背叛-背叛”结果），并且无法捕捉有效的合作策略（如“以牙还牙”），尽管后者可能在外部遗憾上表现为线性遗憾，但能获得更高的效用。

现有的替代方案，如策略遗憾（Policy Regret，考虑了损失函数的记忆性）或响应遗憾（Response Regret，考虑了依赖历史的混合策略），面临着显著的局限性。策略遗憾通常依赖于严格的 $m$ 阶有界记忆假设，而这在重复博弈中并不成立，因为早期的偏差会对长期产生影响。响应遗憾虽然在理论上是完备的，但需要指数级规模的策略空间，导致计算上难以实现。

方法论

1. 重复策略遗憾 (RP-Regret)

作者引入了重复策略遗憾 (RP-Regret)，这是一种针对重复博弈设计的原生性能指标。

定义： RP-Regret 衡量的是实现的累积效用与在假设所有玩家（包括对手）都对博弈历史做出自适应反应的情况下，事后最优的累积效用之间的差异。
核心区别： 与外部遗憾不同，在时间步 $t$ 进行的对比较策略（comparator strategy）的偏差，不仅会影响 $t$ 时刻的损失，还会影响后续所有的损失，因为自适应对手会根据新的历史记录改变其策略。
必要条件： 本文建立了一个结论：如果不施加特定约束，实现亚线性 RP-Regret 是不可能的。文中确定了两个必要条件：
1. 亚线性变化 (Sublinear Variation)： 比较策略随时间的变化不能过于剧烈。
2. 不完美记忆 (Imperfect Recall)： 玩家（及比较策略）不能拥有对整个历史的完美记忆。具体而言，本文提出了指数衰减记忆 (Exponential Decay Memory, EDM)，即过去的历史对当前策略的影响随时间呈指数级衰减。这防止了通过行动进行“状态传递”，并确保有效记忆长度随精度要求仅呈对数增长。

2. 最小化算法

由于目标函数由于随时间变化的策略乘积而呈现非凸性，本文提出了三种方法来最小化该函数：

基于 Oracle 的方法： 在假设可以访问非凸优化 Oracle（如之前的在线非凸学习工作所示）的前提下，作者证明了在满足必要条件（亚线性变化和 EDM）的情况下，可以实现亚线性 RP-Regert。这作为理论基准。
局部重复策略遗憾 (LRP-Regret)： 为了确保计算的可行性，作者提出了一个代理指标——LRP-Regret。该指标将偏差限制在单个时间步内（局部偏差），而非全局策略变更。
- 凸化 (Convexification)： 当将特定时间步的期望损失视为关于该步策略的函数时，它对于该步策略是线性的（从而也是凸的）。
- 算法： 作者提出了投影梯度下降 (PGD) 算法来最小化 LRP-Regret。理论保证显示，如果对手满足 EDM 条件，该算法可以实现亚线性 LRP-Regret。
马尔可夫博弈重构： 对于对手策略变化也较慢（满足亚线性变化）的情况，作者将具有有界记忆的重复博弈重构为无限时界马尔可夫博弈 (Markov Game)。
- 占用度量 (Occupancy Measures)： 算法不再直接优化策略，而是优化占用度量（即状态-动作访问频率）。这通过将非凸问题转化为占用度量空间中的凸问题。
- 约束： 算法处理随时间变化的约束，以确保占用度量对应于针对自适应对手的有效乘积策略剖面。
- 结果： 这种方法直接最小化原始的 RP-Regret（而非仅仅是代理指标），并实现了亚线性遗憾。

关键结果

硬度结果 (Hardness Results)： 本文证明，如果没有亚线性变化和不完美记忆（特别是 EDM）这两个条件，最小化 RP-Regret 是不可能实现的（会导致线性遗憾）。
算法保证：
- LRP-Regret 最小化算法实现的遗憾界限为 $\tilde{O}(|A|^{m+1}\sqrt{P_T/T})$ ，其中 $P_T$ 是比较策略的变化量， $m$ 是记忆长度。
- 基于马尔可夫博弈的算法在对手变化缓慢时，能够实现亚线性 RP-Regret。
均衡计算： 作者建立了最小化这些遗憾概念与计算均衡之间的理论联系。
- 如果所有玩家都最小化 RP-Regret（或 LRP-Regret），则其时间平均策略将收敛至近似子博弈完美纳什均衡 (SPNE) 或子博弈完美粗略相关均衡 (SPCCE)，且具有受限的偏差。
- 具体而言，对于无限重复博弈，轨迹将收敛至一个对一定变化预算内的偏差具有鲁棒性的均衡。
实验验证： 在猎鹿博弈 (Stag-Hunt) 上的实验表明，相比于最小化外部遗憾的方法（后者往往陷入风险占优但效用较低的“猎兔-猎兔”均衡），最小化 LRP-Regret 的玩家能更频繁地收敛到合作均衡（“鹿-鹿”）并获得更高的效用。

意义与主张

本文声称提供了一种原生且自然的重复博弈遗憾指标，该指标在考虑对手自适应性的同时，没有像之前的策略遗憾工作那样施加严格的有界记忆假设，也没有像响应遗憾那样面临计算上的不可行性。

理论贡献： 它确定了自适应环境学习的基本极限（必要条件），并提供了第一个能够允许动态比较者和自适应对手的、用于最小化博弈论遗憾指标的可证明算法。
实际意义： 通过最小化 RP-Regret（或其凸代理指标 LRP-Regret），玩家可以在诸如迭代囚徒困境和猎鹿博弈等游戏中学会合作，从而获得比单次博弈中纳什均衡所规定的更高的效用。
均衡选择： 这项工作表明，重复博弈中的遗憾最小化可以作为一种机制，用于选择那些并非底层单次博弈唯一纳什均衡的更好均衡。

作者对计算复杂度保持了谦逊的态度，承认由于问题的非凸性质，通常需要 Oracle 或特定的结构性假设（如缓慢变化的对手）才能实现计算可行。他们将这项工作定位为为研究更弱的均衡概念以及通过遗憾最小化进行均衡选择开辟了新的方向。