Reinforcement
Learning

Why Markov The Markov property — the future depends only on the present state, not on history — is what makes RL tractable. Without it, value functions wouldn't be well-defined on states alone; you'd have to condition on the entire trajectory, and everything that follows would collapse.

Why γ<1 The discount factor serves two purposes. Mathematically, it makes the Bellman operator a contraction, guaranteeing a unique fixed point and geometric convergence. Behaviourally, it encodes how much the agent values the distant future; $\gamma \to 1$ gives a far-sighted agent, $\gamma \to 0$ a myopic one.

V vs Q Both encode the same object, but answer different questions. $V(s)$ asks "how good is this state?"; $Q(s,a)$ asks "how good is this action in this state?" — and the latter is what you need for model-free control, because you can choose actions without simulating transitions.

Two problems RL really splits into two tasks: prediction (given $\pi$, find $V^\pi$) and control (find $\pi^*$). Every algorithm that follows is either one or the other — or, like policy iteration, both alternating.

Why it converges The Bellman optimality operator $T$ is a $\gamma$-contraction in the sup-norm: $\|TV - TV'\|_\infty \le \gamma \|V - V'\|_\infty$. By the Banach fixed-point theorem, repeatedly applying $T$ from any starting $V$ converges to the unique fixed point $V^*$ at a geometric rate $\gamma^k$.

One sentence Keep applying the Bellman optimality operator until the value function stops changing; then read off the greedy policy.

Cousin: policy iteration Alternates policy evaluation (solve the linear system for $V^\pi$ exactly) with policy improvement (act greedily w.r.t. $V^\pi$). Fewer iterations than value iteration but each one is heavier. In practice, modified policy iteration — a few sweeps of evaluation between improvements — often beats both.

Limitation Requires the model $(P, R)$. Everything below (SARSA, Q-learning, …) drops that requirement at the price of having to sample.

The name The letters spell the transition tuple used in the update: $(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})$. You need all five before you can apply the update, which is why SARSA is naturally online and step-by-step.

Why on-policy The bootstrap target uses $a_{t+1}$ actually sampled from the current behaviour policy (e.g. $\varepsilon$-greedy). So SARSA learns $Q^\pi$ for the policy being followed — including its exploration. Under GLIE schedules (Greedy in the Limit with Infinite Exploration), $\pi$ converges to $\pi^*$ and $Q$ to $Q^*$.

Cliff-walking The textbook demonstration: on a gridworld with a cliff, SARSA learns that $\varepsilon$-greedy exploration sometimes pushes it off the edge, so it takes a safer path further from the cliff. Q-learning (below) learns the optimal path along the cliff edge and falls off regularly during training.

When to prefer it When exploration itself is costly — learning on real hardware, safety-critical settings — SARSA's pessimism about its own randomness is a feature, not a bug.

History Introduced by Watkins in his 1989 Cambridge PhD thesis, Q-learning was the first proven off-policy TD control algorithm — a small equation with an outsized legacy.

Why off-policy The target $r + \gamma \max_{a'} Q(s', a')$ evaluates the greedy policy regardless of how you actually explored. So you can follow $\varepsilon$-greedy (or anything else with sufficient coverage) and still converge to $Q^*$, provided every $(s,a)$ is visited infinitely often and step sizes satisfy Robbins–Monro conditions ($\sum \alpha = \infty$, $\sum \alpha^2 < \infty$).

Maximisation bias Because $\mathbb{E}[\max_a X_a] \ge \max_a \mathbb{E}[X_a]$, the $\max$ over noisy $Q$-estimates is systematically optimistic. In small tabular problems this is a rounding error; in deep RL it becomes a structural pathology that Double DQN was invented to fix.

One sentence Learn the value of behaving greedily, even while you don't.

The breakthrough DQN's contribution wasn't "combine Q-learning with a neural net" — that had been tried. It was discovering how to make it stable. The 2015 Nature paper achieved superhuman play on 49 Atari games from pixels alone, using a single architecture and the same hyperparameters.

The deadly triad Function approximation + bootstrapping + off-policy learning can cause value estimates to diverge. DQN doesn't solve this in theory; it tames it in practice with two engineering tricks.

Replay buffer Uniformly sampling past transitions breaks the temporal correlation between consecutive samples. Without it, SGD sees a sequence of highly correlated mini-batches (all from the same episode), violating the i.i.d. assumption and causing catastrophic forgetting as the distribution shifts.

Target network If you bootstrap off the live network, changing $Q_\theta$ immediately moves the target $Q_\theta$ you're regressing toward — you're chasing your own tail. Freezing $\theta^- \leftarrow \theta$ every $N$ steps gives the optimizer a stationary target for the span of an update cycle.

Descendants Double DQN, Prioritised Replay, Dueling, Noisy Nets, Distributional (C51/QR-DQN), and n-step returns — all combined in Rainbow, which is still a strong baseline for discrete-action deep RL.

The diagnosis Van Hasselt (2010, 2015) showed that DQN's $\max$ systematically overestimates: if each $Q(s', a)$ has mean-zero noise $\varepsilon_a$, then $\max_a (Q^* + \varepsilon_a)$ is upward-biased because the $\max$ selectively picks out the luckiest estimate. That bias propagates through bootstrapping.

