Exploration in Reinforcement Learning — Introduction to Robot Learning (CMU 16-831)

Chapter 0: A Needle in a Haystack

Every reinforcement-learning method you have met so far — Q-learning, policy gradients, actor-critic — shares one quiet assumption: that the agent sees reward often enough to learn from it. Take that away and the whole machinery stalls. This lecture is about what to do when reward is almost never there.

The poster child is the Atari game Montezuma's Revenge. To score a single point you must climb down a ladder, jump a gap, dodge a skull, cross a room, and grab a key — dozens of precise actions in a row. The reward for the key arrives only after that exact sequence. This is a hard-exploration, sparse-reward task: the reward signal is a single needle buried in an enormous haystack of states.

Now recall how Q-learning explores: ε-greedy. Most of the time it takes its best-known action; with probability ε it takes a uniformly random action. That is fine when reward is dense — a few random pokes will bump into a payoff. But ask ε-greedy to find the key in Montezuma's Revenge by chance and the arithmetic is hopeless: the probability of randomly stringing together the dozens of right actions is astronomically small. The agent flails near the start, never sees reward, and so never learns anything to be greedy about. It is stuck.

The whole lecture in one sentence. When reward is too sparse for random actions to ever stumble onto it, we give the agent a second, self-generated reward — an intrinsic reward that pays it for visiting new or surprising states. That bonus drives the agent to systematically cover the world until it finds the real reward. Turning “explore the unknown” into a number you can maximize is the entire game.

Humans do this without thinking. A toddler on a playground gets no points, no score, no win condition — yet she relentlessly pokes, climbs, drops, and tastes everything in reach. Psychologists call this intrinsic motivation or curiosity. The agent in this lecture is going to be given the same drive, mathematically.

ε-greedy vs novelty-seeking on a sparse-reward maze

A robot starts top-left; the only reward (teal) sits in a far corner, reachable only through a narrow corridor. Press Run. The warm agent is ε-greedy — with no reward signal yet, it has nothing to be greedy about and just rattles around near home. The teal agent gets a bonus for entering new cells; watch it fan outward and reach the corner. The heat shows where each has been.

Ready. Teal seeks novelty; warm flails randomly.

Notice what the novelty bonus buys: direction. ε-greedy spreads its random steps evenly and so diffuses outward only as a slow random walk — on average it takes an enormous number of steps to wander down a long corridor. The novelty-seeking agent actively pushes toward the parts of the world it has seen least, so it sweeps the map and finds the goal in a fraction of the time.

Where this is going. Three questions organize the lecture. (1) How do we make “new” precise enough to reward — counting state visits, and a bonus that shrinks as a state grows familiar (Ch 2–3)? (2) In a world with images for states, where you never see the exact same pixels twice, what does “new” even mean — curiosity as prediction error, and the trap it falls into (Ch 4–6)? (3) Is there a novelty signal that can't be fooled by randomness — Random Network Distillation (Ch 7–8)?

Why does plain ε-greedy exploration fail on a hard-exploration, sparse-reward task like Montezuma's Revenge?

Because ε-greedy can only be used with tabular Q-learning, not neural networks. Because the discount factor γ is too small to value distant rewards. Because reward requires a long precise sequence of actions; the chance of stringing it together with uniformly random steps is astronomically small, so the agent never sees reward and has nothing to learn from. Because ε-greedy explores too little — raising ε to 1.0 would solve it.

Chapter 1: Optimism in the Face of Uncertainty

Before we tackle full RL, the lecture sharpens our intuition on the simplest possible exploration problem: the multi-armed bandit. There are several slot-machine arms; each pays a random reward with some unknown average. You want to pull the best one as often as possible — but you do not know which is best until you have tried them. Pull only the arm that looks best so far and you might lock onto a lucky-looking dud forever; pull arms at random and you waste pulls on losers. This is exploration vs exploitation in its purest form.

The bandit world hands us the master principle of this entire field: optimism in the face of uncertainty (OFU). When you are unsure how good an option is, assume it might be great and try it. If it really is great, wonderful. If it is not, you learn that quickly and stop wasting pulls on it. Either way, uncertainty gets resolved.

The classic algorithm built on OFU is the Upper Confidence Bound (UCB). For each arm it keeps not just an estimate of the mean payoff but also a measure of how uncertain that estimate is. It then picks the arm with the highest optimistic estimate — the mean plus a bonus for uncertainty:

