# Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost

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

## Key facts

- Cited by 10 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.
- First posted on arXiv 29 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL for energy, networks and operations](https://mlsanity.com/deeprl/rl-for-energy-networks-and-operations/)

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

- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates](https://mlsanity.com/paper/2410.15612/) (2024)
- [Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agents](https://mlsanity.com/paper/2410.22908/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [Understanding the Statistical Accuracy-Communication Trade-off in Personalized Federated Learning with Minimax Guarantees](https://mlsanity.com/paper/2410.08934/) (2024)
- [Q-Learning with Fine-Grained Gap-Dependent Regret](https://mlsanity.com/paper/2510.06647/) (2025)
- [Explainable reinforcement learning from human feedback to improve alignment](https://mlsanity.com/paper/2512.13837/) (2025)
- [Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost](https://mlsanity.com/paper/2609.00193/) (2026)
- [Learning from Unreliable Trajectories: Adversarially-Robust Federated Q-Learning](https://mlsanity.com/paper/2610.06918/) (2026)

## Abstract (arXiv)

In this paper, we consider model-free federated reinforcement learning for tabular episodic Markov decision processes. Under the coordination of a central server, multiple agents collaboratively explore the environment and learn an optimal policy without sharing their raw data. Despite recent advances in federated Q-learning algorithms achieving near-linear regret speedup with low communication cost, existing algorithms only attain suboptimal regrets compared to the information bound. We propose a novel model-free federated Q-learning algorithm, termed FedQ-Advantage. Our algorithm leverages reference-advantage decomposition for variance reduction and operates under two distinct mechanisms: synchronization between the agents and the server, and policy update, both triggered by events. We prove that our algorithm not only requires a lower logarithmic communication cost but also achieves an almost optimal regret, reaching the information bound up to a logarithmic factor and near-linear regret speedup compared to its single-agent counterpart when the time horizon is sufficiently large.