Reinforcement Learning

Markov decision processes

A tuple of states, actions, transitions, rewards and a discount factor that formalizes sequential decision under uncertainty.

Transitions depend only on the current state and action. The optimal policy is found by maximizing expected discounted return over trajectories.

The Markov property collapses a search over histories into a search over states, making the problem tractable when the state captures enough.

The big idea

Any task where outcomes follow from a sequence of choices and the environment can be modeled as memoryless given the right state representation.

When a choice changes what choices you face next, a single prediction is not enough. The agent needs a way to compare whole futures while still acting from the information available now. A Markov decision process does that by asking the state to carry every fact needed for the next transition and reward. If the state representation succeeds, the policy can depend on the current state alone, and planning no longer has to remember the full path that led there.

$$V^{\pi}(s) = \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^{t} r_t \;\middle|\; s_0 = s\right]$$

The value of a state under a policy is the expected total reward from that state onward, with rewards further in the future counted less.

symbol	meaning
$s$	the current state
$\pi$	the policy: the rule mapping states to actions
$r_t$	reward received at step t
$\gamma$	discount factor between 0 and 1; smaller means more myopic
$V^{\pi}(s)$	expected discounted return, the quantity every value-based method estimates

Formal tuple

A Markov decision process is the tuple $(S, A, P, R, \gamma)$: a set of states $S$, a set of actions $A$, a transition function $P(s' \mid s, a)$ giving the probability of landing in $s'$ after taking $a$ in $s$, a reward function $R(s, a)$, and a discount factor $\gamma \in [0, 1)$. The Markov assumption is that the transition and reward depend only on the current state and action, not on the history that led there. What it buys is that the optimal policy can be a function of the current state alone, which collapses a search over histories of unbounded length into a search over a fixed set.

Without it, the optimal action could depend on everything that came before and the problem is intractable. The assumption is also where most modeling effort goes, because it is a constraint on the state representation rather than on the world: any process becomes Markov if the state is defined to include enough history, and the practical work is finding a state definition that is rich enough to be Markov and small enough to learn. Partially observable formulations handle the case where it fails, at the cost of requiring a belief state over the unobserved variables.

Policy definition

A policy $\pi(a \mid s)$ specifies how to act, as a distribution over actions given a state. The state value function

$$V^\pi(s) = \mathbb{E}_\pi\left[\sum_{t=0}^{\infty} \gamma^t R_t \mid s_0 = s\right]$$

symbol	meaning
$V^\pi(s)$	state value under policy $\pi$: expected discounted return starting from state $s$
$t$	time step index
$R_t$	reward received at step $t$
$\gamma$	discount factor between 0 and 1
$s_0$	initial state

is the expected discounted return from state $s$ when following $\pi$. The action value function $Q^\pi(s, a)$ is the same quantity conditioned on taking action $a$ first and following $\pi$ afterward.

Why both value functions

The reason both exist is that they support different algorithms: acting greedily with respect to $V$ requires a transition model to look one step ahead, and acting greedily with respect to $Q$ does not, since the comparison across actions is already stored. That single difference is why model-free control methods learn $Q$ rather than $V$.

Discounting as computational convenience and modeling choice

Discounting is usually introduced as a mathematical convenience to keep infinite sums finite, which is true and understates what the factor encodes. Three interpretations are simultaneously correct:

Interpretation	What $\gamma$ encodes
Rate of time preference	How much sooner is preferred to later, like an interest rate
Survival probability	A process terminating with probability $1 - \gamma$ each step has expected return matching the discounted sum
Effective horizon	Steps that materially contribute is roughly $\frac{1}{1 - \gamma}$: 10 steps at $\gamma = 0.9$, 100 at $\gamma = 0.99$, 1,000 at $\gamma = 0.999$

Setting $\gamma = 0.99$ on a task where the consequential outcome arrives 500 steps out is choosing to nearly ignore it.

Discounting also serves a computational purpose covered under value iteration below, where it is the contraction factor that makes the fixed-point iteration converge.

Bellman equation

A recursive identity stating that the value of a state equals the immediate reward plus the discounted value of the successor state.

Define a Bellman operator that maps any value function to the right-hand side. Repeatedly apply it until convergence to the fixed point.

The operator is a contraction with modulus gamma, so the Banach fixed-point theorem guarantees a unique solution reachable from any start.

The big idea

Whenever discounted return is well defined. Undiscounted continuing tasks require separate treatment because the fixed point need not exist.

A state cannot be valued in isolation when its worth comes from the states it can reach. The Bellman equation expresses that circular dependence directly: today’s value is immediate reward plus the discounted value of the possible next states. That makes value estimation a fixed-point problem rather than a one-pass calculation, and the discount below one gives the repeated update a unique place to settle.

Recursive value statement

The value of a state is the immediate reward plus the discounted value of where you land, and this is the fixed point every reinforcement learning algorithm chases. For a fixed policy the equation averages over the actions $a$ that policy takes, weighting each by its immediate reward $R(s,a)$ and by the value of wherever it leads, where the discount factor $\gamma$ sets what a future reward is worth today and $P(s' \mid s, a)$ gives the probability of landing in state $s'$:

$$V^\pi(s) = \sum_a \pi(a \mid s) \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s, a) V^\pi(s') \right]$$

Optimal form

For the optimal policy the average over actions becomes a maximum: take the best available action, collect its reward, then add the discounted optimal value of wherever that action lands you.

$$V^*(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s' \mid s, a) V^*(s') \right]$$

symbol	meaning
$V^\pi(s)$	value of state $s$ under policy $\pi$
$V^{*}(s)$	optimal value function
$a$	an action available in state $s$
$R(s,a)$	immediate reward for taking $a$ in $s$
$P(s' \mid s,a)$	probability of landing in state $s'$
$\gamma$	discount factor

Fixed-point interpretation

The Bellman equation states a fixed point rather than a formula you evaluate, and the distinction is the reason this subject has the shape it does.

The right-hand side contains the quantity being defined, so there is nothing to compute directly: the equation constrains $V$ rather than expressing it. What makes the constraint usable is that the map taking a value function to the right-hand side, called the Bellman operator, is a contraction in the maximum norm with modulus $\gamma$, so repeated application converges to a unique fixed point from any starting function.

Without a discount, or with $\gamma$ set to one, the operator need not contract and the iteration can fail to settle.

Banach fixed point

Existence, uniqueness and a convergence rate all follow from the Banach fixed-point theorem, which is why the discount factor below one is doing structural work rather than modeling work. For the policy evaluation form the equation is linear and can be solved directly as a system of $|S|$ equations, at cost cubic in the number of states, and for the optimality form the maximum makes it nonlinear and iteration is the practical route.

Connections to sampled methods

Value iteration and policy iteration, developed in the next section, are the templates for sampled methods: actor-critic methods are policy iteration with function approximation and sampled updates, Q-learning is value iteration with sampled transitions replacing the expectation, and the reinforcement learning stage of a language model pipeline is policy iteration with sampled evaluation, scored by a learned reward model or a checker.

Value and policy iteration

Two exact algorithms for solving a known MDP: one iterates the value function, the other alternates policy evaluation with greedy improvement.

Value iteration applies the Bellman optimality operator repeatedly. Policy iteration solves a linear system for the current policy, then improves.

Both converge because the optimality operator is a contraction and the set of deterministic policies is finite.

The big idea

Only when the state space fits in memory and the transition model is known. Neither condition holds in any deployed system.

If the whole transition model fits on the machine, the Bellman equation becomes something you can solve by repeated sweeps. Value iteration keeps improving the value table itself; policy iteration alternates between scoring the current policy and replacing it with a greedier one. The shared promise is exact convergence in the tabular, known-model setting, and the shared limitation is just as sharp: once the state space stops fitting in memory, the guarantee no longer describes the system being run.

$$\|T V - T V'\|_{\infty} \le \gamma \|V - V'\|_{\infty}$$

Applying the Bellman operator to two different value estimates moves them closer together by at least a factor of gamma, so repeated application drives any starting estimate to the unique fixed point.

symbol	meaning
$T$	the Bellman optimality operator, one sweep of the update
$V, V'$	any two value functions over the state space
$\|\cdot\|_{\infty}$	the largest absolute difference at any single state
$\gamma$	the discount factor, which is the contraction modulus

Iteration schemes

Value iteration applies the Bellman optimality operator repeatedly, updating every state’s value from its successors and stopping when the change falls below a threshold, then extracting a policy. Reaching accuracy $\epsilon$ from initial error $E$ takes $\frac{\ln(E/\epsilon)}{\ln(1/\gamma)}$ iterations, about 687 sweeps at $\gamma = 0.99$ and 6,904 at $\gamma = 0.999$ for a thousandfold error reduction, $E/\epsilon = 1000$. Each sweep costs $O(|S|^2|A|)$.

Policy iteration alternates exact evaluation of the current policy with greedy improvement. It converges in few iterations, often under a dozen on large problems, because each improvement produces a policy at least as good in every state and the policy count is finite. It pays more per sweep: exact evaluation solves a linear system at $O(|S|^3)$.

Modified policy iteration

Modified policy iteration runs evaluation for a fixed small number of sweeps rather than to convergence, and is what most implementations use, with value and policy iteration as the endpoints.

The contraction factor $\gamma$ sets the convergence rate, which is why a discount below one is a computational convenience as much as a modeling choice. Iteration count scales as $\frac{1}{1 - \gamma}$ up to a log factor, so $\gamma = 0.9$ to $\gamma = 0.999$ costs roughly a hundredfold more sweeps. The tension is usually resolved silently: long-horizon problems need a discount near one, and a discount near one makes computation slow and estimates high-variance.

Exact versus approximate algorithms

Both require the transition model $P(s' \mid s, a)$ and a table over all states, and that fails for every deployed problem. The model requirement rules out unknown dynamics, which is most settings. The table is worse: the state space of a board position, a robot configuration or a partial token sequence is astronomically large.

A Go position is one of roughly $10^{170}$, and a 1,000-token prefix over a 100,000-token vocabulary has more values than the observable universe has atoms. The representation they assume does not exist.

Approximate dynamic programming

Approximate dynamic programming is the bridge and it costs the guarantee. Replace the table with a parameterized $V_\theta(s)$, fit it to the Bellman targets by regression, iterate. Everything carries over except what made it work: the Bellman operator is a contraction in value-function space, and its composition with a projection need not be.

The projection can expand errors, the iteration can diverge, and it does so in practice. Function approximation is one component of the deadly triad discussed under Q-learning below.

Why deep RL is unstable

The lost contraction is the reason deep reinforcement learning is an empirical discipline with a large gap between what is proved and what is run.

Convergence against discount factor

Remaining error bound against value iteration sweeps, on a log y axis, for discount factors of 0.9, 0.95, 0.99 and 0.999. Each curve is a straight line whose slope is set by the discount factor, and the sweeps needed to reach one percent error grow roughly in proportion to the effective horizon.

1. one percent of the initial error

Discounting controls how far future rewards echo backward through value iteration. As gamma approaches one, each sweep carries less new contraction, so long horizon problems require many more passes to settle.

Tree search as inference-time planning

A planning method that allocates computation to a partial search tree at decision time rather than relying only on a learned policy.

Monte Carlo tree search repeats selection, expansion, simulation, and backpropagation on a growing asymmetric tree rooted at the current state.

The tree concentrates visits where estimates are uncertain or high-value, making search viable when exhaustive minimax is defeated by branching factor.

The big idea

Games and planning tasks with a simulator, a well-defined action set, and a terminal or otherwise trustworthy evaluation signal.

A search tree makes the computation visible. A node is a state, an edge is an action, and the root is the position where the agent must act now. Minimax with alpha-beta pruning treats the tree as an object to search deeply under adversarial backups, cutting branches that cannot affect the exact backed-up value. Monte Carlo tree search instead treats the tree as a statistical object. It grows only the part its samples visit, keeps a mean value and a visit count on each edge, and improves the root decision by spending more simulations before the action is chosen. Browne et al. survey the family, including the variants that made this structure practical.

The asymmetric tree is the central distinction from exhaustive search. Alpha-beta pruning still reasons over a regular tree defined by move order and depth, even when it proves parts irrelevant. MCTS lets the tree’s shape become evidence. A forced tactical line, a promising joseki, or a move whose value estimates disagree can receive thousands of visits while neighboring legal moves receive one. That allocation is why the method works on branching factors that defeat full-width search. It does not need to prove every sibling bad. It needs enough samples to make the root action robust under the computation available. The tree is not rebuilt as a full game tree at any fixed depth. It is the accumulated trace of where the budget has gone. The selection rule and learned evaluators are developed under Monte Carlo tree search below.

MCTS separates training from the computation spent on a decision. Training amortizes experience into a policy and a value function; search spends fresh compute on the current instance to improve the action before committing. The same tradeoff appears in test-time compute for language models. Sampling multiple continuations, scoring them with a verifier or reward model, branching on promising partial solutions, and backing up the best evidence all substitute inference compute for a better one-shot policy. The genuine commonality is resource allocation: more computation at decision time can compensate for an imperfect learned proposal, especially when a cheap evaluator distinguishes good branches from bad ones. The difference is just as important. Board-game MCTS has an exact simulator, legal moves, reversible state copies, and terminal outcomes. Language model search usually has token continuations or tool calls rather than a compact action set, partial text rather than Markov game states, and learned or sparse evaluation rather than a guaranteed terminal reward. The analogy is about compute allocation, not about theorems transferring.

The method fails when one of its three supports is missing. Without a simulator, the agent cannot sample counterfactual futures from the same state, so the tree is only a record of real actions already taken. Without a well-defined action set, expansion cannot enumerate children or assign visit counts to comparable alternatives; free-form plans and open-ended tool use break this assumption unless a controller discretizes them first. Without a terminal signal or a trusted value evaluator, backpropagation has no scalar to send upward, so selection optimizes noise. The binding constraint in most real problems is the simulator. Many domains can define a finite action set after engineering, and many can provide some delayed reward, but few supply a cheap, resettable, high-fidelity model of the consequences of actions. MCTS is strongest exactly where that model is given by the rules.

Temporal difference learning

A family of methods that update value estimates from successor estimates rather than from complete returns.

At each step compute the TD error: reward plus discounted next-state value minus current value. Move the estimate toward that target.

Bootstrapping replaces variance from the full trajectory with bias from the current estimate; in long or noisy tasks the trade favors bias.

The big idea

When episodes are long, rewards noisy, or learning must happen online. Not when the value function is badly initialized and bias dominates.

Waiting for an episode to finish can make learning both slow and noisy, especially when the reward arrives after many stochastic steps. Temporal difference learning updates after one transition by comparing what just happened with the value estimate already assigned to the next state. The price is that today’s target inherits any error in that next-state estimate; the payoff is that learning can proceed online without a transition model or a completed trajectory.

$$\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t), \qquad V(s_t) \leftarrow V(s_t) + \alpha \delta_t$$

The prediction error is the reward you actually got plus what you now think the next state is worth, minus what you thought the current state was worth; move the estimate a small step in that direction.

symbol	meaning
$\delta_t$	the temporal difference error at step t
$r_t$	reward observed on this transition
$V(s_t)$	current estimate of the value of state s at time t
$\gamma$	discount factor
$\alpha$	step size, which controls how much one transition moves the estimate

A positive error means things went better than expected and the estimate should rise. The update $V(s_t) \leftarrow V(s_t) + \alpha \delta_t$ moves it toward the revised figure at rate $\alpha$. Nothing requires the transition model or the end of the episode, which is what makes it usable where dynamic programming is not applicable.

Bootstrapping versus Monte Carlo

Bootstrapping means using a current estimate to form the target for another estimate, and it is the defining feature.

The bias bootstrapping introduces is direct: if $V(s_{t+1})$ is wrong, the target is wrong, so early in learning the method is fitting to its own errors.

Variance reduction it buys

Bootstrapping buys a large variance reduction, because the target depends on one sampled transition rather than the whole trajectory. With hundreds of steps and stochastic rewards the variance of the full return is enormous and that of a single step is small, and the reduction is usually worth more than the bias.

Monte Carlo waits for the true return and uses it as the target, unbiased by construction. No bootstrapping means no bias from bad value estimates, and variance proportional to the randomness over the episode. It needs episodes to terminate and cannot update until one ends.

Method	Prefer when
Temporal difference	Episodes are long, rewards are noisy, learning must happen online
Monte Carlo	Value function is badly initialized, task is short, bootstrapping bias is suspected

TD(λ) and eligibility traces

TD($\lambda$) is the continuum between them, $\lambda = 0$ giving one-step learning and $\lambda = 1$ Monte Carlo. The forward view makes the target a geometrically weighted average of $n$-step returns; the backward view implements it online with eligibility traces that spike on visit and decay by $\gamma\lambda$ per step.

The two views are equivalent, and the trace implementation is practical: a single pass, constant memory per state. Generalized advantage estimation, below, is the same construction on advantage estimates.

Dopamine correspondence

The dopamine correspondence is the closest thing to a neural validation, and it is often overstated. Recordings from primate midbrain dopamine neurons, published by Schultz and colleagues in the 1990s, show firing that matches the temporal difference error rather than reward: firing to an unexpected reward, silence when a learned cue predicted it, transfer to the cue, and a drop below baseline when a predicted reward fails.

That last finding is the strongest evidence: a system encoding reward has nothing to signal when nothing happens, while one encoding prediction error must signal a negative. The correspondence was not engineered; the algorithm came from machine learning and models of animal conditioning, not from the recordings.

Qualifications on the evidence

The qualifications: dopamine also carries novelty and movement signals, firing rate maps imperfectly to a signed error for large negatives given the low baseline, and the correspondence shows a temporal difference signal is present, not that the brain runs an algorithm on it.

Q-learning and off-policy control

An off-policy algorithm that learns the optimal action-value function regardless of what policy generates the data.

The target uses the maximum over next-state action values rather than the action actually taken, so the update evaluates the greedy policy.

Off-policy learning decouples data collection from the target, enabling replay buffers, logged data, and demonstrations.

The big idea

When data is expensive and must be reused. Fails under function approximation without stabilizers; the deadly triad causes divergence.

An on-policy method learns the value of the policy it follows; an off-policy method learns the value of one policy while following another. On-policy must discard data when the policy changes. Off-policy can learn from replay buffers, demonstrations, logged traffic, or a different agent. Preference-based language model training is off-policy whenever it learns from preference pairs collected under an earlier policy.

The Q-learning update is

$$Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ R_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) \right]$$

