Q-Learning, Step by Step
10 min read · updated August 4, 2026
Q-learning estimates, for every state and action, the return you can expect if you take that action and then behave optimally. The whole algorithm is one line of arithmetic applied repeatedly, and the fastest way to understand it is to apply it by hand until the numbers move.
The update rule, and what each term is for
Q(s, a) <- Q(s, a) + alpha * [ r + gamma * max_a' Q(s', a') - Q(s, a) ]
\_______________ ______________/
\/
the TD targetThe bracket is the temporal-difference error: what we now think this state-action is worth, minus what we thought before. The target is the reward we actually received plus the discounted value of the best thing available from the state we landed in. alpha decides what fraction of the disagreement to absorb.
ris real information — it happened.max_a’ Q(s’, a’)is a guess, and at the start it is a guess of zero everywhere. The algorithm bootstraps: it updates one estimate towards another estimate. That is why early learning looks like nothing happening.alphaat 1.0 replaces the old value entirely, which is correct only if the environment is deterministic. At 0.1 it averages over many visits, which is what you want when transitions are random.
The problem: a four-square corridor
Four squares in a line, then the goal. From any square the agent can move left or right. Moving right from S3 reaches the goal and ends the episode with a reward of 1; every other move gives 0. Moving left from S0 bumps into the wall and stays put.
[S0] -- [S1] -- [S2] -- [S3] -- (G, +1)
alpha = 0.5 gamma = 0.9 all Q values start at 0
the table has eight cells:
L R
S0 0.000 0.000
S1 0.000 0.000
S2 0.000 0.000
S3 0.000 0.000The optimal policy is obvious to you and invisible to the agent. Watch how long it takes for the value of the goal to reach S0.
Five episodes, by hand
Assume the agent moves right at every step in each episode — either because exploration chose it or because it was already the greedy action. Every update is written out.
Episode 1
S0,R -> S1, r=0 : Q = 0 + 0.5*[0 + 0.9*max(0,0) - 0] = 0.000
S1,R -> S2, r=0 : Q = 0 + 0.5*[0 + 0.9*max(0,0) - 0] = 0.000
S2,R -> S3, r=0 : Q = 0 + 0.5*[0 + 0.9*max(0,0) - 0] = 0.000
S3,R -> G, r=1 : Q = 0 + 0.5*[1 + 0 (terminal) - 0] = 0.500
L R
S0 0.000 0.000
S1 0.000 0.000
S2 0.000 0.000
S3 0.000 0.500 <-- the only cell that changedOne full episode, four moves, one non-zero number. Nothing the agent did before the last step produced any learning at all, because the target for every earlier step was zero plus a discounted zero.
Episode 2
S0,R : target = 0 + 0.9*max(0, 0) = 0 Q = 0 + 0.5*(0 - 0) = 0.000
S1,R : target = 0 + 0.9*max(0, 0) = 0 Q = 0 + 0.5*(0 - 0) = 0.000
S2,R : target = 0 + 0.9*max(0, 0.500) = 0.450 Q = 0 + 0.5*(0.450 - 0) = 0.225
S3,R : target = 1 Q = 0.5 + 0.5*(1 - 0.5) = 0.750
L R
S0 0.000 0.000
S1 0.000 0.000
S2 0.000 0.225 <-- value has moved back one square
S3 0.000 0.750Episode 3
S0,R : target = 0 + 0.9*max(0, 0) = 0 Q = 0.000
S1,R : target = 0 + 0.9*max(0, 0.225) = 0.2025 Q = 0 + 0.5*(0.2025 - 0) = 0.101
S2,R : target = 0 + 0.9*max(0, 0.750) = 0.675 Q = 0.225 + 0.5*(0.675-0.225) = 0.450
S3,R : target = 1 Q = 0.75 + 0.5*(1 - 0.75) = 0.875
L R
S0 0.000 0.000
S1 0.000 0.101
S2 0.000 0.450
S3 0.000 0.875Episode 4
S0,R : target = 0.9*0.10125 = 0.0911 Q = 0 + 0.5*(0.0911 - 0) = 0.046
S1,R : target = 0.9*0.45 = 0.4050 Q = 0.10125 + 0.5*(0.405 - 0.10125) = 0.253
S2,R : target = 0.9*0.875 = 0.7875 Q = 0.45 + 0.5*(0.7875 - 0.45) = 0.619
S3,R : target = 1 Q = 0.875 + 0.5*(1 - 0.875) = 0.938
L R
S0 0.000 0.046 <-- the goal has finally reached the start
S1 0.000 0.253
S2 0.000 0.619
S3 0.000 0.938Four episodes for the reward to travel four squares. Value propagates exactly one step per episode along the path the agent takes, which is the single most important intuition about sparse rewards: the number of episodes you need scales with the distance between the reward and the decision that earned it.
Episode 5, with one exploratory move
Suppose this time the epsilon-greedy policy picks L at S1 before continuing. That move is a mistake, and the update records it as a mistake without punishing it:
S0,R : target = 0.9*0.253125 = 0.2278 Q = 0.0456 + 0.5*(0.2278 - 0.0456) = 0.137
S1,L -> S0, r=0 :
target = 0.9*max(0, 0.137) = 0.1233
Q(S1,L) = 0 + 0.5*(0.1233 - 0) = 0.062
S0,R : target = 0.9*0.253125 = 0.2278 Q = 0.137 + 0.5*(0.2278 - 0.137) = 0.182
S1,R : target = 0.9*0.61875 = 0.5569 Q = 0.253125 + 0.5*(0.5569-0.2531) = 0.405
S2,R : target = 0.9*0.9375 = 0.8438 Q = 0.61875 + 0.5*(0.8438 - 0.6188) = 0.731
S3,R : target = 1 Q = 0.9375 + 0.5*(1 - 0.9375) = 0.969
L R
S0 0.000 0.182
S1 0.062 0.405
S2 0.000 0.731
S3 0.000 0.969Q(S1,L) is 0.062, which is positive — going left is not worthless, you can come back. It is well below Q(S1,R) at 0.405, so the greedy policy is unaffected. The agent has learned that the detour is worse without having to be told it is forbidden.
Comparing against the exact answer
This problem is small enough to solve exactly. The optimal value of taking R from S3 is 1; from S2 it is 0.9 times that; and so on:
state optimal Q(s,R) estimate after 5 episodes fraction S3 1.000 0.969 97% S2 0.900 0.731 81% S1 0.810 0.405 50% S0 0.729 0.182 25%
Three things are visible in that table and none of them is obvious from the update rule alone. Estimates approach the true values from below, because they start at zero and the only source of positive value is the goal. Accuracy degrades with distance from the reward. And the states nearest the reward converge first, which means an agent that looks like it has learned nothing may have learned the endgame perfectly.
The same five episodes at three learning rates
Run the identical trajectory with alpha at 1.0 and at 0.1 and the difference is stark. Following Q(S3,R), the cell nearest the reward, episode by episode:
episode alpha = 1.0 alpha = 0.5 alpha = 0.1 1 1.000 0.500 0.100 2 1.000 0.750 0.190 3 1.000 0.875 0.271 4 1.000 0.938 0.344 5 1.000 0.969 0.410 and the whole table at alpha = 1.0 after four episodes: Q(S3,R) = 1.000 (exactly optimal) Q(S2,R) = 0.900 (exactly optimal) Q(S1,R) = 0.810 (exactly optimal) Q(S0,R) = 0.729 (exactly optimal)
At alpha = 1.0 the table reaches the exact optimal values in four episodes, which looks like an argument for always using it. It is not. A learning rate of 1 replaces the old estimate with the newest observation entirely, which is correct only because this environment is deterministic — the same action from the same state always produces the same reward and the same next state.
Make it stochastic and alpha = 1.0 breaks completely. Suppose reaching the goal pays 1 half the time and 0 the other half. With alpha = 1.0, Q(S3,R) alternates between 1.000 and 0.000 forever, and it is wrong on every single episode; the correct value is 0.5 and the estimate never visits it. With alpha = 0.1 the update is an exponentially weighted average over past outcomes and it settles near 0.5, wandering by a few hundredths.
That is the whole trade, and it has a simple statement: alpha is how many past observations you are effectively averaging over, roughly 1 / alpha of them. Ten for 0.1, two for 0.5, one for 1.0. Choose it by how noisy your rewards are, not by how fast you want convergence — and where transitions are stochastic, a schedule that starts high and decays gets both.
Why the max makes it off-policy
The target uses max_a’ Q(s’, a’) — the value of the best action available next — regardless of which action the agent will actually take. In episode 5 the agent took a random left turn, and the update still assumed optimal play from the state it landed in.
That is what off-policy means, and it is a genuinely useful property: the agent can explore badly, act randomly, or replay somebody else’s data, and still converge on the value of the optimal policy. Replace the max with the value of the action actually taken next and you get SARSA, which learns the value of the policy being followed, exploration included. On a cliff-edge problem SARSA learns to walk further from the cliff, because it accounts for the chance that exploration pushes it off. Q-learning walks along the edge, because it assumes it will never slip.
Off-policy learning is also what makes learning from logs conceivable at all — and what makes it fail in a specific way when the logs do not cover the actions the new policy wants to take. That failure is the subject of offline RL.
What breaks when the table becomes a network
A table needs one cell per state-action pair. Chess has more positions than there are atoms available to store them, so the table is replaced with a function approximator, and three things break at once.
- Updates stop being local. Changing the network to fix
Q(S1,R)changesQ(S2,R)too. Generalisation is the point, and it also means an error can spread instead of staying in one cell. - The target moves while you chase it. The target depends on the same network being updated, so the regression target shifts every step. The standard fix is a target network — a delayed copy of the weights, refreshed every few thousand steps — introduced with DQN in Mnih et al. (2015).
- The max becomes a bias. Taking the maximum over noisy estimates systematically overestimates, because the maximum of several noisy numbers is biased upwards. Double Q-learning (van Hasselt, 2010; the deep version, 2016) separates action selection from action evaluation to cut it.
These three problems are the reason value-based deep RL has a reputation for instability, and the reason the language model world mostly went the other way, towards policy gradient methods that optimise the policy directly rather than through a value estimate.