mlsanityData to 14 Oct 2026

Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost

arXiv 2609.00193 ↗First posted 31 Aug 2026stat.ML cs.AI cs.LGcited by 1

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

Abstract (arXiv)

We study federated online reinforcement learning with linear function approximation. While recent multi-agent reinforcement learning algorithms achieve strong regret guarantees, they typically require sharing raw trajectories. This reliance incurs a communication cost that scales linearly with the number of episodes and violates the privacy constraints of federated settings. To address these limitations, we propose Fed-LSVI, the first provably efficient federated algorithm for online reinforcement learning with linear function approximation in episodic Markov decision processes. By integrating a determinant-based event-triggered synchronization with a stepwise backward update mechanism, Fed-LSVI enables agents to collaboratively learn an optimal policy by exchanging only compressed sufficient statistics. We prove that Fed-LSVI achieves a regret bound of widetildemathcal O(√Md3H4T), where d is the feature dimension, H is the horizon length, M is the number of agents, and T is the number of episodes per agent, matching the best-known regret for multi-agent online reinforcement learning with linear function approximation. Moreover, by following the stringent communication and privacy constraints of the federated setting, Fed-LSVI reduces the communication cost to only logarithmic dependence on T, representing a significant improvement over prior methods.

Key facts. Cited by 1 paper 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 47 of its 58 references that are in the map. First posted on arXiv 31 Aug 2026.

Builds on

47 of 58 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learning30 Aug
  2. 2024Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost29 May
  3. 2024Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis9 Apr
  4. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries15 Mar
  5. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning27 Jan

Other references · 42

  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. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
30 more
  1. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  2. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  3. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  4. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  5. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  6. 2020Q-learning with Logarithmic Regretcited by 60
  7. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  8. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  9. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  10. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  11. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  12. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  13. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  14. 2023The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyondcited by 36
  15. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  16. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  17. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  18. 2023Federated Q-Learning: Linear Regret Speedup with Low Communication Costcited by 19
  19. 2024Randomized Exploration in Cooperative Multi-Agent Reinforcement Learningcited by 17
  20. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 15
  21. 2023Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learningcited by 11
  22. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  23. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  24. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  25. 2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
  26. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 6
  27. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  28. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  29. 2026Understanding Gap-Dependent Regret for Optimism-Based Reinforcement Learning with Linear Function Approximationcited by 2
  30. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices
  2. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
  3. 2024Compressed Federated Reinforcement Learning with a Generative Model
  4. 2024Towards Fast Rates for Federated and Multi-Task Reinforcement Learning
  5. 2026FedQHD: Closed-Form Function-Space Federated Reinforcement Learning
  6. 2026Robust Federated Q-Learning with Almost No Communication
  7. 2025Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis
  8. 2026Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning