Research map / Bandits and online learning / Online convex optimization and games
No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests
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 continuous-time FTRL is Poincaré recurrent in all harmonic games, and that an extrapolated FTRL (FTRL+) achieves O(1) regret and converges to Nash equilibrium from any initial condition in discrete time.
Problem
Long-run behavior of no-regret learning (FTRL) in harmonic games, the strategic complement of potential games where players have conflicting interests, which is poorly understood beyond two-player zero-sum games with fully-mixed equilibria.
Approach
Proves Poincaré recurrence of continuous-time FTRL in all harmonic games via a constant of motion derived from a volume-preserving flow in payoff space (generalizing the Shahshahani-metric approach), and introduces FTRL+, a flexible extrapolated FTRL template (covering optimistic, extra-gradient, mirror-prox), which achieves constant regret and convergence to Nash equilibrium in harmonic games.
Key results
- Continuous-time FTRL is Poincaré recurrent in all harmonic games (almost every orbit returns arbitrarily close to its start infinitely often).
- Under FTRL+ with suitable learning rates, each player's individual regret is bounded by a constant independent of the horizon T.
- Under FTRL+, the base state converges to the set of Nash equilibria of any harmonic game from any initial condition, while vanilla FTRL diverges in Matching Pennies.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add an extrapolation step to FTRL | FTRL in harmonic games · Harmonic games, discrete time | convergence to Nash equilibrium | Helped |
| Add an extrapolation step to FTRL | FTRL in harmonic games · Harmonic games, discrete time | individual regret | Helped |
| Use continuous-time FTRL | FTRL in harmonic games · Harmonic games, continuous time | Poincaré recurrence | Hurt |
| Use vanilla FTRL without extrapolation | FTRL in Matching Pennies · Matching Pennies | distance from Nash equilibrium | Hurt |
| Use vanilla FTRL without extrapolation | FTRL in harmonic games · Harmonic games, discrete time | convergence to Nash equilibrium | Hurt |
Surprising findings
- Vanilla discrete-time FTRL can spiral away from equilibrium and get trapped in a cycle of best responses, even in Matching Pennies.
Limitations
- Learning rates must satisfy a bound depending on game parameters (Lipschitz moduli, harmonic measure), so the algorithms are not adaptive.
- Convergence rate to Nash equilibrium is left open (only conjectured linear).
- Analysis assumes full information about mixed payoff vectors; bandit/payoff-based feedback is not covered.
Experimental setup
Metrics: regret convergence to Nash equilibrium Poincaré recurrence
Baselines: vanilla FTRL replicator dynamics
Builds on: follow-the-regularized-leader optimistic gradient extra-gradient mirror-prox harmonic games
Closest papers by meaning
- Adapting to Conflict: Equilibrium Structure and Adaptive Learning in Harmonic Games (NeurIPS 2026 · similarity 0.94)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.92)
- Optimism Without Regularization: Constant Regret in Zero-Sum Games (NeurIPS 2025 · similarity 0.92)
- No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.91)
- Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.90)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.90)
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.