Exploration in Deep RL: Posterior Sampling and Go-Explore

This builds on Exploration in Deep RL: Novelty as Reward, which showed why ε-greedy fails when reward is sparse and deep, and built the two dominant families of intrinsic reward: pseudo-counts (an approximate visit count from a density model) and curiosity (a reward for prediction error, as in ICM and RND). Both convert novelty into a reward $r_t^i$ and let the agent chase it.

Both of those reward novelty only after the agent reaches an unfamiliar state. This lesson takes two ideas that change that — a posterior over value functions that drives committed exploration, and an archive that reliably returns to the frontier — then the modern systems that combine them.

Posterior sampling: bootstrapped DQN

The three schemes above are optimism- or curiosity-driven. A different lineage, inherited from Thompson sampling on the bandit, is posterior-driven: keep a distribution over how good the actions are, sample one plausible value function from it, and act greedily with respect to that sample. On a bandit this is principled and simple — the posterior over each arm's mean has a closed form. In deep RL there is no closed-form posterior over a $Q$-network's millions of weights, so we need an approximation cheap enough to run.

Bootstrapped DQN, from Osband et al. (2016), approximates the posterior with an ensemble.¹ Instead of one $Q$-network, train $K$ heads $Q_1,\dots ,Q_K$ that share a convolutional trunk but diverge in their final layers, each head fit on a different bootstrap resampling of the experience (implemented with per-transition Bernoulli masks). Because the heads see different data and start from different initializations, they disagree about the value of poorly-explored actions and agree about well-explored ones. That disagreement is a usable approximation to the posterior spread.

The exploration mechanism is deep exploration by commitment, and it is what fixes ε-greedy's central defect. At the start of each episode, sample one head $k\sim \text{Uniform}(1,\dots ,K)$ and follow $Q_k$ greedily for the entire episode. That single head encodes one internally consistent hypothesis about the world, so acting on it produces a directed, committed trajectory — the temporally extended exploration ε-greedy can never manage, because ε-greedy re-randomizes every single step and so cannot follow any hypothesis to its conclusion.

The mask $m_j$ decides which heads learn from each transition, giving each head its own bootstrap sample of experience and keeping them diverse. As a state becomes well-explored the heads converge there and stop disagreeing, so exploration of that region naturally winds down — the ensemble spread plays the role UCB's $1/\sqrt{N}$ bonus played on the bandit, but recovered from disagreement instead of a count.

Bootstrapped DQN's cost is modest — extra heads are cheap next to the shared trunk — and it needs no separate density model, hash, or curiosity network. Its limitation is that ensemble disagreement is a coarse posterior, and on the very hardest sparse-reward tasks it is outperformed by explicit novelty bonuses. The two ideas are complementary and are often combined.

Go-Explore: remember and return

Every method so far converts novelty into a reward and relies on the RL optimizer to follow it. Ecoffet et al. (2021) argued that on the hardest problems this coupling itself is the flaw, through two failure modes they named detachment and derailment.² Detachment: an intrinsic-reward agent that wanders away from a promising but not-yet-exhausted frontier may forget it was there, because the intrinsic reward it once found has been consumed and no signal draws it back. Derailment: even when the agent remembers a promising state, its exploratory noise corrupts the long action sequence needed to return to that state, so it can never reliably build on progress it has already made.

Go-Explore attacks both by decoupling returning from exploring and maintaining an explicit archive of the distinct states (or, in practice, low-dimensional cells that group similar states) it has reached, each stored with a trajectory that reaches it. The loop is remember-and-return:

The first phase deliberately sidesteps derailment: to return to a promising cell the agent replays a known trajectory (or resets a deterministic simulator to that state) rather than trying to navigate back through noisy exploration, so it arrives reliably every time. Only after arriving does it explore, and every new cell it discovers is added to the archive — so the frontier is never forgotten, which is what defeats detachment. Because returning is reliable and the frontier persists, the archive grows outward across the whole reachable state space instead of collapsing back toward the start.

A final phase robustifies the best trajectories: the archive's paths may depend on a deterministic environment, so Go-Explore trains a neural policy to imitate them and withstand stochasticity, using imitation learning from the discovered demonstrations. Empirically, Go-Explore scored over $40,000$ points on Montezuma's Revenge and solved it in the sense of reaching past all $24$ rooms, and it cleared the previously-unsolved game Pitfall, both far beyond every reward-bonus method. The conclusion: on the hardest exploration problems, reliably remembering and returning to the frontier can matter more than any particular definition of novelty.

