Q-Learning: Learning Without a Model#

Value iteration solved the gridworld — but look at what it needed: the transition function $P(s' \mid s, a)$ and reward function $R(s, a)$, evaluated inside the update for every state. It’s planning, not learning. In most scientific settings you don’t have the model; you have the ability to act and observe: run the experiment, apply the control voltage, submit the answer — and see what happens.

Q-learning is the classic answer to: can we find the optimal policy from experience alone?

Temporal-difference learning: bootstrapping from samples#

Recall the Bellman optimality equation. At convergence, for every state–action pair,

$$ Q^*(s, a) = \mathbb{E}_{s'}\big[\, r + \gamma \max_{a'} Q^*(s', a') \,\big]. $$

We can’t compute the expectation without the model — but each interaction with the environment hands us one sample of it: a transition $(s, a, r, s')$. The temporal-difference (TD) error measures how inconsistent our current estimate is with that sample:

$$ \delta = \underbrace{r + \gamma \max_{a'} Q(s', a')}_{\text{TD target: what the sample suggests}} - \underbrace{Q(s, a)}_{\text{what we currently believe}} $$

and the Q-learning update nudges the estimate toward the target:

$$ Q(s, a) \leftarrow Q(s, a) + \alpha\, \delta, $$

with learning rate $\alpha$. That’s the whole algorithm: a stochastic, sampled version of the Bellman backup. Averaging many noisy one-sample backups replaces the expectation we couldn’t compute.

Why learn Q rather than V? Acting greedily with respect to $V$ requires a one-step lookahead (i.e. "which action leads to the best next state?), which needs the model again. With $Q$, the greedy action is just $\arg\max_a Q(s,a)$: a table lookup. Learning $Q$ is what makes model-free control possible, not just prediction.
Deep dive: TD learning vs. Q-learning — the full picture
The family principle. Temporal-difference learning is any update that moves a value estimate toward a bootstrapped target — observed reward plus your own estimate of what comes next — instead of waiting for the complete return: $$ \text{estimate} \;\leftarrow\; \text{estimate} + \alpha \big[\, \underbrace{r + \gamma \cdot \text{estimate}(s')}_{\text{TD target}} - \text{estimate}(s) \,\big] $$ It sits between two extremes. Monte Carlo methods wait for the true return $G_t$ (unbiased, high variance, episode must finish). Dynamic programming uses the model to take full expectations (no variance, but needs $P$). TD splits the difference: one sampled step of reality, then bootstrap — biased while estimates are wrong, but low-variance and fully online.

Prediction vs. control. The plain member of the family, TD(0), solves prediction — evaluating a fixed policy $\pi$: $$ V(s) \leftarrow V(s) + \alpha \big[\, r + \gamma V(s') - V(s) \,\big]. $$ It cannot improve behavior by itself: acting greedily on $V$ needs a one-step lookahead through the model.

Control methods fix this by learning $Q(s,a)$, and two categories differ only in one place — whose value stands in the target:
  • SARSA (on-policy): target $r + \gamma\, Q(s', a')$ where $a'$ is the action the exploring policy actually takes next (thus needs SARSA tuple $(s,a,r,s',a')$). It learns the value of the policy it runs, exploration stumbles included.
  • Q-learning (off-policy): target $r + \gamma \max_{a'} Q(s', a')$ — the greedy action's value, whatever the agent does next (needs only tuple $(s,a,r,s')$). It learns about the optimal policy while behaving exploratorily; this is a sampled Bellman optimality backup, versus SARSA's sampled Bellman expectation backup.
So the taxonomy in one line: TD is the genus; TD(0) is prediction; SARSA and Q-learning are the control species, split by on- vs. off-policy targets.

Why the distinction keeps paying rent later. Off-policy targets are what make experience replay legitimate — old transitions from an outdated policy still yield valid $\max$-backups — one of DQN's two pillars. The TD error $\delta = r + \gamma V(s') - V(s)$ itself reappears as the critic's training signal in actor–critic methods and inside GAE, PPO's advantage estimator. And the $\max$ in Q-learning's target has a cost: with function approximation it systematically overestimates values (the motivation for Double DQN). One idea, most of the lecture's remaining algorithms.

Exploration: $\varepsilon$-greedy#

If the agent always takes the current-best action, it can lock onto an early lucky path and never discover better ones — the bandit dilemma from the previous page, now in every state. The standard fix is $\varepsilon$-greedy: with probability $1 - \varepsilon$ act greedily, with probability $\varepsilon$ act uniformly at random.

The full loop:

  1. Initialize $Q(s,a)$ arbitrarily (zeros are fine).
  2. Repeat per episode: from state $s$, pick $a$ by $\varepsilon$-greedy on $Q$; observe $r, s'$; apply the update above (using target $r$ alone if $s'$ is terminal); set $s \leftarrow s'$.

Q-learning on the same gridworld#

Same 4×4 problem as the worked example, but now the agent never sees $P$ or $R$ — it only acts and observes (the environment lives inside step, hidden from the learner):

import numpy as np

rng = np.random.default_rng(0)
N, gamma, alpha, eps = 4, 0.9, 0.1, 0.1
goal = (N - 1, N - 1)
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
Q = np.zeros((N, N, 4))

def step(s, a):                      # the environment: hidden from the agent
    di, dj = moves[a]
    ns = (min(max(s[0] + di, 0), N - 1), min(max(s[1] + dj, 0), N - 1))
    r = 1.0 if ns == goal else 0.0
    return ns, r, ns == goal

for ep in range(5000):
    s, done = (0, 0), False
    while not done:
        a = rng.integers(4) if rng.random() < eps else int(np.argmax(Q[s]))
        ns, r, done = step(s, a)
        target = r + gamma * (0.0 if done else np.max(Q[ns]))
        Q[s][a] += alpha * (target - Q[s][a])
        s = ns

V_learned = Q.max(axis=2); V_learned[goal] = 0.0
print(np.round(V_learned, 3))

Output after 5000 episodes (compare to the value-iteration ground truth):

[[0.59  0.656 0.729 0.81 ]     # top row: matches V* exactly
 [0.531 0.59  0.656 0.9  ]
 [0.13  0.341 0.9   1.   ]     # off the beaten path: still wrong
 [0.    0.    0.324 0.   ]]    # bottom-left corner: never visited ⇒ never learned

This output is the lecture’s best free lesson. Along the corridor the greedy policy actually travels — start, across the top, down the right side — the learned values match $V^*$ to three decimals. In the bottom-left corner they’re badly wrong, and the agent doesn’t care: $\varepsilon$-greedy from a fixed start almost never wanders there, and the optimal policy doesn’t need those values anyway.

Convergence has fine print. Tabular Q-learning provably converges to $Q^*$ — but only if every state–action pair is visited infinitely often and the learning rate decays appropriately (Robbins–Monro conditions: $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$). The corner of the matrix above is what "insufficient visitation" looks like in practice. Exploration isn't a nuisance parameter; it decides which part of the world you learn about — a familiar thought for anyone who has designed an experiment.
Deep dive: on-policy vs. off-policy — SARSA vs. Q-learning
SARSA, the closest sibling, updates toward the action the policy actually takes next: $$ Q(s,a) \leftarrow Q(s,a) + \alpha \big[ r + \gamma\, Q(s', a') - Q(s,a) \big], \quad a' \sim \text{behavior policy}. $$ Q-learning instead uses $\max_{a'} Q(s', a')$ — the value of the greedy action, regardless of what the exploring agent does next. This makes it off-policy: it learns about the optimal policy while behaving according to a different, exploratory one. Two consequences worth remembering:
  • Cliff-walking intuition: SARSA learns values for the exploring policy, so it accounts for its own $\varepsilon$-fraction of random stumbles and prefers safer paths; Q-learning learns the optimal path even while occasionally falling off the cliff during training.
  • Off-policy learning is what allows experience replay — reusing old transitions collected by an outdated policy. Hold that thought: it is one of the two pillars of DQN on the next page.

The wall Q-learning hits#

The table $Q(s, a)$ has one cell per state–action pair. A 4×4 gridworld has 64 cells; a tokamak sensor readout, an Atari screen, or an LLM context has more states than atoms in the universe — and, worse, the agent will never see the same state twice, so a table has no way to generalize from visited states to unvisited ones.

The fix is the same one deep learning applies everywhere: replace the table with a function approximator, $Q_\theta(s, a)$. Doing that naively diverges — and the two tricks that make it work are exactly what define DQN, on the next page.