Research map / Bandits and online learning / RL theory and MDPs
Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition
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.
Proves the first gap-dependent (log T) regret and gap-dependent policy switching cost bounds for the variance-based, reference-advantage Q-learning algorithms UCB-Advantage and Q-EarlySettled-Advantage, using a surrogate reference-function error decomposition.
Problem
Gap-dependent regret and policy switching cost for model-free Q-learning that uses variance estimators and reference-advantage decomposition in finite-horizon tabular episodic MDPs; prior gap-dependent analyses only covered Hoeffding-type bonuses.
Approach
An error decomposition that separates advantage, reference, and reference-settling errors, with surrogate reference functions (clipped between V* and V*+beta) that are determined before each episode, turning the error terms into martingale sums; integrating the weighted error sums over dyadic gap intervals yields 1/Delta_min rather than 1/Delta_min^2 dependence. Also splits switching-cost analysis
Key results
- UCB-Advantage gap-dependent regret O((Q*+β²H)H³SA log(SAT)/Δmin + H⁸S²A log(SAT) log T/β²), and Q-EarlySettled-Advantage gives O((Q*+β²H)H³SA log(SAT)/Δmin + H⁷SA log²(SAT)/β).
- For worst-case Q*=Θ(H²), the gap-dependent term becomes Õ(H⁵SA/Δmin), claimed better than prior Hoeffding-based bounds by a factor of H.
- UCB-Advantage policy switching cost gap-dependent bound removes a factor of A in the leading term when each state has a unique optimal action, versus O(H²SA log T) worst-case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use UCB-Advantage instead of UCB-Hoeffding or AMB | tabular episodic MDPs · synthetic general MDPs | regret | Helped |
| use Q-EarlySettled-Advantage instead of UCB-Hoeffding or AMB | tabular episodic MDPs · synthetic general MDPs | regret | Helped |
| use UCB-Advantage instead of UCB-Hoeffding or AMB | tabular episodic MDPs · synthetic deterministic MDPs | regret | Helped |
| use Q-EarlySettled-Advantage instead of UCB-Hoeffding or AMB | tabular episodic MDPs · synthetic deterministic MDPs | regret | Helped |
| use Q-EarlySettled-Advantage instead of UCB-Advantage | tabular episodic MDPs · synthetic MDPs at large K | regret | Helped |
| use stage-based UCB-Advantage | tabular episodic MDPs · synthetic general and deterministic MDPs | policy switching cost | Helped |
Limitations
- Gap-free terms and polynomial dependence on H, S, A are large; the bounds only beat the worst-case sqrt(T) rate once T is sufficiently large.
- Experiments are small synthetic MDPs (H=5,S=3,A=2 and H=10,S=5,A=5) on a single core.
Experimental setup
Metrics: expected regret policy switching cost
Baselines: UCB-Hoeffding AMB UCB-Advantage Q-EarlySettled-Advantage
Builds on: UCB-Advantage Q-EarlySettled-Advantage UCB-Hoeffding Adaptive Multi-step Bootstrap
Closest papers by meaning
- Q-Learning with Fine-Grained Gap-Dependent Regret (ICLR 2026 · similarity 0.93)
- Gap-Dependent Bounds for Federated $Q$-Learning (ICML 2025 · similarity 0.92)
- Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs (NeurIPS 2025 · similarity 0.92)
- Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.89)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 2024 · similarity 0.88)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.87)
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.