---
title: "Exploration in Deep RL: Novelty as Reward"
module: Modern Deep Reinforcement Learning
moduleNumber: 5
lessonNumber: 7
order: 507
summary: >
  When the state space is enormous and reward is rare, ε-greedy amounts to
  a random walk that almost never reaches the first
  reward. This lesson scales the bandit's exploration ideas up to deep RL through
  the dominant approach — manufacture a reward for novelty and let the agent chase it:
  optimism and pseudo-counts from density models, and intrinsic motivation and
  curiosity (the Intrinsic Curiosity Module and Random Network Distillation). A
  companion lesson takes up posterior sampling, Go-Explore, and the modern methods.
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"
---

The [multi-armed bandit](/reinforcement-learning/foundations/multi-armed-bandits)
isolated one problem and studied it to exhaustion: when feedback only
_evaluates_ the action you took, you must decide how much of your budget to
spend trying alternatives you have not yet measured. There the answer was
mostly settled — ε-greedy, optimistic initial values, UCB, gradient bandits,
and (in spirit) Thompson sampling all balance exploration against exploitation
in the one-state world, and they do it well.

Then the state space explodes. Modern deep RL runs on environments with more
distinct states than there are atoms in the observable universe, and rewards
that arrive once every few hundred or few thousand actions, if at all. In that
regime the bandit's tools break — not because the ideas are wrong, but because
each assumed something (a small action set, a per-arm count, a tractable
posterior) that no longer holds. This lesson is about what replaces them. One
idea runs underneath every method here:
**turn novelty into a reward the agent chases.** If we can score how surprising
or unfamiliar a state is, we can add that score to the environment's reward and
let the same [deep RL machinery](/reinforcement-learning/deep-rl/deep-q-networks)
that maximizes return also drive the agent toward the parts of the world it has
not yet seen.

This lesson builds the two count- and curiosity-based families that dominate:
pseudo-counts (an approximate visit count) and intrinsic curiosity (a reward for
prediction error). The posterior-sampling and archive-based methods — bootstrapped
DQN, Go-Explore, and the modern systems that clear Montezuma's Revenge — continue in a
[companion lesson](/reinforcement-learning/modern-deep-rl/exploration-part-2).

## Why ε-greedy fails at scale

ε-greedy explores by _dithering_: with probability $\varepsilon$ it replaces
the greedy action with a uniformly random one. On a bandit that is enough —
every arm is one action away, so uniform random selection samples all of them.
In a long-horizon environment it is a disaster, because reaching an informative
state requires a _specific sequence_ of many correct actions, and a policy that
flips a coin at every step almost surely never produces that sequence.

The clean illustration is a **hard-exploration chain**. Consider $N$ states in
a line. The agent starts at state $s_1$; every step it moves left or right. A
small reward sits at the left wall, one step away; a much larger reward sits at
the far right wall, $N-1$ steps away. Greedy exploitation grabs the near reward
immediately and never looks further. ε-greedy, when it does explore, takes one
random step — but to reach the large reward it must take $N-1$ correct steps in
a row before any signal tells it the far wall is worth anything. Under uniform
dithering the probability of a directed run of length $N-1$ decays like
$2^{-(N-1)}$: for a chain of even modest length the agent will not see the
distant reward within any practical number of episodes.

$$
% caption: A hard-exploration chain. The agent starts at $s_1$; a small reward
% sits one step left, a large reward $N-1$ steps right. Undirected
% $\varepsilon$-greedy grabs the near reward and needs a run of $N-1$ correct
% steps — probability $\sim 2^{-(N-1)}$ — to ever reach the large one.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st, draw=red, text=red] (r) at (-2.1,0) {r+};
  \node[st, draw=acc, text=acc, thick] (s1) at (0,0) {s1};
  \node[st] (s2) at (1.8,0) {s2};
  \node[st] (s3) at (3.6,0) {s3};
  \node[font=\small] (dots) at (5.1,0) {. . .};
  \node[st, draw=red, text=red, thick] (sN) at (6.6,0) {sN};
  \draw[->, black] (s1) -- (r) node[midway, above, font=\scriptsize, text=black] {left};
  \draw[->, black] (s1) -- (s2);
  \draw[->, black] (s2) -- (s3);
  \draw[->, black] (s3) -- (dots);
  \draw[->, black] (dots) -- (sN);
  \node[red, anchor=north, font=\scriptsize] at (-2.1,-0.65) {reward 0.001};
  \node[red, anchor=north, font=\scriptsize] at (6.6,-0.65) {reward 1.0};
