08 — Reinforcement Learning

Reinforcement learning (RL) is the branch of machine learning where a program learns by acting and being scored, rather than by being shown labelled right answers.

This chapter assumes no prior RL exposure. Every term is defined where it first appears. By the end you should be able to say what each standard algorithm computes, derive the two results everything else is built on, state the assumptions each method quietly requires, and recognise when the problem in front of you is not an RL problem at all — which is the part that decides real projects.

What goes in

The input is a stream of experience, recorded as four-part tuples called transitions: (s, a, r, s'). Read that aloud as “state s, the action a taken in it, the reward r that action paid, and the next state s' the world moved to.”

• A state s is whatever the learner can see about the situation it is in — the screen pixels, the user’s request, the robot’s joint angles.
• An action a is one of the choices available to it.
• A reward r is a single number scoring the immediate consequence. No explanation attached, just a number.
• The next state s' (read “s prime”) is where the world went.

A concrete one, from a game of Pac-Man: s = the current board, a = up, r = +10 because a pellet was eaten, s' = the board one tick later. That is the whole record. Notice what is missing: nothing anywhere in the data says which action should have been taken. There are no labels.

What comes out

The output is a policy, written pi(a|s) and read “pi of a given s” — a rule that maps a state to a choice of action, usually as a probability for each available action.

pi is the Greek letter pi, used here purely as a name for the policy. It is unrelated to 3.14159.

Feeding a state into the policy and reading out an action is the entire deployed system. Everything else in this chapter is machinery for producing a good policy.

Why this is harder than supervised learning

The score arrives late and lumped together.

Supervised learning is handed the right answer for each input. Reinforcement learning is handed a number, late, for a whole sequence of choices, and must work out which choice earned it. That is the credit assignment problem.

Every algorithm in this chapter is an answer to one question: how do you get an unbiased, low-variance estimate of “was that action good?” from data that only ever tells you what happened next?

Two words in that question carry weight for the rest of the chapter. Unbiased means the estimate is right on average, rather than systematically too high or too low. Low-variance means it does not swing wildly from one sample to the next. You want both, and most of the field is trades between them.

The two derivations to know cold

Two proofs carry this chapter, and both live in Policy gradients the derivation that matters:

1. The log-derivative trick, which produces REINFORCE — the original policy-gradient algorithm.
2. The proof that a baseline cuts variance without touching the expectation (Why the baseline is unbiased the proof). A baseline is a reference value subtracted from the score before it is used, so the learner reacts to “better than expected” rather than to the raw number.

If you can do those two on a whiteboard, most of the rest is bookkeeping.

The warning to carry throughout

Every method below is a theorem about an idealised world, and the theorem’s assumptions are not free.

The world is assumed to be memoryless in a specific sense, to hold still while you learn, and to be honestly described by the reward number. Real problems violate all three.

The assumptions and what breaks when they fail collects the assumptions and their failure modes in one place. Each section flags its own as it goes.

1. The MDP, and what gamma actually controls

The formal picture of an RL problem is the Markov Decision Process, abbreviated MDP. Of its five ingredients, one — the discount factor gamma — deserves most of the attention, because gamma is the single setting that most often silently redefines the problem you thought you were solving.

The loop

The diagram below is two boxes passing messages back and forth. Read it clockwise starting at the agent.

The agent box holds the policy pi(a|s) — “pi of a given s,” the probability of taking action a when in state s. This is the thing that learns and chooses.

The environment box is everything else: the game, the market, the user, the physics. It is summarised by P(s'|s,a) — “P of s-prime given s and a,” the probability that taking action a in state s lands you in state s'.

Each tick of the loop, the agent sends an action a_t (“a at time t”). The environment sends back a reward r_t and the next state s_(t+1) (“s at time t plus one”). Then it repeats.

flowchart LR
    A["Agent<br/>pi(a given s)"] -->|"action a_t"| E["Environment<br/>P(s' given s,a)"]
    E -->|"reward r_t"| A
    E -->|"state s_t+1"| A

    style A fill:#40916c,color:#fff
    style E fill:#1d3557,color:#fff

The five ingredients

A Markov Decision Process (MDP) is that loop written down precisely, as five pieces bundled together — the tuple (S, A, P, R, gamma). “Tuple” here just means “this fixed list of ingredients, in this order.”

Each ingredient carries an assumption. The third column of the table is the one to read twice: those assumptions are what break in production, and the last section of this chapter is entirely about what happens when they do.

Three of those words need unpacking.

The Markov property is the claim that the current state is a sufficient summary of history: knowing s_t tells you as much about what happens next as knowing the entire past would. It is what licenses every algorithm below to store one number per state instead of one number per possible history.

The transition kernel P is the environment’s rulebook. “Kernel” is the standard name for a function that hands back a probability distribution rather than a single value — here, a distribution over next states.

Stationary means that rulebook does not change over time. The same action in the same state has the same distribution of consequences in month six as in week one.

Return: what you are actually maximizing

Rewards accumulate into a return. The return from time t, written G_t (“G at time t”), is the discounted sum of everything collected from t onward:

G_t = r_t + gamma*r_(t+1) + gamma^2*r_(t+2) + ...

That is the reward now, plus gamma times the reward next step, plus gamma squared times the one after, and so on forever. The discount factor gamma is a number between 0 and 1 that shrinks each step of delay.

Substitute real numbers. Suppose an episode pays r_0 = 1, r_1 = 0, r_2 = 5, then ends, with gamma = 0.9:

G_0 = 1 + 0.9*0 + 0.81*5 = 1 + 0 + 4.05 = 5.05
G_1 =     0 + 0.9*5      = 4.50
G_2 =           5        = 5.00

The same +5 is worth 5.00 when you are standing next to it and 4.05 when it is two steps away. That shrinkage is the only thing gamma does.

The goal of the whole enterprise is to maximize E[G_0], read “the expected return from the start.” E[...] denotes an expectation — the average over all the randomness in the policy and the environment.

The distinction to hold on to: r is one step’s payment, G is the whole discounted stream. Algorithms differ largely in how they estimate G without waiting to observe all of it.

Effective horizon, derived

Here we turn gamma from a tuning knob with no intuition attached into a number of steps you can count, which is the form in which it is actually decidable.

Discounting is normally justified as “the future is uncertain.” The operational fact is simpler. Add up the weight the return places on all future steps and you get a geometric sum with a closed form:

SUM_{t=0..inf} gamma^t  =  1 / (1 - gamma)

Read that as “the sum of gamma to the power t, for t from zero to infinity, equals one over one minus gamma.”

That number is the effective horizon: the number of steps’ worth of reward the objective actually contains. At gamma = 0.99, 1/(1 - 0.99) = 1/0.01 = 100, so you are optimizing something that behaves like a 100-step problem no matter how long the episode really is.

Two other readings of the same constant are useful:

• The half-life, ln(0.5)/ln(gamma) — the step at which a reward is worth half its face value.
• The 1% horizon, ln(0.01)/ln(gamma) — the step past which rewards are numerically invisible.

ln is the natural logarithm. Both expressions just invert gamma^t = 0.5 and gamma^t = 0.01 for t. At gamma = 0.9: ln(0.5)/ln(0.9) = -0.693/-0.105 = 6.6 steps, and ln(0.01)/ln(0.9) = -4.605/-0.105 = 43.7 steps.

The table below runs those three formulas across the gamma values you will actually meet. The last column is the largest total return possible when every single-step reward is at most 1 in magnitude, written |r| <= 1. It equals the effective horizon, and it tells you the scale the value estimates in Value functions q functions bellman will live on — at gamma = 0.99 a value of 80 is plausible and a value of 8000 means something has broken.

A reward that arrives after the 1% horizon cannot be learned, because its contribution to the gradient is smaller than the gradient noise.

At gamma = 0.9, a reward 100 steps away is discounted by 0.9^100 = 2.7e-5. So a +1 payoff a hundred steps out is worth 0.000027 at decision time. An agent optimizing that objective will trade it away for 0.001 of immediate reward — and given the objective it was handed, it is correct to do so. The problem is the objective, not the agent.

Worked example: what gamma chooses

The exchange rate between “now” and “later” is easy to make concrete.

Give the agent exactly two options from the start state. It can take a reward of +2 immediately, or it can walk 5 steps and collect a reward of +10. Which one it prefers depends entirely on gamma, and you can solve for the gamma at which it is indifferent:

V(shortcut) = 2
V(long path) = gamma^5 * 10

break-even:  gamma^5 * 10 = 2   ->   gamma^5 = 0.2   ->   gamma = 0.2^(1/5) = 0.725

Below that break-even the agent grabs the +2; above it, the agent walks. Same environment, same rewards, opposite behaviour:

Gamma is not a preference, it is a horizon, and setting it below the horizon of your reward silently redefines the problem.

The other half of the trade

A long horizon is not free: raising gamma also makes learning slower, by a factor you can compute.

Gamma is the contraction factor of the Bellman operator — the update rule derived in Value functions q functions bellman that repeatedly refines a value estimate. “Contraction factor” means each application shrinks the remaining error by that factor.

So value iteration’s error shrinks by exactly gamma per sweep, where a sweep is one pass of the update over every state. Reducing an initial error of 100 down to 0.1 means shrinking it by a factor of 1,000, which takes ln(0.001)/ln(gamma) sweeps:

gamma = 0.9   ->   ln(0.001)/ln(0.9)  = -6.908 / -0.1054 = 66 sweeps
gamma = 0.99  ->   ln(0.001)/ln(0.99) = -6.908 / -0.01005 = 687 sweeps

Raising gamma lengthens the horizon you can see and multiplies the number of backups needed to see it.

The assumption underneath the horizon arithmetic

The assumption to keep visible here is stationarity.

The effective-horizon arithmetic assumes the environment’s rules stay fixed over those 1/(1-gamma) steps. If they drift — a recommender whose users change taste month to month, a market that reprices — then a gamma = 0.99 objective is averaging over a hundred steps of a world that no longer exists. The “correct” long-horizon answer is then a fit to stale physics.

Non-stationary problems are usually served by a shorter horizon than the theory recommends, precisely because the theory’s premise has expired.

2. Value functions, Q functions, Bellman

Every RL algorithm is built out of three bookkeeping quantities — the value function, the Q function, and the advantage — plus one recursion that lets you compute them without ever simulating the future to the end.

V, Q, and A

The problem all three solve is that the return G_t is only knowable after the fact, and it is random. So instead of the return itself, we work with its average.

• A value function V^pi(s), read “V-pi of s,” answers: “starting in state s and behaving according to policy pi forever after, what return do I get on average?”
• A Q function Q^pi(s,a), read “Q-pi of s and a,” answers the same question for the case where the very first action is forced to be a and pi takes over afterwards. So Q scores an action, which is what you need in order to choose one.
• The advantage A^pi(s,a) is their difference: how much better this action is than what the policy would have done on average from that state.

The superscript pi on all three is a reminder that these are properties of a specific policy, not of the environment alone. Change the policy and all three change.

V^pi(s)   = E_pi[ G_t | s_t = s ]                 "how good is this state under pi"
Q^pi(s,a) = E_pi[ G_t | s_t = s, a_t = a ]        "how good is this action, then pi"
A^pi(s,a) = Q^pi(s,a) - V^pi(s)                   "how much better than average"

The vertical bar inside the brackets is read “given.” So E_pi[G_t | s_t = s] is “the expected return, given that we are in state s at time t, taking actions from pi.”

A quick substitution. Suppose in state s the policy picks left half the time and right half the time, Q^pi(s, left) = 8 and Q^pi(s, right) = 2. Then V^pi(s) = 0.5*8 + 0.5*2 = 5, and the advantages are A(s, left) = 8 - 5 = +3 and A(s, right) = 2 - 5 = -3.

Notice what happened to those two advantages when you average them under the policy: 0.5*(+3) + 0.5*(-3) = 0. That is not a coincidence, it is the advantage’s defining property:

E_{a~pi}[ A^pi(s,a) ] = 0

Read that as “the expectation of the advantage, over actions a drawn from pi, is zero.” The advantage is centered by construction — averaged over the policy’s own choices, no action is better than average.

That zero-mean property is exactly what will make the advantage a low-variance learning signal in Policy gradients the derivation that matters.

The Bellman equations

The Bellman equations are the recursion that makes V and Q computable without simulating to the end of time.

They are the return definition split after one step: take the immediate reward, then treat everything after it as “the value of wherever you land, discounted once.” Three versions follow, and the only difference between them is what they assume about the next action.

V^pi(s)   = SUM_a pi(a|s) [ R(s,a) + gamma * SUM_s' P(s'|s,a) V^pi(s') ]
Q^pi(s,a) = R(s,a) + gamma * SUM_s' P(s'|s,a) SUM_a' pi(a'|s') Q^pi(s',a')     <- expectation over a'
Q*(s,a)   = R(s,a) + gamma * SUM_s' P(s'|s,a) max_a' Q*(s',a')                  <- max over a'

The notation, symbol by symbol. SUM_a means “sum over all actions a”. SUM_s' means “sum over all next states s'”. max_a' means “take the largest value over the choices of next action a'”. The starred Q* (read “Q-star”) is the optimal Q function — the one belonging to the best possible policy, rather than to some particular pi.

The first two lines say “average over what the policy would do next.” The third says “assume the best available action is taken next.”

Substitute numbers into the first line. Take a state s where the policy picks left and right with probability 0.5 each, gamma = 0.9, and both actions move deterministically: left pays R = 1 and lands in a state worth V = 10, right pays R = 0 and lands in a state worth V = 4.

V^pi(s) = 0.5 * [ 1 + 0.9*10 ]  +  0.5 * [ 0 + 0.9*4 ]
        = 0.5 * 10.0            +  0.5 * 3.6
        = 5.0 + 1.8 = 6.8

The two branch values are 10.0 and 3.6. The first line combines them by averaging under the policy, giving 6.8. Swap in the third line’s combination rule — max instead of the average — and the same two branches give max(10.0, 3.6) = 10.0 instead.

That gap, 6.8 against 10.0, is the cost of a policy that flips a coin where an optimal one would not.

The difference between the last two lines — expectation over a' versus max over a' — is the whole of On policy vs off policy the mechanism.

Every one of these equations is only true because of the Markov property. Splitting the return after one step and replacing the tail with V(s') is legitimate exactly when s' summarises everything that matters about how you got there.

In a problem where it does not — a card game where the discard pile is unobserved, a dialogue where the state omits what was said three turns ago — these equations are still solvable, but what they converge to is not the value of anything.

Value iteration, by hand

Value iteration is the simplest algorithm that uses the Bellman equation: guess all the values, apply the equation everywhere, repeat. Working one example by hand shows exactly how fast information travels, which turns out to be the reason a whole class of RL problems is hard.

Set up the smallest environment that shows the effect: a chain of four states, 1 -> 2 -> 3 -> 4.

• State 4 is terminal, meaning the episode ends when the agent reaches it. Entering it pays a reward of +1.
• Two actions, right and left, move deterministically — no randomness in where you land.
• All other rewards are 0.
• gamma = 0.9.

Start from V = 0 everywhere and repeatedly apply the update V(s) <- max_a [R + gamma*V(s')], where <- means “overwrite the left side with the right side.”

Applying it synchronously means every state is updated from the previous sweep’s values, so within one sweep no state sees another’s fresh number.

The table traces four sweeps. Watch the 1.000 appear at the right edge and then crawl leftward, one column per sweep:

sweep   V(1)    V(2)    V(3)     what just happened
  0     0.000   0.000   0.000
  1     0.000   0.000   1.000    the terminal reward is discovered
  2     0.000   0.900   1.000    it propagates back one state
  3     0.810   0.900   1.000    one more state
  4     0.810   0.900   1.000    converged

Here is the arithmetic behind each new number:

sweep 1:  V(3) <- max( right: 1 + 0.9*V(4)=0 ,  left: 0 + 0.9*V(2)=0 ) = 1.000
sweep 2:  V(2) <- max( right: 0 + 0.9*V(3)=0.9,  left: 0 + 0.9*V(1)=0 ) = 0.900
sweep 3:  V(1) <- max( right: 0 + 0.9*V(2)=0.81, left: stay, 0        ) = 0.810

A backup is one application of the update to one state. The name comes from the fact that it pushes information backwards, from a successor state to its predecessor.

Each backup moves information exactly one state backwards. That is the mechanical reason sparse-reward, long-horizon tasks are hard.

A sparse reward is one that is zero almost everywhere and nonzero only at a goal. When the goal is far away, the reward has to crawl its way back across the whole state space, one sweep per step of distance, before any earlier action’s value is anything but zero.

Notice what that means for the agent in sweeps 0 and 1: from state 1, every action still looks exactly as good as every other, because they all evaluate to 0. The agent gets no useful gradient at all until the wave arrives. It is not learning slowly, it is learning nothing.

3. Model-based vs model-free

The first big fork in the field is whether the agent bothers to learn how the world works, or only learns what to do. That one distinction decides sample efficiency, compute at decision time, and which way the method fails.

A model means a learned copy of the environment’s rules — an approximation of P(s'|s,a) and R(s,a) that the agent can query without touching the real world.

Model-based methods learn one and then plan with it, meaning they simulate candidate futures internally before committing to an action.

Model-free methods never build one. They learn values or a policy directly from experience and let the environment stay a black box.

The table compares them on five axes. Don’t worry about the names in the last row yet: the model-free four are Q-learning from On policy vs off policy the mechanism, the deep Q-network (DQN) of Dqns two tricks and why each is necessary, and REINFORCE and proximal policy optimization (PPO) from Policy gradients the derivation that matters and Actor critic a2c and ppo. Every one of them is derived later in this chapter. The row to read closely is “Failure mode.”

Why compounding error is the whole story

Planning H steps through a learned model multiplies H model errors together, because each simulated step feeds a slightly wrong state into the next prediction. A model that is right 99% of the time per step is right 0.99^50 = 0.61 of the time over a 50-step plan — so nearly 40% of your plan is fiction.

Model-based methods take one of two escapes from that.

Escape 1: keep H short. This is model predictive control (MPC). It plans a handful of steps ahead, executes only the first action, then re-plans from the state the world actually reached. Errors never get a chance to accumulate, because the plan is thrown away and rebuilt against reality every step.

Escape 2: model only what matters. Learn the model in a latent space — an internal compressed representation rather than raw observations — chosen so that only value-relevant detail is modeled. That is MuZero’s trick, MuZero being DeepMind’s planning agent that learns its model end-to-end: don’t predict pixels, predict the things that predict returns.

The other two names in the table are of the same family. Dyna interleaves real experience with imagined experience from a learned model. AlphaZero plans by tree search over a known rulebook (board games) rather than a learned one.

The assumption underneath model-based methods

Every model-based method assumes the environment’s rules are learnable and stable.

Against a fixed simulator that holds. Against a market, a security adversary, or a population of users whose behaviour shifts, the learned P decays after training.

A planner is more exposed to that decay than a model-free learner, because it compounds the stale rulebook H times per decision instead of once.

4. On-policy vs off-policy — the mechanism

Whether an algorithm can reuse old data decides, in practice, how much it costs to train. The whole difference lives in one symbol of one equation, and everything else follows from it.

The vocabulary

• The behavior policy, written mu (the Greek letter mu), is the policy that collected the data — the one that was actually running when the transitions were recorded.
• The target policy is the one you are trying to learn about.
• On-policy methods require these two to be the same. They can only learn from data their current policy generated, so every batch is thrown away after one update.
• Off-policy methods allow them to differ, which means old data, other agents’ data, and human demonstrations are all usable.

The one symbol that separates them

Two canonical algorithms differ in exactly one symbol.

SARSA is named after the five things its update touches, (s, a, r, s', a') — state, action, reward, next state, next action. Q-learning learns the optimal Q function directly.

In both, alpha is the learning rate (how far each update moves). The bracketed quantity is the temporal-difference error: the gap between what we currently believe Q(s,a) is and the better one-step estimate r + gamma*(value of where we landed).

SARSA        (on-policy):   Q(s,a) <- Q(s,a) + alpha * [ r + gamma*Q(s',a') - Q(s,a) ]
Q-learning  (off-policy):   Q(s,a) <- Q(s,a) + alpha * [ r + gamma*max_b Q(s',b) - Q(s,a) ]

In SARSA, a' is the action the behavior policy actually took next. It is a sample from the policy that generated the data — you have to look it up in the log.

In Q-learning, max_b Q(s',b) — “the largest Q value over all actions b available in s'” — is computed from the current table at update time. It never consults the data for the next action at all.

That one difference decides everything about data reuse, and the argument is worth stating in full:

A transition tuple (s, a, r, s') records only properties of the environment. Nothing in it depends on the policy. SARSA’s target additionally needs a', which is a property of the policy that was running when the data was collected. Q-learning can learn from a replay buffer because its target is reconstructed from current parameters; SARSA cannot, because its target is baked into the stored data and evaluates whatever policy wrote it.

A replay buffer is a large store of past transitions — typically the last million — that the learner samples minibatches from at random, instead of consuming experience in the order it arrived.

Replay a buffer through SARSA and you converge to Q^mu: the value of the stale behavior policy mu. Not Q^pi for your current policy, and not Q*. You have carefully learned the value of a policy you already abandoned.

The diagram below traces the same argument. One stored transition feeds both targets. Follow the arrows into each: the Q-learning box takes only the transition, while the SARSA box needs a second input — the stored next action a', written by the old policy. That extra arrow is the entire difference.

flowchart TD
    T["Stored transition<br/>s, a, r, s'"] --> Q["Q-learning target<br/>r + gamma * max_b Q_theta(s',b)"]
    T --> S["SARSA target<br/>r + gamma * Q(s', a')"]
    A["Stored next action a'<br/>written by the OLD policy"] --> S
    Q --> OK["Valid for any behavior policy<br/>replay buffer works"]
    S --> NO["Evaluates the policy that<br/>generated a' — stale data biases it"]

    style OK fill:#2d6a4f,color:#fff
    style NO fill:#9d0208,color:#fff

What off-policy does not buy you

Being off-policy is a weaker guarantee than it sounds, and people over-claim it in two places.

The target is policy-independent. The state-action distribution you minimize error over is not. You are still fitting Q on whatever (s,a) pairs the behavior policy happened to visit, and two consequences follow.

Consequence 1: coverage is still the behavior policy’s problem

If mu never takes action a in state s, then Q(s,a) is not an estimate at all. It is an extrapolation from a neural network into a region it has no data for.

Worse, max_b will happily select that extrapolation, precisely because an unconstrained guess is often optimistically large. The max acts as a filter that finds the network’s most confident hallucination and treats it as a target.

This is the core failure of offline RL — the setting where you must learn from a fixed logged dataset with no ability to try anything new.

Consequence 2: the deadly triad

The deadly triad is three ingredients that are each individually safe, and safe in any pair, but which can make the learning process diverge when all three are present:

1. Function approximation — using a neural network instead of one table entry per state, so an update to one state changes the estimate for others.
2. Bootstrapping — building the training target out of the model’s own current predictions, as the gamma*max_b Q(s',b) term does.
3. Off-policy training — the subject of this section.

The mechanism is that the target is fit under one distribution and evaluated under another.

The regression is fit by minimizing squared error over the (s,a) pairs the behavior policy mu visited. That is the distribution the loss averages over.

The target gamma*max_b Q(s',b) is evaluated at the successor actions the greedy target policy would take. That is a different distribution, and one mu may barely have sampled.

Fit in one place, evaluated in another: the update is no longer guaranteed to shrink the error.

What exactly was lost

Be precise about what that costs, because a guarantee you had in The mdp and what gamma actually controls is gone.

In §1, the Bellman operator applied to an exact table is a contraction in max-norm by exactly gamma. That is a hard, unconditional, quantified statement about an operator: apply it, and the worst-case error over all states shrinks by a factor of gamma. Guaranteed.

Here there is no such object. The fitted update composes the Bellman backup with a least-squares projection taken under the behavior distribution, and that composition is not proved to shrink any norm the algorithm controls.

So the two uses of the word “contraction” are different claims about different objects. §1’s is a property that holds. This is the absence of a comparable property, and the shared word is the only thing they have in common.

An update with no guarantee of shrinking the error can grow it — and grow it again on the next step, and the next. Dqns two tricks and why each is necessary shows exactly what that looks like in a training log.

Cliff walking, the classic separation

The cleanest demonstration that “optimal” and “best for you” are different objectives is a small gridworld, and it is worth being able to draw it from memory.

Picture a 4x12 grid with a cliff running along the bottom row. The agent starts at the bottom-left and must reach the bottom-right.

• Stepping into the cliff costs -100 and teleports the agent back to the start.
• Every ordinary step costs -1, so the agent wants the shortest route.
• The behavior policy is epsilon-greedy at eps = 0.1: it takes what it currently believes is the best action 90% of the time and a uniformly random action the other 10%. That is the simplest way of forcing some exploration.

Two returns are worth distinguishing in the results below. The greedy return is what the learned policy scores with exploration switched off, always taking its best action. The online return is what it scores while still exploring at eps = 0.1 — which is what a system deployed with exploration on actually earns.

                          learned path                 greedy return   online return (eps=0.1)
Q-learning (off-policy)   the cliff edge, 13 steps         -13               -41
SARSA      (on-policy)    the top row, 17 steps            -17               -20

Where the step counts come from

Every ordinary step costs -1, so the greedy return is just the step count negated.

The cliff-edge route runs along the row directly above the cliff: 1 up, 11 right, 1 down — 13 steps, -13.

The top row is three rows up from the start: 3 up, 11 right, 3 down — 17 steps, -17.

SARSA does not retreat by one row; it retreats as far as the grid allows. One row up would be 15 steps and -15, and that is not what it learns. The extra two steps of clearance are what the exploration penalty buys.

Pricing the lie

Q-learning learns the optimal policy. SARSA learns the best policy given that you will keep exploring.

The max in Q-learning’s target assumes the next action is greedy. That is a lie while eps > 0, and the lie has a price you can compute.

P(random action)          = 0.1
P(that random action = down) = 1/4          four actions, chosen uniformly
P(step down on any step)  = 0.1 * 1/4       = 0.025      (2.5%)

P(no fall over 13 steps)  = 0.975^13        = 0.720
P(at least one fall)      = 1 - 0.720       = 0.280      (28%)

expected penalty per episode = 0.28 * 100   = 28
online return              = -13 - 28       ~ -41

That last line is exactly the -41 in the table. The agent hugging the cliff falls off it roughly one episode in four, and each fall costs 100.

If your agent explores in production, SARSA’s pessimism is the correct objective. This is one of the few places where the “worse” algorithm is the right one.

Importance sampling, and why long horizons kill it

There is a general-purpose way to reuse data collected under one policy to evaluate another. It works beautifully for one decision and collapses over a sequence of them.

The technique is importance sampling: if the data came from mu but you want the average under pi, reweight each sample by how much more likely pi was to produce it.

For a single decision this is trivially fine. If mu picked action a with probability 0.2 and pi would have picked it with probability 0.6, that logged sample counts triple: 0.6 / 0.2 = 3.

The trouble starts when you chain decisions. A trajectory, written tau (the Greek letter tau), is one complete run: a sequence of states, actions and rewards from start to finish. Over a trajectory the per-step weights multiply, because the probability of a whole sequence is the product of the probabilities of its steps:

w(tau) = PROD_{t=0..H} pi(a_t|s_t) / mu(a_t|s_t)

PROD means “product over.” Read w(tau) as “the weight of trajectory tau: the product, over every timestep from 0 to the horizon H, of pi’s probability of that action divided by mu’s probability of that action.”

Multiplying H numbers that are sometimes above 1 and sometimes below it produces an enormous range. Suppose each step’s ratio is 0.5 or 2.0 with equal probability, and H = 20:

largest weight    2^20  = 1,048,576       every one of the 20 steps went pi's way
smallest weight   2^-20 = 9.5e-07         every one went mu's way

SPREAD between them  =  2^40  =  1.1e12   twelve orders of magnitude

Read that arithmetic carefully, because the tempting number is the wrong one.

2^20 ~ 1e6 is how far the largest weight sits above 1. The distance from the smallest weight to the largest is that squared: 2^20 / 2^-20 = 2^40 ~ 1e12.

So the gap is a trillion-fold, not a million-fold. In practice a handful of trajectories carry all the weight and everything else contributes nothing, which makes the usable sample size of a logged batch far worse than the friendlier figure suggests.

Trajectory-level importance sampling is unbiased and useless. Every estimate it gives you is right on average and wrong on any batch you can afford to collect. That is exactly the problem PPO’s single-step ratio (Actor critic a2c and ppo) is engineered around.

5. Exploration vs exploitation

Exploitation is taking the action you currently believe is best. Exploration is taking a worse-looking action to learn whether your belief is wrong.

Do only the first and you never discover the better option. Do only the second and you never cash in. Three strategies manage the trade, and each one’s cost can be computed exactly.

The bandit setting

The multi-armed bandit is the clean setting. The name comes from slot machines — “one-armed bandits” — and the image of choosing which of several to play.

• There are K arms.
• Arm a pays a reward with unknown mean mu_a (“mu sub a”).
• You pull one arm per round, for T rounds.

There is no state and no sequence here. The arm you pull does not change what happens next, so all the machinery of the previous sections is unnecessary and only the exploration question remains.

Regret: the scoreboard

Performance is measured by regret: how much total reward you gave up compared with an oracle that knew the best arm from the start. mu* (“mu-star”) is the mean of the best arm.

Regret(T) = T * mu* - E[ SUM_{t=1..T} r_t ]  =  SUM_a Delta_a * E[n_a(T)]

where Delta_a = mu* - mu_a   is the gap, and n_a(T) the pull count

The second form is the one to memorise. The gap Delta_a (“delta sub a”) is how much worse arm a is than the best arm, and n_a(T) is how many times you pulled it. Regret is a sum of gap × pull count, nothing more.

Substitute: three arms with means 0.50, 0.45, 0.30, run for T = 1000 rounds, and suppose you pulled the two losers 100 times each. Regret = 0.05*100 + 0.20*100 = 5 + 20 = 25.

From that form one thing follows immediately: any strategy that pulls a suboptimal arm a constant fraction of the time has regret linear in T. If n_a(T) grows in proportion to T, so does Delta_a * n_a(T).

Linear regret means the loss keeps growing forever at a fixed rate per round rather than levelling off. That single line disqualifies fixed-epsilon exploration before we even analyse it.

Epsilon-greedy

The simplest strategy is to explore at a fixed rate, and its problem is visible directly in the regret formula.

Epsilon-greedy pulls the arm with the best average so far — the empirical best — with probability 1 - eps, and pulls uniformly at random otherwise.

The trouble is that the random pulls never stop. With a fixed eps, each suboptimal arm keeps getting eps/K * T pulls no matter how much evidence has accumulated against it. Plug that pull count into Regret = SUM_a Delta_a * n_a from above:

Regret(T) = (eps/K) * T * SUM_a Delta_a        <- linear in T

At eps = 0.1, K = 3, and T = 1,000,000, an arm you proved was worse a thousand rounds in still gets 0.1/3 * 1e6 = 33,333 pulls.

Decaying eps over time fixes the asymptotic behaviour. The schedule eps_t = min(1, cK/(d^2 t)) gives regret growing like log T instead of T. This is the eps_n-greedy result of Auer, Cesa-Bianchi and Fischer, Finite-time Analysis of the Multiarmed Bandit Problem (Machine Learning 47, 2002) — the same paper that gives UCB1 below.

Read what d is in that schedule, because it is the catch. d is a lower bound on the smallest gap: any d with 0 < d <= min_{a != a*} Delta_a.

So the schedule needs two constants fixed in advance, c and d. And d cannot be checked while the system is running, because checking it would require already knowing the gaps you are running the bandit to learn.

You are stuck between two failures. Set d too large and the bound stops applying. Set it too small and the schedule decays so slowly that you are back to near-linear regret for a very long time.

UCB1, derived

UCB1 stands for upper confidence bound, version 1. It is worth deriving from scratch rather than quoting — the derivation is short and it is the standard interview question.

The idea in one line: act as if each arm is as good as its data allows.

Step 1 — get a confidence width from Hoeffding

To act optimistically you need a confidence width: a number u such that the arm’s true mean is very unlikely to exceed its observed mean by more than u.

That comes from Hoeffding’s inequality, a standard result bounding how far a sample average can stray from the truth. For n independent samples bounded in [0,1] with observed average mu_hat (“mu hat”, where the hat means “estimated from data”):

P( mu_a > mu_hat_a + u )  <=  exp(-2 n u^2)

Read that as “the probability that arm a’s true mean exceeds our estimate by more than u is at most e to the power minus two n u squared.” It shrinks fast in both the sample count n and the width u.

Step 2 — invert it

Call the failure probability we are willing to tolerate delta, set the bound equal to it, and solve for u:

exp(-2 n u^2) = delta
-2 n u^2      = ln(delta)          take logs of both sides
u^2           = ln(1/delta) / (2n) flip the sign using -ln(delta) = ln(1/delta)
u             = sqrt( ln(1/delta) / (2n) )

Step 3 — choose delta so the bound holds everywhere

One application of Hoeffding covers one arm at one moment. We need the bound to hold for every arm at every round, so delta cannot be a fixed constant.

The tool is a union bound: the chance that any one of several bad events occurs is at most the sum of their individual chances. There are roughly t rounds times t possible pull counts to cover, so the total failure mass is about t * t * delta, and we need that to stay finite when summed over all t.

Take delta = t^-4 and check:

SUM_t  t * t * t^-4  =  SUM_t t^-2  =  pi^2/6  ~ 1.64      finite

(That pi is the constant 3.14159, not the policy.) Anything much larger than t^-4 and the sum diverges, so the guarantee would not hold.

Step 4 — substitute back

u = sqrt( ln(t^4) / (2n) ) = sqrt( 4*ln(t) / (2n) ) = sqrt( 2*ln(t) / n )

which is exactly UCB1:

a_t = argmax_a [ mu_hat_a + sqrt( 2*ln(t) / n_a ) ]

Read the rule as “at round t, pick the arm that maximizes its observed mean plus the square root of two times the natural log of t, divided by the number of times that arm has been pulled.”

The second term is the exploration bonus, and neither half of its shape is arbitrary:

• It shrinks as 1/sqrt(n_a) because that is exactly how fast a mean estimate concentrates. A standard error is the typical size of the error in an average, and it falls as one over the square root of the sample count.
• It grows in t only as sqrt(ln t), because that is the price of needing the bound to hold at more and more rounds.

Put numbers on it. At round t = 1000, sqrt(2*ln(1000)) = sqrt(13.8) = 3.72. An arm pulled 9 times gets a bonus of 3.72/3 = 1.24; an arm pulled 900 times gets 3.72/30 = 0.12. The barely-tried arm is granted ten times more benefit of the doubt.

UCB’s regret, derived

Having built the rule, we can now bound what it costs — and the bound is the reason UCB is the default recommendation despite losing on short runs.

An arm stops being pulled once its optimistic estimate falls below the best arm’s. That happens roughly when the bonus is smaller than half the gap, and solving that inequality for n_a gives the pull count:

sqrt( 2*ln(T) / n_a ) < Delta_a / 2

2*ln(T) / n_a  <  Delta_a^2 / 4         square both sides
n_a            >  8*ln(T) / Delta_a^2   rearrange

Now feed that into the regret formula from above, Regret = SUM_a Delta_a * n_a. One factor of Delta_a cancels against the Delta_a^2 in the denominator:

Regret = SUM_{a != a*} Delta_a * 8*ln(T) / Delta_a^2  =  SUM_{a != a*} 8*ln(T) / Delta_a

Logarithmic in T, and inversely proportional to the gap. The inverse-gap dependence is the self-balancing part: an arm that is nearly as good gets pulled many times, but each of those pulls costs almost nothing, so the product stays small.

UCB versus epsilon-greedy, in numbers

Take three arms whose true means are 0.50, 0.45 and 0.30. The gaps against the best arm are 0.05 and 0.20. Substitute those into both regret expressions:

UCB1 bound   = 8*ln(T) * (1/0.05 + 1/0.20) = 8*ln(T) * (20 + 5) = 8*ln(T) * 25 = 200*ln(T)
eps-greedy   = (0.1/3) * T * (0.05 + 0.20) = 0.0333 * T * 0.25   = 0.00833 * T

The table evaluates both across five orders of magnitude of T. Read the columns, not the rows: one grows by a factor of ten every line, the other by about 460 in total.

The crossover is near T = 3e5, from solving 0.008333*T = 200*ln T — at T = 3e5 the left side is 2,500 and the right is 2,522.

Say both halves of this out loud: UCB’s bound is loose and epsilon-greedy genuinely wins at small T, but one column is linear and the other is logarithmic, so the ordering is settled for any long-running system.

Thompson sampling

The third strategy replaces the confidence bound with an act of imagination, and it is usually the one to reach for in production.

Thompson sampling keeps a posterior over each arm’s mean — a probability distribution representing what you currently believe the mean could be, given the data so far. (Its counterpart is the prior, what you believed before seeing any data.)

The algorithm is two steps per round:

1. Draw one random value from each arm’s posterior.
2. Pull the arm whose draw came out highest. (argmax means “the argument that maximizes” — which arm, not the value.)

That is the whole thing. There is no schedule and no bonus term.

For rewards that are simply success-or-failure — Bernoulli rewards, like a click or no click — the natural posterior is a Beta distribution, whose two parameters are counts of successes and failures:

posterior for arm a  =  Beta(1 + successes_a, 1 + failures_a)

Why no exploration schedule is needed

Work two arms with very different amounts of evidence behind them.

Arm A: 60 successes in 100 pulls, so the posterior is Beta(1+60, 1+40) = Beta(61,41). Its mean is 61/102 = 0.598 and its standard deviation is 0.048. (sd, the standard deviation, is the typical spread of the belief.)

Arm B: 5 successes in 10 pulls, so the posterior is Beta(6,6). Mean 0.500, sd 0.139. A worse mean, but a belief nearly three times as wide, because it rests on a tenth of the evidence.

Now ask how often Thompson will pull B. That is exactly the probability that B’s draw beats A’s, which is the probability that B is truly better.

Two notations first: theta_a (“theta sub a”) denotes an arm’s unknown true mean, and Phi is the standard normal cumulative distribution function, which converts a distance measured in standard deviations into a probability.

normal approximation:
  difference in means   = 0.500 - 0.598 = -0.098
  combined spread       = sqrt(0.048^2 + 0.139^2) = sqrt(0.0023 + 0.0193) = 0.147
  z                     = -0.098 / 0.147 = -0.67
  P(theta_B > theta_A) ~ Phi(-0.67) ~ 0.25

exact, integrating the two Beta densities:
  P(theta_B > theta_A) = 0.261

The approximation does the right arithmetic; it is just an approximation. It treats both posteriors as normal, and Beta(6,6) — ten pulls’ worth of evidence spread over the whole unit interval — visibly is not, so the exact answer sits a little above the normal one.

Quote the exact figure, because it is the one a real implementation actually samples:

Arm B is pulled about 26% of the time — not because a schedule says so, but because there is a 26% chance it is actually better.

That is the whole pitch. Thompson sampling’s exploration rate is a posterior probability, so it needs no tuning, it adapts automatically to both gap size and sample count, and it matches UCB’s regret order while usually beating it empirically.

Comparing the three

The table scores all three on four axes. Two of the column headings need definitions first.

Delayed feedback means the reward for a pull arrives long after the pull — a click that lands minutes after an impression, so you have to keep choosing while thousands of results are still outstanding.

Non-stationarity means the arms’ true means drift over time, which violates the setting’s core assumption.

The regret column uses big-O notation. O(T) means regret grows in proportion to the number of rounds; O(log T) means it grows like the logarithm of it. Over a million rounds that is the difference between a factor of a million and a factor of about fourteen.

Delayed feedback is the practical tiebreaker in production, and the failure is worth picturing.

A UCB agent has 10,000 impressions in flight and no results back yet. Its pull counts n_a are frozen, because n_a only updates when a reward returns. Frozen n_a means a frozen bonus, and a frozen bonus means a frozen argmax — so it picks the same arm ten thousand times in a row.

Thompson has no such problem. It samples fresh from the posterior each time, and because the sample is random, those 10,000 impressions spread across arms in proportion to each arm’s probability of being best.

The assumption underneath every bound above

Every regret bound in this section assumes each arm’s reward distribution is fixed.

Under drift the guarantees invert. UCB’s shrinking bonus is a commitment to a mean that may no longer exist, and an algorithm that provably stops exploring is provably unable to notice the world changed.

The standard repairs — discounting old observations, or holding only a sliding window of them — all work by deliberately keeping the posterior wide. You are buying permanent, bounded regret in exchange for the ability to track.

This is the same reason fixed-eps exploration, the worst method on a stationary problem, is the one that survives a non-stationary one.

6. Policy gradients — the derivation that matters

Everything so far learned values and then read a policy off them. The other route is to adjust the policy’s own knobs directly, in the direction that raises the expected return.

This is the family that reinforcement learning from human feedback (RLHF, Rlhf the pipeline this curriculum actually runs on) and every modern large-model alignment method belong to. It rests on one algebraic identity, and that identity is worth being able to reproduce cold.

Setting up

To parameterize the policy means: instead of a lookup table, the policy is a neural network whose weights are collected in a vector theta (the Greek letter theta). It is written pi_theta(a|s), read “pi sub theta of a given s.” Changing theta changes the probabilities the policy assigns.

The objective J(theta) (“J of theta”) is the expected total reward of a trajectory drawn from that policy. Gradient ascent on J is the whole plan — a gradient being the vector of partial derivatives that points in the direction of steepest increase.

J(theta) = E_{tau ~ p_theta}[ R(tau) ],     p_theta(tau) = p(s_0) PROD_t pi_theta(a_t|s_t) P(s_(t+1)|s_t,a_t)

The first expression says: J is the average return over trajectories tau drawn from the distribution p_theta.

The second says how likely any particular trajectory is: the probability of the starting state, times the product over every timestep of the policy’s probability of the action taken and the environment’s probability of the resulting next state. Note that both the agent (pi_theta) and the environment (P) appear in it. Remember that — one of them is about to disappear.

The obstacle

We want grad_theta J, and we cannot get it the obvious way.

theta appears in the distribution we are averaging over, not in the thing being averaged. You cannot simply differentiate R(tau) with respect to theta, because R does not contain theta at all — the return is just a number the environment paid.

The log-derivative trick

The fix moves the derivative onto something we can compute. Four lines, and one algebraic identity in the middle.

INT ... dtau is an integral over all possible trajectories, which is what an expectation looks like when written out so it can be manipulated algebraically.

grad_theta J = grad INT p_theta(tau) R(tau) dtau
             = INT grad p_theta(tau) R(tau) dtau

identity:      grad log p = grad p / p     ->     grad p = p * grad log p

             = INT p_theta(tau) grad log p_theta(tau) R(tau) dtau
             = E_tau[ grad log p_theta(tau) * R(tau) ]

Line by line:

1. Write the expectation as an integral.
2. Move the gradient inside the integral. R(tau) has no theta, so it stays put and only p_theta is differentiated.
3. Apply the identity. This is just the chain rule on log, rearranged: since grad log p = grad p / p, multiplying both sides by p gives grad p = p * grad log p.
4. Substitute, which puts a p_theta(tau) factor back in front — and an integral of p_theta(tau) times something is an expectation again.

The last line is the payoff: an expectation you can estimate by sampling, because everything inside it — the gradient of a log-probability, times an observed return — is computable from data you already have.

Where the environment disappears

Now expand log p_theta(tau), using the fact that the logarithm of a product is the sum of the logarithms:

log p_theta(tau) = log p(s_0) + SUM_t log pi_theta(a_t|s_t) + SUM_t log P(s_(t+1)|s_t,a_t)
                   \_________/                                \_______________________/
                    no theta                                        no theta

The starting-state probability and the transition probabilities contain no theta. Their derivatives with respect to theta are therefore zero, and they drop out of the gradient entirely.

The dynamics appear in the objective and vanish from its gradient. That is the entire reason policy gradients are model-free. You never need to know P. You only need to be able to sample from it, which is what “running the environment” means.

What survives is REINFORCE, the original policy-gradient algorithm:

grad_theta J = E[ ( SUM_t grad log pi_theta(a_t|s_t) ) * R(tau) ]        <- REINFORCE

In plain words: for each action you took, nudge theta in the direction that makes that action more likely, scaled by how good the whole trajectory turned out. Good runs make all of their actions more likely. Bad runs make all of theirs less likely.

It works. It is also extremely noisy, and the rest of this section is about the noise.

Two free variance reductions

REINFORCE as written is unbiased but has enormous variance, and two modifications reduce it without introducing any bias at all. Both are free in the sense that they cost nothing and give up nothing.

The first is causality. An action at time t cannot affect a reward at an earlier time k < t. So multiplying that action’s gradient by those earlier rewards adds noise and no signal — it is pure static.

Formally: conditioned on s_t, the reward r_k for k < t is already determined and is therefore a constant. And E_{a~pi}[grad log pi(a|s_t)] = 0 — the average gradient of the log-probability, over the policy’s own action distribution, is zero (proved in the next subsection). A constant times something with expectation zero has expectation zero, so dropping the cross term changes nothing about the estimator’s mean.

Replace the whole-trajectory return R(tau) with the reward-to-go G_t, which counts only rewards from time t onward:

grad_theta J = E[ SUM_t grad log pi_theta(a_t|s_t) * G_t ],     G_t = SUM_{k>=t} gamma^(k-t) r_k

The second is baselines. You may subtract any function b(s) that depends on the state but not on the action, so that the learner reacts to how much better than expected the outcome was rather than to its raw magnitude:

grad_theta J = E[ SUM_t grad log pi_theta(a_t|s_t) * (G_t - b(s_t)) ]

Why the baseline is unbiased — the proof

This proof is five lines and it is the other one worth being able to write from memory, because it also tells you exactly which baselines are legal.

Fix a state s and take the expectation of the term the baseline contributes:

E_{a~pi}[ grad log pi_theta(a|s) * b(s) ]
   = b(s) * SUM_a pi_theta(a|s) * grad log pi_theta(a|s)
   = b(s) * SUM_a pi_theta(a|s) * grad pi_theta(a|s) / pi_theta(a|s)
   = b(s) * SUM_a grad pi_theta(a|s)
   = b(s) * grad [ SUM_a pi_theta(a|s) ]
   = b(s) * grad(1)
   = 0

Each step is small. Counting the lines of the block from the top:

• Line 2 writes the expectation as an explicit sum over actions, and pulls the constant b(s) out front.
• Line 3 substitutes the same identity used in the log-derivative trick, grad log p = grad p / p.
• Line 4 cancels the two copies of pi_theta(a|s), one in the numerator and one in the denominator.
• Line 5 swaps the order of summing and differentiating.
• Line 6 uses the fact that a probability distribution sums to one, so the bracket is just 1.
• Line 7 is the derivative of a constant, which is zero.

The subtracted term has expectation exactly zero because probabilities sum to one and the gradient of a constant is zero.

Now notice precisely where b had to be action-independent: at line 2, pulling b(s) out of the sum over a. If b depended on a it could not come out, none of the subsequent cancellation happens, and the estimator becomes biased.

That is exactly why the critic — the learned value estimator that supplies the baseline — sits in that slot as V(s) and never Q(s,a).

Why it reduces variance — the arithmetic

Unbiased is only half the claim. The optimal baseline can be derived outright, and the amount of noise it removes put in numbers — and the magnitude is the surprising part.

The estimator is g = grad log pi * (G - b). Its mean is fixed by the proof above — every legal baseline gives the same mean — so only E[g^2], the average of its square, depends on b.

So differentiate the variance with respect to b and set it to zero, the standard way to find a minimum:

Var[g] = E[ (grad log pi)^2 (G-b)^2 ] - (grad J)^2

d/db:   -2 * E[ (grad log pi)^2 (G - b) ] = 0
   ->   b* = E[ (grad log pi)^2 * G ] / E[ (grad log pi)^2 ]

The variance-minimizing baseline is a gradient-magnitude-weighted average of the return. V(s) — a plain average of the return — is a good, cheap approximation to it, and it is what every practical implementation uses.

A worked case

The size of the effect is the point, so work it with actual numbers.

Take a single state with two actions. The gradient of the log-probability is +1 for action a_1 and -1 for action a_2. The returns are stochastic:

• a_1 yields 110 or 100, with equal probability.
• a_2 yields 100 or 90, with equal probability.

So a_1 is genuinely the better action, by 10. That 10 is the signal any estimator has to recover.

Four equally likely outcomes result, and the estimator g = grad log pi * (G - b) takes one value on each. Compute its mean and variance twice: first with no baseline (b = 0), then with b = 100, roughly the average return.

without baseline, g in {+110, +100, -100, -90}, each p=0.25
    E[g]   = (110 + 100 - 100 - 90)/4  = 5.0
    E[g^2] = (12100 + 10000 + 10000 + 8100)/4 = 10,050
    Var    = 10,050 - 25 = 10,025      sd = 100.1

with b = 100,  g in {+10, 0, 0, +10}
    E[g]   = 5.0                        <- IDENTICAL
    E[g^2] = (100 + 0 + 0 + 100)/4 = 50
    Var    = 50 - 25 = 25              sd = 5.0

Same expectation, variance down 401x, standard deviation down 20x.

From “20x noisier” to “401x more data”

That translation is the one to say out loud, because it is where the effect stops sounding survivable.

The standard error of an average of N samples is sd/sqrt(N). To make a noisier estimator as precise as a quieter one, set the two standard errors equal and solve for the sample counts:

sd_1 / sqrt(N_1) = sd_2 / sqrt(N_2)   ->   N_1/N_2 = (sd_1/sd_2)^2

(100.1 / 5.0)^2 = 20.02^2 = 401       the sample-size ratio IS the variance ratio

Matching a 20x larger standard deviation costs 20^2 = 400 times the samples. It is squared because precision buys back only as fast as sqrt(N). So the un-baselined estimator needs 401 times more trajectories to reach the same precision as the baselined one.

The same fact stated as signal-to-noise — the true gradient divided by the typical error in one sample of it:

no baseline:   5 / 100.1 = 0.05
with baseline: 5 / 5.0   = 1.00

At 0.05 the noise is twenty times the signal. On any single trajectory the update direction is essentially random.

Why a constant offset wrecks it

The general statement is sharper than the example: the un-baselined estimator’s variance scales with E[G^2], not with Var[G]. It scales with the average squared return, not with how much the return actually varies.

So an offset that changes nothing about the problem changes everything about the estimator.

Add +1000 to every reward. The optimal policy is untouched, every ordering between actions is untouched — by any reasonable reading it is the same problem:

returns become {1110, 1100, 1100, 1090}
    E[g^2] = (1110^2 + 1100^2 + 1100^2 + 1090^2)/4 = 1,210,050
    Var    = 1,210,050 - 25 = 1,210,025            sd = 1,100    <- 11x worse than before
with b = 1100:  identical to before, Var = 25                    <- unchanged

1,210,025 / 10,025 = 121, so the offset cost you a 121-fold variance increase for nothing.

The baseline is what makes the policy gradient invariant to a constant reward offset. Without one, reward + 1000 is a 121x variance regression that no amount of tuning will recover.

That is the sentence interviewers are hoping for, and it is also why “just add a survival bonus to every step” is one of the most common ways to silently kill an RL run.

Two load-bearing assumptions

The samples must come from the current policy. The derivation averaged over p_theta, so the estimator is only unbiased for data the current theta generated. That is what makes plain REINFORCE on-policy, and why every batch must be discarded after one update. The correction that buys back reuse is Actor critic a2c and ppo.

R must be the objective, not a stand-in for it. The gradient faithfully maximizes whatever number you wrote down, loopholes included. A policy that discovers a way to collect reward without doing the task gets pushed harder toward that discovery every single update, because the mathematics cannot tell the difference between the goal and the proxy.

REINFORCE in code

The block below is the whole algorithm — reward-to-go, baseline, ascent — in a dozen lines. Two things to notice: the loop runs backwards over the rewards, which is how you accumulate reward-to-go in one pass, and the last line uses + rather than - because this is gradient ascent.

This is framework-agnostic pseudocode. policy and value_fn stand in for whatever you are actually using, and nothing here is meant to run as written. The two blocks later in the chapter are the opposite — real PyTorch, and they are labelled as such.

def reinforce_step(traj, policy, value_fn, gamma=0.99, lr=1e-3):
    """One REINFORCE-with-baseline update over a single trajectory."""
    returns, running = [], 0.0
    for r in reversed(traj["rewards"]):          # reward-to-go: causality
        running = r + gamma * running
        returns.append(running)
    returns.reverse()

    grad = 0.0
    for s, a, g in zip(traj["states"], traj["actions"], returns):
        advantage = g - value_fn(s)              # baseline: unbiased, lower variance
        grad = grad + policy.grad_log_prob(a, s) * advantage
    policy.params = policy.params + lr * grad    # ASCENT: we maximize J
    return policy

7. Actor-critic, A2C, and PPO

REINFORCE is correct and unusable at scale: it must wait for a whole episode to finish, and it must throw away every batch after one update. Fixing both gives PPO — proximal policy optimization — the algorithm that trains essentially every reinforcement-learned language model in production, and the one worth knowing in the most detail.

The name actor-critic describes the architecture: the actor is the policy pi_theta that chooses actions, and the critic is a second learned network V that predicts how good states are. The critic’s estimates supply the baseline; the actor uses them to learn.

From baseline to critic

The first fix removes the need to wait for the episode to end, by replacing a measured return with a predicted one.

A Monte Carlo return is one measured by actually running to the end and adding up what happened. It is accurate on average, but only available after the fact, and very noisy.

The alternative is bootstrapping: replace the unobserved tail with the critic’s prediction of it. Substituting the bootstrapped version into G_t - V(s_t) gives the temporal-difference error, written delta_t (“delta at time t”):

delta_t = r_t + gamma*V(s_(t+1)) - V(s_t)          the TD error
E[ delta_t | s_t, a_t ] = Q(s_t,a_t) - V(s_t) = A(s_t,a_t)

The first line reads: “the reward you actually got, plus the discounted value of where you actually landed, minus what you predicted before acting.” It is a one-step surprise.

Substitute. The critic predicted V(s_t) = 5.0. You act, collect r_t = 1, and land somewhere the critic scores V(s_(t+1)) = 6.0, with gamma = 0.9. Then delta_t = 1 + 0.9*6.0 - 5.0 = 1 + 5.4 - 5.0 = +1.4. Better than expected, so the action gets reinforced.

The second line says the average of that surprise is exactly the advantage. The TD error is an unbiased estimate of the advantage given a correct V — and V is learned, so in practice you have traded variance for bias.

GAE: the bias-variance dial

That trade is the entire actor-critic design space, and generalized advantage estimation (GAE) exposes it as a single knob, lambda (the Greek letter lambda). GAE blends TD errors over many lookahead lengths at once:

A_GAE(gamma,lambda)_t = SUM_{l>=0} (gamma*lambda)^l * delta_(t+l)

Read it as “sum over lookahead distances l, of gamma-times-lambda raised to l, times the TD error l steps later.” Near-term surprises count fully; distant ones are damped by (gamma*lambda)^l.

The two ends of the dial:

• lambda = 1 recovers Monte Carlo: unbiased, maximum variance.
• lambda = 0 collapses the sum to delta_t alone, one-step TD: minimum variance, maximum bias.

Credit assignment therefore gets its own effective horizon, 1/(1 - gamma*lambda), computed the same way as §1’s. At the standard gamma = 0.99, lambda = 0.95:

gamma*lambda = 0.99 * 0.95 = 0.9405
horizon      = 1/(1 - 0.9405) = 1/0.0595 = 16.8 steps

Compare that with the reward horizon at the same gamma: 1/(1 - 0.99) = 100 steps.

Lambda is a second horizon dial, and the credit-assignment horizon is usually about 6x shorter than the reward horizon. The objective may care about a hundred steps while the learning signal only reaches back seventeen. Mismatched dials are a common silent misconfiguration.

A2C

A2C — advantage actor-critic — is exactly the above, run with n copies of the environment stepped forward in lockstep.

The parallel rollouts (a rollout being one simulated run of the policy through the environment) decorrelate the batch, doing the same job a replay buffer does for DQN in Dqns two tricks and why each is necessary. The difference is that A2C keeps the data on-policy, because every sample still comes from the current parameters.

PPO’s clipped objective

The second fix recovers data reuse.

Taking multiple gradient epochs — full passes over the same batch — makes the data off-policy the moment the first epoch ends. After one update, theta is no longer the theta that collected it.

So a correction is needed, and §4 already showed which correction not to use. PPO uses a single-step probability ratio rather than the trajectory-long product that blew up in Importance sampling and why long horizons kill it. One ratio cannot span twelve orders of magnitude; a product of twenty of them can.

r_t(theta) = pi_theta(a_t|s_t) / pi_old(a_t|s_t)

L_CLIP = E[ min( r_t*A_t ,  clip(r_t, 1-eps, 1+eps) * A_t ) ]        eps ~ 0.2

Note the name collision: this r_t(theta) is a probability ratio, not the reward r_t. PPO’s paper uses the same letter for both, and so does everyone since.

r_t(theta) is how much more likely the current policy is to take the action than the policy that collected the data. It equals 1 when nothing has changed, 1.5 when the current policy is 50% more likely to take that action, and so on.

clip(r_t, 1-eps, 1+eps) forces the ratio into a band — at the usual eps = 0.2, anything below 0.8 becomes 0.8 and anything above 1.2 becomes 1.2. L_CLIP is the objective actually maximized, and A_t is the advantage estimate from GAE above.

Now work the four cases. This is what separates a memorized answer from an understood one.

The rows split on two questions: was the action better than average (A_t > 0) or worse, and has the update already pushed its probability far up (r_t > 1+eps) or far down (r_t < 1-eps)? Read the “min picks” column — that is where the behaviour is decided, since L_CLIP takes the smaller of the two candidate values.

The pattern in the last column: the two rows where the gradient dies are exactly the two where the update already went the way the advantage wanted, and went too far. The two rows where it flows are the ones where the update needs to come back.

The min is what makes it a pessimistic bound. The clip only kills the gradient once the update has already moved probability in the direction the advantage wanted, past the trust radius. It never blocks a correction back toward the old policy.

The trust radius is the region around the old policy in which the collected data still says something useful about the new one. Plain clipping without the min would trap the policy in the clipped region with no gradient to escape.

What happens without the clip

Remove the correction — set eps effectively infinite, so nothing restrains the update — and the run below is what you get.

Three columns to watch. The mean ratio should stay near 1; it does not. Entropy measures how spread out the policy’s action probabilities are: high entropy means it is still trying different things, zero entropy means it always picks the same action. Mean return is the thing you actually wanted.

epoch   mean ratio   policy entropy   mean return
  0        1.00          1.79            42
  1        1.31          1.44            51
  2        2.87          0.61            38
  3        6.40          0.08            11
  4       11.20          0.01             9      <- deterministic, no exploration, no recovery

Start with the entropy column. 1.79 is ln(6), the entropy of a policy that spreads its probability evenly over six actions — maximally open-minded. By epoch 4 it is 0.01, which is one action with probability essentially 1.

Meanwhile the return went 42 -> 51 -> 38 -> 11 -> 9. Epoch 1 was a real improvement; everything after it was the collapse.

The policy collapsed to a point mass — a distribution with all its probability on a single outcome — and a point-mass policy generates no exploratory data, so there is no gradient signal that could ever undo it.

The failure is one-way. That is why the clip is not a nicety: it caps the per-batch movement so the surrogate — the approximate objective PPO optimizes in place of the true one — stays valid in the region where the ratio was estimated.

The four companions

Essentially every PPO implementation ships four extras alongside the clip, and each is worth naming:

1. Normalize the advantages within each batch to mean zero and unit variance, so the update size does not depend on the scale of the reward.
2. Add an entropy bonus to the loss, which pays the policy a little for staying uncertain.
3. Clip the value function’s update the same way the policy’s is clipped.
4. Stop the epoch early once the measured divergence between the new and old policy exceeds about 1.5 times the target. This is a direct tripwire against the collapse above.

Divergence in that last item is measured by the KL divergence, defined in The rl step and the kl leash.

PPO in code

The two implementations below are real PyTorch, unlike the REINFORCE pseudocode earlier. .exp(), .clamp() and .mean() are tensor methods; torch.minimum is the elementwise minimum and torch.nn.functional.logsigmoid is a numerically stable log(sigmoid(x)).

Each block ends with a call and an assert, so the arithmetic above is actually exercised rather than merely displayed. The assertion here checks row 1 of the four-case table: the loss comes out at -1.2, the clipped value, not -1.6487, the unclipped one.

import torch


def ppo_loss(logp_new, logp_old, adv, eps=0.2, c_v=0.5, c_h=0.01,
             value_pred=None, value_target=None, entropy=None):
    """Clipped surrogate. logp_* are log pi(a|s); adv is normalized per batch."""
    ratio = (logp_new - logp_old).exp()
    unclipped = ratio * adv
    clipped = ratio.clamp(1.0 - eps, 1.0 + eps) * adv
    policy_loss = -(torch.minimum(unclipped, clipped)).mean()   # min -> pessimistic bound
    value_loss = ((value_pred - value_target) ** 2).mean()
    return policy_loss + c_v * value_loss - c_h * entropy.mean()


# Row 1 of the table above: A_t > 0 and r_t > 1+eps, so the clip binds and the
# surrogate stops paying for an action that already got much likelier.
logp_new, logp_old = torch.tensor([0.5]), torch.tensor([0.0])   # ratio = e^0.5 = 1.6487
adv, zero = torch.tensor([1.0]), torch.zeros(1)
loss = ppo_loss(logp_new, logp_old, adv, value_pred=zero, value_target=zero,
                entropy=zero)
assert torch.isclose(loss, torch.tensor(-1.2)), loss   # -(1+eps)*A, NOT -1.6487

8. DQN’s two tricks, and why each is necessary

DQN is a case study in how a small implementation change can break a proof.

DQN — the deep Q-network — is Q-learning from On policy vs off policy the mechanism with a neural network in place of the lookup table. That substitution is what made it work on Atari from raw pixels, where a table would need one entry per possible screen.

But it also breaks two assumptions the tabular version got for free, and each of DQN’s two famous tricks repairs exactly one. A third problem, which neither trick addresses, is handled separately at the end.

Trick 1 — the replay buffer decorrelates

The first broken assumption belongs to the optimizer, not to RL.

Stochastic gradient descent (SGD) — the standard method of training a network by taking small steps on random minibatches — assumes each minibatch is roughly iid: independent and identically distributed, meaning the samples are drawn independently from the same distribution.

Consecutive transitions are anything but independent. s_(t+1) is one action away from s_t, so it looks almost identical.

Quantify that. For a batch of n samples whose neighbours correlate at rho (the Greek letter rho, the lag-1 correlation — the correlation between each sample and the one right after it), the effective sample size is how many genuinely independent samples the batch is worth:

n_eff = n * (1 - rho) / (1 + rho)

n = 32,  rho = 0.95   ->   n_eff = 32 * (1 - 0.95)/(1 + 0.95)
                                 = 32 * 0.05/1.95
                                 = 32 * 0.0256 = 0.82

A batch of 32 consecutive Atari frames carries less than one independent sample’s worth of information. At 60 frames per second, those 32 frames are about half a second of one situation.

There is a second problem on top. The data distribution moves with the policy, so the network is trained on a stream that walks from one region of state space to another and forgets the last one. That failure has a name: catastrophic forgetting.

The replay buffer fixes both at once. Store a million transitions and sample minibatches uniformly at random from that store, and each minibatch draws from hours of play rather than half a second of it. It also lets each transition be reused roughly 8 times, which is a straight sample-efficiency win on top.

This is only legal because Q-learning is off-policy, for exactly the reason On policy vs off policy the mechanism gave. Try the same trick with SARSA and you learn the value of a policy you stopped running a million steps ago.

Trick 2 — the target network stabilizes the bootstrap

The second broken assumption belongs to regression: you cannot fit a target that moves every time you fit it.

The regression target is y = r + gamma * max_b Q_theta(s',b). Look at the subscript: theta — the network’s weights — is the very thing being updated. The target is a function of the parameters chasing it.

Two failures follow.

Failure 1: a moving target. Every gradient step changes the target you were regressing toward, so there is no fixed point for the optimizer to converge to. You are shooting at something that moves whenever you shoot.

Failure 2: positive feedback. This is the dangerous one. A neural network generalizes, so raising Q_theta(s,a) also raises Q_theta(s',b) for states s' that resemble s. That raises y, which raises Q_theta(s,a) further, which raises y again. The loop has gain — each pass amplifies rather than damps — and nothing in the loss bounds it.

The repair is to freeze a copy of the weights, written theta^- (“theta minus”) and called the target network, and refresh it from the live weights only every C steps, with C around 10,000.

For the duration of those C updates the target is a fixed number. The problem becomes ordinary supervised regression against a fixed dataset, which is a solved problem.

Here is what the failure looks like without it. The environment’s maximum possible return is 10, so the right-hand column is behaving and the left-hand one is not:

step      mean Q (no target net)    mean Q (target net, C=10k)
  10k             8.2                        6.4
  50k            41.7                        9.1
 100k           418.0                        9.8
 200k        21,140.0                        9.9      <- max achievable return is 10

Neither run produces a nan — a “not a number”, the numerical error that would at least announce itself — the unstable one just estimates values two thousand times larger than any return the environment can pay, and acts on the ranking that produces. That is the shape of the failure to watch for: not a crash, but confident nonsense.

The third problem: max overestimates

The two tricks above leave one bias untouched, and it comes from the max itself.

The statement is E[max_a Q_hat(s,a)] >= max_a E[Q_hat(s,a)] — “the average of the maximum is at least the maximum of the averages.” It follows from Jensen’s inequality, the general fact that averaging and applying a convex function like max cannot be swapped freely.

The intuition is easier than the algebra. Taking a maximum systematically selects whichever estimate happened to be luckiest. So a max over noisy estimates is biased upward even when every individual estimate is unbiased — the noise does not cancel, it gets picked.

Size the bias. For K actions with zero-mean noise of typical size sigma (the Greek letter sigma, standard deviation), the inflation per backup is about sigma * sqrt(2*ln K). An Atari controller has K = 18 actions:

sqrt(2 * ln 18) = sqrt(2 * 2.890) = sqrt(5.781) = 2.40

So 2.40 * sigma of pure fiction is added at every backup. And because each backup feeds the next, bootstrapping compounds that over the effective horizon 1/(1-gamma) = 100.

Double DQN fixes it by decoupling selection of the action from evaluation of it:

y = r + gamma * Q_theta_minus( s', argmax_b Q_theta(s',b) )

Read it inside out. The online network (the live weights theta) picks which action via the argmax. The target network (theta^-) then scores that chosen action.

Two independently-noisy estimates now have to agree before a value gets inflated: the online net must be lucky about the same action the target net is lucky about. That turns a systematic bias into a much smaller one.

The three tricks together

Three tricks, three broken assumptions, three distinct symptoms — and the middle column is the one to memorize, because it is what makes each trick necessary rather than optional:

9. RL metrics — the part candidates fumble

Telling whether an RL run actually worked is harder than it is in supervised learning, and it is where most published and internal results quietly fall apart. Two ideas carry the whole topic: report the number you actually care about rather than the one you optimized, and treat run-to-run noise as the dominant effect it really is.

What to report

Five numbers cover almost every honest RL report. The table’s third column is the point: each of the five has a specific, common way of being reported dishonestly, and knowing the trap is more useful than knowing the metric.

One term used in the table: AUC stands for area under the curve, the integral of the learning curve. It summarises how quickly a run got good, rather than how good it ended up.

The first row deserves emphasis, because it is the most common error: you train with a discount factor but you report the undiscounted total, since gamma was a device for making learning tractable and was never what anyone wanted.

Why RL evaluation is genuinely hard

The reason has nothing to do with RL being complicated and everything to do with how noisy it is. The run-to-run variation of a single algorithm on a single environment is usually larger than the difference between algorithms.

Here are ten runs of one configuration, differing only in the random seed — the number initializing the random-number generator, which fixes the network’s starting weights and the environment’s randomness. Same code, same hyperparameters, same environment. Look at the spread between 1150 and 3720:

3410  2890  3720  1150  3550  3390  2210  3610  3480  1980

mean = 2,939      sd = 870      SEM(n=10) = 275      95% CI ~ [2,400, 3,478]
median = 3,400    IQR = [2,210, 3,550]   (Tukey hinges)

Four summary statistics appear there:

• sd, the standard deviation — the typical spread of a single run around the mean.
• SEM, the standard error of the mean, sd/sqrt(n) — the typical error in the average of n runs. Here 870/sqrt(10) = 275.
• CI, the confidence interval — the range the true mean plausibly lies in. 2,939 ± 1.96*275 gives [2,400, 3,478].
• IQR, the interquartile range — the span from the 25th to the 75th percentile, computed here by Tukey’s hinge convention. Unlike the mean, a single extreme run cannot move it.

Two conclusions fall straight out of those numbers.

Best-of-k seed selection is a 23% improvement made of nothing

Sort the ten runs and take the top three: 3720, 3610, 3550.

top-3 mean = (3720 + 3610 + 3550)/3 = 10,880/3 = 3,627
true mean  = 2,939
inflation  = 3,627 / 2,939 = 1.23      a 23% "gain"

Nothing about the algorithm changed. Only the reporting did.

Three seeds cannot detect anything

Run the same standard-error arithmetic at n = 3, and then for a comparison between two algorithms:

SEM at n=3                = 870/sqrt(3)   = 502
SE of the difference      = 502*sqrt(2)   = 710       two independent estimates
smallest detectable at 95% = 1.96 * 710   ~ 1,400

The mean itself is 2,939. So the smallest effect three seeds can distinguish from noise is roughly half the mean return.

Any RL result reported at 3 seeds with no interval is indistinguishable from a coin flip, and this is the single most common methodological failure in the field.

Five practices that fix it

1. Run at least 10 seeds and report the whole distribution — median, IQR, and every per-seed curve. A mean with a shaded band hides multimodality, which is exactly the shape RL results usually have.
2. Separate the seeds. The seed controlling training randomness, the one controlling environment layouts, and the one controlling evaluation episodes are three different things. Share them and a policy can memorize a specific level and score as if it had generalized.
3. Fix the budget in environment steps and report it. “Trained to convergence” is not a budget and cannot be compared against.
4. Prefer the interquartile mean — the average of the middle 50% of runs — with stratified bootstrap confidence intervals. “Bootstrap” here means estimating the interval by repeatedly resampling your own runs with replacement. One lucky seed cannot move that statistic.
5. Evaluate on a held-out set of episodes with exploration disabled, and report the online return separately. Those two numbers can differ by a factor of three, as the cliff-walking example showed (-13 against -41).

10. RLHF — the pipeline this curriculum actually runs on

The one place RL touches most people’s work is turning a raw language model into an assistant. It is called RLHF — reinforcement learning from human feedback — and its central problem is that the reward function does not exist until you build one, so the chapter’s warning about reward misspecification stops being hypothetical and becomes the main engineering challenge.

The MDP mapping

Map it onto the MDP first, because the correspondence is not obvious:

The pipeline

The pipeline runs in five stages, top to bottom in the diagram.

1. Pretrained LM. A language model (LM) trained only to predict the next token on internet text.
2. SFT. Supervised fine-tuning on demonstrations of good behaviour. This is ordinary supervised learning — no RL yet.
3. Two copies are made of the SFT model. A trainable one (pi_theta, “initialized from SFT” in the diagram) and a frozen one (pi_ref, “frozen SFT copy”). The frozen one is the reference policy and is never updated.
4. Collect preferences and train a reward model. Humans are shown pairs of responses and say which is better, producing a preferred response y_w (w for winner) and a rejected one y_l (l for loser). Those comparisons train a reward model (RM) r_phi — “r sub phi,” where phi is the Greek letter phi and is just the name for the RM’s weights — using the Bradley-Terry loss derived below.
5. Run PPO. PPO from Actor critic a2c and ppo maximizes r_phi minus beta*KL: the reward model’s score, less beta times the KL divergence from the reference. What comes out is the aligned policy that ships.

flowchart TD
    P["Pretrained LM"] --> S["SFT<br/>supervised on demonstrations"]
    S --> R["Collect preferences<br/>humans rank y_w over y_l"]
    R --> RM["Reward model r_phi<br/>Bradley-Terry loss"]
    S --> REF["pi_ref = frozen SFT copy"]
    RM --> PPO["PPO<br/>maximize r_phi minus beta*KL"]
    REF --> PPO
    S --> POL["pi_theta initialized from SFT"]
    POL --> PPO
    PPO --> OUT["Aligned policy"]

    style RM fill:#2d6a4f,color:#fff
    style PPO fill:#2d6a4f,color:#fff
    style REF fill:#bc6c25,color:#fff

The colours carry a rule. Green marks the two boxes trained by an objective derived in this chapter: the reward model by the Bradley-Terry loss immediately below, and the RL step by PPO’s clipped surrogate from Actor critic a2c and ppo. Orange marks the one copy that is deliberately never updated — the frozen reference the KL penalty measures against. The unfilled boxes are stages this chapter does not derive.

The reward model

The MDP needs a scalar reward and nobody can supply one, so a number has to be manufactured out of the judgements humans can make reliably.

Humans compare; they do not score. Ask ten annotators to rate a response out of ten and you get ten different scales. Ask them which of two responses is better and they largely agree.

The Bradley-Terry model turns those comparisons into a single number. It posits that each item has a hidden quality score, and that the probability one beats another is a function of their difference.

P(y_w > y_l | x) = sigmoid( r_phi(x,y_w) - r_phi(x,y_l) )
L_RM = -E[ log sigmoid( r_phi(x,y_w) - r_phi(x,y_l) ) ]

sigmoid(z) = 1/(1+e^-z) is the S-shaped function that squashes any real number into a probability between 0 and 1.

So the first line reads: “the chance the preferred response wins is the sigmoid of how much higher the reward model scores it.” Substitute: if the RM scores the winner 1.5 and the loser 0.3, the difference is 1.2 and sigmoid(1.2) = 0.77 — the model claims humans would pick the winner 77% of the time.

The second line is the training loss, the negative log-likelihood of the observed human choices. It is minimized by making the model’s implied probabilities match the humans’ actual picks.

The reward is only defined up to a per-prompt shift

Look at what the loss can see: only the difference r_phi(x,y_w) - r_phi(x,y_l).

So add any per-prompt function f(x) to r_phi. Both terms shift by the same amount, the difference is unchanged, and the loss does not move at all. Nothing in training pins down the absolute level.

The reward is identified only up to a per-prompt shift, so reward-model scores are meaningless across prompts and must be normalized per prompt before they enter the RL objective.

Concretely: a score of 1.4 on one prompt and 0.3 on another says nothing about which response is better. Only within-prompt comparisons carry information.

The RL step and the KL leash

Now the reward exists and PPO can run against it. Why running it to convergence destroys the model is the single most important practical fact in the chapter.

maximize   E_{y ~ pi_theta}[ r_phi(x,y) ]  -  beta * KL( pi_theta || pi_ref )

The first term is what you want: a high reward-model score. The second term is the KL penalty, and it is what stops the first term from destroying the model.

KL divergence, short for Kullback-Leibler divergence, measures how far one probability distribution has moved from another. It is zero when they are identical and grows as they separate. When natural logarithms are used it is measured in units called nats.

So KL(pi_theta || pi_ref) is “how far the policy being trained has drifted from the frozen SFT copy,” and beta sets the price of drifting.

In practice it is implemented as a per-token reward of -beta * (log pi_theta(y_t|.) - log pi_ref(y_t|.)) at every token, plus the reward model’s score r_phi(x,y) once at the last one.

Why the KL term exists

r_phi is a learned proxy fitted on the distribution of the SFT policy’s outputs. Optimizing hard against it drags the policy off that distribution, into the region where the proxy is extrapolating.

This is textbook Goodhart’s law — a measure ceases to be a good measure once it becomes a target. It is also what reward hacking means concretely: the policy finds inputs on which the proxy is wrong in its favour, and drives straight at them.

The KL term is a leash tying the policy to the distribution its scorer was actually trained on.

The training trace below is the one to be able to describe from memory. Read the two right-hand columns against each other: one goes up forever, the other turns around at step 1,500.

step     KL(pi||ref)    RM score    human win-rate vs SFT
   0         0.0          0.12            50%
 500         4.1          0.86            64%
1500        12.7          1.42            71%      <- true optimum
3000        34.8          2.10            58%
6000        88.2          2.71            31%      <- RM score still climbing

The win-rate in the last column is the fraction of times human judges prefer this policy’s output to the SFT policy’s, so 50% means indistinguishable.

The proxy improves monotonically the entire time while true quality peaks at step 1,500 and then collapses. RM score goes 0.12 -> 2.71, never once turning down. Win-rate goes 50% -> 71% -> 31%, ending well below where it started.

Nothing in the training loop can see that collapse. The only metric available to the optimizer is the one going up.

What the degraded outputs actually look like at step 6,000: four times longer than the SFT policy’s, opening with the same three flattering clauses every time, hedging every claim. Length and sycophancy (telling the user what they want to hear) are the two axes reward models most reliably fail to penalize — human labelers mildly prefer both, so the model learns to supply them without limit.

Empirically the relationship is win_rate ~ a*sqrt(KL) - b*KL. A square-root gain from real optimization, a linear loss from overoptimization. Since the linear term eventually outgrows the square-root one, the two cross, and quality peaks at a finite KL rather than at convergence.

This is the concrete form of the chapter’s third assumption failing. The MDP assumed R(s,a) is the objective. Here it demonstrably is not — it is a model of a model of what people want.

The consequence is not degraded performance you can spot. It is confident, monotone, measured “improvement” in the wrong direction.

The defence is entirely procedural. Leash the policy near the distribution the proxy was fit on, and evaluate against something the optimizer cannot see — in practice, human judgement or a held-out judge the policy was never trained against.

Four practicalities

1. beta is usually not fixed. An adaptive controller drives it toward a target KL, so the leash tightens automatically when the policy pulls.
2. Use ratio - 1 - log(ratio) as the per-token KL estimator, not the raw log-ratio. That form is never negative and has lower variance.
3. PPO here holds four networks in memory at once — the policy, the frozen reference, the reward model, and the value head (the critic from Actor critic a2c and ppo). That is why RLHF costs so much more per step than supervised fine-tuning.
4. The KL is measured over the token distribution the sampler actually draws from, so everything in Sampling and why temperature0 isnt deterministic about how temperature and top-p shape that distribution applies directly.

The cheap alternative

Best-of-n rejection sampling often gets most of the benefit for none of the machinery: draw n completions from the unchanged model and keep whichever the reward model scores highest.

Its distance from the base policy has a closed form, log n - (n-1)/n. At n = 16:

ln(16) - 15/16 = 2.77 - 0.94 = 1.83 nats of KL

Compare that with the 12.7 nats at the peak of the trace above — best-of-16 is a much shorter leash.

There is no training run and no reward hacking beyond what n independent samples can stumble into. The cost is simply n times the inference, which is a trade you can make and unmake in an afternoon.

DPO — skipping the reward model

Direct preference optimization (DPO) removes the reward model and the sampling loop entirely, and the derivation showing why that is possible is short and elegant.

The derivation is three steps.

Step 1: write down the optimum. The KL-regularized objective above has a known closed-form optimum — the exact policy that maximizes it, written down rather than searched for. For any reward r:

pi*(y|x) = (1/Z(x)) * pi_ref(y|x) * exp( r(x,y) / beta )

Read that as: the optimal policy is the reference policy reweighted by the exponential of the reward divided by beta, then renormalized.

Z(x) is the partition function — the sum of that reweighting over every possible response, which is what makes the result a valid probability distribution. It is also completely intractable, since “every possible response” means every sequence of tokens there is. Hold that thought; the next two steps make it go away.

Step 2: invert it. Solve the same equation for r instead of for pi*:

r(x,y) = beta * log( pi*(y|x) / pi_ref(y|x) ) + beta * log Z(x)

The reward is now written entirely in terms of policies. The intractable term is still there, but it is now an additive constant that depends only on x.

Step 3: substitute into Bradley-Terry, and watch the constant vanish. Bradley-Terry depends only on the difference r(x,y_w) - r(x,y_l), and both responses share the same prompt x. So both carry the identical beta*log Z(x) term, and subtracting one from the other cancels it:

L_DPO = -E[ log sigmoid( beta*log(pi_theta(y_w|x)/pi_ref(y_w|x))
                       - beta*log(pi_theta(y_l|x)/pi_ref(y_l|x)) ) ]

The reward model was never a separate object — it was always a reparameterization of the policy, and the partition function cancels because preferences are pairwise.

Reparameterization means the same object written in different variables: what looked like a second model was the policy’s own log-probability ratio in disguise.

The result is one loss, one forward pass through each of two networks, no sampling loop, and no value head.

The code below implements exactly that loss. Notice the second assertion: dropping both log-probabilities by the same amount leaves the loss unchanged, which is the pathology named in the last row of the comparison table.

import torch
import torch.nn.functional as F


def dpo_loss(pi_logp_w, pi_logp_l, ref_logp_w, ref_logp_l, beta=0.1):
    """Direct Preference Optimization. All args are sequence log-probs."""
    logits = beta * ((pi_logp_w - ref_logp_w) - (pi_logp_l - ref_logp_l))
    return -F.logsigmoid(logits).mean()


# The loss sees only the MARGIN. Drop BOTH log-probs by the same amount and it
# does not move -- which is the pathology named in the last row of the table below.
w, l = torch.tensor([-2.0]), torch.tensor([-3.0])
ref_w, ref_l = torch.tensor([-2.0]), torch.tensor([-2.0])
base = dpo_loss(w, l, ref_w, ref_l)
assert torch.isclose(base, torch.tensor(0.6444), atol=1e-4), base
assert torch.isclose(dpo_loss(w - 5, l - 5, ref_w, ref_l), base)   # both fell; loss identical

The two approaches are not interchangeable. The table compares them on six axes, and the third row is the one that usually decides it.

PPO can find responses better than anything a human ever wrote down, because it samples new ones and has them scored. DPO can only re-rank behaviours already present in its fixed dataset — “bounded by the dataset’s support,” where the support of a dataset is the set of outcomes it actually contains.

That last row is the DPO failure to be able to name.

The loss depends only on the margin between the two log-probability ratios. Nothing in the objective forces the chosen response’s likelihood to rise — only the gap to widen. Widening the gap by pushing log pi(y_l) down hard while log pi(y_w) also drifts down, just less, scores exactly as well.

Empirically both drop. The model becomes less likely to produce the preferred answer while scoring better on the loss.

Three standard patches exist:

• RPO (regularized preference optimization) adds an explicit negative-log-likelihood term on y_w, so the preferred response is directly pushed up.
• IPO (identity preference optimization) bounds the margin so it cannot grow without limit.
• KTO (Kahneman-Tversky optimization) drops the pairwise requirement entirely and learns from isolated good/bad labels.

11. Contextual bandits — the practical middle ground

Most production systems sit in a setting between the two extremes, and reaching for full RL when a bandit will do is the most common and most expensive modelling error in the field.

Between “one decision, no context” (the bandit of Exploration vs exploitation) and “full sequential control” (everything since) sits the contextual bandit.

Each round has three steps:

1. Observe a context x_t — features describing the situation, such as the user and the page.
2. Choose one of K arms.
3. Observe the reward for the arm you chose, and only that arm.

That last restriction is called bandit feedback. You never learn what the other options would have paid.

observe context x_t  ->  choose arm a_t from K  ->  observe reward r_t for a_t ONLY

The defining assumption is that your action does not change the next context. Show a user article A instead of B and the next request still arrives from the same distribution.

That single assumption removes credit assignment, removes gamma, removes bootstrapping, and removes the deadly triad. Every difficulty in On policy vs off policy the mechanism traced back to one decision influencing a later one. Here, none do.

LinUCB

LinUCB is UCB1 from Ucb1 derived with a linear model per arm, so the estimate can depend on the context instead of being a single average.

One prerequisite: ridge regression is ordinary least-squares fitting with a penalty on large coefficients, which keeps the fit stable when an arm has little data.

theta_a from ridge regression on the contexts where a was shown
A_a = X_a^T X_a + I               (the design matrix)
score = x^T theta_a + alpha * sqrt( x^T A_a^-1 x )

Term by term:

• theta_a is the coefficient vector for arm a.
• x^T theta_a (“x transpose theta”) is the predicted reward — the dot product of the context features with those coefficients.
• A_a is the design matrix. It accumulates the contexts on which the arm has been shown, so it records which directions of context space you have data in. I is the identity matrix, contributed by the ridge penalty.
• sqrt(x^T A_a^-1 x) is exactly the standard error of the ridge prediction at x.

That last term makes this the same rule as Ucb1 derived, generalized: the bonus is the uncertainty of the prediction in this direction of context space, shrinking as 1/sqrt(n) in whichever directions you have data.

Concretely: an arm shown a thousand times to teenagers is still uncertain about retirees. The single count n_a cannot express that, but A_a can — the retiree direction of context space has barely been sampled, so x^T A_a^-1 x stays large there and the bonus knows it.

Off-policy evaluation, and why bandits get it and RL does not

This is the property that makes bandits deployable and full RL frightening: in a bandit you can estimate how a new policy would have performed using only data the old one collected, before shipping anything.

It requires that the logs record one extra field.

A propensity is the probability the logging policy assigned to the action it took, mu(a_i|x_i). Not merely which action was chosen, but how likely it was to be chosen. Most logging pipelines record the first and throw away the second, and that is the field you cannot reconstruct later.

With logged rows (x_i, a_i, r_i, mu(a_i|x_i)), inverse propensity scoring (IPS) reweights each observed reward by how much more likely the new policy would have been to take that action:

V_hat_IPS(pi) = (1/n) * SUM_i [ pi(a_i|x_i) / mu(a_i|x_i) ] * r_i

The hat on V_hat marks it as an estimate.

This is unbiased whenever mu(a|x) > 0 for every action pi might take. Which is why you must log propensities and never deploy a deterministic policy without an exploration floor. A zero in the denominator is a permanently unanswerable counterfactual.

If the old system never once showed that item to that user type, no amount of later analysis can recover what would have happened. The data does not exist and cannot be made to exist retroactively.

The variance catch, and how to measure it

The diagnostic is the effective sample size (ESS) — how many equally-weighted samples your weighted sample is really worth:

ESS = (SUM w_i)^2 / SUM w_i^2

Work an example. 10,000 events were logged. On 9,900 of them the new policy roughly agrees with the old one, giving a modest weight of w = 0.5. The remaining 100 involve a rarely-shown arm that the new policy would pick and the old one almost never did, giving w = 50.

SUM w   = 9,900*0.5   + 100*50    = 4,950 + 5,000   = 9,950
SUM w^2 = 9,900*0.25  + 100*2500  = 2,475 + 250,000 = 252,475
ESS     = 9,950^2 / 252,475 = 99,002,500 / 252,475  = 392

Look at where SUM w^2 came from: 250,000 of the 252,475 is contributed by the 100 rare rows. That is 99% of the denominator from 1% of the data.

Ten thousand logged events, 392 effective — 99% of the estimator’s variance comes from 1% of the rows.

Three fixes are standard:

• Clip the weights at a cap. Trades a little bias for a lot of variance reduction.
• Self-normalize: divide by the sum of the weights instead of by n, which bounds the estimate’s scale.
• Use a doubly-robust estimator, which fits a reward model to carry the bulk of the estimate and uses the importance weights only to correct that model’s residuals. The name comes from the fact that it stays unbiased if either the reward model or the propensities are right — you need only one of the two to hold.

Why this does not transfer to full RL

In a bandit the weight is a single ratio. In sequential RL it is a product over the whole horizon (Importance sampling and why long horizons kill it).

At H = 20 steps the smallest and largest weights sit 2^40 ~ 1e12 apart — twelve orders of magnitude, not the six you get by mistakenly reading 2^20 as the spread. Run the ESS formula on weights with that range and it collapses to single digits, regardless of how much data you logged. More logging does not help, because the problem is the ratio between rows, not their count.

Reliable off-policy evaluation is available in bandits and essentially unavailable in full RL, and that alone decides most production architecture questions.

When full RL is the wrong tool

The decision is three questions deep, and the diagram below is the whole of it:

1. Does the action change the state of the next decision?
2. If it does — is there a faithful simulator, or cheap reversible exploration, so that mistakes can be made somewhere they do not cost anything?
3. If there is — is the reward the real objective, and measurable within the horizon you are training over?

flowchart TD
    Q1{"Does the action change<br/>the state of the next decision?"} -->|no| B["Contextual bandit<br/>log propensities, IPS/DR evaluation"]
    Q1 -->|yes| Q2{"Is there a faithful simulator,<br/>or cheap reversible exploration?"}
    Q2 -->|no| SL["Supervised learning on logged outcomes<br/>plus a hand-written policy"]
    Q2 -->|yes| Q3{"Is the reward the real objective,<br/>and measurable within the horizon?"}
    Q3 -->|no| SL
    Q3 -->|yes| RL["Full RL"]

    style B fill:#2d6a4f,color:#fff
    style SL fill:#2d6a4f,color:#fff
    style RL fill:#bc6c25,color:#fff

The colours mark one distinction: can you tell whether it works before shipping it?

The two green terminals are the ones you can evaluate offline — a bandit through IPS or doubly-robust estimation, supervised learning through an ordinary held-out set.

The orange terminal is the one you cannot. Full RL’s off-policy estimates collapse for the reason Importance sampling and why long horizons kill it gave, so the only honest way to learn whether it works is to run it on real traffic. That is the same distinction as the “Offline evaluation” row of the table below.

Reading the routes:

• “No” at the first question routes you to a contextual bandit with logged propensities and IPS or doubly-robust (DR) evaluation.
• “No” at either of the other two routes you to plain supervised learning on logged outcomes with a hand-written policy on top. Unglamorous, and correct far more often than it is chosen.
• Only “yes” at all three earns full RL.

The requirements differ on six axes:

Use full RL only when your action changes the state the next decision faces, and you can either simulate that state or afford to learn it on real users.

In ranking, ads, and most recommendation, neither clause holds. The next request is drawn from the same distribution regardless of what you served, so a contextual bandit is not a simplification — it is the correct model.

The common failure is the opposite of what people expect. Not that RL underperforms, but that you cannot tell whether it does until it is already live.

The same logic applies to agents built on large language models. A per-turn decision that does not alter what the user asks next is a bandit problem. An agent editing a codebase across 40 turns genuinely is sequential — which is why RLHF trains on whole completions, and why The forward pass — one token per forward pass, each conditioned on all previous ones — is the sequential structure the reward has to be assigned across.

12. The assumptions, and what breaks when they fail

Every result in this chapter is a theorem, and every theorem has a premise. The premises belong in one place, each paired with the method it supports and with what its failure actually looks like — because none of these failures announce themselves, and all of them are survivable if you know what you are watching for.

The Markov property

What it assumes: the current state summarises everything from the past that predicts the future, so V(s) and Q(s,a) are well-defined functions of the state alone.

What depends on it: every Bellman equation in Value functions q functions bellman, and therefore value iteration, SARSA, Q-learning, DQN, and every critic in an actor-critic method.

How it breaks: partial observability. A trading agent that sees prices but not order flow. A dialogue agent whose state omits what was said five turns ago. A robot with a camera and no memory of what was behind it.

The consequence is not noise. Two situations that demand different actions look identical to the learner, so the value estimate converges to an average over both and is right in neither.

The symptom: a policy that performs well on aggregate metrics and fails reproducibly on a specific subpopulation you cannot characterise.

The repairs: widen the state with a history window, or carry a learned recurrent state that acts as a memory of what the observation left out.

Stationarity

What it assumes: the transition kernel P and the reward function R do not change over time, so a fixed point exists for the learning process to converge to.

What depends on it: the contraction argument that makes value iteration converge, every regret bound in Exploration vs exploitation, and the entire premise of training now and deploying later.

How it breaks: users change, competitors respond, seasons turn. And — the case people forget — your own deployment changes the environment, because a policy that reshapes what users see reshapes the population it will be evaluated on next quarter.

The consequence is that convergence becomes a liability. An algorithm that provably stops exploring is provably unable to notice the world moved.

The symptom: a model that scores well offline against a recent snapshot and degrades in production at a rate nobody can attribute.

The repairs, all of which amount to refusing to fully converge: discount old data, hold a sliding window, keep an exploration floor, shorten gamma below what the theory recommends, and retrain on a schedule rather than on a metric.

The reward is the objective

What it assumes: the scalar R(s,a) is what you want, not a measurable stand-in for what you want.

What depends on it: everything. No algorithm in this chapter has any access to your intent other than through that number.

How it breaks: reward hacking, worked concretely in The rl step and the kl leash.

The optimizer is an efficient search for the highest-scoring behaviour. So any gap between the score and the goal is not a small error — it is a target, and the optimizer will find it.

The RLHF trace is the canonical evidence: the reward model’s score climbs monotonically from 0.12 to 2.71 while human win-rate rises to 71% and then falls to 31%. The same mechanism produces a click-optimizing feed full of outrage, and a survival-bonus agent that learns to stand perfectly still.

The symptom is the dangerous part: your metrics improve, smoothly and convincingly, throughout.

There is no complete fix, only four partial ones. Every serious system uses several:

1. Constrain the policy to stay near the distribution the proxy was fitted on. That is what the KL leash does.
2. Evaluate against something the optimizer cannot optimize against — human judgement, or a held-out judge the policy was never trained on.
3. Optimize less than you can, stopping at the peak rather than at convergence.
4. Treat any monotone improvement in a proxy across a long run as evidence of hacking until shown otherwise, because genuine progress on a hard objective is almost never monotone.

The smaller assumptions, and where they bind

Beyond the big three, each method carries a narrower premise of its own, and the table pairs each with the method that needs it and the symptom you would actually observe:

The through-line: RL replaces a labelled dataset with a specification, and a specification is a thing that can be wrong in ways a dataset cannot.

A mislabelled example degrades a supervised model in proportion to how often it occurs — one bad row in ten thousand costs you roughly one ten-thousandth of your accuracy.

A misspecified reward is sought out, amplified, and optimized into the policy. It does not cost you in proportion to anything; the optimizer’s job is to find it.

That is why the reward function, not the algorithm, is where nearly all the engineering risk in a real RL project lives.

Cheat sheet

Every claim derived above, compressed to the one line of mechanism that justifies it. If a row is not obvious, the section it came from is the one to reread.

Next: 09 — Model Debugging Playbook.