Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

• URL: http://arxiv.org/abs/2605.09363v1
• Date: Sun, 10 May 2026 06:23:19 GMT
• Title: Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
• Abstract summary: 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.
• Score: 43.45624707071202
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

Related papers

• The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback [46.50566806285207]
  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.
  arXiv  Detail & Related papers  (2026-04-17T14:17:09Z)
• Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier [39.87105929061084]
  We study the problem of learning minimax policies in zero-sum matrix games.<n>We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t-1/4) convergence with high-probability.
  arXiv  Detail & Related papers  (2026-04-16T17:17:42Z)
• 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)
• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  Non-ergodic convergence of learning dynamics in games is widely studied because of its importance in both theory and practice.<n>Recent work showed that a broad class of learning dynamics, including Optimistic Multiplicative Weights Update, can exhibit arbitrarily slow last-iterate convergence.<n>We show that OMWU achieves an $O(T-1/6)$ best-iterate convergence rate, in stark contrast to its slow last-iterate convergence in the same class of games.
  arXiv  Detail & Related papers  (2025-03-04T17:49:24Z)
• 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)
• Adaptively Perturbed Mirror Descent for Learning in Games [10.868347525353293]
  We propose a payoff perturbation technique for the Mirror Descent (MD) algorithm in games where the gradient of the payoff functions is monotone. We show that our algorithm exhibits significantly accelerated convergence.
  arXiv  Detail & Related papers  (2023-05-26T04:02:54Z)
• No-regret learning for repeated non-cooperative games with lossy bandits [5.437709019435926]
  We study the asynchronous online learning strategy of the players to adaptively adjust the next actions for minimizing the long-term regret loss. The paper provides a novel no-regret learning algorithm, called Online Gradient Descent with lossy bandits (OGD-lb)
  arXiv  Detail & Related papers  (2022-05-14T05:02:56Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  We study last-iterate convergence of optimistic algorithms in sequential games. We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
  arXiv  Detail & Related papers  (2021-06-27T22:02: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.