# The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 52 references that are in the map.
- First posted on arXiv 18 May 2023.

## Builds on (most cited first, 28 of 28)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Federated Reinforcement Learning with Environment Heterogeneity](https://mlsanity.com/paper/2204.02634/) (2022)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning](https://mlsanity.com/paper/2206.10185/) (2022)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup](https://mlsanity.com/paper/2012.15511/) (2020)
- [Gossip-based Actor-Learner Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1906.04585/) (2019)
- [Finite-Time Performance of Distributed Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.12530/) (2019)
- [On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias](https://mlsanity.com/paper/2008.07841/) (2020)
- [Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2009.11146/) (2020)

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

- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Asynchronous Federated Reinforcement Learning with Policy Gradient Updates: Algorithm Design and Convergence Analysis](https://mlsanity.com/paper/2404.08003/) (2024)
- [FedRLHF: A Convergence-Guaranteed Federated Framework for Privacy-Preserving and Personalized RLHF](https://mlsanity.com/paper/2412.15538/) (2024)
- [Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning](https://mlsanity.com/paper/2311.00201/) (2023)
- [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)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (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)
- [A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies](https://mlsanity.com/paper/2510.16132/) (2025)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning](https://mlsanity.com/paper/2601.13642/) (2026)
- [CAESAR: Enhancing Federated RL in Heterogeneous MDPs through Convergence-Aware Sampling with Screening](https://mlsanity.com/paper/2403.20156/) (2024)
- [SwiftRL: Towards Efficient Reinforcement Learning on Real Processing-In-Memory Systems](https://mlsanity.com/paper/2405.03967/) (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)
- [Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning](https://mlsanity.com/paper/2505.18447/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents](https://mlsanity.com/paper/2512.17688/) (2025)
- [A finite time analysis of distributed Q-learning](https://mlsanity.com/paper/2405.14078/) (2024)
- [Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost](https://mlsanity.com/paper/2609.00193/) (2026)
- [Robust Federated Q-Learning with Almost No Communication](https://mlsanity.com/paper/2609.20174/) (2026)

## Abstract (arXiv)

When the data used for reinforcement learning (RL) are collected by multiple agents in a distributed manner, federated versions of RL algorithms allow collaborative learning without the need for agents to share their local data. In this paper, we consider federated Q-learning, which aims to learn an optimal Q-function by periodically aggregating local Q-estimates trained on local data alone. Focusing on infinite-horizon tabular Markov decision processes, we provide sample complexity guarantees for both the synchronous and asynchronous variants of federated Q-learning. In both cases, our bounds exhibit a linear speedup with respect to the number of agents and near-optimal dependencies on other salient problem parameters. In the asynchronous setting, existing analyses of federated Q-learning, which adopt an equally weighted averaging of local Q-estimates, require that every agent covers the entire state-action space. In contrast, our improved sample complexity scales inverse proportionally to the minimum entry of the average stationary state-action occupancy distribution of all agents, thus only requiring the agents to collectively cover the entire state-action space, unveiling the blessing of heterogeneity in enabling collaborative learning by relaxing the coverage requirement of the single-agent case. However, its sample complexity still suffers when the local trajectories are highly heterogeneous. In response, we propose a novel federated Q-learning algorithm with importance averaging, giving larger weights to more frequently visited state-action pairs, which achieves a robust linear speedup as if all trajectories are centrally processed, regardless of the heterogeneity of local behavior policies.