choose arm with the largest ( estimated mean ) + ( uncertainty bonus )

An arm you have pulled many times has a small uncertainty bonus — you already know it well. An arm you have barely tried has a large bonus, so UCB is drawn to it even if its current estimate looks mediocre. The bonus is exactly “how much could I still be wrong about this?”

The pattern to carry forward. Optimism says: add a bonus that grows with how little you know about an option, then act greedily on the optimistic total. Everything in the rest of this lecture is the same idea applied to states instead of arms: estimate how unfamiliar a state is, turn that into a reward bonus, and let a standard RL algorithm chase it. UCB's cousin, Thompson sampling, does the same job by sampling from a posterior over each arm's value — it explores in proportion to its uncertainty rather than via an explicit bonus.

So why not just run UCB on a robot? Because UCB needs to count how often it has tried each action, and there are only a handful of arms. In a full sequential task the “arm” you are uncertain about is the state you might visit, and there are astronomically many of those. The next chapters are the story of carrying the bonus-for-uncertainty idea from a few arms to an unboundedly large state space.

In UCB, why does an arm that has been pulled only a few times get chosen even when its current estimated mean is mediocre?

Because UCB ignores the estimated mean entirely and only counts pulls. Because a rarely-pulled arm carries a large uncertainty bonus, so its optimistic total (mean + bonus) can be highest — optimism in the face of uncertainty. Because UCB always alternates arms in a fixed round-robin. Because mediocre arms pay more reward on average.

Chapter 2: Counting States — a Bonus That Shrinks

Here is the most literal way to turn “reward novelty” into a number. Keep a tally: N(s) = how many times the agent has visited state s. A state it has never seen has N(s) = 0; a corridor it has walked a hundred times has N(s) = 100. Now add an exploration bonus to the real reward that is large when the count is small and shrinks as the count grows. The standard choice, straight from UCB, is one over the square root of the count:

r_total(s,a) = r_extrinsic(s,a) + β · ¹⁄_√N(s)

Read every symbol. r_extrinsic is the real reward from the environment — for Montezuma, almost always zero. The second term is the intrinsic exploration bonus. N(s) is the visit count of the state. β (beta) is a knob setting how strongly the agent cares about novelty versus real reward. The fraction ¹⁄_√N(s) is the heart of it: a brand-new state pays a big bonus, the second visit pays less, and after many visits the bonus is nearly nothing.

Then we do nothing exotic: feed r_total to ordinary Q-learning. The agent learns to seek high total reward, which early on means seeking unvisited states — precisely the directed exploration the random ε-greedy walk could never produce. As states fill in, the bonus everywhere decays toward zero and the agent is left chasing only the real reward it has by then discovered.

Why one-over-square-root, not one-over-the-count? The ¹⁄_√N shape is the same uncertainty bonus UCB uses: your uncertainty about a state's value falls like one over the square root of the number of samples (the standard error of an average). A bonus of ¹⁄_N would collapse too fast — one visit and you'd declare the state “known”. The square root lets the agent keep gently re-checking a state a few times before writing it off as familiar.

Watch the bonus decay, by hand

Suppose β = 1. The first time the agent enters a state, N becomes 1 and the bonus is ¹⁄_√1 = 1.00. On the 4th visit, N = 4 and the bonus is ¹⁄_√4 = 0.50. On the 100th visit, N = 100 and the bonus is ¹⁄_√100 = 0.10. The pull toward this state has quietly faded by a factor of ten — exactly the “I've seen enough of this” behavior we want.

A visit-count heatmap — the bonus glow that pulls the agent

A count-based agent wanders a gridworld with no extrinsic reward at all — only the ¹⁄_√N bonus. Each cell's warm glow is its current bonus (bright = unvisited, dim = familiar); the dot is the agent. Press Run and watch the glow burn down behind it as it methodically covers the whole map — no corner is left dark. Slide β to change how hard novelty pulls.

Bonus weight β 1.0

Ready. The glow is the exploration bonus per cell.

Let's encode that bonus ourselves and verify two facts: it is largest for the least-visited state, and an agent that follows it covers far more of the world than a greedy agent that ignores novelty.

With a count-based bonus β·¹⁄_√N(s) and β = 1, how does the bonus for a state change between its 1st visit (N = 1) and its 100th visit (N = 100)?

