🤖 machine learning

Regret, equilibrium, and learning in games: A guided tour

本文对博弈中的正则化学习策略进行了统一的综述，分析了它们在对抗性单智能体设置下的遗憾界，以及在多智能体交互中向均衡的收敛性，同时弥合了在预言机（oracle）和多臂老虎机（bandit）信息模型下动态学习过程与静态理性概念之间的鸿沟。

原作者： Panayotis Mertikopoulos

发布于 2026-08-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Panayotis Mertikopoulos

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

想象一个这样的世界：每个人都在不断尝试做出最佳选择，但没有人拥有规则手册，没有人知道别人在想什么，而且游戏的规则可能每秒钟都在变化。这就是**博弈论（game theory）的混乱游乐场——这是一个研究人类（或计算机、或动物）在成功取决于他人的行为时如何做出决策的科学分支。几十年来，科学家们一直假设，如果每个人都是完全理性的，他们最终会找到那个被称为纳什均衡（Nash equilibrium）**的完美平衡点，即没有任何人有理由改变其策略。但在现实世界中，人们并不是完美的计算器；他们是混乱的、反应性的，并且通常只是为了应付现状。因此，一个重大问题随之而来：如果我们只是让这些不完美的智能体通过试错法进行学习，他们是会偶然发现那个完美的平衡，还是会仅仅在原地打转？

这篇由 Panayiotis Mertikopoulos 撰写的论文带我们进行了一次关于这种混乱现实的导览。它探讨了博弈中的学习（learning in games），这是一个处于经济学、计算机科学和人工智能交汇点的领域。作者介绍了一类聪明的策略，称为正则化学习（regularized learning）。可以将这些策略视为一种玩家观察自己过去错误和奖励的方式，但带有一种“温柔的推动”，以防止他们过于痴迷于某一个特定的动作。这就像一个正在为考试复习的学生：他们回顾过去的旧试卷（过去），但也会强迫自己尝试一些新的练习题（探索），这样就不会陷入错误的答案中。论文提出了这样一个问题：如果每个人都使用这些聪明且略显谨慎的学习规则，他们最终会找到稳定的和平（纳什均衡），还是会在循环的混乱中原地踏步？

聪明学习者的故事

为了理解论文的历程，我们首先要认识我们的主角：学习者（The Learner）。想象你正在玩一款电子游戏，对手是一个你看不到的神秘对手。你不知道游戏的规则，也不知道你的对手是想击败你，还是只是在胡闹。每一回合，你选择一个动作，获得一个分数，然后必须决定下一步该做什么。

在过去，科学家认为最好的玩法是虚构学习（Fictitious Play）。这就像一个学生查看了他们参加过的每一场测试，然后说：“好吧，我在周二拿了 A，那么以后我永远只做周二做的事情。”论文表明，这有点过于僵化了。如果游戏发生哪怕一点点变化，这种“模仿者”策略可能会陷入循环，在两个糟糕的选择之间来回跳跃，永远无法意识到有更好的选择。这就像一只狗在追逐自己的尾巴；它在移动，但并没有取得任何进展。

论文提出了一种更好的方法：跟随正则化领导者（Follow-the-Regularized-Leader, FTLR）。与其只是盲目地模仿过去，这种方法增加了一个“正则化项”。可以将它想象成一个安全垫或好奇心过滤器。它在说：“嘿，你上次做的那个动作很好，但也许不要把整个生命都押在上面。让我们保留一点其他选择的可能性，以防万一。”这防止了学习者过快地变得过于自信并陷入次优的循环。

学习的两个世界

论文将故事分成了两个不同的世界，以观察这种新方法的效果如何。

世界 1：单人玩家（强盗/Bandit）
首先，作者观察了一个面对不可预测环境（例如一个随机改变赔率规则的拉霸机）的单个玩家。在这里，目标是最小化悔恨值（Regregret）。悔恨值是你实际获得的分数与如果你预知了未来并始终选择完美动作所能获得的分数之间的差值。
论文证明，通过使用这种“安全垫”方法，玩家的悔恨值增长得非常缓慢。虽然它不是零，但相对于总游玩时间来说非常小，以至于从长远来看，玩家的表现几乎与那位从一开始就知道一切的完美天才一样好。这就像是在说：“尽管我不知道未来，但我聪明且谨慎的策略防止了我犯下巨大的错误。”

世界 2：群体游戏（混沌）
随后，论文将所有人投入到一个房间里。现在，环境不再是随机的，而是由同样试图学习和改进的其他玩家所塑造的。这就是多智能体设置（multi-agent setting）。
在这里，论文提出了那个大问题：如果每个人都使用这些聪明且谨慎的学习规则，他们最终会冷静下来并达到纳什均衡吗？纳什均衡是一种状态，即每个人都对自己的选择感到满意，没有人想要切换，因为切换只会让自己变得更糟。

答案是一个迷人的“是，但是……”以及“视情况而定”。

