Research map / Bandits and online learning / RL theory and MDPs
Gap-Dependent Bounds for Federated $Q$-Learning
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.
Gives the first gap-dependent regret and communication-cost (and global switching cost) bounds for online federated Q-learning, analyzing FedQ-Hoeffding (and noting FedQ-Bernstein shares the bounds) in tabular episodic MDPs.
Problem
Existing online federated RL methods for tabular episodic MDPs only have worst-case sqrt(T) regret and communication bounds with log T terms scaling with MSA or SA; no gap-dependent analysis exists for online FRL.
Approach
Exploits a positive minimum suboptimality gap to obtain log T regret and a communication bound whose log T term is independent of M, S, A, by controlling value-estimation error with clipped sums and bounding visit counts under varying policies via error recursion over steps, with agent-wise and state-wise simultaneous visit increases.
Key results
- FedQ-Hoeffding achieves gap-dependent regret O(H^6 SA log(MSAT)/Delta_min + C_f), logarithmic in T, with a 1/M error reduction rate versus UCB-Hoeffding for average regret.
- Communication rounds bounded by O(MH^3SA log(MH^2 iota_0) + H^3SA log(H^5SA/Delta_min^2) + H^3S log(...) + H^2 log(T/(HSA))), removing MSA from the log T term.
- For M=1, global switching cost bound O(H^3SA log(H^5SA iota_2/Delta_min^2) + H^3S log(1/C_st) + H^2 log(T/(HSA))), removing SA from the log T term versus prior model-free methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use gap-dependent analysis for FedQ-Hoeffding when the MDP has positive minimum gap | FedQ-Hoeffding · Tabular episodic finite-horizon MDPs | regret: \sqrt{T}-type worst-case regret -> O\left(\frac{H^6 S A \iota_1}{\dmin}+ M\sqrt{H^7}SA\sqrt{\iota_1}+ MH^5SA\right) | Helped |
| Use the gap-dependent communication bound, whose log T term omits MSA | FedQ-Hoeffding · G-MDPs | communication rounds: O(MH^3SA\log T) or O(SA\log T) -> O^*(H^2\log T) | Helped |
| Use the single-agent FedQ-Hoeffding switching-cost bound | FedQ-Hoeffding with M=1 · G-MDPs | global switching cost: H^2SA\log T or H^2S\log T -> H^2\log\Big(\frac{T}{HSA}\Big) | Helped |
| Replace Hoeffding bonuses with Bernstein bonuses (ablation) | FedQ-Hoeffding · Gap-dependent federated tabular MDPs | regret | No clear effect |
Limitations
- Requires full synchronization and random initialization assumptions
- Requires G-MDP uniqueness of optimal policies for the communication bound
- Results are for FedQ-Hoeffding; FedQ-Bernstein gap-dependent tightness left open
Experimental setup
Datasets: synthetic tabular episodic MDP
Benchmarks: synthetic tabular episodic MDP
Metrics: regret communication rounds adjusted regret Regret(T)/log(T/H+1)
Baselines: FedQ-Hoeffding FedQ-Bernstein FedQ-Advantage Fed-UCBVI Byzan-UCBVI UCB-Hoeffding
Builds on: FedQ-Hoeffding UCB-Hoeffding FedQ-Bernstein UCB-Advantage
Closest papers by meaning
- Federated $Q$-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost (ICLR 2025 · similarity 0.93)
- Federated Q-Learning: Linear Regret Speedup with Low Communication Cost (ICLR 2024 · similarity 0.92)
- Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition (ICLR 2025 · similarity 0.92)
- Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (NeurIPS 2025 · similarity 0.92)
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.90)
- The Sample-Communication Complexity Trade-off in Federated Q-Learning (NeurIPS 2024 · similarity 0.89)
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.