# Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Placed in RL for energy, networks and operations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 31 of its 56 references that are in the map.
- First posted on arXiv 27 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [RL for energy, networks and operations](https://mlsanity.com/deeprl/rl-for-energy-networks-and-operations/)

## Builds on (most cited first, 30 of 31)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [FedSplit: An algorithmic framework for fast federated optimization](https://mlsanity.com/paper/2005.05238/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Federated Reinforcement Learning: Techniques, Applications, and Open Challenges](https://mlsanity.com/paper/2108.11887/) (2021)
- [In-Edge AI: Intelligentizing Mobile Edge Computing, Caching and Communication by Federated Learning](https://mlsanity.com/paper/1809.07857/) (2018)
- [Lifelong Federated Reinforcement Learning: A Learning Architecture for Navigation in Cloud Robotic Systems](https://mlsanity.com/paper/1901.06455/) (2019)
- [Federated Reinforcement Learning with Environment Heterogeneity](https://mlsanity.com/paper/2204.02634/) (2022)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learning](https://mlsanity.com/paper/2103.05032/) (2021)
- [Federated Transfer Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1910.06001/) (2019)
- [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)
- [FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergence](https://mlsanity.com/paper/2204.08125/) (2022)
- [Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning](https://mlsanity.com/paper/2206.10185/) (2022)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup](https://mlsanity.com/paper/2012.15511/) (2020)
- [Model-free Learning with Heterogeneous Dynamical Systems: A Federated LQR Approach](https://mlsanity.com/paper/2308.11743/) (2023)
- [FedSysID: A Federated Approach to Sample-Efficient System Identification](https://mlsanity.com/paper/2211.14393/) (2022)

## Built on by (most cited first, 30 of 31)

- [Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis](https://mlsanity.com/paper/2404.08003/) (2024)
- [Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices](https://mlsanity.com/paper/2402.05876/) (2024)
- [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)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (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)
- [Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximation](https://mlsanity.com/paper/2408.08192/) (2024)
- [FOVA: Offline Federated Reinforcement Learning with Mixed-Quality Data](https://mlsanity.com/paper/2512.02350/) (2025)
- [Towards Fast Rates for Federated and Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2409.05291/) (2024)
- [On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representations](https://mlsanity.com/paper/2411.15014/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [DASA: Delay-Adaptive Multi-Agent Stochastic Approximation](https://mlsanity.com/paper/2403.17247/) (2024)
- [A Single Online Agent Can Efficiently Learn Mean Field Games](https://mlsanity.com/paper/2405.03718/) (2024)
- [On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments](https://mlsanity.com/paper/2409.03897/) (2024)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents](https://mlsanity.com/paper/2512.17688/) (2025)
- [Nonparametric Bellman Mappings for Value Iteration in Distributed Reinforcement Learning](https://mlsanity.com/paper/2503.16192/) (2025)
- [Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments](https://mlsanity.com/paper/2510.07436/) (2025)
- [Personalized Collaborative Learning with Affinity-Based Variance Reduction](https://mlsanity.com/paper/2510.16232/) (2025)
- [FIRM: Federated In-client Regularized Multi-objective Alignment for Large Language Models](https://mlsanity.com/paper/2511.16992/) (2025)
- [Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost](https://mlsanity.com/paper/2609.00193/) (2026)
- [Collaborative Yet Personalized Policy Training: Single-Timescale Federated Actor-Critic](https://mlsanity.com/paper/2605.14423/) (2026)
- [FedGuide: Diffusion Prior Alignment and Value Baseline Guidance for Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2609.18964/) (2026)
- [Personalized Federated Reinforcement Learning via Model-Agnostic Meta-Learning: Convergence of Exact and Hessian-Free Meta-Policy Gradients](https://mlsanity.com/paper/2609.22833/) (2026)
- [Trapped by Their Own Rollouts: Understanding Aggregation--Rollout Feedback in Federated On-Policy Distillation](https://mlsanity.com/paper/2609.32573/) (2026)

## Abstract (arXiv)

Federated reinforcement learning (FRL) has emerged as a promising paradigm for reducing the sample complexity of reinforcement learning tasks by exploiting information from different agents. However, when each agent interacts with a potentially different environment, little to nothing is known theoretically about the non-asymptotic performance of FRL algorithms. The lack of such results can be attributed to various technical challenges and their intricate interplay: Markovian sampling, linear function approximation, multiple local updates to save communication, heterogeneity in the reward functions and transition kernels of the agents' MDPs, and continuous state-action spaces. Moreover, in the on-policy setting, the behavior policies vary with time, further complicating the analysis. In response, we introduce FedSARSA, a novel federated on-policy reinforcement learning scheme, equipped with linear function approximation, to address these challenges and provide a comprehensive finite-time error analysis. Notably, we establish that FedSARSA converges to a policy that is near-optimal for all agents, with the extent of near-optimality proportional to the level of heterogeneity. Furthermore, we prove that FedSARSA leverages agent collaboration to enable linear speedups as the number of agents increases, which holds for both fixed and adaptive step-size configurations.