MC propagates the full sampled return along the episode. TD(0) updates one transition at a time using its estimate of the next state.
, deterministic moves, rewards only on exit
RecapBackup diagrams: what each target looks at
Dynamic Programming
Model-based expectation over all actions and successor states.
Monte Carlo
One observed trajectory through episode termination.
TD(0)
One observed transition, then bootstrap from a stored value.
● Actions selected by ● Rewards received● Values and model transitions
RecapA unified view of prediction algorithms
Vary backup depth continuously (how many steps before bootstrapping) and backup width (how many successor branches are considered).
Sampling ↔ expectationFrom one observed successor to the full model-based average.
Bootstrap ↔ full returnFrom one-step TD to longer n-step returns and Monte Carlo.
The axes are continua, not four unrelated algorithms. Adapted from Sutton & Barto (2018), Fig. 6.3.
Recap · same mazeTD(0): update after each step
Follow the same 6-transition episode from Lecture 3. Start with , learning rate , discount .
Temporal-difference update
LIVE UPDATE
Click “Step” to substitute the observed numbers into the TD update above.
Episode 1 · transition 0 / 6
What should you observe?After the first episode, only V(s₁₀) has changed: 2.50. Information moves backwards through later episodes.
Part 2
From prediction to control
Generalised policy iteration, action values, and exploration.
Prediction vs. control
Predict the future given a policy . (estimate the value function)
Prediction · from last weekInput: a fixed policy Output: state values Question: how good is this policy?
Evaluation: estimate expected returns from sampled trajectories.
Optimize the future by finding the best policy . (optimize the value function)
Control · what we want nextInput: experience (s,a,r,s′) Output: an improved policy Question: can we improve actions using ?
Evaluation and improvement alternate, often every time step.
The natural idea: GPI with
Start with an arbitrary policy and state-value estimate. Alternate MC/TD prediction with greedy policy improvement.
GENERALIZED POLICY ITERATION
↗MC / TD prediction of
↘Greedy policy improvement
Repeated evaluation and improvement moves us toward and .
The catch: greedy improvement over V
With a known model, we can improve a policy using :
To choose an action, we need the one-step dynamics and — precisely what we do not know!
How can we avoid needing a model?
What if our value estimate already included the first action?
Remember Lecture 3?Action values
The first action is already included in . So we can replace the model-dependent improvement step by .
From last lectureAction values for a fixed policy:
TD can estimate them from samples.
The model-free shortcutImprove by choosing the action with the highest learned — without knowing or .
Same GPI arrows as before, now predicting Q rather than V.
Generalised policy iteration
Policy evaluation: estimate from sampled transitions.
Policy improvement: adjust using the new action values.
Unlike full DP, both happen incrementally, without knowing or .
Key ideaA control algorithm is essentially prediction + an improving policy.
Greedy policy improvement: revisit the maze
In the same two-exit maze, we start with a fixed policy and its already evaluated values. Click a cell to improve only its action; evaluation is a separate step.
TWO-EXIT MAZE · EVALUATED POLICY
The displayed values come from the last policy evaluation. = 0.9.
1 · SELECT A STATE
s₂Current π: ↑
STEP 0 · V and Q have already been evaluated for the initial policy.
Choose a state to compare its evaluated Q-values.
Now the key questionWhat if a better action was never tried?
The exploration trap: lucky first samples
Two actions have unknown Gaussian rewards. Try each once, then keep choosing the action with the higher sample average.
ONE STATE · TWO ACTIONS
Start with one sample of each action.
REWARD SAMPLES FROM NORMAL DISTRIBUTIONS
B has the larger true mean, but unlucky first samples can hide it. Grey marks = sampled rewards.
EXPLORATION IN REAL LIFE :)
Sometimes you only discover a better move by trying something new.
Epsilon-greedy exploration
With probability , choose a greedy action. With probability , choose uniformly at random.
In this example, ↑ up is the greedy action (it currently has the highest estimated Q-value).
For a unique maximiser ; with ties, split the greedy mass across maximisers.
0.20
Action frequency · observed samples
Select ε, then sample from the policy.
The histogram counts actions actually chosen; it approaches the ε-greedy probabilities with more samples.
GLIE: ε decreases, but exploration continues
Same four actions as on the previous slide. Greedy action: up. Set the exploration-rate scale ε₀. Then εₜ = min(1, ε₀ / √t) gradually decreases.
Greedy in the limit with infinite exploration
1. Each action is sampled infinitely often: .
2. Exploration probability tends to zero: .
For every ε₀ > 0, the scale ε₀/√t tends to zero but the sum of the exploration probabilities diverges (for this single-state example).
1.0
t = 0 · run samples to observe ε decreasing.
Observed action frequenciesExploration rate over time
Monte Carlo control: improve after full episodes
Try full episodes in the Maze environment. Each episode updates sampled returns G for state–action pairs and improves the ε-greedy policy.
MAZE ENVIRONMENT · 4 × 4
Click a numbered cell to inspect learned Q-values. Orange path: the last sampled episode. Arrows: the current greedy direction.
2.0
MC CONTROL LAB
s₂0 episodes
Start episodes: first-visit MC estimates Q from sampled returns.
GPI cycle: 0 complete Monte Carlo evaluations → 0 ε-greedy improvements
Every episode begins at s₁; εₖ = min(1, ε₀ / √k), = 0.9. Model-free tabular first-visit MC control.
GPI now uses ε-greedy policy improvement
Purely greedy control can miss better actions. ε-greedy improvement keeps exploring while we learn a better policy.
What changes? Evaluation still estimates from MC/TD experience. The improved continues to explore.
From our maze lab0 completed episodes Every full episode supplies returns, then Q and the ε-greedy policy are updated.
We do not have to finish policy evaluation
Every episode: MC can improve after one sampled return. Every step: TD control can improve even faster.
Generalised policy iteration Each short green arrow is just a partial evaluation; then orange improves the policy. We alternate before reaching exactly.
Spoiler: SARSA TD prediction of Q + ε-greedy policy improvement after every time step.
EVERY EPISODE → EVERY STEP
Part 3
SARSA
On-policy temporal-difference control: learn from the action you actually take.
From TD prediction to TD control
Last lecture: one-step TD for action values, under a fixed policy:
Only two changes1. Select actions with an ε-greedy policy derived from the current Q. 2. Update Q and therefore the policy continuously.
Observe → Update Q → Act ε-greedily
No model and no full-episode return needed.
SARSA: the update
TD target
Current pairState Action
ObservedReward
Next pairState Action
S-A-R-S-A = state, action, reward, next state, next sampled action.
Let us calculate one SARSA update in the maze
In the same Maze environment, each state contains four action values. Click a state or directional triangle, observe the transition, then update one Q-value.
4×4 MAZE · 4 ACTION VALUES IN EACH CELL
The highlighted triangle is the selected action.
INTERACTIVE SARSA BACKUP
s₂, →α = 0.5, γ = 0.9
Observe the result of the selected action.
Previous Q(s,a)0.00
Observed reward R0
Sampled action 0.00
TD target0.00
Updated Q(s,a)0.00
Choose a state and an action to see the update.
SARSA in six lines
On-policy TD control
Initialize Q(s,a) arbitrarily; choose α, γ, ε For each episode: Initialize S; choose A ∼ ε-greedy(Q(S,·)) Repeat: Take A, observe R and S' If S' is not terminal, choose A' ∼ ε-greedy(Q(S',·)) Q(S,A) ← Q(S,A) + α [R + γQ(S',A') − Q(S,A)] S ← S', A ← A' Until S is terminal
Interpret Q(terminal,·) = 0.
Spot the crucial lineWhy do we have to choose A' before updating Q?
Windy Gridworld: learn with SARSA
7 × 10 grid · Start S → Goal G · updrafts in columns 4–9reward = −1 / step · γ = 1
↑ blue: wind strengthblack arrows: current greedy policyorange: actual trajectory of the last completed episode
0 episodes · not trained
Every counted episode ends at G. The orange lines show the actual experienced trajectory, not the current greedy policy. How does SARSA compensate for the wind without knowing its dynamics?
Why SARSA is on-policy
The target contains the value of the action actually chosen by the same policy:
With > 0, can be exploratory, even when there is a better greedy action.
InterpretationSARSA learns the action values of its current exploratory behaviour. It accounts for future mistakes caused by exploration.
SARSA: strengths and trade-offs
Strengths
Processes each transition immediately
Cheap tabular update
Directly incorporates the risks of its current policy
Limitations
Action samples must come from the current behaviour policy
Needs sustained exploration and many samples
Sensitive to learning-rate and exploration schedules
Can be unstable with naive function approximation
Part 4
Q-Learning
Off-policy TD control: learn about the greedy policy while exploring.
Q-Learning: change one term
SARSA
Q-Learning
The complete update
The next action may be exploratory, but the target assumes the best action is selected next.
Q-Learning: update the same maze, a different target
In the same Maze environment, each state contains four action values. Click a state or directional triangle, observe the transition, then update one Q-value.
4×4 MAZE · 4 ACTION VALUES IN EACH CELL
The highlighted triangle is the selected action.
INTERACTIVE Q-LEARNING BACKUP
s₂, →α = 0.5, γ = 0.9
Observe the result of the selected action.
Previous Q(s,a)0.00
Observed reward R0
Greedy continuation 0.00
TD target0.00
Updated Q(s,a)0.00
Choose a state and an action to see the update.
Q-Learning in six lines
Off-policy TD control
Initialize Q(s,a) arbitrarily; choose α, γ, ε For each episode: Initialize S Repeat: Choose A ∼ ε-greedy(Q(S,·)) Take A, observe R and S' Q(S,A) ← Q(S,A) + α [R + γ maxa' Q(S',a') − Q(S,A)] S ← S' Until S is terminal
Define maxa' Q(terminal,a') = 0.
Which line is no longer needed compared with SARSA?
We do not need to sample A' before the update.
One slide: SARSA vs. Q-Learning
SARSA
Q-Learning
TD bootstrap
Learning type
On-policy
Off-policy
Evaluates
Actual exploratory policy
Greedy target policy
Can use old exploratory samples?
Not in the same straightforward form
Yes, under suitable coverage
With persistent exploration
Accounts for risk of exploratory actions
Plans as though next action were greedy
Both are model-free, use one-step TD, and update Q(s,a) after every transition.
Part 5
Cliff Walking
A small world where an exploratory mistake can be expensive.
Cliff Walking: the setup
Start SGoal GCliff: -100
Moves up, down, left, right.
Each normal step yields -1.
Walking into the cliff yields −100 and resets to S (the episode continues).
Only reaching G terminates an episode.
Undiscounted episodic task: = 1.
Compare both algorithms with = 0.1.
PredictWhich learned route stays farther away from the cliff when exploration continues?
Textbook convention, Sutton & Barto (2018), Example 6.6: the cliff resets to S without terminating the episode.
Cliff Walking: train both agents
Both agents: tabular, α = 0.5, γ = 1Each train click runs actual TD updates in your browser
0.10
SARSA · ON-POLICY
0 episodes
Q-LEARNING · OFF-POLICY
0 episodes
Episode return · 30-episode moving average (higher is better)
Why the two algorithms can behave differently
SARSA
Its TD target uses the next action actually chosen by the -greedy policy.
It learns that walking next to the cliff makes future exploration risky.
Often prefers a safer route while exploration persists.
Q-Learning
Its TD target assumes the next action is .
It learns the shortest greedy route, which can pass near the cliff.
But its exploratory behaviour can still slip into the cliff.
Thought experiment: what if ε = 0?
Exercise 6.12 · Sutton & BartoSuppose both algorithms always select greedily. Are SARSA and Q-Learning now exactly the same? Will their updates and trajectories be identical?
AnswerIf both start with the same Q, see the same transitions, and break greedy ties the same way, then and their updates coincide.
Different tie-breaking, random seeds or sampled trajectories can still lead to different runs.
Part 6
Extensions & takeaways
Convergence, reusing experience, and Double Q-Learning.
When do we converge?
For finite tabular MDPs, convergence results rely on conditions — not just the update formula.
Both methods
Every relevant pair is visited sufficiently often.
Learning rates decrease appropriately: .
Policy conditions
SARSA: a GLIE-style policy that becomes greedy in the limit.
Q-Learning: off-policy sampling must still cover all relevant pairs sufficiently.
A constant and constant can be useful in demonstrations and nonstationary settings, but do not satisfy these exact tabular convergence conditions.
Off-policy learning reuses experience
YesterdayRandom exploratory agent
TodayUpdated target policy
TomorrowMore transitions
All these transitions can inform Q-Learning, if the state-action coverage is appropriate.
Behaviour policy: where did this transition come from?
Target policy: which future value is in the bootstrap target?
With Q-Learning, these do not have to match.
This motivates experience replay and later deep RL variants.
The Double Q-Learning idea
The problem: taking the maximum of noisy Q estimates can systematically overestimate action values.
Maintain two action-value tables, and :
Randomly update one tableChoose the best next action with one table, but evaluate it using the other.
Use one of the two updates on each transition, with terminal bootstrap set to zero. The behaviour policy can be ε-greedy w.r.t. Q1 + Q2.
Double Q-Learning: maximisation bias, then correction
Sutton & Barto, Fig. 6.5 (simplified to five actions at B): in state A, RIGHT terminates at reward 0; LEFT leads to B, where noisy terminal rewards have mean −0.1.
RUN 1 · CURRENTLY LEARNED Q(B,a) FOR 5 ACTIONS · TRUE MEAN −0.1 (DASHED)
Q-learning: Q(A,left)0.000
Double: Q(A,left)0.000
True value of LEFT−0.100
True value of RIGHT0.000
Click +1 ep to see one sampled transition and Bellman update. Both algorithms start from Q = 0.
PERCENTAGE OF LEFT ACTIONS FROM A · AVERAGE ACROSS INDEPENDENT TRAINING RUNS
When the Q table is too large
For tabular control we store
numbers. This becomes impossible in many real environments.
Replace the table with a parameterized estimate and update it using sampled TD errors.
MDPknown model
MC / TDprediction
SARSA / Q-Learningcontrol
Function approximationlarge state spaces
DQNdeep features
What distinguishes the methods?
Monte Carlo
SARSA
Q-Learning
When update?
After episode
After each step
After each step
Target
Bootstrapping?
No
Yes
Yes
Policy relationship
On-policy MC control variant
On-policy
Off-policy
Main complication
High return variance
Exploratory target
Max bias, off-policy instability
In every case, exploration determines which state-action pairs the agent can learn about.
Three questions to check understanding
1. Why is not a useful model-free policy improvement rule?
Because does not depend on action a. Without a model we need to compare actions.
2. What happens in a SARSA update when the next action was exploratory?
SARSA bootstraps from that exploratory next action's Q-value, not the maximum.
3. Can Q-Learning behave non-greedily while learning a greedy target?
Yes. It can collect data using ε-greedy behaviour and still bootstrap from .
Takeaways
01
Prediction → control
Learn action values and improve the policy while collecting data.
02
Exploration matters
ε-greedy prevents a learner from trusting its early guesses forever.
03
SARSA is on-policy
It bootstraps from the next action actually taken.
04
Q-Learning is off-policy
It bootstraps from the best next action, even while exploring.
MAIN REFERENCES
Sutton & Barto (2018), Reinforcement Learning: An Introduction, Chapters 5–6. David Silver, UCL RL course, Lecture 5: Model-Free Control.