It stays the same — the bonus does not depend on the count. It drops from 1.0 to 0.1 — a tenfold shrink, so the state stops pulling the agent once it is familiar. It drops from 1.0 to 0.01 — a hundredfold shrink. It grows, because more visits mean more reward.

Chapter 3: Pseudo-counts — Counting When You Never Repeat

Chapter 2's count works beautifully in a tiny gridworld, where the same cell really is visited again and again. Now make the state an image — the Atari screen. The state is hundreds of pixels. You will essentially never observe the exact same screen twice. Every frame is a tiny bit different: a flickering animation, a sprite one pixel over, a score digit ticking up. So the literal count N(s) is 1 for every state forever, the bonus never decays, and counting is useless.

This is the same wall the whole field keeps hitting: methods that work on a finite table fall apart in a high-dimensional, continuous world. We need a notion of count that says “I have seen states like this many times,” even if not this exact one.

The misconception to kill. “Just hash the image down to a few bits and count the hashes.” You can — that is one real method — but a naive hash either merges genuinely different states (so it under-counts novelty) or splits near-identical ones (so it over-counts and never decays). The deeper fix is to replace the count with a density: a model of how probable each state is under everything seen so far.

The idea is the pseudo-count. Instead of tallying exact states, train a density model — call its estimated probability of a state p(s). A state you have seen a lot looks probable (high p); a genuinely novel state looks improbable (low p). You can then back out a fictitious count from how that probability changes after one more observation of s. The intuition is clean: if seeing s once barely nudges its estimated probability, the model has already seen plenty like it, so the pseudo-count is high; if one observation noticeably raises p(s), the state was surprising and rare, so the pseudo-count is low.

You then drop that pseudo-count, call it N̂(s), straight into the same bonus from Chapter 2:

r_intrinsic(s) = β · ¹⁄_√N̂(s)

This is exactly what gave the first big breakthrough on Montezuma's Revenge: a count-based bonus driven by a learned density model, scoring far above anything ε-greedy could reach. The lesson is general — when you can't count exact states, count their probability instead.

Concept to realization. The data flow is: state image → density model gives p(s) → convert to a pseudo-count N̂(s) → bonus β·¹⁄_√N̂ → add to the extrinsic reward → ordinary RL maximizes the total. The only new box is the density model; everything downstream is the count-based recipe you already understand. This same shape — learn a model, turn its output into a novelty bonus, add it to reward — is the template for the rest of the lecture.

Why do literal visit counts N(s) fail when the state is a raw image (e.g. an Atari screen)?

Because images are too large to store in memory. Because you essentially never observe the exact same image twice, so every count stays at 1 and the bonus never decays — a pseudo-count from a learned density model fixes this by counting how probable a state is. Because images have no reward attached to them. Because the discount factor must be 1 for image states.

Chapter 4: Curiosity = Prediction Error

Pseudo-counts answer “how often have I seen this?” Curiosity answers a different, more human question: “how surprised am I by what just happened?” A toddler is not counting screens — she is building a little model of how the world responds to her pokes, and she is drawn to whatever her model gets wrong.

Pathak and colleagues (2017) made this precise with one conjecture and one definition. The conjecture: exploring with no external goal, just to understand the world, makes the agent generalize better. The definition is the engine of the lecture:

The core idea. Curiosity ≜ prediction error. Train a forward model that, given the current state and the action, predicts the next state. Whatever it predicts badly — the surprising parts of the world — gets a high curiosity reward. Whatever it predicts well — the familiar, already-understood parts — gets almost none. The agent is paid to seek out what it cannot yet predict.

Here is the machinery in plain terms. We keep a forward dynamics model f — a small network with parameters that we will call θ (theta). It takes the current state s_t and the action a_t and outputs a guess for the next state, ŝ_t+1. We train it by gradient descent to make that guess match the next state the world actually produced, minimizing the squared error between guess and reality. The leftover error — how wrong the guess was — is handed back to the agent as the intrinsic reward:

r_t^intrinsic = ∥ ŝ_t+1 − s_t+1 ∥² where ŝ_t+1 = f_θ(s_t, a_t)

The double bars mean “length of the difference vector” (the gap between predicted and real next state); the superscript two means we square it. Read it as: the bigger the surprise, the bigger the reward. As the agent revisits a region and the forward model learns it, the error there falls, the curiosity reward there fades, and the agent moves on to fresh, still-unpredictable territory. The bonus self-extinguishes — just like the count bonus did.

