Research map / Federated learning and privacy / Communication-efficient FL
Federated $Q$-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic 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-Advantage, a model-free federated Q-learning algorithm for tabular episodic MDPs that combines reference-advantage decomposition with event-triggered rounds and stages to achieve almost optimal regret and logarithmic communication cost.
Problem
Model-free federated RL in tabular episodic MDPs: existing federated Q-learning methods achieve only suboptimal regret or incur high communication cost, and it is unknown whether almost optimal regret with logarithmic communication is possible.
Approach
Extends the single-agent UCB-Advantage reference-advantage decomposition to federated settings using aligned communication rounds with unaligned stage-wise policy switching, heterogeneous event-triggered communication thresholds across rounds within a stage, and an optional forced synchronization mechanism.
Key results
- Regret upper bound of order tilde-O(sqrt(H^2 SAMT)) when T is large, matching the information bound up to log factors and giving near-linear speedup in M.
- With forced synchronization, communication rounds K = O(M H^2 SA (log H) log T); without it, K = O(H^2 SA (log H) log T), independent of M.
- In synthetic experiments, FedQ-Advantage shows lower regret and fewer communication rounds than FedQ-Hoeffding and FedQ-Bernstein.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FedQ-Advantage instead of FedQ-Hoeffding or FedQ-Bernstein | Federated Q-learning · Synthetic tabular episodic MDP, M=10 | regret | Helped |
| use FedQ-Advantage instead of FedQ-Hoeffding or FedQ-Bernstein | Federated Q-learning · Synthetic tabular episodic MDP, M=10 | communication rounds | Helped |
| enable forced synchronization (ablation) | FedQ-Advantage · Tabular episodic MDPs | regret | No clear effect |
| disable forced synchronization (ablation) | FedQ-Advantage · Tabular episodic MDPs | communication cost: $O(M^2H^3S^2A(\log H)\log T)$ -> $O(MH^3S^2A(\log H)\log T)$ | Helped |
| disable forced synchronization (ablation) | FedQ-Advantage · Tabular episodic MDPs | communication rounds: $O(MH^2SA(\log H)\log T)$ -> $O(H^2SA(\log H)\log T)$ | Helped |
| use heterogeneous rather than homogeneous triggering conditions | FedQ-Advantage · Tabular episodic MDPs | synchronizations per stage: $O(f_MH)$ -> $O(f_M\log H)$ | Helped |
| use FedQ-Advantage rather than FedQ-Bernstein | Federated Q-learning · Tabular episodic MDPs | regret: $\tilde{O}(\sqrt{H^{3}SAMT})$ -> $\tilde{O}(\sqrt{H^{2}SAMT})$ | Helped |
| use FedQ-Advantage rather than FedQ-Bernstein | Federated Q-learning · Tabular episodic MDPs | communication cost: $O(M^2H^4S^2A\log T)$ -> $O(M^2H^3S^2A(\log H)\log T)$ | Helped |
| use FedQ-Advantage rather than UCB-A with $10^6$ episodes | Multi-agent Q-learning · Synthetic tabular episodic MDP | regret | Hurt |
Surprising findings
- Without forced synchronization, communication rounds do not scale with the number of agents M.
- With a single agent generating all episodes under high communication cost, the algorithm has larger regret than the single-agent UCB-A baseline, attributed to multi-agent burn-in cost.
Limitations
- Regret bound includes an overhead term M poly(HSA, 1/beta) from burn-in costs, so near-linear speedup holds only when T is sufficiently large.
- Communication cost analysis assumes sharing of aggregated statistics per round; the switching-cost matching holds only under restrictions on sharing original trajectories.
- Requires the central server to know reward functions in advance (unknown rewards handled by a slight modification).
Experimental setup
Datasets: synthetic tabular episodic MDP
Benchmarks: synthetic tabular episodic MDP (H=10, S=5, A=5, M=10)
Metrics: regret communication rounds
Baselines: FedQ-Hoeffding FedQ-Bernstein UCB-A (single-agent)
Builds on: UCB-Advantage Q-learning with UCB Hoeffding-type federated Q-learning (FedQ-Hoeffding) FedQ-Bernstein
Closest papers by meaning
- Federated Q-Learning: Linear Regret Speedup with Low Communication Cost (ICLR 2024 · 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.93)
- Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices (ICML 2024 · similarity 0.91)
- 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.88)
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.