mlsanityData to 14 Oct 2026

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

arXiv 2609.34656 ↗First posted 28 Sep 2026cs.LG cs.GTcited by 1

Not on the map. Why?

Abstract (arXiv)

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with d actions per player, we develop an algorithm achieving a duality gap of widetildeO(√d/t) with high probability, simultaneously at every round t. This improves the dimension dependence of the best previously known guarantee by a factor of d3/2. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only O(d) time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 20 of its 26 references that are in the map. First posted on arXiv 28 Sep 2026.

Builds on

20 of 26 references.

References · 20

  1. 2024Self-Play Preference Optimization for Language Model Alignmentcited by 232
  2. 2023Nash Learning from Human Feedbackcited by 224
  3. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  4. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  5. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  6. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  7. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
  8. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  9. 2020Matrix games with bandit feedbackcited by 16
  10. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 14
  11. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 10
  12. 2026Beyond Pessimism: Offline Learning in KL-regularized Gamescited by 10
8 more
  1. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  2. 2024Uncoupled and Convergent Learning in Monotone Games under Bandit Feedbackcited by 6
  3. 2024Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysiscited by 6
  4. 2026Optimal last-iterate convergence in matrix games with bandit feedback using the log-barriercited by 5
  5. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
  6. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 4
  7. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
  8. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedbackcited by 0