Research map / Federated learning and privacy / Communication-efficient FL

The Sample-Communication Complexity Trade-off in Federated Q-Learning

NeurIPS 2024 · Federated learning and privacy › Communication-efficient FL · approach: Federated optimization algorithms · 1 citations (OpenAlex)

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.

Characterizes the sample-communication trade-off for intermittent-communication federated Q-learning: proves a lower bound of order 1/(1-γ) rounds (and |S||A|/(1-γ) bits per agent) for any speedup, and proposes Fed-DVR-Q, which achieves order-optimal sample and communication complexity.

Problem

Federated Q-learning with M agents and a generative model must trade off sample complexity against communication; it is unclear how little communication is needed to obtain any linear speedup in the number of agents, and whether optimal sample complexity can be achieved with optimal communication.

Approach

Replaces the usual many-small-noisy-local-steps scheme with large minibatch variance-reduced updates (re-centered at a communicated estimate of the Bellman operator), with stochastic quantization for bit-level communication; a matching lower bound uses a hard MDP to show local bias dominates when communication is infrequent.

Key results

• Lower bound: any intermittent-communication federated Q-learning algorithm achieving any speedup in agents needs Omega(1/((1-γ) log^2 N)) communication rounds and Omega(|S||A|/((1-γ) log^2 N)) bits per agent.
• Fed-DVR-Q achieves per-agent sample complexity Õ(|S||A|/(M(1-γ)^3 ε^2)) with Õ(1/(1-γ)) rounds and Õ(|S||A|/(1-γ)) bits per agent.
• Numerical study: Fed-DVR-Q attains lower error than Fed-SynQ at the same sample budget and uses much less communication (bits) than Fed-SynQ with 5 agents.

Measured effects reported in the paper

Surprising findings

• Communication rounds must scale with the effective horizon 1/(1-γ) to obtain any collaborative gain, even though policy evaluation (TD learning) needs only one round.

Limitations

• Lower bound and algorithm restricted to the tabular setting and intermittent communication class.
• Analysis holds for the synchronous generative-model setting; log factors hidden in the bounds.
• Experiments are small synthetic MDP with 3 states and 2 actions.

Experimental setup

Benchmarks: synthetic 3-state MDP with gamma=0.9

Metrics: error rate (l-infinity) sample complexity communication complexity (rounds and bits)

Baselines: Fed-SynQ Q-learning variance reduced Q-learning

Builds on: Q-learning variance-reduced Q-learning Fed-SynQ

Closest papers by meaning

• Federated $Q$-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost (ICLR 2025 · similarity 0.90)
• Federated Q-Learning: Linear Regret Speedup with Low Communication Cost (ICLR 2024 · similarity 0.90)
• Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.89)
• Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
• Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices (ICML 2024 · similarity 0.86)
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge (AAAI 2024 · similarity 0.86)