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.
Introduction
In Reinforcement Learning (RL), an agent typically learns by receiving rewards from its environment. However, in many complex scenarios, rewards are sparse: an agent might wander for thousands of steps before receiving any feedback. This creates a "needle in a haystack" problem where standard exploration strategies, such as uniform random walks, are highly inefficient due to frequent backtracking over familiar territory.
While the "options framework" allows agents to learn high-level, temporally extended actions (e.g., "navigate to the doorway"), a fundamental challenge remains: how to discover useful options without prior knowledge of the reward locations. This paper addresses this by framing exploration as a graph coverage problem, proposing a method to discover options that specifically minimize the expected time to visit every state.
Methods: Exploration as Graph Connectivity
The authors bridge reinforcement learning with spectral graph theory by modeling the agent's early behavior as a uniform random walk on a graph where nodes are states and edges are possible transitions.
Cover Time and Algebraic Connectivity
The core metric used is cover time, defined as the expected number of steps a random walk needs to visit every node in the graph. The authors identify cover time as a direct proxy for exploration difficulty. Crucially, they show that cover time is bounded by the algebraic connectivity ($\lambda_2$) of the graph's Laplacian matrix. A higher $\lambda_2$ indicates a more well-connected graph that is easier for a random walk to traverse.
The Covering Options Algorithm
To minimize cover time, the algorithm seeks to increase $\lambda_2$ by adding "bridges" between the most distant parts of the state space. The process involves:
- Computing the Fiedler vector (the eigenvector corresponding to $\lambda_2$).
- Identifying the two states with the maximum and minimum values in this vector, which represent the "most distant" points in the current graph topology.
- Creating a Point Option (a bridge) between these two states.
- Greedily repeating this process to "knit" the graph together more tightly.
Empirical Evaluation and Results
The researchers evaluated "Covering Options" on six classic discrete RL benchmarks: the 9x9 Grid, Four-room Gridworld, Taxi, Towers of Hanoi, Parr’s Maze, and Race Track. These tasks range from simple navigation to complex puzzles requiring specific sequences of actions.
Faster Learning and Improved Connectivity
In all tested domains, the Covering Options method allowed agents to find rewards and converge on optimal policies significantly faster than previous state-of-the-art methods, such as eigenoptions or betweenness options.
The paper empirically confirms the theoretical link between graph topology and performance. As the algorithm adds options and increases algebraic connectivity, the measured cover time drops, directly correlating with higher accumulated rewards.
Discussion and Limitations
While the method provides a provable improvement in exploration efficiency, it has certain limitations:
- Graph Assumptions: The current theory relies on the state-transition graph being undirected and strongly connected. Environments with "one-way" transitions (directed edges) present a challenge for standard spectral analysis.
- Scalability: Computing eigenvectors for massive state spaces (e.g., high-resolution video games) is computationally expensive. While the Fiedler vector can be computed efficiently for large graphs, scaling to continuous, high-dimensional spaces remains an area for future work.
Conclusion
By treating exploration as a problem of connectivity, the authors provide a principled approach to option discovery. Minimizing cover time through spectral graph theory transforms "long, thin" state spaces into "dense, round" ones, enabling agents to navigate sparse-reward environments with unprecedented efficiency.
Summary updated