Research map / Bandits and online learning / Multi-armed bandits
Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path
Haoyuan Cai, Tengyu Ma, Simon Du
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 VALAE instead of UcbExplore | Autonomous exploration · Autonomous exploration | sample complexity: \widetilde{O}(L^3S^2A/\varepsilon^3) -> \widetilde{O}(LSA/\varepsilon^2) | Improved |
| Use VALAE instead of DisCo | Autonomous exploration · Autonomous exploration | sample complexity: \widetilde{O}(L^3S^2A/\varepsilon^2) -> \widetilde{O}(LSA/\varepsilon^2) | Improved |
| Exploit value-function variance information to guide exploration | VALAE · Autonomous exploration | sample complexity dependence on L: cubic to linear | Improved |
| Exploit value-function variance information to guide exploration | VALAE · Autonomous exploration | sample complexity dependence on S: square to linear | Improved |
| Apply VALAE to multiple goal states | Multi-goal SSP · Multi-goal SSP | cumulative cost: \widetilde{O}(LSA\varepsilon^{-2}) | Improved |
Closest papers by meaning
- Improved Sample Complexity for Incremental Autonomous Exploration in MDPs (NeurIPS 2020 · similarity 0.92)
- Layered State Discovery for Incremental Autonomous Exploration (ICML 2023 · similarity 0.89)
- Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret (NeurIPS 2021 · similarity 0.89)
- Regret Lower Bounds for Decentralized Multi-Agent Stochastic Shortest Path Problems (NeurIPS 2025 · similarity 0.86)
- Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration (NeurIPS 2026 · similarity 0.85)
- The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration (NeurIPS 2026 · similarity 0.85)
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.
