Research map / Optimization / Nonconvex and smooth optimization
From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
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.
Proposes A2L, a black-box reduction that makes the last iterates of a new uncoupled dynamics equal the average iterates of an original dynamics in games with linear utilities, yielding improved last-iterate rates for OMWU in zero-sum polymatrix games under gradient and bandit feedback.
Problem
Achieving fast anytime last-iterate convergence of uncoupled learning dynamics in games, which typically requires problem-specific analysis, especially under bandit feedback.
Approach
Players play the running average of an online learner's iterates and recover the unseen utility vector via u^t = t·ū^t − (t−1)·ū^{t−1}, which is exact under linear utilities; the learner then receives the same utilities as if played alone, so the last iterate of the new dynamics equals the average iterate of the original. Under bandit feedback, a sampling-based utility estimator with epsilon-unifo
Key results
- A2L-OMWU achieves O(log d / T) last-iterate convergence under gradient feedback in zero-sum polymatrix games, versus previous poly(d)/T rates.
- A2L-OMWU-Bandit achieves high-probability Õ(d^{1/5} T^{-1/5}) last-iterate rate under bandit feedback, improving on Õ(sqrt(d) T^{-1/8}) and Õ(sqrt(d) T^{-1/6}).
- The A2L-OMWU dynamics yield O(log d log T) dynamic regret per player.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply A2L to OMWU | OMWU in zero-sum polymatrix games with gradient feedback · Zero-sum polymatrix games, gradient feedback | last-iterate convergence rate: O(\poly(d) / T) -> O(\log d\cdot T^{-1}) | Helped |
| Apply A2L to OMWU | OMWU in zero-sum games · Zero-sum games, gradient feedback | last-iterate convergence rate: O(\frac{\log d \log T}{T}) -> O(\log d\cdot T^{-1}) | Helped |
| Add bandit utility estimation to A2L-OMWU | A2L-OMWU · Zero-sum polymatrix games, bandit feedback | last-iterate convergence rate: \Tilde{O}(T^{-1/8}) -> \Tilde{O}(T^{-1/5}); \Tilde{O}(T^{-1/6}) -> \Tilde{O}(T^{-1/5}) | Helped |
| Use B_t = t^4 instead of B_t = d·t^4 (ablation) | A2L-OMWU-Bandit · Zero-sum polymatrix games, bandit feedback | last-iterate convergence rate: \Tilde{O}(d^{\frac{1}{5}}k^{-\frac{1}{5}}) -> \Tilde{O}(dk^{-\frac{1}{5}}) | Mixed |
| Apply A2L to PRD | PRD in Fisher markets with Gross Substitutes utilities · Fisher markets with Gross Substitutes utilities | last-iterate convergence rate: O(1/T) | Helped |
Surprising findings
- Naive first-order error analysis under bandit feedback gives only T^{-1/7}; a second-order error analysis is needed to reach T^{-1/5}.
- Playing averaged strategies and recovering unseen utilities makes the last iterate of the new dynamics exactly equal the average iterate of the original one.
Limitations
- Reduction requires linear utilities in own strategy and in opponents' joint strategy; does not directly cover concave min-max or general nonlinear games.
- Requires computing and playing running averages, unlike EG/OG which do not average.
- Bandit rate depends on epoch lengths growing as t^4, so sampling cost grows quickly.
Experimental setup
Metrics: total gap (duality gap) last-iterate convergence rate dynamic regret
Baselines: OMWU (average-iterate) accelerated optimistic gradient entropy regularized extragradient mirror-descent bandit last-iterate algorithm (T^{-1/8}/T^{-1/6}) best-response bandit algorithm (T^{-1/8})
Builds on: Optimistic Multiplicative Weights Update anytime online-to-batch regret bounded by variation in utility
Closest papers by meaning
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.95)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.93)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.91)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.91)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.91)
- Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback (ICML 2025 · 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.