What makes exploration hard
Two properties turn an ordinary task into a hard-exploration problem. First, sparse reward: the environment is silent for hundreds or thousands of steps and only pays out at the very end, so there is almost no gradient pulling the agent toward success. Second, delayed reward tangled with the credit-assignment problem: even when reward finally arrives, the agent must figure out which of its many past actions deserve the credit.
Diagram of an agent taking an action in an environment and receiving a state and reward back.
Under sparse reward, the undirected methods from Guide 1 are hopeless — random actions will essentially never chain into the long correct sequence. This is the regime where everything in this track was invented to matter.
The toolbox so far
Before the hardest cases, take stock. You now hold a layered toolbox of exploration strategies, roughly from cheapest to most powerful:
- Undirected dithering — ε-greedy, Boltzmann: trivial to add, fine when reward is close.
- Optimism & posterior — UCB, Thompson/posterior sampling: principled, provably efficient, need an uncertainty estimate.
- Count-based & pseudo-counts: scale optimism to high-dimensional states with a density model.
- Curiosity — ICM, RND: intrinsic reward for the unfamiliar; RND dodges the noisy-TV trap.
Detachment and derailment
Intrinsic-reward methods suffer from two linked pathologies on the hardest games. Detachment: the agent consumes the novelty bonus near its start, drifts off to explore some other region, and forgets about a promising but only-partly-explored frontier — it has detached from the unfinished area and may never come back. Derailment: even if it remembers a promising state, the stochastic exploration it relies on to leave that state knocks it off the long, fragile path it took to reach it in the first place.
Intrinsic-reward methods add a novelty bonus r^i to the extrinsic reward r^e — but once the bonus near the start is consumed, the agent can detach.
Together these mean the agent keeps re-exploring shallow territory and can rarely build on its own best discoveries. The frontier of progress collapses faster than it advances.
Go-Explore: remember, return, then explore
The Go-Explore algorithm attacks detachment and derailment head-on with a simple, almost obvious idea everyone else had skipped: *first reliably return to a promising state, and only then explore from it.* It keeps an explicit archive of interesting states it has reached. Each iteration it (1) picks a state from the archive, (2) returns there — by replaying the stored trajectory or resetting a deterministic simulator, not by hoping random actions reproduce the path — and (3) explores from that secured foothold, adding any new states it finds to the archive.
A branching tree of states explored outward from a remembered root node.
By separating returning from exploring, Go-Explore never derails (the return is reliable, not random) and never detaches (the archive is permanent memory). It famously was the first to solve Montezuma's Revenge and Pitfall outright, scoring far beyond previous methods. A second phase then robustifies the discovered solution — training a neural policy to imitate the archived winning trajectories so it works even when the environment is stochastic, not just in the deterministic exploration phase.
That is the arc of exploration: from a blind coin flip, to optimism and curiosity, to systems that remember where they have been and deliberately go back to push the frontier. Mastering when to reach for each tool is one of the deepest practical skills in reinforcement learning.