# Distributed TD(0) with Almost No Communication

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 25 May 2023.

## Builds on (most cited first, 13 of 13)

- [Benchmarking Deep Reinforcement Learning for Continuous Control](https://mlsanity.com/paper/1604.06778/) (2016)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising](https://mlsanity.com/paper/1802.09756/) (2018)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning](https://mlsanity.com/paper/2206.10185/) (2022)
- [Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup](https://mlsanity.com/paper/2012.15511/) (2020)
- [Temporal Difference Learning as Gradient Splitting](https://mlsanity.com/paper/2010.14657/) (2020)
- [Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness](https://mlsanity.com/paper/2003.10973/) (2020)
- [Approximate Temporal Difference Learning is a Gradient Descent for Reversible Policies](https://mlsanity.com/paper/1805.00869/) (2018)
- [Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1911.00934/) (2019)
- [Optimal Lockdown for Pandemic Control](https://mlsanity.com/paper/2010.12923/) (2020)
- [Single-Bit Consensus with Finite-Time Convergence: Theory and Applications](https://mlsanity.com/paper/2001.00141/) (2020)

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

- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2402.04114/) (2024)
- [One-Shot Averaging for Distributed TD(λ) Under Markov Sampling](https://mlsanity.com/paper/2403.08896/) (2024)
- [Towards Fast Rates for Federated and Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2409.05291/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning](https://mlsanity.com/paper/2508.05984/) (2025)
- [Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments](https://mlsanity.com/paper/2510.07436/) (2025)
- [Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices](https://mlsanity.com/paper/2610.05915/) (2026)
- [Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning](https://mlsanity.com/paper/2610.06918/) (2026)

## Abstract (arXiv)

We provide a new non-asymptotic analysis of distributed temporal difference learning with linear function approximation. Our approach relies on ``one-shot averaging,'' where N agents run identical local copies of the TD(0) method and average the outcomes only once at the very end. We demonstrate a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of N faster than the convergence time of TD(0). This is the first result proving benefits from parallelism for temporal difference methods.