Q-learning and DQN: learning the value of actions, from a table to a neural network

Temporal-difference learning, Q-learning and SARSA on cliff walking, ε-greedy exploration, on-policy and off-policy, DQN with experience replay and a target network on the cart-pole written from scratch, and why DQN learning falls apart so easily.

12 minutes Matěj Žalmánek 2026-10-16

Series AI basics Part 48 of 52

Full series syllabus 52 of 83 topics published

What you will take away

How an agent learns the values of actions without knowing the rules of the world.
Why Q-learning and SARSA choose different paths on the cliff.
What experience replay and the target network do in DQN, and why DQN is fickle.

Useful to know first: Markov decision processes: states, actions, rewards and the Bellman equations, Neuroevolution: evolving the weights and shape of neural networks, and the NEAT algorithm

In the previous part we computed the best policy exactly, because we knew the rules of the world: where each action leads and with what probability, and what the agent gets for it. A real agent does not know them. A robot does not know exactly how its wheel will slip, a program playing a game does not know the game’s internals. It has to try things and learn from what happened. In this part we write two such algorithms: Q-learning with a table and DQN, where a neural network replaces the table — exactly the combination DeepMind used in 2015 to teach a computer to play dozens of Atari games from the screen.

It builds on the parts Markov decision processes and A neural network from scratch.

1. Learning from experience

Definition — temporal-difference (TD) learning

Let (S, A, P, R, γ) be an MDP (notation from the previous part), π the policy the agent acts by, V : S → ℝ the current estimate of the value function V^π and α ∈ (0, 1] the learning rate. Let (s, a, r, s′) ∈ S × A × ℝ × S be one transition that actually happened: the agent was in state s, chose action a, received the reward r = R(s, a, s′) and got to s′. We define

the TD target y = r + γ V(s′) (if s′ is terminal, V(s′) = 0, so y = r);
the TD error δ = y − V(s);
the TD step (the TD(0) method): the new estimate V′ : S → ℝ is V′(s) = V(s) + α δ, V′(u) = V(u) for all u ∈ S, u ≠ s.

So instead of the average ∑_s′ P(s′ | s, a) […] over all possible next states (as in the Bellman equation), a single transition that actually happened is used, and we need to know neither P nor R. The target y contains the method’s own estimate V(s′) — an estimate is corrected using another estimate (bootstrapping).

In plain words

In the morning you estimate that you will get to work in 30 minutes. Ten minutes later you are stuck in a traffic jam and the navigation says there are still 35 to go. You do not have to wait until you arrive — you already know that the morning estimate was 15 minutes off, and next time you will raise it a little. You learn from the difference between two successive estimates.

V(s) ← V(s) + α [r + γ V(s′) − V(s)]

V(s): the current estimate of the value of the state we started from — this is what we correct; inside the brackets it is subtracted so that the correction is proportional to the error, not to the whole value
α: learning rate, 0 < α ≤ 1 — how big a piece of the error we accept; a single transition is a random sample, so we do not trust it completely
r: the reward actually received — the only part of the target that is measured, not estimated
γ: discount — the value of the next state comes one step later, just as in the Bellman equation
V(s′): the estimated value of the state we actually reached — it stands in for the whole remaining future we have not lived through yet (bootstrapping); a single sample instead of the average ∑ P(s′ | …)

r + γ V(s′) is the TD target, the expression in square brackets is the TD error.

Example — the commute in numbers

The estimate from home is V(home) = 30 minutes. After r = 10 minutes of driving you are in a jam and the estimate from there is V(jam) = 35. Time is not discounted (γ = 1) and we add up minutes instead of rewards, so the TD target is 10 + 1 · 35 = 45 and the TD error 45 − 30 = 15 (colours as in the formula above).

with α = 0.5: the new estimate is 30 + 0.5 · 15 = 37.5 minutes,
with α = 0.1: 30 + 0.1 · 15 = 31.5 minutes,
with α = 1: straight to 45 — the last experience would completely overwrite all earlier ones.

Theorem — with a fixed α the estimate is a moving average of the targets

