Exploration in Deep RL: Novelty as Reward

The multi-armed bandit 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 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.

Why ε-greedy fails at scale

ε-greedy explores by dithering: with probability $ε$ 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.

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

ε

-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.

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.¹ 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.

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 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 $6.91/1 = 2.63$ ; tried ten times, $6.91/10 = 0.83$ ; tried a hundred times, $6.91/100 = 0.26$ ; tried a thousand, $0.083$ . The bonus falls like $1/ 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/ N$ curve is the exact shape every deep-RL bonus below is trying to recover once the literal count $N$ is unavailable.

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.

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.¹ Fit a density model $ρ (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 $ρ^{'} (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.

The exploration bonus is then a count-based reward, in the spirit of UCB's $1/ N$ : an intrinsic reward added to the environment's reward,

r_{t}^{i} = \frac{β}{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 $ρ (s) = 0.001$ , and after one more training update on $s$ the probability rises to $ρ^{'} (s) = 0.0012$ . Then

\hat{N} (s) = ρ (s) \frac{1 - ρ ^{'} ( s )}{ρ ^{'} ( s ) - ρ ( 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 $β / \hat{N} = β / 5 = 0.447 β$ . Now take a genuinely novel state, where the same observation moves the model much more sharply — the model was very surprised. Say $ρ (s) = 0.001 \to ρ^{'} (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 $β / 1 = β$ is more than double the $0.447 β$ of the familiar state. The formula's structure — the model's surprise (the increment $ρ^{'} - ρ$ ) 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 $ϕ$ 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 (ϕ (s))$ .² The bonus is still $β / N (ϕ (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.

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

β / \hat{N} (s)

rewards the unfamiliar.

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 $β$ trading them off:

r_{t} = r_{t}^{e} + β r_{t}^{i} .

Every method in this lesson is one choice of $r_{t}^{i}$ . The RL algorithm does not change — it still maximizes cumulative $r_{t}$ — but because $r_{t}^{i}$ is large in unexplored regions, the optimal policy under $r_{t}$ deliberately seeks them out.

The reward the agent maximizes is a sum of the environment's extrinsic reward and a novelty-driven intrinsic reward,

r_{t} = r_{t}^{e} + β r_{t}^{i}

. 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_{t}^{i}

decays.

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.³ 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 $ϕ (s_{t})$ and $ϕ (s_{t + 1})$ and predicts the action $a_{t}$ that connected them. Training this model shapes the feature encoder $ϕ$ : to predict the action, $ϕ$ 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 $ϕ (s_{t})$ and the action $a_{t}$ and predicts the next features $\hat{ϕ} (s_{t + 1})$ . The intrinsic reward is how badly it misses:

r_{t}^{i} = \frac{η}{2} \hat{ϕ} (s_{t + 1}) - ϕ (s_{t + 1})^{2} .

Where the forward model predicts well — familiar, already-mastered dynamics — the error is small and $r_{t}^{i} \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.

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.

The Intrinsic Curiosity Module. An inverse model predicts the action

a_{t}

from features

ϕ (s_{t}), ϕ (s_{t + 1})

, which trains the encoder

ϕ

to keep only the controllable part of the state. A forward model predicts

\hat{ϕ} (s_{t + 1})

from

ϕ (s_{t})

and

a_{t}

; its error becomes the curiosity reward

r_{t}^{i}

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.⁴

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_{t}^{i} = \hat{f} (s_{t + 1}) - f (s_{t + 1})^{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.

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_{t}^{i} = ∥ \hat{f} (s) - f (s) ∥^{2}

; on a familiar state the error has been driven down.

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_{t}^{i}$ , and add it to the environment's reward so the return-maximizing agent seeks the unfamiliar.

Pseudo-counts recover UCB's $1/ 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.

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, 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, 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, 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. ↩