mlsanityData to 7 Oct 2026

Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling

arXiv 2305.08104 ↗First posted 14 May 2023cs.LG cs.AI cs.MAcited by 14

Not on the map. Why?

Abstract (arXiv)

Federated learning (FL) has recently gained much attention due to its effectiveness in speeding up supervised learning tasks under communication and privacy constraints. However, whether similar speedups can be established for reinforcement learning remains much less understood theoretically. Towards this direction, we study a federated policy evaluation problem where agents communicate via a central aggregator to expedite the evaluation of a common policy. To capture typical communication constraints in FL, we consider finite capacity up-link channels that can drop packets based on a Bernoulli erasure model. Given this setting, we propose and analyze QFedTD - a quantized federated temporal difference learning algorithm with linear function approximation. Our main technical contribution is to provide a finite-sample analysis of QFedTD that (i) highlights the effect of quantization and erasures on the convergence rate; and (ii) establishes a linear speedup w.r.t. the number of agents under Markovian sampling. Notably, while different quantization mechanisms and packet drop models have been extensively studied in the federated learning, distributed optimization, and networked control systems literature, our work is the first to provide a non-asymptotic analysis of their effects in multi-agent and federated reinforcement learning.

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

Builds on

28 of 42 references.

References · 28

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Towards Federated Learning at Scale: System Designcited by 826
  3. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  4. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  5. 2021Federated Learning Based on Dynamic Regularizationcited by 555
  6. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  7. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  8. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  9. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  10. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
  11. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  12. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
16 more
  1. 2020On Biased Compression for Distributed Learningcited by 140
  2. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  3. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  4. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  5. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  6. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 79
  7. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  8. 2022FedAvg with Fine Tuning: Local Updates Lead to Representation Learningcited by 55
  9. 2018An Exact Quantized Decentralized Gradient Descent Algorithmcited by 34
  10. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 34
  11. 2022Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learningcited by 27
  12. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  13. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  14. 2021Finite-Bit Quantization For Distributed Algorithms With Linear Convergencecited by 15
  15. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  16. 2017Linear Stochastic Approximation: Constant Step-Size and Iterate Averagingcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 6; 2026: 1.

14 papers.

Sort:

  1. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  2. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 6
  3. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  4. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  5. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learningcited by 3
  6. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  7. 2025Convergence of Agnostic Federated Averagingcited by 2
  8. 2025Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learningcited by 2
  9. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  10. 2024Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channelscited by 1
  11. 2024DASA: Delay-Adaptive Multi-Agent Stochastic Approximationcited by 1
  12. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
2 more
  1. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  2. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0