mlsanityData to 14 Oct 2026

Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games

arXiv 2112.07859 ↗First posted 15 Dec 2021cs.GT cs.LG cs.MAcited by 4

Not on the map. Why?

Abstract (arXiv)

Learning in stochastic games is arguably the most standard and fundamental setting in multi-agent reinforcement learning (MARL). In this paper, we consider decentralized MARL in stochastic games in the non-asymptotic regime. In particular, we establish the finite-sample complexity of fully decentralized Q-learning algorithms in a significant class of general-sum stochastic games (SGs) - weakly acyclic SGs, which includes the common cooperative MARL setting with an identical reward to all agents (a Markov team problem) as a special case. We focus on the practical while challenging setting of fully decentralized MARL, where neither the rewards nor the actions of other agents can be observed by each agent. In fact, each agent is completely oblivious to the presence of other decision makers. Both the tabular and the linear function approximation cases have been considered. In the tabular setting, we analyze the sample complexity for the decentralized Q-learning algorithm to converge to a Markov perfect equilibrium (Nash equilibrium). With linear function approximation, the results are for convergence to a linear approximated equilibrium - a new notion of equilibrium that we propose - which describes that each agent's policy is a best reply (to other agents) within a linear space. Numerical experiments are also provided for both settings to demonstrate the results.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 30 of its 94 references that are in the map. First posted on arXiv 15 Dec 2021.

Builds on

30 of 94 references.

References · 30

  1. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  2. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  3. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  4. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 109
  5. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  6. 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 101
  7. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  8. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  9. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  10. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  11. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  12. 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 69
18 more
  1. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  2. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  3. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  4. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  5. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  6. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  7. 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 35
  8. 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 32
  9. 2019Feature-Based Q-Learning for Two-Player Stochastic Gamescited by 24
  10. 2019A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithmscited by 15
  11. 2016Nash Social Welfare Approximation for Strategic Agentscited by 9
  12. 2020Online Learning in Unknown Markov Gamescited by 9
  13. 2017Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimizationcited by 5
  14. 2020Inducing Equilibria in Networked Public Goods Games through Network Structure Modificationcited by 5
  15. 2020Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Boundscited by 4
  16. 2018Fast Algorithms for Rank-1 Bimatrix Gamescited by 2
  17. 2020The Efficiency of Best-Response Dynamicscited by 1
  18. 2021Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chorescited by 1

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2.

4 papers.

  1. 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
  2. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  3. 2022Task Oriented Video Coding: A Surveycited by 3
  4. 2023Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Gamescited by 2