提出最优交替后悔算法，实现博弈学习中更快的均衡收敛。
Optimal Alternating Regret for Online Learning and Games
- 设计新算法，在线线性优化下交替后悔仅随维度对数增长。
- 在零和与一般和博弈中，均衡收敛率达 $O(\log d / T)$，突破旧有 $\log T$ 限制。
- 首次实现无耦合学习动态下一般和博弈的 $O(1/T)$ 精确收敛，适合博弈论研究者。
本文解决了在线线性优化（OLO）和在线凸优化（OCO）中最小最大最优交替后悔问题。针对概率单纯形 $Δ_d$ 上的 OLO，提出了 $O(\log d)$ 交替后悔的算法，且在任意时间 $T$ 下保持常数上界，并给出匹配下界。该结果显著优于此前 $O(\log^{2/3}d \cdot T^{1/3})$ 的成果。由此可得，在双人零和博弈中，交替学习动态以 $O(\log d / T)$ 收敛至纳什均衡；在双人一般和博弈中，以 $O(\log d / T)$ 收敛至联合相关均衡（CCE），这是首个无需 $\log T$ 因子的无耦合动态。对于 $d$ 维紧凸集上的通用 OCO，给出 $O(d\log(1+T/d))$ 交替后悔算法，优于之前的 $\widetilde{O}(d^{2/3}T^{1/3})$，并证明下界 $Ω(d\log(1+T/d))$，表明 $Ω(\log T)$ 因子不可避免。
原文摘要 · Abstract (English)
We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $Δ_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $Ω(d\log (1+T/d))$, showing that the $Ω(\log T)$ factor is unavoidable.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。