mlsanityData to 7 Oct 2026

Distributed TD(0) with Almost No Communication

arXiv 2305.16246 ↗First posted 25 May 2023cs.LG cs.SY eess.SYcited by 11

Not on the map. Why?

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.

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

Builds on

13 of 35 references.

References · 13

  1. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 361
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  3. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  4. 2018Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertisingcited by 65
  5. 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
  6. 2022Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learningcited by 27
  7. 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 23
  8. 2020Temporal Difference Learning as Gradient Splittingcited by 21
  9. 2020Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomnesscited by 18
  10. 2018Approximate Temporal Difference Learning is a Gradient Descent for Reversible Policiescited by 10
  11. 2019Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximationcited by 9
  12. 2020Optimal Lockdown for Pandemic Controlcited by 7
1 more
  1. 2020Single-Bit Consensus with Finite-Time Convergence: Theory and Applicationscited by 6

Built on by

Cited by year

Citing papers per year: 2024: 5; 2025: 6.

11 papers.

  1. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  2. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  3. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  4. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 4
  5. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  6. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learningcited by 3
  7. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  8. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  9. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  10. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  11. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1