一般博弈中的常数个体遗憾

Constant Individual Regret in General Games

arXiv: 2608.31166v1

论文信息

标题: Constant Individual Regret in General Games

作者: Mingyang Liu, Gabriele Farina, Asuman Ozdaglar

发布日期: 2026-08-31

arXiv ID: 2608.31166v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：在有限 N 人正规形式博弈、完全信息反馈的自博弈设定下，无耦合 no-regret 动态能否让每个玩家的个体遗憾不随 horizon T 增长，而保持常数？
  • 核心方法：提出 ECHO-OFTRL，将 optimistic follow-the-regularized-leader 与 EMA 级联高阶乐观（ECHO）结合，用稳定滤波器 δ=(I−L)/(I−ρL)\delta=(I-\mathsf{L})/(I-\rho\mathsf{L}) 构造高阶预测。
  • 关键结果：定理 3.3 证明，当学习率 η=2−94/(N20Ξmax⁡)\eta=2^{-94}/(N^{20}\Xi_{\max}) 时，任意 T≥1T\ge 1 都有 ∑i=1N[Reg⁡i(T)]+≤2112N21(1+log⁡(mmax⁡+1))4\sum_{i=1}^N[\operatorname{Reg}_i(T)]_+\le 2^{112}N^{21}(1+\log(m_{\max}+1))^4。
  • 主要局限：常数依赖为 N21N^{21} 且未优化；需要所有玩家都采用同一确定性算法和完整 payoff 向量反馈；学习率极小，理论界对实际调参指导有限。
  • 适合读者：研究在线学习、博弈论、no-regret dynamics、最优化与信号处理交叉方向的研究生和学者。

论文背景和研究动机

无耦合 no-regret 动态是去中心化学习中通往均衡的重要路径：如果每个玩家都只有小的外部遗憾，经验行动分布会接近粗相关均衡（CCE）。传统在线学习把 payoff 序列视为任意且可能对抗的外生过程，T\sqrt T 遗憾不可回避；但在自博弈中，payoff 序列由固定博弈和所有玩家的更新共同决定。由于策略更新光滑，每个玩家面临的动态环境具有一定可预测性，乐观方法正是利用这种可预测性来加速收敛。

该方向的进展经历了从 RVU 框架的 T1/4T^{1/4} 个体遗憾（Syrgkanis et al., 2015），到两玩家特殊情形 T1/6T^{1/6}（Chen and Peng, 2020），再到 Optimistic Hedge 的 O(log⁡4T)O(\log^4 T)（Daskalakis, Fishelson, and Golowich, 2021），以及 lifted OFTRL 的 O(log⁡T)O(\log T)（Farina et al., 2022a）。近期工作如 DLRC-OMWU / Cautious Optimism（Soleymani et al., 2025b; Soleymani et al., 2025a）进一步把动作数依赖降到 polylogarithmic。本文的核心问题是：是否能把个体遗憾的 horizon 依赖彻底去掉？论文给出的答案是肯定的，并用表 1 总结了这些进展与本文的常数界对比。

核心方法和技术细节

论文的关键技术之一是 lifting。对每个玩家 ii，定义 lifted 集合 Δ~i={(λ,y):0≤λ≤1,y∈λΔmi}\widetilde\Delta_i=\{(\lambda,\bm y):0\le\lambda\le 1,\bm y\in\lambda\Delta^{m_i}\}，并令 payoff 差向量为 gi(t)=ui(t)−⟨ui(t),xi(t)⟩1\bm g_i^{(t)}=\bm u_i^{(t)}-\langle\bm u_i^{(t)},\bm x_i^{(t)}\rangle\bm 1。这样，相对于 lifted comparators 的最大化恰好等于原外部遗憾的正部：

