# Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

arXiv: https://arxiv.org/abs/2609.34656 · HTML: https://mlsanity.com/paper/2609.34656/

## Key facts

- Cited by 1 papers 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 (most cited first, 20 of 20)

- [Self-Play Preference Optimization for Language Model Alignment](https://mlsanity.com/paper/2405.00675/) (2024)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning](https://mlsanity.com/paper/2407.00617/) (2024)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [Matrix games with bandit feedback](https://mlsanity.com/paper/2006.05145/) (2020)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2502.17625/) (2025)
- [Beyond Pessimism: Offline Learning in KL-regularized Games](https://mlsanity.com/paper/2604.06738/) (2026)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback](https://mlsanity.com/paper/2408.08395/) (2024)
- [Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis](https://mlsanity.com/paper/2409.01447/) (2024)
- [Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier](https://mlsanity.com/paper/2604.15242/) (2026)
- [The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2604.16087/) (2026)
- [Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback](https://mlsanity.com/paper/2602.21436/) (2026)
- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Games](https://mlsanity.com/paper/2407.20128/) (2024)

## Built on by (most cited first, 1 of 1)

- [Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2610.05968/) (2026)

## 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.