好消息： 在玩家直接竞争的游戏中（例如一方赢一方输的零和博弈），论文表明，如果你随着时间的推移对他们的动作取平均值，他们确实会收敛到纳什均衡。这就像一场混乱的舞蹈，当你放慢速度并观察平均步幅时，会展现出完美的节奏。
与“福尔克定理（Folk Theorem）”的联系： 论文将这种学习过程与进化生物学中一个著名的概念——“福尔克定理”联系起来。在自然界中，如果一个物种找到了生存的稳定方式，它就会坚持下去。论文显示，在这些游戏中，如果玩家的学习过程稳定在某个特定点，那么该点必然是一个纳什均衡。此外，如果一个点是“严格”均衡（意味着它是唯一的最佳选择），玩家几乎肯定会找到它并停留在那里，就像一个球滚入深碗底部一样。
代价： 论文也警告说，这并不发生在每一个游戏中。在一些复杂的场景中，玩家可能永远无法稳定下来，或者他们可能会停在一个“糟糕”的均衡上，即每个人都陷入了次优的循环。论文明确排除了学习总是能在所有可能的游戏中导致完美结果的观点。

“黑盒”的魔力

论文最酷的部分之一是它如何处理信息。在现实世界中，你很少知道一切。你可能只知道自己的得分，而不知道对手做了什么，也不知道其他选项是什么。
论文使用了一个巧妙的技巧，称为黑盒模型（Black-Box Model）。想象你是一名试图猜测天气的侦探。你没有卫星；你只有一个温度计。你必须建立一个“黑盒”模型，根据这一个数字来推测完整的气象图景。
论文表明，即使在这种有限的信息（称为强盗反馈/bandit feedback）下，正则化学习方法仍然有效。这就像侦探利用有限的线索最终推断出风暴即将到来，即使他手头没有卫星。论文证明，即使玩家只能看到自己的奖励并必须猜测其余部分，这种“安全垫”策略仍能帮助他们避免灾难并趋向稳定。

结论

那么，最终的启示是什么？论文并未声称已经解决了宇宙中的每一个游戏。它并没有说学习算法总会让世界变成乌托邦。相反，它提供了一张理解学习如何运作的统一地图。

它告诉我们：

悔恨值是一个好的指南针： 如果你能学会最小化悔恨（避免重大错误），你就走在了正确的轨道上。
谨慎是关键： 加入一点“正则化”（保持选择开放）可以防止系统陷入循环。
稳定性是可能的： 在许多重要的游戏类型中，如果每个人都使用这些聪明的学习规则，他们最终会找到一个无人想改变的稳定平衡。

这篇论文是对这样一种理念的赞美：你不需要成为一个完美的天才才能玩好一场游戏。你只需要一个能够从过去学习、对未来保持好奇、并知道何时保持谨慎的策略。它将博弈论的混乱之舞转变为一个关于不完美的智能体如何通过聪明的学习，一步步走向完美平衡的故事。

技术摘要：博弈中的遗憾、均衡与学习：引导之旅

1. 问题陈述与背景

本文探讨了非合作博弈论中“仿佛”理性（"as-if" rationality）这一基本问题：在重复交互且无需完全了解博弈规则或结构的条件下，自私且近视的智能体是否最终会表现得“仿佛”是理性的？具体而言，学习过程是否会导致纳什均衡（NE）的产生？

作者指出，标准的理性假设（完美知识、具备计算均衡的能力）在现代应用（如机器学习和数据科学）中很少得到满足。此外，寻找纳什均衡的计算复杂度是 PPAD 完全的，且 Hart & Mas-Colell 已证明，不存在能在所有博弈中都收敛至纳什均衡的解耦动力学过程。因此，研究重点从均衡的存在性转向刻画特定学习策略的长期行为。

本文区分了两种设定：

单智能体（单边/开环）： 学习者面对一个任意的、非平稳的且可能具有对抗性的环境（对抗性多臂土匪问题）。目标是最小化遗憾（实际收益与事后最佳固定动作之间的差异）。
多智能体（博弈论/闭环）： 多个玩家进行交互，彼此塑造对方的环境。目标是确定诱导的博弈序列是否收敛于纳什均衡，或表现出其他稳定性属性。

2. 方法论：正则化学习

本文提出了一个名为**正则化学习（Regularized Learning）**的统一框架，该框架推广了多种现有算法（例如：虚构学习 Fictitious Play、跟随领导者 Follow-the-Leader、指数权重 Exponential Weights、EXP3、Tsallis-INF）。

核心模板

学习过程被建模为每个玩家 $i$ 在时间 $t$ 的两阶段更新：