Let α ∈ (0, 1], n ∈ ℕ, n ≥ 1, Q₀ ∈ ℝ and c₁, …, c_n ∈ ℝ (the targets). Let, for k = 1, …, n,

Q_k = Q_k−1 + α (c_k − Q_k−1).

Then

Q_n = (1 − α)ⁿ Q₀ + ∑_k=1ⁿ α (1 − α)^n−k c_k,

and the weights are non-negative and sum to (1 − α)ⁿ + ∑_k=1ⁿ α (1 − α)^n−k = 1 — Q_n is a weighted average of Q₀ and the targets.

Proof. The rule can be rewritten as Q_k = (1 − α) Q_k−1 + α c_k and substituted repeatedly (by induction on n). The sum of the weights follows from the formula for a geometric series: ∑_k=1ⁿ α (1 − α)^n−k = α · 1 − (1 − α)ⁿ/α = 1 − (1 − α)ⁿ. ∎

The weights decrease geometrically: with α = 0.5 the last target has weight 0.5, the one before 0.25, the next 0.125… Older experience is thus gradually forgotten — that helps when the targets change (and in TD learning they do change, because they are computed from estimates that are themselves being learned), but in a random world the estimate fluctuates. That is why the theory requires α to decrease gradually for guaranteed convergence.

2. Q-learning

Definition — Q-learning and SARSA

Let (S, A, P, R, γ) be an MDP, Q : S × A → ℝ a table of current estimates of action values (at the start, say, 0 everywhere), α ∈ (0, 1] the learning rate and (s, a, r, s′) a transition that actually happened, as in the definition of TD. For a terminal state s′ we set Q(s′, a′) = 0 for all a′ ∈ A.

Q-learning (Christopher Watkins, 1989) changes a single cell of the table after every transition: Q(s, a) ← Q(s, a) + α [r + γ · max_{a′ ∈ A} Q(s′, a′) − Q(s, a)]; the other cells Q(u, b), (u, b) ≠ (s, a), stay unchanged.
SARSA additionally needs the action a′ ∈ A that the agent actually chooses in s′ according to its policy (hence the name: s, a, r, s′, a′), and replaces the maximum with its value: Q(s, a) ← Q(s, a) + α [r + γ · Q(s′, a′) − Q(s, a)].

So Q-learning learns the value of the best behaviour Q*, SARSA the value Q^π of how the agent actually behaves, exploration included. For Q-learning it holds (Watkins and Dayan, 1992): if γ < 1, the rewards are bounded, every pair (s, a) is corrected infinitely often and the learning rates α_k(s, a) at the k-th correction of the cell (s, a) satisfy ∑_k α_k = ∞ and ∑_k α_k² < ∞, then Q converges to Q* with probability 1.

In plain words

A table of “how good is it to do this here”. After every step the cell is corrected by what came right after: the reward plus how good things look from the new place. Q-learning calculates as if it played perfectly from there on; SARSA reckons that it will occasionally do something silly.

Q(s, a) ← Q(s, a) + α [r + γ · max_a′ Q(s′, a′) − Q(s, a)]

Q(s, a): the table cell for the action just tried — only this one is corrected; the other actions in s do not change, because this step said nothing about them
α: learning rate — 0.5 here: the cliff world is deterministic, so we need not be afraid of the new target
r: the reward for the step: −1, or −100 for a fall
γ: discount — on the cliff γ = 1, because an episode always ends and every step costs −1, so a shorter path is better even without discounting
max_a′ Q(s′, a′): the value of the best action in the new state — Q-learning assumes it will play optimally from there on, even though in reality it occasionally tries a random action; in the charts below Q-learning is amber

Instead of the amber maximum, SARSA has Q(s′, a′) for the action a′ that the ε-greedy policy actually chooses in s′ (green in the charts). It is a sampled form of the Bellman equation: the TD target with the maximum replaces the ∑ P(s′ | s, a) […] from the previous part with a single transition that actually happened.