Notice this gives us the same balance the bandit chapter promised: the total reward the agent maximizes is the real reward plus the curiosity reward, r_extrinsic + r_intrinsic. The intrinsic term drives exploration early; the extrinsic term takes over once real reward is found. It is OFU again — optimism, now expressed as “go where you're most wrong.”

Surprise decays as a region becomes predictable

A forward model is learning to predict the next state across a 1-D world of locations. The warm bars are the current prediction error (the curiosity reward) at each location. Press Visit a region to send the agent there a few times; watch the model learn that region and its surprise bar collapse — the agent will then be pulled toward whatever is still tall.

Ready. Tall bar = surprising = high curiosity reward.

This is a beautiful idea, and it works — an agent driven by curiosity alone, with the game's score switched off entirely, taught itself to play a good chunk of Super Mario Bros and to walk sensibly down corridors in a 3-D maze. But it hides a flaw that, if you predict in the wrong space, sinks the whole thing. That flaw is the subject of the next chapter.

In curiosity-driven exploration, what makes the intrinsic reward fade for a region the agent keeps visiting?

The discount factor γ multiplies it away. The forward model learns to predict that region accurately, so its prediction error — which IS the curiosity reward — shrinks toward zero there. The extrinsic reward overwrites it. Nothing — the curiosity reward is constant per state.

Chapter 5: The Noisy-TV Problem

Curiosity says “reward what you can't predict.” Read that sentence again, slowly, and you'll spot the bug. Some things are unpredictable not because they are new and worth exploring, but because they are random — and random things stay unpredictable forever.

Schmidhuber's famous thought experiment makes it vivid. Put a television in the agent's world that displays pure white noise — static, a fresh random pattern every frame. Ask a forward model to predict the next frame of static. It cannot, ever, no matter how long it trains, because the static carries no information about its own future. So the prediction error stays pegged high, the curiosity reward stays maximal, and a naive curiosity agent will sit in front of the noisy TV forever, mesmerized, collecting infinite intrinsic reward while learning nothing and going nowhere.

The trap, stated cleanly. Curiosity rewards prediction error. It cannot tell apart two very different sources of error: (1) genuine novelty — a new room the model hasn't learned yet, where error will fall once it does; and (2) irreducible randomness — static, dice, flickering distractors, sensor noise, where error never falls because there is nothing to learn. A naive curiosity agent is captured by the second kind. This is the noisy-TV problem, and it is not a corner case — real worlds are full of random distractors.

Why does this matter so much for robots specifically? Because the physical world is drenched in irreducible noise: camera sensor grain, shadows from things you don't control, swaying leaves, other agents moving unpredictably, the random chatter of actuators. If your exploration bonus is “raw prediction error of the next sensor reading,” the robot will be paid to stare at whatever is noisiest — the equivalent of a robot vacuum hypnotized by a flickering light.

The noisy-TV trap — raw prediction error never falls on a random cell

Five regions of the world. Four are ordinary (their next state is learnable); one is a noisy TV (its next state is pure random static). The warm bars are raw next-state prediction error. Press Train everywhere repeatedly: the ordinary bars collapse as the model learns them, but the noisy-TV bar stays pegged high forever — so a raw-curiosity agent gets stuck there.

Ready. The red region is irreducibly random.

So the curiosity idea is sound but the space you predict in is wrong. Predicting raw pixels (or raw sensor readings) makes you a slave to every random pixel. The fix is to predict in a space that throws the noise away and keeps only what the agent can actually control or affect. Two different answers to “which space?” make up the rest of the lecture: ICM learns such a space; RND sidesteps the problem with a clever trick. We take them in turn.

A curiosity agent driven by raw next-state prediction error gets permanently stuck watching a screen of random static. Why?

Because the static gives a large extrinsic reward. Because the forward model has too few parameters. Because the static is irreducibly random, so its prediction error never falls no matter how much the model trains — the curiosity reward there stays maximal, and curiosity can't distinguish “random” from “genuinely novel”. Because γ is too close to 1.

Chapter 6: ICM — Predict in a Feature Space You Control

The Intrinsic Curiosity Module (ICM) fixes the noisy-TV problem with one decisive move: don't predict the next state in pixel space — predict it in a learned feature space that only encodes what the agent can affect. Get that feature space right and random static simply isn't represented, so it can't generate reward.

