Research map / Bandits and online learning / RL theory and MDPs
Sample-Efficient Reinforcement Learning with loglog(T) 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 |
|---|---|---|---|
| Use staged exploration with adaptive policy elimination and an absorbing-MDP value estimator | APEVE · Tabular non-stationary episodic RL | regret: \widetilde{O}(\sqrt{H^{4}S^{2}AT}) regret | Helped |
| Schedule policy changes in advance across progressively longer stages | APEVE · Tabular non-stationary episodic RL | global switching cost: O(HSA\log\log T), versus existing O^*(\log T) switching cost | Helped |
| Use reward-independent crude and fine exploration, then optimize for the supplied reward | LARFE · Reward-free exploration | sample complexity (episodes): \widetilde{O}(\frac{H^{5}S^{2}A}{\epsilon^{2}}) | Helped |
| Use LARFE as the exploration phase before following its reward-optimal policy | Explore-First with LARFE · Tabular non-stationary episodic RL | regret: \widetilde{O}(T^{2/3}H^{4/3}S^{2/3}A^{1/3}) | Helped |
| Limit policy switching for algorithms with near-optimal regret | RL algorithms with \widetilde{O}^*(\sqrt{T}) regret · Tabular non-stationary episodic RL | global switching cost: \Omega(HSA\log\log T) lower bound; APEVE uses O(HSA\log\log T) | Mixed |
| Require sub-linear regret | RL algorithms · Tabular non-stationary episodic RL | global switching cost: \Omega(HSA) | Mixed |
Closest papers by meaning
- Reinforcement Learning with Logarithmic Regret and Policy Switches (NeurIPS 2022 · similarity 0.92)
- Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- Switching the Loss Reduces the Cost in Batch Reinforcement Learning (ICML 2024 · similarity 0.90)
- A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.89)
- Test-Time Regret Minimization in Meta Reinforcement Learning (ICML 2024 · similarity 0.88)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 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.