Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback
Not on the map. Why?
Abstract (arXiv)
We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a widetildeO(t-1/4) duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the widetildeO(t-1/(9+nu)) rate of Cai et al. (2023), for any fixed nu>0, under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 24 of its 28 references that are in the map. First posted on arXiv 5 Oct 2026.
Builds on
24 of 28 references.
References · 24
- 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
- 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
- 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
- 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
- 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
- 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
- 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 60
- 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
- 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
- 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 30
12 more
- 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 28
- 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 26
- 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
- 2023Offline Learning in Markov Games with General Function Approximationcited by 18
- 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
- 2024Uncoupled and Convergent Learning in Monotone Games under Bandit Feedbackcited by 6
- 2024Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysiscited by 6
- 2026Optimal last-iterate convergence in matrix games with bandit feedback using the log-barriercited by 5
- 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 5
- 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
- 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 4
- 2026Minimax Last-Iterate Convergence in Matrix Games with Observed Actionscited by 1
Built on by
Not cited yet.