Logarithmic Regret for Alternating Mirror Descent

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.

Alternating updates, that is, where each player is updated in turn, tend to typically perform better in regret matching algorithms than simultaneous updates. Alternation within the regret matching family has long been a central ingredient of practical solvers for zero-sum games. Yet our theoretical understanding is lagging behind. In this paper, we address this gap by developing a systematic way of analyzing such algorithms. Our framework centers on an alternating analog of the RVU property that we introduce, which we use to obtain the optimal $T^{-1}$ average-iterate convergence within this family. In particular, we establish this for two simple variants of predictive regret matching$^+$: i) increasing-regret predictive regret matching$^+$ and ii) half-prediction regret matching$^+$. Interestingly, we find that half prediction is the unique prediction multiplier that satisfies our alternating RVU property, giving it a strong theoretical justification. Going beyond average-iterate convergence, we refine our framework to obtain $T^{-1/2}$ best-iterate convergence and further establish convergence of their strategy profiles to a single Nash equilibrium, without assuming equilibrium uniqueness. We go on to establish separations between alternating and simultaneous updates, including a game in which half-prediction regret matching$^+$ converges under alternating updates but fails to converge in terms of the last iterate under simultaneous updates. This provides theoretical support for the empirical observation that alternation can stabilize learning dynamics. Finally, experiments on 15 game benchmarks demonstrate that the strong theoretical properties of the half-prediction mechanism translate to strong practical performance, being on par with state-of-the-art solvers.

In this paper, we study alternating regret in online convex optimization (OCO), motivated by the success of alternating learning dynamics in two-player games. Although previous works have shown that $o(\sqrt{T})$ alternating regret is achievable under various assumptions on the loss functions and feasible domains, the minimax regret rate has remained open even for the expert problem. In this paper, we resolve this question by showing matching lower and upper bounds for both the expert problem and general OCO. Somewhat surprisingly, for the $d$-expert problem, we show that the minimax alternating regret is $Θ(\log d)$ by providing both a lower bound and an algorithm achieving a matching upper bound. This significantly improves upon the $O(T^{1/3}\log^{2/3} d)$ established by [HLLZ25]. We further extend our results to general OCO over a $d$-dimensional compact convex set and prove that the worst-case minimax alternating regret is $Θ\left(d\log \left(1+\frac{T}{d}\right)\right)$, also significantly improving upon the $O((d\log T)^{2/3}T^{1/3})$ upper bound and resolving the open problem posed by [CCK+23,HLLZ25]. As a direct implication, our alternating dynamics achieve $O(\frac{\log d}{T})$ convergence to Nash equilibrium in two-player zero-sum games, matching the state of the art, and give the first such convergence rate to coarse correlated equilibrium in two-player general-sum games. Technically, our upper bound for the expert problem is achieved by a corrected variant of Hedge. We extend the same corrected-potential argument to continuous action sets to obtain the optimal alternating-regret rate for OCO. For the lower bounds, the construction for the expert problem repeatedly eliminates half of the candidate experts, while the OCO lower bound instance construction replaces this discrete elimination by a more involved multiscale construction on the unit disk.