Logarithmic Regret for Alternating Mirror Descent

Tianlong Nan, Christian KroerarXiv 2026 · arXiv

TL;DR

This paper proves that Alternating Online Mirror Descent (AltOMD)—a simple, widely used learning rule—achieves $O(\log T)$ regret in two-player zero-sum bilinear games. By treating the algorithm as a discretization of Hamiltonian dynamics and using a time-dependent truncation of the Baker-Campbell-Hausdorff (BCH) series, the authors resolve a long-standing open question, showing that simple alternation is sufficient for near-constant regret without needing complex modifications like optimism.

What Problem Does This Paper Address?

In the world of game theory and optimization, we often want to know how quickly decentralized agents can reach a Nash equilibrium. A standard metric for this is external regret: how much better a player could have done by picking the single best fixed strategy in hindsight.

For two-player zero-sum games, the sum of players' regrets directly controls the "duality gap" (how far the average strategies are from equilibrium). While simultaneous Mirror Descent yields $O(\sqrt{T})$ regret, researchers have long observed that alternating updates (Player 1 moves, then Player 2 moves based on Player 1's new position) perform much better numerically.

Previous theoretical work struggled to prove just how much better. Bounds were stuck at polynomial rates like $O(T^{1/3})$ or $O(T^{1/5})$. The community suspected that AltOMD could achieve "near-constant" (logarithmic) regret, similar to more complex "optimistic" algorithms, but the proof remained elusive due to the difficulty of controlling discretization errors over long time horizons.

Methods

The authors bridge the gap between discrete algorithms and continuous physics by viewing AltOMD through the lens of Hamiltonian dynamics.

  1. Dual Space Analysis: They analyze the algorithm in the "mirror" or dual space, where the updates become additive and unconstrained.
  2. Modified Energy Functions: In continuous time, Hamiltonian systems conserve "energy." In discrete time, the energy drifts. To track this, the authors use a Modified Hamiltonian—a formal power series constructed using the Baker-Campbell-Hausdorff (BCH) formula.
  3. Dynamic Truncation: The key innovation is how they handle this series. Previous attempts truncated the series at a fixed order (e.g., 3rd order). This paper uses a truncation order $N$ that scales with the time horizon ($N = \Theta(\log T)$).
  4. Controlled Stepsize: For a fixed horizon $T$, they set a constant stepsize $\eta = \Theta(1/\log T)$.
  5. Derivative Growth Condition: They identify a specific regularity condition (Assumption 3.1) on the regularizers (mirror maps) that ensures the higher-order terms in the BCH series don't explode, allowing the $O(\log T)$ bound to hold.

Datasets

As a theoretical work in mathematical optimization, this paper does not use empirical datasets for training or evaluation. However, the authors have provided a Lean formalization of their proofs, making the mathematical results machine-verifiable. The code is available at: https://github.com/CoffeeAndConvexity/AltOMD-Lean.

Key Insights and Ideas

  • Alternation as a Stabilizer: The paper reinforces the idea that alternation isn't just a heuristic; it provides a structural stability that mimics "optimistic" methods (which use extra gradient steps to predict the opponent's move) without the extra computational overhead.
  • Exponential Error Suppression: By letting the approximation order of the energy function grow with the horizon, the discretization error is suppressed exponentially relative to the truncation order. This is what allows the jump from polynomial $O(T^{1/a})$ bounds to logarithmic $O(\log T)$.
  • Generality of Regularizers: The results aren't limited to standard Euclidean gradients. They apply to any Legendre regularizer satisfying a derivative growth condition, most notably negative Shannon entropy, which leads to the popular Multiplicative Weights Update (MWU) algorithm.

Key Results

  • Logarithmic Regret: The sum of external regrets for AltOMD is bounded by $O(\log T)$ for any two-player zero-sum bilinear game with compact convex strategy sets.
  • Equilibrium Convergence: This implies an $O(\frac{\log T}{T})$ convergence rate for the duality gap of the averaged strategies.
  • MWU Guarantee: For the specific case of the simplex (using entropy), the paper proves a regret bound of $O(\|A\| \log(nm) \log T + \|A\|^2)$, where $A$ is the payoff matrix and $n, m$ are the number of actions.
  • Boundary Robustness: Unlike some previous results, this analysis holds even when the equilibrium lies on the boundary of the strategy set and dual trajectories are unbounded.

Limitations and Future Work

  • Bilinear Restriction: The current proof is tailored to bilinear games (like matrix games). Extending these logarithmic bounds to general convex-concave saddle-point problems remains an open challenge.
  • Horizon Dependence: The optimal stepsize $\eta$ requires knowing the time horizon $T$ in advance. Developing an "anytime" version of the algorithm that maintains $O(\log T)$ regret without knowing $T$ is a natural next step.
  • Assumption 3.1: While the authors show that entropy satisfies their derivative growth condition, it remains to be seen which other exotic regularizers used in machine learning fit this framework.

Summary updated

Abstract

Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.
BibTeX
@misc{nan2026logarithmic,
  author = {Tianlong Nan and Christian Kroer},
  title = {{Logarithmic Regret for Alternating Mirror Descent}},
  year = {2026},
  eprint = {2611.05243},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05243},
}

Loading related content...

Figure