\end{tikzpicture}
$$

Chains are contrived, but they are a faithful model of what happens in a real
game. **Montezuma's Revenge**, an Atari platformer, became the canonical
hard-exploration benchmark for exactly this reason.[^bellemare] The agent
controls a character who must descend a ladder, jump a gap, cross a moving
skull, and collect a key before any door opens — a scripted sequence of dozens
of correct actions to earn the first point. DQN with ε-greedy, which reached
superhuman scores on most Atari games, scored a flat **zero** on Montezuma's
Revenge across the whole training run: its dithering never assembled the
sequence that earns the key, so it never saw a single reward to learn from.

> **Definition (Hard-exploration problem).** A task where reward is _sparse_
> (nonzero only in a vanishingly small fraction of states) and _deep_ (reaching
> a rewarding state requires a long, specific sequence of actions). Undirected
> exploration — perturbing the policy with independent per-step randomness, as
> in ε-greedy — reaches a rewarding state with probability that decays
> exponentially in the required sequence length, so the agent effectively never
> receives a learning signal.

The failure is structural. ε-greedy has no memory of where it has been and no
preference for the unfamiliar; each random action is independent of the last, so
it cannot commit to a _direction_ long enough to explore deeply. The fixes below
all repair one of those two defects: they either count what has been visited
(memory) or reward the unfamiliar (direction), or both.

### Why the bandit tools do not lift directly

Each classical scheme assumed something the deep setting removes.

| Bandit method | What it needs | Why it breaks in deep RL |
| --- | --- | --- |
| ε-greedy | a small action set | undirected; cannot chain a deep sequence |
| Optimistic initial values | a table $Q(a)$ to seed high | a neural net's outputs cannot all be held optimistic |
| UCB | a per-arm count $N_t(a)$ | states are never revisited exactly; $N_t(s,a)$ is $0$ everywhere |
| Thompson sampling | a tractable posterior over values | no closed-form posterior for a deep $Q$-network |

Every row is a missing count or a missing posterior. The rest of the lesson
recovers _approximate_ versions of exactly these: a pseudo-count that stands in
for $N_t(s,a)$, and an ensemble that stands in for a posterior.

## Optimism and pseudo-counts

UCB's bonus $c\sqrt{\ln t / N_t(a)}$ prefers actions that have been tried little.
It is **optimism in the face of uncertainty** — treat the unknown as good until
proven otherwise. For example, fix the exploration constant
$c = 1$ and the time step $t = 1000$, so $\ln t = 6.91$. An action tried once carries a
bonus $\sqrt{6.91/1} = 2.63$; tried ten times, $\sqrt{6.91/10} = 0.83$; tried a hundred
times, $\sqrt{6.91/100} = 0.26$; tried a thousand, $0.083$. The bonus falls like
$1/\sqrt{N}$ — fast at first, then slowly — so a rarely-tried action is strongly
favored, but the pull relaxes smoothly as evidence accumulates rather than switching
off abruptly. That $1/\sqrt{N}$ curve is the exact shape every deep-RL bonus below is
trying to recover once the literal count $N$ is unavailable.

