Go-Explore

Why Does This Exist?

In reinforcement learning, environments with sparse, delayed rewards and long-horizon bottlenecks represent the hardest exploration benchmark. For years, benchmark Atari games like Montezuma's Revenge and Pitfall! defeated state-of-the-art model-free RL algorithms, including Deep Q-Networks (DQN), Proximal Policy Optimization (PPO), Rainbow, and distributed actor-critic architectures. Even intrinsic motivation mechanisms—such as prediction-error curiosity (ICM) or count-based exploration bonuses—struggled to achieve consistent progress across multi-room mazes.

Standard reinforcement learning methods fail in these environments because they fundamentally couple state space exploration with policy optimization. When an agent relies on standard exploratory noise (such as $\epsilon$-greedy action selection, Gaussian perturbations, or policy entropy bonuses) while simultaneously updating its policy parameters, it falls prey to two fatal exploration pathologies:

1. Detachment: An agent's exploratory policy discovers a promising frontier (e.g., reaching the entrance of a second room). However, as the agent explores the local neighborhood, its intrinsic novelty bonuses rapidly diminish. Before the agent can fully exhaust the frontier, policy parameter updates or environment non-stationarity cause it to wander away. Because standard RL stores knowledge solely in neural network weights rather than an explicit state archive, the agent forgets how to reach that frontier and rarely rediscovers it.
2. Derailment: To reach a deeply nested frontier state at depth $d = 100$ in a complex environment, the agent must execute a precise, coordinated sequence of 100 actions (e.g., jumping across conveyor belts, dodging rolling skulls, and timing rope swings). If the exploration mechanism injects exploratory stochasticity at every step along the way, the probability of executing the precise trajectory collapses exponentially. The exploratory noise meant to discover new states inevitably derails the agent before it can even return to the frontier!

Introduced by Ecoffet et al. (Nature 2021), Go-Explore solves this fundamental dilemma by separating exploration into two distinct phases:

• Phase 1 (Explore Until Solved): Build an explicit archive of discovered environmental states. Instead of exploring from the initial start state $s_0$ every episode, the agent selects a promising cell from the archive, returns directly to that exact state without exploratory noise, and only then explores onward.
• Phase 2 (Robustification): Once a high-scoring trajectory is discovered, extract a robust, closed-loop deep neural network policy via imitation learning and domain randomization so the agent can execute the solution from scratch under stochastic environmental noise.

Think of It Like This

How It Actually Works

Detachment, Derailment, and the Two-Phase Exploration Paradigm

Go-Explore formalizes environment navigation as a search process over an expanding discrete cell archive $\mathcal{A}_{\text{archive}}$, decoupling search tree expansion from policy representation.

1+-------------------------------------------------------------------------------+2|                       PHASE 1: EXPLORE UNTIL SOLVED                          |3|                                                                               |4|   +-------------------+  1. Select   +-------------------+                    |5|   |   Cell Archive    | -----------> |   Return to Cell  | (No noise added;   |6|   |  A_archive = {c}  |              |    without drift  |  derailment cured) |7|   +-------------------+              +-------------------+                    |8|             ^                                  |                              |9|             | 4. Map &                         | 2. Reached frontier          |10|             |    Update                        v                              |11|             |                        +-------------------+                    |12|             +----------------------- |   Explore Onward  | (k steps of        |13|                  (Detachment cured)  |    from frontier  |  stochastic noise) |14|                                      +-------------------+                    |15+-------------------------------------------------------------------------------+16                                      |17                                      | Discovered Winning Trajectory tau*18                                      v19+-------------------------------------------------------------------------------+20|                         PHASE 2: ROBUSTIFICATION                              |21|                                                                               |22|   Trajectory tau* ----> Backward Algorithm ----> Deep Policy pi_theta(a | s) |23|   (Open-loop path)      + Environmental Noise     (Closed-loop neural net)    |24+-------------------------------------------------------------------------------+

1. Cell Representation and Archive Structure

Let $s \in \mathcal{S}$ denote a high-dimensional observation (e.g., an Atari frame). A downsampling function $d: \mathcal{S} \to \mathcal{C}$ maps $s$ to a discrete cell identifier $c \in \mathcal{C}$ (for example, downsampling an image to $11 \times 8$ grayscale pixels with 8 intensity levels).

The archive $\mathcal{A}_{\text{archive}}$ maps each discovered cell $c$ to a tuple: $\mathcal{A}_{\text{archive}}[c] = \big( \tau(c), V(c), S(c), s_c \big)$ where:

• $\tau(c) = (a_0, a_1, \dots, a_{T-1})$ is the stored action trajectory leading from start state $s_0$ to cell $c$.
• $V(c) \in \mathbb{N}_{\ge 1}$ is the cumulative visitation count (the number of times cell $c$ has been chosen for exploration).
• $S(c) \in \mathbb{R}$ is the cumulative environment return achieved upon reaching cell $c$.
• $s_c$ is the underlying environment simulator state for cell $c$.

