Reinforcement Learning

01 · Motivation

Why does this matter?

Dynamic programming gave us a clean object — the Markov Decision Process — and solved it: value iteration, policy iteration, and the Bellman equations produce optimal policies in a few dozen lines. But every one of those algorithms quietly assumed something extraordinary: that we already know the transition probabilities $P(s' \mid s, a)$ and the reward function $R(s, a)$ .

Outside textbook gridworlds, we almost never do. A helicopter pilot has no closed-form aerodynamics model. A market-maker doesn’t know the distribution of incoming orders. A robot vacuum has no probability table over carpet textures. What they do have is the ability to act and observe: try something, see what happens, get a number back. That is the gap reinforcement learning fills. The question becomes: given that I can interact with the world but cannot read its source code, how do I learn to act optimally?

No model, just episodes

The agent sees a stream of $\langle s, a, r, s' \rangle$ tuples and nothing else. No matrix $P$ , no function $R$ . Everything we know about the world must be inferred from what we did and what came back.

Acting while learning

Unlike supervised learning, the data we get depends on the decisions we make. A bad early policy collects bad data, which trains a bad policy. The data distribution is endogenous — the learner shapes its own training set.

Reward, not labels

No one tells you the correct action. You receive a scalar reward and must figure out, from delayed and noisy signals, which past decisions deserved credit. This is the credit-assignment problem, and it is the soul of RL.

How RL differs from supervised learning

It is tempting to think of RL as “supervised learning with rewards instead of labels.” That picture is misleading on three counts, and noticing them now saves confusion later.

Supervised learning

A fixed dataset $\{(x_i, y_i)\}$ is handed to you. Each example carries the correct answer. The data are i.i.d., the loss is local (depends only on the current prediction), and there is no notion of an “action” that changes what you see next.

No labels — only a scalar reward, often delayed. The data stream is not i.i.d.: each action changes the distribution of what comes next, and a bad early policy poisons the data used to train later policies. Feedback is evaluative, not instructive — “that move scored +3” tells you nothing about what would have scored +5.

The agent–environment loop

Every RL problem unfolds as the same loop. At each time step $t$ the agent observes a state $s_t$ , picks an action $a_t$ according to its policy $\pi$ , receives a reward $r_{t+1}$ and a new state $s_{t+1}$ from the environment, and the cycle repeats. The agent’s goal is to maximise the cumulative discounted reward — the return — over the long run.

Three things make this loop hard, and every algorithm in the chapter is a response to one of them. First, the credit-assignment problem: a reward arriving at step $t + 50$ might be the consequence of an action taken at step $t$ — which of the fifty decisions deserves the credit? Second, delayed consequences: an action that looks good now (eat the marshmallow) may be bad later (no second marshmallow). Third, endogenous data: the agent’s policy is also its data-collection strategy, so it must explore to learn yet exploit to perform.

How RL algorithms are classified

Before diving into methods, it helps to know the four axes used to classify them — you’ll see these labels attached to every algorithm in the chapter.

Axis	Options	What it means
Model	model-based · model-free	Does the agent learn/use an explicit model of $P$ and $R$ , or only sampled transitions?
Policy source	on-policy · off-policy	Is the agent learning the value of the policy it executes, or the value of a different policy?
Update timing	online · offline	Does the update happen after each step, or after a full episode/batch?
Representation	tabular · function approximation	Is the value function a lookup table, or a parametric function (e.g. a neural net)?

This chapter lives almost entirely in the model-free, tabular corner. We meet both on- and off-policy methods, and both online (TD-family) and offline (MC-family) updates. Function approximation is the bridge to deep RL — a topic for later.

why

The conceptual leap from dynamic programming

Dynamic programming says: “here is the MDP — compute the optimal value.” Reinforcement learning says: “here is a simulator — discover the optimal value.” We trade a closed-form Bellman expectation for noisy samples of it, and we trade certainty for the need to explore. Everything in this chapter — MC, TD, SARSA, Q-learning, ε-greedy — is a different answer to: how do you make that trade pay off?

Why RL is hard in practice

Three structural difficulties make RL fundamentally harder than supervised learning, and explain why a “small” RL problem can need millions of samples to solve.

Delayed credit

A reward at step 100 may be the consequence of a decision at step 3. The agent must figure out — from many noisy trajectories — which past actions actually caused the outcome.

Non-stationary data

The policy improves over time, so the distribution of states the agent sees keeps changing. A value function that fitted yesterday’s data may be wrong today — the target is moving.

Exploration cost

The agent has to try sub-optimal actions to learn about them. Every exploratory step pays a small price in expected return: too little and you miss the optimum, too much and you bleed reward forever.

02 · Intuition

The idea in plain language

Imagine you are dropped into a casino with a hundred slot machines and a thick wallet. Each machine pays out under some unknown distribution. After a few hours you want to be playing mostly the best machine, but at the start you have no idea which one that is. How do you decide what to pull, and how do you update your beliefs as the cherries (or lemons) land?

That tiny puzzle contains every idea in this chapter. You need to estimate values from samples, you need to act on your current best guess, and you need to keep trying things you’re not sure about, because your current best guess might be wrong. Slot machines are stateless; real RL adds the wrinkle that the lever you pull now also determines which machines are even available next turn. But the basic instincts carry over.

Three questions the chapter answers

Q1 · Prediction

I’m going to follow a fixed policy $\pi$ forever. What’s the value $V^\pi(s)$ of being in each state? How do I estimate it from sampled trajectories alone?

Q2 · Control

I don’t just want to evaluate a policy — I want the best one. How do I learn an optimal policy $\pi^*$ while only being able to sample from the environment?

Q3 · Exploration

If I always take what currently looks best, I never gather evidence about the others. How do I balance exploitation of what I know against exploration of what I don’t?

Q4 · Whose policy?

Sometimes I learn about the policy I’m actually using (on-policy). Sometimes I learn about a different policy while collecting data from another (off-policy). When is each right?

Two ways to learn a value

Suppose you’re estimating $V^\pi(s)$ — the expected return from state $s$ under policy $\pi$ . Two philosophies present themselves immediately.

Monte Carlo · wait and average

Roll out a complete episode. Add up all the rewards you got after visiting $s$ . That sum — the return $v_t$ — is one sample of the random variable whose mean is $V^\pi(s)$ . Run many episodes, average the returns, done. Strength: unbiased — the law of large numbers does the work. Weakness: must wait for each episode to end, and one observed return carries all the noise of the whole trajectory.

Temporal Difference · update right now

The Bellman equation says $V^\pi(s) = \mathbb{E}[r + \gamma V^\pi(s')]$ . After a single step $s \to s'$ with reward $r$ , use $r + \gamma V(s')$ — your current guess for $V(s')$ — as a target for $V(s)$ . No waiting: you learn a guess from a guess. Strength: online, works on non-terminating tasks, much lower variance. Weakness: biased — early on you learn towards garbage estimates of $V(s')$ .

key

The single sentence to remember

MC is patient and accurate; TD is impatient and noisy in a different way. MC uses the actual return — one full, honest sample — but pays the price in variance. TD uses the next reward plus the current value estimate — much less variance, but only because it trusts an estimate it just made up. The whole chapter is variations on this trade.

”Bootstrapping” — the word that does all the work

You’ll hear bootstrap over and over. It means: use your own current estimate of something as a target for learning more of it. TD bootstraps; MC does not. Dynamic programming bootstraps using the model; TD bootstraps using samples.

Monte Carlo — sample, no bootstrap

Use the real return $v_t$ . No estimate of future value appears in the update. Patient and honest, but waits for episodes to finish.

Temporal Difference — sample and bootstrap

Use one real reward plus the current estimate $V(s')$ . Online, low-variance, biased — the sweet spot for most RL applications.

Dynamic Programming — no sample, all bootstrap

Use the full expectation $\mathbb{E}[r + \gamma V(s')]$ via the known model. No sampling noise, but you must know $P$ and $R$ .

The two-doors thought experiment

One more vignette before we leave intuition. You stand before two doors. You open the left door and find a reward of $0$ . You open the right door three times and find rewards $+1, +3, +2$ . Your current best estimates are $V(\text{left}) = 0$ and $V(\text{right}) = 2$ .

Are you sure the right door is best? You have one observation behind the left door and three behind the right. The left door’s true mean could easily be $+5$ — you’d never know, because you stopped looking. A purely greedy agent locks onto the right door forever and accepts that it might be wrong. This is the exploration–exploitation dilemma in its simplest form, and ε-greedy is the simplest fix: with small probability ε, try a non-greedy action anyway.

!

A subtlety students miss

Exploration is not just about finding the best action — it is about being sure you’ve found it. Even after the right door looks better, you still need to test the left door enough times to rule it out. This is why convergence guarantees require every state–action pair to be visited infinitely often (the first half of the GLIE condition, formalised below).

Every algorithm in this chapter is some flavour of “sample, maybe bootstrap” — and TD(λ) is the dial that slides continuously between the MC and TD endpoints.

03 · Formalism

Definitions and equations

Let’s anchor the intuition. The MDP machinery is still in play: a state space $\mathcal{S}$ , an action space $\mathcal{A}$ , unknown dynamics $P(s' \mid s, a)$ , unknown reward $R(s, a)$ , and a discount factor $\gamma \in [0, 1)$ . The difference is that $P$ and $R$ are now hidden behind a simulator.

π(a|s): policy — a (possibly stochastic) rule mapping states to actions.
vₜ: return from time $t$ : $v_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots$ . For an episode of length $T$ this is a finite sum.
Vπ(s): state-value function $\mathbb{E}_\pi[v_t \mid s_t = s]$ — what you expect starting in $s$ and following $\pi$ forever.
Qπ(s,a): action-value function $\mathbb{E}_\pi[v_t \mid s_t = s, a_t = a]$ — what you expect taking $a$ once in $s$ then following $\pi$ .
α: step-size (learning rate). Small $\alpha$ is stable but slow; large $\alpha$ is fast but unstable.
δₜ: TD error — the discrepancy between the current estimate and the bootstrapped target.

Monte Carlo prediction

Run an episode under $\pi$ . For each visited state $s$ , compute the return $v_t$ from that point onward and update the running average.

MC update

V(s_t) \;\leftarrow\; V(s_t) + \alpha \bigl( v_t - V(s_t) \bigr)

With $\alpha = 1/N(s_t)$ you recover the exact running mean. With a small constant $\alpha$ you get an exponentially-weighted recency average — better for non-stationary problems where the value drifts.

First-visit MC averages returns only over the first time $s$ appears in each episode — an unbiased estimator. Every-visit MC uses every occurrence — biased on any single episode but consistent in the limit, and often simpler to implement. Both converge to $V^\pi(s)$ .

Temporal-difference prediction — TD(0)

The Bellman expectation equation reads $V^\pi(s) = \mathbb{E}_\pi[r + \gamma V^\pi(s')]$ . Take one sample of that expectation — observe $s, a, r, s'$ — and treat $r + \gamma V(s')$ as a noisy target for $V(s)$ .

TD(0) update

V(s_t) \;\leftarrow\; V(s_t) + \alpha \underbrace{\bigl( r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \bigr)}_{\text{TD error } \delta_t}

The TD target $r_{t+1} + \gamma V(s_{t+1})$ replaces the MC return $v_t$ . The update happens after a single transition — no waiting for episode termination.

The bias–variance trade-off, formally

Both updates push $V(s_t)$ toward a target. The question is what kind of target.

Quantity	MC return $v_t$	TD target $r_{t+1} + \gamma V(s_{t+1})$
Unbiased of $V^\pi(s_t)$ ?	Yes — $\mathbb{E}[v_t] = V^\pi(s_t)$ .	Only when $V = V^\pi$ (in the limit). Biased during training.
Variance	High — accumulates noise from every action, transition, reward across the whole episode.	Low — depends on one action, one transition, one reward.
Bootstraps?	No — uses the real return.	Yes — uses $V(s_{t+1})$ , an estimate.
Needs episode termination?	Yes.	No.
Exploits the Markov property?	No — uses the raw return.	Yes — relies on $V(s_{t+1})$ summarising the future.

n-step returns and TD(λ)

What if we don’t want to commit fully to either end? Look $n$ steps ahead, use the actual rewards, then bootstrap:

v_t^{(n)} \;=\; r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n-1} r_{t+n} + \gamma^n V(s_{t+n})

$n = 1$ is TD(0). $n \to \infty$ (or the episode end) is Monte Carlo. Intermediate $n$ blends the two — using more real signal than TD(0), less variance than MC.

TD(λ) averages all n-step returns with geometrically decaying weights $(1 - \lambda)\lambda^{n-1}$ :

λ-return

v_t^\lambda \;=\; (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} v_t^{(n)}

$\lambda = 0$ collapses to TD(0); $\lambda = 1$ recovers MC (modulo bookkeeping at episode ends). The weights sum to 1, so the λ-return is a proper convex combination.

Forward view vs backward view

The λ-return as written is a forward view: it looks at future rewards to compute the target. Elegant, but it requires waiting for the episode to finish. The backward view uses eligibility traces — a per-state memory that decays over time — to update online:

Eligibility trace

e_t(s) \;=\; \gamma \lambda \, e_{t-1}(s) + \mathbb{1}(s_t = s), \qquad V(s) \leftarrow V(s) + \alpha \, \delta_t \, e_t(s)

Each state’s trace bumps up when visited and decays each step. The TD error $\delta_t$ is applied to every state in proportion to its trace — sending credit backward through the trajectory. Sutton’s classical result: forward and backward views give identical updates when computed offline at the end of the episode.

Optional depth Accumulating vs replacing traces

The recipe $e_t(s) = \gamma\lambda\, e_{t-1}(s) + \mathbb{1}(s_t = s)$ is the accumulating trace: every revisit adds another 1 on top of the decayed history, so a frequently visited state can accumulate a trace greater than 1. In practice this can hurt convergence. The replacing trace caps the trace at 1 on each visit:

e_t(s) \;=\; \begin{cases} 1 & \text{if } s = s_t \\ \gamma \lambda \, e_{t-1}(s) & \text{otherwise} \end{cases}

Replacing traces give a cleaner credit-assignment signal and are the default for most TD(λ) and SARSA(λ) implementations.

SARSA(λ). The same trace machinery transfers to action-values: each state–action pair gets its own trace, and the one-step TD error is applied to every $(s, a)$ in proportion to its trace,

\delta_t = r_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t), \qquad Q(s, a) \leftarrow Q(s, a) + \alpha \, \delta_t \, e_t(s, a).

With $\lambda = 0$ this collapses to plain SARSA; with $\lambda = 1$ and offline updates it becomes Monte-Carlo control. Intermediate $\lambda$ is usually fastest, just as in prediction.

From prediction to control

Prediction estimates $V^\pi$ . Control searches for $\pi^*$ . The trick: instead of $V$ , learn the action-value $Q(s, a)$ and improve the policy greedily.

Greedy improvement

\pi'(s) \;=\; \arg\max_{a \in \mathcal{A}} Q(s, a)

Crucial: with $Q$ in hand, greedy improvement is model-free — no $P$ or $R$ . Compare to dynamic programming, where improving from $V$ required a one-step lookahead through the model.

Two famous control algorithms differ in one symbol:

SARSA · on-policy

$Q(s, a) \leftarrow Q(s, a) + \alpha\,[r + \gamma\, Q(s', a') - Q(s, a)]$ . Here $a'$ is the action actually chosen by the (ε-greedy) behaviour policy. We learn the value of the policy we’re executing — exploration costs included.

Q-learning · off-policy

$Q(s, a) \leftarrow Q(s, a) + \alpha\,[r + \gamma \max_{a'} Q(s', a') - Q(s, a)]$ . We bootstrap off the best next-state action, not the one we’ll take. We learn the value of the greedy policy while behaving ε-greedily — pure off-policy.

That one symbol changes where the agent ends up walking. The standard test is a gridworld with a cliff along the bottom edge: stepping in costs $-100$ and teleports you back to the start.

Q-learning’s target is $\max_{a'} Q(s', a')$ , which assumes the next action will be greedy. Under that assumption the row directly above the cliff is worth exactly what the shortest path is worth, so Q-learning learns to walk the edge. SARSA’s target is $Q(s', a')$ for the $a'$ its ε-greedy policy will actually choose — so the chance of a random step over the edge is baked into the value of those cells, they end up worth less than the detour, and SARSA routes around them.

Neither is wrong; they answer different questions. With $\varepsilon > 0$ SARSA collects more reward while training, because it is evaluating the policy that is really running. Q-learning converges to the genuinely optimal greedy policy — which is only the better policy once you stop exploring.

Off-policy learning — learning π while behaving as µ

SARSA and Q-learning illustrate the two stances in miniature, but the off-policy idea is more general. Sometimes we want to evaluate or improve a target policy $\pi$ while collecting data from a different behaviour policy $\mu$ . Why bother?

To reuse old data collected under earlier policies $\pi_1, \pi_2, \dots$ without throwing it away.
To learn from demonstrations — humans or experts whose policy is not the one you’re training.
To learn about $\pi^*$ while exploring — exactly what Q-learning does.
To learn multiple policies simultaneously from a single stream of experience.

For Monte-Carlo prediction, naïvely averaging returns gathered under $\mu$ gives you $V^\mu$ , not $V^\pi$ . The standard fix is importance sampling: re-weight each return by the likelihood ratio of the trajectory under the two policies.

Importance-sampled MC return

v_t^{\pi/\mu} \;=\; \prod_{k=t}^{T-1} \frac{\pi(a_k \mid s_k)}{\mu(a_k \mid s_k)} \; v_t

Each step where the policies disagree on the action’s probability gets weighted by the ratio. Required: $\mu$ must be non-zero wherever $\pi$ is (coverage). The variance can explode for long episodes — it is a product of $T$ ratios.

For TD, only a single importance ratio is needed, because we bootstrap just one step ahead:

Importance-sampled TD target

Q(s_t, a_t) \;\leftarrow\; Q(s_t, a_t) + \alpha \left( r_{t+1} + \gamma \, \frac{\pi(a_{t+1} \mid s_{t+1})}{\mu(a_{t+1} \mid s_{t+1})} \, Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \right)

Much lower variance than the MC form — the two policies only need to be similar over a single step.

Q-learning’s elegance is that it sidesteps importance sampling entirely: bootstrapping from $\max_{a'} Q(s', a')$ is equivalent to evaluating the deterministic greedy target policy at $s'$ , which assigns probability 1 to that single action — no ratio needed.

GLIE — the condition that makes everything converge

Greedy in the Limit with Infinite Exploration is the two-part promise we need from our exploration schedule:

Every state–action pair is visited infinitely often: $\lim_{k \to \infty} N_k(s, a) = \infty$ .
The policy converges to the greedy policy: $\lim_{k \to \infty} \pi_k(a \mid s) = \mathbb{1}(a = \arg\max_{a'} Q_k(s, a'))$ .

A simple GLIE recipe: use ε-greedy with $\varepsilon_k = 1/k$ . Early on you explore freely; later you settle into the greedy policy. Under GLIE plus the Robbins–Monro step-size conditions $\sum_k \alpha_k = \infty$ and $\sum_k \alpha_k^2 < \infty$ , both SARSA and Q-learning provably converge to $Q^*$ .

The three time-scales of RL

A practical rule of thumb behind every working implementation: three quantities must be tuned and they live on different scales.

Scale	Symbol	What it controls	Typical range
Behavioural horizon	$1 - \gamma$	how far into the future a reward still matters	0.01 – 0.10
Estimation rate	$\alpha$	how fast value estimates absorb new evidence	0.01 – 0.20, often annealed
Exploration rate	$\varepsilon$	how often the agent deviates from greedy	0.01 – 0.20, often annealed

The classical recommendation is $1 - \gamma \gg \alpha \gg \varepsilon$ : optimise over a horizon longer than the learning rate, and explore less often than you learn. Anneal $\varepsilon$ faster than $\alpha$ , so that once the agent has settled into a sensible policy it stops wasting steps on random actions. A common schedule: $\alpha_k = 1/k$ , $\varepsilon_k = 1/k$ — satisfying both Robbins–Monro and GLIE.

04 · Worked example

MC vs TD(0) on a tiny three-state chain

Time to make every formula concrete. We watch MC and TD(0) update the same value function on a small Markov reward process, doing each arithmetic step by hand, so you see why they disagree and what each is actually doing.

States are $s_1, s_2, s_3$ (non-terminal) and $T$ (terminal). Dynamics are deterministic: from any $s_i$ you transition to $s_{i+1}$ (with $s_4$ understood as $T$ ). The reward is $0$ on every step except the final transition into $T$ , which pays $+1$ . The discount factor is $\gamma = 1$ . The true values are obvious: $V^\pi(s_1) = V^\pi(s_2) = V^\pi(s_3) = 1$ and $V^\pi(T) = 0$ . We initialise all estimates to $V(s_i) = 0$ and use $\alpha = 0.5$ so the arithmetic stays clean.

Worked example One episode under MC, then under TD(0)

1 · One episode under Monte Carlo

We sample the only possible trajectory $s_1 \to s_2 \to s_3 \to T$ with rewards $0, 0, +1$ . First-visit MC computes the return from each visited state: $v_{s_1} = 0 + 0 + 1 = 1$ , $v_{s_2} = 0 + 1 = 1$ , $v_{s_3} = 1$ . Each state is visited once, so the running average is the single observation.

2 · MC updates all three at once

With $\alpha = 0.5$ :

V(s_i) \leftarrow 0 + 0.5\,(1 - 0) = 0.5 \quad \text{for } i = 1, 2, 3.

After one episode all three estimates jump to $0.5$ together. MC sees the full reward signal and applies it everywhere it should land, in a single step.

3 · The same episode under TD(0)

TD(0) updates after every transition, using the current estimate of $V(s_{t+1})$ at the moment of each update. $s_1 \to s_2$ , reward 0: target $r + \gamma V(s_2) = 0 + 0 = 0$ , error $\delta = 0 - 0 = 0$ , so $V(s_1)$ stays at 0. $s_2 \to s_3$ , reward 0: same story, $V(s_2)$ stays at 0.

4 · The reward finally bites

$s_3 \to T$ , reward 1: target $1 + \gamma V(T) = 1 + 0 = 1$ , error $\delta = 1 - 0 = 1$ , update $V(s_3) \leftarrow 0 + 0.5 \cdot 1 = 0.5$ . End of episode 1: $V(s_1) = 0$ , $V(s_2) = 0$ , $V(s_3) = 0.5$ . Only the state adjacent to the rewarding terminal transition has learned anything.

5 · The deep difference

After one episode MC has updated all three states to 0.5; TD(0) has updated only $s_3$ . MC is “patient” — it waits for the full return and credits everyone. TD(0) is “stingy” — it updates only as far as its current estimates let it bootstrap. But run a second episode: now $V(s_3) = 0.5$ already, so the $s_2 \to s_3$ target is $0 + 0.5 = 0.5$ and $V(s_2)$ finally moves. The reward signal seeps backward one state per episode; both methods converge to the true values. What TD bought: each update was much less variable, because each TD target depended on one reward, not three.

map

Map the example back onto the formalism

MC return: $v_{s_1} = 1$ — uses real rewards all the way to $T$ , gives full credit immediately.
TD(0) target at $s_1$ : $r + \gamma V(s_2) = 0 + 0 = 0$ — uses the current estimate of $V(s_2)$ , which is zero. Nothing to learn yet.
Bias: after one episode TD’s estimate of $V(s_1)$ is 0, far from the truth — TD is biased early. MC’s 0.5 is unbiased even if noisy.
Variance: over $N$ episodes, MC’s estimate of $V(s_1)$ would fluctuate with the return distribution; TD’s converges with much smaller fluctuations because each update uses only one reward.

On a deterministic chain like this the difference is mild. In a real environment with stochastic transitions and rewards, MC’s high variance becomes painful and TD’s lower variance is worth its early bias. The hands-on labs show that picture on a stochastic random walk.

05 · Visual explanation

The backup diagram, and why it explains everything

The backup-diagram zoo

Every value-update method in this course can be classified by two binary axes: does it bootstrap? and does it sample? The combinations give four cells; three are populated by methods you already know.

Read it left-to-right and you see the historical sequence: dynamic programming gave us bootstrapping with a known model. MC traded the model for sampling but lost bootstrapping. TD recovered both. Every method in the rest of the chapter sits somewhere on the spectrum between MC (pure right) and TD(0) — and that spectrum is exactly what TD(λ) makes navigable.

Reward propagation through the trajectory

The worked example showed that TD only propagates reward one state per episode. MC paints the whole trajectory in one stroke (a high-information update, but the stroke wobbles a lot when the environment is stochastic). TD paints one cell per episode (each stroke steady, but you need many episodes for the colour to reach the start). TD(λ) with eligibility traces is the compromise — paint several cells per episode, fading out as you go backward.

Eligibility traces in motion

An eligibility trace is a memory of recent visits. Every step, each state’s trace decays by $\gamma\lambda$ ; when a state is visited, its trace bumps up by 1. When a TD error happens, it is applied to every state in proportion to its trace. The trace acts as a credit-assignment heuristic: a state gets credit for a TD error in proportion to how recently and how frequently it was visited. Pick $\lambda = 0$ and only the current state has a non-zero trace — that’s TD(0). Pick $\lambda = 1$ and traces last forever (until reset) — that’s MC.

view

Forward and backward views are the same picture

The forward view says: “to update $V(s_t)$ , look at the weighted average of all n-step returns starting from $t$ .” The backward view says: “to update every state, accumulate the TD error $\delta_t$ into the traces of all recently visited states.” When you sum the updates across an entire episode, the two come out algebraically identical. The backward view is just the forward view rotated by 90° so it can run online.

06 · Bandits

When there is only one state

Take an MDP and delete the part that makes it an MDP — the state. What is left is a multi-armed bandit: one state, $K$ actions, and an unknown reward distribution behind each. Nothing you do changes what happens next, so there is no credit assignment, no bootstrapping, no Bellman equation. The only thing left is the exploration–exploitation trade-off, in its purest form — which is exactly why it gets studied on its own.

why

The two doors, every night

Remember the two doors from §2. Now suppose the doors reset overnight: whatever you found behind one tonight tells you nothing about tomorrow’s world, only about that door’s average payout. You get $T$ nights. Every night you must pick a door, and you only ever see the payout of the door you opened — never the other one.

That last clause is the whole difficulty. This is not supervised learning: you don’t get a label for the action you didn’t take. The name comes from slot machines, “one-armed bandits” — $K$ of them, each paying out at an unknown rate.

Q

Ten questions, seven sessions, 30 marks

Bandits are asked in 7 of the 12 sessions in the question bank — 10 questions worth 30 of 477 marks (6.3%) — and they are the only topic in this chapter that has appeared as a dedicated 4-point Exercise 8 in both of the two most recent sessions (2026-02 and 2026-06).

The asked shape is remarkably stable, in three parts: (1) compute the regret from a table of pulls, (2) say which arm UCB1 plays next and justify it, (3) give the Beta posteriors and say which arm Thompson Sampling probably plays. Graders want the arithmetic and one sentence of motivation for each part.

Regret — the only score that matters

You cannot score a bandit algorithm by its total reward, because that depends on how generous the arms happen to be. You score it by what it lost against an oracle that knew the best arm all along. Write $\mu_i$ for arm $i$ ‘s expected reward, $\mu^* = \max_i \mu_i$ for the best, and $\Delta_i = \mu^* - \mu_i$ for arm $i$ ‘s gap.

Pseudo-regret after T rounds

R_T \;=\; T\mu^* - \sum_{i=1}^{K} \mu_i\, T_i \;=\; \sum_{i=1}^{K} \Delta_i\, T_i

$T_i$ is the number of times arm $i$ was pulled, so $\sum_i T_i = T$ . The two forms are the same sum rearranged, and the right-hand one is the one to use in the exam: regret is gaps times pulls. The optimal arm has $\Delta = 0$ and therefore contributes nothing, no matter how often it was played.

This immediately tells you what a good algorithm must do: pull high-gap arms only a few times. It cannot pull them zero times — it doesn’t know the gaps — so the entire game is finding out which arms are bad while paying as little as possible for the information.

×

Counting the optimal arm's pulls in the regret

The single most common slip on this exercise. If arm $a_7$ is optimal and was pulled 5 times, those 5 pulls add $\Delta_7 \times 5 = 0 \times 5 = 0$ — not $\mu_7 \times 5$ . Sum $\Delta_i T_i$ over the suboptimal arms only; including the best arm’s term is harmless only because it is zero, but students who use $T\mu^* - \sum \mu_i T_i$ often forget the $T\mu^*$ and get a negative number.

Two ways to let uncertainty speak

ε-greedy explores by flipping a coin — a fixed rate of pure noise, blind to which arm is worth investigating. Both algorithms below do something smarter: they let each arm’s uncertainty argue for it. An arm pulled twice is not “as good as” an arm pulled two hundred times with the same mean; it is less known, and that is a reason to try it.

Look at what happens to $a_2$ in both panels. It has the lowest sample mean of the three ( $0.50$ against $0.63$ and $0.56$ ), and it is played anyway — by both rules, for the same underlying reason and by two different mechanisms. UCB1 adds a bonus that is large precisely because $a_2$ has only 6 pulls, pushing the top of its interval to $1.69$ , above everything else. Thompson keeps a posterior that is wide for the same reason, so a single random draw from it can easily land high — the three dots marked draws in the right panel are one such round, and $a_2$ ‘s is the rightmost at $0.84$ , so it wins. Neither rule is being generous to a bad arm — both are saying the same thing: we do not yet know that it is bad.

UCB1 index — optimism in the face of uncertainty

\text{UCB}_i(t) \;=\; \underbrace{\bar{x}_i}_{\text{exploit}} \;+\; \underbrace{\sqrt{\frac{2\ln t}{n_i}}}_{\text{explore}} \qquad\text{play}\quad a_t = \arg\max_i \text{UCB}_i(t)

$\bar{x}_i$ is the empirical mean of the rewards actually observed from arm $i$ , and $n_i$ its pull count; $t$ is the round number. The bonus shrinks as $1/\sqrt{n_i}$ when you pull an arm, and grows as $\sqrt{\ln t}$ for every arm you don’t — so a neglected arm slowly becomes attractive again, which is what stops UCB1 from locking onto a wrong early winner. Every arm is played once first, or the bonus is undefined.

Step-through Worked example

Thompson Sampling — keep a posterior, not an estimate

For Bernoulli rewards, put a $\text{Beta}(\alpha_i, \beta_i)$ prior on each arm’s unknown success probability. The uniform prior is $\text{Beta}(1,1)$ .

Sample one value per arm

Each round, draw $\theta_i \sim \text{Beta}(\alpha_i, \beta_i)$ independently for every arm. This is the randomisation — it is not a tie-break, it is the exploration.

Play the argmax of the samples

Pull $a_t = \arg\max_i \theta_i$ . An arm with a wide posterior sometimes draws high and gets tried; an arm shown to be poor rarely does.

Update only the arm you pulled

On reward $r \in \{0, 1\}$ : $\alpha_i \mathrel{+}= r$ and $\beta_i \mathrel{+}= 1 - r$ . After $s$ successes and $f$ failures from a uniform prior the posterior is $\text{Beta}(s+1, f+1)$ , whose mean is $\frac{s+1}{s+f+2}$ and whose mode is exactly the sample mean $s/(s+f)$ .

Exploration here is self-annealing: as evidence accumulates the posteriors concentrate, the draws stop straying, and the algorithm exploits — without you scheduling anything. That is the structural advantage over ε-greedy, which keeps wasting an $\varepsilon$ fraction of every round forever unless you decay it by hand.

Worked example — the exam’s three parts

Use the three arms from the diagram: after $t = 71$ pulls, $a_1$ has $25$ successes in $40$ pulls, $a_2$ has $3$ in $6$ , and $a_3$ has $14$ in $25$ .

(1) Regret. Suppose the true means are $\mu = (0.60,\ 0.45,\ 0.55)$ , so $a_1$ is optimal and $\Delta = (0,\ 0.15,\ 0.05)$ . Then

R_{71} = 0\cdot 40 + 0.15\cdot 6 + 0.05\cdot 25 = 0.9 + 1.25 = 2.15 .

(2) UCB1. Empirical means are $\bar{x}_1 = 25/40 = 0.625$ , $\bar{x}_2 = 3/6 = 0.50$ , $\bar{x}_3 = 14/25 = 0.56$ . With $2\ln 71 \simeq 8.53$ :

Arm	$\bar{x}_i$	bonus $\sqrt{2\ln t / n_i}$	index
$a_1$	$0.625$	$\sqrt{8.53/40} = 0.46$	$1.09$
$a_2$	$0.500$	$\sqrt{8.53/6\phantom{0}} = 1.19$	$\mathbf{1.69}$
$a_3$	$0.560$	$\sqrt{8.53/25} = 0.58$	$1.14$

UCB1 plays $a_2$ — the worst arm by sample mean, because it is the least explored.

(3) Thompson. From a uniform prior the posteriors are $\text{Beta}(26, 16)$ , $\text{Beta}(4, 4)$ and $\text{Beta}(15, 12)$ . Their means are $26/42 = 0.62$ , $4/8 = 0.50$ and $15/27 = 0.56$ , so on average $a_1$ is most likely to be played — but $a_2$ ‘s posterior is much flatter, so its draw has real probability of exceeding $a_1$ ‘s. Say that: Thompson’s answer is a probability, never a certainty, and the grader is looking for the two posteriors plus that sentence.

×

Plugging the true means into UCB1

Named explicitly in the 2026 solutions. UCB1 does not know $\mu_i$ — if it did there would be nothing to learn. Its index is built from the observed $\bar{x}_i$ plus the bonus. The true means appear only in the regret computation, which is an after-the-fact analysis you can do because the exam told you the answer, not something the algorithm has access to.

×

Thinking Thompson explores at a fixed rate

ε-greedy explores at rate $\varepsilon$ regardless of what it knows. Thompson has no exploration parameter at all — the exploration is a side effect of posterior width, so it is adaptive (uncertain arms get tried) and self-annealing (it fades as the posteriors sharpen). “It’s like ε-greedy with a random ε” earns no marks.

Deep dive Where the √(2 ln t / n) bonus comes from, and the log-regret bound

The bonus is a Hoeffding confidence bound. For an arm with rewards in $[0,1]$ pulled $n_i$ times, Hoeffding’s inequality gives

\mathbb{P}\bigl( \mu_i > \bar{x}_i + u \bigr) \;\leq\; e^{-2 n_i u^2}.

Choose the failure probability $t^{-4}$ — small enough that, summed over all rounds and arms, the bound essentially never fails. Setting $e^{-2 n_i u^2} = t^{-4}$ and solving gives $u = \sqrt{\frac{2\ln t}{n_i}}$ , which is exactly the UCB1 bonus. So $\text{UCB}_i(t)$ is an upper end of a confidence interval for $\mu_i$ , and “play the largest index” is the principle of optimism in the face of uncertainty: act as if the world is as good as it plausibly could be, and you either do well or learn something.

The payoff is the regret bound. A suboptimal arm stops being selected once its interval separates from the optimal arm’s, which happens after roughly $n_i \approx \frac{8\ln T}{\Delta_i^2}$ pulls, giving

R_T \;\leq\; \sum_{i:\,\Delta_i > 0} \frac{8\ln T}{\Delta_i} + O(1)\;=\;O(\log T).

Logarithmic regret is optimal — the Lai–Robbins lower bound says no algorithm can do better than $\Omega(\log T)$ on every problem. Thompson Sampling attains the same $O(\log T)$ rate and matches the constant in the Lai–Robbins bound for Bernoulli arms, which is why it typically edges out UCB1 empirically despite being the simpler idea. Compare with ε-greedy at a fixed $\varepsilon$ : it pulls suboptimal arms a constant fraction of the time forever, so $R_T = \Theta(T)$ — linear, and therefore infinitely worse in the long run. Decaying $\varepsilon_t \sim 1/t$ recovers $O(\log T)$ , which is the same GLIE condition you met in §2.

key

Why this sits in the RL chapter at all

A bandit is an MDP with $\lvert \mathcal{S}\rvert = 1$ , so everything here is the one-state corner of the machinery in §3 — with no next state to carry value into, the discount $\gamma$ never bites and the Bellman equation collapses to “estimate each arm’s mean”. That is also why bandit algorithms do not solve MDPs. UCB1 and Thompson optimise immediate reward; they have no notion of a state to carry value into, so they cannot do credit assignment. Go the other way, though, and the ideas transfer: optimistic initialisation in Q-learning is UCB’s trick, and posterior sampling over MDPs is Thompson’s.

Now try the real thing — these are past-exam items, in the format described above.

2026-06-q82026Q08Multi-armed bandits — UCB1 & Thompson Samplingmedium4 pts

Consider a MAB with binary rewards and two arms $\{a_1, a_2\}$ over a horizon $T = 8$. The table reports the reward $R_t$ each round (only the played arm's reward is revealed): ``` t 1 2 3 4 5 6 7 8 Reward from a1 1 1 0 1 1 Reward from a2 0 1 0 ``` 1. Knowing the expected rewards $\mu_1 = 0.75$ and $\mu_2 = 0.25$, compute the expected regret over $T$. 2. Which arm would UCB1 play in round $t = 9$? Use $\sqrt{\frac{2\ln 8}{5}} \simeq 0.91$ and $\sqrt{\frac{2\ln 8}{3}} \simeq 1.18$. Motivate your answer. 3. Which arm is Thompson Sampling (uniform Beta prior at $t=0$) more likely to play at $t = 9$? Give the two posterior distributions.

2023-08-q82023Q08Multi-armed bandits — regretmedium4 pts

Consider a stochastic Multi-Armed Bandit (MAB) with 10 arms whose real expected rewards are, respectively, $\mu = (0.5,\ 0.2,\ 0.1,\ 0.0,\ 0.2,\ 0.4,\ 0.6,\ 0.1,\ 0.1,\ 0.3)$. 1. Which arm will Thompson Sampling converge to as $T \to \infty$ (starting from a uniform prior)? 2. Assuming the arms have been pulled $T_1 = 5,\ T_2 = 50,\ T_3 = 10,\ T_4 = 5,\ T_5 = 10,\ T_6 = 10,\ T_7 = 5,\ T_8 = 10,\ T_9 = 2,\ T_{10} = 10$ times, compute the pseudo-regret accumulated so far. Motivate your answers.

thompson-samplingBanditshard4 pts

Describe the Thompson Sampling algorithm for multi-armed bandit (MAB) problems.

07 · Hands-on

Try it yourself

Four interactive widgets, each engineered to make one core idea move under your finger. Read the instruction, push the controls, then read the takeaway.

Hands-on 1

MC vs TD(0) on a random walk

Seven-state random walk: start in the middle, step left or right with equal probability, reward +1 only if you exit on the right. The MC estimate (red) and the TD(0) estimate (gold) are plotted against the true value V(sᵢ) = i/6 (blue dashed). Advance episodes and tune α to watch the two methods differ.

learning rate α0.10

ep 0

Episodes

0

RMSE · MC

—

RMSE · TD

—

Try thisReset, set α = 0.10, and click "+10 episodes" three times. The TD curve hugs the true line quickly with a small early bias, while the MC curve wobbles around it with larger swings. Now bump α to 0.40 and step again — MC's full-return noise kicks the estimates around far more than TD's single-reward targets.

TakeawayOn a stochastic task TD(0) reaches a low-RMSE solution with fewer episodes than MC. MC is unbiased but every update is a noisy full return; TD bootstraps from a lower-variance target and pays a small bias. The trade is bias for variance — and TD usually wins on sample efficiency.

Hands-on 3

Why you must explore — ε-greedy on a bandit

Three slot machines with true means μ = (0.30, 0.55, 0.50) — machine B is best, C a close runner-up. Each Q̂(a) is the sample mean of ε-greedy pulls; regret accumulates as Σ (μ* − μ(aₜ)). Too small an ε locks onto a sub-optimal arm; too large an ε pays an exploration tax forever.

ε (exploration)0.10

0 pulls

Q̂(A) · μ=0.30

—

Q̂(B) · μ=0.55

—

Q̂(C) · μ=0.50

—

Total regret

—

Optimal-arm share: —

Try thisSet ε = 0.00 (pure exploitation), reset, and step a few times — the agent may "lock in" on whichever arm happened to look best first, often not the true best. Bump ε to 0.10: it mostly plays greedily yet keeps sampling, and Q̂(B) converges to its true mean. Crank ε to 0.50 and regret grows roughly linearly — you keep exploring long after the answer is clear.

TakeawayNo exploration → you may never find the best arm. Too much → you pay for it forever. The GLIE recipe εₖ = 1/k gets both: ample exploration early, vanishing exploration eventually — the same principle that makes SARSA and Q-learning converge.

Hands-on 4

SARSA vs Q-learning on the cliff

Walk from S (bottom-left) to G (bottom-right). The bottom row between them is a cliff: stepping on it costs −100 and snaps you back to S; every other step costs −1. Both agents train ε-greedy with ε = 0.1, α = 0.5, γ = 1. Arrows show the greedy policy; the line traces it from S. The optimal path runs along the cliff edge; the safe path detours upward.

0 episodes

SARSA (on-policy) — safe detour

Q-learning (off-policy) — cliff edge

SARSA · avg return

—

Q-learn · avg return

—

SARSA greedy len

—

Q-learn greedy len

—

Try thisReset and train a few batches. You will reliably see SARSA pick the upper route and Q-learning hug the cliff edge. Now compare the average return per episode: with ε = 0.1 SARSA's realised return is better, because Q-learning's cliff-edge policy occasionally explores a step right into the cliff. Q-learning learns the better policy; SARSA learns the better online policy.

TakeawaySARSA bootstraps from Q(s′, a′) for the action it will actually take — including ε-explorations — so it learns "this edge is risky." Q-learning bootstraps from max Q(s′, a′), ignoring the exploration cost, so it learns the truly optimal greedy policy but behaves recklessly while exploring. As ε → 0 the two converge.

key

Hands-on 2 — the TD(λ) dial

The fourth idea — TD(λ) interpolating between TD(0) and MC — is best felt by re-reading §3 with the $\lambda$ -return in front of you. Slide $\lambda$ mentally from 0 to 1: at $\lambda = 0$ almost all weight sits on the 1-step return (pure TD(0)); at $\lambda = 1$ the weight spreads far into the future (pure MC). The RMSE-vs- $\lambda$ curve is typically a shallow U — an intermediate $\lambda \in [0.4, 0.8]$ beats both extremes, because combining several n-step targets averages out per-step noise (variance reduction) while also reducing the single-step bootstrap bias. A first guess of $\lambda \approx 0.7$ works for many problems.

08 · Exam intel

What the exam actually tests

This chapter is high-yield: clean update rules, standard comparison tables, predictable derivations. Eight question shapes appear repeatedly.

Q1

Write the update rule for MC / TD / SARSA / Q-learning

Memorise these four lines verbatim — they’re the building blocks of half the exam.

Method	Update	Target
MC	$V(s_t) \leftarrow V(s_t) + \alpha(v_t - V(s_t))$	actual return
TD(0)	$V(s_t) \leftarrow V(s_t) + \alpha(r_{t+1} + \gamma V(s_{t+1}) - V(s_t))$	bootstrapped
SARSA	$Q(s, a) \leftarrow Q(s, a) + \alpha(r + \gamma Q(s', a') - Q(s, a))$	$a'$ actually taken
Q-learning	$Q(s, a) \leftarrow Q(s, a) + \alpha(r + \gamma \max_{a'} Q(s', a') - Q(s, a))$	$\max_{a'}$ — off-policy

Q2

Compare MC and TD on the standard axes

	Monte Carlo	TD(0)
Bias	unbiased	biased (until convergence)
Variance	high	low
Bootstraps?	no	yes
Needs terminating episodes?	yes	no
Exploits Markov property?	no	yes
Sensitivity to initial $V$	low	higher

Q3

Why does Q-learning need the max but SARSA doesn't?

The two differ in which next-state action they bootstrap from. SARSA uses the action $a'$ the behaviour policy will actually take, so it learns $Q^\pi$ for that policy — on-policy. Q-learning uses $\max_{a'} Q(s', a')$ , bootstrapping from the greedy action regardless of behaviour, so it learns $Q^*$ — off-policy. The full answer mentions: (i) the Bellman expectation equation for SARSA, the Bellman optimality equation for Q-learning; (ii) under GLIE both converge to $Q^*$ ; (iii) for any fixed $\varepsilon > 0$ SARSA produces a safer online policy and Q-learning a riskier one — the cliffwalking example.

Q4

State the convergence conditions

For SARSA and Q-learning to converge to $Q^*$ you need two ingredients:

GLIE behaviour: every $(s, a)$ pair visited infinitely often; the policy converges to the greedy one. Canonical recipe: ε-greedy with $\varepsilon_k = 1/k$ .
Robbins–Monro step sizes: $\sum_k \alpha_k = \infty$ and $\sum_k \alpha_k^2 < \infty$ . The classic choice $\alpha_k = 1/k$ satisfies both.

For MC: just GLIE (plus a Robbins–Monro step size if using exponential averaging). For TD(0) prediction with fixed $\pi$ : just Robbins–Monro.

Q5

Show that forward TD(λ) = backward TD(λ)

The textbook proof is a telescoping argument. Take $\lambda = 1$ : the forward view gives the MC update $V(s_t) \leftarrow V(s_t) + \alpha(v_t - V(s_t))$ . The backward view sums TD errors weighted by traces; for an episode of length $T - t$ , the trace of $s_t$ when $\delta_{t+k}$ is emitted equals $\gamma^k$ , so the total update at $s_t$ is

\sum_{k=0}^{T-t-1} \alpha\, \gamma^k\, \delta_{t+k} = \alpha \sum_{k=0}^{T-t-1} \gamma^k \bigl(r_{t+k+1} + \gamma V(s_{t+k+1}) - V(s_{t+k})\bigr).

Telescope the $V$ -terms: each $\gamma^k V(s_{t+k+1})$ cancels with $-\gamma^{k+1} V(s_{t+k+1})$ in the next term, leaving $-V(s_t)$ and a sum of discounted rewards — which is exactly $v_t$ . So the accumulated backward-view update equals $\alpha(v_t - V(s_t))$ , the forward-view update at $\lambda = 1$ . For general $\lambda$ , the same telescoping with $\gamma\lambda$ traces yields the λ-return update. Key insight: the equivalence holds offline; online updates introduce small differences that vanish as $\alpha \to 0$ .

Q6

Off-policy MC requires importance sampling — why?

Returns sampled under behaviour policy $\mu$ are drawn from a different distribution than returns under the target $\pi$ . To estimate $\mathbb{E}_\pi[v_t]$ from $\mu$ -samples, re-weight each by the trajectory likelihood ratio:

\mathbb{E}_\pi[v_t] = \mathbb{E}_\mu\!\left[ \prod_{k=t}^{T-1} \frac{\pi(a_k \mid s_k)}{\mu(a_k \mid s_k)} \, v_t \right].

Two traps: (i) the ratio is over the whole episode for MC but a single step for TD, so off-policy TD has dramatically lower variance; (ii) the method fails whenever $\mu(a \mid s) = 0$ and $\pi(a \mid s) > 0$ — the coverage condition. Q-learning is special: its target policy is greedy, so $\pi(a' \mid s') = 1$ at $a' = \arg\max$ and 0 elsewhere — the ratio collapses to the indicator inside the $\max$ .

Q7

Classify a method on the four dichotomies — and the DP↔TD map

Method	Model	On/off-policy	Bootstrap?	Online?
Value iteration (DP)	model-based	—	yes	no
MC control	free	on	no	no (per-episode)
SARSA	free	on	yes	yes
Q-learning	free	off	yes	yes

Every TD-style update is the sample version of a DP backup. Iterative policy evaluation $V(s) \leftarrow \mathbb{E}_\pi[r + \gamma V(s')]$ becomes TD(0) $V(s) \xleftarrow{\alpha} r + \gamma V(s')$ . Q-policy iteration $Q(s,a) \leftarrow \mathbb{E}_\pi[r + \gamma Q(s', a')]$ becomes SARSA. Q-value iteration $Q(s,a) \leftarrow \mathbb{E}[r + \gamma \max_{a'} Q(s', a')]$ becomes Q-learning. Same Bellman equation; the left column takes the expectation through the model, the right replaces it with one sampled transition and an $\alpha$ -smoothed update.

Q8

Bandits: regret, UCB1, Thompson — the three-part exercise

Asked in 7 of 12 sessions (30 of 477 marks), and a standalone 4-point Exercise 8 in both 2026 sessions. Always the same three moves:

Regret — $R_T = \sum_i \Delta_i T_i$ with $\Delta_i = \mu^* - \mu_i$ . Gaps times pulls; the optimal arm contributes $0$ .
UCB1 — $\text{UCB}_i = \bar{x}_i + \sqrt{2\ln t / n_i}$ , using the empirical mean, never $\mu_i$ . Compute every index, compare, name the winner, say why (least-explored arm keeps the largest bonus).
Thompson — from a uniform prior, $s$ successes and $f$ failures give $\text{Beta}(s+1, f+1)$ . Quote both posteriors and answer with a probability, not a certainty.

The exam usually hands you the square roots pre-computed, which is a strong hint that it wants the comparison and the justification, not the arithmetic.

tip

Eight formulas — that's the whole chapter

MC return: $v_t = \sum_{k=0}^{T-t-1} \gamma^k r_{t+k+1}$ .
TD(0): $V(s_t) \leftarrow V(s_t) + \alpha(r_{t+1} + \gamma V(s_{t+1}) - V(s_t))$ .
λ-return: $v_t^\lambda = (1-\lambda)\sum_{n \geq 1} \lambda^{n-1} v_t^{(n)}$ .
Eligibility trace: $e_t(s) = \gamma\lambda\, e_{t-1}(s) + \mathbb{1}(s_t = s)$ .
SARSA: $Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma Q(s', a') - Q(s, a))$ .
Q-learning: $Q(s,a) \leftarrow Q(s,a) + \alpha(r + \gamma \max_{a'} Q(s', a') - Q(s, a))$ .
Pseudo-regret: $R_T = \sum_i \Delta_i T_i$ , $\Delta_i = \mu^* - \mu_i$ .
UCB1 index: $\text{UCB}_i(t) = \bar{x}_i + \sqrt{2\ln t / n_i}$ .

09 · Common mistakes

Where students get this wrong

×

'TD is just a noisy version of MC'

Completely backwards. TD has lower variance than MC — each TD target depends on one reward and one bootstrapped estimate, while the MC return aggregates noise from the whole episode. What TD pays is bias: while the value estimates are still learning, the bootstrap targets are wrong. The trade isn’t variance for speed — it’s bias for variance.

×

'Q-learning is better because it converges to Q*'

Both algorithms converge to $Q^*$ under GLIE. The difference is what they do during learning. SARSA learns the value of the policy it is actually executing, so it accounts for the cost of exploration; Q-learning learns the value of the greedy policy regardless of behaviour. On cliffwalking with $\varepsilon > 0$ SARSA realises higher returns even though Q-learning’s final policy is technically optimal. Which is “better” depends on whether you care about asymptotic optimality or online safety.

×

'More exploration is always safer'

The opposite is sometimes true. In cliffwalking, more exploration is exactly what makes Q-learning’s “optimal” cliff-edge policy dangerous — every random action near the cliff risks falling in. And a high constant ε means you keep exploring long after identifying the best action, paying a linear regret penalty forever. Exploration schedules should decay — that’s the GLIE condition.

×

'TD(λ) with λ = 1 is exactly MC'

Only when computed offline (updates batched until end of episode). With online updates and a non-zero learning rate, TD(1) and every-visit MC differ in the order updates land — TD(1) interleaves them with bootstrapping that hasn’t fully settled. The two are algebraically equivalent over a complete episode, numerically not quite the same in an online loop.

×

Improving π from V without a model

Greedy improvement from $V(s)$ requires $\arg\max_a [R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')]$ — which needs the model. That’s why model-free control uses $Q(s, a)$ : greedy improvement is just $\arg\max_a Q(s, a)$ , no $P$ or $R$ required. Forgetting this is a textbook way to get stuck in a model-free derivation.

×

'Eligibility traces are an optimisation trick'

They are a credit-assignment algorithm, not a speedup. Forward-view TD(λ) and backward-view TD(λ) compute the same updates — traces just make it possible to do so online and incrementally. Without traces, you’d have to wait until the end of each episode to apply the λ-return.

×

Confusing α with γ

Two completely different roles. $\alpha$ controls how fast you trust new information — a hyperparameter of the algorithm, typically small ( $\approx 0.1$ ) and possibly annealing. $\gamma$ is a property of the problem — how much future rewards matter relative to immediate ones. It usually sits between 0.9 and 0.99 and is dictated by the MDP, not chosen by tuning.

×

'The reward is the label'

A reward is not a label. A label tells you the correct answer; a reward tells you only how good the action you took turned out to be — never what would have happened under a different action. This is why RL must explore (to learn about alternatives) and why it propagates information through value estimates rather than gradient signals from a ground truth. If your problem genuinely has labels, supervised learning is almost always cheaper and faster.

10 · Self-check

Can you answer these?

Six questions in the style the chapter likes to be tested. Click an option for instant feedback.

Which of the following is the defining feature of model-free reinforcement learning?

After one episode of TD(0) on a chain with a reward only at the terminal transition, how many state values have changed from their initial zeros?

In cliffwalking with ε = 0.10, why does SARSA tend to learn a longer, safer path while Q-learning learns the optimal cliff-edge path?

Which combination of conditions guarantees that ε-greedy SARSA converges to Q*?

What is the most important difference between supervised learning and reinforcement learning?

A return vₜ is observed under behaviour policy µ. To estimate the expected return under target policy π, which factor should you multiply vₜ by?

A 3-armed bandit has true means µ = (0.6, 0.2, 0.5). The arms were pulled T = (10, 4, 6) times. What is the pseudo-regret?

After 71 rounds, arm a₂ has been pulled 6 times with sample mean 0.50 — the lowest of the three arms. UCB1 plays it next. Why?

11 · Recap

One-screen summary

Chapter 10 — load-bearing ideas

Model-free RL learns from sampled experience. No access to $P$ or $R$ ; the agent infers optimal behaviour from $\langle s, a, r, s' \rangle$ tuples alone.
Monte Carlo: wait for an episode, average the returns. Unbiased, high variance, needs episode termination, doesn’t bootstrap.
TD(0): update online using $r + \gamma V(s')$ as a noisy target. Biased early, low variance, works on non-terminating tasks, bootstraps from a guess.
TD(λ): a dial between TD(0) ( $\lambda = 0$ ) and MC ( $\lambda = 1$ ). The λ-return averages all n-step returns with weights $(1-\lambda)\lambda^{n-1}$ ; sweet spot $\lambda \approx 0.7$ .
Forward = backward view. Eligibility traces $e_t(s) = \gamma\lambda\, e_{t-1}(s) + \mathbb{1}(s_t = s)$ propagate TD errors back through visited states, computing the λ-return update online.
For control, use $Q$ , not $V$ . Greedy improvement from $Q(s, a)$ is model-free; from $V(s)$ it would need the transition model.
Exploration is mandatory. ε-greedy with decaying ε is the simplest GLIE schedule. Without it, you may lock onto a suboptimal action forever.
Bandits are the one-state case, where exploration is the entire problem. Score by pseudo-regret $R_T = \sum_i \Delta_i T_i$ ; UCB1 plays $\arg\max_i \bar{x}_i + \sqrt{2\ln t / n_i}$ (deterministic optimism), Thompson draws $\theta_i \sim \text{Beta}(s_i+1, f_i+1)$ and plays the best draw (randomised). Both reach optimal $O(\log T)$ regret; fixed-ε is $\Theta(T)$ .
SARSA vs Q-learning, in one symbol. SARSA bootstraps from $Q(s', a')$ (on-policy, learns under exploration); Q-learning from $\max_{a'} Q(s', a')$ (off-policy, learns $Q^*$ ). Cliffwalking shows it: SARSA safe, Q-learning bold.
Convergence: GLIE policies + Robbins–Monro step sizes ( $\sum \alpha = \infty$ , $\sum \alpha^2 < \infty$ ) give convergence to $Q^*$ for both SARSA and Q-learning.
Backup taxonomy: DP (bootstrap, no sample), MC (sample, no bootstrap), TD (sample + bootstrap). Every algorithm here fits this 2×2 picture.
Off-policy = learn $\pi$ while behaving as $\mu$ . MC needs trajectory-wide importance ratios $\prod \pi/\mu$ ; TD needs only a one-step ratio. Q-learning dodges importance sampling entirely because its target is greedy.
Three time-scales in any working implementation: $1 - \gamma \gg \alpha \gg \varepsilon$ . Anneal $\varepsilon$ faster than $\alpha$ . Replacing traces are safer than accumulating ones.

radar

Exam radar — what to re-derive the night before

In descending order of evidence from the question bank: §8 Q1 (the four update rules — the densest cluster of marks in the chapter, and everything else is built on them), §8 Q3 (SARSA vs Q-learning — 6 questions worth 24 marks, spread over 5 sessions — with the cliffwalking justification), §6 bandits (7 of 12 sessions, and a standalone 4-point exercise in both 2026 papers — practise the regret sum and one full set of UCB1 indices by hand), and §8 Q4 (the two convergence ingredients). If time is short, the bandit exercise is the most mechanical marks in the chapter: it is arithmetic with a fixed three-part shape.