$$
% caption: The UCB exploration bonus c*sqrt(ln t / N) as a function of the visit count
% N, at t=1000. It decays like 1/sqrt(N): steep for small N, flat for large N, so
% rarely-seen actions are favored and the preference relaxes as evidence accrues. The
% count-based deep-RL methods below all rebuild this curve from a pseudo-count.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[black, ->] (0,0) -- (6.4,0) node[anchor=north east, text=black] {visit count N};
  \draw[black, ->] (0,0) -- (0,3.2) node[anchor=south east, text=black] {bonus};
  % curve: y = 2.63/sqrt(x) scaled; plot for x from 1..40 mapped to width
  % x in [1,40] -> plot at (x/40*6, value). value=2.63/sqrt(x)*1.0
  \draw[acc, very thick] plot[domain=1:40, samples=80] ({\x/40*6}, {2.63/sqrt(\x)});
  \node[acc, anchor=west, font=\scriptsize] at (5.2,2.7) {c sqrt(ln t / N)};
  % marked points at N=1,10,40
  \fill[red] ({1/40*6},2.63) circle (2pt);
  \node[red, anchor=west, font=\scriptsize] at ({1/40*6+0.1},2.63) {N=1: 2.63};
  \fill[red] ({10/40*6},0.83) circle (2pt);
  \node[red, anchor=south west, font=\scriptsize] at ({10/40*6+0.05},0.83) {N=10: 0.83};
  \node[anchor=north, font=\scriptsize, text=black] at (3.2,-0.55) {each visit shrinks the bonus, ever more slowly};
\end{tikzpicture}
$$
To carry it into deep RL we need a count $N(s)$ of how often
state $s$ has been visited, and then a reward bonus that shrinks as that count
grows. The obstacle is that in a high-dimensional state space (an Atari frame is
$210 \times 160$ pixels) the agent essentially never visits the _same_ state
twice, so the literal count $N(s)$ is $0$ for almost every $s$ and $1$ for the
handful just seen. A raw count carries no useful information.

The insight of Bellemare et al. (2016) is that even when states never repeat
exactly, a **density model** over states can tell you how _typical_ a state is,
and typicality is a smooth stand-in for a count.[^bellemare] Fit a density model
$\rho(s)$ to the states seen so far (a model that assigns a probability to any
state, generalizing across similar ones). After observing one more instance of
$s$, refit to get $\rho'(s)$. The amount by which the model's probability for $s$
_increased_ tells you how surprised it was — and a **pseudo-count** $\hat N(s)$
can be recovered from that increase so that it behaves like a real visit count on
the states the model has effectively seen.

> **Definition (Pseudo-count).** A generalized visit count $\hat N(s)$ derived
> from a learned density model $\rho$ over states, rather than from exact-match
> tallying. Writing $\rho(s)$ for the model's probability of $s$ before an update
> and $\rho'(s)$ for its probability after training on one more occurrence of $s$,
> the pseudo-count is the value consistent with treating that one update as
> adding a single count to an empirical frequency,
> $$
> \hat N(s) = \rho(s)\,\frac{1 - \rho'(s)}{\rho'(s) - \rho(s)}.
> $$
> On states the model generalizes to, $\hat N(s)$ can be large even for a state
> the agent has literally seen only once — the property that makes it useful
> where the raw count is not.

The exploration bonus is then a count-based reward, in the spirit of UCB's
$1/\sqrt{N}$: an **intrinsic reward** added to the environment's reward,
$$
r^i_t \;=\; \frac{\beta}{\sqrt{\hat N(s_t)}},
$$
large where the density model finds $s_t$ unfamiliar and decaying as
$\hat N(s_t)$ grows. Bellemare et al. combined this bonus with DQN and, for the
first time, drove meaningful progress on Montezuma's Revenge — the agent
collected keys and opened doors, states no ε-greedy agent had ever reached.

For example, suppose the density model, before
seeing $s$ again, assigns it probability $\rho(s) = 0.001$, and after one more training
update on $s$ the probability rises to $\rho'(s) = 0.0012$. Then

$$
\hat N(s) = \rho(s)\,\frac{1 - \rho'(s)}{\rho'(s) - \rho(s)}
= 0.001 \cdot \frac{1 - 0.0012}{0.0012 - 0.001}
= 0.001 \cdot \frac{0.9988}{0.0002}
= 0.001 \cdot 4994 \approx 5.0.
$$

