Core ML

Q-Learning and DQN

Learn what each action is finally worth, then take the biggest number. Two tricks made that work with a network: sampled replay, and a target that holds still.

One cell of the action-value table is pulled toward the reward just seen plus the discounted best value in the next state's row, so an estimate is trained on another estimate rather than on a finished outcome

Why Does This Exist?

A signal controller sits at the crossing of two arterial roads. Every second it can hold the current green or switch phase. It sees the queue on each of four approaches, which phase is running, and for how long. Its reward each second: minus the number of vehicles sitting still.

The reinforcement learning setup gives you the vocabulary — states, actions, a reward, a discount factor $\gamma$ . It doesn't give you a controller.

Suppose you knew how much each of the two actions was ultimately worth in every situation, counting everything that follows. Then you'd never plan again. Look up two numbers, take the bigger one.

Think of It Like This

Reading the next road sign instead of driving the whole way

You want to know how long the drive is from your depot to the port. The honest method: drive it and time it.

The cheap one: drive to the next junction, note that it took six minutes, and read the sign there — "Port 48". Your estimate for the depot is now 54. One measured hop, plus a sign you trusted.

The obvious objection is right: if that sign is wrong, your new number is wrong too. What saves it is that the sign nearest the port is the one you can get right, and corrections propagate back one junction at a time. Start with signs full of nonsense, keep measuring single hops, and the whole map converges.

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 if you take action $a$ in state $s$ and behave well after. Switch phases now, and it accounts for every vehicle-second out to the horizon.

You learn it one transition at a time. You were in $s$ , took $a$ , got reward $r$ , landed in $s'$ :

Q(s, a) \leftarrow Q(s, a) + \alpha\big[\, r + \gamma \max_{a'} Q(s', a') - Q(s, a) \,\big]

$\alpha$ is a small step size, $r$ the reward you observed, $s'$ where you ended up, and $\max_{a'} Q(s', a')$ the best value your current estimates claim is available there. The bracket is how wrong the old estimate was; you move a fraction of the way toward fixing it.

What isn't in that expression: the end of the episode. You updated a value from one real step plus your own guess about the next state. That's bootstrapping, and it lets learning start before any outcome finishes — which matters, because an intersection has no episodes.

The $\max$ never asks how you behaved. Hand it six months of logs from a fixed-timer controller and it still learns about the greedy policy. That's off-policy — old data isn't wasted data.

What breaks when the table becomes a network

A table is fine while you can count the states. Four queue lengths from zero to forty, times eight phases, times a timer — millions of cells, most never visited.

So predict instead of store. Feed the state in, read one $Q$ value per action out; an MLP does the job. Train it with gradient descent on a squared-error loss 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 you're updating, so every step changes the thing you were fitting toward.

Consecutive transitions are nearly identical. Gradient descent assumes roughly independent samples, and traffic states one second apart are the same state with a rounding difference. A batch of consecutive frames carries roughly as much information as one example.

Replay, a frozen target, and the bias that's left

The replay buffer stores the last million transitions and hands out batches sampled uniformly at random. That breaks the correlation, and every transition gets reused dozens of times — which matters when each one costs a real second at a real intersection.

The target network is a frozen copy of the weights, used only for the label, refreshed every few thousand steps. Between refreshes the target holds still, so each stretch of training is ordinary regression against a fixed label. Together, most of what DQN was.

One bias survives. Take the largest of several noisy estimates and you get a number too high on average, even when every action is worth the same — the $\max$ selects whichever estimate got the luckiest noise, and bootstrapping compounds it. Double Q-learning splits selection from scoring: one set of weights picks, a second scores.

The hard limit lives in the $\max$ : you enumerate the actions. Two signal phases, fine. A valve position anywhere between open and shut, not fine. That's the other page.

Show Me the Code

No environment needed to show the overestimation: give every action a true value of zero and add noise.

1import numpy as np2
3
4def bias_of_max(n_actions: int, noise: float = 1.0, trials: int = 200_000) -> tuple[float, float]:5    """Every action is truly worth 0.0 here. Only the estimation noise differs."""6    rng = np.random.default_rng(0)7    a = rng.normal(0.0, noise, size=(trials, n_actions))  # one set of estimates8    b = rng.normal(0.0, noise, size=(trials, n_actions))  # an independent second set9    single = a.max(axis=1)                                # choose and score with the same numbers10    picked = a.argmax(axis=1)11    double = b[np.arange(trials), picked]                 # choose with a, score with b12    return float(single.mean()), float(double.mean())13
14
15for k in (2, 4, 8):16    single, double = bias_of_max(k)17    print(f"{k} actions: one table {single:+.3f}   two tables {double:+.3f}")18    # -> 2 actions: one table +0.566   two tables -0.00219    # -> 4 actions: one table +1.031   two tables +0.00020    # -> 8 actions: one table +1.423   two tables -0.001

Eight actions worth nothing report +1.42, and the bias grows with the action count: more candidates, more chances for one to look lucky. Score with an independent second set and it collapses to zero.

Watch Out For

Training against a target that moves with you

Loss drops for four thousand steps, climbs for three thousand, drops again. Average $Q$ creeps past any return the intersection could physically produce. You check the buffer, the reward, the shapes, the learning rate. All correct.

Nothing is broken — you're regressing onto a label computed from the weights you're changing. Freeze a copy, compute the label from that, refresh every few thousand steps. If the oscillation survives, lengthen the interval before touching the learning rate: the period of the wobble tracks the refresh interval, not the step size.

A policy that's confident about actions it got lucky with

The controller strongly prefers holding green on the eastbound approach, and its $Q$ values say that action is worth far more than switching. Watch it run: the northbound queue backs up around the corner while eastbound sits nearly empty.

That's the maximisation bias arriving at its destination, and it hits hardest where samples are few — the eastbound approach got lucky early, and bootstrapping copied the inflated value backwards instead of averaging it out. Pick with the online network, evaluate with the target network; rising average $Q$ next to flat return is the pattern to watch.

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 an estimate toward the reward plus the discounted best estimate at the next state — bootstrapping.
Off-policy, so exploratory behaviour and old logs both teach you about the greedy policy.
A network breaks two assumptions: the label moves with the weights, and consecutive transitions aren't independent.
A replay buffer fixes the correlation, a frozen target fixes the moving label; those two are the substance of DQN.
The $\max$ overestimates on noisy estimates and bootstrapping compounds it. Split selection from evaluation.
Needs a small discrete action set, because the max enumerates them.