Maximum makes it off-policy

The maximum operator makes it off-policy: the target evaluates the greedy policy regardless of what action is actually taken next.

SARSA is the on-policy counterpart, using $R_{t+1} + \gamma Q(s_{t+1}, a_{t+1})$ instead. In cliff-walking, Q-learning learns the optimal path along the cliff edge (evaluating the greedy policy that never falls), while SARSA learns a safer path further away (accounting for the exploratory steps it actually takes). On-policy methods account for their own exploration; off-policy methods learn the target policy and ignore the cost of getting there.

Convergence and the deadly triad

Tabular Q-learning converges under Robbins-Monro conditions ($\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$) with every state-action pair visited infinitely often. This does not carry to function approximation: with a table each update touches one entry, but with a function approximator every update changes estimates at unvisited states.

The deadly triad is bootstrapping, off-policy learning, and function approximation together. All three at once is where the standard counterexamples live; Baird’s, among them, is linear. Dropping a leg is not a theorem of safety, though: bootstrapping with nonlinear approximation can diverge on-policy too. Most deep RL systems run all three simultaneously, in the region where no convergence theorem applies. Language model reinforcement stages that train a learned critic bootstrap with function approximation while staying only approximately on-policy, and critic-free Monte Carlo policy gradient methods such as GRPO, now common in language model training, do not bootstrap at all.

