Research map / Federated learning and privacy / Communication-efficient FL
Federated Q-Learning: Linear Regret Speedup with Low Communication Cost
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FedQ-Hoeffding and FedQ-Bernstein, model-free federated Q-learning algorithms for tabular episodic MDPs that achieve linear regret speedup in the number of agents with logarithmic communication cost via event-triggered synchronization and equal-weight server aggregation.
Problem
Achieving linear regret speedup with the number of agents in federated reinforcement learning for tabular episodic MDPs using a model-free algorithm, while keeping communication cost low.
Approach
Event-triggered rounds in which agents explore a fixed policy until a visit-count threshold is hit; the server aggregates local Q-estimates with equal weights across all visits in a round, so agents need only send empirical averages of next-state values rather than trajectories, and a new concentration analysis handles the resulting non-martingale weighted sums.
Key results
- FedQ-Hoeffding achieves regret Õ(sqrt(H^4 SAMT)) with communication cost O(M^2 H^4 S^2 A log(T/M)), giving linear speedup in M when T is large enough.
- FedQ-Bernstein achieves regret Õ(sqrt(H^3 SAMT)), improving on FedQ-Hoeffding by a factor of sqrt(H), with the same logarithmic communication cost order.
- The paper claims these are the first model-free federated RL algorithms with linear regret speedup and logarithmic communication cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Bernstein-type confidence bound instead of the Hoeffding-type bound | FedQ-Bernstein versus FedQ-Hoeffding · Tabular episodic MDP | regret upper bound: by a factor of \sqrt{H} | Helped |
| Use FedQ-Hoeffding instead of its single-agent counterpart | Federated Q-learning · Tabular episodic MDP, when T is sufficiently large | regret | Helped |
| Use FedQ-Bernstein instead of its single-agent counterpart | Federated Q-learning · Tabular episodic MDP, when T is sufficiently large | regret | Helped |
Limitations
- Linear speedup holds only when T is sufficiently large relative to a burn-in term M poly(H,S,A).
- Assumes no communication latency and full synchronization among agents.
Experimental setup
Metrics: regret communication cost
Baselines: Q-UCB2H Q-UCB2B UCB-Advantage Multi-batch RL APEVE Byzan-UCBVI
Builds on: Q-UCB2H Q-UCB2B (Bernstein) UCB-Advantage Concurrent Q-learning Multi-batch RL
Closest papers by meaning
- Federated $Q$-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost (ICLR 2025 · similarity 0.97)
- Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (NeurIPS 2025 · similarity 0.93)
- Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.92)
- Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices (ICML 2024 · similarity 0.92)
- The Sample-Communication Complexity Trade-off in Federated Q-Learning (NeurIPS 2024 · similarity 0.90)
- Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning (ICLR 2024 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.