Optimal Alternating Regret for Online Learning and Games
Not on the map. Why?
Abstract (arXiv)
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 Deltad, 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/3d · T1/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(dlog (1+T/d)) alternating regret, improving the previous best of widetildeO(d2/3T1/3). We also prove a matching lower bound of Omega(dlog (1+T/d)), showing that the Omega(log T) factor is unavoidable.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 22 of its 35 references that are in the map. First posted on arXiv 25 Aug 2026.
Builds on
22 of 35 references.
References · 22
- 2019Introduction to Online Convex Optimizationcited by 803
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
- 2015Fast Convergence of Regularized Learning in Gamescited by 150
- 2014Solving Large Imperfect Information Games Using CFR+cited by 78
- 2020Hedging in games: Faster convergence of external and swap regretscited by 57
- 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
- 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
- 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
- 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 29
- 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
- 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
- 2022Alternating Mirror Descent for Constrained Min-Max Gamescited by 13
10 more
- 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 13
- 2025Negative Stepsizes Make Gradient-Descent-Ascent Convergecited by 11
- 2025Faster Rates for No-Regret Learning in General Games via Cautious Optimismcited by 10
- 2024Fundamental Benefit of Alternating Updates in Minimax Optimizationcited by 9
- 2025Cautious Optimism: A Meta-Algorithm for Near-Constant Regret in General Gamescited by 7
- 2025Alternating Regret for Online Convex Optimizationcited by 4
- 2026Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularizationcited by 4
- 2024A Riemannian Alternating Descent Ascent Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifoldscited by 3
- 2025Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Gamescited by 3
- 2025On the O(1/T) Convergence of Alternating Gradient Descent-Ascent in Bilinear Gamescited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.