Discovering Options for Exploration by Minimizing Cover Time

Abstract

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.

References in corpus (5)

• A Laplacian Framework for Option Discovery in Reinforcement Learning
• Eigenoption Discovery through the Deep Successor Representation
• Adaptive Skills, Adaptive Partitions (ASAP)
• Learning Purposeful Behaviour in the Absence of Rewards
• Finding Options that Minimize Planning Time

Cited by in corpus (8)

• A Survey of Exploration Methods in Reinforcement Learning
• Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs
• Temporally-Extended ε-Greedy Exploration
• Attention Option-Critic
• Temporal Abstraction in Reinforcement Learning with the Successor Representation
• Direct then Diffuse: Incremental Unsupervised Skill Discovery for State Covering and Goal Reaching
• When should agents explore?
• Option Discovery in the Absence of Rewards with Manifold Analysis