mlsanityData to 7 Oct 2026

Layered State Discovery for Incremental Autonomous Exploration

arXiv 2302.03789 ↗First posted 7 Feb 2023cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the autonomous exploration (AX) problem proposed by Lim & Auer (2012). In this setting, the objective is to discover a set of ε-optimal policies reaching a set SLrightarrow of incrementally L-controllable states. We introduce a novel layered decomposition of the set of incrementally L-controllable states that is based on the iterative application of a state-expansion operator. We leverage these results to design Layered Autonomous Exploration (LAE), a novel algorithm for AX that attains a sample complexity of tildeO(LSrightarrowL(1+ε)GammaL(1+ε) A ln12(SrightarrowL(1+ε))/ε2), where SrightarrowL(1+ε) is the number of states that are incrementally L(1+ε)-controllable, A is the number of actions, and GammaL(1+ε) is the branching factor of the transitions over such states. LAE improves over the algorithm of Tarbouriech et al. (2020a) by a factor of L2 and it is the first algorithm for AX that works in a countably-infinite state space. Moreover, we show that, under a certain identifiability assumption, LAE achieves minimax-optimal sample complexity of tildeO(LSrightarrowLAln12(SrightarrowL)/ε2), outperforming existing algorithms and matching for the first time the lower bound proved by Cai et al. (2022) up to logarithmic factors.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 35 references that are in the map. First posted on arXiv 7 Feb 2023.

Builds on

24 of 35 references.

References · 24

  1. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
  2. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 632
  3. 2016Variational Intrinsic Controlcited by 262
  4. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  5. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  6. 2019Skew-Fit: State-Covering Self-Supervised Reinforcement Learningcited by 171
  7. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  8. 2020Adaptive Reward-Free Explorationcited by 77
  9. 2020Near-optimal Regret Bounds for Stochastic Shortest Pathcited by 50
  10. 2019No-Regret Exploration in Goal-Oriented Reinforcement Learningcited by 34
  11. 2021Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regretcited by 34
  12. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
12 more
  1. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  2. 2021Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Pathcited by 23
  3. 2020Active Model Estimation in Markov Decision Processescited by 20
  4. 2021Direct then Diffuse: Incremental Unsupervised Skill Discovery for State Covering and Goal Reachingcited by 19
  5. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 15
  6. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  7. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  8. 2020Improved Sample Complexity for Incremental Autonomous Exploration in MDPscited by 9
  9. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  10. 2021Adaptive Multi-Goal Explorationcited by 4
  11. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  12. 2022Near-Optimal Algorithms for Autonomous Exploration and Multi-Goal Stochastic Shortest Pathcited by 2

Built on by

Not cited yet.