# Q-learning (and SARSA) on cliff walking
Q(s, a) = 0 for all states and actions
for each episode:
    s = start
    a = ε-greedy action by Q in s
    while s is not the goal:
        take a, observe r and s′          # fall: r = −100, s′ = start
        a′ = ε-greedy action by Q in s′
        target = max over b Q(s′, b)     # Q-learning
        target = Q(s′, a′)               # SARSA (instead of the line above)
        if s′ is the goal: target = 0
        Q(s, a) = Q(s, a) + α · (r + γ · target − Q(s, a))
        s = s′;  a = a′

Example — the first falls (α = 0.5, γ = 1, the table starts at zeros)

Right at the start the agent tries a step to the right and falls: r = −100, s′ = start, where all values are still 0. The new value is Q(start, →) = 0 + 0.5 · (−100 + 1 · 0 − 0) = −50 (colours as in the formula above).

Then it tries a step up: r = −1, the new cell has all zeros, Q(start, ↑) = 0 + 0.5 · (−1 + 1 · 0 − 0) = −0.5.

When it falls from the start a second time, the largest value at the start is still 0 (it has not tried ↓ and ← yet), so Q(start, →) = −50 + 0.5 · (−100 + 1 · 0 − (−50)) = −75. With every further fall it gets closer to −100 and beyond.

Notice the side effect: all real rewards are negative, so untried actions with zero look better than the tried ones. A table starting at zeros pushes the agent to try new things by itself here (so-called optimism in the face of uncertainty) — in the greedy choice, before chance ε even comes into play.

Definition — ε-greedy policy

Let S be a set of states, A a finite non-empty set of actions, Q : S × A → ℝ and ε ∈ [0, 1]. For every s ∈ S let a*(s) ∈ argmax_{a ∈ A} Q(s, a) be the greedy action (if there are several maxima, one of them). The ε-greedy policy with respect to Q is the stochastic policy

π(a | s) = 1 − ε + ε/|A| for a = a*(s), π(a | s) = ε/|A| for a ≠ a*(s).

Equivalently: with probability 1 − ε choose a*(s), with probability ε choose an action uniformly at random from the whole of A (the greedy one included). For ε = 0 it is the greedy policy. Without random actions the agent would never try anything that does not yet seem best to it, and it could get stuck on the first decent path it finds. It is the simplest solution to the exploration versus exploitation dilemma.

In plain words

Nine times out of ten you go to your favourite restaurant. Once in a while you try a new one — otherwise you would never find out that the place a street further on cooks better.

Example — action probabilities at ε = 0.1

The random action is chosen from all |A| = 4 actions, including the best one. Therefore

π(a | s) = 1 − ε + ε/|A| = 1 − 0.1 + 0.1/4 = 0.925 for the best action and ε/|A| = 0.1/4 = 0.025 for each of the other three.

Any particular “bad” action — say a step down into the cliff — thus comes up in one step out of 40.

3. Cliff walking: Q-learning versus SARSA

A classic experiment from the textbook by Richard Sutton and Andrew Barto. A 12 × 4 grid, the start at the bottom left, the goal at the bottom right and a cliff between them. Every step costs −1, a fall into the cliff −100 and a return to the start. No discounting. The shortest path runs right along the edge of the cliff (13 steps). Both algorithms learn for 500 episodes with ε = 0.1 and α = 0.5, each in 50 independent runs.

Learned (greedy) paths from the start S to the goal G; the cliff in red Q-learning (13 steps) SARSA (17 steps)

In all 50 of 50 runs Q-learning learned the shortest path along the cliff. In 41 runs SARSA chose a path along the top edge of the grid, as far from the cliff as possible (17 steps), in one a path two steps longer still, and in 8 runs the greedy policy still does not reach the goal after 500 episodes — it loops in places the agent hardly ever got to during learning.

Sum of rewards per episode during learning (average of 50 runs, ε = 0.1) Q-learning SARSA shortest path (−13)

And now a paradox: during learning SARSA does better. Over the last hundred episodes it gets −25.1 on average, Q-learning −51.1. Q-learning walks along the edge of the cliff, and because every tenth step is random, it falls 0.34 times per episode on average; SARSA only 0.04 times. Q-learning learned what is best without exploration; SARSA, what is best with exploration. Which one we want depends on whether the agent will keep exploring in real operation — a robot learning on a real machine should think like SARSA.

