Chapter 3 · Book pages 125–137

Introduction to Reinforcement Learning

Main read ≈ 18 minutes · dotted words have hover/tap definitions · ▸ boxes go deeper · finish with the test (100% to complete)

The big picture

Supervised learning needs labeled input-output pairs. Reinforcement learning needs none: an agent learns by acting in an environment, receiving rewards as feedback, and adjusting its behavior to maximize cumulative reward — trial and error, not answer keys. This chapter is the toolkit the whole of Part II stands on: the MDP formalism, value functions, TD learning, Q-learning, policy gradients, actor-critic, GAE, and reward shaping — each one ending with "and here is what it means for LLMs."

Why does an LLM book spend a chapter on game-playing math? Because RLHF — the technique that turns a raw text predictor into a helpful assistant — is exactly this chapter applied to language: the policy is the model, an action is a token, and the reward is human preference. PPO and GRPO, the workhorses of chapters 5 and 7, are stop 7 of this chapter with a language model plugged in (and stop 8 is the advantage estimator they train with).

Stop 1 — The MDP: rules of the game

RL's playing field is the Markov Decision Process, a 5-tuple (S, A, P, R, γ): the state space S (all configurations of the environment), the action space A (everything the agent can do), the transition function P(s′|s,a) (the physics: what state follows an action), the reward function R(s,a,s′) (immediate scalar feedback), and the discount factor γ ∈ [0,1] (how much future rewards count versus immediate ones).

The loop never changes: at each step t the agent observes state s_t, picks action a_t from its policy, the environment transitions to s_t+1 ~ P(·|s_t,a_t), the agent receives reward r_t, and this repeats until a terminal state or horizon T.

The agent-environment loop: observe, act, transition, reward — the heartbeat of every RL algorithm (book p. 125–126).

The Markov property makes all of this tractable: the future depends only on the current state, not the history — P(s_t+1|s_t,a_t,s_t−1,a_t−1,…) = P(s_t+1|s_t,a_t). If the state captures everything that matters, you may forget the past.

For an LLM, the mapping is: state = the token sequence so far, action = the next token, transition = append the token (trivially deterministic). The hard part is never the dynamics — it is the reward, which is why stop 9 explains LLM RL is model-free and stop 10 is all about shaping rewards.

Go deeper: the 5-tuple in the book's words

S: all possible environment configurations. A: all actions available to the agent. P(s′|s,a): probability of reaching s′ from s after a. R(s,a,s′): immediate scalar feedback for a transition. γ ∈ [0,1]: how much future rewards are valued relative to immediate ones. γ near 0 makes the agent myopic; γ near 1 makes it far-sighted — and for LLMs the book later fixes γ = 1.0 (all tokens matter equally in a single turn, stop 8). Book §3.1, p. 125–126.

Stop 2 — Policy, value, and the Bellman equations

Five definitions carry the whole field. A policy π(a|s) maps states to action probabilities (deterministic: a = π(s); stochastic: a ~ π(·|s)). The return G_t is the cumulative discounted reward from step t onward:

G_t = Σ_k=0^∞ γ^k r_t+k = r_t + γr_t+1 + γ²r_t+2 + ⋯ (3.1)

The value function V^π(s) = E_π[G_t | s_t = s] is the expected return from a state; the Q-function Q^π(s,a) = E_π[G_t | s_t=s, a_t=a] is the expected return after taking a specific action first; and the advantage A^π(s,a) = Q^π(s,a) − V^π(s) measures how much better that action is than average (3.2–3.4).

The Bellman equations make values recursive — the value of a state is the immediate reward plus the discounted value of wherever you land (3.5–3.6). The optimality versions swap expectation for max: V*(s) = max_a Σ_s′ P(s′|s,a)[R + γV*(s′)], and once Q* is known, the optimal policy is just π*(s) = arg max_a Q*(s,a) (3.7–3.8).

Learn to read A = Q − V and you can read every modern RLHF paper: PPO's clipped objective and GRPO's group baseline are both, at bottom, clever ways to estimate this one quantity. Stop 8 (GAE) is entirely about estimating it well.

Go deeper: the full Bellman recursions

