# The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

arXiv: https://arxiv.org/abs/2604.16087 · HTML: https://mlsanity.com/paper/2604.16087/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 17 Apr 2026.

## Builds on (most cited first, 18 of 18)

- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall](https://mlsanity.com/paper/2106.06279/) (2021)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities](https://mlsanity.com/paper/2107.01906/) (2021)
- [Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Games](https://mlsanity.com/paper/1802.04221/) (2018)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Improved Rates for Derivative Free Gradient Play in Strongly Monotone Games](https://mlsanity.com/paper/2111.09456/) (2021)
- [Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback](https://mlsanity.com/paper/2408.08395/) (2024)
- [On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Games](https://mlsanity.com/paper/2202.11147/) (2022)
- [Zeroth-Order Learning in Continuous Games via Residual Pseudogradient Estimates](https://mlsanity.com/paper/2301.02279/) (2023)
- [On the Impossibility of Convergence of Mixed Strategies with No Regret Learning](https://mlsanity.com/paper/2012.02125/) (2020)

## Built on by (most cited first, 5 of 5)

- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [Minimax Last-Iterate Convergence in Matrix Games with Observed Actions](https://mlsanity.com/paper/2609.34656/) (2026)
- [Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2609.34812/) (2026)
- [Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2610.05968/) (2026)
- [Thompson Sampling for Learning in Zero-Sum Games](https://mlsanity.com/paper/2610.18899/) (2026)

## Abstract (arXiv)

We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of O(T-1/8) on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being Omega(T-1/4) in contrast to the usual Omega(T-1/2) rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.