Example — how often Q-learning falls (a simplified estimate)

Q-learning’s learned path goes up from the start and then along ten cells right above the cliff. At the start and on each of those ten cells a step down leads into the cliff (at the start a step to the right), i.e. one particular action — with probability 0.025 at ε = 0.1. Getting through 11 such cells without a fall:

0.975¹¹ = 0.757, so a fall during one pass has probability q = 1 − 0.757 = 0.243.

After a fall the agent starts again at the start, so the number of falls before a successful pass has a geometric distribution with mean q/1 − q = 0.243/0.757 = 0.32 falls per episode. Measured: 0.34 — a bit more, because the estimate ignores random steps to the left, after which the agent spends further steps above the cliff. SARSA walks along the top edge, three rows above the cliff: there it would take several random steps down in a row to get it into the cliff. It takes risks mainly at the start, and that alone gives 0.025/0.975 = 0.026 falls per episode; measured: 0.04.

Definition — learning from one’s own and another policy (on-policy / off-policy)

Let a learning method estimate the value function V^π or Q^π of some policy π (the target policy) from transitions that arise when the agent acts by a policy b (the behaviour policy).

The method is on-policy if and only if the target and the behaviour policy are identical, π = b. Example: SARSA with an ε-greedy policy — it estimates Q^π of the very ε-greedy policy it acts by.
The method is off-policy if and only if it allows π ≠ b. Example: Q-learning — it acts ε-greedily, but thanks to the maximum in the target it estimates Q* of the greedy (optimal) policy.

Off-policy methods can therefore also learn from experience collected earlier (by a different, older policy) or by someone else.

In plain words

On-policy: I learn from my own drives and judge them as they are. Off-policy: I also watch other people’s drives (or my old ones) and work out from them how the best driver would drive.

4. When the table does not fit: DQN

A table needs a row for every state. The cart-pole from the part on neuroevolution has a state of four real numbers (the position and velocity of the cart, the angle and angular velocity of the pole); an Atari game has a state made of a 210 × 160 pixel screen. No table will do. Instead, Q(s, a) is estimated by a neural network.

Definition — Deep Q-Network (DQN)

Let an MDP be given with a finite set of actions A and with states described by vectors, S ⊆ ℝ^d (the set of states need not be finite here; the sums over s′ in the definitions of the previous part are then replaced by expected values). Let Q(·, ·; θ) : S × A → ℝ be a neural network with parameters θ ∈ ℝ^m that for a state s returns the vector (Q(s, a; θ))_{a ∈ A} ∈ ℝ^|A|. DQN (Volodymyr Mnih et al., DeepMind, 2015) additionally has

experience replay (a replay buffer) D — a finite list of at most N latest transitions (s, a, r, s′, k), where k ∈ {0, 1} says whether s′ is terminal;
a target network — parameters θ⁻ ∈ ℝ^m that are copied from θ only once every C steps (θ⁻ ← θ).

For a transition from D the target is y = r + (1 − k) γ max_{a′ ∈ A} Q(s′, a′; θ⁻), and DQN minimises with respect to θ (with θ⁻ fixed) the loss

L(θ) = E_{(s, a, r, s′, k) ~ D} [(y − Q(s, a; θ))²],

where ~ D means drawing a transition from the buffer uniformly at random; in practice the expected value is estimated by the average over a random batch of transitions. So in every step the agent acts (ε-greedily with respect to Q(·, ·; θ)), stores the transition in D, takes one gradient step on L and every C steps renews θ⁻. Experience replay ensures that the network learns from random batches, not from the latest steps in a row; the target network, that the target does not move with every learning step.

In plain words

Experience replay: instead of learning only from the last few minutes, the agent looks through random memories from its whole history, so it does not forget what it could do yesterday. Target network: when you are learning to hit a target, it does not help if the target moves every time you shoot. We leave it in place for a while.

