Novel Exploration via Orthogonality

Andreas Theophilou, Özgür ŞimşekNeurIPS 2025 · OpenReview

TL;DR

Novel Exploration via Orthogonality (NEO) is a reinforcement learning framework that uses a modified "Source Laplacian" to automatically identify unvisited regions of an environment and generate explicit policies to reach them. Unlike previous spectral methods, NEO provides theoretical gradient guarantees for both undirected and directed graphs, ensuring agents explore diverse, novel states rather than getting stuck in well-trodden paths.

The Exploration Problem in RL

In reinforcement learning (RL), an agent must explore its environment to discover rewards. This presents a classic "chicken and egg" problem: to find the reward, the agent needs to explore, but to explore effectively, it needs to know where it hasn't been.

Existing approaches generally fall into two camps:

  1. Count-based methods: These give the agent a "novelty bonus" for visiting new states. While theoretically sound, they don't tell the agent how to get there; the agent has to stumble upon the reward through trial and error.
  2. Spectral methods (like Eigen-options): These use the math of graph theory (specifically, the Laplacian matrix) to find the "far reaches" of a state space. However, these methods often assume the environment is symmetric (undirected). In the real world, many actions are one-way (directed), and standard spectral methods can accidentally drive agents back to heavily visited areas if those areas happen to be geometrically "far" from the start.

NEO bridges this gap by providing a "how-to" guide—explicit gradients—that specifically targets novelty and works in complex, directed environments.

Methods: The Source Laplacian

The core innovation of NEO is the Source Laplacian ($L_\zeta = I + \Gamma - P$). Here is the breakdown of its components:

  • $P$ (Transition Matrix): Represents how the agent moves between states.
  • $\Gamma$ (Sink Weights): This is a diagonal matrix where the values are based on how many times the agent has visited each state. Heavily visited states act as "sinks" that pull the values of the eigenvectors toward zero.
  • Eigenvectors as Gradients: NEO calculates the "smoothest" eigenvectors of this matrix. Because of the sink weights, the peaks of these eigenvectors naturally align with the most novel (least visited) regions.
3D visualization of an eigenvector surface over a maze environment, demonstrating how NEO creates gradients toward novel regions.

The algorithm follows a simple loop:

  1. Execute the current policy and record transitions and visitation counts.
  2. Construct the Source Laplacian using a scaled version of these counts.
  3. Compute the top $Z$ eigenvectors.
  4. Create options (temporally extended actions) that follow the gradient of these eigenvectors toward their peaks.
  5. Because eigenvectors are orthogonal, each option naturally points toward a different novel region, preventing the agent from putting all its eggs in one basket.

Key Insights and Ideas

  • Converting Novelty to Energy: By adding visitation counts to the diagonal of the Laplacian, the authors effectively turn "novelty" into a physical-like potential. The math forces the "energy" of the eigenvectors to concentrate in unvisited states.
  • Solving the Directed Graph Hurdle: Most Laplacian methods fail in directed graphs because the math becomes unstable, resulting in complex eigenvalues. NEO’s construction stabilizes these values, providing guaranteed directed paths to novel states.
  • The "Backtracking" Trap: Standard Eigen-options often rely on the "Fiedler vector," which might have one end anchored in a very popular state. If an agent follows it blindly, it might spend half its time running back to the start. NEO avoids this by specifically weighting against visited states.
  • Diversity through Orthogonality: Since eigenvectors are orthogonal, they are mathematically independent. If you generate four exploration options, they will likely lead the agent to four distinct corners of the map.
Eigenvector gradient mapped over a four-room gridworld, highlighting how the Source Laplacian identifies distinct unvisited areas.

Empirical Performance

The authors evaluated NEO across a diverse suite of eight environments, ranging from simple grids (Four Rooms, Large Maze) to complex directed graphs (Tower of Hanoi, a directed Torus, and a massive directed graph of New York City streets with 10,000 nodes).

NEO consistently outperformed state-of-the-art exploration methods like Eigen-options and Cover-options:

  • Superior Learning: In sparse-reward tasks, NEO reached the goal significantly faster and more reliably across almost all domains.
  • State Coverage: In the largest environments, NEO visited roughly twice as many unique states as its competitors within the same timeframe.
  • Robustness in Directed Space: NEO was the only spectral method that functioned effectively in the 10,000-node NYC street graph, where other solvers crashed or failed to provide useful guidance.

Limitations and Future Work

While highly effective, NEO currently operates on discrete state spaces where a graph can be explicitly built. Extending this framework to continuous spaces—such as robotics or high-resolution video games—remains a major next step. Additionally, calculating eigenvectors for massive graphs can be computationally expensive, though recent approximation methods for Laplacians could help scale NEO to even larger environments. Finally, future research could explore how these learned "novelty-seeking" skills might transfer to entirely new maps, rather than learning exploration policies for one specific environment at a time.

Summary updated

Abstract

Efficient exploration remains one of the most important open problems in reinforcement learning. Discovering novel states or transitions requires policies that efficiently direct the agent away from the regions of the state space that are already well explored. We introduce Novel Exploration via Orthogonality (NEO), an approach that automatically uncovers not only which regions of the environment are novel but also how to reach them by leveraging Laplacian representations. NEO uses the eigenvectors of a modified graph Laplacian to induce gradient flows from states that are frequently visited (less novel) to states that are seldom visited (more novel). We show that NEO's modified Laplacian yields eigenvectors whose extreme values align with the most novel regions of the state space. We provide bounds for the eigenvalues of the modified Laplacian; and we show that the smoothest eigenvectors with real eigenvalues below certain thresholds provide guaranteed gradients to novel states for both undirected and directed graphs. In an empirical evaluation in online, incremental settings, NEO outperformed related state-of-the-art approaches, including eigen-options and cover options, in a large collection of undirected and directed environments with varying connectivity structures.
BibTeX
@inproceedings{theophilou2025novel,
  author = {Andreas Theophilou and Özgür Şimşek},
  title = {{Novel Exploration via Orthogonality}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=yJS1eZSNUv},
}
Figure