mlsanityData to 14 Oct 2026

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

arXiv 2604.16087 ↗First posted 17 Apr 2026cs.LG stat.MLcited by 5

Not on the map. Why?

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.

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

18 of 42 references.

References · 18

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  2. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  3. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  4. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  5. 2018Bandit learning in concave N-person gamescited by 35
  6. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  7. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  8. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  9. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  10. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  11. 2021The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalitiescited by 12
  12. 2018Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Gamescited by 11
6 more
  1. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  2. 2021Improved Rates for Derivative Free Gradient Play in Strongly Monotone Gamescited by 7
  3. 2024Uncoupled and Convergent Learning in Monotone Games under Bandit Feedbackcited by 6
  4. 2022On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Gamescited by 4
  5. 2023Zeroth-Order Learning in Continuous Games via Residual Pseudogradient Estimatescited by 3
  6. 2020On the Impossibility of Convergence of Mixed Strategies with No Regret Learningcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 5.

5 papers.

  1. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  2. 2026Minimax Last-Iterate Convergence in Matrix Games with Observed Actionscited by 1
  3. 2026Polylogarithmic Nash Regret in Matrix Games with Bandit Feedbackcited by 0
  4. 2026Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedbackcited by 0
  5. 2026Thompson Sampling for Learning in Zero-Sum Gamescited by 0