But here is the catch: how do you train a feature encoder to keep “what the agent controls” and discard “random stuff the agent can't touch” — without anyone hand-labeling which is which? ICM's answer is genuinely clever, and it is the whole reason ICM works. It uses a second, helper model: an inverse dynamics model.

The inverse model is the trick

The inverse model is trained on a self-supervised task: given the features of the current state and the features of the next state, predict which action the agent took to get from one to the other. Think about what that forces the features to learn.

To recover the action, the features must encode the things the action changed — the agent's own position, the objects it moved. That information is essential to the task.
The features have no incentive to encode anything the action didn't affect — the noisy TV, a swaying background, a distractor sprite — because that stuff is useless for guessing the action. So the encoder learns to ignore it.

Why this is the right space. The inverse-model task is a filter: it keeps exactly the part of the state that responds to the agent's actions and discards the part that doesn't. Random distractors (the noisy TV) are uncontrollable, so they vanish from the feature space — and what isn't represented can't produce prediction error, so it can't lure the agent. The features encode “the world, as far as I can affect it.”

Putting the two models together

Now the forward model from Chapter 4 runs in feature space instead of pixel space. Writing φ(s) (phi) for the feature encoding of state s, ICM predicts the next state's features from the current features and the action, and uses that error as curiosity:

r_t^intrinsic = ∥ φ̂(s_t+1) − φ(s_t+1) ∥² where φ̂(s_t+1) = f_θ( φ(s_t), a_t )

s_t, s_t+1 (raw states)

Two consecutive states, e.g. two screens, possibly full of random distractors.

