Deep reinforcement learning

Search (previous chapter) knew the whole map. Reinforcement learning does not: an agent acts, the environment responds with a new state and a scalar reward, and the agent must improve from that feedback alone — no labels, no gradient of the world, consequences only. This chapter builds the full route from the formalism to the algorithms you can train in the playground: MDPs → Bellman equations → tabular methods (which you’ll watch solve a gridworld live) → deep value-based methods (DQN and its fixes) → policy gradients (REINFORCE to PPO).

The MDP: five objects and a goal

A Markov decision process is $(\mathcal S, \mathcal A, P, R, \gamma)$: states, actions, transition kernel $P(s' \mid s, a)$, reward function, and a discount $\gamma \in [0, 1)$. The Markov property — the future depends on the past only through the current state — is what makes the mathematics go; “state design” in practice is mostly the art of making it approximately true (Pong’s paddle needs the ball’s velocity in its state, which is why the playground’s Pong observation includes the previous frame).

A policy $\pi(a \mid s)$ is the agent’s behaviour. The objective is the expected return — discounted cumulative reward:

Discounting is doing two jobs at once: economically it values sooner over later, and mathematically it makes the infinite sum finite and — as you are about to see — makes the whole theory a contraction. The practical intuition worth keeping: $\gamma$ sets an effective horizon of roughly $1/(1-\gamma)$ steps ($\gamma = 0.99 \Rightarrow$ ~100 steps of lookahead).

Value functions and the Bellman equations

Two functions organize everything. The state value and action value under $\pi$:

Peel one step off the return ($G_t = r_{t+1} + \gamma G_{t+1}$) and take expectations — the Bellman expectation equation:

For the best possible behaviour, replace the average over actions with a max — the Bellman optimality equation:

Why does iterating this converge? Define the backup operator $(\mathcal T V)(s) = \max_a \sum_{s'} P\,[R + \gamma V(s')]$. For any two value functions,

— $\mathcal T$ is a $\gamma$-contraction, so by Banach’s fixed-point theorem it has a unique fixed point ($V^\ast$) and repeated application converges to it geometrically from any start. This is the optimization module’s linear-convergence story wearing RL clothes, and it is not abstract — the widget below prints the contraction as a shrinking max-delta, sweep by sweep:

Learning without the model: TD and Q-learning

Value iteration needed $P$ and $R$. Q-learning replaces the expectation with a sampled transition $(s, a, r, s')$ and a step toward the sampled target — temporal-difference learning:

Three structural facts, each of which returns at deep scale:

• It is off-policy: the max in the target evaluates the greedy policy while the agent behaves ε-greedily — learning about the best policy from imperfect behaviour. (SARSA, its on-policy sibling, uses the actually taken next action.)
• It is bootstrapping: the target contains the current estimate $Q(s', \cdot)$ — learning a guess from a guess. That is what makes it sample-efficient, and what makes it dangerous later.
• With decaying $\alpha$ (the Robbins–Monro conditions — the SGD lesson, again) and sufficient exploration, tabular Q-learning converges to $Q^\ast$.

Going deep: DQN and why it needs its tricks

Pac-Man’s state space (a stack of image planes) has no table. Replace $Q(s,a)$ with a convolutional network $Q_\theta$ and minimize the squared TD error:

Naively this diverges, for reasons the theory names precisely — the deadly triad of function approximation + bootstrapping + off-policy training. DQN (2015) made it work with two stabilizers, both visible in that loss:

• Experience replay $\mathcal D$: store transitions, train on random minibatches. This breaks the temporal correlation of consecutive frames (SGD’s unbiased-sample assumptions — the noise-ball lesson — quietly required i.i.d.-ish batches) and reuses data.
• Target network $\theta^-$: the bootstrap target uses a frozen, periodically updated copy. Without it you are regressing toward a target that moves with every gradient step — a feedback loop; with it, the target holds still long enough to be learned.

Two refinements complete the playground’s value-based family:

Double DQN. The same max that selects the target action also evaluates it, and a max over noisy estimates is biased upward: $\mathbb{E}[\max_a \hat Q(a)] \ge \max_a \mathbb{E}[\hat Q(a)]$. Systematic overestimation compounds through bootstrapping. The fix decouples the two roles — select with the online net, evaluate with the target net:

Dueling architecture. Decompose $Q(s,a) = V(s) + A(s,a)$ with two heads sharing the conv trunk (centering $A$ to make the split identifiable). In states where actions barely matter — most of Pac-Man’s corridor frames — the $V$ head learns the state’s worth once, instead of separately per action; the advantage head spends its capacity only where actions differ.

The other family: policy gradients

Value-based methods derive the policy from $Q$. The policy-gradient family parameterizes the policy $\pi_\theta$ directly and ascends $J(\theta)$ — necessary when actions are continuous, and often better-behaved when the optimal policy is stochastic. The engine is the policy gradient theorem, whose derivation is one identity — the score/likelihood-ratio trick $\nabla_\theta \pi_\theta = \pi_\theta \nabla_\theta \log \pi_\theta$ — applied to the trajectory distribution:

Read it as a reweighted classifier gradient: increase the log-probability of every action taken, in proportion to the return that followed. No gradient of the environment appears — the trick’s entire point.

REINFORCE is this, verbatim, with Monte-Carlo returns — unbiased and viciously high-variance (a whole game’s worth of noise credits every action). The variance program has three steps, each a named algorithm:

1. Baselines. Subtracting any state-dependent $b(s)$ from $G_t$ leaves the gradient unbiased (the subtracted term has expectation zero — exercise 4) but can slash variance. The best simple choice is $b(s) = V(s)$, making the weight the advantage $A(s,a) = Q(s,a) - V(s)$: “was this action better than typical here?”
2. Actor–critic (A2C). Learn $V_\phi$ (the critic) alongside $\pi_\theta$ (the actor); estimate advantages by bootstrapped TD instead of full returns. GAE interpolates the spectrum with $\lambda$: one-step TD (biased, low variance) at $\lambda = 0$, Monte-Carlo (unbiased, high variance) at $\lambda = 1$ — the bias–variance dial of RL.
3. PPO. Policy gradients are valid only near the sampling policy; a large step can collapse performance unrecoverably (the data you would need to recover comes from the policy you just broke). PPO reuses each batch for several epochs while clipping the incentive to stray, via the ratio $\rho_t = \pi_\theta(a_t \mid s_t) / \pi_{\theta_{\text{old}}}(a_t \mid s_t)$:

Read the clip: once the ratio moves more than $\epsilon$ (~0.2) in the profitable direction, the min switches to the clipped branch and the gradient vanishes — no more incentive to push that sample further. It is trust-region thinking implemented with a min and a clamp, and it is the modern default (and, next chapter, the engine under RLHF).

Choosing, and reading the training curves

Both families inherit everything from this track’s earlier modules — Adam’s per-coordinate scaling, the noise-ball’s schedule logic, non-convex landscapes — plus RL’s own pathologies: non-stationarity (the data distribution changes as the policy improves; yesterday’s replay buffer is a slightly foreign country) and reward hacking (the agent optimizes the reward you wrote, not the one you meant — you built the miniature version in the widget when the living-reward slider changed the policy’s risk appetite). When your playground curve is flat: check exploration (ε, entropy) before touching the learning rate. When it collapses mid-training: suspect the step size or, for PPO, too many epochs per batch — the clipped objective only removes the incentive to stray; it does not forbid straying.

Exercises