mlsanityData to 14 Oct 2026

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

arXiv 2604.15242 ↗First posted 16 Apr 2026cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 4 of its 15 references that are in the map. First posted on arXiv 16 Apr 2026.

Builds on

4 of 15 references.

References · 4

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  2. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
  3. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  4. 2018Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Gamescited by 11

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