Go-Explore

Go-Explore splits hard search in two: first map new states by returning to frontiers without noise, then train a sturdy policy from the best path.

An archive scores cells 0.32, 1.06 and 2.00 so the frontier takes 59.2 percent of picks, then return without noise finds cell 4 at score 120

Why Does This Exist?

Sparse long horizon games beat coupled methods. Montezuma style rooms need dozens of exact moves before any payoff, and standard noise fails twice. Detachment drops a frontier once local novelty fades, because weights hold no map. Derailment shakes the agent off the narrow path back, because noise runs during transit too.

Ecoffet and coauthors split the job in Nature 2021. Phase one maps with an explicit archive, returning to cells cleanly and branching only there. Phase two turns the best open loop into a closed loop policy under noise. Use count-based exploration for mild sparsity and curiosity-driven exploration for dense novelty; use Go-Explore when depth and bottlenecks dominate.

The one idea you need first

A cell is a downsampled state bucket, like an $11 \times 8$ frame plus room and key flags. The archive stores per cell a path $\tau(c)$ , visit count $V(c)$ , and score $S(c)$ . Search happens over cells, not raw pixels.

Think of It Like This

A surveyor with a teleport beacon

A normal caver restarts at the entrance daily and stumbles along known halls, forgetting last week staircase. The surveyor keeps a logbook of rooms plus the exact route back.

Each morning the surveyor picks a thinly visited high scoring room, teleports to its door with no wandering, takes a few bold steps into the dark, and logs new rooms. Once the treasure is mapped, a runner drills the full route under rain and loose rocks until it holds.

Where it stops: caves have walls. Pixels need bucketing, and teleport needs a simulator reset or exact replay.

How It Actually Works

Cells are sampled by novelty times promise:

W(c) = \frac{1}{\sqrt{V(c)}}\left(1 + \frac{S(c)}{S_0}\right)

In words: rarely picked cells weigh more, high scoring cells weigh more, $S_0$ scales score. Normalize $W$ for pick probability $P(c)$ .

Then four steps repeat. Select $c$ by $P$ . Return with zero search noise by state restore or exact replay of $\tau(c)$ , which removes derailment. Branch for $k$ noisy steps only from $c$ . Map each landing to a cell: add if new, replace if higher score or same score with shorter path. Permanent storage removes detachment.

Phase two robustifies. The backward method starts training near the end of best path $\tau_*$ and slides the start back to $s_0$ under sticky actions and noise, via cloning or PPO, until a neural $\pi(a \mid s)$ runs it reliably.

Worked example

Archive holds $C_1$ , $C_2$ , $C_3$ with $S_0 = 100$ . Visits are $10$ , $2$ , $1$ ; scores are $0$ , $50$ , $100$ .

Weights are $W(C_1) = 1/\sqrt{10} \times 1.0 = 0.3162$ , $W(C_2) = 1/\sqrt{2} \times 1.5 = 1.0607$ , $W(C_3) = 1/1 \times 2.0 = 2.0000$ . Total is $3.3769$ . Probabilities are $0.3162/3.3769 = 9.36$ percent, $1.0607/3.3769 = 31.41$ percent, $2.0000/3.3769 = 59.23$ percent. The frontier $C_3$ dominates.

Return replays $15$ steps to $(5, 5)$ cleanly. Three search steps reach $(6, 7)$ for $+20$ . New cell $C_4$ enters with score $120$ , length $18$ , visits $1$ , while $C_3$ ticks to $2$ .

Code

Same weighting in code:

1import math2
3
4def cell_weight(visits: int, score: float, s0: float = 100.0) -> float:5    """W(c) = 1/sqrt(V) * (1 + S/S0)."""6    return (1.0 / math.sqrt(visits)) * (1.0 + score / s0)7
8
9def probs(weights: list[float]) -> list[float]:10    total = sum(weights)11    return [round(w / total, 4) for w in weights]12
13
14ws = [cell_weight(10, 0.0), cell_weight(2, 50.0), cell_weight(1, 100.0)]15print([round(w, 4) for w in ws])  # -> [0.3162, 1.0607, 2.0]16print(round(sum(ws), 4))  # -> 3.376917print(probs(ws))  # -> [0.0936, 0.3141, 0.5923]

Fractions match $9.36$ , $31.41$ and $59.23$ percent, and the new cell scores $100 + 20 = 120$ .

Watch Out For

Bucketing states too coarse or too fine

Too coarse merges key states, like with key versus without, into one hash, so the archive discards progress and stalls. Too fine treats flicker as new cells, so the archive explodes and weights go flat. The symptom is either zero new useful cells or thousands of junk cells per minute.

Include progress features like room and inventory beside pixels, prefer latent codes that ignore flicker, and watch creation rate versus score gain to tune granularity.

The Quick Version

Coupled search forgets frontiers and shakes off narrow paths back.
Archive holds cells with path, visit count and score, sampled by $1/\sqrt{V}$ times score bonus.
With visits 10, 2 and 1 and scores 0, 50 and 100, picks are 9.36, 31.41 and 59.23 percent.
Clean return plus frontier only branching finds cell 4 at score 120 and length 18.
Phase two trains backward under noise into a closed loop policy.