mlsanityData to 14 Oct 2026

Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents

arXiv 2512.17688 ↗First posted 19 Dec 2025cs.LG stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

We present a novel theoretical analysis of Federated SARSA (FedSARSA) with linear function approximation and local training. We establish convergence guarantees for FedSARSA in the presence of heterogeneity, both in local transitions and rewards, providing the first sample and communication complexity bounds in this setting. At the core of our analysis is a new, exact multi-step error expansion for single-agent SARSA, which is of independent interest. Our analysis precisely quantifies the impact of heterogeneity, demonstrating the convergence of FedSARSA with multiple local updates. Crucially, we show that FedSARSA achieves linear speed-up with respect to the number of agents, up to higher-order terms due to Markovian sampling. Numerical experiments support our theoretical findings.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 32 of its 55 references that are in the map. First posted on arXiv 19 Dec 2025.

Builds on

32 of 55 references.

References · 32

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  5. 2022FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settingscited by 125
  6. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  7. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
  8. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  9. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 81
  10. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 63
  11. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  12. 2019Federated Deep Reinforcement Learningcited by 35
20 more
  1. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 31
  2. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 21
  3. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  4. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  5. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  6. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  7. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 15
  8. 2021Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximationcited by 14
  9. 2013Off-policy Learning with Eligibility Traces: A Surveycited by 12
  10. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  11. 2023Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learningcited by 11
  12. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 9
  13. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 8
  14. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
  15. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 6
  16. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 5
  17. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learningcited by 4
  18. 2025On Global Convergence Rates for Federated Softmax Policy Gradient under Heterogeneous Environmentscited by 3
  19. 2024Decentralized Federated Policy Gradient with Byzantine Fault-Tolerance and Provably Fast Convergencecited by 2
  20. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Trapped by Their Own Rollouts: Understanding Aggregation--Rollout Feedback in Federated On-Policy Distillationcited by 0
  2. 2026Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Alwayscited by 0