---
title: "Exploration in Deep RL: Posterior Sampling and Go-Explore"
module: Modern Deep Reinforcement Learning
moduleNumber: 5
lessonNumber: 8
order: 508
summary: >
  A companion to the novelty-as-reward lesson. Pseudo-counts and curiosity reward the
  unfamiliar after the agent stumbles into it; this lesson covers two ideas that go
  further. Bootstrapped DQN keeps an ensemble that approximates a posterior over value
  functions and explores by committing to one sampled hypothesis per episode — the
  deep, directed exploration ε-greedy cannot manage. Go-Explore remembers and returns
  to the frontier, defeating detachment and derailment to solve Montezuma's Revenge.
  We close with episodic memory (Never Give Up), Agent57, and model-based exploration.
topics: [Deep RL]
sources:
  - book: Grokking Deep RL
    ref: "Ch. 4 — Balancing the gathering and use of information; strategic exploration"
  - book: Grokking Deep RL
    ref: "Ch. 10 — Sample-efficient value-based methods; exploration in high dimensions"
---

This builds on
[Exploration in Deep RL: Novelty as Reward](/reinforcement-learning/modern-deep-rl/exploration),
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^i_t$ 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**.[^osband] 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.

```algorithm
caption: $\textsc{Bootstrapped-DQN}$ — deep exploration by posterior sampling
input: number of heads $K$, masking probability $p$
initialize shared network with $K$ value heads $Q_1, \ldots, Q_K$
for each episode do
  sample a head $k \sim \text{Uniform}\{1, \ldots, K\}$
  initialize state $S$
  repeat
    $A \gets \arg\max_a Q_k(S, a)$ // commit to head $k$ all episode
    take action $A$, observe $R$, $S'$
    draw a mask $m \in \{0,1\}^K$, each $m_j \sim \text{Bernoulli}(p)$
    store $(S, A, R, S', m)$ in replay buffer
    sample a minibatch and update each head $Q_j$ on transitions with $m_j = 1$
    $S \gets S'$
  until $S$ is terminal
```

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.

$$
% caption: Bootstrapped DQN approximates a posterior over value functions with
% $K$ heads on a shared trunk, each trained on a bootstrap of the data. Heads
% agree on well-explored states and disagree on novel ones; sampling one head
% per episode and following it greedily yields committed, directed exploration.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=20mm, minimum height=11mm, align=center, font=\scriptsize},
  head/.style={draw, minimum width=15mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (in) at (0,0) {state s};
  \node[box, draw=acc, text=acc] (trunk) at (3.4,0) {shared trunk};
  \node[head] (h1) at (7.0,1.7) {head Q1};
  \node[head] (h2) at (7.0,0.4) {head Q2};
  \node[font=\small] at (7.0,-0.7) {. . .};
  \node[head, draw=acc, text=acc] (hk) at (7.0,-1.9) {head QK};
  \draw[->, acc, thick] (in) -- (trunk);
  \draw[->, black] (trunk) -- (h1);
  \draw[->, black] (trunk) -- (h2);
  \draw[->, acc, thick] (trunk) -- (hk);
  \node[anchor=west, font=\scriptsize, text=acc] at (8.4,-1.9) {sampled this episode};
\end{tikzpicture}
$$

> **Definition (Bootstrapped DQN).** A value-based agent that maintains $K$
> $Q$-value heads on a shared feature trunk, each trained on an independent
> bootstrap of the replay data, so the ensemble approximates a posterior over
> value functions. Exploration is by posterior sampling with temporal
> commitment: at the start of each episode one head is drawn and followed
> greedily throughout, producing the deep, directed exploration that undirected
> per-step randomization cannot.

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**.[^ecoffet] _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:

```algorithm
caption: $\textsc{Go-Explore}$ — archive promising states, return, then explore
initialize archive with the start state and its (empty) trajectory
repeat
  select a cell $c$ from the archive // bias toward promising / rarely-chosen cells
  return to $c$ by replaying its stored trajectory // no exploration on the way back
  explore from $c$ for a short horizon // e.g. random or policy actions
  for each state $s'$ newly reached do
    if $s'$ maps to a new cell or a shorter path to its cell then
      add or update $s'$ in the archive with the trajectory that reached it
until budget exhausted
robustify the best archived trajectories into a policy // imitation learning
```

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.

$$
% caption: Go-Explore keeps an archive of reached cells. Each iteration selects a
% promising cell, returns to it reliably (replaying a stored trajectory rather
% than exploring), then explores a short horizon from there. New cells are
% archived, so the frontier is never forgotten (no detachment) and returning
% never fails (no derailment).
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc] (arc) at (0,0) {archive of cells};
  \node[box] (sel) at (3.9,0) {select a cell};
  \node[box, draw=acc, text=acc] (ret) at (7.8,0) {return\\(replay path)};
  \node[box, draw=red, text=red] (exp) at (7.8,-2.3) {explore\\from cell};
  \node[box] (add) at (3.9,-2.3) {add new cells};
  \draw[->, acc, thick] (arc) -- (sel);
  \draw[->, black] (sel) -- (ret);
  \draw[->, red, thick] (ret) -- (exp);
  \draw[->, black] (exp) -- (add);
  \draw[->, acc, thick] (add) -- (arc);
\end{tikzpicture}
$$

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](/reinforcement-learning/foundations/markov-decision-processes)
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.

