Research map / Bandits and online learning / RL theory and MDPs
Provably Efficient Q-Learning with Low Switching Cost
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add UCB2-scheduled delayed policy updates to Q-Learning with a Hoeffding bonus | Q-Learning · H-step episodic tabular MDP | local switching cost: O(H^3SA\log(K/A)) versus the UCB version's worst-case HS(K-1) | Helped |
| Add UCB2-scheduled delayed policy updates to Q-Learning with a Hoeffding bonus | Q-Learning · H-step episodic tabular MDP | regret: \wt{O}(\sqrt{H^4SAT}) | No clear effect |
| Replace the Hoeffding exploration bonus with a Bernstein-type bonus (ablation) | Q-Learning with UCB2 exploration · H-step episodic tabular MDP | regret: \wt{O}(\sqrt{H^4SAT}) -> \wt{O}(\sqrt{H^3SAT}) | Helped |
| Replace the Hoeffding exploration bonus with a Bernstein-type bonus (ablation) | Q-Learning with UCB2 exploration · H-step episodic tabular MDP | local switching cost: O(H^3SA\log(K/A)) | No clear effect |
| Use concurrent Q-Learning with UCB2 exploration on M parallel machines | Q-Learning with UCB2H/UCB2B · Concurrent episodic MDP | rounds to return an \eps near-optimal policy: \wt{O}\left(H^3SA + \frac{H^{\set{5,4}}SA}{\eps^2M} \right) | Helped |
| Restrict an RL algorithm's local switching cost to at most HSA/2 | Any RL algorithm · Episodic MDPs | regret: N_{\rm switch}\le HSA/2; KH/4 | Hurt |
Closest papers by meaning
- Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP (ICLR 2020 · similarity 0.90)
- Is Q-Learning Provably Efficient? (NeurIPS 2018 · similarity 0.89)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.88)
- Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- A General Framework for Sequential Decision-Making under Adaptivity Constraints (ICML 2024 · similarity 0.86)
- Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition (ICLR 2025 · similarity 0.86)
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.