核心结论
麻省理工学院 LIDS 的 Mingyang Liu、Gabriele Farina 与 Asuman Ozdaglar 团队在预印本 Constant Individual Regret in General Games(arXiv:2608.31166v1,首次公告归属 2026-09-01 上海日历日,对应 31 Aug 2026 17:59 UTC)中证明:在任意有限 N 人正规博弈的完全信息自对弈中,存在确定性非耦合学习动态使每个玩家的个体外部遗憾被与时域 T 无关的常数一致上界控制。该结论为作者理论推导结果,尚未经同行评审,独立验证仍待开展。
方法与评估条件
研究将每轮 payoff 向量经 lifted 变换为 g_i(t) 并引入 EMA 级联高阶乐观 ECHO。设 L 为延迟算子,A=(I-rho L)^-1,delta=A(I-L),则预测器 hat g_i=(I-delta^N)g_i、误差 e_i=delta^N g_i;delta 将标准单步差分的指数放大从 2^N 降至不超过 e,同时时域滤波界保持对 N 多项式。动态采用 lifted 平方根熵响应与动态 pacing,公共学习率 eta>0,每轮通过 N 级 EMA 递归计算预测向量后再执行 OFTRL 更新,策略呈现 Hedge 形式,所有更新仅依赖玩家自身历史 payoff。评估条件为 N>=2、m_i>=2、效用在[0,1]的任意有限正规博弈、全信息反馈且全体共用该动态。
数据范围与主要结果
在上述范围内,作者证明同时对全部 horizon T>=1、全部玩家 i 满足 Reg_i(T) <= C(N+1)^21(1+log(m_max+1))^4,C 为通用常数,界仅依赖玩家数与最大动作数的对数多项式,与 T 无关。对比表显示此前最佳为 O(N log^2 m log T),本工作首次将 log T 依赖去除,代价为显式指数 N^21 与 log^4 项。方法在 lifted 遗憾与非负 RVU 界框架下,利用高阶预测误差可和性与负 movement 项相消得到常数界,并指出因 dynamics 基于 lifted Hedge,可核化至组合与扩展式博弈。结果为理论上界,未给出常数数值。
局限与不确定性
作者未回避以下边界:界中 N^21 极高且未尝试优化,常数可能极大,实际意义更多在定性去除时域依赖而非数值紧致;理论仅在全信息、有限、效用有界且全体共用相同动态假设下成立,单方偏离或对抗性任意序列下不适用;分析未包含实证实验或与现有方法对弈胜率对比,高阶 EMA 级联在 N 较大时开销与数值稳定性亦未实测。所有提升均在作者控制理论模型内取得,不代表通用系统保证。
同行评审状态与潜在意义
该工作当前为预印本 arXiv:2608.31166v1,尚未发表于期刊或会议,需标注为未同行评审,引用与落地应审慎。若经同行评审与独立验证成立,其意义在于回答了非耦合正则学习能否保持每玩家正遗憾一致有界的长期问题,为去中心化均衡寻求与大规模博弈求解提供了新乐观构造,并为后续优化常数与扩展至更一般反馈指明方向。