得分聚合： 玩家根据观察到的反馈（收益）更新聚合得分向量 $y_{i,t}$ 。
$y_{i, t+1} = y_{i, t} + \gamma_t \hat{v}_{i, t}$
这里 $\hat{v}_{i, t}$ 是混合收益向量 $v_i(x_t)$ 的“黑盒模型”（代理模型），根据反馈类型的不同，它可能包含噪声或偏差。 $\gamma_t$ 是步长。
策略选择： 玩家通过正则化选择映射 $Q_i$ 将得分映射为混合策略 $x_{i, t}$ ：
$x_{i, t+1} = Q_i(y_{i, t+1}) = \arg\max_{x \in X_i} \{ \langle y_{i, t+1}, x \rangle - h_i(x) \}$
其中 $h_i$ 是严格凸的正则化项（例如，指数权重使用负熵，懒惰投影 Lazy Projections 使用二次项）。

反馈模型

该框架通过黑盒模型 $\hat{v}_t = v(x_t) + Z_t$ 容纳了各种信息结构，其中 $Z_t$ 代表误差：

预言机（全信息）： 玩家观察到完整的收益向量（或其无偏估计）。
土匪（基于收益）： 玩家仅观察到其选择动作的实现收益。为了构建向量估计，本文利用了重要性加权估计器（IWE），通常结合显式探索（将策略与均匀分布混合）来控制方差。

3. 核心贡献与结果

A. 单智能体遗憾界限

在对抗性多臂土匪设定下，本文推导了正则化学习（FTRL）的遗憾界限。

机制： 正则化防止了未正则化的跟随领导者（FTL）所表现出的“乒乓效应”，后者在对抗性序列中会遭受线性遗憾。
结果： 对于 $K$ -强凸正则化项和有界收益，期望遗憾被界定为：
$E[\text{Reg}(T)] \leq \frac{H}{\eta} + \frac{\eta M^2 T}{2K}$
通过优化学习率 $\eta$ ，可以获得 $O(\sqrt{T})$ 的遗憾界限。
特定算法：
- 二次正则化项： 在 $L_\infty$ 设定下产生 $O(\sqrt{AT})$ 遗憾。
- 指数权重（熵正则化项）： 产生 $O(\sqrt{T \log A})$ 遗憾，其相对于动作数量 $A$ 是对数级的。
- 土匪设定（EXP3 & Tsallis-INF）： 使用 IWE 结合显式探索，本文推导出的界限显示，相比于全信息，土匪反馈会带来惩罚（通过简单分析通常为 $O(T^{2/3})$ ，通过更紧密的分析对于 Tsallis-INF 则为 $O(\sqrt{T})$ ）。

B. 零和博弈中的多智能体收敛性

对于两人零和博弈，本文确立了博弈的**遍历平均值（ergodic average）**向纳什均衡集的收敛性。

结果： 在适当的步长和探索计划下，期望间隙函数（衡量与纳什均衡距离的函数）以 $\tilde{O}(T^{-1/2})$ （针对预言机方法）和 $\tilde{O}(T^{-1/3})$ （针对土匪方法，通过局部范数论证可提升至 $T^{-1/2}$ ）的速度收敛至零。
意义： 这为正则化学习在零和博弈中的收敛提供了定量保证，架起了经典虚构学习结果与现代在线学习之间的桥梁。

C. 正则化学习的“福克定理”

本文推导了一组将动态学习属性与策略均衡概念联系起来的稳定性结果，类似于进化博弈论中的福克定理（复制动态）。

性质 (P1)： 如果博弈序列以正概率收敛于一点 $x^*$ ，则 $x^*$ 是一个纳什均衡。
性质 (P2)： 如果一点 $x^*$ 是随机稳定的（即如果从附近开始，以高概率保持在 $x^*$ 附近），则它是纳什均衡。
性质 (P3)： 严格纳什均衡是随机渐近稳定的（具有高概率的吸引性）。
新颖性： 不同于通常需要递减步长的标准随机逼近结果，这些结果即使在常数步长下对于严格均衡也成立，这依赖于严格均衡是策略空间的角点这一事实。

4. 重要性与范围

本文将自身定位为一份“引导之旅”而非全面的综述。其主要意义在于：

统一性： 它提供了一个单一的分析框架（正则化学习），涵盖了多种算法（虚构学习、FTRL、EXP3、Tsallis-INF）和各种反馈类型（预言机、土匪）。
理性分析： 它澄清了遗憾最小化与均衡收敛之间的关系，证明了虽然无遗憾博弈并不保证在所有博弈中都能达到均衡，但正则化学习具有强大的理性属性（在零和博弈中收敛至纳什均衡，以及严格纳什均衡的稳定性）。
方法论清晰度： 通过利用凸分析（Fenchel 耦合、强凸对偶）和随机逼近的工具，本文为推导遗憾界限和收敛速率提供了一个连贯的叙述。

作者明确指出了局限性：为了保持叙述的聚焦性和自洽性，本文省略了关于粗略相关均衡（coarse correlated equilibria）、遗憾匹配（regret-matching）、校准（calibration）、试错学习（trial-and-error learning）以及连续时间模型的广泛文献。分析也局限于有限博弈（尽管提到可扩展至变分不等式设定），并且没有深入讨论基于外插法的变体（例如 Extra-Gradient）。