The fix Decouple action selection from action evaluation. Use one network to pick the arg-max action, and a different network to estimate its value. Since the two networks have independent noise, the evaluation of the chosen action is no longer conditioned on it looking lucky.

Why it's almost free DQN already has two networks ($\theta$ online, $\theta^-$ target). Double DQN simply reuses them: online selects, target evaluates. No new parameters, no new hyperparameters, often dramatically more stable learning.

When it matters most Environments with many actions, sparse rewards, or long bootstrapping chains — exactly the settings where DQN's optimism compounds badly.

The observation Wang et al. (2016) noticed that in many states, the choice of action barely matters — standing still in a Breakout frame when the ball is far away has similar consequences regardless of which action you pick. Yet vanilla DQN must learn $Q(s, a)$ separately for every action, wasting capacity.

The decomposition Split the network: one head predicts $V(s)$ (how good is this state?), another predicts $A(s, a)$ (how much better is each action than average?). Then $Q(s, a) = V(s) + A(s, a)$.

The identifiability trick The decomposition is not unique: adding a constant to $V$ and subtracting it from $A$ gives the same $Q$. Subtracting the mean advantage, $A(s,a) - \tfrac{1}{|\mathcal{A}|}\sum_{a'} A(s, a')$, pins down $V$ as the average-action value and makes the decomposition unique up to the gauge.

Why it helps The $V$ stream receives gradient on every transition, not only on transitions taking action $a$. Sample efficiency improves markedly in environments with many actions or long periods where action choice is irrelevant.

Policy gradient theorem The gradient of expected return equals the expectation of the score function times the return: $\nabla_\theta J = \mathbb{E}[\nabla_\theta \log \pi_\theta(a|s) \cdot G]$. This is the log-derivative trick, and it's beautiful because it lets you estimate a gradient through a stochastic, possibly non-differentiable environment — you only need gradients of your own policy.

Why baselines are free Because $\mathbb{E}_a[\nabla_\theta \log \pi_\theta(a|s)] = 0$ for any fixed $s$, subtracting any function $b(s)$ from the return leaves the gradient unbiased but can dramatically reduce variance. This is the seed of every actor-critic method that follows.

Why it's unreliable REINFORCE is unbiased but its variance scales with trajectory length and stochasticity — sample-inefficient, and often needs very careful reward scaling and baselines to make progress. It works but rarely wins on standard benchmarks; its descendants do.

One sentence Push up the log-probability of actions whose returns beat the baseline; push down the rest.

Bias–variance trade REINFORCE uses the full Monte-Carlo return $G_t$ (unbiased, high variance). Replacing it with the one-step advantage $r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$ introduces bias (the critic is wrong) but slashes variance (you no longer depend on every future reward). Actor-critic methods live on this spectrum.

GAE Generalised Advantage Estimation interpolates between $n$-step returns via a parameter $\lambda \in [0, 1]$: $\hat A^{\text{GAE}(\lambda)}_t = \sum_{k=0}^{\infty} (\gamma\lambda)^k \delta_{t+k}$ where $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$. $\lambda = 1$ recovers Monte-Carlo, $\lambda = 0$ the 1-step TD. $\lambda \approx 0.95$ is a common sweet spot.

Why entropy bonus Without the $-\beta H[\pi]$ term, the policy tends to collapse deterministically too quickly — locking in whichever action looked best early and refusing to explore. The entropy bonus keeps the policy soft until enough evidence has accumulated.

A2C vs A3C A3C (Mnih 2016) ran many actors asynchronously on CPU, each updating shared parameters. A2C is the synchronous version: wait for all actors to produce a batch, then update on GPU. A2C is usually as fast in wall-clock and far easier to debug.

The central trick Instead of enforcing a KL constraint exactly, clip the probability ratio so that large policy updates can't produce outsized gradients. When $A_t > 0$ and the ratio $r_t$ has climbed past $1+\epsilon$, the gradient is zero — no incentive to push further. Symmetric treatment for $A_t < 0$ and $r_t < 1-\epsilon$.

Why it approximates a trust region Clipping caps the per-sample influence of any transition on the gradient, which in aggregate bounds how far the policy can move per epoch. It's a crude but remarkably effective substitute for TRPO's KL ball, using only first-order SGD.

