Discovering Options for Exploration by Minimizing Cover Time

By Yuu Jinnai, Jee Won Park, David Abel, George Dimitri Konidaris. 2019

60 citations recorded by the source corpus.

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning World Graphs to Accelerate Hierarchical Reinforcement Learning (2019, neutral): “Pivotal state discovery is related to unsupervised sequence segmentation [17, 47, 76, 13, 16] and option or sub-task discovery in the context of RL [48, 6, 72, 30, 56, 53, 52].”
Flexible Option Learning (2021, methodology): “…that although our implementation is based upon the option-critic algorithm [Bacon et al., 2016], our approach can be straightforwardly adapted to most hierarchical RL algorithms [Riemer et al., 2018, Jain et al., 2018, Jinnai et al., 2019, Zhang and Whiteson, 2019, Bagaria and Konidaris, 2019].”
Value Preserving State-Action Abstractions (2020, background): “…Topin et al., 2015), encourage better exploration (Şimşek and Barto, 2004, 2009; Brunskill and Li, 2014; Bacon et al., 2017; Fruit and Lazaric, 2017; Machado et al., 2017; Tiwari and Thomas, 2019; Jinnai et al., 2019), and make planning more efficient (Mann and Mannor, 2014; Mann et al., 2015).”