mlsanityData to 14 Oct 2026

Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling

arXiv 2504.11645 ↗First posted 15 Apr 2025cs.LG cs.AI cs.SYcited by 2

On the map: Deep reinforcement learning methods → RL for energy, networks and operations

Abstract (arXiv)

Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving M agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity in the roots of the agents' local operators. The limited recent work that has accounted for both these features in a federated setting fails to guarantee convergence to the desired point or to show any benefit of collaboration; furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithm titled textttFedHSA, and prove that it guarantees convergence to the correct point, while enjoying an M-fold linear speedup in sample-complexity due to collaboration. To our knowledge, this is the first finite-time result of its kind, and establishing it (without relying on a projection step) entails a fairly intricate argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-effects induced by heterogeneous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents' Markov decision processes can differ in their probability transition kernels and reward functions.

Key facts. Cited by 2 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 46 of its 64 references that are in the map. First posted on arXiv 15 Apr 2025.

Builds on

46 of 64 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learning9 Sep
  2. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learning30 Aug
  3. 2024Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments29 May
  4. 2024Compressed Federated Reinforcement Learning with a Generative Model26 Mar
  5. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning27 Jan

Other references · 41

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  3. 2019Towards Federated Learning at Scale: System Designcited by 832
  4. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 564
  5. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  6. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  7. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  8. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  9. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  10. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  11. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  12. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
29 more
  1. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  2. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 81
  3. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  4. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  5. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  6. 2018On Markov Chain Gradient Descentcited by 63
  7. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 63
  8. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  9. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 54
  10. 2021Convergence and Accuracy Trade-Offs in Federated Learning and Meta-Learningcited by 52
  11. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  12. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  13. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 38
  14. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  15. 2017Least-Squares Temporal Difference Learning for the Linear Quadratic Regulatorcited by 30
  16. 2022FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergencecited by 29
  17. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 27
  18. 2020Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedupcited by 25
  19. 2023Improved Communication Efficiency in Federated Natural Policy Gradient via ADMM-based Gradient Updatescited by 21
  20. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
  21. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 15
  22. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  23. 2023Distributed TD(0) with Almost No Communicationcited by 13
  24. 2023Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learningcited by 12
  25. 2020Finite-Time Convergence Rates of Decentralized Stochastic Approximation with Applications in Multi-Agent and Multi-Task Learningcited by 10
  26. 2023Stability of Q-Learning Through Design and Optimismcited by 8
  27. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
  28. 2024Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Samplingcited by 7
  29. 2024One-Shot Averaging for Distributed TD(λ) Under Markov Samplingcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximationcited by 0
  2. 2026High-Probability Convergence of SGD via Batched Updatescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Parameter-Free Federated TD Learning with Markov Noise in Heterogeneous Environments
  2. 2024On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments
  3. 2025On Global Convergence Rates for Federated Softmax Policy Gradient under Heterogeneous Environments
  4. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost
  5. 2024Momentum-Based Federated Reinforcement Learning with Interaction and Communication Efficiency
  6. 2024Single-Loop Federated Actor-Critic across Heterogeneous Environments
  7. 2026Collaborative Yet Personalized Policy Training: Single-Timescale Federated Actor-Critic
  8. 2026Personalized Federated Reinforcement Learning via Model-Agnostic Meta-Learning: Convergence of Exact and Hessian-Free Meta-Policy Gradients