Research map / Bandits and online learning / RL theory and MDPs
Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs
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 restarting schedule to Q-learning with UCB bonuses (RestartQ-UCB vs no-restart Q-Learning UCB) (ablation) | Q-learning with UCB exploration · Bidirectional Diabolical Combination Lock, abrupt variations | cumulative reward: RestartQ-UCB reaches 1.36x Q-Learning UCB cumulative reward | Helped |
| Use RestartQ-UCB (restart plus UCB exploration) instead of epsilon-greedy restart-based exploration | restart-based Q-learning · Bidirectional Diabolical Combination Lock, abrupt variations | cumulative reward: RestartQ-UCB reaches 2.52x Epsilon-Greedy cumulative reward | Helped |
| Replace LSVI-UCB-Restart with model-free RestartQ-UCB | non-stationary RL agent · Bidirectional Diabolical Combination Lock, abrupt and gradual variations | cumulative reward and computation time: nearly matches LSVI-UCB-Restart reward while ~0.18% of compute time | No clear effect |
| Remove knowledge of local variation budgets via modified Q-update (Equation 1) | RestartQ-UCB Hoeffding · Theory: dynamic regret | dynamic regret order | No clear effect |
| Use Freedman-style instead of Hoeffding confidence bonuses | RestartQ-UCB · Theory: dynamic regret | dynamic regret order: Õ(S^1/3 A^1/3 Δ^1/3 H^5/3 T^2/3) to Õ(S^1/3 A^1/3 Δ^1/3 H T^2/3) | Helped |
Closest papers by meaning
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.93)
- Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (ICML 2020 · similarity 0.92)
- MetaCURL: Non-stationary Concave Utility Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
- Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds (ICLR 2025 · similarity 0.90)
- Pausing Policy Learning in Non-stationary Reinforcement Learning (ICML 2024 · similarity 0.90)
- NeoRL: Efficient Exploration for Nonepisodic RL (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.