> **Definition (Go-Explore).** A two-phase exploration algorithm that maintains
> an archive mapping distinct states (grouped into cells) to trajectories that
> reach them. Each iteration selects a promising cell, _returns_ to it by
> replaying its stored trajectory (avoiding derailment from exploratory noise),
> _explores_ from there, and archives any new cells (avoiding detachment from the
> frontier). A final robustification phase distills the best trajectories into a
> policy by imitation learning.

## 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](/reinforcement-learning/modern-deep-rl/model-based-rl)
and [value-based](/reinforcement-learning/modern-deep-rl/distributional-and-rainbow)
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).[^ngu] The intrinsic reward is the product of
the fast episodic signal $r^{epi}_t$ and the slow lifelong (RND-style) modulator $\alpha_t \in
[1, L]$,

$$
r^i_t = r^{epi}_t \cdot \min(\max(\alpha_t, 1), L), \qquad r^{epi}_t = \frac{1}{\sqrt{\textstyle\sum_{f \in N_k} K(f, f_t)} + c},
$$

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](/reinforcement-learning/modern-deep-rl/distributional-and-rainbow)
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.[^agent57ex] 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^e_t + \beta_j\, r^i_t$. A
meta-controller — a bandit, closing the loop back to the
[bandit lesson](/reinforcement-learning/foundations/multi-armed-bandits) 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.[^plan2explore] 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^i_t = \tfrac{1}{B}\sum_i \big\| \hat f_i(z_t, a_t) -
\bar f(z_t, a_t) \big\|^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.

$$
% caption: Two axes the post-RND methods added. Lifelong novelty (top, RND-style)
% fades slowly over training; episodic novelty (bottom, NGU) resets each episode to
% drive within-episode exploration; their product is the NGU reward. Plan2Explore
% instead plans toward predicted model disagreement, exploring before any task reward.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc] (life) at (0,1.2) {lifelong novelty\\(fades over training)};
  \node[box, draw=red, text=red] (epi) at (0,-1.2) {episodic novelty\\(resets each episode)};
  \node[circle, draw, minimum size=8mm] (mul) at (4.6,0) {x};
  \node[box, thick] (ngu) at (8.6,0) {NGU intrinsic\\reward};
  \draw[->, acc, thick] (life.east) -- (mul);
  \draw[->, red, thick] (epi.east) -- (mul);
  \draw[->, black, thick] (mul) -- (ngu);
\end{tikzpicture}
$$

## 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^i_t$, and let the return-maximizing agent chase it via $r_t = r^e_t + \beta r^i_t$. The
count-based archetype recovers the bandit's UCB bonus directly, $r^i_t = 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.

| Method | Novelty signal | Recovers | Cost |
| --- | --- | --- | --- |
| Pseudo-counts | density-model surprise $\to \hat N(s)$ | UCB's $1/\sqrt{N}$ bonus | a density model |
| Hash counts | count of state's hash code | UCB's count, cheaply | a hash + table |
| ICM | forward-model error in controllable features | curiosity, noise-filtered | inverse + forward nets |
| RND | error vs. a fixed random net | novelty, noise-proof | one extra net |
| Bootstrapped DQN | ensemble disagreement | Thompson posterior + commitment | $K$ value heads |
| Go-Explore | new cell in an archive | directed frontier growth | an archive + replay |

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](/reinforcement-learning/foundations/multi-armed-bandits) 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.


[^osband]: **Osband, Blundell, Pritzel, Van Roy** (2016), "Deep Exploration via Bootstrapped DQN", _NeurIPS_ — approximates a posterior over value functions with an ensemble of bootstrapped $Q$-heads on a shared network, and explores by sampling one head per episode and following it greedily, achieving temporally-extended deep exploration.
[^ecoffet]: **Ecoffet, Huizinga, Lehman, Stanley, Clune** (2021), "First Return, Then Explore", _Nature_ — the Go-Explore family: an archive of reached cells with return-then-explore, diagnosing detachment and derailment as the failures of intrinsic-reward exploration, solving Montezuma's Revenge and Pitfall before robustifying trajectories into a policy by imitation learning.
[^ngu]: **Badia, Sprechmann, Vitvitskyi, Guo, Piot, Kapturowski, Tieleman, Arjovsky, Pritzel, Bolt, Blundell** (2020), "Never Give Up: Learning Directed Exploration Strategies", _ICLR_ — combines a slow lifelong novelty (RND-style) with a fast episodic novelty from a per-episode memory scored by $k$-nearest-neighbor distance in an embedding, multiplying the two so the agent explores both across training and within each episode.
[^agent57ex]: **Badia, Piot, Kapturowski, Sprechmann, Vitvitskyi, Guo, Blundell** (2020), "Agent57: Outperforming the Atari Human Benchmark", _ICML_ — a parameterized family of policies over exploration weights and discounts on a distributional Q-learning core with the Never-Give-Up intrinsic reward, and a bandit meta-controller selecting the policy per episode; the first agent above the human baseline on all 57 Atari games, including the hard-exploration holdouts.
[^plan2explore]: **Sekar, Rybkin, Daniilidis, Abbeel, Hafner, Pathak** (2020), "Planning to Explore via Self-Supervised World Models", _ICML_ — Plan2Explore: task-agnostic exploration in a Dreamer world model driven by the disagreement of an ensemble of latent one-step models (epistemic uncertainty), planning toward expected future novelty and solving downstream tasks zero-shot or with little adaptation.