2. Phase 1: The Four-Step Discovery Loop

The agent repeats four core steps until the environment is solved or a computation budget is exhausted:

1. Step A — Select a Promising Cell: A cell $c$ is sampled from the archive according to a probability distribution $P(c)$ proportional to an exploration weight $W(c)$: $P(c) = \frac{W(c)}{\sum_{c' \in \mathcal{A}_{\text{archive}}} W(c')}$ The heuristic weight function balances novelty (inversely proportional to visitation count) and task performance (proportional to cumulative score): $W(c) = \frac{1}{\sqrt{V(c)}} \left( 1 + \frac{S(c)}{S_0} \right)$ where $S_0 > 0$ is a normalization constant. Cells that have been chosen fewer times receive higher weight, while cells that accumulated higher scores are prioritized to deepen promising branches.

2. Step B — Return to Cell: The agent travels to cell $c$ without exploratory noise:

   • With simulator state reset: The simulator's internal state is restored directly to $s_c$.
   • Without simulator reset (action replay): In non-resettable environments, the agent resets to $s_0$ and deterministically replays the stored action sequence $\tau(c)$. Because zero exploratory stochasticity is injected during transit, the agent reaches the exact frontier state with $100\%$ reliability, completely eliminating derailment.

3. Step C — Explore Onward: From state $s_c$, the agent executes $k$ exploratory actions (e.g., $k \in [20, 100]$ steps sampled from a uniform random action distribution or an intrinsic curiosity policy).

