ODPP: A Unified Algorithm Framework for Unsupervised Option Discovery based on Determinantal Point Process

Jiayu Chen, Vaneet Aggarwal, Tian LanarXiv 2022 · arXiv · OpenReview

Abstract

Learning rich skills through temporal abstractions without supervision of external rewards is at the frontier of Reinforcement Learning research. Existing works mainly fall into two distinctive categories: variational and Laplacian-based skill (a.k.a., option) discovery. The former maximizes the diversity of the discovered options through a mutual information loss but overlooks coverage of the state space, while the latter focuses on improving the coverage of options by increasing connectivity during exploration, but does not consider diversity. In this paper, we propose a unified framework that quantifies diversity and coverage through a novel use of the Determinantal Point Process (DPP) and enables unsupervised option discovery explicitly optimizing both objectives. Specifically, we define the DPP kernel matrix with the Laplacian spectrum of the state transition graph and use the expected mode number in the trajectories as the objective to capture and enhance both diversity and coverage of the learned options. The proposed option discovery algorithm is extensively evaluated using challenging tasks built with Mujoco and Atari, demonstrating that our proposed algorithm substantially outperforms SOTA baselines from both diversity- and coverage-driven categories. The codes are available at https://github.com/LucasCJYSDL/ODPP.

Introduction

In unsupervised Reinforcement Learning (RL), the goal is to learn useful "skills" or options without any external reward signal. This allows an agent to build a library of behaviors that can be leveraged for downstream tasks. Historically, research has split into two camps: variational methods and Laplacian-based methods. Variational methods focus on diversity, ensuring options are distinct but often failing to explore the environment's periphery. Laplacian-based methods focus on coverage, analyzing environment geometry to traverse bottlenecks, yet they often produce repetitive skills.

The fundamental challenge is that diversity and coverage often pull in opposite directions. ODPP (Unsupervised Option Discovery based on Determinantal Point Process) introduces a framework that treats them as two sides of the same coin, providing a mathematical bridge between these two objectives.

Methodology: The DPP Framework

The core innovation is the application of Determinantal Point Processes (DPP), a probabilistic model that assigns higher probabilities to subsets of items that are diverse or "spread out." ODPP utilizes DPPs in three primary ways:

  1. Landmark Extraction: To mitigate noise, ODPP identifies "landmark states"—the most representative and diverse points in a trajectory—rather than processing every noisy state.
  2. Three-Pronged Objective:
  3. Coverage ($L_1$): Maximizes state diversity within a single option's trajectory, forcing the agent to travel further.
  4. Consistency ($L_2$): Minimizes diversity across trajectories of the same option, ensuring reliable behavior.
  5. Inter-option Diversity ($L_3$): Maximizes diversity between different options to build a wide library of distinct skills.
  6. Unified Optimization: These terms are integrated with a Variational Information Bottleneck (IB) objective, allowing simultaneous learning of latent skill codes and movement policies.

Experimental Results

The authors evaluated ODPP on challenging benchmarks, including Mujoco Mazes (Point and Ant agents), Atari games (RiverRaid, AirRaid), and OpenAI Gym (CartPole).

Comparison of option discovery methods in a maze. (a) Variational methods show diversity but poor coverage. (b) Laplacian methods show coverage but poor diversity. (c) ODPP achieves both. (d) Quantitative comparison of diversity and coverage metrics.

As shown in the figure above, ODPP was the only method that successfully discovered options traversing narrow bottlenecks to reach distant maze sections. In downstream tasks, ODPP-initialized agents reached higher rewards significantly faster than those using baselines like DADS or APS. On high-dimensional Atari games, the performance gap widened as difficulty increased, highlighting the necessity of balancing diversity and coverage.

Key Insights and Conclusion

ODPP demonstrates that coverage and diversity can be quantified using the same mathematical tool: DPP expected cardinality. Furthermore, the authors prove that their coverage objective generalizes previous Laplacian-based methods. While the algorithm introduces some computational overhead and hyperparameter sensitivity, it represents a significant step toward robust, unsupervised skill acquisition in complex environments.

Summary updated

Abstract

Learning rich skills through temporal abstractions without supervision of external rewards is at the frontier of Reinforcement Learning research. Existing works mainly fall into two distinctive categories: variational and Laplacian-based skill (a.k.a., option) discovery. The former maximizes the diversity of the discovered options through a mutual information loss but overlooks coverage of the state space, while the latter focuses on improving the coverage of options by increasing connectivity during exploration, but does not consider diversity. In this paper, we propose a unified framework that quantifies diversity and coverage through a novel use of the Determinantal Point Process (DPP) and enables unsupervised option discovery explicitly optimizing both objectives. Specifically, we define the DPP kernel matrix with the Laplacian spectrum of the state transition graph and use the expected mode number in the trajectories as the objective to capture and enhance both diversity and coverage of the learned options. The proposed option discovery algorithm is extensively evaluated using challenging tasks built with Mujoco and Atari, demonstrating that our proposed algorithm substantially outperforms SOTA baselines from both diversity- and coverage-driven categories. The codes are available at https://github.com/LucasCJYSDL/ODPP.
BibTeX
@misc{chen2022odpp,
  author = {Jiayu Chen and Vaneet Aggarwal and Tian Lan},
  title = {{ODPP: A Unified Algorithm Framework for Unsupervised Option Discovery based on Determinantal Point Process}},
  year = {2022},
  eprint = {2212.00211},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2212.00211},
}
Figure