V^π(s) = Σ_a π(a|s) Σ_s′ P(s′|s,a)[R(s,a,s′) + γV^π(s′)] (3.5); Q^π(s,a) = Σ_s′ P(s′|s,a)[R(s,a,s′) + γ Σ_a′ π(a′|s′)Q^π(s′,a′)] (3.6). Optimality: Q*(s,a) = Σ_s′ P(s′|s,a)[R(s,a,s′) + γ max_a′ Q*(s′,a′)] (3.8). The expectation versions average over what the policy would do; the optimality versions assume the best action every time — that single word, max, is the seed of Q-learning in stop 5. Book §3.2, p. 126.

Stop 3 — The taxonomy map

Every RL algorithm answers three questions. Do you model the world? Model-free methods learn a policy or value function directly from experience; model-based methods learn the transition dynamics P(s′|s,a) and can plan ahead — more sample-efficient, but model errors compound. What do you learn? Value-based methods learn Q or V and derive the policy as arg max_a Q(s,a) — great for small discrete action spaces (Atari), hopeless for huge ones. Policy-based methods optimize π_θ(a|s) directly — essential for LLMs, where the vocabulary is 32K–128K actions. Actor-critic combines both: the actor proposes, the critic evaluates. Whose data do you learn from? On-policy learns only from the current policy's fresh data (stable, wasteful); off-policy learns from any policy's data, old or foreign (sample-efficient, harder to stabilize).