4. Step D — Map and Update Archive: At each step during exploration, the agent visits a state $s'$ with cumulative score $S'$ and trajectory $\tau'$. The state is mapped to cell $c' = d(s')$.

   • Novel Cell: If $c' \notin \mathcal{A}_{\text{archive}}$, add $c'$ to the archive with $V(c') = 1$, $S(c') = S'$, and $\tau(c') = \tau'$.
   • Better Trajectory: If $c' \in \mathcal{A}_{\text{archive}}$, compare $(S', |\tau'|)$ with existing entry $(S(c'), |\tau(c')|)$. If $S' > S(c')$, or if $S' = S(c')$ and $|\tau'| < |\tau(c')|$ (a shorter path to the same state), replace the stored trajectory and score. Because all discovered cells remain permanently in $\mathcal{A}_{\text{archive}}$, frontiers are never abandoned or forgotten, completely eliminating detachment.

3. Phase 2: Policy Robustification

Phase 1 produces an open-loop trajectory $\tau^*$ that achieves a high score, but open-loop sequences are brittle: if the test environment introduces stochastic transitions (e.g., sticky actions where actions are repeated with probability $0.25$), an open-loop sequence fails.

Phase 2 trains a closed-loop neural network policy $\pi_\theta(a \mid s)$ to reproduce $\tau^*$ robustly:

• The Backward Algorithm: Training directly from $s_0$ across a 5,000-step trajectory suffers from severe credit assignment degradation. Instead, the agent is initialized near the end of $\tau^*$ (at step $T - k$), learning via reinforcement learning (e.g., PPO) or imitation learning (Behavioral Cloning / DAgger) to reach the goal from the final states.
• Progressive Unrolling: As the policy achieves high success from $T - k$, the start position is moved backward along $\tau^*$ toward $s_0$ until the policy can reliably complete the full task from the initial state $s_0$ under stochastic noise.

Worked numerical example

Consider a 2D navigation gridworld with an archive containing three discovered cells:

$\mathcal{A}_{\text{archive}} = \{C_1, C_2, C_3\}$

The cells possess the following properties:

• Cell $C_1$ (Initial corridor): Visited $V(C_1) = 10$ times, cumulative score $S(C_1) = 0$, trajectory length $|\tau(C_1)| = 5$.
• Cell $C_2$ (Key chamber): Visited $V(C_2) = 2$ times, cumulative score $S(C_2) = 50$, trajectory length $|\tau(C_2)| = 10$.
• Cell $C_3$ (Deep frontier room): Visited $V(C_3) = 1$ time, cumulative score $S(C_3) = 100$, trajectory length $|\tau(C_3)| = 15$.

Let the score normalization scale be $S_0 = 100$.

Step 1: Compute Cell Exploration Weights

We evaluate the exploration weight function: $W(c) = \frac{1}{\sqrt{V(c)}} \left(1 + \frac{S(c)}{100}\right)$

1. For Cell $C_1$: $W(C_1) = \frac{1}{\sqrt{10}} \left(1 + \frac{0}{100}\right) = \frac{1}{3.162277} \times 1.0 = 0.3162$

2. For Cell $C_2$: $W(C_2) = \frac{1}{\sqrt{2}} \left(1 + \frac{50}{100}\right) = \frac{1}{1.414213} \times 1.5 = 0.707106 \times 1.5 = 1.0607$

3. For Cell $C_3$: $W(C_3) = \frac{1}{\sqrt{1}} \left(1 + \frac{100}{100}\right) = 1.0000 \times 2.0 = 2.0000$

Step 2: Compute Selection Probabilities

Summing the individual weights yields total archive weight: $W_{\text{total}} = 0.3162 + 1.0607 + 2.0000 = 3.3769$

The normalized selection probabilities are: $P(C_1) = \frac{0.3162}{3.3769} \approx 0.0936 \quad (9.36\%)$ $P(C_2) = \frac{1.0607}{3.3769} \approx 0.3141 \quad (31.41\%)$ $P(C_3) = \frac{2.0000}{3.3769} \approx 0.5923 \quad (59.23\%)$

Cell $C_3$ dominates the selection probability ($59.23\%$) because its rare visitation count ($V=1$) and high score ($S=100$) designate it as the primary unexhausted frontier.

Step 3: Return, Explore, and Archive Update

• Return: The agent selects cell $C_3$ and deterministically replays its 15-step trajectory $\tau(C_3)$ without exploratory noise, landing exactly at state $(5, 5)$.
• Explore: From state $(5, 5)$, the agent executes $k = 3$ exploratory actions, reaching a newly discovered state $(6, 7)$ and obtaining an additional reward of $+20$.
• Archive Update:
  • The new state maps to novel cell $C_4$.
  • New trajectory length: $15 + 3 = 18$ steps.
  • New cumulative score: $100 + 20 = 120$.
  • Cell $C_4$ is added to the archive with $V(C_4) = 1$, $S(C_4) = 120$, and $|\tau(C_4)| = 18$.
  • The visitation counter of selected cell $C_3$ increments from $1$ to $2$.

Code

Below is a complete, self-contained Python implementation of the Go-Explore Phase 1 archive, selection weighting, deterministic return, exploratory stepping, and archive updates.

1import math2from dataclasses import dataclass3from typing import Dict, List, Optional, Tuple4
5
6@dataclass7class CellEntry:8    """Represents a discovered state in the Go-Explore archive."""9    cell_id: str10    visitation_count: int11    score: float12    trajectory: List[int]13    state: Tuple[int, int]14
15
16class GoExploreArchive:17    """Manages Phase 1 cell archiving, selection weighting, and state exploration18
19    for hard-exploration reinforcement learning environments.20    """21
22    def __init__(self, score_scale: float = 100.0) -> None:23        self.archive: Dict[str, CellEntry] = {}24        self.score_scale = score_scale25
26    def add_or_update(27        self,28        cell_id: str,29        score: float,30        trajectory: List[int],31        state: Tuple[int, int],32        initial_visits: int = 1,33    ) -> bool:34        """Adds a new cell or updates an existing entry if the new trajectory yields35
36        a strictly higher score or an equal score with fewer steps.37        """38        if cell_id not in self.archive:39            self.archive[cell_id] = CellEntry(40                cell_id=cell_id,41                visitation_count=initial_visits,42                score=score,43                trajectory=list(trajectory),44                state=state,45            )46            return True47
48        entry = self.archive[cell_id]49        if score > entry.score or (50            math.isclose(score, entry.score) and len(trajectory) < len(entry.trajectory)51        ):52            entry.score = score53            entry.trajectory = list(trajectory)54            entry.state = state55            return True56        return False57
58    def compute_cell_weights(self) -> Dict[str, float]:59        """Calculates selection weight W(c) = (1 / sqrt(visitation)) * (1 + score / S0)."""60        weights: Dict[str, float] = {}61        for cid, entry in self.archive.items():62            inv_freq = 1.0 / math.sqrt(entry.visitation_count)63            score_factor = 1.0 + (entry.score / self.score_scale)64            weights[cid] = inv_freq * score_factor65        return weights66
67    def compute_selection_probabilities(self) -> Dict[str, float]:68        """Calculates normalized selection probabilities across all archived cells."""69        weights = self.compute_cell_weights()70        total_w = sum(weights.values())71        return {cid: w / total_w for cid, w in weights.items()}72
73    def select_cell(self, target_cell: Optional[str] = None) -> str:74        """Selects a cell from the archive, incrementing its visitation count."""75        probs = self.compute_selection_probabilities()76        chosen = target_cell if target_cell is not None else max(probs, key=lambda k: probs[k])77        self.archive[chosen].visitation_count += 178        return chosen79
80    def return_to_cell(self, cell_id: str) -> Tuple[Tuple[int, int], List[int]]:81        """Phase 1 Step B: Deterministic return to frontier cell without exploratory noise."""82        entry = self.archive[cell_id]83        return entry.state, list(entry.trajectory)84
85
86def run_go_explore_simulation() -> None:87    # Initialize archive with worked example data88    archive = GoExploreArchive(score_scale=100.0)89    archive.add_or_update("C1", score=0.0, trajectory=[0] * 5, state=(0, 1), initial_visits=10)90    archive.add_or_update("C2", score=50.0, trajectory=[0] * 10, state=(2, 3), initial_visits=2)91    archive.add_or_update("C3", score=100.0, trajectory=[0] * 15, state=(5, 5), initial_visits=1)92
93    # Step 1: Compute weights and probabilities94    weights = archive.compute_cell_weights()95    probs = archive.compute_selection_probabilities()96    total_w = sum(weights.values())97
98    print("--- Phase 1: Archive Cell Weights ---")99    for cid in ["C1", "C2", "C3"]:100        print(f"{cid}: Weight = {weights[cid]:.4f}, Prob = {probs[cid]:.4f}")101    print(f"Total Archive Weight: {total_w:.4f}")102
103    # Step 2: Select frontier cell C3 and return104    chosen = archive.select_cell("C3")105    state, traj = archive.return_to_cell(chosen)106    print(f"\nSelected Cell: {chosen}")107    print(f"Returned to State: {state}, Trajectory Length: {len(traj)}")108
109    # Step 3: Explore forward k=3 steps110    new_state = (state[0] + 1, state[1] + 2)111    new_score = archive.archive[chosen].score + 20.0112    new_traj = traj + [1, 2, 0]113
114    # Step 4: Archive update with novel cell C4115    archive.add_or_update("C4", score=new_score, trajectory=new_traj, state=new_state, initial_visits=1)116
117    c4_entry = archive.archive["C4"]118    c3_entry = archive.archive["C3"]119    print("\n--- Archive Update ---")120    print(121        f"Added Cell C4: Score = {new_score:.1f}, "122        f"Trajectory Length = {len(new_traj)}, Visited = {c4_entry.visitation_count}"123    )124    print(f"C3 New Visitation Count: {c3_entry.visitation_count}")125
126    # Step 5: Automated validation assertions127    assert math.isclose(weights["C1"], 0.3162, abs_tol=1e-3), "C1 weight mismatch"128    assert math.isclose(weights["C2"], 1.0607, abs_tol=1e-3), "C2 weight mismatch"129    assert math.isclose(weights["C3"], 2.0000, abs_tol=1e-3), "C3 weight mismatch"130    assert math.isclose(total_w, 3.3769, abs_tol=1e-3), "Total weight mismatch"131    assert math.isclose(probs["C3"], 0.5923, abs_tol=1e-3), "C3 selection probability mismatch"132    assert len(archive.archive) == 4, "Archive should contain 4 cells"133    assert c4_entry.score == 120.0, "C4 score should be 120"134    print("\nAll assertions passed successfully!")135
136
137if __name__ == "__main__":138    run_go_explore_simulation()

1# -> expected output:2--- Phase 1: Archive Cell Weights ---3C1: Weight = 0.3162, Prob = 0.09364C2: Weight = 1.0607, Prob = 0.31415C3: Weight = 2.0000, Prob = 0.59236Total Archive Weight: 3.37697
8Selected Cell: C39Returned to State: (5, 5), Trajectory Length: 1510
11--- Archive Update ---12Added Cell C4: Score = 120.0, Trajectory Length = 18, Visited = 113C3 New Visitation Count: 214
15All assertions passed successfully!

Watch Out For

The Quick Version

• Two Deadly Pathologies: Standard deep RL fails on hard exploration because exploratory noise causes derailment (perturbing actions along narrow paths before reaching frontiers) and detachment (abandoning promising frontiers once local curiosity fades).
• Two-Phase Decoupling: Go-Explore resolves this by separating state discovery from policy extraction: Phase 1 builds an archive of discovered cells via return-and-explore, while Phase 2 extracts a robust closed-loop policy.
• Noise-Free Return: By restoring simulator states or deterministically replaying action sequences to the frontier without injecting exploratory noise, the agent eliminates derailment.
• Novelty and Performance Weighting: Cells in the archive are sampled proportional to $W(c) = \frac{1}{\sqrt{V(c)}} (1 + S(c)/S_0)$, aggressively prioritizing rarely visited states that produced high cumulative rewards.
• Phase 2 Robustification: The backward algorithm trains a deep neural network policy backward from the goal under environmental noise, transforming brittle open-loop trajectories into reliable policies that solve games like Montezuma's Revenge from start to finish.

What to Read Next

• Curiosity-Driven Exploration (ICM)
• Random Network Distillation (RND)
• Count-Based Exploration
• Variational Information Maximising Exploration (VIME)