Exploration in Reinforcement Learning with Deep Covering Options

Yuu Jinnai, Jee Won Park, Marlos C. Machado, George Dimitri KonidarisICLR 2020 · OpenReview

TL;DR

This paper introduces Deep Covering Options, a method that automatically discovers temporal abstractions (options) to accelerate exploration in large or continuous state spaces. By approximating the eigenfunctions of the state-space Laplacian, the algorithm identifies and creates options to reach under-explored regions, provably reducing the time required for an agent to "cover" the entire environment.

What Problem Does This Paper Address?

Exploration remains one of the hardest challenges in Reinforcement Learning (RL), particularly in "sparse-reward" environments where an agent might wander for thousands of steps before receiving any feedback. Standard "dithering" strategies (like adding random noise to actions) are often too slow to find narrow passages or distant goals.

While the Options Framework allows agents to learn high-level "macro-actions" (like "go to the doorway"), knowing which options to build is an open question. A previous approach called "Covering Options" provided a principled mathematical way to discover options that minimize cover time—the expected number of steps to visit every state in a graph. However, that method was limited to small, discrete "tabular" worlds. This paper addresses the gap of scaling these theoretically grounded exploration options to the high-dimensional, continuous domains handled by Deep RL.

Methods

The authors bridge the gap between graph theory and Deep RL using the following steps:

  1. Approximating the Laplacian: In a tabular world, the environment is a graph. In continuous space, the authors use a neural network to estimate the eigenfunctions of the Laplacian (specifically the second eigenfunction, or Fiedler vector). This function acts as a "map" of the environment's connectivity.
  2. Identifying the Frontier: The extremes (maximum and minimum values) of this eigenfunction correspond to states that are "farthest apart" in terms of transition dynamics.
  3. Option Construction:
    • Termination Set: The algorithm identifies an under-explored region (e.g., the bottom 10% of the eigenfunction values) and sets it as the "goal" or termination region for a new option.
  4. Initiation Set: The rest of the state space is defined as the area where the option can be started.
  5. Policy Training: The option's policy is trained off-policy using a pseudo-reward derived from the eigenfunction ($r = f(s) - f(s')$). This effectively creates a gradient that pulls the agent toward the under-explored "frontier."
Option Construction: Initiation and Termination Sets
  1. Task-Agnosticism: Crucially, this process does not require a reward signal from the environment. It can be done during a "pretraining" phase or incrementally while the agent learns.

Datasets

The method was evaluated on several benchmark platforms:

  • Pinball Domain: A continuous state-space task requiring precise maneuvering through narrow passages and bounces.
  • MuJoCo (PointFall, PointMaze, PointPush): Continuous control tasks where agents must navigate mazes or move blocks without falling into traps.
  • Atari 2600 (Arcade Learning Environment): High-dimensional pixel-based games including Montezuma’s Revenge, MsPacman, and Amidar, used for qualitative analysis of exploration in massive state spaces.

Key Insights and Ideas

  • Connectivity over Diversity: Unlike methods like DIAYN (Diversity is All You Need), which focus on making skills as different as possible, Deep Covering Options focuses on connectivity. It specifically targets regions that are hard to reach via random walks, making it more effective for navigating complex topologies like mazes.
  • Minimizing Cover Time: The core "aha moment" is that exploration can be treated as a graph connectivity problem. By adding "edges" (options) between distant parts of the state-space graph, you mathematically shrink the diameter of the world, making every state easier to reach.
Minimizing Cover Time with Macro-Actions
  • Incremental Frontier Expansion: As the agent discovers one option and reaches a new area, the Laplacian estimate updates, allowing the agent to identify the next farthest region, effectively pushing the frontier of its knowledge step-by-step.

Key Results

  • Superior Exploration: In the PointFall domain—where agents often fail because they fall off a cliff before finding the goal—Deep Covering Options significantly outperformed flat RL baselines and other option-discovery methods.
  • Sample Efficiency: In the Pinball domain, agents equipped with these options reached the goal and stabilized their reward much faster than "flat" agents.
  • Qualitative Success in Atari: In Montezuma's Revenge, a notoriously difficult exploration game, the method successfully identified the "key" and "door" areas as termination regions for options without ever seeing a game reward.
  • Offline vs. Online: The method proved robust in both "pretraining" scenarios (learning options before the task starts) and "online" scenarios (discovering options while trying to solve the task).

Limitations and Future Work

  • Computational Overhead: Training separate neural networks for eigenfunctions and then training individual policies for each discovered option adds significant computational complexity compared to simple RL.
  • Hyperparameter Sensitivity: The choice of the percentile ($k$) for the termination set size affects performance; if the termination region is too small, the agent may never hit it; if it's too large, the option isn't specific enough.
  • Scaling the Eigenspectrum: The current work focuses primarily on the second eigenfunction. The authors note that exploring deeper into the "eigenspectrum" (using the 3rd, 4th, etc., eigenfunctions) could lead to even more diverse and useful options, but this requires more complex orthogonalization constraints.

Summary updated

BibTeX
@inproceedings{jinnai2020exploration,
  author = {Yuu Jinnai and Jee Won Park and Marlos C. Machado and George Dimitri Konidaris},
  title = {{Exploration in Reinforcement Learning with Deep Covering Options}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=av5NwO7r7d},
}
Figure