这篇论文提出了在线学习和博弈中的最优交替遗憾算法，对于在线线性优化和在线凸优化领域的研究具有重要意义，特别是对于收敛速度和下界的研究。
本研究解决了在线线性优化（OLO）和在线凸优化（OCO）中的最小-最大最优交替遗憾问题，提出了一种具有 $O(\log d)$ 交替遗憾的算法，该算法在任何时间范围内都保持常数，并给出了匹配的下界。在两人零和博弈中，实现了 $O(\log d /T)$ 收敛到纳什均衡，在两人一般和博弈中实现了 $O(\log d /T)$ 收敛到粗相关均衡。此外，对于 $d$ 维紧凸集上的通用 OCO，提出了具有 $O(d\log (1+T/d))$ 交替遗憾的算法，并证明了匹配的下界 $Ω(d\log (1+T/d))$。
Optimal Alternating Regret for Online Learning and Games
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.