# Improved Sample Complexity for Incremental Autonomous Exploration in MDPs

arXiv: https://arxiv.org/abs/2012.14755 · HTML: https://mlsanity.com/paper/2012.14755/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Dec 2020.

## Built on by (most cited first, 9 of 9)

- [Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret](https://mlsanity.com/paper/2104.11186/) (2021)
- [Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path](https://mlsanity.com/paper/2106.08377/) (2021)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Adaptive Multi-Goal Exploration](https://mlsanity.com/paper/2111.12045/) (2021)
- [Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path](https://mlsanity.com/paper/2210.04946/) (2022)
- [Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Path](https://mlsanity.com/paper/2205.10729/) (2022)
- [Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model](https://mlsanity.com/paper/2604.16111/) (2026)
- [Layered State Discovery for Incremental Autonomous Exploration](https://mlsanity.com/paper/2302.03789/) (2023)
- [SUN: Reaching for Novelty in Reinforcement Learning](https://mlsanity.com/paper/2609.08642/) (2026)

## Abstract (arXiv)

We investigate the exploration of an unknown environment when no reward function is provided. Building on the incremental exploration setting introduced by Lim and Auer [1], we define the objective of learning the set of ε-optimal goal-conditioned policies attaining all states that are incrementally reachable within L steps (in expectation) from a reference state s0. In this paper, we introduce a novel model-based approach that interleaves discovering new states from s0 and improving the accuracy of a model estimate that is used to compute goal-conditioned policies to reach newly discovered states. The resulting algorithm, DisCo, achieves a sample complexity scaling as tildeO(L5 SL+ε GammaL+ε A ε-2), where A is the number of actions, SL+ε is the number of states that are incrementally reachable from s0 in L+ε steps, and GammaL+ε is the branching factor of the dynamics over such states. This improves over the algorithm proposed in [1] in both ε and L at the cost of an extra GammaL+ε factor, which is small in most environments of interest. Furthermore, DisCo is the first algorithm that can return an ε/cmin-optimal policy for any cost-sensitive shortest-path problem defined on the L-reachable states with minimum cost cmin. Finally, we report preliminary empirical results confirming our theoretical findings.