Learning to act with no model of the world — only trial-and-error samples. From the temporal-difference idea, to the off-policy max that makes Q-learning special, to the two tricks (replay + target network) that let a neural network do it from raw pixels.
In Lecture 7 you learned to solve a Markov Decision Process when you know everything: the reward function r(s,a) and the transition probabilities P(s′|s,a). Value iteration sweeps the whole table, the Bellman backup contracts to the optimal values, and you read off the policy. Clean. Powerful. And, for a real robot, unavailable.
Drop a robot into an unfamiliar building. It does not know the floor plan. It does not know that turning left near the kitchen leads to a staircase. It does not know what reward it will get until it actually tries something and sees what happens. There is no P, no r written down anywhere. There is only the loop: take an action, land somewhere, collect a number, repeat.
This is called model-free learning: we never build a model of P or r. Instead we directly learn a value — a number attached to each situation telling us how good it is — from raw experience. Specifically we learn the action-value Q(s,a): "if I am in state s and take action a, then act well afterward, how much total reward should I expect?"
Why Q and not just the state-value V(s)? Because Q already names the action. If you have Q(s,a) for every action, choosing what to do is trivial — take the action with the biggest Q. With V alone you would need the model to look one step ahead and ask "which action lands me in the best next state?" — and the model is exactly what we don't have. Q is the model-free-friendly value.
Press Run. A robot wanders a 5×5 gridworld it has never seen. It does not know where the goal (teal) or the pit (red) are. Each cell's color shows its current estimated value — grey = unknown, warming up as the robot learns. The arrows are the greedy policy that emerges from the values, with no model at all.
Notice what is happening: the robot is not told the answer. It bumps into the pit, gets a big negative number, and the value of the cell it came from drops. It stumbles into the goal, gets a reward, and the value flows backward toward it over many episodes. The map of values builds itself out of nothing but rewards and the structure of the loop.
We want to estimate a value — say the value of a state under our current policy, V(s) = the expected return starting from s. We have no model. We only have episodes: sequences of state, action, reward, state, action, reward, … that we collected by acting. How do we squeeze a value out of those?
Monte Carlo (MC) takes the honest, patient route. Run an episode all the way to the end. Add up the actual discounted rewards you actually received from state s onward — that is one sample of the return, call it G. Then nudge your estimate of V(s) a little toward that observed return:
Here α (alpha) is the learning rate or step size — a small number that says "move this fraction of the way toward the new evidence." The bracket (G − V(s)) is the error: how far off our current guess was from the return we actually saw. Average enough returns and V(s) converges to the true expected return.
MC is unbiased — it uses the real return, no assumptions. But it has two problems. First, you must wait until the episode ends to get G; you cannot learn during a long episode, and you cannot learn at all in a task that never terminates. Second, G has high variance: it depends on every random thing that happened for the whole rest of the episode, so a single return can be wildly lucky or unlucky.
Temporal-difference (TD) learning refuses to wait. After just one step — you took action a in s, got reward r, landed in s′ — it asks: what is a good estimate of the return from s? Well, the return is "the reward I just got, plus the discounted value of where I ended up." We don't know the true value of s′, but we have a current estimate V(s′). So use it:
This quantity — one real reward plus our discounted guess about the rest — is the TD target. We then nudge V(s) toward it exactly as before. Because the target itself contains an estimate V(s′), TD is bootstrapping: it updates a guess using another guess.
A robot walks a 6-state chain; only the last step pays +1, every step is noisy. The warm bars are Monte-Carlo estimates (updated only at episode end, from the full return); the teal bars are TD(0) estimates (updated every step from r + γV(s′)). The dashed line is the true value. Press Run and watch TD's smooth, low-variance crawl vs MC's jumpier convergence.
Let us build the update from the ground up, because every Q-learning variant is a tweak of these four symbols. We start where Lecture 7 left off: the Bellman equation for the value of a policy. It says the value of a state equals the immediate reward plus the discounted value of the next state, averaged over what the world does:
The expectation E[·] is the troublemaker. To evaluate it exactly you would average over all next states s′ weighted by P(s′|s,a) — and we don't have P. But here is the saving grace: a single sampled transition is an unbiased sample of that expectation. When the robot actually takes the step and observes (s, r, s′), the quantity r + γV(s′) is one draw whose average is exactly the right-hand side.
If our estimate V were perfect, then V(s) would equal r + γV(s′) on average, so the gap between them would be zero on average. That gap is the TD error, written δ (delta):
Read it aloud: "what I now think the value is" (the TD target r + γV(s′)) "minus what I used to think" (the old V(s)). A positive δ means this state turned out better than expected; a negative δ means worse. δ is the surprise.
We don't want to overreact to one noisy sample, so we move only a fraction α of the way along the error:
Expanding δ, this is V(s) ← V(s) + α(r + γV(s′) − V(s)). The learning rate α in [0,1] is a trust dial: α = 0 ignores all new evidence (never learns); α = 1 throws away the old estimate and believes this one sample completely (jittery); a small α like 0.1 blends slowly and smoothly. This is the famous TD(0) update for state values.
For control we want the action-value Q(s,a), because (Chapter 0) Q lets us pick actions without a model. The same logic gives the TD update on Q. We need a value for the next state too — and the next-state value is some Q(s′, a′) for some next action a′. Which a′ we plug in is the entire question of the next chapter. The skeleton is:
A single state has a true value of 10 (dashed line). Each step we feed a noisy sample of the target and apply the TD update. Slide α: tiny α crawls smoothly but slowly; α near 1 snaps to each noisy sample and jitters forever. This is the bias–variance dial of every TD method.
We left one slot blank: in the TD target r + γQ(s′, a′), which next action a′ do we evaluate? There are two natural answers, and they define the two most famous control algorithms in all of RL. They differ by one symbol and that one symbol changes everything.
SARSA is named after the five things it uses: State, Action, Reward, next State, next Action — (s, a, r, s′, a′). It plugs in the action a′ that the agent actually takes next, drawn from its own behavior policy (with all that policy's exploration randomness):
Because the target uses the action the current policy chose, SARSA learns the value of the policy it is actually following, exploration warts and all. This makes it an on-policy method: learn about the policy you use to act.
Q-learning ignores what the agent did next. In the target it inserts the maximum Q over all next actions — the value of acting greedily from s′:
That little maxa′ is the most important symbol in the lecture. The agent might be exploring — wandering randomly, taking bad actions to learn — but the target always assumes it will behave optimally from the next state onward. So Q-learning learns the value of the optimal greedy policy while following a different, exploratory behavior policy. That gap between "the policy I learn about" and "the policy I act with" is what makes it off-policy.
Recall the FQI slide from lecture: given (s, a), the Q-learning update is independent of the policy π that collected the data — π only influences which transitions we see. The max throws away any dependence on how the action a′ would have been chosen. Concretely this buys three things robotics cares about deeply:
| SARSA | Q-Learning | |
|---|---|---|
| TD target next-action | a′ actually taken | argmax over a′ (the max) |
| Learns the value of… | the policy it follows (with exploration) | the optimal greedy policy |
| Class | On-policy | Off-policy |
| From the Bellman… | evaluation equation | optimality equation |
| Can reuse old / others' data? | No (target depends on current policy) | Yes (target independent of π) |
| Behavior near danger | cautious (accounts for own slips) | aggressive (assumes perfect future) |
We will see that last row come alive in Chapter 6 on the cliff. For now hold the picture: SARSA values what it will really do; Q-learning values what it could ideally do.
Formulas hide until you push real numbers through them. Let us do exactly one Q-learning update with our pencil, then one SARSA update on the same transition, so the single-symbol difference becomes a single-number difference.
Suppose γ = 0.9 and α = 0.5. The robot is in state s, takes action a, gets reward r = 1, and lands in s′. From s′ there are two available actions with current estimates:
Our current estimate for the state-action we are updating is Q(s,a) = 4. Because the robot is exploring, the action it actually takes next happens to be up (the worse one) — an exploratory choice.
The target uses the best next action, ignoring what the robot did:
Same transition, same reward — but SARSA plugs in Q(s′, up) = 5, because up is what the robot really did next:
Now let's implement the bare tabular Q-learning update and let it solve a tiny gridworld from scratch — no model, only transitions. You will write the one line that is Q-learning: the TD update with the max.
Q-learning's convergence has a hidden condition that the math quietly assumes: every state-action pair must be tried infinitely often. You cannot learn the value of an action you never take. But the whole point of learning Q is to exploit — take the action with the highest Q to earn reward. These pull in opposite directions. This is the exploration vs exploitation dilemma, and it is the oldest problem in RL.
The simplest workable answer is ε-greedy (epsilon-greedy). With probability 1 − ε take the greedy action (exploit the best you know); with probability ε take a uniformly random action (explore something new):
Why does this matter for off-policy Q-learning specifically? Because Q-learning's target uses the max regardless of what we do, we are free to explore as recklessly as we like without biasing the learned values — exploration only changes which transitions we sample (the coverage), never what they teach. So ε-greedy is a clean fit: it guarantees coverage, and the off-policy max guarantees the values stay correct.
How greedy is ε-greedy, really? With n actions, the greedy action is taken with probability (1 − ε) + ε/n — the explicit exploit term plus the chance the random draw happens to land on it. Each non-greedy action is taken with probability ε/n. Let's watch the trade-off as a slider.
A 5-armed bandit: one arm pays much more, but the agent must find it. Slide ε. Left (ε→0): pure exploitation — it locks onto whatever looked best first and may never discover the real winner. Right (ε→1): pure exploration — it finds the winner but keeps throwing reward away on random arms. The sweet spot is a small positive ε that decays.
Let's nail the probabilities down in code — both the per-action selection probabilities and the empirical greedy fraction over many draws.
Chapter 3 promised that SARSA and Q-learning behave differently, not just compute differently. The classic demonstration is Sutton & Barto's cliff-walking gridworld, and it is worth understanding deeply because it exposes what "on-policy" really means.
The world: a grid. Start bottom-left, goal bottom-right. Along the bottom edge between them runs a cliff: stepping into it gives a huge −100 reward and snaps you back to the start. Every ordinary step costs −1. The robot still uses ε-greedy exploration the whole time, so it always has a chance of a random misstep.
Both algorithms learn the same Q* in the limit. But the paths they walk while learning differ sharply:
Both agents are trained on the same cliff with the same ε. After training, the warm path is the policy Q-learning learned (the risky optimal edge); the teal path is SARSA's (the safe detour one row up). The red strip is the cliff. Press Train, then watch how often each falls when you act ε-greedily.
The deeper lesson: the max in Q-learning is optimistic. It assumes flawless future execution. That optimism is exactly right when you want the truly optimal policy and exploration will eventually vanish. It is dangerous when you must act under the very exploration you are using to learn. SARSA's on-policy honesty is a feature, not a bug, in safety-critical settings.
So far Q has been a table: one cell per (state, action). For our 5-cell corridor that is 10 numbers. For Atari it is hopeless. The state is the screen: roughly 210×160 pixels, and the lecture uses 4 stacked frames to capture motion. The number of distinct screens is astronomically larger than the number of atoms in the universe. You will never visit the same pixel-state twice, so a table learns nothing — this is Bellman's curse of dimensionality.
Replace the table with a parametric function Qφ(s,a), where φ (phi) is a vector of weights — for Atari, a convolutional neural network. The good news from the lecture: the optimal Q has structure, smooth patterns over states, and "that is exactly what deep learning is good at." Input a screen, output one Q-value per action. We fit φ by regression, minimizing the squared TD error:
This is fitted Q-iteration: collect transitions, form the regression targets y = r + γmax Q, fit Qφ to them, repeat. Done in one batch it is offline FQI; done one sample at a time with a gradient step it is online Q-learning:
Look carefully at the target y = r + γmaxa′Qφ(s′,a′). It also depends on φ — the same weights we are updating! A true gradient would differentiate through y as well. Q-learning does not; it freezes y and only differentiates Qφ(s,a). The lecture calls this a semi-gradient method. You are chasing a target that moves every time you take a step toward it.
Concretely the failure mode is a feedback loop: you raise Qφ(s,a) toward its target; generalization also raises Qφ(s′,·); but that raises the target y for (s,a); so you raise Qφ(s,a) again; and the estimates spiral upward without bound. Add correlated, non-stationary data (consecutive frames are nearly identical, and the data distribution shifts as the policy improves) and the regression has none of the i.i.d. comfort supervised learning relies on.
A single Q-value (warm dot) chases its bootstrap target (teal). With moving target on, every step we move toward the target also drags the target up (generalization) — watch them race off to infinity. Toggle fixed target (DQN's idea): freeze the target for a while and the estimate settles onto it cleanly.
In 2013 (workshop) and 2015 (Nature), DeepMind's Deep Q-Network (DQN) trained a single network to play Atari from raw pixels and the score alone — no game-specific features, the same architecture across games. The lecture's framing is the cleanest: every algorithmic idea in DQN aims to make Q-learning "closer" to standard supervised learning with an SGD update. Two ideas do most of the work, and each attacks one leg of the deadly triad.
Instead of training on the stream of consecutive, highly correlated transitions, store every transition in a large replay buffer and train on random minibatches sampled from it. This does two things. It breaks the temporal correlation — a random minibatch looks much more like the i.i.d. data SGD expects. And it reuses each transition many times, which is precious when robot data is expensive. This is only legal because Q-learning is off-policy: a transition collected long ago by a stale policy is still a valid sample of r + γmax Q, since the target ignores how the action was chosen (Chapter 3).
The remaining problem is the moving target from Chapter 7: y depends on φ. DQN keeps a second copy of the network, the target network with parameters φ−, identical architecture but lagging weights. All targets are computed with φ−:
For C steps φ− is frozen, so the target is a fixed regression target — exactly the stability that offline FQI enjoyed. Every C steps we copy φ− ← φ (or blend it slowly). Now the SGD step really is fitting a static target, and the feedback loop that diverged in Chapter 7's widget is broken — just as the "fixed target" toggle showed.
The max in the target has a subtle flaw. Note r + γmaxa′Qφ−(s′,a′) = r + γQφ−(s′, argmaxa′Qφ−(s′,a′)). The same noisy network both picks the best action (argmax) and evaluates it. The argmax systematically selects whichever action got a lucky positive noise bump, so the max is biased upward — a "guess of a guess" that overestimates. Double DQN (DDQN) fixes it in three lines: use the live network φ to pick the action, the target network φ− to evaluate it:
Decoupling selection from evaluation removes most of the optimistic bias. Two more lecture extensions round it out: prioritized experience replay samples high-TD-error transitions more often (replay the surprising data), and the dueling architecture splits the network into a state-value V(s) and per-action advantages A(s,a) = Q(s,a) − V(s), so the agent learns "this state is good" without needing to nail every action.
The strip is a replay buffer of stored transitions, colored by recency. Stream mode trains on the latest few in order (highly correlated — the red bracket). Replay mode samples a random minibatch from the whole buffer (the scattered teal picks — decorrelated, and old data reused). Toggle and press Step.
You arrived with value iteration and a known model. You leave able to learn the optimal action-values of an unknown world from raw experience, and to scale that to a neural network on pixels. Here is the whole lecture on one page.
| Method | Target | Class | Needs model? |
|---|---|---|---|
| Value iteration (L7) | r + γ∑s′P(s′|s,a)max Q | planning | Yes |
| Monte Carlo | full return G | model-free | No |
| TD(0) (state value) | r + γV(s′) | model-free | No |
| SARSA | r + γQ(s′,a′) | on-policy | No |
| Q-learning | r + γmaxa′Q(s′,a′) | off-policy | No |
| FQI / DQN | r + γmaxa′Qφ−(s′,a′) | off-policy + neural net | No |
| Double DQN | r + γQφ−(s′, argmaxa′Qφ) | off-policy, debiased max | No |
"The best way to learn about algorithms is to implement them." — from the lecture's own closing slide. You just did, three times.