mlsanityData to 14 Oct 2026

A finite time analysis of distributed Q-learning

arXiv 2405.14078 ↗First posted 23 May 2024cs.AI cs.LG cs.MAcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Multi-agent reinforcement learning (MARL) has witnessed a remarkable surge in interest, fueled by the empirical success achieved in applications of single-agent reinforcement learning (RL). In this study, we consider a distributed Q-learning scenario, wherein a number of agents cooperatively solve a sequential decision making problem without access to the central reward function which is an average of the local rewards. In particular, we study finite-time analysis of a distributed Q-learning algorithm, and provide a new sample complexity result of tildeOleft( minleftfrac1ε2fractmix(1-γ)6 dmin4 ,frac1εfrac√|gS||gA|(1-σ2(boldsymbolW))(1-γ)4 dmin3 rightright) under tabular lookup

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 31 of its 62 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

31 of 62 references.

References · 31

  1. 2017Value-Decomposition Networks For Cooperative Multi-Agent Learningcited by 503
  2. 2020Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 485
  3. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 311
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  5. 2018Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agentscited by 194
  6. 2018Distributed Stochastic Gradient Tracking Methodscited by 106
  7. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  8. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  9. 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 93
  10. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  11. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  12. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
19 more
  1. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  2. 2020Multi-Agent Reinforcement Learning in Stochastic Networked Systemscited by 32
  3. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 28
  4. 2019Scalable Reinforcement Learning for Multi-Agent Networked Systemscited by 24
  5. 2019A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learningcited by 21
  6. 2022Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learningcited by 20
  7. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  8. 2013Distributed Policy Evaluation Under Multiple Behavior Strategiescited by 17
  9. 2021A Discrete-Time Switching System Analysis of Q-learningcited by 16
  10. 2019Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximationcited by 15
  11. 2019Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensuscited by 11
  12. 2021A Framework for Real-World Multi-Robot Systems Running Decentralized GNN-Based Policiescited by 11
  13. 2020Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learningcited by 10
  14. 2013Distributed Reinforcement Learning via Gossipcited by 9
  15. 2018Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTDcited by 8
  16. 2021Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guaranteescited by 6
  17. 2022Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learningcited by 6
  18. 2014Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Controlcited by 3
  19. 2023A primal-dual perspective for distributed TD-learningcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Variance-Reduced Q-Learning over Static and Time-Varying Networkscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  2. 2026Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games
  3. 2024Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning
  4. 2026Fully Byzantine-Resilient Distributed Multi-Agent Q-Learning
  5. 2024Mixed Q-Functionals: Advancing Value-Based Methods in Cooperative MARL with Continuous Action Domains
  6. 2025Distributed Value Decomposition Networks with Networked Agents
  7. 2024Mitigating Relative Over-Generalization in Multi-Agent Reinforcement Learning
  8. 2024On Convergence of Average-Reward Q-Learning in Weakly Communicating Markov Decision Processes