# Optimism Without Regularization: Constant Regret in Zero-Sum Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 47 references that are in the map.
- First posted on arXiv 20 Jun 2025.

## Builds on (most cited first, 30 of 31)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games](https://mlsanity.com/paper/2111.06008/) (2021)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Near-Optimal No-Regret Learning Dynamics for General Convex Games](https://mlsanity.com/paper/2206.08742/) (2022)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Acceleration through Optimistic No-Regret Dynamics](https://mlsanity.com/paper/1807.10455/) (2018)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Alternating Mirror Descent for Constrained Min-Max Games](https://mlsanity.com/paper/2206.04160/) (2022)
- [A Counter-Example to Karlin's Strong Conjecture for Fictitious Play](https://mlsanity.com/paper/1412.4840/) (2014)
- [Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Games](https://mlsanity.com/paper/2111.04317/) (2021)
- [Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games](https://mlsanity.com/paper/2106.03579/) (2021)
- [Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games](https://mlsanity.com/paper/2311.00676/) (2023)
- [Efficient Phi-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games](https://mlsanity.com/paper/2402.09670/) (2024)
- [Alternating Regret for Online Convex Optimization](https://mlsanity.com/paper/2502.12529/) (2025)
- [Sampling Equilibria: Fast No-Regret Learning in Structured Games](https://mlsanity.com/paper/2201.10758/) (2022)
- [Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play](https://mlsanity.com/paper/2506.13086/) (2025)
- [A Symplectic Analysis of Alternating Mirror Descent](https://mlsanity.com/paper/2405.03472/) (2024)

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

- [Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games](https://mlsanity.com/paper/2510.04407/) (2025)
- [Minimax Alternating Regret for the Experts Problem and Online Convex Optimization](https://mlsanity.com/paper/2608.25182/) (2026)

## Abstract (arXiv)

This paper studies the optimistic variant of Fictitious Play for learning in two-player zero-sum games. While it is known that Optimistic FTRL -- a regularized algorithm with a bounded stepsize parameter -- obtains constant regret in this setting, we show for the first time that similar, optimal rates are also achievable without regularization: we prove for two-strategy games that Optimistic Fictitious Play (using any tiebreaking rule) obtains only constant regret, providing surprising new evidence on the ability of non-no-regret algorithms for fast learning in games. Our proof technique leverages a geometric view of Optimistic Fictitious Play in the dual space of payoff vectors, where we show a certain energy function of the iterates remains bounded over time. Additionally, we also prove a regret lower bound of Omega(√T) for Alternating Fictitious Play. In the unregularized regime, this separates the ability of optimism and alternation in achieving o(√T) regret.