L(θ) = E_{(s, a, r, s′) ~ D} [(r + γ max_a′ Q(s′, a′; θ⁻) − Q(s, a; θ))²]

E_{… ~ D}: the average over random transitions from the replay buffer D — it mixes old and new experience, so consecutive, very similar steps do not pull the network in one direction
r: reward — on the cart-pole +1 for every step the pole stays up
γ: discount 0.99 — the network “sees” roughly 1/1 − γ = 100 steps ahead
max Q(s′, a′; θ⁻): the target from the target network with frozen parameters θ⁻ — the same maximum as in tabular Q-learning, it just does not move during a learning step; when the state s′ means a fall, this term is 0
Q(s, a; θ): the learned network’s estimate for the action actually taken — the only thing that changes in a learning step (the gradient flows only through θ)

Tabular Q-learning does with one cell what the gradient step here does with all the parameters: it pulls Q(s, a) towards the TD target.

Definition — the Huber loss

The Huber loss (with threshold 1) is the function H : ℝ → ℝ,

H(d) = d²/2 for |d| ≤ 1, H(d) = |d| − 1/2 for |d| > 1.

It is continuously differentiable with the derivative H′(d) = d for |d| ≤ 1 and H′(d) = sgn d = ±1 for |d| > 1. Our DQN plugs in d = Q(s, a; θ) − y and instead of the squared error minimises E[H(d)] (like the original paper, which clips the error to ±1): small errors are corrected as with the square, a large error (for example when the target jumps after the target network is copied) gives at most a unit gradient, and one odd transition does not throw the network off.

# DQN on the cart-pole
network Q(·; θ) 4 → 64 → 64 → 2, target network θ⁻ = θ, buffer D empty
s = random start
for t = 1 … 30,000:
    ε = max(0.05, 1 − 0.95 · t / 10,000)
    a = random action with probability ε, otherwise argmax Q(s, ·; θ)
    take a, observe s′ and whether the pole fell
    store (s, a, r = 1, s′, fell) in D        # the oldest drops out above 20,000
    s = new start if the pole fell or lasted 500 steps, otherwise s′
    draw a random batch of 32 transitions from D, for each:
        target = r,                          if it fell
        target = r + γ · max Q(s′, ·; θ⁻),   otherwise
    one Adam step on the mean Huber loss (Q(s, a; θ) − target)
    every 500 steps: θ⁻ = θ

Example — exploration and the size of the values

Exploration decreases linearly: ε₀ = 1 (all actions random), at step 5,000 ε = 1 − 0.95 · 0.5 = 0.525, and from step 10,000 on it stays at 0.05.

How large are the values the network has to learn? If the pole stood forever, the value would be 1 + 0.99 + 0.99² + … = 1/1 − 0.99 = 100; for an episode limited to 500 steps it is 1 − 0.99⁵⁰⁰/1 − 0.99 = 99.3. At the beginning the network returns numbers close to zero, so the targets have to grow by two orders of magnitude during learning — and they keep moving along with it.

Our DQN: a 4 → 64 → 64 → 2 network (two actions: push left or right), reward +1 for every step the pole stays up, γ = 0.99, a buffer of 20,000 transitions, batch 32, the target network is copied every 500 steps, ε decreases from 1 to 0.05 over the first 10,000 steps. 30,000 steps in total. Every 2,500 steps we measure how many steps the greedy policy lasts (the average over four starts, at most 500, i.e. 10 seconds).

How many steps the DQN greedy policy keeps the pole up during learning (at most 500) full DQN, seed 1 full DQN, seed 2 without experience replay without a target network

variant	best measurement	when	at the end
full DQN, seed 1	500	step 17,500	110
full DQN, seed 2	500	step 12,500	217
without experience replay	192	step 7,500	124
without a target network	9	step 2,500	9

The full DQN learns to keep the pole up for the whole 500 steps — in the run with seed 1 for the first time at step 17,500. But then it forgets again: at the end of learning it lasts only 110 steps. The second run fluctuates similarly. Without experience replay (learning only from the last 32 steps) the network does not get past 192. And without a target network learning falls apart completely: the policy lasts only 9 steps the whole time — exactly as long as a cart you keep pushing to the right. The network has “learned” a single action.

