# Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes

arXiv: https://arxiv.org/abs/1905.04532 · HTML: https://mlsanity.com/paper/1905.04532/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2019.

## Built on by (most cited first, 14 of 14)

- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games](https://mlsanity.com/paper/2106.03579/) (2021)
- [Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence](https://mlsanity.com/paper/2106.04748/) (2021)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [Optimism Without Regularization: Constant Regret in Zero-Sum Games](https://mlsanity.com/paper/2506.16736/) (2025)
- [Configurable Mirror Descent: Towards a Unification of Decision Making](https://mlsanity.com/paper/2405.11746/) (2024)
- [Regret Minimization in Population Network Games: Vanishing Heterogeneity and Convergence to Equilibria](https://mlsanity.com/paper/2507.17183/) (2025)
- [Chaos persists in large-scale multi-agent learning despite adaptive learning rates](https://mlsanity.com/paper/2306.01032/) (2023)
- [Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos](https://mlsanity.com/paper/2312.11943/) (2023)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)

## Abstract (arXiv)

We show for the first time, to our knowledge, that it is possible to reconcile in online learning in zero-sum games two seemingly contradictory objectives: vanishing time-average regret and non-vanishing step sizes. This phenomenon, that we coin ``fast and furious" learning in games, sets a new benchmark about what is possible both in max-min optimization as well as in multi-agent systems. Our analysis does not depend on introducing a carefully tailored dynamic. Instead we focus on the most well studied online dynamic, gradient descent. Similarly, we focus on the simplest textbook class of games, two-agent two-strategy zero-sum games, such as Matching Pennies. Even for this simplest of benchmarks the best known bound for total regret, prior to our work, was the trivial one of O(T), which is immediately applicable even to a non-learning agent. Based on a tight understanding of the geometry of the non-equilibrating trajectories in the dual space we prove a regret bound of Theta(√T) matching the well known optimal bound for adaptive step sizes in the online setting. This guarantee holds for all fixed step-sizes without having to know the time horizon in advance and adapt the fixed step-size accordingly. As a corollary, we establish that even with fixed learning rates the time-average of mixed strategies, utilities converge to their exact Nash equilibrium values.