Q-Learning

Learning Without a Map

Lesson 14.2 solved a Markov decision process with value iteration and policy iteration. Both of those methods need something you almost never have: the transition probabilities. To compute the expected value of an action you must sum over every state the environment might move you to, weighted by how likely each one is. That table of probabilities is the model, and outside of board games and textbook puzzles nobody hands it to you.

A robot does not know the probability that a wheel slips. A recommender does not know the probability that a user clicks. Writing those numbers down is often harder than the original problem. So the practical question is this: can an agent learn to act well by simply acting, observing what happens, and never estimating a transition probability at all?

The answer is yes, and the family of methods that does it is called model-free. Instead of reasoning about what might happen, the agent uses what did happen. Sutton and Barto’s Reinforcement Learning: An Introduction (2nd edition, 2018) is the standard reference for everything in this lesson, and it draws exactly this line: dynamic programming needs a model, temporal-difference learning does not.

The Temporal-Difference Idea

There is an obvious model-free strategy: play a whole episode, add up the reward you actually received, and use that total as the value of the states you visited. This is the Monte Carlo approach, and it works. But it has a hard requirement — the episode has to finish before you learn anything. A game of chess, a delivery route, a customer session: you wait for the end, then update.

Temporal-difference (TD) learning refuses to wait. After a single step it already has an estimate it can improve. It moved from state S_t to state S_t+1 and collected reward R_t+1. Its old opinion was “the value here is this.” Its new, one-step-better opinion is “the value here is the reward I just got, plus the discounted value of where I landed.” The gap between those two opinions is a learning signal.

This is called bootstrapping: the update uses the agent’s own current estimate of the next state’s value in place of the true value it does not know. It sounds circular, and it is — but it converges, because the one term that is not an estimate, the observed reward, keeps injecting real information into the table.

The Q-Learning Update Rule

Q-learning takes the TD error and uses it to nudge a table of action values. Chris Watkins introduced the algorithm in his 1989 PhD thesis, and Watkins and Dayan (1992) proved that it converges to the optimal action-value function under suitable conditions on the step size and provided every state-action pair keeps being visited.

Read it as a correction rather than a computation. The agent has an opinion; the world gives it evidence; it shifts its opinion partway toward the evidence. With α = 1 it would overwrite the old value entirely and be at the mercy of a single noisy sample; with α = 0 it would never learn. In between it averages over experience.

Worked by Hand: A Four-Cell Corridor

The rule is short enough that you can run it with a pen. Here is the smallest grid world that shows the interesting behaviour — a corridor of four cells:

Update 1 — the agent is in C and moves right, entering G. It receives R = +10 and lands in a terminal state, so the bootstrap term is zero.

Update 2 — a new episode; the agent is in B and moves right, arriving in C. The reward is 0. But C is no longer worthless: the table now says Q(C, right) = 5.0, and the update rule takes the maximum over the actions available from C, which is max(Q(C, left) = 0, Q(C, right) = 5.0) = 5.0.

Update 3 — the agent is in C again and moves right into G. Same transition as update 1, but the table has changed, so the arithmetic changes with it.

Run one more step for the pattern. If the agent then moves right from A into B, the reward is 0 and max_a Q(B, a) = 2.25, so Q(A, right) ← 0 + 0.5 × (0 + 0.9 × 2.25 − 0) = 0.5 × 2.025 = 1.0125.

Three things are now visible that no amount of formalism conveys as clearly. First, value flows backwards from the reward — one cell per episode, C before B before A. Second, the agent never needed to know where right would take it; it found out by going there. Third, the values are converging to the correct answer. The true optimal values here are Q*(C, right) = 10, Q*(B, right) = 0.9 × 10 = 9, and Q*(A, right) = 0.9 × 9 = 8.1 — each cell worth one discount factor less than the next, because the reward is one step further away.

Epsilon-Greedy, and Decaying It

The worked example quietly assumed the agent kept choosing right. Why would it? At the start every entry is 0 and every action looks identical. And once Q(C, right) = 5.0, an agent that always takes its current best action will never try left again — it will never discover a better route, because it never looks.

The standard remedy is the epsilon-greedy rule from Lesson 14.1: with probability 1 − ε take the action with the highest Q-value, and with probability ε take an action uniformly at random. It is crude and it works. Lesson 14.1 also promised that Q-learning replaces the bandit’s 1/n averaging with a fixed step size α — that is exactly the α in the update above. Watkins and Dayan’s convergence result needs every state-action pair to be visited infinitely often, and a fixed positive ε is the simplest way to guarantee it.

