Research map / Bandits and online learning / Online convex optimization and games
Optimism Without Regularization: Constant Regret in Zero-Sum Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that unregularized Optimistic Fictitious Play attains constant regret in 2x2 zero-sum games with a unique interior Nash equilibrium (any tiebreaking), and that Alternating Fictitious Play has Omega(sqrt(T)) regret on Matching Pennies.
Problem
Whether unregularized (unbounded stepsize) fictitious play variants can achieve O(1) regret in zero-sum games, as optimistic regularized FTRL does, and whether alternation alone can beat sqrt(T) regret.
Approach
Views Optimistic FP as skew-gradient descent on the support function of the strategy simplex in dual payoff space, and shows via a 2x2 subspace reduction and cycling invariants that this energy function stays bounded, giving constant regret without regularization.
Key results
- Optimistic FP with any tiebreaking rule has O(1) regret in all 2x2 zero-sum games with unique interior NE; energy bound 8 a_max (1+2 a_max/a_gap)^2.
- Alternating FP on Matching Pennies has regret at least Omega(sqrt(T)) for nearly all initializations, for any tiebreaking.
- Experiments on 15x15, 25x25, 50x50 games (T=10000) show OFP regret around 2-25 versus about 116-243 for standard FP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add optimism to standard fictitious play | FP · Identity 15×15 | total regret: 155.1 ± 3.9 -> 8.1 ± 1.6 | Helped |
| Add optimism to standard fictitious play | FP · RPS 15×15 | total regret: 235.6 ± 7.6 -> 2.9 ± 0.5 | Helped |
| Add optimism to standard fictitious play | FP · Random [0, 1] 15×15 | total regret: 116.2 ± 5.8 -> 4.3 ± 0.8 | Helped |
| Use optimism without regularization | Fictitious Play in 2×2 zero-sum games with unique interior NE · 2×2 zero-sum games | regret: O(√T) -> O(1) | Helped |
| Use alternation without regularization instead of optimism | Fictitious Play · 2×2 Matching Pennies | regret: O(1) -> Ω(√T) | Hurt |
Surprising findings
- Unregularized optimistic FP attains constant regret, whereas unregularized standard FP grows as sqrt(T) in 2x2 games.
- Alternation without regularization cannot beat sqrt(T) regret on Matching Pennies, in contrast to alternating FTRL with small stepsize.
Limitations
- Main theorem is proven only for 2x2 games with a unique interior Nash equilibrium.
- Whether OFP has constant regret in all zero-sum games is stated as open.
- Higher-dimensional results are empirical only.
Experimental setup
Benchmarks: Matching Pennies identity matrix game generalized Rock-Paper-Scissors random [0,1] payoff matrices
Metrics: total regret
Baselines: Fictitious Play Alternating Fictitious Play Optimistic FTRL
Builds on: Fictitious Play Optimistic FTRL Optimistic Multiplicative Weights Optimistic Gradient Descent
Closest papers by meaning
- Near-Optimal No-Regret Learning in General Games (NeurIPS 2021 · similarity 0.93)
- Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes (NeurIPS 2019 · similarity 0.93)
- Minimizing Regret on Reflexive Banach Spaces and Nash Equilibria in Continuous Zero-Sum Games (NeurIPS 2016 · similarity 0.92)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.92)
- Best of Both Worlds: Regret Minimization versus Minimax Play (ICML 2025 · similarity 0.91)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.