# Distributed TD(0) with Almost No Communication

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 16 Apr 2021.

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

- [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)
- [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)

## Abstract (arXiv)

We provide a new non-asymptotic analysis of distributed TD(0) with linear function approximation. Our approach relies on "one-shot averaging," where N agents run local copies of TD(0) and average the outcomes only once at the very end. We consider two models: one in which the agents interact with an environment they can observe and whose transitions depends on all of their actions (which we call the global state model), and one in which each agent can run a local copy of an identical Markov Decision Process, which we call the local state model. In the global state model, we show that the convergence rate of our distributed one-shot averaging method matches the known convergence rate of TD(0). By contrast, the best convergence rate in the previous literature showed a rate which, according to the worst-case bounds given, could underperform the non-distributed version by O(N3) in terms of the number of agents N. In the local state model, 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). As far as we are aware, this is the first result rigorously showing benefits from parallelism for temporal difference methods.