mlsanityData to 7 Oct 2026

Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity

arXiv 2302.02212 ↗First posted 4 Feb 2023cs.LG math.OCcited by 25

Not on the map. Why?

Abstract (arXiv)

We initiate the study of federated reinforcement learning under environmental heterogeneity by considering a policy evaluation problem. Our setup involves N agents interacting with environments that share the same state and action space but differ in their reward functions and state transition kernels. Assuming agents can communicate via a central server, we ask: Does exchanging information expedite the process of evaluating a common policy? To answer this question, we provide the first comprehensive finite-time analysis of a federated temporal difference (TD) learning algorithm with linear function approximation, while accounting for Markovian sampling, heterogeneity in the agents' environments, and multiple local updates to save communication. Our analysis crucially relies on several novel ingredients: (i) deriving perturbation bounds on TD fixed points as a function of the heterogeneity in the agents' underlying Markov decision processes (MDPs); (ii) introducing a virtual MDP to closely approximate the dynamics of the federated TD algorithm; and (iii) using the virtual MDP to make explicit connections to federated optimization. Putting these pieces together, we rigorously prove that in a low-heterogeneity regime, exchanging model estimates leads to linear convergence speedups in the number of agents.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 36 of its 52 references that are in the map. First posted on arXiv 4 Feb 2023.

Builds on

36 of 52 references.

References · 36

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2020Personalized Federated Learning with Moreau Envelopescited by 612
  3. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  4. 2021Exploiting Shared Representations for Personalized Federated Learningcited by 537
  5. 2020An Efficient Framework for Clustered Federated Learningcited by 505
  6. 2019Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraintscited by 499
  7. 2021Towards Personalized Federated Learningcited by 462
  8. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
  9. 2020Personalized Federated Learning: A Meta-Learning Approachcited by 309
  10. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  11. 2015DeepDriving: Learning Affordance for Direct Perception in Autonomous Drivingcited by 229
  12. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
24 more
  1. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  2. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  3. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  4. 2020Lower Bounds and Optimal Algorithms for Personalized Federated Learningcited by 122
  5. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  6. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  7. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  8. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
  9. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  10. 2018In-Edge AI: Intelligentizing Mobile Edge Computing, Caching and Communication by Federated Learningcited by 80
  11. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  12. 2019Lifelong Federated Reinforcement Learning: A Learning Architecture for Navigation in Cloud Robotic Systemscited by 77
  13. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  14. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 61
  15. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
  16. 2022FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participationcited by 35
  17. 2020On the Outsized Importance of Learning Rates in Local Update Methodscited by 34
  18. 2022Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learningcited by 27
  19. 2020Temporal Difference Learning as Gradient Splittingcited by 21
  20. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 20
  21. 2020Local SGD With a Communication Overhead Depending Only on the Number of Workerscited by 13
  22. 2017Linear Stochastic Approximation: Constant Step-Size and Iterate Averagingcited by 7
  23. 2022Global Convergence of Federated Learning for Mixed Regressioncited by 6
  24. 2022Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraintscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 17; 2025: 3; 2026: 3.

25 papers.

Sort:

By area:

  1. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  2. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  3. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 20
  4. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 15
  5. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 14
  6. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  7. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  8. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 7
  9. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  10. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 6
  11. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  12. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
13 more
  1. 2025FOVA: Offline Federated Reinforcement Learning with Mixed-Quality Datacited by 5
  2. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 4
  3. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  4. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learningcited by 3
  5. 2024On the Convergence Rates of Federated Q-Learning across Heterogeneous Environmentscited by 2
  6. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  7. 2024DASA: Delay-Adaptive Multi-Agent Stochastic Approximationcited by 1
  8. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  9. 2025Personalized Collaborative Learning with Affinity-Based Variance Reductioncited by 1
  10. 2024Single-Loop Federated Actor-Critic across Heterogeneous Environmentscited by 0
  11. 2026Variance-Reduced Q-Learning over Static and Time-Varying Networkscited by 0
  12. 2026Robust Federated Q-Learning with Almost No Communicationcited by 0
  13. 2026Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Alwayscited by 0