Optimal Alternating Regret for Online Learning and Games

In online learning, standard regret measures performance against a fixed strategy. However, in two-player games where players update their strategies sequentially (alternating learning dynamics), this standard notion is often too pessimistic. The authors investigate the minimax-optimal alternating regret, a refined metric that accounts for the information available to players in alternating updates, and its implications for the convergence rates of learning dynamics in games.

To address this, the authors introduce the "alternation-aware Hedge" (AA-Hedge) algorithm. This algorithm modifies the classic Hedge approach by incorporating a bias toward the most recently observed loss function. For online linear optimization (OLO) over a probability simplex, they prove that this algorithm achieves constant alternating regret. They then extend this to a continuous version for general online convex optimization (OCO) over compact convex sets. The authors also derive matching lower bounds for both settings, confirming that their algorithms are minimax-optimal.

This work resolves a long-standing open question regarding the fundamental limits of alternating regret. By achieving O(1/T) convergence to coarse correlated equilibria (CCE) in general-sum games, the paper provides the first uncoupled learning dynamics that avoid the additional logarithmic factors (log T) present in previous approaches. This makes alternating learning dynamics more theoretically efficient and practically relevant for training AI models in complex game environments.