Exploration via Elliptical Episodic Bonuses

Mikael Henaff, Roberta Raileanu, Minqi Jiang, Tim Rocktäschel

Abstract

In recent years, a number of reinforcement learning (RL) methods have been proposed to explore complex environments which differ across episodes. In this work, we show that the effectiveness of these methods critically relies on a count-based episodic term in their exploration bonus. As a result, despite their success in relatively simple, noise-free settings, these methods fall short in more realistic scenarios where the state space is vast and prone to noise. To address this limitation, we introduce Exploration via Elliptical Episodic Bonuses (E3B), a new method which extends count-based episodic bonuses to continuous state spaces and encourages an agent to explore states that are diverse under a learned embedding within each episode. The embedding is learned using an inverse dynamics model in order to capture controllable aspects of the environment. Our method sets a new state-of-the-art across 16 challenging tasks from the MiniHack suite, without requiring task-specific inductive biases. E3B also matches existing methods on sparse reward, pixel-based VizDoom environments, and outperforms existing methods in reward-free exploration on Habitat, demonstrating that it can scale to high-dimensional pixel-based observations and realistic environments.

Introduction

Exploration remains a fundamental challenge in Reinforcement Learning (RL), particularly in Contextual Markov Decision Processes (CMDPs) where the environment configuration changes with every episode. In such settings, an agent cannot simply rely on global novelty; it must identify what is new within the specific context of its current episode. While episodic count-based bonuses have emerged as a powerful tool for these tasks, they are inherently limited by their reliance on discrete state representations.

This paper introduces Exploration via Elliptical Episodic Bonuses (E3B), a method designed to bring the benefits of episodic exploration to high-dimensional, continuous, and noisy environments. By moving from discrete counting to a geometric measure of novelty, E3B provides a robust framework for exploration that scales from grid-based games to complex 3D simulations.

The Problem: The Fragility of Counting

Most modern exploration methods utilize an "intrinsic reward" to encourage the agent to visit novel states. In procedurally generated environments, the most effective strategy has been "episodic counting"—rewarding the agent for visiting states it has not yet seen within the current episode.

However, count-based methods struggle with the "noisy TV" problem. In a high-dimensional state space, even minor irrelevant changes (like a flickering light or a ticking clock) can make every frame appear unique. This causes the count-based bonus to remain high everywhere, effectively blinding the agent to meaningful exploration. To circumvent this, researchers often resort to hand-engineered features (e.g., coordinate-based counting), which limits the agent's ability to generalize to new, complex domains where such features are not easily defined.

Methodology: Elliptical Bonuses and Controllability

E3B addresses these limitations through two primary innovations:

1. The Elliptical Bonus

Instead of maintaining a tally of discrete states, E3B maps observations into a continuous embedding space. Within each episode, the agent maintains a covariance matrix of all embeddings encountered so far. The intrinsic reward for a new state is determined by its "distance" from the distribution of previously visited states, calculated as a bilinear form using the inverse covariance matrix. If a state falls far outside the "ellipse" defined by previous observations, it is deemed novel and the agent is rewarded.

2. Inverse Dynamics for Noise Filtering

To ensure the agent focuses on meaningful features rather than environmental noise, E3B learns its embedding space using an inverse dynamics model. The encoder is trained to predict the action taken to transition from state $A$ to state $B$. This approach forces the model to ignore background elements that the agent cannot influence, as those elements provide no information about the agent's actions. This "controllability" filter allows E3B to remain effective even in visually rich or noisy environments.

Computational Optimization

To maintain efficiency during training, E3B utilizes the Sherman-Morrison identity. This matrix trick allows the agent to update the inverse covariance matrix in $O(d^2)$ time (where $d$ is the embedding dimension) rather than the standard $O(d^3)$ required for full matrix inversion. In practice, this results in significant computational speedups, making the method feasible for real-time RL training.

Experimental Evaluation

The researchers evaluated E3B across three diverse benchmarks to test its versatility and scalability:

  • MiniHack: A suite of 16 tasks based on NetHack, involving navigation and complex skill usage (e.g., using wands or potions). E3B achieved state-of-the-art results across all tasks using a single hyperparameter configuration, whereas previous methods required task-specific feature engineering.
  • VizDoom: A pixel-based environment used to test scalability to high-dimensional visual inputs. E3B matched the performance of existing specialized exploration methods in sparse-reward settings.
  • Habitat: A realistic 3D simulator of indoor environments. In reward-free exploration tasks, E3B successfully mapped significantly more area in novel house layouts than baselines like RND, ICM, or NovelD.

Key Insights

A significant finding of this research is that the episodic count-based term—often viewed as a minor heuristic in previous SOTA methods like RIDE or NovelD—is actually the primary driver of their success in contextual environments. E3B formalizes and improves this "secret sauce" by replacing discrete counts with a more general geometric framework.

Limitations and Future Work

While E3B is highly effective, it is susceptible to "action exploitation." In environments where certain actions produce unique but meaningless feedback (such as text logs in NetHack that don't change the game state), the inverse dynamics model may still capture these features, leading the agent to repeat those actions. Future research will focus on more sophisticated feature filtering and the integration of within-episode novelty with long-term, across-episode learning.

Conclusion

E3B represents a significant step forward in making episodic exploration robust for real-world applications. By combining elliptical bonuses with learned, controllable features, it provides a general-purpose exploration mechanism that excels in complex, changing, and high-dimensional worlds.

Summary updated

Abstract

In recent years, a number of reinforcement learning (RL) methods have been proposed to explore complex environments which differ across episodes. In this work, we show that the effectiveness of these methods critically relies on a count-based episodic term in their exploration bonus. As a result, despite their success in relatively simple, noise-free settings, these methods fall short in more realistic scenarios where the state space is vast and prone to noise. To address this limitation, we introduce Exploration via Elliptical Episodic Bonuses (E3B), a new method which extends count-based episodic bonuses to continuous state spaces and encourages an agent to explore states that are diverse under a learned embedding within each episode. The embedding is learned using an inverse dynamics model in order to capture controllable aspects of the environment. Our method sets a new state-of-the-art across 16 challenging tasks from the MiniHack suite, without requiring task-specific inductive biases. E3B also matches existing methods on sparse reward, pixel-based VizDoom environments, and outperforms existing methods in reward-free exploration on Habitat, demonstrating that it can scale to high-dimensional pixel-based observations and realistic environments.
BibTeX
@inproceedings{henaff2022exploration,
  author = {Mikael Henaff and Roberta Raileanu and Minqi Jiang and Tim Rocktäschel},
  title = {{Exploration via Elliptical Episodic Bonuses}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=SNQhe49TSj},
}
Figure