Research map / Reinforcement learning / MDPs and planning
Improved Sample Complexity for Incremental Autonomous Exploration in MDPs
Jean Tarbouriech, Matteo Pirotta, Michal Valko, Alessandro Lazaric
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 ALGO's model-based incremental exploration instead of UCBExplore | Incremental autonomous exploration · DCL sample complexity | sample complexity: \widetilde{O}(L^6 S_{L + \varepsilon} A/\varepsilon^3) for UCBExplore; ALGO bound: \widetilde{O}(L^5 \Gamma_{L + \vareps | Improved |
| Target near-optimal shortest-path policies on the final discovered state set | Incremental autonomous exploration · DC* | objective capability | Improved |
| Use SSP policies rather than finite-horizon policies for policy evaluation | Incremental autonomous exploration · DCL sample complexity | sample complexity: \widetilde{O}(\varepsilon^{-3}) for UCBExplore; \widetilde{O}(\varepsilon^{-2}) for ALGO | Improved |
| Recompute policies using the final expanded set of controllable states | ALGO · Incrementally L-controllable states | goal-reaching policy optimality | Improved |
| Use ALGO's exploration data for zero-shot planning with arbitrary supported costs | ALGO · Cost-sensitive SSP on incrementally L-controllable states | policy suboptimality: \varepsilon/c_{\min} | Improved |
Closest papers by meaning
- Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path (ICML 2022 · similarity 0.92)
- Layered State Discovery for Incremental Autonomous Exploration (ICML 2023 · similarity 0.91)
- The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration (NeurIPS 2026 · similarity 0.88)
- Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration (NeurIPS 2026 · similarity 0.87)
- Scalable Online Exploration via Coverability (ICML 2024 · similarity 0.87)
- Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts (NeurIPS 2025 · 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.
