提出新算法实现任意多人博弈中恒定遗憾，性能更优且稳定。
Constant regret in general games via higher-order optimism
- 采用高阶乐观预测与熵正则化结合的无耦合学习机制
- 在任意N人、每方最多K动作的博弈中，个体遗憾为O(N³log²K)
- 适合研究多智能体博弈学习或追求稳定收敛的场景
我们提出一种无耦合学习算法，当所有玩家在任意具有至多K个动作的N人正常形式博弈中使用时，可保证个体遗憾为O(N³log²K)，且该结果对博弈时长均匀成立。所提算法——高阶乐观带折扣（HOOD）——是乐观跟随正则化领导者（OptFTRL）的变体，结合了折扣化的(N+1)阶预测器与策略空间适当“提升”后的熵正则化。该设计旨在可控地抑制策略序列的大幅振荡，从而消除此前实现恒定遗憾方法的关键障碍。本方法与近期独立完成的Liu、Farina和Ozdaglar（arXiv:2608.31166）工作存在显著相似性，后者通过高阶乐观与指数移动平均估计器也得到了O(N²¹log⁴K)的遗憾界。
原文摘要 · Abstract (English)
We introduce an uncoupled learning algorithm which, when employed by all players of an arbitrary $N$-player normal form game with up to $K$ actions per player, guarantees $O(N^3\log^2 K)$ individual regret, uniformly over the horizon of play. The proposed algorithm - which we call higher-order optimism with discounting (HOOD) is a variant of optimistic follow-the-regularized-leader (OptFTRL) that combines a discounted $(N+1)$-th order predictor with entropic regularization over a suitable "lifting" of the game's strategy space. This combination of ingredients is purposefully designed to dampen large oscillations of the induced sequence of play in a controlled manner, removing in this way a key stumbling block of previous attempts to achieve constant regret in general games. Our approach bears several striking similarities to the concurrent - and completely independent - work of Liu, Farina, and Ozdaglar (arXiv:2608.31166), who very recently derived an $O(N^{21}\log^{4} K)$ regret bound through the use of higher-order optimism and an exponential moving average estimator.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。