Beyond the reward bonus: episodic memory, model-based exploration, and Agent57

The methods above define novelty at the scale of a whole training run: RND's predictor, a density model, or an ensemble all forget slowly, so a state seen many episodes ago still reads as familiar. The work after 2019 refined when novelty should reset and tied exploration back to the model-based and value-based lines.

Never-Give-Up and episodic novelty. RND's slow-fading novelty has a cost: once the agent has thoroughly explored a region, the intrinsic reward there is gone for good, so within a single long episode it has no incentive to revisit a junction and try a different branch. Never Give Up (Badia et al., 2020) adds a second, faster novelty signal — an episodic memory $M$ that is wiped at the start of every episode and scores a state by how different it is from the states already seen this episode (a $k$-nearest-neighbor distance in an embedding).³ The intrinsic reward is the product of the fast episodic signal $r_t^{epi}$ and the slow lifelong (RND-style) modulator ${\alpha }_t\in [1,L]$,

with $N_k$ the $k$ nearest neighbors of the embedded state $f_t$ in $M$. The agent is thus pushed to visit new states both across training and within each episode — the within-episode drive that lets it keep probing a maze it has already partly mapped.

Agent57 ties exploration to value. The distributional lesson noted Agent57 (Badia et al., 2020) as the first agent above the human baseline on all 57 Atari games; the exploration side is what earned the last few.⁴ It runs the Never-Give-Up intrinsic reward on top of a distributional Q-learning core, but maintains a family of policies indexed by $({\beta }_j,{\gamma }_j)$ — the intrinsic weight ${\beta }_j$ and discount ${\gamma }_j$ — each optimizing $r_t=r_t^e+{\beta }_j{r}_t^i$. A meta-controller — a bandit, closing the loop back to the bandit lesson this course opened with — selects per episode which $j$ to run by treating undiscounted episode return as the bandit reward, so the agent behaves as a cautious exploiter (${\beta }_j$ small, ${\gamma }_j$ high) on easy games and a relentless explorer on Montezuma's Revenge without retuning. Directed exploration is a selectable mode of one agent, not a bolt-on.

Model-based exploration: Plan2Explore. Every method in this lesson so far explores then (or while) learning a task. Plan2Explore (Sekar et al., 2020) explores with no task reward at all, using a Dreamer-style world model.⁵ Its novelty signal is the disagreement of an ensemble of $B$ one-step latent models $\{{\hat{f}}_i\}$ — the variance of their predicted next latent, $r_t^i=\frac{1}{B}{\sum }_i\Vert {\hat{f}}_i(z_t,a_t)-\bar{f}(z_t,a_t){\Vert }^2$ with $\bar{f}$ the ensemble mean — the same epistemic-uncertainty idea PETS used, now driving exploration rather than cautious planning. Because the world model is learned, the agent can plan toward predicted future novelty (states the ensemble expects to disagree about) instead of only reacting to surprise after visiting a state. After a purely self-supervised exploration phase it solves downstream tasks zero-shot or with little adaptation: a good world model turns exploration into a planning problem — seek the states your model is most unsure about.

The shared blueprint

The methods differ in machinery but agree on strategy. Directed, memory-bearing exploration replaces undirected dithering, and in almost every case the mechanism is the same: score novelty, convert the score into an intrinsic reward $r_t^i$, and let the return-maximizing agent chase it via $r_t=r_t^e+\beta r_t^i$. The count-based archetype recovers the bandit's UCB bonus directly, $r_t^i=1/\sqrt{\hat{N}(S_t)}$ from an approximate visit count $\hat{N}$; every other row replaces $\hat{N}$ with a surrogate that generalizes across an astronomical state space.

Read the table against the earlier one: each row recovers one bandit tool the deep setting had broken — a count, a posterior, optimism — in a form that generalizes across an enormous state space. The exploration–exploitation tension the bandit isolated never disappeared; scale only forced us to build approximate counts and approximate posteriors, then feed them back to the agent as a reward it will pursue on its own.