# A finite time analysis of distributed Q-learning

arXiv: https://arxiv.org/abs/2405.14078 · HTML: https://mlsanity.com/paper/2405.14078/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, 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.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 30 of 31)

- [Value-Decomposition Networks For Cooperative Multi-Agent Learning](https://mlsanity.com/paper/1706.05296/) (2017)
- [Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2003.08839/) (2020)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents](https://mlsanity.com/paper/1802.08757/) (2018)
- [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Multi-Agent Reinforcement Learning in Stochastic Networked Systems](https://mlsanity.com/paper/2006.06555/) (2020)
- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Scalable Reinforcement Learning for Multi-Agent Networked Systems](https://mlsanity.com/paper/1912.02906/) (2019)
- [A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning](https://mlsanity.com/paper/1903.06372/) (2019)
- [Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.17116/) (2022)
- [Federated Q-Learning: Linear Regret Speedup with Low Communication Cost](https://mlsanity.com/paper/2312.15023/) (2023)
- [Distributed Policy Evaluation Under Multiple Behavior Strategies](https://mlsanity.com/paper/1312.7606/) (2013)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensus](https://mlsanity.com/paper/1903.09255/) (2019)
- [A Framework for Real-World Multi-Robot Systems Running Decentralized GNN-Based Policies](https://mlsanity.com/paper/2111.01777/) (2021)
- [Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learning](https://mlsanity.com/paper/2010.15088/) (2020)
- [Distributed Reinforcement Learning via Gossip](https://mlsanity.com/paper/1310.7610/) (2013)
- [Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD](https://mlsanity.com/paper/1803.08031/) (2018)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Understanding Value Decomposition Algorithms in Deep Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2202.04868/) (2022)
- [Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control](https://mlsanity.com/paper/1411.4186/) (2014)

## Built on by (most cited first, 1 of 1)

- [Variance-Reduced Q-Learning over Static and Time-Varying Networks](https://mlsanity.com/paper/2607.21876/) (2026)

## 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