TL;DR
E3B is a novel reinforcement learning (RL) exploration method that replaces brittle, discrete "state-counting" bonuses with a continuous elliptical bonus. By combining this geometric approach with embeddings learned via inverse dynamics, the agent can effectively explore complex, procedurally generated environments without needing hand-engineered features or being distracted by uncontrollable noise.
The Challenge of Exploration in Procedural Environments
In reinforcement learning, "exploration" is the challenge of finding rewards in sparse environments where an agent might wander for thousands of steps before seeing a single positive signal. To solve this, researchers use intrinsic rewards (or bonuses)—essentially "curiosity" signals that reward the agent for visiting novel states.
However, most current exploration methods are designed for "singleton" tasks where the environment is identical every time. In more realistic Contextual Markov Decision Processes (CMDPs)—like procedurally generated levels where the layout changes every episode—standard novelty measures fail. If every episode is unique, everything looks new.
Existing solutions often rely on "episodic counts" (counting how many times a state was seen within the current episode). But these methods break down in high-dimensional or noisy spaces. For example, if a clock on the screen changes every second, a discrete counter will treat every frame as a "new state," trapping the agent in a loop of watching the clock rather than exploring the room.
Introducing E3B
To address these limitations, the authors introduce Exploration via Elliptical Episodic Bonuses (E3B), which consists of two main components:
- The Elliptical Bonus: Instead of a hash table that counts discrete states, E3B fits an "ellipse" (a covariance matrix) to the embeddings of all states visited in the current episode. The intrinsic reward for a new state is proportional to how far it lies outside this ellipse. Mathematically, this uses the bilinear form $b(s_t) = \phi(s_t)^T C_{t-1}^{-1} \phi(s_t)$, where $C$ is the unnormalized covariance matrix.
- Inverse Dynamics Embeddings: To ensure the agent isn't distracted by uncontrollable "noise" (like moving clouds or background textures), the state embedding $\phi$ is learned using an inverse dynamics model. The model is trained to predict which action $a_t$ was taken to get from state $s_t$ to $s_{t+1}$. This forces the encoder to ignore any part of the environment the agent cannot control.
- Computational Efficiency: Inverting a matrix at every step is expensive ($O(d^3)$). E3B uses the Sherman-Morrison identity to perform rank-1 updates to the inverse covariance matrix in $O(d^2)$ time, making it scalable to long episodes.
Key Insights
- Episodic Memory is Essential: The paper demonstrates that popular methods like RIDE, AGAC, and NovelD actually fail completely in CMDPs if their episodic counting term is removed. The "within-episode" novelty is the primary driver of their success.
- Generalizing the Count: The elliptical bonus is a "natural generalization" of count-based bonuses. In a tabular setting with one-hot encodings, the elliptical bonus mathematically reduces to $1/N_e(s_t)$ (the inverse of the episodic count).
- Avoiding the "Position Trap": Many RL researchers inadvertently "cheat" by giving agents their exact $(x, y)$ coordinates to help them explore. E3B achieves state-of-the-art results using only raw observations (pixels or symbolic grids), proving that learned embeddings can replace hand-engineered spatial features.
Key Results
The authors evaluated E3B across three distinct types of environments: MiniHack, VizDoom, and Habitat (HM3D).
- MiniHack: E3B set a new state-of-the-art across 16 challenging, procedurally generated tasks based on the game NetHack. Notably, it outperformed specialized versions of NovelD that were given "cheats" like agent position or textual messages.
- Habitat: In photorealistic 3D environments, E3B was tested on "reward-free exploration," where the goal is simply to map as much of a house as possible. E3B revealed significantly more of the map than RND, ICM, or NovelD, proving much more effective at pushing into new rooms rather than retreading familiar ground.
- VizDoom: E3B matched the performance of the best existing methods on sparse-reward pixel tasks, showing it is robust across both symbolic and visual inputs.
Limitations and Future Work
- Large Action Spaces: E3B (and all other tested methods) struggled on MiniHack tasks when the full action space (dozens of commands) was enabled, suggesting that exploration in high-dimensional action spaces remains an open problem.
- Long-term Memory: While E3B is excellent at "within-episode" diversity, it doesn't explicitly address "across-episode" novelty. Integrating E3B with global novelty bonuses could help agents remember what they learned in previous attempts.
- Advanced Feature Learning: While inverse dynamics are robust, they might discard useful "passive" information (like a moving platform the agent can't control but can ride). Exploring other self-supervised objectives for the embedding remains a promising path.
Summary updated