max⁡(λ^i,λ^ix^i)∈Δ~i∑t=1T⟨gi(t),λ^ix^i−λi(t)xi(t)⟩=[Reg⁡i(T)]+.\max_{(\hat\lambda_i,\hat\lambda_i\hat{\bm x}_i)\in\widetilde\Delta_i}\sum_{t=1}^T\langle\bm g_i^{(t)},\hat\lambda_i\hat{\bm x}_i-\lambda_i^{(t)}\bm x_i^{(t)}\rangle=[\operatorname{Reg}_i(T)]_+.

该式来自论文 3.1 节公式 (3.1)。抬升后的遗憾是非负的，避免某个玩家的负遗憾掩盖其他玩家的正遗憾。

第二项关键设计是平方根熵响应。正则化器定义为

ψ~m(λ,y)=−1−λ+λ[ψm(y/λ)−2Γm−3],\widetilde\psi_m(\lambda,\bm y)=-\sqrt{1-\lambda}+\sqrt\lambda\bigl[\psi_m(\bm y/\lambda)-2\Gamma_m-3\bigr],

其中 ψm\psi_m 是熵，Γm\Gamma_m 控制方差。响应 Qm(θ)=arg⁡max⁡(λ,y)∈Δ~m(⟨θ,y⟩−ψ~m(λ,y))Q_m(\bm\theta)=\arg\max_{(\lambda,\bm y)\in\widetilde\Delta^m}(\langle\bm\theta,\bm y\rangle-\widetilde\psi_m(\lambda,\bm y)) 在给定 λ\lambda 时正好退化为 Hedge 策略，学习率为 ηλ\eta\sqrt{\lambda}（见 3.2 节和 Lemma 3.1）。这一构造把普通遗憾转为 lifted 遗憾，并为后续非负 RVU 界提供几何基础。

第三项是论文的核心信号处理构造：ECHO。传统乐观方法通常用前一 payoff 向量预测当前值，高阶差分若直接使用 (I−L)N(I-\mathsf L)^N，系数绝对值会达到 2N2^N，可能指数放大振荡。论文改为令

ρ=1−1N,δ=I−LI−ρL,\rho=1-\frac1N,\qquad \delta=\frac{I-\mathsf L}{I-\rho\mathsf L},

取预测 g^i=(I−δN)gi\widehat{\bm g}_i=(I-\delta^N)\bm g_i，则预测误差为 ei=δNgi\bm e_i=\delta^N\bm g_i。因为 I−δ=(1−ρ)L(I−ρL)−1I-\delta=(1-\rho)\mathsf L(I-\rho\mathsf L)^{-1} 是一个单极点 EMA，所以 NN 阶差分的频率增益从 2N2^N 降到 (2/(1+ρ))N≤e(2/(1+\rho))^N\le e，同时时域滤波器界仍保持多项式 NN（见 1.1 节与 3.3 节）。算法用 EMA 级联递归实现，对每个 h∈[N]h\in[N]：

emai,h(t+1)=ρ emai,h(t)+(1−ρ)(gi(t)−∑ℓ=1h−1emai,ℓ(t)),\mathsf{ema}_{i,h}^{(t+1)}=\rho\,\mathsf{ema}_{i,h}^{(t)}+(1-\rho)\Bigl(\bm g_i^{(t)}-\sum_{\ell=1}^{h-1}\mathsf{ema}_{i,\ell}^{(t)}\Bigr),

并令 g^i(t)=∑h=1Nemai,h(t)\widehat{\bm g}_i^{(t)}=\sum_{h=1}^N\mathsf{ema}_{i,h}^{(t)}。该递归对应 Algorithm 1，每个玩家每轮使用 O(Nmi)O(Nm_i) 记忆和算术操作。

分析上，论文先利用乐观 FTRL 路径不等式把遗憾界转化为预测误差加权和减去策略运动项（见公式 A.19）。随后通过加权卷积、频域/时域滤波器估计和递归 bound，证明关键变差估计：

