Research map / Bandits and online learning / Online convex optimization and games
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
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 uncoupled last-iterate convergence under bandit feedback in zero-sum matrix games is harder (Omega(T^{-1/4}) for L2 rather than T^{-1/2}), and proposes an explore-exploit wrapper and a regularized EXP3 with a doubling trick that match the rate up to log factors.
Problem
Last-iterate convergence to Nash equilibrium for uncoupled learning in zero-sum matrix games with bandit feedback, where the best known rate was O(T^{-1/8}) on exploitability gap.
Approach
Proves a lower bound showing that last-iterate guarantees for uncoupled bandit learners are strictly harder than average-iterate guarantees, then matches it with (i) a synchronized explore-or-exploit wrapper around an anytime regret-based algorithm and (ii) a two-step KL-regularized EXP3 whose regularization is tuned to T, made anytime via a doubling trick with a shared seed.
Key results
- Lower bound: no uncoupled bandit learner can achieve L^p last-iterate rate better than Omega(T^{-1/(2+p)}) for p in (0,2], versus O(T^{-1/2}) for average iterates.
- Explore-or-exploit wrapper around EXP3-IX attains tilde-O(T^{-1/(2+p)}) L^p last-iterate rate for p in (0,2].
- Regularized EXP3 with tau ~ T^{-1/4} attains L^2 exploitability gap O(T^{-1/4} sqrt(log)) at the fixed horizon T; the doubling-trick variant gives anytime O((A+B)/t)^{1/4} rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require last-iterate convergence rather than convergence of the average iterates | uncoupled learning with bandit feedback · Zero-sum matrix games | exploitability gap convergence rate: \Omega(T^{-1/4}) vs. \Omega(T^{-1/2}) | Hurt |
| Use EOE to transform an anytime regret-based algorithm into a last-iterate algorithm | EXP3 · Zero-sum matrix games, L^p last-iterate (p in (0,2]) | exploitability gap convergence rate: \tcO(T^{-1/(2+p)}) | Helped |
| Use strong regularization and unbiased bandit loss estimates | Regularized EXP3 · Zero-sum matrix games, L^2 last-iterate | exploitability gap convergence rate: \cO(T^{-1/4}) | Helped |
| Apply a doubling trick that trades off between the old and new instances | Regularized EXP3 · Zero-sum matrix games, L^2 last-iterate | exploitability gap convergence rate: \tcO(T^{-1/4}) | Helped |
| Use horizon-dependent regularization | Regularized EXP3 · Zero-sum matrix games, L^2 last-iterate over the full sequence | exploitability gap convergence rate: f^t\asymp \min\pa{1,\frac{T^{1/4}}{t^{1/2}}} | Hurt |
Surprising findings
- Guaranteeing last-iterate convergence of policy profiles is provably harder for uncoupled bandit learners than average-iterate convergence (T^{-1/4} vs T^{-1/2} for L2).
Limitations
- Explore-or-exploit wrapper requires shared random seed between players and computing averages at nearly every iteration.
- Regularized algorithm needs horizon-dependent regularization; anytime version requires doubling trick with synchronization.
- Lower bound for p>2 is loose and only conjectured tight.
Experimental setup
Metrics: L^p norm of exploitability gap
Baselines: EXP3-IX-based last-iterate method (O(T^{-1/8})) Mirror descent with regularized pseudo-gradient
Builds on: EXP3 EXP3-IX Optimistic Mirror Descent
Closest papers by meaning
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.93)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.91)
- Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback (NeurIPS 2025 · similarity 0.91)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.91)
- Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback (ICML 2025 · similarity 0.91)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 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.