mlsanityData to 14 Oct 2026

Optimism Without Regularization: Constant Regret in Zero-Sum Games

arXiv 2506.16736 ↗First posted 20 Jun 2025cs.LG cs.GTcited by 2

Not on the map. Why?

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.

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

31 of 47 references.

References · 31

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  2. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  3. 2017Cycles in adversarial regularized learningcited by 124
  4. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  5. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  6. 2018Negative Momentum for Improved Game Dynamicscited by 60
  7. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  8. 2020Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scalingcited by 49
  9. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  10. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  11. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 31
  12. 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 29
19 more
  1. 2020Fictitious play in zero-sum stochastic gamescited by 26
  2. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  3. 2018Faster Rates for Convex-Concave Gamescited by 23
  4. 2018Acceleration through Optimistic No-Regret Dynamicscited by 22
  5. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
  6. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  7. 2019Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizescited by 14
  8. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  9. 2022Alternating Mirror Descent for Constrained Min-Max Gamescited by 13
  10. 2014A Counter-Example to Karlin's Strong Conjecture for Fictitious Playcited by 10
  11. 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 10
  12. 2021Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Gamescited by 6
  13. 2023Last-Iterate Convergence Properties of Regret-Matching Algorithms in Gamescited by 6
  14. 2024Efficient Phi-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Gamescited by 6
  15. 2025Alternating Regret for Online Convex Optimizationcited by 4
  16. 2022Sampling Equilibria: Fast No-Regret Learning in Structured Gamescited by 3
  17. 2025Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Playcited by 3
  18. 2024A Symplectic Analysis of Alternating Mirror Descentcited by 2
  19. 2025On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Gamescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Gamescited by 3
  2. 2026Minimax Alternating Regret for the Experts Problem and Online Convex Optimizationcited by 0