↓ encode with φ (the encoder we're learning)

φ(s_t), φ(s_t+1) (features)

Compact codes that keep only action-relevant info.

→ inverse model: predict the action a_t from the two features — this trains φ to keep only what the action changed

forward model f_θ( φ(s_t), a_t )

Predicts the NEXT features. Trained to minimize feature-space error.

↓ leftover error becomes…

r^intrinsic = feature prediction error

Added to extrinsic reward; a standard RL algorithm maximizes the sum.

The same forward-model-error idea as before — but because it lives in a space scrubbed of uncontrollable noise, the noisy TV produces no error and no reward. The agent is curious about the parts of the world it can act on, and indifferent to the static. That is exactly the curiosity we wanted.

Concept to realization — the three pieces. (1) An encoder φ maps raw state → features. (2) An inverse model uses φ(s), φ(s') to predict the action — its gradients shape φ to keep only action-relevant features. (3) A forward model predicts φ(s') from φ(s) and a — its error is the curiosity reward. All three train jointly, online, from the agent's own experience. No labels, no human-specified features.

In ICM, what is the job of the inverse dynamics model (predicting the action from two consecutive feature encodings)?

To directly produce the intrinsic reward. To shape the feature encoder φ so it keeps only the parts of the state the agent's actions affect, and discards uncontrollable noise like the noisy TV — so curiosity is measured in a space where random distractors don't appear. To replace the policy network. To predict the extrinsic reward of the environment.

Chapter 7: Random Network Distillation

ICM beats the noisy TV by carefully learning the right feature space. Random Network Distillation (RND) takes a startlingly different route: it sidesteps dynamics prediction entirely and asks a much simpler question — have I seen a state like this before? — with a trick so clean it is almost a magic act.

RND uses two networks that both map a state to a feature vector:

A target network with random, frozen weights. It is initialized randomly and never trained. It computes some fixed, arbitrary-but-deterministic function of the state. Same state in → same output out, always.
A predictor network, trained to copy the target's output on every state the agent actually visits, by minimizing the squared difference between its output and the target's.

The novelty signal — the intrinsic reward — is the error between the two networks on the current state:

r_t^intrinsic = ∥ predictor(s_t) − target(s_t) ∥²

Now watch why this is a novelty detector. The target's output on a state is a fixed number. On states the agent has visited many times, the predictor has had many chances to match that number, so its error there is tiny — familiar. On a state the agent has never seen, the predictor has never been trained there, so it produces some untrained guess that is far from the target — large error = novel. As the agent revisits a state, the predictor trains down its error there, and the bonus fades. Familiarity is “the predictor has caught up to the target here.”

The trick, and why it dodges the noisy TV. The target function is deterministic — the same state always yields the same target output — so it is, in principle, perfectly learnable: nothing random stands between input and output. Therefore on a noisy-static screen, even though the screen itself is random, RND's error reflects only how often the predictor has been trained on screens like this, not the unpredictability of the next frame. There's no forward prediction, so there's nothing for randomness to corrupt. Show the same kind of static enough times and the predictor learns the target's response to it, and the bonus drops — unlike raw curiosity, which would stay pegged forever.

RND is the method that finally cracked Montezuma's Revenge — the first to beat average human performance on it without demonstrations or access to the game's internal state. And it is dead simple: a fixed random network, a trained copy of it, and the gap between them. No dynamics model, no inverse model, no density estimator. Novelty, distilled.

Let's build the novelty signal and confirm its defining property: the error drops as a state is seen more often.

In RND, why is the squared error between the predictor and the fixed random target network a good novelty signal?

Because the target network is trained on reward, so its output equals the value of the state. Because the predictor is only trained on states the agent has actually visited, so its error is small on familiar states (it has matched the target there) and large on never-seen states (it hasn't) — the error tracks familiarity. Because both networks are random, so the error is pure noise. Because the error equals the extrinsic reward.

Chapter 8: Beating the TV — Why RND Doesn't Get Stuck

Chapter 5 showed raw curiosity hypnotized by static. Chapter 7 claimed RND escapes that trap. This chapter pins down exactly why — because the difference comes down to a single question: does your novelty signal depend on predicting the future, or only on recognizing the present?

Line the two up on the same noisy TV:

	Raw curiosity (forward model)	RND
What it predicts	the next state from this state + action	a fixed function of this state
On a random-static screen	next frame is unpredictable → error stays high forever	target output for this screen is fixed → predictor can learn it
Does the bonus decay?	No — trapped at the TV	Yes — once the predictor has seen enough static
Source of error	irreducible randomness of the future	only unfamiliarity of the present

The crux is in the last row. Raw curiosity's error has a floor it can never get below: the part of the next state that is genuinely random. No amount of training removes it, so the reward never dies. RND has no such floor — the target is a deterministic function of the current state, so given enough exposure the predictor can drive the error all the way to zero, even on noise. RND's error measures only one thing: how often have I been trained on inputs like this? That is novelty, full stop, uncontaminated by the unpredictability of the future.

The unifying lesson of the lecture. Both ICM and RND fix the noisy-TV problem the same way in spirit: don't let irreducible randomness leak into the novelty signal. ICM does it by predicting in a learned feature space that discards uncontrollable noise. RND does it by predicting a deterministic target of the current state rather than the random future. Different mechanisms, same goal — measure unfamiliarity, not unpredictability.

Let's make the contrast undeniable: on the very same stochastic state, RND novelty must fall as the state is revisited, while the raw next-state prediction error must stay high.

On the noisy TV, why does RND's novelty signal decay to zero while raw next-state curiosity stays stuck high?

RND uses a larger network than the forward model. RND predicts a deterministic target of the CURRENT (fixed) state, which is learnable, so its error falls with familiarity; raw curiosity predicts the RANDOM next state, whose error has an irreducible floor that never disappears. RND ignores the noisy TV by detecting it as random and skipping it. Because RND has no intrinsic reward at all.

Chapter 9: Three Flavors of Intrinsic Reward

Counting, curiosity, and RND are all intrinsic rewards — rewards the agent manufactures for itself rather than receiving from the environment. The lecture organizes the whole zoo of such rewards into three families, by the question each one answers. Knowing the taxonomy keeps you from confusing methods that look similar but optimize different things.

Flavor	The question it asks	Examples
Knowledge-based	How surprising / unpredictable is this? How much did I learn about the world?	Curiosity (ICM), prediction-error bonuses
Competence-based	What distinct skills can I reliably perform?	Empowerment, skill discovery (DIAYN)
Data-based	How much of the state space have I covered?	State-entropy / coverage bonuses, RND (a coverage proxy)

The knowledge-based family is Chapters 4–6: reward surprise, measured as prediction error. The data-based family is Chapters 2, 3, and 7: reward visiting under-covered states — literally counts, pseudo-counts, or RND as a stand-in for “how much have I covered.” The middle family is new and worth a paragraph.

Competence-based: reward distinct skills

Empowerment / skill discovery asks the agent not “what's new?” but “what can I reliably cause?” A method like DIAYN (“Diversity Is All You Need”) hands the policy a random latent code z, has it roll out a trajectory, then tries to recover z back from that trajectory. The reward is high when different codes produce distinctly different, recognizable behaviors — so the agent is paid to discover a diverse repertoire of skills, each one a controllable, distinguishable way of behaving, all without any task reward.

The shared data flow. Every method in this lecture obeys the same pipeline: state → some learned model → an intrinsic-reward number → added to the extrinsic reward → ordinary RL maximizes the sum. They differ only in the middle box — a visit counter, a density model, a forward+inverse model, a fixed-target predictor, or a skill discriminator. Master that template and every new exploration method is just a new way to fill the “learned model” slot. And in all of them, the intrinsic reward is designed to self-extinguish — the agent stops chasing a state once it is no longer novel/surprising/uncovered — so that the real reward eventually takes over.

A skill-discovery method (e.g. DIAYN) rewards the agent for producing trajectories from which a random latent code z can be recovered. Which family of intrinsic reward is this?

Knowledge-based (surprise / prediction error). Competence-based (empowerment / skills) — it rewards discovering distinct, controllable behaviors, not novelty or coverage. Data-based (coverage / state entropy). Extrinsic reward from the environment.

Chapter 10: Cheat Sheet & Connections

You arrived stuck — a sparse-reward task that ε-greedy could never crack. You leave with a toolbox of ways to manufacture a reward for novelty and surprise, and a sharp understanding of the one failure mode (the noisy TV) that separates the naive methods from the ones that work. Here is the whole lecture on a page.

The exploration ladder

Method	Intrinsic reward	Beats the noisy TV?	Works on images?
ε-greedy	none (random actions)	n/a	fails on sparse reward
UCB / optimism	uncertainty bonus on actions	n/a	too few “arms”
Count-based	β · ¹⁄_√N(s)	yes (counts are exact)	No — never repeats a state
Pseudo-counts	β · ¹⁄_√N̂(s) via density model	yes	Yes
Curiosity (raw)	next-state prediction error	No — trapped	Yes, but fragile
ICM	prediction error in a learned feature space	Yes — ignores uncontrollable noise	Yes
RND	error vs a fixed random target network	Yes — deterministic target is learnable	Yes (cracked Montezuma)

The five things to remember

Sparse reward breaks random exploration. If reward needs a long precise action sequence, ε-greedy never stumbles onto it. You must direct exploration.
Optimism is the master principle. Add a bonus that grows with how little you know, then act greedily on the optimistic total. Carry it from bandit arms to states.
A good bonus self-extinguishes. ¹⁄_√N, prediction error, RND error — all shrink as a state becomes familiar, so the agent moves on and the real reward eventually dominates.
Curiosity = prediction error, but predict in the right space. Raw pixels make you a slave to the noisy TV; ICM predicts in a feature space (trained via inverse dynamics) that keeps only what the agent controls.
RND = unfamiliarity, not unpredictability. Error against a fixed, deterministic random target measures “have I been trained here?” — immune to irreducible randomness. Simple, and it solved Montezuma's Revenge.

The frontier. Intrinsic motivation also splits into knowledge-based (surprise), competence-based (skills/empowerment, e.g. DIAYN), and data-based (coverage/entropy). The open hard problems: how to set β so novelty doesn't drown the real reward; the “detachment” problem where a bonus drains before the agent reaches distant reward; and exploration in lifelong, ever-changing worlds where nothing ever stops being a little novel.

Where to go next

← Lecture 19: Bandits & Preference Learning — the bandit setting and UCB/Thompson sampling that gave us “optimism in the face of uncertainty.” Start here if Chapter 1 felt fast.
Lecture 21: Sim2Real → — how policies trained in simulation (where exploration is cheap and safe) transfer to the real robot.
RL Algorithms overview — where value-based and policy-based methods fit; the engines that the intrinsic reward in this lecture plugs into.
Lecture 8: Q-Learning — the ε-greedy exploration this lecture replaces, and the value machinery that consumes r_extrinsic + r_intrinsic.

The throughline of the course. Lecture 1 said robotics is “learning to make sequential decisions in the physical world,” and warned that data is the bottleneck. Exploration is about which data the agent collects — and in a sparse-reward, noisy, physical world, collecting the right data is the difference between a robot that learns and one that flails near home forever. Intrinsic motivation is how you make a robot go look.

“Reward the agent for being surprised — but never by random static.”