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

• URL: http://arxiv.org/abs/2604.16087v1
• Date: Fri, 17 Apr 2026 14:17:09 GMT
• Title: The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
• Abstract summary: We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback.<n>We propose uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium.
• Score: 46.50566806285207
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\mathcal{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 $Ω(T^{-1/4})$ in contrast to the usual $Ω(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.

Related papers

• Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities [8.350639529216876]
  This algorithm is single-loop and single-call since it uses one unbiased sample of the operator at every iteration to be applicable to monotone games with noisy feedback.<n>We prove the anytime last-iterate convergence rate of $O(t-1/4)$ for both gradient-mapping norm and restricted gap.
  arXiv  Detail & Related papers  (2026-09-14T09:17:23Z)
• Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions [43.45624707071202]
  Last-iterate convergence of learning dynamics in games has attracted significant recent attention.<n>We show that t(-1/2) last-iterate convergence is achievable with high probability in games with bandit feedback.
  arXiv  Detail & Related papers  (2026-05-10T06:23:19Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  We show that alternating RM$+$ converges to an $epsilon$-KKT point after $O_epsilon (1/epsilon4)$, establishing for the first time that it is a sound and fast first-order.<n>Our lower bound shows that convergence to coarse correlated equilibria in potential games is exponentially faster than convergence to Nash equilibria.
  arXiv  Detail & Related papers  (2025-10-20T00:45:47Z)
• From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications [54.49053278073321]
  We show that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics.<n>Our reduction applies to games where each player's utility is linear in both their own strategy and the joint strategy of all opponents.
  arXiv  Detail & Related papers  (2025-06-04T00:24:14Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret$+$ (RM$+$)<n>Our analysis builds on a new characterization of the geometric structure of the limit points of our algorithms, marking a significant departure from most of the literature on last-iterate convergence.
  arXiv  Detail & Related papers  (2023-11-01T17:34:58Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  Online gradient descent (OGD) is well known to be doubly optimal under strong convexity or monotonicity assumptions. In this paper, we design a fully adaptive OGD algorithm, textsfAdaOGD, that does not require a priori knowledge of these parameters.
  arXiv  Detail & Related papers  (2023-10-21T18:38:13Z)
• Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
  We study decentralized learning in two-player zero-sum discounted Markov games. The goal is to design a policy optimization algorithm for either agent satisfying two properties.
  arXiv  Detail & Related papers  (2023-03-03T02:40:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.