Q-Learning and DQN

Why Does This Exist?

A signal controller sits at the crossing of two arterial roads. Every second it holds the current green or switches phase. It sees the queue on each approach, which phase runs, and for how long. Its reward each second is minus the number of vehicles sitting still.

The reinforcement learning setup gives you the vocabulary for this: states, actions, a reward, a discount factor. It does not give you a controller. But suppose you knew how much each action was ultimately worth in every situation, counting everything that follows. Then you would never plan again. Look up two numbers, take the bigger one.

This page covers learning those worths with Q-learning and scaling that to a network with DQN. The setup underneath is on the reinforcement learning foundations page, and the alternative family that learns a policy directly is policy gradient methods.

The one idea you need first. Future rewards count less than immediate ones through a discount factor $\gamma$ between 0 and 1. A reward of 10 three steps out at $\gamma = 0.9$ is worth $10 \times 0.9^3 = 7.29$ now. That single number is what makes "finally worth" a finite quantity.

Think of It Like This

How It Actually Works

The Bellman update, and why bootstrapping is the trick

The action value $Q(s, a)$ is the discounted return you expect from taking action $a$ in state $s$ and behaving well afterward. You learn it one transition at a time. You were in $s$, took $a$, observed reward $r$, and landed in $s'$:

$\alpha$ is a small step size, $r$ is the reward just seen, $s'$ is where you landed, and $\max_{a'} Q(s', a')$ is the best value your current estimates claim is available there. The bracket is how wrong the old estimate was, and you move a fraction of the way toward fixing it. Nothing in that expression waits for an episode to end. You updated a value from one real step plus your own guess about the next state, which is bootstrapping, and it lets learning start before any outcome finishes. The $\max$ never asks how you behaved, so old logs from any controller still teach the greedy policy. That is off-policy.

Worked example

One transition at the intersection. Holding green in state $s$ currently rates $Q(s, \text{hold}) = 3.2$. You hold, two vehicles wait, so $r = -2.0$, and you land in $s'$ whose best action rates $\max_{a'} Q(s', a') = 4.0$. With $\gamma = 0.9$ and $\alpha = 0.1$:

• Target: $r + \gamma \max_{a'} Q(s', a') = -2.0 + 0.9 \times 4.0 = -2.0 + 3.6 = 1.6$.
• Error: $1.6 - 3.2 = -1.6$. The old estimate was optimistic.
• New value: $3.2 + 0.1 \times (-1.6) = 3.2 - 0.16 = 3.04$.

The cell moves a tenth of the way from 3.2 toward 1.6. Thousands of such nudges, spread across states, converge on the true worths.

What breaks when the table becomes a network

A table works while states are countable, then the state space explodes and most cells sit empty forever. So predict instead of store: feed the state into a small network, read one $Q$ value per action out, and train it with gradient descent on the squared error against $r + \gamma \max_{a'} Q(s', a')$. Two things go wrong, and neither is a bug.

The target moves. That label comes from the very weights being updated, so every step shifts what you fit toward. Consecutive transitions are near-identical. Traffic one second apart is the same scene with rounding differences, while gradient descent expects roughly independent samples.

Replay, a frozen target, and the bias that survives

The replay buffer stores the last million transitions and serves random batches, which breaks the correlation and reuses each expensive real-world second dozens of times. The target network is a frozen copy of the weights used only for the label, refreshed every few thousand steps, so each stretch of training is ordinary regression against a fixed label. Those two fixes are most of what DQN was.

One bias survives them. Taking the largest of several noisy estimates returns a number too high on average, because the $\max$ selects whichever estimate got the luckiest noise, and bootstrapping compounds it upward. Double Q-learning splits selection from scoring: one set of weights picks the action, an independent set scores it. And the hard limit lives in the $\max$ itself: you must enumerate the actions, so two signal phases work fine and a continuous valve position needs a different family.

Code

The point of this snippet is the update as arithmetic: one Bellman step on the worked numbers above, nothing else.

1def q_update(q: float, reward: float, next_best: float, gamma: float, alpha: float) -> tuple[float, float, float]:2    target = reward + gamma * next_best3    error = target - q4    return target, error, q + alpha * error5
6
7target, error, new_q = q_update(3.2, -2.0, 4.0, 0.9, 0.1)8print(round(target, 2))9# -> 1.610print(round(error, 2))11# -> -1.612print(round(new_q, 2))13# -> 3.04

The cell drops from 3.2 to 3.04, exactly the hand computation in the worked example.

Watch Out For

The Quick Version

• $Q(s, a)$ is the discounted return from taking action $a$ in state $s$ and behaving well after. Know it and the policy is an argmax.
• The Bellman update moves one estimate a fraction $\alpha$ toward the reward plus the discounted best estimate at the next state, which is bootstrapping.
• Off-policy learning means exploratory behavior and old logs both teach the greedy policy.
• With a network the label moves with the weights and consecutive samples correlate, so DQN adds a replay buffer and a frozen target network.
• The $\max$ overestimates on noisy estimates and bootstrapping compounds it, so split selection from scoring.
• The $\max$ enumerates actions, so this family needs a small discrete action set.

What to Read Next

• Reinforcement Learning Foundations
• Temporal Difference Learning
• Policy Gradient Methods