mlsanityData to 7 Oct 2026

Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback

arXiv 2303.02738 ↗First posted 5 Mar 2023cs.GT cs.LGcited by 28

Not on the map. Why?

Abstract (arXiv)

We revisit the problem of learning in two-player zero-sum Markov games, focusing on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic convergence rates. We start from the case of stateless matrix game with bandit feedback as a warm-up, showing an O(t^-frac18) last-iterate convergence rate. To the best of our knowledge, this is the first result that obtains finite last-iterate convergence rate given access to only bandit feedback. We extend our result to the case of irreducible Markov games, providing a last-iterate convergence rate of O(t^-frac19+varepsilon) for any varepsilon>0. Finally, we study Markov games without any assumptions on the dynamics, and show a path convergence rate, which is a new notion of convergence we defined, of O(t^-frac110). Our algorithm removes the coordination and prior knowledge requirement of [Wei et al., 2021], which pursued the same goals as us for irreducible Markov games. Our algorithm is related to [Chen et al., 2021, Cen et al., 2021] and also builds on the entropy regularization technique. However, we remove their requirement of communications on the entropy values, making our algorithm entirely uncoupled.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). Builds on 37 of its 68 references that are in the map. First posted on arXiv 5 Mar 2023.

Builds on

37 of 68 references.

References · 37

  1. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  2. 2017Cycles in adversarial regularized learningcited by 122
  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 112
  5. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  6. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  7. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  8. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  9. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
  10. 2019On the convergence of single-call stochastic extra-gradient methodscited by 88
  11. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  12. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
25 more
  1. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  2. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  3. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  4. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  5. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  6. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
  7. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  8. 2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
  9. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  10. 2022Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalitiescited by 33
  11. 2018Bandit learning in concave N-person gamescited by 32
  12. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  13. 2020Fictitious play in zero-sum stochastic gamescited by 24
  14. 2022Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescited by 22
  15. 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
  16. 2022Policy Optimization for Markov Games: Unified Framework and Faster Convergencecited by 16
  17. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 14
  18. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 14
  19. 2023Doubly Optimal No-Regret Learning in Monotone Gamescited by 12
  20. 2022O(T-1) Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Gamescited by 11
  21. 2020Online Learning in Unknown Markov Gamescited by 9
  22. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  23. 2021Improved Rates for Derivative Free Gradient Play in Strongly Monotone Gamescited by 6
  24. 2022On the Rate of Convergence of Payoff-based Algorithms to Nash Equilibrium in Strongly Monotone Gamescited by 4
  25. 2023Zeroth-Order Learning in Continuous Games via Residual Pseudogradient Estimatescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 8; 2025: 4; 2026: 10.

28 papers.

Sort:

By area:

  1. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 141
  2. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  3. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  4. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  5. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  6. 2024COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferencescited by 8
  7. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  8. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  9. 2024Approximate Global Convergence of Independent Learning in Multi-Agent Systemscited by 3
  10. 2026Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regretcited by 3
  11. 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 3
  12. 2026Optimal last-iterate convergence in matrix games with bandit feedback using the log-barriercited by 3
16 more
  1. 2026The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedbackcited by 3
  2. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2
  3. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  4. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  5. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2
  6. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 2
  7. 2024Is Thompson Sampling Susceptible to Algorithmic Collusion?cited by 1
  8. 2025Two-Player Zero-Sum Games with Bandit Feedbackcited by 1
  9. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  10. 2024widetildeO(T-1) Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Gamescited by 0
  11. 2024Decentralized Online Learning in General-Sum Stackelberg Gamescited by 0
  12. 2025Randomised Optimism via Competitive Co-Evolution for Matrix Games with Bandit Feedbackcited by 0
  13. 2026Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Gamescited by 0
  14. 2026Matching Multiple Experts: On the Exploitability of Multi-Agent Imitation Learningcited by 0
  15. 2026Minimax Last-Iterate Convergence in Matrix Games with Observed Actionscited by 0
  16. 2026Polylogarithmic Nash Regret in Matrix Games with Bandit Feedbackcited by 0