新算法HOOD实现一般博弈中常数个体遗憾，界达O(N³ log²K)
arXiv论文提出一种非耦合学习算法，在所有玩家采用时，任意N人正则型博弈中个体遗憾为常数，显著优于此前结果。
AI解读：博弈论中的“遗憾”衡量一个玩家在反复博弈中，因没有提前知道对手策略而损失的平均收益。以往算法在一般博弈中遗憾会随时间增长，无法保证长期稳定。这项研究提出的HOOD算法，通过结合高阶预测和熵正则化，首次将个体遗憾压到不依赖对局轮数的常数，具体为O(N³ log²K)。这意味着只要每个玩家都使用该算法，无论玩多少轮，平均损失都不会无限制累积。对多智能体系统、在线广告拍卖或资源分配等场景，这提供了更可靠的学习策略。不过，该结果是理论保证，实际计算成本可能较高，论文尚未提供实验验证。另一组研究者独立得到了类似结论，但遗憾界更差（O(N²¹ log⁴K)），说明HOOD在理论上更优。感兴趣的研究者可以关注后续是否出现实用化改进。
arXiv上一项新研究提出一种非耦合学习算法HOOD（高阶乐观折扣法），当所有玩家在最多K个动作的N人正则型博弈中采用该算法时，可保证个体遗憾为O(N³ log²K)，且不随对局轮数增长。
论文作者为Omar Abbadi、Rida Laraki和Panayotis Mertikopoulos，预印本编号arXiv:2609.04113，于 2026 年 9 月 3 日提交。
HOOD是乐观跟随正则化领袖（OptFTRL）的变体，结合了折扣的N+1阶预测器和在博弈策略空间适当“提升”上的熵正则化。
论文指出，该设计旨在受控地抑制玩法序列的大幅振荡，从而消除了此前在一般博弈中实现常数遗憾的关键障碍。
完整证明见 42 页正文及 1 幅图，属于机器学习（cs.LG）和计算机科学与博弈论（cs.GT）交叉领域。
与独立工作的比较
论文提到，其方法与Liu、Farina和Ozdaglar的并行工作（arXiv:2608.31166）有显著相似之处，但两篇论文完全独立完成。
Liu等人通过高阶乐观和指数移动平均估计器推导出O(N²¹ log⁴K) 的遗憾界，而HOOD的界为O(N³ log²K)，就理论界而言更优。
以上比较基于论文摘要中的声明，未涵盖完整技术细节。