# Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents

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

## 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 (most cited first, 30 of 32)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings](https://mlsanity.com/paper/2210.04620/) (2022)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Federated Reinforcement Learning: Techniques, Applications, and Open Challenges](https://mlsanity.com/paper/2108.11887/) (2021)
- [Federated Reinforcement Learning with Environment Heterogeneity](https://mlsanity.com/paper/2204.02634/) (2022)
- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Federated Deep Reinforcement Learning](https://mlsanity.com/paper/1901.08277/) (2019)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updates](https://mlsanity.com/paper/2310.19807/) (2023)
- [Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis](https://mlsanity.com/paper/2404.08003/) (2024)
- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Federated Q-Learning: Linear Regret Speedup with Low Communication Cost](https://mlsanity.com/paper/2312.15023/) (2023)
- [On the Convergence of SARSA with Linear Function Approximation](https://mlsanity.com/paper/2202.06828/) (2022)
- [Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling](https://mlsanity.com/paper/2305.08104/) (2023)
- [Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation](https://mlsanity.com/paper/2106.07472/) (2021)
- [Off-policy Learning with Eligibility Traces: A Survey](https://mlsanity.com/paper/1304.3999/) (2013)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning](https://mlsanity.com/paper/2311.00201/) (2023)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments](https://mlsanity.com/paper/2405.19499/) (2024)
- [SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2402.04114/) (2024)
- [Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents](https://mlsanity.com/paper/2410.22908/) (2024)
- [One-Shot Averaging for Distributed TD(λ) Under Markov Sampling](https://mlsanity.com/paper/2403.08896/) (2024)
- [Towards Fast Rates for Federated and Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2409.05291/) (2024)
- [On Global Convergence Rates for Federated Softmax Policy Gradient under Heterogeneous Environments](https://mlsanity.com/paper/2505.23459/) (2025)

## Built on by (most cited first, 2 of 2)

- [Trapped by Their Own Rollouts: Understanding Aggregation--Rollout Feedback in Federated On-Policy Distillation](https://mlsanity.com/paper/2609.32573/) (2026)
- [Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always](https://mlsanity.com/paper/2610.11555/) (2026)

## 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.