# Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2022.

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

- [The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond](https://mlsanity.com/paper/2305.10697/) (2023)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [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)
- [Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling](https://mlsanity.com/paper/2305.08104/) (2023)
- [Distributed TD(0) with Almost No Communication](https://mlsanity.com/paper/2305.16246/) (2023)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Federated Multi-Objective Learning](https://mlsanity.com/paper/2310.09866/) (2023)
- [Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices](https://mlsanity.com/paper/2402.05876/) (2024)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [Momentum for the Win: Collaborative Federated Reinforcement Learning across Heterogeneous Environments](https://mlsanity.com/paper/2405.19499/) (2024)
- [RBLA: Rank-Based-LoRA-Aggregation for Fine-tuning Heterogeneous Models in FLaaS](https://mlsanity.com/paper/2408.08699/) (2024)
- [To Store or Not? Online Data Selection for Federated Learning with Limited Storage](https://mlsanity.com/paper/2209.00195/) (2022)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [FedHQL: Federated Heterogeneous Q-Learning](https://mlsanity.com/paper/2301.11135/) (2023)
- [Local Environment Poisoning Attacks on Federated Reinforcement Learning](https://mlsanity.com/paper/2303.02725/) (2023)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [One-Shot Averaging for Distributed TD(λ) Under Markov Sampling](https://mlsanity.com/paper/2403.08896/) (2024)
- [Federated reinforcement learning for robot motion planning with zero-shot generalization](https://mlsanity.com/paper/2403.13245/) (2024)
- [Federated Prompt-based Decision Transformer for Customized VR Services in Mobile Edge Computing System](https://mlsanity.com/paper/2402.09729/) (2024)
- [Momentum-Based Federated Reinforcement Learning with Interaction and Communication Efficiency](https://mlsanity.com/paper/2405.17471/) (2024)
- [Federated Offline Policy Optimization with Dual Regularization](https://mlsanity.com/paper/2405.17474/) (2024)
- [Over-the-air Federated Policy Gradient](https://mlsanity.com/paper/2310.16592/) (2023)
- [Communication Efficient and Privacy-Preserving Federated Learning Based on Evolution Strategies](https://mlsanity.com/paper/2311.03405/) (2023)

## Abstract (arXiv)

Since reinforcement learning algorithms are notoriously data-intensive, the task of sampling observations from the environment is usually split across multiple agents. However, transferring these observations from the agents to a central location can be prohibitively expensive in terms of communication cost, and it can also compromise the privacy of each agent's local behavior policy. Federated reinforcement learning is a framework in which N agents collaboratively learn a global model, without sharing their individual data and policies. This global model is the unique fixed point of the average of N local operators, corresponding to the N agents. Each agent maintains a local copy of the global model and updates it using locally sampled data. In this paper, we show that by careful collaboration of the agents in solving this joint fixed point problem, we can find the global model N times faster, also known as linear speedup. We first propose a general framework for federated stochastic approximation with Markovian noise and heterogeneity, showing linear speedup in convergence. We then apply this framework to federated reinforcement learning algorithms, examining the convergence of federated on-policy TD, off-policy TD, and Q-learning.