But you do not want the same ε forever. Early on the table is meaningless and exploration is nearly free; later the table is good and random actions are pure cost. So ε is decayed — typically multiplied by a constant slightly below 1 after each episode, down to a small floor. Starting at ε = 1.0 and multiplying by 0.995 per episode gives ε ≈ 0.08 after 500 episodes; a floor of ε = 0.05 then keeps a trickle of exploration alive rather than freezing the policy.

On-Policy and Off-Policy: SARSA Beside Q-Learning

Look again at the bracket in the Q-learning update. It contains max_a Q(S_t+1, a) — the value of the best action from the next state. But the agent, being epsilon-greedy, will not necessarily take that action. Q-learning therefore learns the value of a policy it is not following. That is what off-policy means.

Rummery and Niranjan (1994) described the on-policy alternative, later named SARSA after the quintuple it uses — state, action, reward, state, action. It is the same update with one substitution: instead of the maximum, it uses the value of the action the agent actually went on to take.

The corridor makes the difference concrete. Take update 2 again — the agent moves right from B into C — and suppose that from C its epsilon-greedy choice happens to be the exploratory one, left. Q-learning uses max(0, 5.0) = 5.0 and learns Q(B, right) = 2.25, exactly as computed above. SARSA uses Q(C, left) = 0 instead, so its TD error is 0 + 0.9 × 0 − 0 = 0 and Q(B, right) stays at 0. Same transition, same reward, two different lessons drawn from it.

Neither is simply better. Because SARSA accounts for the exploration it is actually doing, it learns safer policies when exploratory mistakes are expensive — Sutton and Barto’s cliff-walking example is the canonical demonstration, where SARSA takes the longer route away from the edge and Q-learning walks the optimal path along it and occasionally falls off. Q-learning learns the optimal policy directly, which is what you want if exploration is cheap or happens in simulation. Off-policy learning also has one decisive practical advantage: because it does not require the data to come from the current policy, it can learn from stored past experience. That property is what makes the next section possible.

Why the Table Runs Out

Everything so far assumes Q is a table with one row per state and one column per action. The corridor needs eight entries. That approach ends abruptly as soon as states get big.

Consider learning to play an Atari game from the screen. Each frame is a grid of pixels with many possible values per pixel, so the number of distinct screens is astronomically larger than the number of atoms in the observable universe — and a table needs one row for every one of them. The problem is not only storage. It is that a table has no notion of similarity: two screens differing by a single pixel are separate, unrelated rows, and experience gathered in one teaches the agent nothing about the other. Even with infinite memory, an agent that must visit every state individually will never finish.

The fix is to stop storing Q and start approximating it. Replace the table with a parameterised function — a neural network taking the state as input and producing an estimated Q-value for each action — and train its weights instead of table cells. Now similar states produce similar outputs by construction, so learning generalises. This is a Deep Q-Network: the table is replaced, the update rule is not.

DQN and Its Two Stabilisers

Bolting a neural network onto the Q-learning update naively does not work; it was known to be unstable long before it was made to work. Mnih et al., “Human-level control through deep reinforcement learning” (Nature, 2015), made it work on Atari 2600 games learned directly from pixels — one architecture and one set of hyperparameters across dozens of games, reaching a level comparable to a professional human games tester on many of them. Two mechanisms did the stabilising, and each fixes a specific, nameable problem.

Experience replay fixes correlated data. Supervised learning assumes training examples are roughly independent; consecutive frames of a game are nothing of the sort, and training on them in order means every gradient step is computed on a batch of near-identical, highly correlated samples. So DQN stores transitions — state, action, reward, next state — in a large buffer and trains on random minibatches drawn from it. This breaks the correlation, and it lets each transition be reused many times instead of being consumed once. Note that this is only legitimate because Q-learning is off-policy: the buffer contains actions chosen by older, worse policies, and an on-policy method could not learn from them.

The target network fixes a moving target. In the update, the same network supplies both the prediction Q(S_t, A_t) and the target it is being fitted to, which contains max_a Q(S_t+1, a). Every gradient step therefore changes the target as well as the prediction — the agent is chasing a goal that moves whenever it moves, and the result is oscillation or divergence. DQN keeps a second, frozen copy of the network with parameters θ⁻, uses that copy to compute targets, and refreshes it from the live network only every C steps.

It is worth being clear about what changed and what did not. The learning rule is still the Q-learning update Watkins wrote down in 1989. What Mnih et al. contributed is the machinery that lets a function approximator survive it — and the convergence guarantee of Watkins and Dayan (1992), which was proved for the tabular case, does not carry over. Deep reinforcement learning works in practice, and it does so without the theoretical safety net the table had.