知识卡片：一般博弈中的常数个体遗憾

一句话结论

在全信息反馈（full-information feedback）下，论文提出确定性的完全非耦合算法 ECHO-OFTRL，在任意有限 (N) 人策略式博弈中，使每个玩家的个体遗憾上界为
[ O(\mathrm{poly}(N,\log m_{\max})) ] 其中 (m_{\max}) 是最大的行动集大小。该上界与时间范围 (T) 无关，因此个体遗憾相对于 (T) 可视为“常数”。

研究问题

非耦合无遗憾动力学（uncoupled no-regret dynamics）为去中心化地达到均衡提供了一条经典路线，但此前的个体遗憾保证中，对时间范围 (T) 仍有 polylog 依赖。本文研究的问题是：在一般有限 (N) 人策略式博弈中，能否在全信息反馈下消除这种对 (T) 的依赖，得到常数级个体遗憾。

方法/产品要点

提出算法 ECHO-OFTRL：optimistic follow-the-regularized-leader（OFTRL）配上 EMA cascade for high-order optimism，其中 EMA 是 exponential moving average，即指数移动平均。
算法是确定性的，并且满足**完全非耦合（fully uncoupled）**约束。
该算法利用了一种受“现代滤波器设计”启发的新形式乐观项（optimism）。
论文结果局限于全信息反馈设定；具体的更新规则、EMA 级联参数与证明细节摘要中未展开。

主要结果或产业意义

对于每个有限 (N) 人策略式博弈，在全信息反馈下，该算法同时对所有 (T \ge 1) 成立：
- 每个玩家的个体遗憾不超过 (O(\mathrm{poly}(N,\log m_{\max})))。
该上界不依赖 (T)，只依赖玩家数 (N) 和行动集大小的对数。
就理论意义而言，它把非耦合无遗憾动力学中个体遗憾对时间范围的依赖完全移除，进一步巩固了“去中心化学习能通往均衡”这一理论路线的可行性。
摘要未提供具体产业场景；可理解为对长期运行的多智能体去中心化系统具有潜在理论意义。

为什么重要

此前非耦合无遗憾动力学中，个体遗憾通常只能做到随 (T) 呈 polylog 增长。本文把这一依赖去掉，同时保持算法确定性和完全非耦合，说明在一般有限博弈中，只要反馈是全信息的，个体长期遗憾可以做到不随时间范围变大。这为博弈论、在线学习和多智能体系统方向的后续研究提供了新的理论基准。

与既有脉络的关系

已有相关卡片分别涉及多模态生成基准、扩散环境多臂老虎机、不确定 MDP 策略集合，均未覆盖一般博弈中的非耦合无遗憾动力学/个体遗憾问题。本条不是对既有卡片的重复，而是一个新的理论结果。

局限与不确定性

来源目前是 arXiv 预印本，是否经过同行评审待核实。
摘要未给出 (O(\mathrm{poly}(N,\log m_{\max}))) 的具体指数、隐藏常数，也未说明收益是否需要有界或归一化假设（待核实）。
“完全非耦合”在本文中的精确信息结构、通信假设，以及算法是否只需要每个玩家自身的行动和收益历史，需以原文为准（待核实）。
摘要未说明该结果是否可扩展到 bandit 反馈或部分信息反馈（待核实）。
“通往均衡”具体指相关均衡、粗相关均衡或其他均衡概念，以及收敛速度，摘要中未展开（待核实）。
摘要中未给出匹配下界，因此该上界是否最优待核实。

可用于图书/PPT/简报的角度

标题角度：从“个体遗憾随 (T) 呈 polylog 增长”到“常数个体遗憾”。
算法设计角度：用“EMA 级联”和“滤波器设计”启发在线学习中的乐观项。
理论意义角度：去中心化无遗憾学习在一般有限博弈中可以摆脱时间范围依赖。

原始材料

英文标题：Constant Individual Regret in General Games
英文关键词（根据摘要提炼）：no-regret dynamics; uncoupled dynamics; normal-form games; individual regret; full-information feedback; optimistic follow-the-regularized-leader; ECHO-OFTRL
原始来源：arXiv:2608.31166v1 [cs.LG, cs.GT]
URL：https://arxiv.org/abs/2608.31166v1
PDF URL：https://arxiv.org/pdf/2608.31166v1
作者：Mingyang Liu, Gabriele Farina, Asuman Ozdaglar
发布时间：2026-08-31T17:59:16Z