Baird’s counterexample

Baird’s counterexample shows parameters growing without bound on a problem with a well-defined solution. Target networks, gradient clipping, replay buffers, and conservative step sizes are empirical stabilizers, not proofs.

Maximization bias

The expectation of a maximum over noisy estimates exceeds the maximum of the expectations. Taking $\max_{a'} Q(s', a')$ over noisy estimates produces an upward-biased target that compounds through bootstrapping. With $n$ equal-valued actions and independent standard normal noise, the expected maximum reaches about 1.54 standard deviations at $n = 10$ and 2.51 at $n = 100$.

Double Q-learning corrects this: maintain two independent estimators, use one to select the maximizing action and the other to evaluate it. The deep variant reuses the target network as the second estimator at no extra cost.

Policy gradient theorem

A result stating that the gradient of expected return with respect to the policy parameters has a form that does not require differentiating the environment.

The gradient is an expectation of the log-policy gradient times a return estimate, computable by sampling trajectories.

Terms involving the state distribution cancel, leaving only quantities the agent observes. No environment model or simulator is needed.

The big idea

Any differentiable parameterized stochastic policy. Variance is large and must be reduced by baselines; without them the method is impractically noisy.

Sometimes the object being trained is the policy itself, not a table of values used to choose actions afterward. The policy gradient theorem makes that direct optimization usable by rewriting the gradient in terms of log action probabilities and sampled returns. The payoff is that the environment does not need to be differentiable or known, although the sampled gradient is noisy enough that baselines become part of the method rather than a refinement.

The policy gradient theorem states that the gradient of expected return with respect to policy parameters is

$$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\left[ \nabla_\theta \log \pi_\theta(a \mid s) \, Q^{\pi_\theta}(s, a) \right]$$

where $J(\theta)$ is the expected discounted return, $\pi_\theta(a \mid s)$ is the policy, and $Q^{\pi_\theta}(s,a)$ is its action-value function.

Avoiding the state distribution

The naive approach needs the gradient of the state distribution with respect to the parameters, since changing the policy changes which states you visit. The theorem shows those terms cancel, leaving the log-policy gradient, available in closed form, times a sampled return estimate. Nothing about the environment must be differentiable or known.

Variance and baselines

Variance is the practical obstacle. The estimator is unbiased with large variance, because the return multiplying the log-probability gradient accumulates randomness over the trajectory.

Subtracting a state-dependent baseline leaves the gradient unbiased because $b(s)$ factors out of the expectation, where $\theta$ are the policy parameters being differentiated and the inner sum runs over every action $a$ available in the state:

$$b(s) \sum_a \pi_\theta(a \mid s) \nabla_\theta \log \pi_\theta(a \mid s) = b(s) \sum_a \nabla_\theta \pi_\theta(a \mid s) = b(s) \nabla_\theta \sum_a \pi_\theta(a \mid s) = b(s) \nabla_\theta 1 = 0$$

The condition is that the baseline not depend on the action; a baseline that peeks at the sampled action biases the gradient. The variance-minimizing choice is close to $V^\pi(s)$, converting $Q$ into the advantage $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$.

Only the relative merit of an action should change its probability: if every action in a state returns 100, none should be reinforced, and without a baseline all are. The variance reduction is often an order of magnitude.

Direct preference optimization

Direct preference optimization removed the separately trained reward model. The standard pipeline fits a reward model to human preference comparisons, then optimizes the policy against that reward with a divergence penalty toward a reference policy.

The optimal policy for that penalized objective has a closed form, and inverting it expresses the reward in terms of the optimal and reference policies. Substituting into the preference likelihood eliminates the reward, leaving a loss over preference pairs optimized by gradient descent on the policy.

What is gained	What is given up
Removal of an entire model, training stage, and sampling loop	Ability to score arbitrary new samples
Large reduction in engineering surface and cost	The method learns only from the fixed preference dataset

Actor-critic and advantage estimation

An architecture pairing a policy (actor) with a value function (critic) that supplies low-variance return estimates for the policy gradient.

The critic learns by TD updates on the same trajectories. The actor uses the critic to form advantage estimates rather than raw returns.

Subtracting a state-dependent baseline does not bias the gradient and greatly reduces variance, since only relative action merit is reinforced.

The big idea

Continuous control, language model RL, and anywhere policy gradients are used. Fails when the critic is poorly trained and biases the actor.

A raw trajectory return tells the policy whether the whole run was good, but not whether one action was better than the other actions available in the same state. Actor-critic methods split that job. The actor is the policy being improved, and the critic estimates state value so the update can use advantage rather than raw return. That subtraction lowers variance by reinforcing relative action quality, while a poor critic can pass its errors straight into the actor.

Actor and critic

The actor is the policy, updated by the policy gradient. The critic is a value function, updated by TD learning on the same trajectories, supplying the return estimates the actor needs. The arrangement is policy iteration with both phases approximated and interleaved.

Advantage function

The advantage $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$ measures how much better an action is than the average for that state. An advantage of zero means the action is exactly as good as the policy’s expectation; positive means better, negative means worse.

Raw returns vary by orders of magnitude across states, dominating the gradient regardless of action quality; the advantage removes that dependence.

Generalized advantage estimation is $\hat{A}_t = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_{t+l}$, where $\delta_t = R_{t+1} + \gamma V(s_{t+1}) - V(s_t)$. At $\lambda = 0$ it is the one-step TD estimate with low variance and full critic bias. At $\lambda = 1$ it is the Monte Carlo advantage with full variance. Values around 0.95 are standard. Note $\gamma$ and $\lambda$ discount different things: $\gamma$ is part of the problem, $\lambda$ is an estimator choice.

Where critic error hurts

Critic error hurts most at low $\lambda$ and in states seen least. In language model pipelines, the value head is trained on returns from a reward model that is itself approximate, on a distribution shifting as the policy updates. Its errors are largest on outputs the policy has recently started producing. Practical checks: monitor explained variance of the value head, normalize advantages within a batch, and raise $\lambda$ when the critic is suspect.

Trust region methods and PPO

Policy gradient methods that forbid or discourage large changes to the policy in one update, to prevent destructive steps.

TRPO constrains the KL divergence from the old policy. PPO clips the importance ratio so the objective flattens past a threshold.

The gradient estimate is valid only near the policy that generated the data; a large step evaluates a distribution that was never sampled.

The big idea

Any policy gradient setting. PPO dominates in practice because it is first-order, parallelizes easily, and avoids second-order solves.

Trust region methods constrain how far a policy may move in one update, because a large policy step invalidates the data it was estimated from.

$$L^{\mathrm{CLIP}}(\theta) = \mathbb{E}_t\!\left[\min\!\left(\rho_t \hat{A}_t,\; \mathrm{clip}(\rho_t, 1-\epsilon, 1+\epsilon)\hat{A}_t\right)\right], \quad \rho_t = \frac{\pi_{\theta}(a_t\mid s_t)}{\pi_{\theta_{\mathrm{old}}}(a_t\mid s_t)}$$

symbol	meaning
$L^{\mathrm{CLIP}}$	the clipped surrogate objective
$\theta$	policy parameters
$\rho_t$	importance ratio: how much more likely the new policy makes the action already taken
$a_t$	action taken at step $t$
$s_t$	state at step $t$
$\hat{A}_t$	estimated advantage of that action
$\epsilon$	clip width, typically 0.1 to 0.2
$\pi_{\theta_{\mathrm{old}}}$	the policy the data was collected under

The gradient is a local approximation estimated from the current policy’s data, and a step that degrades the policy degrades the next batch, compounding the failure.

Trust region policy optimization

TRPO constrains the update by:

$$\mathbb{E}_s\left[ D_{KL}\left(\pi_{\theta_{old}}(\cdot \mid s) \,\Vert\, \pi_\theta(\cdot \mid s)\right) \right] \leq \delta$$

symbol	meaning
$D_{KL}$	Kullback-Leibler divergence
$\pi_\theta$	the policy parameterized by $\theta$
$\pi_{\theta_{old}}$	the old policy from which data was collected
$s$	a state
$\delta$	the trust region size

The constraint is on the policy’s output distribution, not its parameters. Solving to second order gives the natural gradient, preconditioned by the inverse Fisher information matrix; practical implementations use conjugate gradient plus a line search. The monotonic improvement guarantee belongs to the theory, which bounds divergence at the worst state and optimizes an exact surrogate; the average KL constraint and approximate solve used in practice keep it as a motivation rather than a promise. TRPO also costs a second-order solve per update.

Proximal policy optimization

PPO approximates a trust region with a first-order method:

$$L = \mathbb{E}\left[ \min\left( r_t \hat{A}_t, \; \mathrm{clip}(r_t, 1-\epsilon, 1+\epsilon)\hat{A}_t \right) \right]$$

symbol	meaning
$L$	the surrogate objective to maximize
$r_t$	importance ratio between new and old policy probabilities
$\hat{A}_t$	estimated advantage
$\epsilon$	clip width, typically 0.1 to 0.2

When the advantage is positive and the ratio exceeds $1 + \epsilon$, the minimum selects the clipped term, which no longer depends on the ratio, so that sample adds nothing to the gradient. With $\hat{A}_t = 2$, $\epsilon = 0.2$ and $r_t = 1.3$, the term is $\min(1.3 \times 2, 1.2 \times 2) = 2.4$, and it stays at 2.4 however far the ratio rises. The same mechanism operates for negative advantage below $1 - \epsilon$. The objective stops paying for movement beyond the region where the data supports the estimate, but nothing pulls an overshooting ratio back, so after an update some ratios can sit outside $[1 - \epsilon, 1 + \epsilon]$ and the new policy can end up further from the old one than intended. OpenAI’s Spinning Up implementation, for one, stops taking gradient steps once the mean KL divergence from the old policy passes a threshold.

Divergence penalty in preference-based training

The objective adds $-\beta D_{KL}(\pi_\theta \Vert \pi_{ref})$, where $\pi_{ref}$ is a frozen reference model, usually the supervised fine-tuned model that reinforcement learning started from. InstructGPT applied the penalty at each token against that model and brought in pretraining data through a separate gradient term. The PPO ratio’s $\pi_{\theta_{old}}$ is a different policy, whichever one sampled the current batch, and it is replaced with each new batch. The penalty serves two purposes: stability and keeping the policy inside the region where the reward model is valid.

Raising the KL penalty caps how much the policy can improve on the reward; lowering it lets the policy drift into the region where the reward model is wrong. The two roles argue for different anchors, and implementations differ on which they use.

Why PPO dominates

The constrained method has a monotonic improvement guarantee that the clipped method lacks, but the guarantee holds under assumptions deep networks violate. PPO has first-order updates compatible with any optimizer, supports multiple epochs over the same batch, parallelizes easily, and is short enough to implement correctly. The method won on operational grounds.

The clipped objective

The PPO clipped surrogate objective against the probability ratio, for advantage plus one and minus one. The positive branch flattens above a ratio of 1.2; the negative branch keeps falling.

1. flat: no reward for going further
2. still falling: no floor on backing off
3. 1 − ε
4. 1 + ε

Clipping turns policy improvement into a guarded step. Once the new policy moves too far from the old one, the surrogate stops rewarding additional movement, which is how PPO limits destructive updates.

Monte Carlo tree search

A decision-time planning method that grows a search tree from sampled trajectories, spending its budget on the branches that look most promising instead of expanding every move.

Each iteration selects a path by a tree policy, adds a node, estimates that node's value by a rollout or a learned evaluator, and passes the result back up the path.

A tree grown toward high-value moves reaches strong decisions after evaluating far fewer positions than exhaustive search, and it keeps improving while the budget lasts.

The big idea

Games and planning problems that supply a model to sample from. Weak when the branching factor is enormous, the evaluator is poor, or one decisive move is almost never sampled.

Monte Carlo tree search plans when a decision is due rather than learning a policy in advance. Given an environment it can copy and step forward, it runs many simulated continuations from the current position, records a value and a visit count for every node it touches, and lets the tree grow unevenly toward the moves those simulations reward. When the compute budget runs out it commits to the most visited move at the root and reuses or discards the rest of the tree.

Tree policy and the UCT rule

Each iteration has four steps. Selection walks the current tree from the root by a tree policy until it reaches a node with an unexpanded legal child. Expansion adds one or more such children. Simulation estimates the new leaf’s value. Backpropagation sends that scalar result back along the selected path, updating visit counts and mean returns for each state-action edge. The sampling concentrates in the selection step, where the upper confidence bound for trees picks at each node the child that maximizes

$$\mathrm{UCT} = \bar{Q}(s,a) + c\sqrt{\frac{\ln N(s)}{N(s,a)}}$$

symbol	meaning
$\bar{Q}(s,a)$	mean simulated return from taking $a$ in state $s$
$N(s)$	number of visits to the parent state $s$
$N(s,a)$	number of visits to the child reached by $a$
$c$	constant setting the weight on the exploration term

A child earns selection because its sampled value is high or because it has been tried too rarely to trust, and the second reason fades as its visit count climbs. Averaging the simulated returns and backing them up gives every node an estimate that sharpens with each visit. The move played at the root is the most visited one rather than the highest mean, since the visit count already folds in both the value and the confidence earned by repeated selection.

From rollouts to learned value

The value of a fresh node came originally from a random rollout to the end of the game, cheap and unbiased for the rollout policy but brutal in variance, since random play from a Go position can throw away all structure before the end score arrives. Silver et al.’s 2016 AlphaGo cut that variance by combining tree search with learned policy and value networks; Silver et al.’s 2017 AlphaGo Zero removed rollouts entirely, and Silver et al.’s 2018 AlphaZero generalized the no-rollout design across Go, chess, and shogi. The policy prior narrows the effective branching factor by concentrating early visits on the moves the network rates plausible, and the value network scores a position without playing the game to its end, removing the noisiest part of the original method.

A learned policy prior and a learned value network change where the budget goes rather than what the loop is. The substitution buys far more useful simulations per second but costs independence from the learned model: when the search stops at a leaf, the backup is only as good as the network’s judgment there. Search can correct a weak prior near the root, but it cannot repair a systematically wrong leaf evaluator beyond the horizon it actually expands.

This is where planning meets the learning methods above. Search turns the current policy and value into better decisions for the compute spent at the moment of choice, and those decisions become supervised targets: the visit counts at the root form a sharpened policy to imitate, and the game outcomes train the value estimate, so search and learning raise each other across iterations. The standing limit is the dependence on a model, since the method needs an environment it can copy and roll forward, which board games provide exactly and most consequential problems do not.

Exploration in large state spaces

The problem of reaching states that yield no reward signal until visited, and methods attempting to drive the agent toward them.

Optimism under uncertainty adds a bonus inversely related to visit count. Intrinsic motivation rewards prediction error or novelty.

Random exploration finds a distant reward with probability exponentially small in path length; only directed exploration can reach it.

The big idea

Hard exploration tasks with sparse reward. Sidestepped in language model RL because pretraining already concentrates the policy near useful outputs.

Epsilon-greedy takes a random action with small probability and fails once a reward requires a long specific sequence. If the reward needs $k$ actions from a set of size $|A|$, undirected exploration finds it with probability $|A|^{-k}$ per attempt: $10^{-20}$ for 20 steps from 10 actions. Random walking explores diffusively, covering distance proportional to $\sqrt{n}$, while the task requires directed movement.

Optimism under uncertainty is the principled response: treat unvisited options as good until evidence says otherwise. The tabular implementation adds $\frac{c}{\sqrt{N(s,a)}}$ to the reward for a pair visited $N$ times. The bonus decays as evidence accumulates, matching the upper confidence bound construction for bandits, and comes with near-optimal regret bounds in the tabular setting.

Pseudo-counts and intrinsic motivation

Pseudo-counts extend count-based bonuses to continuous state spaces, where every state is visited at most once. A density model over states yields an implied count from how much its assigned probability increases after observing a state. Random network distillation is the simpler variant: train a predictor to match a fixed random network’s output on visited states and use prediction error as the novelty signal.

Intrinsic motivation rewards prediction error on the reasoning that being wrong marks something unlearned. The noisy television problem defeats it: a screen of random static is unpredictable forever, so the intrinsic reward is permanent and the agent stops doing anything else.

Noisy television problem

The problem is general: any stochastic element in the environment, including other agents and sensor noise, produces permanent prediction error. Intrinsic motivation based on prediction error conflates what the agent has not learned with what is inherently random.

Corrections reward reduction in error rather than error itself, use information gain over model parameters, or use a deterministic target as random network distillation does.

Hard exploration benchmarks

Montezuma’s Revenge is the standing benchmark: the first reward, for collecting a key, comes only after a long sequence of precise moves through the opening room, and the next requires carrying that key to a door. Random network distillation reached human-level scores via a novelty bonus. Go-Explore archived reached states and returned to promising ones directly; its first version used a deterministic emulator to reset, a capability unavailable in most settings. Demonstrations solved it most cheaply, with a single human trajectory. The general exploration problem was not solved.

Language model reinforcement learning

Exploration is largely sidestepped in language model RL. The pretrained policy already proposes fluent, task-relevant continuations concentrated on a tiny subset of $|V|^k$ possible sequences, so the first reward is reachable in the first batch.

The cost: the policy explores only within the pretrained distribution’s support. Behaviors the base model never produces are unreachable regardless of reinforcement. The diversity of the initial policy sets a ceiling on what the reinforcement stage can find.

Offline reinforcement learning

Learning a policy from a fixed dataset of logged interactions with no further environment access.

Constrain or penalize the learned policy to stay near the behavior policy that generated the data, preventing value extrapolation errors.

The Bellman target includes out-of-distribution actions whose values are fabricated by the approximator; the max selects the worst errors.

The big idea

Logged production data, demonstrations, or any setting where online interaction is expensive or unsafe. Requires data from a reasonable policy.

The naive approach, running an off-policy algorithm on the dataset, fails for a specific reason. The Bellman target contains $\max_{a'} Q(s', a')$, and the maximization ranges over all actions including ones the dataset never contains at that state.

The value estimate for an absent action is whatever the function approximator extrapolated. The maximum selects the largest such extrapolation, and the estimates diverge upward.

Distributional shift

Distributional shift is the single obstacle. The dataset came from some behavior policy, the learned policy is different, and every estimated quantity is an expectation under the learned policy computed from behavior-policy samples. Where they overlap the estimate is supported by data; where they diverge it is extrapolation.

Conservative and pessimistic methods

Conservative and pessimistic methods respond by penalizing value estimates outside the data support.

Method family	Mechanism
Conservative Q-learning	Pushes down values for actions sampled from the learned policy and pushes up values for actions present in the data, yielding a lower bound on true value
Policy-constrained methods	Restrict the learned policy to stay close to the behavior policy by an explicit divergence penalty
Implicit methods	Avoid querying out-of-distribution actions at all by using an expectile or quantile regression on in-data actions

All three encode the same principle, which is the reverse of the online case: online methods are optimistic because they can test their optimism, and offline methods must be pessimistic because they cannot.

Behavior cloning baseline

Behavior cloning is the baseline and is hard to beat. It is supervised learning of the state-to-action mapping, ignoring rewards, making no value estimates and so having no extrapolation problem. Comparisons repeatedly find it competitive with or better than offline reinforcement learning when the data comes from a good policy.

Offline reinforcement learning beats it under identifiable conditions: data from a mediocre or mixed policy, so there is room to improve; good segments from different episodes that stitch into a better whole, which cloning cannot do; and reward information distinguishing good from bad behavior, which cloning discards. Filtered cloning on high-return trajectories captures part of the gain.

Off-policy evaluation

Off-policy evaluation estimates how a proposed policy would perform from logged data. Importance weighting is the unbiased estimator, reweighting each trajectory by the ratio of its probability under the target policy to that under the behavior policy. Weight variance grows exponentially in the horizon, since the trajectory weight is a product of $H$ per-step ratios.

The estimate is dominated by a few trajectories with enormous weights and is useless beyond short horizons. Per-step weighting, clipping, and self-normalization trade variance for bias; doubly robust estimators combine importance weighting with a learned value model and are consistent if either is correct. None repeals the exponential.

Application to language models

The application to language models is direct rather than analogical. Preference data is a fixed offline dataset from an earlier policy, and direct preference optimization inherits everything above. The support constraint is operative: the objective is determined only where the dataset has preference pairs, and the closed-form relation between reward and policy says nothing off that support.

Direct preference optimization never samples from the policy it is training, so it sees only the chosen and rejected completions in the fixed dataset and gets no feedback about anything else. The loss raises the probability of the preferred response relative to the dispreferred one, and outside the pairs it was shown it constrains nothing, so the policy is free to move probability mass onto completions no comparison ever covered. Where those completions are bad, nothing in the objective pushes back.

The observed failure modes match the offline literature: degradation on outputs unlike anything in the preference set, and drift toward the idiosyncrasies of the policy that generated the pairs. Regenerating preference pairs from the current policy converts the problem back to an online one, at the cost of the labeling loop the offline formulation was adopted to avoid.

The reward-model pipeline that direct preference optimization replaces samples fresh completions from the current policy and scores them, so it discovers where the policy has drifted and corrects it, at the cost of the sampling loop and the reward model. Without that feedback, direct preference optimization depends on preference data covering the outputs the deployed policy will actually produce, and the policy constraints described above penalize movement into regions the dataset does not cover.

Reward design, shaping, and hacking

The problem of specifying an objective such that maximizing it produces the intended behavior, and the failure modes when it does not.

Sparse rewards signal only at the outcome. Dense rewards guide each step. Shaping adds terms that preserve the optimal policy.

Any reward is a proxy for the true goal; strong optimization finds the point where the proxy most exceeds the truth.

The big idea

Every RL application. Verifiable rewards from checkers shrink the proxy problem where available; learned reward models do not.

A sparse reward signals only at the outcome: easy to specify correctly, hard to learn from. A dense reward signals at every step: fast to learn, hard to specify, because every intermediate signal is a guess about progress and each guess can reward something other than the goal. The field prefers sparse verifiable rewards where a checker exists.

Potential-based shaping

The modified reward is $R'(s,a,s') = R(s,a,s') + \gamma \Phi(s') - \Phi(s)$. Ng, Harada, and Russell proved in 1999 that this preserves the optimal policy exactly and is the only additive form with that guarantee. The added terms telescope along any trajectory, so their discounted sum collapses to $-\Phi(s_0)$ plus a discounted terminal term, a quantity that does not depend on the path taken. A distance-to-goal potential speeds learning without distorting the optimum. The condition people violate: shaping that depends on the action taken or rewards a behavior directly loses the guarantee.

Goodhart and reward hacking

Goodhart’s law: when a measure becomes a target, it ceases to be a good measure. Any reward is a proxy correlated with the true goal on the designer’s intended distribution. Optimization searches for the point maximizing the proxy, which is where the proxy most exceeds the truth. The stronger the optimizer, the further from the region where the correlation held.

Documented hacking cases

In a boat racing game, a policy trained on the game’s own score learned to circle in a lagoon collecting regenerating powerups, scoring on average about 20 percent higher than human players without finishing the race. In physics simulations, agents have exploited collision handling for locomotion without valid gaits and flipped blocks to satisfy a stacking reward. In evaluation settings, policies have produced output triggering keyword checks or code special-casing test inputs.

Reward model overoptimization

As the policy optimizes against a learned reward model, measured reward rises monotonically while true quality (held-out human raters or a stronger model) rises then falls. The turning point is predicted by divergence from the reference policy: true reward rises then declines as a function of $\sqrt{D_{KL}}$, with peak location depending on reward model size and preference data quantity.

Measured reward is not a training progress indicator past the overoptimization turning point. A held-out evaluation independent of the reward model is required to locate the peak, and larger reward models push it further out without removing it.

Verifiable reward

Score against a checker: run the unit tests, execute the program, verify the proof, check the answer.

The reward is then a fact about the output rather than a prediction about how a human would rate it. With a proof checker or an exact answer there is no proxy to diverge from the truth; with unit tests the proxy shrinks to the tests themselves, as the next subsection explains. This is why the strongest recent results are concentrated in mathematics, competitive programming and formal verification.

Where checkers exist

A checker is available for correctness, not for helpfulness, tone, judgment, or safety. Reward hacking against checkers still happens: solutions pass the tests without solving the problem. Test coverage becomes the specification and inherits the specification problem one level down.

Credit assignment over long horizons

The problem of attributing a scalar outcome to the individual steps in a long trajectory.

Discounting weights recent steps more. Process supervision scores intermediate steps. Hierarchical methods shorten the effective horizon.

A single outcome shared by many steps provides almost no gradient per step; the signal-to-noise ratio degrades with trajectory length.

The big idea

Any task with sparse terminal reward. The binding constraint on long-running agents, and the reason decomposition into subtasks helps.

Credit assignment: a trajectory of thousands of steps ends with one scalar and nothing says which steps earned it. Every action receives the same signal, so a good move early and a bad move late are reinforced identically. The learner recovers each step’s contribution from many trajectories, and the number required grows with length.

Credit assignment mechanisms

Discounting is the crude solution. Weighting rewards by $\gamma^t$ makes steps near the reward matter more than distant ones, which supplies a coarse attribution and bounds the variance.

Discount factor	Effective horizon	Consequence
$\gamma = 0.99$	~100 steps	An action whose payoff arrives 500 steps later is discounted to under one percent of its value
$\gamma = 0.999$	~1000 steps	Better for long-horizon but destroys variance reduction and slows convergence

Long-horizon problems need $\gamma$ near one to represent the objective correctly, and $\gamma$ near one destroys the variance reduction. There is no setting that solves both.

Variance and sample complexity

The variance of the policy gradient estimate grows with horizon length, setting a ceiling on episode length. The estimator sums a per-step term over the trajectory, each carrying noise from sampled actions and stochastic returns, so variance grows roughly linearly in the horizon and standard error as its square root.

Trajectories needed for a fixed signal-to-noise ratio grow linearly in the horizon, and each costs linearly more, so total sample cost grows quadratically. Methods that work at a hundred steps degrade at a thousand and fail at ten thousand, because the sample requirement outruns the budget.

Process supervision

Process supervision scores intermediate steps rather than only the final answer. A reward model judging each step of a solution, rather than only whether the answer was right, picked correct solutions more often than an outcome reward model when reranking the same samples on mathematical reasoning (Lightman et al., 2023), though that study did not train the policy with reinforcement learning. DeepSeek-R1, trained with rule-based outcome rewards, reported that process reward models did not repay their overhead in large-scale reinforcement learning and invited reward hacking. The case for process supervision rests on three mechanisms:

Mechanism	How it helps
Solves credit assignment directly	Each step gets its own signal rather than sharing the outcome
Eliminates a specific failure mode	A wrong path reaching a right answer no longer gets fully reinforced
Denser signal	Reduces the sample requirement described above

The cost is that step-level labels are far more expensive to collect than outcome labels; automated approaches infer step labels from whether a step can be completed to a correct answer.

Hierarchical decomposition

Hierarchical approaches shorten the effective horizon by acting at a coarser grain. An option is a temporally extended action with an initiation set, internal policy and termination condition; a policy over options decides at that granularity, so a thousand-step task becomes twenty decisions. Credit assignment is divided rather than solved.

The persistent difficulty is discovering options automatically: hand-specified options work and defeat the purpose, and no learned-option method reliably finds good decompositions without domain knowledge. In current agent systems the structure is supplied by construction, since tool calls, subagent delegation and planning steps are hand-designed options.

Binding constraint on agents

Credit assignment is the binding constraint on long-running agents. On reliability, per-step success $p$ over $n$ steps gives $p^n$: 99 percent per step is 60.5 percent over 50 steps and 36.6 percent over 100. On learning, the signal available to improve step reliability degrades over the same horizon, so where improvement matters most the signal is weakest.

Shorten the horizon by decomposing into checkpointed subtasks. Supply intermediate verification. And prefer domains with checkers, because a checker converts a long-horizon credit assignment problem into a sequence of short verifiable ones.