Q-Learning
The classic algorithm that learns the value of every action by trial and error — no model of the world needed — and from those values, reads off the optimal way to behave.
🎯 By the end you'll understand
What Q-learning actually does — learn an action-value Q(s,a) for every state-action pair, then act greedily — why it's model-free and off-policy, the exact update rule (and every symbol in it), and how value propagates back from the goal until the greedy policy becomes optimal. You'll do one update by hand and watch a gridworld converge.
KEY INSIGHTThe one idea to take away
If you knew, for every situation, how good each possible action was — you wouldn't need a teacher, a map, or a plan. You'd just pick the best one. Q-learning learns that table of "how good" from raw experience.
Back in Lesson 2.3 you met the action-value Q(s,a): the expected return from taking action a in state s and behaving well afterwards. Q-learning is the algorithm that fills in that table — one nudge at a time, from nothing but the rewards the agent stumbles into. Once the table is good, behaving optimally is trivial: in each state, pick the action with the largest Q.
Q-learning needs no model of the environment — no transition probabilities, no reward map handed to it in advance. It learns the optimal action-values Q* purely by trying things and applying one small correction after each step. That correction is the whole algorithm.
CORE CONCEPTWhat Q-learning is (and isn't)
Remember the cleaning robot from earlier in this stage — three rooms, and a value for each. We asked two questions about it. V(s) answered "how good is it to be in this room?" And Q(s,a) answered the more useful question: "how good is it to be in this room and move toward the kitchen?" The action-value tells you not just where you are, but what to do.
Q-learning's job is to learn Q(s,a) for every room-and-direction the robot could be in. It does this without ever being told how the rooms connect or where the dirt is — it discovers all of that by bumping around and watching the rewards. Two words capture what makes it special, and you'll meet both again in Lesson 2.7.
A reinforcement-learning algorithm that learns the optimal action-value function Q*(s,a) by repeatedly applying a small update after each experienced step, then derives optimal behaviour by acting greedily with respect to the learned Q.
The agent never builds or needs a model of the environment's dynamics (which state follows which, with what probability, for what reward). It learns directly from samples of experience — the actual transitions it lives through.
The agent learns about one policy (the optimal, always-greedy one) while it may be behaving according to a different, more exploratory policy. It can act curiously and still learn what the best behaviour would have been.
In a state s, the action with the highest learned value: argmaxa Q(s,a). Acting greedily for every state is the policy Q-learning is ultimately trying to discover.
Hold the contrast: Q-learning is happy to explore recklessly while it learns, because the max in its update always asks "what's the best I could have done from the next state?" — not "what did I actually do next?" That single design choice is what makes it off-policy. We'll put it head-to-head with the on-policy alternative, SARSA, next lesson.
FORMALThe Q-learning update
Everything Q-learning does lives in one line. After the agent, in state St, takes action At, receives reward Rt+1, and lands in St+1, it nudges its estimate:
It looks dense, but it's just "old estimate, plus a small step toward a better estimate." Let's name every piece:
Learning rate α
How big a step to take, between 0 and 1. Small α = cautious, slow, stable learning; large α = fast but jumpy. It's the size of the nudge.
Reward Rt+1
The actual reward the environment just handed back for that step — the only ground-truth signal in the whole equation.
Discount γ
How much future reward is worth now (Lesson 1.3). Multiplies whatever value comes after this step, so distant rewards count for a little less.
The best next value maxa Q(St+1,a)
The largest action-value available from the state we just arrived in — "the best I could do from here." This is the spotlighted term, and it's what makes Q-learning off-policy: it assumes optimal play from the next state on, regardless of what the agent actually does next.
The TD error (the bracket)
Rt+1 + γ maxa Q(St+1,a) − Q(St,At) is the temporal-difference error from Lesson 2.5: the gap between our old guess and a fresher, reward-informed one. If it's positive, this action was better than we thought — raise its value. If negative, lower it.
Read it in plain English: "My new estimate of how good that action was should move a fraction α of the way toward (the reward I just got) plus (the discounted value of the best thing I can do next)." The target in brackets — Rt+1 + γ maxa Q(St+1,a) — is exactly a one-step Bellman optimality backup (Lesson 2.4), but estimated from a single sampled transition instead of a known model. That's the bridge: Bellman tells us what the value should satisfy; TD lets us approach it from raw experience; Q-learning aims that backup at the optimal values by using max.
Swap that maxa Q(St+1,a) for "the value of the action I'm actually going to take next," and you no longer have Q-learning — you have SARSA, an on-policy method. One symbol is the entire difference. Hold that thought for 2.7.
EXAMPLEOne update, worked by hand
Numbers make it click. Suppose the robot is in state s, takes action right, gets reward Rt+1 = 0 (an ordinary step, no payoff yet), and lands in state s′. Use α = 0.5 and γ = 0.9.
Current estimates: Q(s, right) = 0 (we've never been here, so it starts at zero). From the new state s′, the action-values we've learned so far are:
| Action from s′ | up | down | left | right |
|---|---|---|---|---|
| Q(s′, ·) | 0 | 0 | 0 | 10 |
Step 1 — the best next value: maxa Q(s′,a) = max(0, 0, 0, 10) = 10.
Step 2 — the TD target: Rt+1 + γ maxa Q(s′,a) = 0 + 0.9 × 10 = 9.
Step 3 — the TD error: 9 − Q(s, right) = 9 − 0 = 9.
Step 4 — the update:
Notice what just happened. A reward of zero still raised this action's value from 0 to 4.5 — because moving right led to a state from which something great is reachable. The max term carried value backward, one step at a time, away from where the reward actually lives. Run this loop over many episodes and that value seeps further and further from the goal, lighting up a trail of good actions all the way back to the start. That backward seep is the soul of the algorithm — and it's exactly what you'll watch in the widget below.
FRAMEWORKThe algorithm, step by step
Zoomed out, Q-learning is a short loop you repeat over many episodes:
Initialise Q
One entry per state-action pair, typically all zeros. A blank table — the agent knows nothing.
Observe the state St
Where am I right now?
Choose an action — with exploration
Usually ε-greedy: mostly pick the greedy (highest-Q) action, but occasionally pick at random to keep discovering. Exploration is essential — more on it in Lesson 2.8.
Act; observe Rt+1 and St+1
Take the action, see the reward and where you land.
Apply the update
Nudge Q(St,At) toward Rt+1 + γ maxa Q(St+1,a).
Repeat
St+1 becomes the new current state. Loop until the episode ends; run many episodes. Over time, Q converges toward Q*.
The same loop as pseudocode:
initialize Q[s, a] = 0 # for all states s, actions a for episode in range(num_episodes): s = env.reset() while not done: a = epsilon_greedy(Q, s) # explore vs. exploit s_next, r, done = env.step(a) # take the action # the Q-learning update — the only line that learns best_next = max(Q[s_next, a2] for a2 in actions) td_target = r + gamma * best_next Q[s, a] += alpha * (td_target - Q[s, a]) s = s_next
That highlighted middle block is the entire learning rule from above, transcribed. Everything else is bookkeeping: walk around, see what happens, correct one number.
SEE ITQ-learning on a gridworld
Here's a 4×4 gridworld. The bottom-right is the goal (+10 reward); one cell is a trap (−10). Every other step earns 0. The agent starts top-left and can move up, down, left, or right. It begins with a blank Q-table — every cell white, no idea what's good.
Watch the order things happen: the cell next to the goal learns its value first, then the cell before that, then the one before that — a wave of value flowing backward, exactly like the hand-worked update. Meanwhile the trap stays dark and the arrows learn to route around it. By the end, following the arrows from the start traces the optimal path — no map was ever given. (This demo uses hand-authored, deterministic convergence so it lands the same way every time; real Q-learning gets here through noisy ε-greedy wandering.)
INTUITIONWhy the value flows backward
It can feel like magic that a goal reward "knows" how to spread across the whole grid. It isn't — it's just the max term, applied over and over.
The first time the agent stumbles into the goal, only the very last action — the step into the goal — gets its value raised, because that's the only step whose St+1 is the goal. Every earlier step that episode still saw max Q = 0 for its next state, so nothing changed. But now one cell glows. The next episode, any step landing in that glowing cell finds a non-zero max waiting, and inherits a discounted slice of it. Episode by episode, the glow climbs one cell further from the goal.
This is a sampled, repeated Bellman backup (Lesson 2.4): each state's value is being pulled toward "best reward I can get from here, then act optimally after." Do it enough times, with enough exploration to visit every cell, and the table settles at Q* — the fixed point where no update changes anything because every estimate already equals the discounted best-future-value. That settling-down has a name: convergence to Q*, and Q-learning is guaranteed to reach it under modest conditions (visit every state-action infinitely often, shrink α appropriately).
Q-learning doesn't plan and it doesn't memorise paths. It just keeps nudging one number toward "reward now plus the best I could do next" — and optimal behaviour falls out for free.
WEAKNESSWhere tabular Q-learning breaks
Be honest about the catch. Everything above assumed a table with one entry per state-action pair. For a 4×4 grid that's 16 × 4 = 64 numbers — trivial. But the table grows with the number of states, and states explode fast.
A chess position? Roughly 1040 states. A camera frame from a robot? Effectively infinite — every pixel combination is a different "state." You cannot store, let alone visit, a table that big. And if the state is continuous (a steering angle, a joint position), there's no discrete cell to index at all.
Replace the lookup table with a function approximator — usually a neural network — that predicts Q(s,a) from features of the state instead of storing it. That's Deep Q-Networks (DQN), and it's exactly where this lesson points: Lesson 3.2. The update rule you just learned survives almost unchanged — the network just learns to output the Q-values the table used to hold.
So: tabular Q-learning is the right tool for small, discrete problems, and the perfect place to understand the idea. For the big, messy, continuous world, you'll carry this exact update into deep RL.
WEAKNESSCommon mistakes to avoid
It's model-free — that's the headline. It never needs transition probabilities or a reward map. It learns purely from sampled transitions (St, At, Rt+1, St+1) it actually experiences. (Methods that do use a model are a different family — model-based RL.)
If you only ever take the current-best action, you'll never discover that some untried action was better, and Q will lock onto a bad estimate. You must explore (e.g. ε-greedy) to visit every state-action. The max lives only in the update target, not necessarily in how you behave — that's the off-policy split, and exactly why exploration is safe (Lesson 2.8).
No — it needs one stored value per state-action pair. That's fine for small, discrete problems and hopeless for huge or continuous ones. Scaling up means function approximation: deep Q-networks (Lesson 3.2).
KEY INSIGHTHow it connects in your course
- Action-values (2.3) — Q(s,a) is the thing Q-learning learns; this lesson is how that table actually gets filled.
- Bellman backups (2.4) — the TD target R + γ max Q is a sampled Bellman optimality backup; convergence to Q* is the Bellman fixed point.
- TD learning (2.5) — the bracket is the TD error; Q-learning is TD control with a max in the target.
- SARSA & on-/off-policy (2.7) — swap the max for the value of the action actually taken and you get on-policy SARSA. The full comparison is next.
- Exploration: ε-greedy (2.8) — how the agent visits enough state-actions for Q-learning to converge.
- Deep Q-Networks (3.2) — replace the table with a neural net so the same update scales to huge/continuous problems.
The one sentence to keep: learn Q by nudging it toward "reward now plus the best I could do next," then act greedily. Everything from here is making that scale.
GLOSSARYKey terms introduced
- Q-learning
- A model-free, off-policy algorithm that learns the optimal action-value function by applying a TD update with a max target after each step.
- Action-value (Q(s,a))
- The expected return from taking action a in state s, then behaving optimally thereafter.
- Model-free
- Learning from sampled experience alone, without any model of the environment's transitions or rewards.
- Off-policy
- Learning about the optimal (greedy) policy while behaving according to a different, more exploratory one.
- Greedy action
- The highest-value action in a state, argmaxa Q(s,a); acting greedily everywhere is the target policy.
- Max operator (maxa Q(St+1,a))
- The best action-value from the next state; using it in the update is what makes Q-learning off-policy and aims it at Q*.
- Convergence to Q*
- The guarantee that, with enough exploration and a suitable learning rate, the learned Q settles at the optimal action-values.
ACTIVE RECALLCheck your understanding
Answer in your own words first, then reveal.
1What does the maxa Q(St+1,a) term do, and why does it make Q-learning off-policy?›
It's the best action-value available from the next state — "the most I could get from here if I play optimally." Because the update assumes optimal continuation regardless of what the agent actually does next, Q-learning learns the optimal policy's values even while behaving exploratively. That gap between learned policy and behaviour policy is exactly what "off-policy" means.
2Do the update by hand: Q(s,a)=2, reward =1, best next value =10, α=0.1, γ=0.9. What's the new Q(s,a)?›
Target = 1 + 0.9 × 10 = 10. TD error = 10 − 2 = 8. New value = 2 + 0.1 × 8 = 2.8.
3Why does value appear to "flow backward" from the goal across episodes?›
The first success only raises the value of the step into the goal (the only step whose next state is the goal). Once that cell is non-zero, any step landing in it finds a non-zero max and inherits a discounted slice. Each episode the glow climbs one cell further back — a repeated Bellman backup propagating value outward from the reward.
4Why does tabular Q-learning fail on chess or a robot's camera input, and what's the fix?›
It stores one value per state-action pair, but those problems have astronomically many (or infinitely many, or continuous) states — no table can hold or visit them all. The fix is function approximation: a neural network that predicts Q(s,a) from state features instead of storing it — a Deep Q-Network (Lesson 3.2).