The min is doing work The $\min$ in $\min(r_t A_t, \mathrm{clip}(r_t) A_t)$ forms a pessimistic lower bound on the surrogate objective. When clipping would make the objective larger than the unclipped version, the $\min$ rejects the clip — so you're only ever conservative, never optimistic.

In practice Combined with GAE-$\lambda$ for advantages, a shared or separate value network, and modest entropy bonus. Standard recipe: collect a batch, do ~10 epochs of mini-batch SGD on it, discard it, repeat. Robust across hyperparameters in a way few RL algorithms are.

Beyond games PPO is the on-policy workhorse behind most large-scale RL, including RLHF for LLMs. Its simplicity, stability, and tolerance for distributed training made it the default.

The problem Q-learning in continuous action spaces is awkward: you can't tabulate $Q(s, a)$ over uncountably many $a$, and the $\max_a Q(s, a)$ step becomes an inner optimisation problem at every transition. DDPG sidesteps this by learning a deterministic policy $\mu_\theta(s)$ and treating it as "the argmax."

Deterministic Policy Gradient Silver et al. (2014) showed that for deterministic policies, the policy gradient has a clean form: $\nabla_\theta J = \mathbb{E}\big[\nabla_a Q_\phi(s, a)\big|_{a=\mu_\theta(s)} \nabla_\theta \mu_\theta(s)\big]$. You pass gradients from $Q$ through the action, into the actor — essentially asking "how should I move the action to make $Q$ go up?"

DQN tricks, ported Off-policy replay buffer, plus soft target updates $\theta^- \leftarrow \tau\theta + (1-\tau)\theta^-$ with $\tau \approx 0.005$ — a continuous Polyak averaging that's gentler than DQN's hard copies.

Exploration A deterministic policy doesn't explore on its own, so noise is added externally: originally Ornstein–Uhlenbeck (temporally correlated, good for physics), in practice often just Gaussian.

Caveat DDPG is notorious for being unstable and hyperparameter-sensitive. Q-values tend to explode, and seemingly minor hyperparameter changes can break it. TD3 (next) fixes most of this with surgical precision.

Diagnosis Fujimoto, van Hoof & Meger (2018) diagnosed three specific failure modes in DDPG and patched each. The result is the same sample-efficiency regime with dramatically better stability.

1. Clipped double-Q DDPG inherits Q-learning's overestimation bias, which is worse in continuous control because the actor actively exploits Q-errors. TD3 maintains two critics $Q_{\phi_1}, Q_{\phi_2}$ and uses $\min(Q_{\phi_1^-}, Q_{\phi_2^-})$ in the target — a pessimistic estimate, an analogue of Double Q-learning for continuous actions.