The model behaves as if it had seen $s$ about five times — even though the raw
exact-match count might be one — because it generalizes from the similar states it
has visited. The exploration bonus is then $\beta/\sqrt{\hat N} = \beta/\sqrt{5} =
0.447\,\beta$. Now take a genuinely novel state, where the same observation moves the
model _much more sharply_ — the model was very surprised. Say $\rho(s) = 0.001 \to
\rho'(s) = 0.002$ (the probability doubled). Then

$$
\hat N(s) = 0.001 \cdot \frac{1 - 0.002}{0.002 - 0.001}
= 0.001 \cdot \frac{0.998}{0.001} = 0.998 \approx 1,
$$

a pseudo-count of about one — the state has effectively been seen only once, so its
bonus $\beta/\sqrt{1} = \beta$ is more than double the $0.447\,\beta$ of the familiar
state. The formula's structure — the model's _surprise_ (the increment $\rho'-\rho$)
sits in the denominator — turns "how much did one observation move the
model" into "how many times has this effectively been seen." The bigger the jump, the
smaller the pseudo-count, and the larger the exploration bonus.

A cheaper approximation replaces the density model with **hashing**. Map each
state through a hash function $\phi$ that sends similar states to the same code
(a locality-sensitive hash, or a learned discrete code), keep an ordinary count
table over hash codes, and treat $\hat N(s) = N(\phi(s))$.[^tang] The bonus is
still $\beta / \sqrt{N(\phi(s))}$; only the counting mechanism changed. The hash
granularity is the whole design: too coarse and distinct states collide into one
count so novelty is undercounted; too fine and every state is its own bucket so
every count stays at one and nothing is ever "familiar."

$$
% caption: Count-based exploration in high dimensions. A raw state visited once
% never recurs, so the exact count is useless. A density model (or a hash)
% generalizes across similar states to produce a pseudo-count $\hat N(s)$, from
% which a bonus $\beta / \sqrt{\hat N(s)}$ rewards the unfamiliar.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=24mm, minimum height=12mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (s) at (0,0) {state s(t)};
  \node[box, draw=acc, text=acc] (d) at (3.9,0) {density model / hash};
  \node[box] (n) at (8.0,0) {pseudo-count N-hat(s)};
  \node[box, draw=acc, text=acc, thick] (b) at (8.0,-2.2) {bonus = beta / sqrt(N-hat)};
  \draw[->, acc, thick] (s) -- (d);
  \draw[->, acc, thick] (d) -- (n);
  \draw[->, acc, thick] (n) -- (b);
  \node[font=\scriptsize, text=black, anchor=south] at (3.9,0.7) {generalizes across similar s};
\end{tikzpicture}
$$

## Intrinsic motivation and curiosity

Pseudo-counts reward states that are _rare_. A subtly different idea rewards
states that are _surprising_ — that violate the agent's own predictions. This is
**intrinsic motivation**: a reward manufactured internally by the agent, not
handed down by the environment, meant to capture something like curiosity. The
two notions overlap (a rare state is often a surprising one) but the machinery
differs, and the curiosity view scales better because it needs no
explicit count table.

Formally, we split the reward the agent maximizes into an **extrinsic** part
from the environment and an **intrinsic** part from the exploration signal, with
a coefficient $\beta$ trading them off:
$$
r_t \;=\; r^e_t \;+\; \beta\, r^i_t.
$$
Every method in this lesson is one choice of $r^i_t$. The RL algorithm does not
change — it still maximizes cumulative $r_t$ — but because $r^i_t$ is large in
unexplored regions, the optimal policy under $r_t$ deliberately seeks them out.

$$
% caption: The reward the agent maximizes is a sum of the environment's
% extrinsic reward and a novelty-driven intrinsic reward, $r_t = r^e_t + \beta
% r^i_t$. The intrinsic term is nonzero even where the environment is silent, so
% the agent keeps moving toward the unfamiliar until the world becomes familiar
% and $r^i_t$ decays.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=12mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (ext) at (0,1.3) {extrinsic r-e(t)\\(from environment)};
  \node[box, draw=acc, text=acc] (int) at (0,-1.3) {intrinsic r-i(t)\\(novelty signal)};
  \node[circle, draw, minimum size=9mm] (sum) at (4.4,0) {+};
  \node[box, draw=red, text=red, thick] (tot) at (8.6,0) {total r(t)\\to RL algorithm};
  \draw[->, black, thick] (ext.east) -- (sum);
  \draw[->, acc, thick] (int.east) -- (sum);
  \node[font=\scriptsize, text=black, anchor=north] at (2.3,-0.95) {weight beta};
  \draw[->, red, thick] (sum) -- (tot);
\end{tikzpicture}
$$

### The Intrinsic Curiosity Module

The Intrinsic Curiosity Module (ICM) of Pathak et al. (2017) defines surprise as
**prediction error in a learned feature space**, and its central trick is to
choose that feature space so the agent is not fooled by noise it cannot
control.[^pathak] Predicting raw future pixels would make an agent "curious"
about a swaying tree or television static — high-entropy pixels it can neither
predict nor influence. ICM avoids this with two coupled models.

The **inverse model** takes the features of two consecutive states $\phi(s_t)$
and $\phi(s_{t+1})$ and predicts the action $a_t$ that connected them. Training
this model shapes the feature encoder $\phi$: to predict the action, $\phi$ must
keep exactly the parts of the state the agent's actions _affect_, and it has no
reason to encode anything the agent cannot change (the static, the tree). This is
the key move — the representation is filtered down to the controllable.

The **forward model** then works inside that filtered space. It takes
$\phi(s_t)$ and the action $a_t$ and predicts the next features
$\hat\phi(s_{t+1})$. The intrinsic reward is how badly it misses:
$$
r^i_t \;=\; \frac{\eta}{2}\,\bigl\lVert \hat\phi(s_{t+1}) - \phi(s_{t+1}) \bigr\rVert^2 .
$$
Where the forward model predicts well — familiar, already-mastered dynamics —
the error is small and $r^i_t \approx 0$. Where it predicts poorly — a state
whose consequences the agent has not yet learned — the error is large and the
agent is rewarded for going there. As it revisits and the forward model learns,
the reward for that region decays, so curiosity is self-extinguishing: once a
region is understood its reward vanishes, and the agent moves on.

$$
% caption: Self-extinguishing curiosity. The intrinsic reward for a region is the
% forward model's prediction error there; as the agent revisits and the model learns,
% the error (and the reward) decays toward zero, so the agent stops being paid for a
% mastered region and its attention moves to the next unfamiliar one.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[black, ->] (0,0) -- (6.4,0) node[anchor=north east, text=black] {visits to a region};
  \draw[black, ->] (0,0) -- (0,3.0) node[anchor=south east, text=black] {curiosity reward};
  \draw[acc, very thick] plot[domain=0.1:6.0, samples=70] (\x, {2.6*exp(-0.6*\x)});
  \node[acc, anchor=west, font=\scriptsize] at (2.4,1.3) {reward decays as the model learns};
  \fill[red] (0.3,{2.6*exp(-0.6*0.3)}) circle (2pt);
  \node[red, anchor=west, font=\scriptsize] at (0.5,2.4) {novel: high reward};
  \fill[red] (5.0,{2.6*exp(-0.6*5.0)}) circle (2pt);
  \node[red, anchor=west, font=\scriptsize] at (4.2,0.55) {mastered: near zero};
\end{tikzpicture}
$$

$$
% caption: The Intrinsic Curiosity Module. An inverse model predicts the action
% $a_t$ from features $\phi(s_t), \phi(s_{t+1})$, which trains the encoder
% $\phi$ to keep only the controllable part of the state. A forward model
% predicts $\hat\phi(s_{t+1})$ from $\phi(s_t)$ and $a_t$; its error becomes the
% curiosity reward $r^i_t$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\scriptsize},
  enc/.style={draw, minimum width=17mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (st) at (0,1.3) {s(t)};
  \node[box] (st1) at (0,-1.3) {s(t+1)};
  \node[enc, draw=acc, text=acc] (pt) at (3.0,1.3) {phi(s(t))};
  \node[enc, draw=acc, text=acc] (pt1) at (3.0,-1.3) {phi(s(t+1))};
  \draw[->, acc, thick] (st) -- (pt);
  \draw[->, acc, thick] (st1) -- (pt1);
  % inverse model: predicts action from both features
  \node[box, draw=acc, text=acc] (inv) at (6.4,0) {inverse model:\\predict a(t)};
  \draw[->, black] (pt) -- (inv);
  \draw[->, black] (pt1) -- (inv);
  % forward model: predicts next feature from phi(s(t)) and a(t)
  \node[box, draw=red, text=red] (fwd) at (10.2,1.3) {forward model:\\predict phi-hat};
  \draw[->, black] (pt) -- (fwd);
  \draw[->, black] (inv) -- (fwd) node[midway, right, font=\scriptsize, text=black] {a(t)};
  % reward = forward error vs actual next feature
  \node[box, draw=red, text=red, thick] (r) at (10.2,-1.3) {r-i(t) =\\forward error};
  \draw[->, red, thick] (fwd) -- (r);
  \draw[->, red, thick] (pt1) -- (r);
\end{tikzpicture}
$$

> **Definition (Intrinsic Curiosity Module).** An intrinsic-reward scheme that
> learns a feature encoder $\phi$ via an _inverse_ dynamics model (predict the
> action from consecutive state features, forcing $\phi$ to represent only the
> agent-controllable factors of the state) and a _forward_ dynamics model
> (predict the next features from the current features and action). The intrinsic
> reward is the forward model's prediction error, so the agent is rewarded for
> reaching states whose dynamics it cannot yet predict, and the reward vanishes
> as those dynamics are learned.

Pathak et al. showed ICM driving exploration in VizDoom and Super Mario Bros.
with _no extrinsic reward at all_ — pure curiosity carried Mario across large
fractions of a level, because progress into unseen territory is precisely what
maximizes forward-model surprise.

### Random Network Distillation

ICM's forward model is expensive and, worse, exposed to the **noisy-TV problem**
in its sharpest form: if any part of the environment is genuinely stochastic and
unpredictable, the forward model can never drive its error to zero there, so the
agent gets stuck earning intrinsic reward by staring at noise. Random Network
Distillation (RND) of Burda et al. (2019) sidesteps both issues with a
deliberately simpler definition of novelty.[^burda]

Fix a **random target network** $f$: a neural net with random, frozen weights
that maps a state to a feature vector. It computes some arbitrary but
_deterministic_ function of the state. Train a second **predictor network**
$\hat f$ to match the target's output on the states the agent visits. The
intrinsic reward is the predictor's error:
$$
r^i_t \;=\; \bigl\lVert \hat f(s_{t+1}) - f(s_{t+1}) \bigr\rVert^2 .
$$
The logic is pure novelty detection. On states seen many times, the predictor
has been trained to match the target and its error is small. On a genuinely new
state, the predictor has never been trained there, so it mispredicts the target's
(deterministic) output and the error is large. Because the target is a _fixed
deterministic function_, there is nothing stochastic for the predictor to chase —
the noisy-TV failure that afflicts a forward model is absent, since the target gives
the same output for a given state every time regardless of environment noise.

$$
% caption: Random Network Distillation. A fixed random target network maps
% states to features; a predictor is trained to match it on visited states. On a
% novel state the predictor has not been trained and its error is large, giving
% the intrinsic reward $r^i_t = \lVert \hat f(s) - f(s)\rVert^2$; on a familiar
% state the error has been driven down.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (s) at (0,0) {state s};
  \node[box] (tgt) at (4.2,1.5) {target f\\(random, frozen)};
  \node[box, draw=acc, text=acc] (pred) at (4.2,-1.5) {predictor f-hat\\(trained)};
  \draw[->, black] (s) -- (tgt);
  \draw[->, acc, thick] (s) -- (pred);
  \node[box, draw=red, text=red, thick] (err) at (9.0,0) {r-i = \\squared error\\(f-hat vs. f)};
  \draw[->, black] (tgt.east) -- (err.north west);
  \draw[->, acc, thick] (pred.east) -- (err.south west);
  \node[font=\scriptsize, text=black, anchor=west, align=left] at (9.0,-1.5) {large on novel s\\small on familiar s};
\end{tikzpicture}
$$

> **Definition (Random Network Distillation).** An intrinsic-reward scheme in
> which a predictor network is trained to reproduce the output of a fixed,
> randomly initialized target network on the states the agent visits. The
> prediction error is the intrinsic reward: high on novel states (the predictor
> was never trained there) and low on familiar ones. Because the target is a
> deterministic function of the state, environment stochasticity does not inflate
> the reward, avoiding the noisy-TV failure of forward-model curiosity.

RND is simple enough to bolt onto a strong policy-gradient learner, and Burda et
al. did exactly that, combining it with PPO and separate value heads for the
extrinsic and intrinsic streams. The result was the first agent to _exceed
average human performance_ on Montezuma's Revenge and to occasionally finish the
first level — a task ε-greedy agents scored zero on. The whole apparatus is one
extra network trained by regression; it added a single well-chosen intrinsic
reward, and that was enough.

## Where this leaves us

Two families of novelty signal are now in hand, and both plug into the same template:
score how unfamiliar a state is, turn the score into an intrinsic reward $r^i_t$, and
add it to the environment's reward so the return-maximizing agent seeks the unfamiliar.

- **Pseudo-counts** recover UCB's $1/\sqrt{N}$ bonus where the literal visit count is
  useless, deriving an approximate count from a density model's surprise (or a hash).
- **Curiosity** (ICM, RND) rewards _prediction error_ instead of rarity, and
  self-extinguishes as the agent masters a region — with RND's fixed random target
  sidestepping the noisy-TV failure of forward models.

Both reward novelty _after_ the agent stumbles into it. Two further ideas change that:
a posterior over value functions that drives _committed_, directed exploration, and an
explicit archive that _remembers and returns_ to the frontier rather than hoping a
reward bonus leads back. Those — bootstrapped DQN, Go-Explore, and the modern systems
built on them — continue in
[Exploration in Deep RL: Posterior Sampling and Go-Explore](/reinforcement-learning/modern-deep-rl/exploration-part-2).

[^bellemare]: **Bellemare, Srinivasan, Ostrovski, Schaul, Saxton, Munos** (2016), "Unifying Count-Based Exploration and Intrinsic Motivation", _NeurIPS_ — derives pseudo-counts from a sequential density model, relates them to information gain and prediction gain, and demonstrates the first substantial progress on Montezuma's Revenge with a count-based bonus on DQN.
[^tang]: **Tang, Houthooft, Foote, Stooke, Chen, Duan, Schulman, De Turck, Abbeel** (2017), "#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning", _NeurIPS_ — replaces the density model with a hash of the state (SimHash / a learned autoencoder code) and keeps ordinary counts over hash codes, giving a simple count-based bonus that generalizes to continuous and high-dimensional states.
[^pathak]: **Pathak, Agrawal, Efros, Darrell** (2017), "Curiosity-driven Exploration by Self-supervised Prediction", _ICML_ — the Intrinsic Curiosity Module: an inverse dynamics model learns a feature space capturing only agent-controllable factors, and a forward model's prediction error in that space is the intrinsic reward, shown to explore VizDoom and Super Mario Bros. with little or no extrinsic reward.
[^burda]: **Burda, Edwards, Storkey, Klimov** (2019), "Exploration by Random Network Distillation", _ICLR_ — defines novelty as the error of a predictor trained to match a fixed random target network, avoiding the noisy-TV problem of forward-prediction curiosity, and combined with PPO first exceeds average human performance on Montezuma's Revenge.