Regret, equilibrium, and learning in games: A guided tour
Panayotis Mertikopoulos
cs.GT, cs.LG, math.OC
2026-08-10
这篇导览用 FTRL 正则化学习框架，把单智能体多臂老虎机的 O(√T) regret 界与多智能体的均衡收敛（零和博弈、严格纳什稳定性）统一在同一套分析里。
博弈论里有个老问题叫「拟似理性」（as-if rationality）：一群只顾自己、目光短浅、甚至不知道自己在博弈的智能体，反复交锋后，会不会自然而然地玩到纳什均衡？在 1950 年代的经济学语境里这是个理论 curiosity，但在今天的机器学习里它变成了工程问题。广告拍卖、推荐系统、多智能体强化学习、GAN 训练，本质上都是若干学习器在博弈，而博弈论那些「人人知道完整规则、算得出均衡、完美执行均衡策略」的前提，几乎没有一个成立。
这篇是 Mertikopoulos（Grenoble/CNRS/Inria）写的一篇导览（guided tour），把这个问题的两条主线缝在一起。一条是单智能体的「对抗大自然」：学习者面对一串任意的、可能是恶意的回报向量，目标是把 regret（后悔值，即累计回报与事后最优固定策略的差距）压下去，这就是对抗多臂老虎机。另一条是多智能体的闭环：若干玩家互相博弈，回报由彼此的行动共同塑造，问题是博弈过程会不会收敛、收敛到什么。两条线靠一个统一的模板串起来：正则化学习（regularized learning）。
有两个坏消息先得认下。第一，算纳什均衡是 PPAD 完全的（Daskalakis 等人），意味着在一般博弈里别指望多项式时间算出来。第二，Hart 和 Mas-Colell 的不可能定理说，不存在能在所有博弈里都收敛到纳什的「非耦合」动力学。所以有意义的问题不是「能不能收敛」，而是「在哪些博弈类、用哪些策略，能收敛」。
核心模板是 follow-the-regularized-leader（FTRL）：每一轮对历史累计回报做一个最佳响应，但减掉一个正则化惩罚项 h，用来鼓励探索、防止死磕某个次优选择。这个惩罚项是整件事能成立的关键。没有它的 follow-the-leader（FTL）会因为太容易被预测而被对手利用，论文给了个两臂老虎机的反例，FTL 永远慢最优选择一轮，regret 以 Θ(T) 量级发散。加上强凸的正则项，策略序列被「平滑」住，灾难性的来回摇摆才被压下去。
FTRL 写成迭代形式很简洁：先把每轮回报累加成一个「分数变量」y，再通过一个选择映射 Q(ηy) 把分数变成混合策略。换不同的正则项 h 就得到一族经典算法：
把 oracle（全信息）和 bandit（只看所选动作回报）两类反馈统一掉，靠的是「黑箱回报模型」（BBM）：学习者每轮拿到的是一个带噪声的估计 v̂ = v + Z，真实回报向量 v 本身并不直接可见，Z 的方差和偏置由反馈类型决定。全信息时 Z=0，bandit 时 Z 的方差是 O(1/δ)，δ 是探索参数。一套分析同时覆盖两类。
单智能体 regret 界（Theorem 2）：FTRL 配 K-强凸正则项、定步长 η 时，E[Reg(T)] ≤ H/η + ηM²T/(2K)；把 η 调成 (1/M)√(2KH/T) 就得到标准的 O(√T)。这个界的关键是 Fenchel coupling 这个势函数。连续时间下 FTRL 的 regret 是常数 O(1)，离散时间多出一个可控的离散化误差项，强凸性正是用来压住这一项。
bandit 侧：
| 算法 | 反馈 | regret |
| EXP3 | bandit | O(√(AT log A))，首个无 regret 的 bandit 算法 |
| Tsallis-INF | bandit | O(√(AT))，最优，比 EXP3 省掉一个 log A |
多智能体侧，两人零和博弈是主力正面结果（Theorem 4）：FTRL 的遍历平均 x̄T（按步长加权的时间平均）的均衡 gap 收敛速率为 Õ(T^{-min{1-p, β, p-2μ}})。代入具体算法：全信息（EW/SEW）是 Õ(T^{-1/2})，bandit（EXP3/Tsallis-INF）是 Õ(T^{-1/3})，后者用 local norm 论证可收紧到 T^{-1/2}。
核心结果是「正则化学习的 folk 定理」（Theorem 5），它把演化博弈论里关于 replicator 动力学的经典 folk 定理搬到离散随机学习上来：
合起来是一句话：混合（非纯）纳什均衡不是吸引子，正则化学习的轨迹长期会避开它们，只有严格（纯策略）纳什均衡能留住。这就是「最严格者存活」（survival of the strictest）。即便在 bandit 反馈、甚至定步长下，严格纳什均衡仍然渐近稳定，这对随机逼近算法来说是相当少见的好性质。
对真正在部署多智能体学习系统的人，MARL、GAN、广告拍卖、推荐，这篇给的是一个收敛预期：如果你的博弈有严格（纯）纳什均衡，无 regret 学习器会找到并粘在上面；别指望它们稳稳收敛到混合均衡。这既是保证（严格均衡在 bandit、定步长下都可达），也是警告（一般和博弈里别假设收敛）。
统一框架的工程价值在于，oracle 版和 bandit 版是同一套分析的两种特例，速率都给到了。这篇定位是综述而非新方法，价值在综合。一条 Fenchel coupling 的分析主线，从老虎机的 regret 界一路拉到博弈的均衡收敛，把分散在博弈论、优化、概率论三边的结论讲成一个故事。
作者自己反复声明只「蹭了点皮」：扩展型博弈、随机博弈、extra-gradient 与 optimistic 变体都留给后续更长的专著。
更实质的几点。零和博弈的收敛是对遍历平均 x̄T 成立，不是对实际迭代 xt，最后迭代可能在单纯形边界附近游走；要拿到 last-iterate 收敛得加外推步（extra-gradient），论文没深讲。folk 定理在随机情形下的逆命题也不完整（Remark 9）。
更结构性的限制：两人零和是唯一的通用正面结果，一般和博弈只有 folk 定理这种偏负面的结论（只有严格纳什稳），并没有通用收敛保证。PPAD 完全性和 Hart 与 Mas-Colell 的不可能定理横在头顶，这篇综述既不能也不打算翻过去。通篇是凸分析和随机逼近，密度很高，「对 ML 的应用」只作为动机出现，没有任何实验。