# Discovering Options for Exploration by Minimizing Cover Time

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

## Key facts

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

## Built on by (most cited first, 30 of 31)

- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Temporal Abstraction in Reinforcement Learning with the Successor Representation](https://mlsanity.com/paper/2110.05740/) (2021)
- [Decomposing the Enigma: Subgoal-based Demonstration Learning for Formal Theorem Proving](https://mlsanity.com/paper/2305.16366/) (2023)
- [Deep Laplacian-based Options for Temporally-Extended Exploration](https://mlsanity.com/paper/2301.11181/) (2023)
- [Flexible Option Learning](https://mlsanity.com/paper/2112.03097/) (2021)
- [When should agents explore?](https://mlsanity.com/paper/2108.11811/) (2021)
- [Direct then Diffuse: Incremental Unsupervised Skill Discovery for State Covering and Goal Reaching](https://mlsanity.com/paper/2110.14457/) (2021)
- [A Distributional Analogue to the Successor Representation](https://mlsanity.com/paper/2402.08530/) (2024)
- [Proper Laplacian Representation Learning](https://mlsanity.com/paper/2310.10833/) (2023)
- [Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs](https://mlsanity.com/paper/2307.11629/) (2023)
- [Attention Option-Critic](https://mlsanity.com/paper/2201.02628/) (2022)
- [A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process](https://mlsanity.com/paper/2212.00211/) (2022)
- [QMP: Q-switch Mixture of Policies for Multi-Task Behavior Sharing](https://mlsanity.com/paper/2302.00671/) (2023)
- [Creating Multi-Level Skill Hierarchies in Reinforcement Learning](https://mlsanity.com/paper/2306.09980/) (2023)
- [Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs](https://mlsanity.com/paper/2201.08227/) (2022)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Toward Discovering Options that Achieve Faster Planning](https://mlsanity.com/paper/2205.12515/) (2022)
- [Timing is Everything: Learning to Act Selectively with Costly Actions and Budgetary Constraints](https://mlsanity.com/paper/2205.15953/) (2022)
- [SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving](https://mlsanity.com/paper/2310.12960/) (2023)
- [Subgoal Discovery Using a Free Energy Paradigm and State Aggregations](https://mlsanity.com/paper/2412.16687/) (2024)
- [The Laplacian Keyboard: Beyond the Linear Span](https://mlsanity.com/paper/2602.07730/) (2026)
- [Going Beyond State-Reaching: Learning Abstractions for Intrinsically Motivated Option Discovery](https://mlsanity.com/paper/2609.36473/) (2026)
- [Multi-agent Deep Covering Skill Discovery](https://mlsanity.com/paper/2210.03269/) (2022)
- [An Autonomous Non-monolithic Agent with Multi-mode Exploration based on Options Framework](https://mlsanity.com/paper/2305.01322/) (2023)
- [A Cover Time Study of a non-Markovian Algorithm](https://mlsanity.com/paper/2306.04902/) (2023)
- [Realizable Abstractions: Near-Optimal Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2512.04958/) (2025)
- [Inter-Agent Relative Representations for Multi-Agent Option Discovery](https://mlsanity.com/paper/2512.24827/) (2025)
- [Hierarchical Successor Representation for Robust Transfer](https://mlsanity.com/paper/2602.12753/) (2026)
- [When Do Options Help? Policy Necrosis and Redundant Coverage in Option-Critic](https://mlsanity.com/paper/2609.05508/) (2026)
- [Spectral Prioritized Sweeping in Nonstationary Reinforcement Learning](https://mlsanity.com/paper/2609.06186/) (2026)

## 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.