The LLM verdict, three stops early: model-free (language dynamics are intractable to model — and don't need modeling), policy-based (a 32K–128K-token action space kills value methods), and mostly on-policy (PPO, GRPO) — with DPO as the off-policy exception. Keep this map; stops 4–10 fill in every cell.

Go deeper: the book's taxonomy with examples

On-policy examples: REINFORCE, PPO, A2C — more stable but less sample-efficient. Off-policy: Q-learning, DQN, SAC — can reuse past experience but harder to stabilize. Value-based struggles with continuous or large action spaces; policy-based is natural for them. PPO for LLMs is actor-critic: a policy network steered by a value network's judgment. Book §3.3, p. 127.

Stop 4 — TD learning: surprise as a signal

Temporal Difference (TD) learning bootstraps: it updates value estimates using other value estimates, without waiting for the episode to end. The engine is the TD error — the gap between what you thought would happen and what actually happened plus what you expect next. The book's driving analogy: you predict a 30-minute drive; 10 minutes in, construction hits and the GPS says 35 minutes remain. The new total estimate is 45 minutes, so the TD error is +15 — pure surprise, and exactly the signal that updates your expectations.

δ_t = R_t+1 + γV(S_t+1) − V(S_t) (3.9) · V(S_t) ← V(S_t) + α·δ_t (3.11)

The first two terms form the TD target — the "better estimate" we move toward — so TD error = TD target − old estimate. δ > 0: better than expected, raise the value; δ < 0: worse, lower it; δ = 0: perfect prediction, nothing to learn. Try it:

Interactive · TD-error calculator (the driving analogy)

Set your predicted drive time, the elapsed time, and the GPS's new remaining estimate — watch δ and the value update.

TD vs Monte Carlo: MC waits for the episode to end and uses the actual return G_t — unbiased but high variance (one trajectory may be unrepresentative). TD updates every step using the estimated γV(s_t+1) — biased (depends on V's accuracy) but far lower variance. TD(λ) interpolates: λ = 0 is pure TD, λ = 1 is pure MC — and that is exactly what GAE does for PPO with λ = 0.95 (stop 8).

Go deeper: multi-step returns

The n-step return G_t⁽ⁿ⁾ = r_t + γr_t+1 + ⋯ + γⁿ⁻¹r_t+n−1 + γⁿV(s_t+n) (3.12) looks n real steps ahead before bootstrapping. n = 1 is one-step TD; n = ∞ is Monte Carlo. TD(λ) averages over all n with exponentially decaying weights instead of picking one (standard result, beyond the book's scope here) — the same trick GAE later applies to advantages. Book §3.4, p. 127–129.

Stop 5 — Q-learning, DQN, and replay buffers

Q-learning is the foundational off-policy, value-based algorithm — it learns the optimal Q* directly, regardless of the policy being followed:

Q(s_t,a_t) ← Q(s_t,a_t) + α [ r_t + γ max_a′ Q(s_t+1,a′) − Q(s_t,a_t) ] (3.13)

Watch it learn on a tiny gridworld:

Interactive · Q-learning gridworld

Step an ε-greedy agent through a 4×4 grid and watch Q-values converge via the update rule above.

Why off-policy: the target uses max_a′ Q(s_t+1,a′) — the best action's value — no matter which action the agent actually took (often a random one, under ε-greedy exploration). The target is always computed under the optimal policy, so Q-learning can learn from replay buffers, demonstrations, or any experience at all. SARSA, the on-policy alternative, uses the action actually taken: r_t + γQ(s_t+1,a_t+1) (3.14).

DQN replaces the Q-table with a neural network and adds two stabilizers. A replay buffer stores transitions e_t = (s_t,a_t,r_t,s_t+1,d_t) and trains on random mini-batches — consecutive steps are highly correlated and neural nets generalize poorly on sequential data, so random sampling makes training approximately i.i.d., prevents catastrophic forgetting, and reuses every transition many times. A target network Q_θ̄ — a frozen copy updated only every C steps (e.g. 10,000) — prevents the moving-target problem where prediction and target shift together and diverge. See the buffer work:

Interactive · Replay-buffer sampler

Stream correlated transitions into a buffer, then sample a mini-batch uniformly or with prioritization by |δ|.

Prioritized Experience Replay (PER) scales sampling probability by TD-error magnitude: transitions that caused massive surprise (high |δ_t|) get replayed more often, accelerating learning 2–3× on Atari benchmarks.

Why LLMs don't do any of this: the action space is the full vocabulary (|A| = 32K–128K) and the state space is every possible token sequence — computing max_a Q(s,a) over 128K actions at every token position is intractable. That dead end is the whole motivation for the next three stops: policy gradients, actor-critic, and GAE.

Go deeper: the DQN training loop, step by step

Per training step: (1) act ε-greedily, annealing ε from 1.0 → 0.01 over the first 1M steps; (2) store (s,a,r,s′,d) in a buffer of capacity ~1M; (3) sample a mini-batch of 32 uniformly; (4) compute target y = r + γ(1−d) max_a′ Q_θ̄(s′,a′) — zero future value if terminal; (5) gradient descent on (y − Q_θ(s,a))², clipping gradients to [−1,1]; (6) every C steps, copy θ̄ ← θ. The loss is the mean squared TD error over the batch (3.15), and no gradient flows through the frozen target (3.16–3.17). Book §3.5, p. 129–130.

Stop 6 — REINFORCE: optimizing the policy directly

Instead of learning values and deriving a policy, policy gradient methods optimize the policy parameters θ directly to maximize expected return J(θ) = E_τ~πθ[R(τ)]. The policy gradient theorem delivers:

∇_θ J(θ) = E_πθ [ Σ_t=0^T ∇_θ log π_θ(a_t|s_t) · G_t ] (3.19)

REINFORCE (Williams, 1992) turns this into an algorithm: sample a full trajectory under π_θ, compute the return G_t at each step, and update θ ← θ + α Σ_t ∇_θ log π_θ(a_t|s_t) · G_t. Read it as reward-weighted maximum likelihood: ∇ log π is the direction that raises the probability of the action taken, and multiplying by G_t means high-reward trajectories get all their actions reinforced, low-reward ones suppressed (negative G_t after a baseline). Supervised learning where the labels are your own actions, weighted by how well they turned out.

Subtracting a baseline b(s_t) — best choice V^π(s_t), turning G_t − V(s_t) into the advantage — keeps the gradient unbiased (E[∇ log π · b(s)] = 0 for any state-dependent baseline) while slashing variance (3.20). REINFORCE's remaining limitations — one-trajectory gradients, no bootstrapping, single-use data, no step-size control — motivate the progression REINFORCE → Actor-Critic → TRPO → PPO.

Go deeper: the 5-step derivation of the policy gradient theorem

(1) Write the objective as an expectation over trajectories: J(θ) = Σ_τ P(τ|θ)R(τ). (2) Differentiate — only the π_θ factors depend on θ, the environment dynamics don't. (3) Apply the log-derivative trick ∇P = P∇ log P to get an expectation again: ∇J = E[∇ log P(τ|θ) R(τ)]. (4) Expand log P(τ|θ) — the log p(s₀) and log p(s_t+1|s_t,a_t) terms vanish under ∇_θ, leaving Σ_t ∇_θ log π_θ(a_t|s_t). (5) By causality, future rewards don't depend on past actions, so each ∇ log π pairs only with the future return G_t. The beauty: the gradient never requires differentiating through the environment. Book §3.6, p. 131–132.

Stop 7 — Actor-critic: two networks, one learner

Actor-critic combines the policy gradient with a learned value function to cut variance while keeping policy optimization's flexibility. The actor π_θ(a|s) proposes actions; the critic V_φ(s) or Q_φ(s,a) judges them, providing a low-variance baseline. The actor updates with the critic's TD-based advantage, the critic trains by minimizing squared TD error:

∇_θJ = E[ ∇_θ log π_θ(a_t|s_t) · Â_t ], Â_t = r_t + γV_φ(s_t+1) − V_φ(s_t) (3.21) · L_critic = E[ (r_t + γV_φ(s_t+1) − V_φ(s_t))² ] (3.22)

Actor-critic: the critic's advantage estimate replaces REINFORCE's noisy raw return (book p. 132).

The evolution to LLM training: REINFORCE (high variance, no bootstrapping — impractical) → A2C/A3C (TD advantage, lower variance, but unbounded step sizes) → TRPO (constrains KL divergence between updates — stable but expensive second-order math) → PPO (clips the policy ratio for TRPO-like stability with first-order optimization — the LLM standard) → GRPO (removes the critic entirely, using group statistics as the baseline — simpler and effective for verifiable rewards).

Go deeper: why the critic helps

REINFORCE's G_t comes from a single full trajectory — thousands of samples needed for a stable gradient. The critic replaces it with a one-step bootstrapped estimate r_t + γV_φ(s_t+1) − V_φ(s_t): lower variance (one random step instead of a whole rollout), some bias (V_φ may be wrong). Trading that bias and variance well is exactly stop 8's subject. Book §3.7, p. 132.

Stop 8 — GAE: the bias-variance dial

Actor-critic needs a good advantage estimate, and the two extremes both hurt: 1-step TD (r_t + γV(s_t+1) − V(s_t)) has low variance but is biased whenever V is wrong; Monte Carlo (G_t − V(s_t)) is unbiased but the sum of many random rewards swings wildly between episodes. Generalized Advantage Estimation (Schulman et al., 2016) blends them with one parameter λ — an exponentially-weighted average of all n-step advantage estimates:

Â_t^GAE = Σ_l=0^T−t (γλ)^l δ_t+l, δ_t = r_t + γV(s_t+1) − V(s_t) (3.23)

Recent TD errors get full weight; distant ones decay by (γλ)^l. Drag λ and watch the blend:

Interactive · GAE λ slider

Slide λ from 0 to 1 over a fixed stream of TD errors and watch the weights, the advantage, and the bias/variance balance shift.

λ = 0: Â_t = δ_t — trust V completely (low variance, biased if V is inaccurate; risk: policy trapped in local minima, never discovering delayed rewards). λ = 1: full Monte Carlo minus baseline (unbiased, extreme variance; risk: destructive gradient updates, training explosions). λ = 0.95 is the standard sweet spot, and for LLMs the book fixes γ = 1.0 — no time discounting, all tokens matter equally in a single turn.

The book's reframing: in supervised learning, bias and variance come from model assumptions; in GAE they come from how much you trust a flawed value network (bias) versus a chaotic environment (variance). Choosing λ ∈ [0.95, 0.99] minimizes the total mean squared error of the advantage estimate.

Go deeper: diagnostics for tuning λ

High-variance indicators: policy entropy drops precipitously while the value function's explained variance goes highly negative or erratic → noisy policy updates; remedy: lower λ to smooth targets. High-bias indicators: training stabilizes early but the agent never discovers complex delayed-reward sequences → bootstrapping hides long-horizon dependencies; remedy: raise λ toward 1.0 to expose the policy to real downstream signals. Book §3.8, p. 133–135.

Stop 9 — On-policy vs off-policy, and why LLM RL is model-free

The comparison that decides your training bill. On-policy learns only from the current policy's data: after each update the old data is invalid and must be regenerated — low sample efficiency, high stability. Off-policy learns from any policy's data, reusing it many times — high sample efficiency, but distribution mismatch can diverge. For RLHF: PPO and GRPO are on-policy (generate responses, compute advantages, update, discard, regenerate — which is why generation is 60% of compute). DPO is off-policy (a fixed preference dataset, no generation during training — much cheaper, but the data goes stale as the policy drifts). Online DPO is the hybrid: fresh on-policy generation with DPO's supervised-style loss.

PPO's cleverness: the clip ratio r = π_new/π_old squeezes multiple gradient steps (4 epochs) out of one batch of on-policy data — making PPO "slightly off-policy" in a controlled way. Chapter 5 is entirely this trick.

Model-based vs model-free: model-based methods (MuZero, Dreamer, AlphaGo) learn P̂(s′|s,a) and plan in imagination — sample-efficient but model errors compound. LLM RL is fundamentally model-free: language dynamics are trivial (append a token — deterministic), so a world model adds nothing. What is hard is the reward — predicting what humans prefer. The RLHF reward model predicts preference, but it is used as a reward signal, not for planning.

Go deeper: the comparison tables

On-policy (REINFORCE, PPO, A2C, GRPO): consistent data distribution, more stable, data used once. Off-policy (Q-learning, DQN, SAC, DPO): replay-buffer reuse, can diverge from distribution mismatch. Model-free (PPO, DQN, SAC): no model bias, must experience everything. Model-based: can simulate futures, high sample efficiency, best when dynamics are simple and efficiency matters. Book §3.9–3.10, p. 135–136.

Stop 10 — Reward shaping: dense rewards without the hacking

Reward shaping modifies the environment's reward to turn a sparse signal (feedback only at final completion) into a dense one (intermediate signals), accelerating convergence: R′(s,a,s′) = R(s,a,s′) + F(s,a,s′) (3.26). The danger is reward hacking: a naive F invites loopholes — a navigation agent rewarded for intermediate landmarks learns to loop around one checkpoint forever without reaching the goal; an LLM rewarded for "sounding confident" learns to always open with "Absolutely!" regardless of accuracy.

Potential-Based Reward Shaping removes the danger by constraining F to the difference of a scalar potential function Φ across states:

F(s,a,s′) = γΦ(s′) − Φ(s) (3.27) ⇒ R′ = R + γΦ(s′) − Φ(s) (3.28)

PBRS comes with a theorem. Policy invariance: the optimal policy under R′ is identical to the one under R — shaping cannot introduce sub-optimal behavior. Loop immunity: any cycle returns to its starting state with net potential change exactly zero (Φ(s) − Φ(s) = 0), so loops cannot be farmed. And the payoff: denser gradient signals converge 5–50× faster in sparse-reward environments.

This closes the loop on the chapter's LLM story. The reward is the one hard, hackable component of language RL — chapter 9's reward models are learned Φ-like signals, and every RLHF failure you will read about (sycophancy, verbosity inflation) is reward hacking wearing a new costume. The checkpoint-looper and the "Absolutely!" model are the same bug.

Go deeper: why the telescope collapses

Sum the shaping terms along a trajectory and they telescope: (γΦ(s₁) − Φ(s₀)) + (γ²Φ(s₂) − γΦ(s₁)) + ⋯ — every intermediate Φ cancels, leaving only −Φ(s₀) plus the discounted final potential. Progress toward genuinely higher-potential states is rewarded; sideways wandering nets zero. That is the mechanical reason behind both policy invariance and loop immunity (the telescoping derivation itself is standard RL canon, beyond the book's scope). Book §3.11, p. 136–137.