mlsanityData to 7 Oct 2026

Decentralized Q-Learning in Zero-sum Markov Games

arXiv 2106.02748 ↗First posted 4 Jun 2021cs.GT cs.LG cs.MAcited by 53

Not on the map. Why?

Abstract (arXiv)

We study multi-agent reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). Builds on 23 of its 91 references that are in the map. First posted on arXiv 4 Jun 2021.

Builds on

23 of 91 references.

References · 23

  1. 2015Continuous control with deep reinforcement learningcited by 3,279
  2. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
  4. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  5. 2017StarCraft II: A New Challenge for Reinforcement Learningcited by 268
  6. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 224
  7. 2018A Survey and Critique of Multiagent Deep Reinforcement Learningcited by 173
  8. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  9. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  10. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  11. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  12. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
11 more
  1. 2017A Survey of Learning in Multiagent Environments: Dealing with Non-Stationaritycited by 93
  2. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 91
  3. 2016Learning in games with continuous action sets and unknown payoff functionscited by 78
  4. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  5. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
  6. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  7. 2019Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Gamescited by 38
  8. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
  9. 2020Fictitious play in zero-sum stochastic gamescited by 24
  10. 2020Online Learning in Unknown Markov Gamescited by 9
  11. 2020On Reinforcement Learning for Turn-based Zero-sum Markov Gamescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 14; 2023: 16; 2024: 11; 2025: 2; 2026: 4.

53 papers.

Sort:

By area:

  1. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
  2. 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
  3. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  4. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  5. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  6. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  7. 2022Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Gamescited by 25
  8. 2022Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Gamescited by 24
  9. 2021Independent Learning in Stochastic Gamescited by 20
  10. 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
  11. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  12. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
38 more
  1. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  2. 2023Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learningcited by 12
  3. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  4. 2024Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Gamescited by 11
  5. 2024Independent Learning in Constrained Markov Potential Gamescited by 10
  6. 2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9
  7. 2022Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instrumentscited by 9
  8. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  9. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learningcited by 9
  10. 2022Symmetric (Optimistic) Natural Policy Gradient for Multi-agent Learning with Parameter Convergencecited by 8
  11. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
  12. 2024Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scalecited by 8
  13. 2024Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving O(1/k) Finite-Sample Complexitycited by 7
  14. 2022Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chainscited by 6
  15. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  16. 2023Markov α-Potential Gamescited by 6
  17. 2021Provably Efficient Multi-Agent Reinforcement Learning with Fully Decentralized Communicationcited by 5
  18. 2023Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environmentscited by 5
  19. 2021Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Gamescited by 4
  20. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  21. 2023Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistencecited by 3
  22. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  23. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  24. 2024Finite-Sample Guarantees for Learning Dynamics in Zero-Sum Polymatrix Gamescited by 2
  25. 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Gamescited by 2
  26. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  27. 2022Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximationcited by 1
  28. 2023Logit-Q Dynamics for Efficient Learning in Stochastic Teamscited by 1
  29. 2023Scalable and Independent Learning of Nash Equilibrium Policies in n-Player Stochastic Games with Unknown Independent Chainscited by 1
  30. 2024Risk-Sensitive Multi-Agent Reinforcement Learning in Network Aggregative Markov Gamescited by 1
  31. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  32. 2022Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricingcited by 0
  33. 2023Decentralized model-free reinforcement learning in stochastic games with average-reward objectivecited by 0
  34. 2023Decentralized Multi-Agent Reinforcement Learning for Continuous-Space Stochastic Gamescited by 0
  35. 2023Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processescited by 0
  36. 2024Risk Sensitivity in Markov Games and Multi-Agent Reinforcement Learning: A Systematic Reviewcited by 0
  37. 2024Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Costcited by 0
  38. 2025Nash Equilibrium Between Consumer Electronic Devices and DoS Attacker for Distributed IoT-enabled RSE Systemscited by 0

50 most cited of 53 All 53 (JSON)