Optimal Alternating Regret for Online Learning and Games

arXiv:2608.24731v1 Announce Type: new Abstract: 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 Delta_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 dot 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(dlog (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 Omega(dlog (1+T/d)), showing that the Omega(log T) factor is unavoidable.

Related

• Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
• Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
• Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
• Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization

Source: arXiv cs.LG | 2026-08-26