5. Why DQN is so fickle

Definition — the deadly triad

Sutton and Barto use this name for the situation in which a value-learning method has all three of the following properties at once:

function approximation: the estimate is not a table but a function with parameters θ ∈ ℝ^m (say a network) and there are fewer parameters than states, so changing θ because of one state also changes the estimates in other states;
bootstrapping: the target contains the method’s own estimate, e.g. y = r + γ max_a′ Q(s′, a′; θ);
off-policy learning: the transitions it learns from come from a policy other than the target one (see the definition above).

When any one of the three properties is missing, instability can be avoided; when all three are present, there is no general guarantee of convergence and the estimates can oscillate or diverge to infinity (Baird’s counterexample is well known). DQN contains all three — experience replay and the target network only mitigate the danger.

In plain words

The network learns from its own estimates. When the estimate rises in one state, it also rises (because the network generalises) in similar states, including the one the target is computed from. The target rises, the estimate stretches after it… A dog chasing its own tail.

In practice, therefore, a number of modifications are added: Double DQN (Hado van Hasselt et al., 2015) separates choosing the best action from evaluating it and dampens the systematic overestimation that the maximum in the target brings; then prioritised replay, the duelling of value and advantage (dueling) and more — their combination is called Rainbow (2017). And one very practical tip: during learning, save the network from the best measurement, not the last one.

y = r + γ Q(s′, argmax_a′ Q(s′, a′; θ); θ⁻)

r: reward, unchanged
γ: discount, unchanged
argmax Q(s′, a′; θ): the choice of action by the learned network — which action we would pick in s′
Q(s′, …; θ⁻): the evaluation of that action by the target network — a different estimate with different errors, so an action the learned network happened to overrate does not automatically get an overrated value too

The Double DQN target; plain DQN takes both the choice and the evaluation from the same network θ⁻ (max).

Example — why the maximum overestimates (simplified)

Two actions have a true value of 0, but the estimate of each carries an independent error of +1 or −1 (each with probability 1/2). The four equally likely cases give a maximum of the estimates of 1, 1, 1 and −1, so

E[max(Q̂₁, Q̂₂)] = 1 + 1 + 1 − 1/4 = 0.5 > 0 = max(Q₁, Q₂).

The maximum over noisy estimates is on average larger than the maximum of the true values, and because the target with the maximum is plugged in again and again, the overestimation spreads. When one estimate chooses the action and a second, independent one evaluates it, the expected value of the evaluation is 0 — the error of the second estimate no longer has anything to do with the choice.

Value-based methods like DQN work well when there are few actions (push left or right; the buttons on a controller). For continuous actions — how much force to turn a robot’s joint with — it is better to learn the policy directly. That is the topic of the next part, on policy gradient and PPO.

6. Summary

Without knowing the rules of the world, values are learned from transitions that actually happened: the estimate moves towards the target r + γ · the estimate of the next state.
Q-learning learns the value of the best behaviour (off-policy), SARSA the value of behaviour with exploration (on-policy).
On the cliff: Q-learning finds the shortest path (13 steps), but at ε = 0.1 it falls 0.34 times per episode; SARSA goes more safely and gets more during learning (−25.1 versus −51.1).
DQN replaces the table with a network; without experience replay and a target network it does not learn (at most 192 and 9 steps respectively).
Even the full DQN fluctuates: it keeps the pole up for 500 steps and then forgets it again — the deadly triad.

Want to get hands-on? Have an AI agent train a DQN on the CartPole environment from the Gymnasium library and plot the learning curve for five seeds. Then have it add Double DQN and compare.

Do you see it differently? Write to support@coden-app.com.

Q-learning and DQN: learning the value of actions, from a table to a neural network

1. Learning from experience

2. Q-learning

3. Cliff walking: Q-learning versus SARSA

4. When the table does not fit: DQN

5. Why DQN is so fickle

6. Summary

An Agent on your computer, driven from your phone