Q-Learning

Setup from the previous topics. The world is an MDP (topic 196). Good behavior is a policy (topic 197). Prices on states and actions are values and Q-values (topic 198). The Bellman equation says every correct price satisfies one recursion (topic 199). TD learning says you can chase that recursion one real step at a time (topic 200).

One brutal constraint remains:

Watkins' 1989 answer — Q-learning — is so clean it became the field's default: keep a table of action-values, and after every transition, nudge each guess toward one step of reality plus the best of what you already know about where you landed. The blunders in your behavior never enter the target. That single design choice is the entire magic trick.

Q-learning maintains a table Q(s,a) of action-values and, after each observed transition (s, a, r, s'), applies:

Q(s,a) ← Q(s,a) + α[ r + γ max_{a'} Q(s',a') − Q(s,a) ]

The bracketed piece, r + γ max_{a'} Q(s',a') − Q(s,a), is the TD error from topic 200 — with one word changed: where SARSA would put "the next action I will actually take," Q-learning puts max_{a'}: the best action at the next state, whichever it is. The expression r + γ max_{a'} Q(s',a') is called the TD target.

Three properties define the algorithm:

1. Model-free. It never needs P(s'|s,a) — the world's dice stay hidden. It learns from raw samples: state, action, reward, next state.
2. Off-policy. The max_{a'} in the target aims at the optimal policy, while the agent's behavior can be greedy-with-exploration (ε-greedy below). Data-gatherer and data-learner are different policies — and the algorithm does not care.
3. It estimates Q* directly. When the table converges, the optimal policy is a free lookup: π*(s) = argmax_a Q(s,a).

That is everything: one line of arithmetic, repeated on experience, outputs the whole optimal cheat sheet.

You are in state s, action a currently scores Q(s,a) = 2.0.

You take it and observe: reward r = 1, landing in state s'. You glance at your current table: the best action-value at s' is max_{a'} Q(s',a') = 5.0. Learning rate α = 0.1, discount γ = 0.9.

Step by step:

• TD target: y = r + γ max_{a'} Q(s',a') = 1 + 0.9 × 5 = 5.5.
• TD error: δ = y − Q(s,a) = 5.5 − 2.0 = 3.5. ("Reality plus my best future guess says this move was worth 3.5 more than I believed.")
• Update: Q(s,a) ← 2.0 + 0.1 × 3.5 = 2.35.

One tiny step toward the target — 10% of the way — because α = 0.1. After enough visits, Q(s,a) sits at its target's average: exactly the Bellman fixed point from topic 199, now chased from samples instead of from a model.

Then, next time you stand at s, your behavior is ε-greedy: with probability ε (say 0.1) you sample a random action to keep learning; otherwise you exploit argmax_a Q(s,a). Notice carefully: the random 10% exploration changes which cell of the table gets updated, but never changes what the update aims at.

Carry one analogy: Q-learning is a restaurant guidebook writer who eats randomly but writes the optimal review.

• Her behavior: 10% of the time she orders a random dish (exploration) so she can taste everything.
• Her review of each restaurant: "the best possible meal here, followed by the best plan from wherever that meal leads you." She writes the guide for a perfect planner, even though she herself orders like a coin flip.

In MDP language:

code
Copy
behavior policy μ (what she DOES):   90% argmax Q, 10% random   ← gathers data
        │  transition (s, a, r, s')
        ▼
target policy π (what she LEARNS):   greedy forever: max_{a'}   ← written into Q

This is where off-policy learning shines. Even though exploration injects random, mediocre actions, the update target ignores them and always bootstraps from the best action at the next state. So clumsy exploratory behavior does not poison the learned Q*: the algorithm still recovers the optimal policy.

And this is what makes the code below — plain tabular Q-learning — work: one loop, two roles. The ε-greedy line behaves; the np.max(Q[s2]) line learns. The environment supplies (s2, r, done); the done flag zeroes the bootstrap at the terminal state (no future beyond the end). Run it and the final policy = Q.argmax(axis=1) is the deployable cheat sheet: one best action per state, learned entirely from imperfect play.

import numpy as np, random

Q = np.zeros((n_states, n_actions))
alpha, gamma, epsilon = 0.1, 0.99, 0.1

for ep in range(5000):
    s = env.reset()
    done = False
    while not done:
        # epsilon-greedy BEHAVIOR policy
        a = random.randrange(n_actions) if random.random() < epsilon \
            else int(np.argmax(Q[s]))
        s2, r, done = env.step(a)
        # OFF-Policy target uses max over s' actions, not the one taken
        target = r + gamma * (0.0 if done else np.max(Q[s2]))
        td_error = target - Q[s, a]
        Q[s, a] += alpha * td_error
        s = s2

policy = Q.argmax(axis=1)   # deployable greedy policy

Q-learning is proven to reach Q* with probability 1 on finite MDPs — the TD-error form of the Bellman-optimality contraction from topic 199, now driven by samples. The theorem needs two things:

• Every (s,a) pair is visited infinitely often. This is what exploration is for: cells never tried are cells never corrected. Sustained ε-greedy (or decaying-but-not-zero) guarantees it.
• The step-size schedule satisfies Robbins–Monro: Σ_t α_t = ∞ (steps large enough in total to reach the answer from any start) and Σ_t α_t² < ∞ (small enough late that the noise of random experience averages out instead of jiggling forever). Learn fast early, damp the noise late.

With a constant small α — the norm in deep RL — convergence is to a neighborhood of Q*, not exactly to it: the table keeps wobbling as fresh samples arrive.

A classic interview comparison — and the place where the guidebook analogy pays rent.

• SARSA learns the value of the policy actually followed (on-policy: its target is r + γQ(s', a_next), with the exploratory next action included). It is safer in the real world because it knows its own risk and routes away from deadly states.
• Q-learning learns the value of acting optimally (off-policy: r + γ max_{a'} Q(s',a')). More aggressive, more sample-efficient if your goal is to imitate the best policy — but its optimistic max can overvalue states.

The picture Sutton and Barto made famous — cliff walking:

code
Copy
  start • ─ ─ ─ ─ ─ ─ ─ ► goal
          ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
          ☠☠☠☠☠☠☠☠☠☠☠☠☠☠   ← falling in = big negative reward

  SARSA route:      hugs the far wall — it knows its own dice sometimes slip
  Q-learning route: hugs the cliff edge — it assumes PERFECT future control

During training, Q-learning walks close enough to the cliff that a random ε-exploration step occasionally falls in. Its learned policy is still the shortest edge route (the target assumed perfect play), but living with that policy while exploring is a different matter. The guidebook writer never falls — but her readers might.

And three closing facts the field built on this split:

Everything value-based after 1989 is Q-learning wearing an accessory:

• DQN (topic 202): same update, table → deep network, plus replay and a target network to survive the deadly triad.
• Double DQN / Double Q-learning: two tables (or nets) to de-bias the optimistic max.
• Offline RL (2020s): learn purely from stored logs of someone else's behavior — only an off-policy algorithm can do that honestly, and Q-learning's target is precisely "what the best policy would have gotten."
• Delivery robots and grid agents (see the real-world example below): a discretized warehouse, Q(state, move) learned from trial and error alone, greedy argmax traced out the shortest safe route with no map of slip or traction.

Know this update rule cold and you can read most of the value-based literature — the equations that follow are it, dressed up.