Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

• URL: http://arxiv.org/abs/2604.15242v1
• Date: Thu, 16 Apr 2026 17:17:42 GMT
• Title: Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
• Abstract summary: 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.
• Score: 39.87105929061084
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. 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. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.

Related papers

• 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)
• 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)
• 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)
• Is Thompson Sampling Susceptible to Algorithmic Collusion? [7.398059199829556]
  We show that when the players use Thompson sampling, the game dynamics converge to the Nash equilibrium.<n>We show that algorithmic collusion doesn't arise in this case despite the fact that the players do not intentionally deploy competitive strategies.
  arXiv  Detail & Related papers  (2024-05-23T08:21:48Z)
• 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)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  We focus on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic convergence rates. Our algorithm is related to [Chen et al., 2021, Cen et al., 2021] and also builds on the entropy regularization technique.
  arXiv  Detail & Related papers  (2023-03-05T18:08: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.