∑i=1N∑t=1T(λi(t))3/2∥(δNgi)(t)∥∞2=O(N16(1+PTΞ)),\sum_{i=1}^N\sum_{t=1}^T(\lambda_i^{(t)})^{3/2}\bigl\|(\delta^N\bm g_i)^{(t)}\bigr\|_\infty^2 = O\bigl(N^{16}(1+\mathcal P_T^\Xi)\bigr),

其中 PTΞ\mathcal P_T^\Xi 是 Bregman 散度累积量。最终选择合适的 η\eta，策略运动项被负项吸收，于是遗憾界与 TT 无关（见 4.2 节和 Proposition A.6）。

创新点和贡献

本文的主要贡献是首次在一般有限 N 人正规形式博弈、完全信息反馈下，用无耦合、确定性学习动态实现常数个体遗憾。正式结果来自定理 3.3：对所有 T≥1T\ge 1，同时保证

∑i=1N[Reg⁡i(T)]+≤2112N21(1+log⁡(mmax⁡+1))4.\sum_{i=1}^N[\operatorname{Reg}_i(T)]_+\le 2^{112}N^{21}\bigl(1+\log(m_{\max}+1)\bigr)^4.

与之相比，表 1 中此前最好的同类方法至少还保留 log⁡T\log T 或更高阶 horizon 依赖。论文没有宣称常数很小，作者明确指出未优化指数，且该界对玩家数依赖为多项式。

方法上，新的 EMA 级联高阶乐观（ECHO）提供了稳定的高阶预测器设计。它不同于更早的 clairvoyant MWU：后者需要固定点联合计算，且遗憾保证只适用于稀疏子序列；本文算法是真正逐轮、完全无耦合的，并保证全历史遗憾（见 1.1 节）。此外，论文提到由于动态基于 lifted Hedge，可以 kernelize，因此可能扩展到组合设置和 extensive-form games，不过本文未展开这些扩展的完整证明。

实验结果分析

本文未报告数值实验。论文结果以形式化定理和伪代码（Algorithm 1）给出，没有在具体数据集或仿真环境中验证常数遗憾行为的经验表现。因此，关于算法在有限时间内的实际收敛速度、对不同博弈结构的敏感性、以及 η=2−94/(N20Ξmax⁡)\eta=2^{-94}/(N^{20}\Xi_{\max}) 这样的极小学习率在真实迭代中的影响，论文没有提供实验数据，读者只能依据理论界做推断。

局限与待解决问题

首先，定理 3.3 中的常数极大。N21N^{21} 与 21122^{112} 的组合使得在玩家数稍大时，理论遗憾上界对实际性能几乎没有参考价值。作者明确表示没有尝试优化这些指数，因此后续工作可以朝降低玩家数依赖、显式优化常数方向改进。

第二，算法需要完整 payoff 向量反馈，且分析建立在 utilities 取值 [0,1][0,1] 的多线性正规形式博弈上。论文提到可以通过 kernelized Hedge 扩展到组合和 extensive-form 设置，但这部分没有在本文完整证明，仍属于待验证方向。

第三，算法要求所有玩家都采用同一 ECHO-OFTRL，并使用共同的学习率 η\eta。一旦某些玩家偏离算法或使用不同学习率，界是否会退化、是否仍保持常数遗憾，本文未讨论。

第四，学习率 η=2−94/(N20Ξmax⁡)\eta=2^{-94}/(N^{20}\Xi_{\max}) 极小。尽管理论上保证了最坏情况的常数遗憾，但在实际迭代早期，策略可能几乎不移动，这会影响有限轮次内的实际性能。论文未给出更实用的调参策略或自适应版本。

最后，本文的滤器分析依赖 δ=(I−L)/(I−ρL)\delta=(I-\mathsf L)/(I-\rho\mathsf L) 的特定形式，且需要 NN 阶 EMA 级联。是否可以用更低复杂度的悲观/乐观混合或不同滤波器设计达到更小常数，仍是开放问题。