mlsanityData to 7 Oct 2026

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

arXiv 2401.15273 ↗First posted 27 Jan 2024cs.LG cs.SY eess.SYcited by 29

Not on the map. Why?

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.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 31 of its 56 references that are in the map. First posted on arXiv 27 Jan 2024.

Builds on

31 of 56 references.

References · 31

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  4. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  6. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  7. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  8. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  9. 2017On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learningcited by 136
  10. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  11. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  12. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
19 more
  1. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 93
  2. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  3. 2018In-Edge AI: Intelligentizing Mobile Edge Computing, Caching and Communication by Federated Learningcited by 80
  4. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  5. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 79
  6. 2019Lifelong Federated Reinforcement Learning: A Learning Architecture for Navigation in Cloud Robotic Systemscited by 77
  7. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 61
  8. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
  9. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  10. 2019Federated Transfer Reinforcement Learning for Autonomous Drivingcited by 43
  11. 2019Federated Deep Reinforcement Learningcited by 34
  12. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 34
  13. 2022FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergencecited by 29
  14. 2022Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learningcited by 27
  15. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  16. 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 23
  17. 2023Model-free Learning with Heterogeneous Dynamical Systems: A Federated LQR Approachcited by 19
  18. 2022FedSysID: A Federated Approach to Sample-Efficient System Identificationcited by 15
  19. 2023Distributed TD(0) with Almost No Communicationcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 14; 2025: 10; 2026: 5.

29 papers.

Sort:

By area:

  1. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysiscited by 21
  2. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Sufficescited by 11
  3. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  4. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environmentscited by 7
  5. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 6
  6. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  7. 2024Stochastic Semi-Gradient Descent for Learning Mean Field Games with Population-Aware Function Approximationcited by 5
  8. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  9. 2025FOVA: Offline Federated Reinforcement Learning with Mixed-Quality Datacited by 5
  10. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 4
  11. 2024On the Linear Speedup of Personalized Federated Reinforcement Learning with Shared Representationscited by 4
  12. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
17 more
  1. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learningcited by 3
  2. 2024A Single Online Agent Can Efficiently Learn Mean Field Gamescited by 2
  3. 2024On the Convergence Rates of Federated Q-Learning across Heterogeneous Environmentscited by 2
  4. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysiscited by 2
  5. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  6. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  7. 2024DASA: Delay-Adaptive Multi-Agent Stochastic Approximationcited by 1
  8. 2025Nonparametric Bellman Mappings for Value Iteration in Distributed Reinforcement Learningcited by 1
  9. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  10. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environmentscited by 1
  11. 2025Personalized Collaborative Learning with Affinity-Based Variance Reductioncited by 1
  12. 2025FIRM: Federated In-client Regularized Multi-objective Alignment for Large Language Modelscited by 0
  13. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learningcited by 0
  14. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0
  15. 2026FedGuide: Diffusion Prior Alignment and Value Baseline Guidance for Heterogeneous Federated Reinforcement Learningcited by 0
  16. 2026Personalized Federated Reinforcement Learning via Model-Agnostic Meta-Learning: Convergence of Exact and Hessian-Free Meta-Policy Gradientscited by 0
  17. 2026Trapped by Their Own Rollouts: Understanding Aggregation--Rollout Feedback in Federated On-Policy Distillationcited by 0