Research map / Optimization / Nonconvex and smooth optimization
Accelerated Regularized Learning in Finite N-Person 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.
Introduces "follow the accelerated leader" (FTXL), a Nesterov-style momentum version of regularized learning (FTRL/exponential weights) in finite games, proving superlinear local convergence to strict Nash equilibria under full, realization-based, and bandit feedback.
Problem
Regularized learning in games (FTRL, exponential weights) converges to strict Nash equilibria only at a geometric (linear) rate, and it is unknown whether Nesterov-style acceleration can be carried over to game-theoretic online learning.
Approach
Apply the continuous-time heavy-ball-with-vanishing-friction view of Nesterov's method to the score variables of FTRL, giving a second-order (payoff-momentum) learning scheme; with zero friction it is a discrete momentum update on scores whose mirror map gives strategies, achieving superlinear convergence to strict equilibria across feedback models.
Key results
- Continuous-time FTXL with logit best responses satisfies sup-norm distance to a strict NE bounded by exp(C - c t^2 / (2(γ+1))), a superlinear rate versus geometric rate for replicator dynamics.
- Discrete-time FTXL with full information achieves exp(C - c η² N(N-1)/2) = exp(-Θ(N²)) local convergence to strict NE.
- Superlinear rate is maintained with realization-based and bandit (importance-weighted) feedback with high probability, with degraded subleading terms (exponent 5/3 and 9/5 respectively).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FTXL instead of first-order regularized learning | Learning near strict Nash equilibria · Strict Nash equilibria | convergence rate: \exp(-\Theta(\nRuns)) -> \exp \parens[\big]{-\Theta(\cramped{\nRuns^{2}})} | Helped |
| Use FTXL with full-information feedback | FTXL · Strict Nash equilibria, full information | strategy error bound: \exp(-\Theta(\nRuns)) -> \exp \parens[\big]{-\Theta(\cramped{\nRuns^{2}})} | Helped |
| Use FTXL with realization-based feedback | FTXL · Strict Nash equilibria, realization-based feedback | strategy error bound: \exp \parens[\big]{-\Theta(\cramped{\nRuns^{2}})} | Helped |
| Use FTXL with bandit payoff feedback | FTXL · Strict Nash equilibria, bandit feedback | strategy error bound: \exp \parens[\big]{-\Theta(\cramped{\nRuns^{2}})} | Helped |
| Use bandit feedback instead of realization-based feedback | FTXL · Zero-sum and congestion games | convergence performance | Hurt |
| Use non-vanishing friction instead of zero friction (ablation) | FTXL · Single-player, two-action strict Nash game | strategy error decay rate: \sim \exp\parens*{\Const - \frac{\step^2\horizon^2}{2(\step\fr+1)}}; \sim \exp\parens*{\Const - \frac{\step}{\fr}\run} | Hurt |
| Use positive vanishing friction instead of zero friction (ablation) | Continuous-time FTXL · Strict Nash equilibria | convergence rate: \exp\parens*{\Const - \frac{\const\draft{t}^{2}}{2(\fr+1)}} | Hurt |
Surprising findings
- Zero friction is optimal among the vanishing-friction schemes studied; adding friction hinders the equilibrium convergence rate.
- Superlinear convergence is retained even under bandit payoff-based feedback, despite the method being second-order in time rather than space.
Limitations
- Results are local: finite games can have multiple strict equilibria, so only local convergence to strict NE is established.
- Bandit feedback introduces a bias-variance trade-off via explicit exploration, and the subleading term worsens with less information.
- Numerical validation is limited to a small 2-player zero-sum game and a 100-player congestion game.
Experimental setup
Metrics: distance to strict Nash equilibrium convergence rate
Baselines: FTRL / exponential weights replicator dynamics
Builds on: Nesterov's accelerated gradient follow the regularized leader replicator dynamics heavy ball with vanishing friction
Closest papers by meaning
- On the Rate of Convergence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Beyond (NeurIPS 2021 · similarity 0.93)
- (Doubly) Exponential Lower Bounds for Follow the Regularized Leader in Potential Games (ICML 2026 · similarity 0.91)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.91)
- The Equivalence of Dynamic and Strategic Stability under Regularized Learning in Games (NeurIPS 2023 · similarity 0.90)
- Learning from Delayed Feedback in Games via Extra Prediction (NeurIPS 2025 · similarity 0.89)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.89)
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.