mlsanityData to 14 Oct 2026

Discovering Options for Exploration by Minimizing Cover Time

arXiv 1903.00606 ↗First posted 2 Mar 2019cs.AIcited by 31

Not on the map. Why?

Abstract (arXiv)

One of the main challenges in reinforcement learning is solving tasks with sparse reward. We show that the difficulty of discovering a distant rewarding state in an MDP is bounded by the expected cover time of a random walk over the graph induced by the MDP's transition dynamics. We therefore propose to accelerate exploration by constructing options that minimize cover time. The proposed algorithm finds an option which provably diminishes the expected number of steps to visit every state in the state space by a uniform random walk. We show empirically that the proposed algorithm improves the learning time in several domains with sparse rewards.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). First posted on arXiv 2 Mar 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 5; 2022: 7; 2023: 9; 2024: 2; 2025: 2; 2026: 6.

31 papers.

Sort:

By area:

  1. 2021A Survey of Exploration Methods in Reinforcement Learningcited by 73
  2. 2021Temporal Abstraction in Reinforcement Learning with the Successor Representationcited by 54
  3. 2023Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Provingcited by 37
  4. 2023Deep Laplacian-based Options for Temporally-Extended Explorationcited by 29
  5. 2021Flexible Option Learningcited by 25
  6. 2021When should agents explore?cited by 20
  7. 2021Direct then Diffuse: Incremental Unsupervised Skill Discovery for State Covering and Goal Reachingcited by 19
  8. 2024A Distributional Analogue to the Successor Representationcited by 17
  9. 2023Proper Laplacian Representation Learningcited by 11
  10. 2023Scalable Multi-agent Covering Option Discovery based on Kronecker Graphscited by 9
  11. 2022Attention Option-Criticcited by 8
  12. 2022A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Processcited by 7
19 more
  1. 2023QMP: Q-switch Mixture of Policies for Multi-Task Behavior Sharingcited by 6
  2. 2023Creating Multi-Level Skill Hierarchies in Reinforcement Learningcited by 5
  3. 2022Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphscited by 4
  4. 2022Hierarchies of Reward Machinescited by 4
  5. 2022Toward Discovering Options that Achieve Faster Planningcited by 3
  6. 2022Timing is Everything: Learning to Act Selectively with Costly Actions and Budgetary Constraintscited by 2
  7. 2023SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solvingcited by 1
  8. 2024Subgoal Discovery Using a Free Energy Paradigm and State Aggregationscited by 1
  9. 2026The Laplacian Keyboard: Beyond the Linear Spancited by 1
  10. 2026Going Beyond State-Reaching: Learning Abstractions for Intrinsically Motivated Option Discoverycited by 1
  11. 2022Multi-agent Deep Covering Skill Discoverycited by 0
  12. 2023An Autonomous Non-monolithic Agent with Multi-mode Exploration based on Options Frameworkcited by 0
  13. 2023A Cover Time Study of a non-Markovian Algorithmcited by 0
  14. 2025Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learningcited by 0
  15. 2025Inter-Agent Relative Representations for Multi-Agent Option Discoverycited by 0
  16. 2026Hierarchical Successor Representation for Robust Transfercited by 0
  17. 2026When Do Options Help? Policy Necrosis and Redundant Coverage in Option-Criticcited by 0
  18. 2026Spectral Prioritized Sweeping in Nonstationary Reinforcement Learningcited by 0
  19. 2026Mastering Atari 2600 Games with Discovered Optionscited by 0