2. Target-policy smoothing The deterministic actor tends to find sharp peaks in the critic that are artifacts of function approximation. Adding clipped Gaussian noise to the target action before evaluating $Q$ acts as a regulariser: the critic must be smooth in a neighbourhood of $\mu_{\theta^-}(s')$, which it always is if the underlying $Q$-function is.

3. Delayed policy updates A bad critic produces a bad policy gradient. Updating the actor (and targets) only once every $d$ critic steps — typically $d = 2$ — lets the critic catch up before the actor exploits its errors. Simple, almost free, very effective.

Takeaway The same tricks that stabilise DQN (double estimators, target smoothing, delayed targets) are needed in continuous control too, sometimes even more urgently.

Maximum entropy RL Instead of maximising just expected return, SAC (Haarnoja 2018) maximises return plus the policy's entropy: $J(\pi) = \sum_t \mathbb{E}\big[r_t + \alpha \, H(\pi(\cdot | s_t))\big]$. The optimal policy is deliberately stochastic wherever multiple actions are near-equally good.

Why entropy is fundamental It solves two problems at once. (1) Exploration is baked into the objective, not bolted on as noise. (2) The policy becomes more robust to perturbations — if two actions have nearly the same $Q$, both get probability mass, so small Q-errors don't cascade into catastrophic deterministic choices.

Soft Bellman equation Under max-entropy RL, the optimal policy turns out to be a Boltzmann distribution of the soft $Q$: $\pi^*(a|s) \propto \exp(Q^*(s, a)/\alpha)$. This is mathematically elegant — it connects RL to energy-based models and to the softmax that's everywhere in ML.

Reparameterisation trick SAC's actor outputs parameters of a squashed-Gaussian ($\tanh$ of a Normal sample). Using $a = \tanh(\mu + \sigma \cdot \epsilon)$ with $\epsilon \sim \mathcal{N}(0, I)$ lets gradients flow through the sample — far lower variance than the score function estimator.

Automatic $\alpha$ Hand-tuning the temperature $\alpha$ is brittle. The second SAC paper learns it by dual descent on the constraint $\bar H(\pi) \ge H_{\text{target}}$ — choosing a target entropy (e.g. $-|\mathcal{A}|$) is far more intuitive than choosing $\alpha$ directly. This is why modern SAC "just works" out of the box.

Status SAC has largely displaced DDPG/TD3 as the default continuous-control algorithm: comparable or better sample efficiency, higher asymptotic performance, and vastly more stable across tasks.

Two kinds of RL Sutton distinguishes direct RL (update $Q$ from real experience) and indirect RL (update $Q$ from simulated experience via a model). Dyna-Q does both, on the same $Q$-table, in a tight loop.

Why planning helps Each real transition is expensive (environment step); each planning step is cheap (model lookup). With $n = 50$ planning steps per real step, you get effectively 51× the $Q$-updates per environment interaction — an enormous sample-efficiency multiplier.

The model is trivial In the tabular case, the model is a dictionary — memorising each observed $(s, a) \to (r, s')$. This only works because tabular Dyna-Q assumes deterministic dynamics; for stochastic environments you'd store counts or distributions.

Dyna-Q+ Adds an exploration bonus $\kappa \sqrt{\tau(s,a)}$ where $\tau$ is time since last visit — encourages revisiting stale parts of the model, which matters in non-stationary environments where the true dynamics drift.

Legacy Dyna-Q is the conceptual ancestor of everything that follows. Replace "lookup table model" with "neural network model" and "tabular $Q$" with "policy gradient," and you have MBPO. The template hasn't changed in 35 years.

Four phases per iteration (1) Selection — descend the tree via UCB until reaching a leaf. (2) Expansion — add a new child node. (3) Simulation — roll out to a terminal state (or use a value estimator). (4) Backup — propagate the outcome up the visited path, updating $N$ and $\hat Q$.

Why UCB The bonus $c\sqrt{\ln N / N(a)}$ is the classical upper confidence bound from multi-armed bandits. It decays as an action is tried more, so the search eventually focuses on the best moves, but it keeps under-visited branches alive — giving asymptotic optimality guarantees under mild conditions.

Asymmetric search MCTS grows the tree deeper in promising directions and barely visits bad ones — unlike minimax with alpha-beta, which explores more uniformly. This is exactly what made it practical for Go, where the branching factor (~250) crushes exhaustive search.

AlphaGo and beyond AlphaGo combined MCTS with two neural networks: a policy net providing $P(a|s)$ as a search prior, and a value net replacing expensive rollouts at the leaves. AlphaZero simplified further — one network outputting both $(\pi, v)$, trained purely from self-play with no human data. MuZero (below) takes the final step: learn the model too.

When to use MCTS shines when you have a simulator (board games, puzzles, physics) and moderate-to-large branching factors. It's naturally discrete — continuous action spaces require progressive widening or clever parameterisations.

Two uncertainties Aleatoric uncertainty (inherent stochasticity) is captured by each network outputting a distribution, not a point. Epistemic uncertainty (insufficient data) is captured by the disagreement between ensemble members. Good planning needs both; ignoring either leads to over-confidence.

Why trajectory sampling A naive approach — average predictions across ensemble members at every step — collapses epistemic uncertainty and produces over-confident plans. TS-$\infty$ keeps each particle bound to a single ensemble member for its whole rollout, so trajectories diverge when the ensemble disagrees, correctly representing the uncertainty.

CEM in one paragraph Cross-Entropy Method: sample $N$ action sequences from a Gaussian, score each by running it through the model, keep the top $k$ elites, refit the Gaussian to them, repeat. A gradient-free optimiser that handles noisy, non-differentiable objectives — ideal when the objective goes through a learned model.

Sample efficiency Chua et al. (2018) showed PETS matches SAC's asymptotic performance on standard benchmarks in 10–100× fewer environment steps. The price: each real step runs CEM through the ensemble, which is computationally heavy.

Limitation Pure planning, no learned policy — every action requires running CEM from scratch. Fine for low-dimensional control, painful for high-frequency or vision-based tasks.

The core insight Model error compounds with rollout length. A 1% per-step error becomes a ~40% error after 50 steps. Long model rollouts drift off the data manifold into regions where the model was never trained — and the policy happily exploits those hallucinations, breaking training.

Branched rollouts Instead of long rollouts from the initial state, MBPO starts rollouts from real states in the replay buffer and runs them for only $k$ steps (typically 1–5). You stay close to the data manifold, generate many short rollouts instead of a few long ones, and the error bound stays tight.

SAC underneath The policy optimiser is SAC. MBPO fills a separate buffer with $k$-step model rollouts; SAC samples a mixture (often 95% model / 5% real) from the two buffers. Because SAC is off-policy, it doesn't care that the synthetic data wasn't collected by the current policy.

Schedule The rollout horizon $k$ is typically annealed upward during training: as the model improves and the policy stabilises, longer rollouts become trustworthy — and more useful.

Result Janner et al. (2019) matched SAC's asymptotic performance on MuJoCo benchmarks in ~5× fewer environment steps, with far less compute than PETS. MBPO became the go-to template for pairing learned dynamics with modern off-policy RL.

Learn once, dream forever Train a world model on collected experience; then do all policy learning in the latent imagination. Sample $h_0$ from the replay buffer, unroll the learned dynamics in latent space for $H$ steps, compute imagined rewards and values, backprop through everything. No environment steps wasted on policy gradient noise.

Why the split latent The deterministic $h_t$ carries long-term information (a GRU state); the stochastic $z_t$ captures per-step uncertainty. Together they're expressive enough to model complex pixel environments, but compact enough to roll out hundreds of imagined steps cheaply.

Actor-critic in imagination Two small MLPs: an actor $\pi_\psi(a \mid h, z)$ and a value $v_\xi(h, z)$. Because the latent dynamics are fully differentiable, the policy gradient can flow back through the imagined trajectory — no score function estimator needed, variance is drastically lower than model-free policy gradient.

Dreamer's evolution V1 (2020) — pixel control suite. V2 (2021) — replaced Gaussian latents with categorical ones, huge stability gains, mastered Atari. V3 (2023) — added symlog transforms, tuned hyperparameters; the same network and settings solved 150+ tasks from Atari to Minecraft, including the first agent to mine diamonds from scratch.

Why it matters Dreamer is today's reference point for sample-efficient learning from pixels. The paradigm — learn a latent dynamics model, then do all RL in imagination — has become the dominant template for model-based deep RL.

AlphaZero's missing piece AlphaZero still needed to know the rules of the game — its dynamics function was provided by the environment. MuZero learns an implicit model: $g_\theta$ predicts next latent states and rewards without ever reconstructing observations. No rules, no simulator, no hand-coded transitions.

Value-equivalent modelling This is MuZero's key philosophical break. Dreamer learns a model that predicts what the next frame looks like. MuZero learns a model that predicts only what matters for planning — reward, value, and policy — and nothing else. The latent space has no obligation to correspond to physical state; it only has to support good predictions of these three quantities.

Why it scales The same architecture mastered Go (perfect information, huge branching), Atari (stochastic, pixel-based), chess, and shogi — domains that previously each required bespoke, hand-crafted models. The clean separation into $(h, g, f)$ lets each function focus on one narrow task.

MCTS in latent space Planning unrolls $g_\theta$ through the search tree, using $f_\theta$ at every node for the policy prior and value estimate. Policy improvement comes from the MCTS visit distribution $\hat\pi$ being a better policy than the raw $\pi^0$ output by the network — so the network is then trained to match $\hat\pi$, a form of policy distillation.

Descendants EfficientZero (Ye 2021) matched MuZero's Atari performance with 500× less data by adding self-supervised latent consistency. Stochastic MuZero handles stochastic environments. Sampled MuZero handles continuous actions. The template continues to expand.

Bias–variance dial Small $n$: heavy bootstrapping, biased by the current value estimate but low variance because the target depends on few random transitions. Large $n$: less bootstrapping, unbiased in expectation but high variance because the target depends on many stochastic rewards. The best $n$ is problem-dependent — there's no free lunch.

Why it matters In practice, intermediate $n$ (typically 4–20) often dominates both endpoints. TD(0) propagates information one step at a time and can be agonizingly slow on long horizons; Monte Carlo has to wait for episode end and suffers from variance.

Delay The update for state $s_t$ can't be computed until $n$ more steps have been observed — you have to delay the update until $t + n$. This is why online implementations need a small FIFO buffer of recent transitions.

Gateway drug n-step TD is the conceptual stepping stone to TD(λ): instead of picking one value of $n$, average them all with exponentially decaying weights.

The equivalence The forward and backward views produce (approximately) the same updates — they're two ways to describe the same algorithm. Forward says "look ahead and average n-step returns"; backward says "propagate this step's error back through a decaying memory of visited states." The backward view is what you actually implement, because it's online and local.

Credit assignment Traces solve RL's hardest problem — which earlier action caused this reward? — by keeping a fading record of recent states. When a reward finally arrives, every state with non-zero trace shares the credit, weighted by how recently it was visited.

Two trace flavours Accumulating traces add 1 each visit (can exceed 1 if a state is re-visited). Replacing traces clip to 1 — often more stable in tabular settings, especially with revisits during exploration.

Why it's fast Information propagates backward by $\gamma\lambda$ per step — so after $n$ steps a reward has already updated states $n$ back. Compared to TD(0), where each value update takes one bootstrap step to propagate one hop, traces give a qualitative speedup in long-horizon problems.

Caveat The backward-view update is approximately, not exactly, the forward-view update online — they only match at the end of an episode or offline. True Online TD(λ) (below) fixes this.

SARSA + traces Exactly SARSA's on-policy update, but with an eligibility trace over state–action pairs instead of just states. Reward signal propagates back along the entire recent trajectory in one update, not one step at a time.

Mountain Car demo The textbook case. Vanilla SARSA struggles here — reaching the flag requires a long sequence of correct actions, and reward only arrives at the end. With $\lambda \approx 0.9$, traces propagate that terminal reward back through the entire climb, and learning is roughly an order of magnitude faster.

Why on-policy is natural here Because the trace records actions actually taken, and the TD target uses the next actually chosen action, SARSA(λ) is internally consistent — no correction terms needed, unlike off-policy $Q(\lambda)$ below.

Function approximation With linear function approximation, traces become vectors of the same shape as the weights: $\vec e_t = \gamma\lambda \vec e_{t-1} + \vec \phi(s_t, a_t)$. With non-linear nets, traces are more awkward — modern deep RL uses GAE (below) to get the same effect in a batched way.

The tension Q-learning is off-policy: it targets the greedy policy while behaving $\varepsilon$-greedily. Traces are a way of propagating n-step returns along the trajectory you actually took. These are at odds — any n-step segment containing an exploratory action represents behaviour, not the greedy target policy, so propagating rewards back through it is biased.

Watkins's fix Cut the trace whenever a non-greedy (exploratory) action is taken. From that point on, the next trace segment starts fresh. This is provably sound but wasteful — traces are often cut before they can do much work, especially under high $\varepsilon$.

Peng's Q(λ) An alternative that never cuts traces — uses a mixed-policy target. It usually works better empirically but has no formal convergence guarantees. The practical divide between "theoretically sound but limited" and "works well but fragile" runs right through this algorithm.

Modern heirs Tree Backup (Precup 2000) handles off-policy multi-step without importance sampling. Retrace(λ) (Munos 2016) uses clipped importance ratios — safer than naïve IS, more data-efficient than Watkins. V-trace (IMPALA, 2018) applies the same idea at massive scale. All descend from the same problem Watkins identified.

TD(λ), but for policy gradient GAE is literally TD(λ) applied to the advantage rather than the value. The policy gradient $\mathbb{E}[\nabla \log \pi(a|s)\, \hat A]$ is unbiased for any unbiased $\hat A$; the question is always: what's the lowest-variance unbiased estimator? GAE's answer: average all n-step advantages with exponentially decaying weights — just as TD(λ) averages all n-step value targets.

The two dials $\gamma$ controls how far into the future we care. $\lambda$ controls the bias–variance trade in advantage estimation: $\lambda = 1$ is full Monte-Carlo advantage (unbiased, high-variance); $\lambda = 0$ is the one-step advantage $\delta_t$ (maximally biased, lowest variance). Unlike $\gamma$, $\lambda$ doesn't change the objective — it only changes the estimator's statistical properties.

Why $\lambda \approx 0.95$ Schulman et al. (2015) found empirically that $\lambda$ close to 1 but not exactly 1 performs best across MuJoCo tasks. Values around 0.95–0.97 are the standard default in PPO, A2C, and TRPO implementations — including OpenAI's original PPO codebase and every modern RLHF pipeline.

The clean recursion You don't need to compute the infinite sum; work backward through a trajectory with the one-line recursion $\hat A_t = \delta_t + \gamma\lambda \hat A_{t+1}$. That tight little loop is probably the most-executed piece of RL code in the world right now.

Full circle GAE is why eligibility traces still matter even when "traces" as a concept have disappeared from deep RL code. The math is identical; it's just been vectorised, batched, and renamed.

Why not just SFT Supervised fine-tuning needs target outputs. But for open-ended generation ("write a helpful response"), there's no single correct answer — and experts can't enumerate every good response. Preferences are easier to collect (rank A vs B) and carry relative quality information SFT can't express.

The KL penalty Is the load-bearing detail. Without it, the policy quickly drifts into gibberish that happens to score high on $r_\phi$ (reward hacking). With it, the policy stays close to the distribution the reward model was trained on — where its judgments are reliable. $\beta$ controls how tightly: too high and learning stalls, too low and the policy diverges.

Lineage Christiano et al. (2017) invented preference-based RL. Stiennon et al. (2020) applied it to summarisation. Ouyang et al. (2022) — InstructGPT — made it the core of ChatGPT. Bai et al. (2022) scaled it at Anthropic. The entire commercial LLM era rests on this 3-stage recipe.

Variants of the data source RLHF uses human labellers. RLAIF (Bai et al. 2022, Lee et al. 2023) uses another LLM as a judge. Constitutional AI generates preferences via explicit written principles. RLVR (see 7.7) replaces the reward model with programmatic verifiers.

The great unbundling In 2023–2026 every piece of this pipeline got challenged. DPO (7.4) removed the RM. GRPO (7.6) removed the value network. RLVR (7.7) removed the reward model. ORPO combined SFT and preference stages. The three-stage recipe is still the mental model, but in production only the first stage is untouched.

Where it comes from The Bradley–Terry–Luce model is 70 years old and underlies everything from chess Elo to tournament seeding. Its insight: you can't directly observe quality, but you can observe pairwise outcomes, and those outcomes reveal a latent scalar score up to an additive constant.

Why pairs, not ratings Asking humans "rate this response 1–10" produces noisy, uncalibrated, rater-dependent data — one person's 7 is another's 5. Asking "which of these two is better?" is cognitively easier, less noisy, and automatically normalised per-rater. Preference pairs are the data source RLHF was designed around.

Architecture In practice, $r_\phi$ is an LLM (usually initialised from the SFT model) with a scalar head replacing the LM head. The final-token hidden state is projected to a single number. Training is a few epochs on preference data — cheap compared to everything else.

Reward hacking The RM is a proxy, not a ground-truth measurement of quality. As the policy optimises against it, it finds regions of output space where the RM is wrong — responses humans don't prefer but that score high. Gao, Schulman & Hilton (2023) derived scaling laws for reward model over-optimisation: there's a KL-budget past which true quality starts to decrease.

Outcome vs process rewards A outcome RM scores a whole response. A process RM scores each step (useful for reasoning chains) — typically trained on human-annotated correctness of intermediate steps. Process RMs give denser signal and reduce credit-assignment difficulty, at the cost of much more expensive data.

Four models in memory The canonical implementation loads policy $\pi_\theta$, reference $\pi_{\text{ref}}$ (frozen SFT), reward model $r_\phi$ (frozen), and a value network $V_\psi$ (trainable). For a 70B-parameter model, that's ~280B parameters live — the main reason GRPO (below) exists.

Why per-token KL Putting KL in the reward rather than as an outer constraint gives a dense, differentiable signal that steers every token — not just ones near the sequence end. Mathematically equivalent to a trajectory KL only under strong assumptions; the per-token version is what actually ships.

The value head Typically an extra scalar head on the policy backbone, trained on discounted returns. The advantage $\hat A_t = \hat R_t - V_\psi(s_t)$ is computed with GAE ($\lambda \approx 0.95$, $\gamma \approx 1$). The value head is a major memory cost, and in practice is often a source of instability.

Common pathologies Entropy collapse (policy becomes deterministic too fast); KL explosion (policy diverges from reference, reward hacking kicks in); mode collapse (same few responses regardless of prompt); length bias (longer responses get higher reward via spurious correlations). Each has a dedicated mitigation and an unhappy engineer.

Why it's being replaced The engineering burden is enormous — four models, careful $\beta$ tuning, distributed training, sensitivity to hyperparameters. DPO (7.4) skips the RL entirely; GRPO (7.6) skips the value net. Both now dominate what was once PPO territory.

The pivot Rafailov et al. (NeurIPS 2023, best paper) noticed that the RM and the policy share the same information. Training an RM to match preferences, then training a policy to match the RM, is doing the same work twice. Because the KL-constrained RL problem has an analytic solution, you can skip the middleman and fit the policy to preferences directly.

What gets computed No sampling, no rollouts, no value network, no reward model. Just log-probability ratios of chosen vs rejected responses under the current policy and the frozen reference, fed into a sigmoid cross-entropy. Training looks indistinguishable from supervised fine-tuning.

What $\beta$ does Same role as in RLHF — controls how tightly $\pi_\theta$ stays near $\pi_{\text{ref}}$. Larger $\beta$: stronger preference signal, but also stronger regularisation anchoring to the reference. In DPO it's effectively a temperature on the implicit reward.

Failure modes DPO's convenience is also its trap. It can decrease the probability of both winner and loser (if lowering the loser's probability more than the winner's reduces the loss). It overfits to static preference data because there's no online exploration. It doesn't handle on-policy shift — you can't collect fresh preferences and iterate the way you can with PPO.

Descendants The DPO lineage has exploded: IPO (Azar 2023, fixes overfitting), cDPO (conservative), SimPO (Meng 2024, reference-free), ORPO (Hong 2024, folds in SFT), KTO (7.5, binary labels). Each swaps one limitation for another.

Status Now the default first-pass alignment method in most open-weight LLM releases. When preference data is available and the reference model is strong, DPO is faster, cheaper, and more stable than PPO-based RLHF.

The data problem DPO has Preference pairs are expensive and unnatural. Real product feedback is unary: a thumbs-up, a thumbs-down, a regeneration click. Paired data has to be constructed, often synthetically. DPO wastes most of the real-world feedback signal by insisting on pairs.

Prospect theory Kahneman & Tversky showed (Nobel-prize work) that humans don't evaluate outcomes linearly — they feel losses ~2× more strongly than equivalent gains, relative to a reference point. KTO (Ethayarajh et al., 2024) encodes this explicitly: desirable examples pull the policy up, undesirable examples push it down harder.

The reference point $z_0$ Is not a single fixed value — it's approximated as the average implicit reward over a batch. Intuitively: "is this response better than a typical one under the current policy?" This makes the utility scale-free and self-normalising.

What you get KTO matches or beats DPO on standard benchmarks while using data that's roughly an order of magnitude cheaper to collect. It's the method of choice when you have natural binary feedback — post-deployment click data, moderation flags, satisfaction signals.

Caveat KTO doesn't handle the explicit comparison signal that preference pairs carry. When you have curated pairs from expert annotators, DPO is still competitive. The two methods solve different data regimes.

Origin Introduced by Shao et al. (2024) in the DeepSeekMath paper, then made famous as the algorithm behind DeepSeek-R1 (2025) — the first open-weight model to match frontier reasoning performance, trained almost entirely with GRPO on verifiable rewards.

Why drop the critic In LLM-scale RLHF, the value network is another multi-billion-parameter model in memory. Removing it cuts memory and compute substantially. The question is whether you can do without a learned baseline — GRPO's answer: yes, if you sample a group per prompt, the group mean is a baseline.

Why group baselines work Any baseline $b(s)$ that doesn't depend on the action leaves the policy gradient unbiased (same reason as REINFORCE). The group mean satisfies this — and being sample-based, it tracks the current policy automatically without any separate training.

Same advantage on every token This is a minor heresy. Classical PPO has a per-token advantage; GRPO assigns the whole completion the same value. It works because for discrete, sparse-reward tasks (math/code), a single sequence-level signal is usually what you have anyway. GSPO and TIC-GRPO (2025) formalise this as sequence-level importance sampling.

KL in the loss, not the reward GRPO puts KL directly in the loss as an explicit regulariser, rather than shaping per-token rewards. Differentiable, transparent, and easier to tune. But — the gradient of a sample-based KL estimator is subtle; recent work (Tang & Munos 2025, Shah et al. 2026) shows some popular libraries compute biased gradients here.

When to use it GRPO shines when rewards are cheap and verifiable (math answers, unit tests, logical proofs). Pair it with RLVR (7.7) and you get the recipe behind essentially every reasoning model released since R1.

The paradigm shift Classical RLHF assumed quality was subjective — you needed humans (or an RM trained on humans) to judge. RLVR recognises that for a growing set of tasks — math, code, proofs, structured outputs — correctness is objective and automatically checkable. When it is, there's no reason to introduce a fallible human-preference proxy.

R1's surprise DeepSeek-R1-Zero (early 2025) was trained purely with RLVR on math and code, with no SFT stage at all. It developed long chain-of-thought reasoning, self-verification, and backtracking emergently — not from imitation, but because those behaviours got rewarded by the verifier. This shocked the field and launched a wave of reasoning-model work.

No reward hacking The verifier is ground truth, not a proxy. A correct answer is a correct answer; there's no latent quality dimension to exploit. This is an enormous simplification: you can train much more aggressively (high $\beta$, many steps) without fear of the model finding a degenerate solution the RM mislabels.

What DAPO teaches us Long chain-of-thought responses (thousands of tokens) break assumptions built into PPO/GRPO for shorter completions. Variance in sequence length creates gradient imbalances; low-probability-but-correct reasoning tokens get clipped away; empty reward regions waste compute. DAPO's four fixes each address a specific failure mode observed in the DeepSeek-R1 reproduction effort.

Results DAPO trained Qwen2.5-32B to 50 points on AIME 2024 with half the steps of DeepSeek-R1-Zero — and open-sourced the full system. GRPO + RLVR + DAPO-style tricks is now the standard stack for reasoning-model post-training.

Limits of verifiability RLVR works where verification is easier than generation. For open-ended writing, dialogue, or subjective quality, you still need an RM (or DPO/KTO on preferences). The emerging consensus: use RLVR-GRPO for reasoning, DPO/KTO for style/alignment — and chain the two stages.