Reinforcement learning

Supervised learning needs a correct answer for every example. Reinforcement learning does not: an agent acts, receives a score, and has to work out for itself which of its actions earned it. This section covers the setup and the two hard problems inside it — exploring enough to find good behaviour at all, and assigning credit when the reward arrives long after the action that deserved it. It is here rather than in a robotics course because training a language model from human preferences is reinforcement learning, and the alignment literature assumes you have this vocabulary.

The setup#

An agent observes a state, takes an action, receives a reward and moves to a new state. It learns a policy, a mapping from states to actions, that maximises reward over time. Unlike supervised learning there is no correct answer given, only a score.

Every one of those words is used in a specific way and the papers never stop to define them, so here they are against a concrete example. A shop wants to decide which of three versions of its checkout page to show each visitor.

word          what it means                          in the checkout example

agent         the thing choosing                    your ranking service
environment   everything else, which answers back    the visitor and the shop
state         what the agent can see right now       the visitor's country and device
action        one of the choices available           show page A, B or C
reward        a number scoring what just happened    1 if they bought, 0 if not
policy        the rule from state to action          "on mobile, show B"
episode       one run from start to finish           one visit, from landing to leaving
return        the rewards of an episode added up,    total purchases from that visit,
              with later ones discounted             counting today more than next month
value         the return you expect from a state     what a mobile visitor is worth
              if you follow the policy

The policy is the thing being learned and the only thing you ship. Everything else — values, returns, advantages — exists to work out how the policy should change. If you remember one sentence from this section, make it that.

Why this is not supervised learning with extra steps#

It is tempting to read the setup as classification with a strange loss. It is not, and three differences are the reason the field has its own algorithms.

• There is no label. Nobody says which action was correct, only what score followed the one you took. You never find out what the other actions would have paid.
• Consequences are delayed. The reward that arrives now may have been earned twenty actions ago, and working out which one earned it is the credit assignment problem.
• Your own behaviour produces your data. A supervised dataset sits still. A policy that never turns right never sees what is to the right, so it cannot learn that the right-hand path was better.

The third one is the strangest and the easiest to underrate, so here it is measured. A corridor of nine squares, starting in the middle. Falling off the left end pays 0.1, falling off the right end pays 1.0, and the policy is a single number: the probability of stepping right.

import random

CORRIDOR = 9                       # squares 0 to 8; both ends end the episode
START, SMALL, BIG = 4, 0.1, 1.0

def walk(p_right, rng, cap=500):
    s, visited = START, []
    for _ in range(cap):
        visited.append(s)
        s += 1 if rng.random() < p_right else -1
        if s <= 0:
            return visited, SMALL
        if s >= CORRIDOR - 1:
            return visited, BIG
    return visited, 0.0

for p_right in (0.3, 0.5, 0.7):
    rng = random.Random(0)
    seen, big = [0] * CORRIDOR, 0
    for _ in range(2000):
        visited, r = walk(p_right, rng)
        for s in visited:
            seen[s] += 1
        big += (r == BIG)
    print(f"p(right)={p_right}: found the big reward in {100*big/2000:5.1f}% of episodes  visits {seen}")
# p(right)=0.3: found the big reward in   3.8% of episodes  visits [0, 2808, 4003, 4389, 4523, 1795, 691, 225, 0]
# p(right)=0.5: found the big reward in  48.6% of episodes  visits [0, 2119, 4084, 5961, 7975, 6013, 4031, 1997, 0]
# p(right)=0.7: found the big reward in  96.4% of episodes  visits [0, 229, 736, 1975, 4709, 4416, 3865, 2690, 0]

The agent that leans left is not merely slower. It collects almost no data about the half of the corridor where the good reward lives, and the data it does collect keeps telling it that left pays 0.1, which is better than the zero it has estimated for right. A supervised model with a bad initialisation still sees the whole training set on the next epoch. A policy with a bad initialisation may never see the part of the world that would correct it. This is why exploration is a first-class problem here and barely a topic anywhere else.

Return, and what the discount actually decides#

Rewards are added up over an episode, with later ones multiplied by a discount factor gamma raised to the number of steps away they are. Gamma is usually described as how far-sighted the agent is, which is true but vague. What it concretely does is set the exchange rate between a reward now and a larger reward later, and you can read that rate off directly.

now   = [1.0, 0, 0, 0, 0, 0]        # one point, straight away
later = [0, 0, 0, 0, 0, 10.0]       # ten points, five steps from now

def ret(rewards, gamma):
    return sum(r * gamma ** t for t, r in enumerate(rewards))

for gamma in (0.0, 0.5, 0.631, 0.9, 0.99):
    print(f"gamma {gamma:5.3f}:  take it now {ret(now, gamma):6.3f}   wait five steps {ret(later, gamma):6.3f}")
print("crossover at gamma =", round((1 / 10) ** (1 / 5), 3))
# gamma 0.000:  take it now  1.000   wait five steps  0.000
# gamma 0.500:  take it now  1.000   wait five steps  0.312
# gamma 0.631:  take it now  1.000   wait five steps  1.000
# gamma 0.900:  take it now  1.000   wait five steps  5.905
# gamma 0.990:  take it now  1.000   wait five steps  9.510
# crossover at gamma = 0.631

So gamma is part of the problem specification, not a training detail. Set it low and the agent is provably right to be short-sighted, and no amount of training will fix behaviour you have defined as optimal. Set it near 1 and the horizon is long, values grow towards the sum of everything, and learning gets slower and noisier because a single early action is now credited with thousands of later rewards. 0.99 is the usual default for episodes of a few hundred steps, which values a reward a hundred steps away at about a third of one received now.

The two hard problems#

• Credit assignment: a reward arrives after a long sequence of actions. Which of them was responsible? This is the central difficulty.
• Exploration versus exploitation: repeat what worked, or try something new that might work better. Too much of either fails.

Policy gradients#

Rather than learning the value of each state, directly adjust the policy to make high-reward actions more likely. PPO is the widely used variant, and its key idea is limiting how far the policy can move in one update, because large policy changes destabilise training.

The reason the limit matters is the third difference above. In supervised learning a step that overshoots makes the loss worse and the next batch pulls it back, because the data is the same data either way. In reinforcement learning a step that overshoots changes which states the agent visits, so the next batch is drawn from a worse part of the world, and the correction never arrives. PPO's clip is a crude guard against exactly that, and the policy-gradients section of this topic builds it from REINFORCE upwards with the numbers measured.

Why this matters for language models#

The largest practical impact is post-training. A pretrained model produces plausible text; making it helpful and harmless is done by learning from preferences, which is reinforcement learning with the reward derived from human judgement rather than a game score.

The mapping is exact rather than metaphorical. The state is the prompt plus the tokens generated so far, the action is the next token, the policy is the model, one episode is one response, and the reward is a single score for the finished response — which makes it the sparse, delayed, end-of-episode case, the hardest kind. Sequence-level rewards are why post-training needs the variance machinery at all. How the score itself is produced, and what goes wrong when it is a learned stand-in for human judgement, is the alignment topic's subject; this topic supplies the algorithms it assumes.

What to skip if you are an AI engineer rather than a researcher: the classical control literature. Dynamic programming proofs, convergence conditions, continuous-control benchmarks, the Atari results and the exploration-bonus papers are a large and interesting body of work you will not use. Learn the vocabulary on this page, the bandit section because it is genuinely useful for ranking and experimentation, and the section on language models because it is what alignment work is built from. Q-learning and policy gradients are worth doing once with your own hands so that PPO is not a magic word, and then left alone.

Reinforcement learning papers assume you can place a method in a family and know why it has the shape it does. This section gives you that: the split between learning what states are worth and learning behaviour directly, the recursive definition that makes credit assignment possible at all, and why the standard algorithm's main feature is a limit on how far one update may move. It closes on why the field is unstable, which is also why a reported improvement on a single seed is not a result.

Two families#

• Value methods learn how good a state or action is, then act greedily with respect to that. Q-learning is the canonical example. They suit discrete action spaces.
• Policy methods learn the behaviour directly, adjusting the probability of actions according to the reward that followed. They handle continuous actions and are what language model post-training uses.
• Actor-critic combines both: a policy that acts and a value estimate that reduces the variance of its updates. Most modern methods are in this family.

Placing a method takes three questions, and a paper's abstract usually answers all three in its first two sentences.

question                          answer            what it tells you

what does the network output?     action values     value method: DQN, Rainbow, double DQN
                                  action probs      policy method: REINFORCE, TRPO, PPO, GRPO
                                  both              actor-critic: A2C, SAC, DDPG, TD3

can it learn from old data?       yes               off-policy: replay buffers, sample-efficient,
                                                    prone to divergence with a network
                                  no                on-policy: fresh rollouts each update,
                                                    stable, expensive in experience

what are the actions?             discrete          argmax is available, value methods work
                                  continuous        argmax over actions is not available,
                                                    so policy or actor-critic

The Bellman idea#

The value of a state is the immediate reward plus the discounted value of wherever you end up next. That recursive definition lets you propagate information backwards from rewards to the states that led to them, which is how credit assignment is done in practice.

value(state) = reward + discount x value(next state)

The discount factor decides how much the future counts. Near 1
means far-sighted and slow to learn. Near 0 means short-sighted.

Two properties make that definition useful rather than merely circular. Applying it as an assignment — compute the right-hand side from your current guesses and overwrite the left — shrinks the largest error in the value table by a factor of gamma every pass, so repeated sweeps converge to a unique answer from any starting guess. And the algorithms differ mainly in what they put on the right. Value iteration takes the exact expectation because it has the environment's transition probabilities; Q-learning replaces that expectation with a single sampled next state and takes a small step towards it; policy-gradient methods drop the recursion entirely and use a whole episode's return. Sampled, model-free versions of the same line are what you use when nobody will give you the transition probabilities, which is almost always.

Why PPO constrains the step#

In supervised learning a bad update makes the loss worse and the next batch corrects it. In RL a bad update changes the policy, which changes the data you collect next, which can make recovery impossible. The system can destroy itself in a way supervised learning cannot.

PPO clips how far the policy is allowed to move in one update. That is essentially the whole idea, and it is why it became the default: not because it is clever but because it is hard to blow up.

Why RL is hard#

• The data distribution depends on the policy, so it shifts as you learn. Nothing is stationary.
• Rewards are sparse and delayed, so credit assignment is genuinely ambiguous.
• Exploration is unsolved in general. Too little and you never find the good behaviour; too much and you never exploit it.
• Variance is high, so results need many seeds and reported RL improvements have a poor reproducibility record.

Those four are usually read as cautions. They are better read as numbers, and small experiments produce them honestly. Sample inefficiency first: on the 4-by-4 slippery gridworld in this topic's Q-learning section, value iteration reaches the optimal policy in 36 sweeps of 13 squares by 4 actions, which is 1,872 backups, because it is handed the transition probabilities. Q-learning on the same grid, with only sampled transitions, needs about 54,000 environment steps to land within one and a half per cent of the same policy. Twenty-nine times the work for a problem with thirteen states, and the gap widens with the state space rather than narrowing.

Balancing a pole described by four numbers cost about 110,000 environment steps across 400 episodes with REINFORCE, and roughly 42,000 to 58,000 before the pole stayed up reliably. Hold that next to a supervised problem of comparable difficulty, which is a few thousand labelled examples, and the rule of thumb writes itself: reinforcement learning buys you the ability to learn without labels, and it pays for it in orders of magnitude of experience. That is affordable in a simulator and rarely affordable against the real world.

Seed sensitivity is the one that damages careers. In that same cart-pole run, the identical code at three seeds ended at 293, 500 and 14 steps per episode. The third seed is not a slow seed, it is a collapsed one: it found a good region, took a large update, and never recovered. Any of those three numbers could have been reported as the result of the method. This is why RL papers are expected to show several seeds with a spread, why a single learning curve is not evidence, and why you should distrust your own first good run as much as anyone else's.

Reward hacking is not an exotic failure#

The optimiser has no idea what you meant. It has your reward function, and if there is a way to score well that you did not intend, enough optimisation will find it. This is easiest to believe once you have caused it deliberately, which takes about thirty lines. The environment is a 4-by-4 grid with a goal worth 1, a hole worth -1 and a small cost per step. To help the agent along, someone adds what looks like a harmless progress bonus: 0.3 for stepping onto a square on the way.

import random

GRID = ["S...",
        ".#.H",
        "..b.",
        "...G"]          # b is an ordinary square; the shaping bonus is attached to it
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]
GAMMA, STEP_COST = 0.95, -0.04
BONUS_SQUARE = 2 * 4 + 2

def at(s):
    r, c = divmod(s, 4)
    return GRID[r][c]

def arrive(s):
    return {"G": 1.0, "H": -1.0}.get(at(s), STEP_COST)

def move(s, a):
    r, c = divmod(s, 4)
    dr, dc = MOVES[a]
    nr, nc = r + dr, c + dc
    if not (0 <= nr < 4 and 0 <= nc < 4) or GRID[nr][nc] == "#":
        return s
    return nr * 4 + nc

def train(seed, bonus, episodes=3000, alpha=0.1):
    rng = random.Random(seed)
    Q = [[0.0] * 4 for _ in range(16)]
    eps = 1.0
    for ep in range(episodes):
        s = 0
        for t in range(100):
            a = rng.randrange(4) if rng.random() < eps else max(range(4), key=lambda x: Q[s][x])
            ns = move(s, a)
            r = arrive(ns) + (bonus if ns == BONUS_SQUARE else 0.0)
            done = at(ns) in "GH"
            Q[s][a] += alpha * (r + (0.0 if done else GAMMA * max(Q[ns])) - Q[s][a])
            s = ns
            if done: break
        eps = max(0.05, eps * 0.999)
    return Q

def rollout(Q):
    s, path, bonus_visits = 0, [0], 0
    for t in range(60):
        s = move(s, max(range(4), key=lambda a: Q[s][a]))
        path.append(s)
        if s == BONUS_SQUARE: bonus_visits += 1
        if at(s) in "GH": break
    return path, bonus_visits, at(s)

for bonus in (0.0, 0.3):
    for seed in range(3):
        Q = train(seed, bonus)
        path, bv, end = rollout(Q)
        print(f"bonus {bonus}: seed {seed} steps {len(path)-1:3d} "
              f"visits to the bonus square {bv:3d} ends on '{end}'")
# bonus 0.0: seed 0 steps   6 visits to the bonus square   0 ends on 'G'
# bonus 0.0: seed 1 steps   6 visits to the bonus square   0 ends on 'G'
# bonus 0.0: seed 2 steps   6 visits to the bonus square   0 ends on 'G'
# bonus 0.3: seed 0 steps  60 visits to the bonus square  29 ends on 'b'
# bonus 0.3: seed 1 steps  60 visits to the bonus square  29 ends on 'b'
# bonus 0.3: seed 2 steps  60 visits to the bonus square  29 ends on 'b'

Nothing went wrong. The agent maximised the reward it was given: a repeatable 0.3 beats a one-off 1.0 that ends the episode. Notice also what the metrics would have said. Average reward per episode went up, which is the number you would have plotted, and the completion rate went to zero, which is the number you cared about. Every real reward-hacking story has that shape — the proxy improves and the thing you wanted gets worse — whether the agent is a boat driving in circles through a bonus pickup or a language model padding its answers because the reward model likes length.

The fix is not a cleverer bonus. Potential-based shaping, where the bonus is a difference of some function of the state, is the one form provably unable to change the optimal policy, and that is the shape to reach for if you must shape at all. Otherwise, score the outcome you actually want, and audit with a held-out measure the optimiser never sees.

Reinforcement learning is far easier to understand if you take the states out of it first. This section does that: a fixed set of options, a reward after each choice, and nothing else, which isolates the one question that makes the whole field hard, namely when to stop trying alternatives and commit to whatever looks best so far. You implement three answers to it and compare them on a measure of what the choosing itself cost you.

Strip RL down to one decision#

Imagine three versions of a signup page. Each visitor sees one, and either signs up or does not. You do not know which version is best, and every visitor you send to a worse one is a lost signup. This is a multi-armed bandit: repeated choices, a reward after each, no states to worry about. It isolates the exploration problem cleanly.

The measure that makes the comparison honest is regret: the signups you would have had if you had known the best page from the start, minus the signups you actually got. It is not something the agent can compute — it needs the true rates — but you can compute it in a simulation, and it is the only number that scores the choosing itself rather than the luck. Everything below is measured against these three pages, whose true rates are 5, 7 and 10 per cent, which is the sort of gap a real page test lives with.

import random

RATES = [0.05, 0.07, 0.10]          # the true signup rate of each page. The agent never sees this.
BEST = max(RATES)

def visit(page):
    """One visitor sees one page and either signs up or does not."""
    return 1 if random.random() < RATES[page] else 0

def regret(plays):
    """Signups lost by not having shown the best page to every visitor."""
    return sum(BEST - RATES[p] for p in plays)

Epsilon-greedy#

Most of the time pick the action with the best average so far. With a small probability, epsilon, pick at random. Simple, and it works, but it keeps exploring obviously bad options forever at the same rate.

import random

class EpsilonGreedy:
    def __init__(self, n, eps=0.1):
        self.counts, self.means, self.eps = [0] * n, [0.0] * n, eps

    def choose(self):
        if random.random() < self.eps:
            return random.randrange(len(self.means))
        return max(range(len(self.means)), key=lambda a: self.means[a])

    def update(self, a, reward):
        self.counts[a] += 1
        self.means[a] += (reward - self.means[a]) / self.counts[a]   # running mean

Optimism: upper confidence bounds#

UCB picks the action whose plausible best case is highest: its average plus a bonus that is large when it has been tried rarely. Untried actions get explored, well-understood bad actions are dropped, and exploration fades naturally.

import math

def ucb_choose(counts, means, t):
    for a, c in enumerate(counts):
        if c == 0:
            return a                                   # try everything once
    return max(range(len(means)),
               key=lambda a: means[a] + math.sqrt(2 * math.log(t) / counts[a]))

Thompson sampling#

Keep a belief about each action's success rate as a probability distribution. Each round, draw one sample from each belief and pick the highest draw. Actions you are unsure about sometimes draw high and get tried; actions you are confident are poor rarely do. For yes or no rewards, the Beta distribution makes this a few lines.

import random

wins, losses = [1, 1, 1], [1, 1, 1]          # Beta(1, 1) prior: know nothing

def thompson_choose():
    draws = [random.betavariate(w, l) for w, l in zip(wins, losses)]
    return draws.index(max(draws))

def thompson_update(a, reward):
    if reward: wins[a] += 1
    else:      losses[a] += 1

Measuring it: regret#

Regret is the reward you missed by not always playing the best action. Plot cumulative regret over time for each strategy. A good strategy's regret curve bends and flattens; a bad one keeps climbing in a straight line.

Straight-line regret is what committing produces, and the usual alternative to a bandit is exactly that: run a fixed split for a while, declare a winner, send everything to it. Here are all of them, including that one, at two horizons, over 400 simulated runs each. Two horizons matter because a strategy that ends on the wrong page loses at a constant rate forever, so its regret grows with the length of the experiment while a bandit's does not.

def run_pilot(steps, per_page):
    """The usual thing: a fixed split, then all traffic to the winner."""
    agent, plays = EpsilonGreedy(3, eps=0.0), []
    for page in range(3):
        for _ in range(per_page):
            agent.update(page, visit(page))
            plays.append(page)
    winner = agent.choose()
    return regret(plays + [winner] * (steps - 3 * per_page)), winner

def run_epsilon(steps, eps):
    agent, plays = EpsilonGreedy(3, eps), []
    for _ in range(steps):
        a = agent.choose()
        agent.update(a, visit(a))
        plays.append(a)
    return regret(plays), max(range(3), key=lambda a: agent.counts[a])

def run_ucb(steps, c=2.0):
    counts, means, plays = [0] * 3, [0.0] * 3, []
    for t in range(1, steps + 1):
        if min(counts) == 0:
            a = counts.index(0)                          # every page once before judging any
        elif c == 2.0:
            a = ucb_choose(counts, means, t)             # the block above, textbook constant
        else:
            a = max(range(3),
                    key=lambda p: means[p] + math.sqrt(c * math.log(t) / counts[p]))
        counts[a] += 1
        means[a] += (visit(a) - means[a]) / counts[a]
        plays.append(a)
    return regret(plays), max(range(3), key=lambda a: counts[a])

def run_thompson(steps):
    wins[:] = [1, 1, 1]
    losses[:] = [1, 1, 1]                                # forget the previous run
    counts, plays = [0] * 3, []
    for _ in range(steps):
        a = thompson_choose()
        thompson_update(a, visit(a))
        counts[a] += 1
        plays.append(a)
    return regret(plays), max(range(3), key=lambda a: counts[a])

STRATEGIES = {
    "pilot of 50 each":   lambda n: run_pilot(n, 50),
    "pilot of 300 each":  lambda n: run_pilot(n, 300),
    "epsilon-greedy 0.10": lambda n: run_epsilon(n, 0.10),
    "epsilon-greedy 0.01": lambda n: run_epsilon(n, 0.01),
    "UCB, c = 2 (textbook)": lambda n: run_ucb(n, 2.0),
    "UCB, c = 0.2 (tuned)": lambda n: run_ucb(n, 0.2),
    "Thompson":            run_thompson,
}

for horizon in (2000, 20000):
    print(f"{horizon} visitors, averaged over 400 runs")
    for name, strategy in STRATEGIES.items():
        random.seed(0)
        lost, wrong = 0.0, 0
        for run in range(400):
            r, final = strategy(horizon)
            lost += r
            wrong += (final != 2)                        # page 3 is the best one
        print(f"  {name:22s} {lost/400:7.1f} signups lost   "
              f"settled on the wrong page {100*wrong/400:5.1f}%")
# 2000 visitors, averaged over 400 runs
#   pilot of 50 each          29.5 signups lost   settled on the wrong page  39.5%
#   pilot of 300 each         27.7 signups lost   settled on the wrong page  10.8%
#   epsilon-greedy 0.10       29.6 signups lost   settled on the wrong page  25.2%
#   epsilon-greedy 0.01       72.6 signups lost   settled on the wrong page  74.8%
#   UCB, c = 2 (textbook)     41.9 signups lost   settled on the wrong page   2.5%
#   UCB, c = 0.2 (tuned)      23.3 signups lost   settled on the wrong page   0.8%
#   Thompson                  17.9 signups lost   settled on the wrong page   5.5%
# 20000 visitors, averaged over 400 runs
#   pilot of 50 each         277.9 signups lost   settled on the wrong page  39.5%
#   pilot of 300 each         87.5 signups lost   settled on the wrong page  10.8%
#   epsilon-greedy 0.10       86.4 signups lost   settled on the wrong page   0.8%
#   epsilon-greedy 0.01      245.9 signups lost   settled on the wrong page  21.2%
#   UCB, c = 2 (textbook)    255.1 signups lost   settled on the wrong page   0.0%
#   UCB, c = 0.2 (tuned)      64.1 signups lost   settled on the wrong page   0.0%
#   Thompson                  33.1 signups lost   settled on the wrong page   0.0%

Start with the pilot. Fifty visitors per page sounds like a test; at those rates the standard error of each estimate is about 3 percentage points against gaps of 2 and 3, so it picks the wrong page 39.5 per cent of the time. That error is then permanent, which is why its regret rises from 29.5 to 277.9 when the experiment runs ten times longer while every bandit's rises far less. Three hundred visitors per page is a real test and gets the wrong answer 10.8 per cent of the time — better, and still linear in the horizon.

Epsilon-greedy at 0.01 is the clearest failure on the page, and it is the one people write by accident when they think a small epsilon means a careful agent. It settles on the wrong page 74.8 per cent of the time at 2,000 visitors. Its first few observations are almost all zeros — nobody signs up — and a page that scores an early success is then ahead of the others with only a one in a hundred chance per visitor of anything else being tried. It is not exploring too little in general; it is exploring too little early, when the estimates are worthless. At 0.10 it recovers and its regret is respectable, at the price of permanently sending a tenth of visitors to pages it already knows are worse, which is why its regret also grows linearly, from 29.6 to 86.4.

The two UCB rows are the trap worth taking away. The textbook bonus assumes rewards spread across the whole of 0 to 1; here they are all near 0.07, so a bonus of the square root of two log t over n swamps every real difference and the agent explores far past the point of usefulness — 255.1 lost at the long horizon, worse than epsilon-greedy, while never once ending on the wrong page. Dropping the constant to 0.2 cuts that to 64.1. A method with an exploration constant tuned for your reward scale is a different method from the one in the paper, and the constant is not optional.

Thompson sampling wins at both horizons with no tuning at all, which is the usual outcome of this comparison and the reason it is widely used in production ranking systems. Its exploration is proportional to how uncertain it actually is, so it needs no schedule and no constant, and its regret bends: 17.9 over 2,000 visitors and only 33.1 over 20,000, since almost all of the cost is paid early.

Where an engineer actually meets this#

Bandits are the one piece of reinforcement learning that turns up routinely in ordinary product work, usually without the name. Anywhere you have many candidate items, a cheap binary signal and traffic to spend, the machinery above applies directly.

• Ranking and recommendation. Which of a thousand candidate articles to put in the slot, where a click is the reward. Almost always contextual: the features of the user and the item go into a model that predicts reward, and Thompson sampling or an upper confidence bound is applied to that model's uncertainty rather than to a per-item count.
• Anything with a cold start. New items have no history, so a purely greedy ranker will never show them and they will never acquire one. This is exactly the locked-on failure above, and it is why catalogues that rank purely on measured click-through go stale.
• Model and prompt selection at serving time. Several prompts or several models, a thumbs-up or a task success signal, and a slow shift towards whichever is winning — a bandit, and a much better fit than an offline evaluation when the traffic is already there.
• Non-stationary rewards. Real click rates drift. The estimators above assume they do not, and the standard fix is to discount old evidence: an exponentially weighted mean instead of a running one, or decaying the Beta counts towards the prior so the agent stays willing to re-check.

Put the states back and the question changes: not which option pays off now, but which actions lead somewhere good later. This section builds the classic answer in full, as a table of what each action in each state is worth, an update rule that nudges those numbers towards what actually happened, and a runnable agent on a small environment. It then covers what changes when the table is replaced by a neural network, and why the naive version of that diverges.

What Q means#

Q(s, a) is the total future reward you expect if you take action a in state s and act well afterwards. If you knew Q exactly, acting well would be trivial: in each state, take the action with the highest Q. Q-learning estimates it from experience.

The difference between Q and the plain value V is worth being precise about, because it is what makes Q the useful one. V(s) says how good a state is, which tells you nothing about what to do unless you also know where each action leads. Q(s, a) says how good each action is from that state, so the policy falls out as an argmax over four numbers and no model of the environment is needed. That is the whole reason value methods are written in terms of Q. It is also the reason they need a small, countable set of actions: you cannot take an argmax over a steering angle.

The update#

Q[s, a] += alpha * ( r + gamma * max(Q[s_next]) - Q[s, a] )
                     \______________________/   \_____/
                       what we just learned     what we believed

alpha   step size: how far to move towards the new estimate
gamma   discount: how much future reward counts (0.99 is common)
r + gamma * max(Q[s_next])   the target: reward now plus the best value from where we landed

The difference in brackets is the temporal difference error: how surprised we were. The update nudges the old belief towards the new evidence. Reward information flows backwards one step at a time, from the goal to the states that lead to it. That is credit assignment in practice.

An environment small enough to check#

Write the environment rather than importing one. Thirteen squares you can decide in means the whole table fits on the screen, and it means you can compute the right answer separately and hold the agent to it, which no benchmark environment lets you do. This is a 4-by-4 grid with a goal worth 1, a hole worth -1, a wall, and a cost of 0.04 per step so that dawdling is penalised. The floor is slippery: an action goes where you intended 80 per cent of the time and sideways otherwise, which is what stops the problem being a maze puzzle.

import random

GRID = ["S...",
        ".#.H",
        "....",
        "...G"]                                  # S start, # wall, H hole, G goal
MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]       # up right down left
ARROWS = "^>v<"
GAMMA, STEP_COST, SLIP = 0.95, -0.04, 0.1

def at(s):                                       # the character on square s
    r, c = divmod(s, 4)
    return GRID[r][c]

def is_end(s):
    return at(s) in "GH"

def arrive(s):                                   # reward for arriving on square s
    return {"G": 1.0, "H": -1.0}.get(at(s), STEP_COST)

def slide(s, a):                                 # where action a lands you
    r, c = divmod(s, 4)
    dr, dc = MOVES[a]
    nr, nc = r + dr, c + dc
    if not (0 <= nr < 4 and 0 <= nc < 4) or GRID[nr][nc] == "#":
        return s                                 # walls and edges: you stay put
    return nr * 4 + nc

def outcomes(s, a):                              # the floor is slippery
    p = {}
    for act, prob in ((a, 0.8), ((a + 1) % 4, 0.1), ((a - 1) % 4, 0.1)):
        ns = slide(s, act)
        p[ns] = p.get(ns, 0.0) + prob
    return list(p.items())

def step(s, a, rng):                             # one sampled transition
    u = rng.random()
    if u < SLIP:       a = (a + 1) % 4
    elif u < 2 * SLIP: a = (a - 1) % 4
    ns = slide(s, a)
    return ns, arrive(ns), is_end(ns)

squares = [s for s in range(16) if at(s) != "#"]
inner = [s for s in squares if not is_end(s)]
print(len(inner), "squares to decide in,", len(inner) * 4, "state-action pairs in the table")
# 13 squares to decide in, 52 state-action pairs in the table

Because the transition probabilities are written down, the exact answer is available without any learning. Value iteration applies the Bellman assignment to every square until nothing moves, and what comes out is the best any policy can do. Keep it: it is the ruler that every later claim gets measured against.

V = [0.0] * 16
for sweep in range(1, 1001):
    nxt = list(V)
    for s in inner:
        nxt[s] = max(sum(p * (arrive(ns) + GAMMA * V[ns]) for ns, p in outcomes(s, a))
                     for a in range(4))
    delta = max(abs(nxt[s] - V[s]) for s in inner)
    V = nxt
    if delta < 1e-9:
        break

def greedy_policy(value):
    return {s: max(range(4), key=lambda a: sum(p * (arrive(ns) + GAMMA * value[ns])
                                               for ns, p in outcomes(s, a)))
            for s in inner}

def draw(policy):
    for r in range(4):
        print(" ".join(ARROWS[policy[r * 4 + c]] if r * 4 + c in policy else at(r * 4 + c)
                       for c in range(4)))

best = greedy_policy(V)
print("converged after", sweep, "sweeps")
for r in range(4):
    print(" ".join(f"{V[r * 4 + c]:6.3f}" if at(r * 4 + c) != "#" else "  wall" for c in range(4)))
draw(best)
# converged after 36 sweeps
#  0.481  0.402  0.453  0.231
#  0.576   wall  0.570  0.000
#  0.666  0.765  0.858  0.965
#  0.737  0.847  0.965  0.000
# v < v <
# v # v H
# > > v v
# > > > G

Read the policy and the environment is explained back to you. The top-right corner steers left, away from the hole below it, even though that is the long way round: with a 10 per cent chance of sliding sideways, standing next to a -1 is not worth 0.04 a step. The start square is worth 0.481, which is the number to remember, because everything the learner does from here is judged against it.

The whole thing, runnable#

Now throw the transition probabilities away. The agent gets only the sampler: it acts, it sees where it landed and what it got. Epsilon starts at 1, which is pure random flailing, and decays as the table fills.

def q_learn(seed, episodes, alpha=0.1, init=0.0, mask_terminal=True):
    rng = random.Random(seed)
    Q = [[init] * 4 for _ in range(16)]
    visits = [0] * 16
    eps, env_steps = 1.0, 0
    for ep in range(episodes):
        s = 0
        for t in range(100):
            a = rng.randrange(4) if rng.random() < eps else max(range(4), key=lambda x: Q[s][x])
            ns, r, done = step(s, a, rng)
            target = r + (0.0 if done and mask_terminal else GAMMA * max(Q[ns]))
            Q[s][a] += alpha * (target - Q[s][a])
            visits[s] += 1
            env_steps += 1
            s = ns
            if done:
                break
        eps = max(0.05, eps * 0.999)                     # explore less as the table fills
    return Q, visits, env_steps

Q, visits, env_steps = q_learn(seed=0, episodes=5000)
learned = {s: max(range(4), key=lambda a: Q[s][a]) for s in inner}
print(env_steps, "environment steps; value of the start square:",
      round(max(Q[0]), 3), "against", round(V[0], 3), "from value iteration")
draw(learned)
print("squares where the two policies disagree:", [s for s in inner if learned[s] != best[s]])
# 53882 environment steps; value of the start square: 0.474 against 0.481 from value iteration
# v < < <
# v # v H
# v > v v
# > > > G
# squares where the two policies disagree: [2, 8]

Two squares out of thirteen came out different, and the reason is not that the agent is half-trained. Count where it has been.

def true_value(policy):
    """Exact expected return of a policy, by sweeping its own Bellman equation."""
    Vp = [0.0] * 16
    for _ in range(2000):
        nxt = list(Vp)
        for s in inner:
            nxt[s] = sum(p * (arrive(ns) + GAMMA * Vp[ns]) for ns, p in outcomes(s, policy[s]))
        if max(abs(nxt[s] - Vp[s]) for s in inner) < 1e-12:
            return nxt
        Vp = nxt
    return Vp

print("visits per square, seed 0:")
for r in range(4):
    print(" ".join(f"{visits[r * 4 + c]:6d}" for c in range(4)))

scores = []
for seed in range(20):
    Qs, _, _ = q_learn(seed, 5000)
    pol = {s: max(range(4), key=lambda a: Qs[s][a]) for s in inner}
    scores.append(true_value(pol)[0])
print(f"optimal start value {V[0]:.4f}")
print(f"20 seeds: {sum(1 for v in scores if abs(v - V[0]) < 1e-9)} reached it exactly, "
      f"worst {min(scores):.4f}, mean {sum(scores) / 20:.4f}")
for s in (8,):
    qs = [sum(p * (arrive(ns) + GAMMA * V[ns]) for ns, p in outcomes(s, a)) for a in range(4)]
    print("true action values on square 8:", " ".join(f"{ARROWS[a]}{qs[a]:+.3f}" for a in range(4)))
# visits per square, seed 0:
#   8861   2430    716    264
#   8743      0    747      0
#   7300   4883   4275   1212
#   4148   4364   5939      0
# optimal start value 0.4815
# 20 seeds: 9 reached it exactly, worst 0.4670, mean 0.4751
# true action values on square 8: ^+0.534 >+0.666 v+0.656 <+0.591

The start square was visited 8,861 times and the square in the top-right corner 264 times, a factor of 34, and the two disagreements are in the thin part of that map. This is the third property of reinforcement learning made visible: the agent's own policy decides where its data comes from, so it learns the squares it walks through and stays vague about the ones it avoids. It avoids them because they are bad, which is usually fine and occasionally the reason it never finds something better.

The second disagreement is a different thing entirely, and it is why you should measure policies rather than compare them square by square. On square 8 the exact values of going right and going down are 0.666 and 0.656 — a gap of 0.01 that no finite amount of sampling will reliably resolve, and which costs almost nothing to get wrong. Across 20 seeds, 9 recovered the optimal policy exactly and the worst was worth 0.4670 against the optimum of 0.4815, a loss of 3 per cent. So more than half the seeds produce a policy that is technically wrong and practically fine. Reporting the fraction of exactly-correct seeds would have made the algorithm look far worse than it is.

That bug is worth running rather than believing, because it has a condition attached that nobody mentions. The q_learn above takes a mask_terminal flag; turn it off and the target bootstraps from the terminal square's row of the table, which should be nonsense. Whether it is depends on what that row was initialised to.

for init in (0.0, 1.0):
    for mask in (True, False):
        vals = []
        for seed in range(10):
            Qs, _, _ = q_learn(seed, 3000, init=init, mask_terminal=mask)
            vals.append(Qs[3][2])                  # square (0,3), action down, into the hole
        print(f"init {init}, mask_terminal={mask}: Q(into the hole) = {sum(vals) / 10:+.3f}")
# init 0.0, mask_terminal=True: Q(into the hole) = -0.817
# init 0.0, mask_terminal=False: Q(into the hole) = -0.817
# init 1.0, mask_terminal=True: Q(into the hole) = -0.747
# init 1.0, mask_terminal=False: Q(into the hole) = +0.173

With zeros everywhere the missing mask adds gamma times zero, so the two columns agree to three decimal places and the bug hides completely — which is how it survives review and reaches the run where it matters. Initialise optimistically at 1.0, a standard trick for encouraging exploration, and stepping into a hole is valued at +0.173 instead of -0.747: a -1 reward followed by 0.95 times an imaginary future. The general lesson is the one to carry: a bug whose effect is multiplied by an initialisation is a bug that only appears when something else changes.

The same agent against a standard environment#

Once it works on a grid you wrote, the identical algorithm runs against the environments papers use. Gymnasium's FrozenLake is the same shape of problem, and the only real differences are that the environment owns the state and that reset and step return tuples rather than plain values. This needs gymnasium installed; it is not part of the standard library.

import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1", is_slippery=False)       # 16 states, 4 actions
Q = np.zeros((env.observation_space.n, env.action_space.n))
alpha, gamma, eps = 0.1, 0.99, 1.0

for episode in range(5000):
    s, _ = env.reset()
    done = False
    while not done:
        a = env.action_space.sample() if np.random.rand() < eps else int(Q[s].argmax())
        s_next, r, terminated, truncated, _ = env.step(a)
        target = r + gamma * Q[s_next].max() * (not terminated)
        Q[s, a] += alpha * (target - Q[s, a])
        s, done = s_next, terminated or truncated
    eps = max(0.05, eps * 0.999)                         # explore less over time

print(Q.argmax(axis=1).reshape(4, 4))                    # the learned policy

When the table is too big: DQN#

For images or large state spaces, a table is impossible, so a neural network predicts Q values from the state. Training it naively diverges. The DQN work that learned Atari games from pixels made it stable with two changes.

• Experience replay: store transitions in a buffer and train on random samples from it, which breaks the strong correlation between consecutive steps.
• A target network: compute targets with a copy of the network that is updated only occasionally, so the thing you are chasing does not move with every step.

Both fixes address the same thing, which is that the table version had a property the network version quietly loses. Updating one cell of a table changes one cell. Updating a network changes its prediction everywhere, including at the state whose value you are using as the target, so the target moves as you chase it. Add to that a max over noisy estimates, which is biased upwards because the largest of several noisy numbers tends to be one that was overestimated — the overestimation that double DQN exists to correct — and the naive version diverges rather than merely learning slowly.

What to take from this section and what to leave. The update rule, the meaning of each term, the off-policy property and the two DQN fixes are standard interview ground and worth knowing cold. The rest of the value-method literature — duelling architectures, prioritised replay, distributional value estimates, Rainbow's combination of all of them — is a body of work aimed at Atari scores, and reading it will not help you unless you are doing exactly that. The habits transfer better than the algorithms: compute the exact answer on a small case, count your visits, judge a policy by its measured value rather than by matching a reference policy square by square.

The previous section learned what actions are worth and then acted greedily on that. This section learns the behaviour itself: make the actions that preceded a good outcome more likely and the others less. The idea works and is extremely noisy, so most of the section is about what gets added to make it usable, namely a baseline, a second network that predicts what to expect, and a limit on how far a single update may move the policy. That last one is PPO, which is what language model post-training is built on.

Skip the values, learn the behaviour#

A policy network outputs probabilities over actions. After an episode, make the actions that led to high return more likely and the others less likely. That is the whole idea. The maths makes it precise: the gradient of expected return is the average of the gradient of log probability of each action, weighted by the return that followed it.

It is worth seeing why that weighting is the right one rather than a plausible one. You cannot differentiate the reward with respect to the policy's parameters, because the environment is not differentiable and nobody gave you its equations. What you can differentiate is the probability of the action you took. Raising the log probability of an action by one unit multiplies how often that action happens; weighting that push by the return that followed means good episodes push their own actions up hard and bad episodes push theirs down. Average over enough episodes and the pushes that were luck cancel, while the ones that were the policy survive. Enough episodes is the entire problem, and the rest of this section is about reducing how many are needed.

An environment you can write down#

Cart-pole is the standard first problem: a pole hinged on a cart, two actions, push left or push right, one point per time step the pole stays within twelve degrees of upright and the cart within 2.4 units of the centre. It is four lines of physics and worth writing out, because an environment you wrote is an environment you can instrument.

import math, torch, torch.nn as nn

GRAV, M_CART, M_POLE, HALF_LEN, FORCE, DT = 9.8, 1.0, 0.1, 0.5, 10.0, 0.02
TOTAL_MASS, POLE_ML = M_CART + M_POLE, M_POLE * HALF_LEN

def cart_step(state, action):
    """The standard cart-pole equations. State is (x, x_dot, angle, angle_dot)."""
    x, x_dot, th, th_dot = state.tolist()
    force = FORCE if action == 1 else -FORCE
    cos, sin = math.cos(th), math.sin(th)
    temp = (force + POLE_ML * th_dot ** 2 * sin) / TOTAL_MASS
    th_acc = (GRAV * sin - cos * temp) / (HALF_LEN * (4 / 3 - M_POLE * cos ** 2 / TOTAL_MASS))
    x_acc = temp - POLE_ML * th_acc * cos / TOTAL_MASS
    nxt = torch.tensor([x + DT * x_dot, x_dot + DT * x_acc,
                        th + DT * th_dot, th_dot + DT * th_acc], dtype=torch.float32)
    fallen = abs(nxt[0].item()) > 2.4 or abs(nxt[2].item()) > 12 * math.pi / 180
    return nxt, 1.0, fallen                       # one point per step survived

def run_episode(policy, rng, cap=500):
    state = torch.rand(4, generator=rng) * 0.1 - 0.05
    log_probs, rewards = [], []
    for t in range(cap):
        dist = torch.distributions.Categorical(logits=policy(state))
        a = dist.sample()
        log_probs.append(dist.log_prob(a))
        state, r, fallen = cart_step(state, a.item())
        rewards.append(r)
        if fallen:
            break
    return log_probs, rewards

def rewards_to_go(rewards, gamma=0.99):
    out, G = [], 0.0
    for r in reversed(rewards):
        G = r + gamma * G
        out.insert(0, G)
    return torch.tensor(out)

Note what the reward-to-go function does. Each action is credited with the rewards that came after it, not with the whole episode's total, because an action cannot have caused a reward that arrived before it. That is free variance reduction and it is the only change from the naive formula that requires no justification beyond causality.

REINFORCE#

def train(seed, baseline, episodes=400, lr=1e-2):
    torch.manual_seed(seed)
    rng = torch.Generator().manual_seed(seed)
    policy = nn.Sequential(nn.Linear(4, 32), nn.Tanh(), nn.Linear(32, 2))
    opt = torch.optim.Adam(policy.parameters(), lr=lr)
    lengths = []
    for ep in range(episodes):
        log_probs, rewards = run_episode(policy, rng)
        lengths.append(len(rewards))
        G = rewards_to_go(rewards)
        weights = (G - G.mean()) / (G.std() + 1e-8) if baseline else G
        loss = -(torch.stack(log_probs) * weights).sum()
        opt.zero_grad(); loss.backward(); opt.step()
    return lengths

for baseline in (False, True):
    for seed in (0, 1, 2):
        lengths = train(seed, baseline)
        print(f"baseline={baseline!s:5s} seed {seed}: "
              f"first 50 episodes {sum(lengths[:50]) / 50:6.1f} steps, "
              f"last 50 {sum(lengths[-50:]) / 50:6.1f}, best {max(lengths)}")
# baseline=False seed 0: first 50 episodes   36.8 steps, last 50  293.6, best 500
# baseline=False seed 1: first 50 episodes   12.5 steps, last 50  500.0, best 500
# baseline=False seed 2: first 50 episodes   39.2 steps, last 50   14.1, best 500
# baseline=True  seed 0: first 50 episodes   82.5 steps, last 50  376.3, best 500
# baseline=True  seed 1: first 50 episodes   36.8 steps, last 50  500.0, best 500
# baseline=True  seed 2: first 50 episodes   33.7 steps, last 50  324.2, best 500

The third row is the one to sit with. Same code, same hyperparameters, seed 2, and the policy ends at 14 steps per episode having at some point reached the 500-step cap. It did not fail to learn; it learned and then destroyed what it had. A large update after a run of lucky episodes moved the policy somewhere that collects worse episodes, which produce worse updates. Nothing in the loss function notices, because there is no held-out set and no ground truth, only the agent's own increasingly bad data. If you had run one seed and it had been this one, the honest conclusion would have been that the code is broken.

Variance, and why the baseline matters#

Returns vary enormously from episode to episode by luck, so raw REINFORCE gradients are very noisy. Subtracting a baseline, a typical return for that situation, keeps the gradient unbiased but far less noisy: actions are judged by whether they did better than usual, not by the raw total.

That claim is testable, and testing it turns up something the tutorials do not say. Take a half-trained policy, sample 200 episodes, and compute the gradient four ways: weighted by the raw reward-to-go, minus a constant baseline measured from other episodes, minus the mean of the episode's own reward-to-go, and the standardised version the training loop above uses. Then compare not just the variance but the variance against the signal — a weighting that divides everything by 60 reduces variance by 3,600 and has told you nothing.

torch.manual_seed(0)
rng = torch.Generator().manual_seed(0)
policy = nn.Sequential(nn.Linear(4, 32), nn.Tanh(), nn.Linear(32, 2))
opt = torch.optim.Adam(policy.parameters(), lr=1e-2)
for ep in range(150):                                    # a half-trained policy to measure at
    lp, rw = run_episode(policy, rng)
    G = rewards_to_go(rw)
    loss = -(torch.stack(lp) * ((G - G.mean()) / (G.std() + 1e-8))).sum()
    opt.zero_grad(); loss.backward(); opt.step()

probe = [rewards_to_go(run_episode(policy, rng)[1]).mean().item() for _ in range(50)]
b = sum(probe) / len(probe)                              # a state-independent baseline

def gradient(log_probs, weights):
    loss = -(torch.stack(log_probs) * weights).sum()
    opt.zero_grad(); loss.backward(retain_graph=True)
    return torch.cat([p.grad.flatten().clone() for p in policy.parameters()])

rows = {"raw reward-to-go": [], "minus a constant": [], "minus episode mean": [], "standardised": []}
for k in range(200):
    lp, rw = run_episode(policy, rng)
    G = rewards_to_go(rw)
    rows["raw reward-to-go"].append(gradient(lp, G))
    rows["minus a constant"].append(gradient(lp, G - b))
    rows["minus episode mean"].append(gradient(lp, G - G.mean()))
    rows["standardised"].append(gradient(lp, (G - G.mean()) / (G.std() + 1e-8)))

print(f"baseline b = {b:.1f}, measured over 200 episodes")
for name, grads in rows.items():
    stack = torch.stack(grads)
    var = stack.var(0).sum().item()                      # total variance of the estimator
    signal = stack.mean(0).norm().item()                 # the direction it agrees on
    print(f"  {name:20s} variance {var:11.1f}   mean gradient {signal:8.3f}   "
          f"ratio {signal / var ** 0.5:.3f}")
# baseline b = 66.4, measured over 200 episodes
#   raw reward-to-go     variance   4397940.5   mean gradient  299.672   ratio 0.143
#   minus a constant     variance   1080077.6   mean gradient  230.449   ratio 0.222
#   minus episode mean   variance   1043069.0   mean gradient  142.781   ratio 0.140
#   standardised         variance      1666.7   mean gradient    6.059   ratio 0.148

The constant baseline does what the textbook says. Variance falls fourfold and the ratio rises from 0.143 to 0.222, which is a real improvement: over half again as much usable signal per episode, for the cost of tracking one number. Nothing about it is subtle.

The other two rows are the controls, and they kill a claim people make constantly. Subtracting the episode's own mean drops the variance by the same fourfold and the ratio comes out at 0.140, which is no better than doing nothing at all — it removed as much signal as noise. Standardising drops the variance by a factor of 2,600, which looks spectacular and is entirely a change of scale: the mean gradient shrinks by the same factor and the ratio finishes at 0.148. What standardising buys in the training loop above is a step size that does not depend on how long episodes have become, which matters a great deal to Adam and is not variance reduction. Report a variance number without its signal and you can prove anything.

Actor-critic#

Make the baseline smart: train a second network, the critic, to predict the expected return from each state. The difference between what happened and what the critic expected is the advantage. The actor is pushed towards actions with positive advantage.

A critic is a per-state baseline and it is legal, because it is a function of the state alone and never of the action taken. That is what makes it the right answer where the constant above is a workable one: the constant says whether this episode beat the average episode, while the critic says whether this action beat what was expected from this position, which is a far sharper question when some states are simply better than others. The price is a second network with its own loss, its own learning rate and its own way of being wrong, and a critic that lags the policy injects a bias of its own. Generalised advantage estimation, the lambda you see in every PPO configuration, is a dial between trusting the critic and trusting the observed rewards.

PPO: do not move too far#

ratio = pi_new(a | s) / pi_old(a | s)       how much more likely the action became

L = mean( min( ratio * A,  clip(ratio, 1 - eps, 1 + eps) * A ) )      eps around 0.2

PPO reuses each batch of experience for several updates, which is efficient but dangerous: the policy can drift far from the one that collected the data. The clip removes any incentive to push the probability ratio beyond a small band. Taking the minimum means the objective never rewards going further. It is crude and very robust, which is why it became the default.

The objective is four lines of arithmetic, and printing its slope is more convincing than any description of it. Slope here means how much the objective changes as the probability ratio changes, which is the only thing an optimiser responds to.

EPS = 0.2

def ppo_term(ratio, adv):
    return min(ratio * adv, min(max(ratio, 1 - EPS), 1 + EPS) * adv)

print("ratio    advantage +1            advantage -1")
print("         plain    ppo   slope    plain    ppo   slope")
for ratio in (0.6, 0.9, 1.0, 1.1, 1.4, 2.0):
    cells = ""
    for adv in (1.0, -1.0):
        slope = (ppo_term(ratio + 1e-4, adv) - ppo_term(ratio - 1e-4, adv)) / 2e-4
        cells += f"  {ratio * adv:+6.2f} {ppo_term(ratio, adv):+6.2f}  {slope:+5.2f} "
    print(f"{ratio:5.2f} {cells}")
# ratio    advantage +1            advantage -1
#          plain    ppo   slope    plain    ppo   slope
#  0.60    +0.60  +0.60  +1.00    -0.60  -0.80  +0.00
#  0.90    +0.90  +0.90  +1.00    -0.90  -0.90  -1.00
#  1.00    +1.00  +1.00  +1.00    -1.00  -1.00  -1.00
#  1.10    +1.10  +1.10  +1.00    -1.10  -1.10  -1.00
#  1.40    +1.40  +1.20  +0.00    -1.40  -1.40  -1.00
#  2.00    +2.00  +1.20  +0.00    -2.00  -2.00  -1.00

Read the slope columns and the design is obvious. For a good action, advantage +1, the gradient is a constant +1 until the action has become 1.2 times as likely as it was, and then it is exactly zero: no matter how good the action looked, this batch will not push it further. For a bad action, advantage -1, the gradient keeps pushing the probability down until the action is 0.8 times as likely, and then stops. The plain columns show what would happen without the clip — an objective that grows without limit in both directions, which is precisely the incentive to take one enormous step off the data you have.

Notice that the clip is one-sided in each case. With a positive advantage the objective is still free to move downwards, and with a negative advantage still free to move up: the min never blocks the direction that undoes an overshoot. That asymmetry is the whole trick, and it is why PPO is safe to run for several epochs over one batch of experience while plain policy gradient is not.

Where this lands for an AI engineer: PPO is the algorithm underneath RLHF, and the clip is the reason a preference-training run does not usually destroy the model outright. Two further guards appear there, both covered in the section on language models in this topic — a KL penalty against the starting model, which is a different constraint from the clip and does a different job, and the option of skipping the sampling loop entirely with DPO. Implementing PPO from scratch is not a good use of your time; being able to say what the ratio, the advantage, the clip and the min each do, and why removing any of them breaks something specific, is.

What to skip: trust region derivations, the natural gradient, and the conjugate-gradient machinery in TRPO. They are the reason PPO has the shape it has, and knowing that PPO is a cheap approximation of a trust region is the entire useful content. Read a clean implementation instead — CleanRL's single-file version is a few hundred lines — and check each term against the table above.

A language model producing a response is a policy taking actions, and once you see it that way the algorithms from the previous sections apply directly. This section maps the pieces across and then covers the three ways it is done in practice: a reward model learned from human comparisons, a method that skips the reward model and trains on the comparisons directly, and rewards that can simply be checked, which is what drove the recent progress in reasoning models. It also covers how each one fails, which in every case is the model optimising the reward it was given rather than the thing you meant.

Mapping the pieces#

state    the prompt plus the text generated so far
action   the next token
policy   the language model
episode  one full response
reward   a score for the finished response

Two things follow from that mapping and both are inconvenient. The action space is the vocabulary, so a hundred thousand actions at every step rather than the two in cart-pole, which rules out anything that takes a max over actions and leaves policy methods. And the reward arrives once, at the end of a response that may be a thousand tokens long, so a single number has to be shared out among a thousand decisions. Sparse, delayed, enormous action space: this is the hard corner of the field, which is why the machinery is all about controlling variance and limiting how far the policy may move.

A reward model from comparisons#

People find it easier to say which of two answers is better than to score one. Collect many such comparisons, then train a reward model to give the preferred answer a higher score. The standard loss pushes the score difference up for the chosen answer.

import torch.nn.functional as F

def reward_model_loss(r_chosen, r_rejected):
    return -F.logsigmoid(r_chosen - r_rejected).mean()

The loss is uncontroversial. What it learns from is not. Raters are people with habits, and any habit that correlates with their choices becomes part of the reward — length being the best documented one. The rest of this section is one such reward model, fitted to synthetic comparisons, and then followed all the way to the damage it does. Answers here are two numbers: whether they are correct, and how long they are. Raters pick the correct one when correctness differs, and otherwise prefer the longer answer three times in four.

import numpy as np
rng = np.random.default_rng(0)

def sample_answer():
    """An answer is (is it correct, how many tokens long)."""
    return int(rng.integers(0, 2)), int(rng.integers(20, 200))

pairs = []
for _ in range(4000):
    a, b = sample_answer(), sample_answer()
    if a[0] != b[0]:
        chosen, rejected = (a, b) if a[0] > b[0] else (b, a)      # raters spot correctness
    else:
        longer, shorter = (a, b) if a[1] > b[1] else (b, a)       # otherwise the longer one
        chosen, rejected = (longer, shorter) if rng.random() < 0.75 else (shorter, longer)
    pairs.append((chosen, rejected))

def features(answer):
    return np.array([answer[0], answer[1] / 100.0])

diff = np.stack([features(c) - features(r) for c, r in pairs])
w = np.zeros(2)
for it in range(3000):                                            # the Bradley-Terry loss
    w -= 1.0 * (diff * (-1 / (1 + np.exp(diff @ w)))[:, None]).mean(0)
loss = np.log1p(np.exp(-diff @ w)).mean()
print(f"reward weights: correct {w[0]:+.3f}   per 100 tokens {w[1]:+.3f}")
print(f"loss {loss:.4f}, agrees with {100 * (diff @ w > 0).mean():.1f}% of the comparisons")

def reward(answer):
    return float(features(answer) @ w)
# reward weights: correct +7.722   per 100 tokens +1.245
# loss 0.3033, agrees with 86.9% of the comparisons

The model is not broken. It learned that correctness is worth far more than length, exactly as the raters behaved, and it agrees with them 86.9 per cent of the time. But it did pick up 1.245 points per hundred tokens, and a reward model is not used to predict preferences. It is used as an objective, and an objective is pushed on.

RLHF#

1. 1.Supervised fine-tuning on good example responses gives a starting policy.
2. 2.Train a reward model on human comparisons.
3. 3.Optimise the policy with PPO to maximise reward, minus a penalty for drifting far from the starting model, measured by KL divergence.

The KL penalty is essential. Without it, the policy finds text that the reward model scores highly but that is not actually good, because the reward model is only accurate near the kind of text it was trained on.

That trade has a closed form, which means it can be examined without training anything. The policy that maximises reward minus beta times the KL from the starting model is the starting model reweighted by the exponential of reward over beta. Beta is the dial: large means stay close, small means chase the reward. Here it is over six candidate responses, using the reward model fitted above, against a column for what a reader actually gets — a correct answer, with padding counted against it.

answers = [(1, 30), (1, 60), (1, 120), (1, 400), (0, 190), (0, 60)]
names = ["correct 30", "correct 60", "correct 120", "correct 400", "wrong 190", "wrong 60"]
r = np.array([reward(a) for a in answers])
p_ref = np.array([0.25, 0.22, 0.13, 0.05, 0.15, 0.20])            # the model before any RL
utility = np.array([a[0] - 0.4 * a[1] / 100 for a in answers])    # what a reader actually gets

print("answer         reward   what the reader gets")
for n, ri, ui in zip(names, r, utility):
    print(f"{n:14s} {ri:+7.3f} {ui:+15.3f}")

print("  beta     KL   mean reward   reader utility   most likely answer")
for beta in (100.0, 10.0, 2.0, 1.0, 0.5, 0.25):
    p = p_ref * np.exp(r / beta)
    p /= p.sum()
    kl = float((p * np.log(p / p_ref)).sum())
    print(f"{beta:6.2f}  {kl:5.3f}      {float(p @ r):+7.3f}          "
          f"{float(p @ utility):+7.3f}   {names[int(p.argmax())]}")
# answer         reward   what the reader gets
# correct 30      +8.095          +0.880
# correct 60      +8.469          +0.760
# correct 120     +9.215          +0.520
# correct 400    +12.700          -0.600
# wrong 190       +2.365          -0.760
# wrong 60        +0.747          -0.240
#   beta     KL   mean reward   reader utility   most likely answer
# 100.00  0.001       +6.358           +0.277   correct 30
#  10.00  0.059       +7.443           +0.378   correct 30
#   2.00  0.795      +10.141           +0.185   correct 400
#   1.00  2.165      +12.047           -0.390   correct 400
#   0.50  2.962      +12.685           -0.595   correct 400
#   0.25  2.996      +12.700           -0.600   correct 400

Reward climbs the whole way down the table, from +6.36 to +12.70, and it never once goes backwards. The thing you wanted rises from +0.277 to +0.378 and then collapses to -0.600. The peak sits at a KL of 0.059, which is almost no movement at all, and by a KL of 2.2 the model is confidently producing four-hundred-token answers that are correct and that nobody wants to read. Every number on the dashboard would have looked excellent throughout.

This is Goodhart's law with the axes labelled, and it is the single most important picture in preference training. It also explains the practices that otherwise look superstitious: KL is monitored during RLHF runs as a first-class metric rather than a regulariser detail, checkpoints are selected on held-out evaluations the reward model never influenced, and beta is tuned on the shape of that curve rather than set by theory. The reward model is a local approximation to human judgement, valid near the text it was trained on. The KL term is the statement of how far you trust it.

DPO: skip the reward model#

Direct Preference Optimisation shows that the same objective can be optimised directly on preference pairs with a simple classification-style loss, without training a separate reward model or sampling during training. It is much simpler and more stable to run, which is why it spread quickly. The trade-off is that it learns only from the fixed pairs you have, not from fresh samples of the current model.

The claim that it reaches the same place is checkable on the candidates above. Generate preferences from a reward the algorithm never sees, run the DPO loss on nothing but those win-lose pairs, and compare the resulting distribution with the closed form from the previous block. The policy here is six logits rather than a language model, which is the smallest thing that can be called a policy and is enough to test the identity.

import torch
r_true = torch.tensor(r / 4, dtype=torch.float32)         # scaled so raters disagree sometimes
p_ref_t = torch.tensor(p_ref, dtype=torch.float32)
BETA = 1.0

p_star = p_ref_t * torch.exp(r_true / BETA)
p_star = p_star / p_star.sum()                            # the RLHF optimum, in closed form

g = torch.Generator().manual_seed(0)
i = torch.randint(0, 6, (40000,), generator=g)
j = torch.randint(0, 6, (40000,), generator=g)
i, j = i[i != j], j[i != j]
i_wins = torch.rand(len(i), generator=g) < torch.sigmoid(r_true[i] - r_true[j])
chosen, rejected = torch.where(i_wins, i, j), torch.where(i_wins, j, i)

logits = torch.zeros(6, requires_grad=True)
opt = torch.optim.Adam([logits], lr=0.05)
log_ref = torch.log(p_ref_t)
for step in range(3000):
    log_pi = torch.log_softmax(logits, 0)
    margin = BETA * ((log_pi[chosen] - log_ref[chosen]) - (log_pi[rejected] - log_ref[rejected]))
    loss = -torch.nn.functional.logsigmoid(margin).mean()
    opt.zero_grad(); loss.backward(); opt.step()
p_dpo = torch.softmax(logits, 0).detach()

print(f"DPO loss {loss.item():.4f}")
print("answer          before    DPO   closed form")
for k in range(6):
    print(f"{names[k]:14s} {p_ref[k]:6.3f} {p_dpo[k]:6.3f} {p_star[k]:12.3f}")
print(f"largest disagreement between DPO and the closed form: "
      f"{float((p_dpo - p_star).abs().max()):.4f}")
# DPO loss 0.4994
# answer          before    DPO   closed form
# correct 30      0.250  0.271        0.281
# correct 60      0.220  0.276        0.272
# correct 120     0.130  0.199        0.193
# correct 400     0.050  0.175        0.178
# wrong 190       0.150  0.040        0.040
# wrong 60        0.200  0.038        0.036
# largest disagreement between DPO and the closed form: 0.0102

Read the margin line and the equivalence stops being mysterious. The quantity being pushed up is the log ratio of the new policy to the reference, scaled by beta, which is precisely the implicit reward that the closed form inverts. DPO is not an approximation of RLHF; it is the same optimum reached by fitting the preference model directly to the policy. The wrong answers fall from 0.15 and 0.20 to 0.04, the four-hundred-token answer rises from 0.05 to 0.175, and yes, the length preference is faithfully reproduced — a simpler algorithm inherits the same rater habits, because they were in the data, not in the optimiser.

What DPO gives up is on-policy sampling. RLHF scores the model's current outputs, so the reward model gets asked about text the model actually produces now; DPO only ever sees the pairs you collected, and the further the policy moves from whatever generated them, the less those pairs say about it. Hence the online variants, and hence the fact that neither has fully displaced the other.

Verifiable rewards#

For maths with known answers or code with tests, no human or reward model is needed: check the answer. Training with RL on these checks, sampling several attempts per problem and reinforcing the ones that succeed, has driven much of the recent progress in reasoning models. Methods such as GRPO compare each attempt with the others in its group instead of training a separate critic.

Group-relative is simpler than it sounds, and it is worth seeing that the critic — a whole second network, with its own instability — is replaced by one line of arithmetic. Sample several answers to the same problem, check each, and standardise the scores within the group. An attempt that succeeded where most failed gets a large positive advantage; the same success when everything succeeded gets nothing, because there is nothing to learn from a problem the model has already mastered.

group = np.array([1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0])        # eight attempts, three correct
adv = (group - group.mean()) / (group.std() + 1e-8)
print("rewards  ", group)
print("advantage", np.round(adv, 3))
print("mean advantage", round(float(adv.mean()), 6), "- no critic network anywhere")
# rewards   [1. 0. 0. 1. 0. 0. 1. 0.]
# advantage [ 1.291 -0.775 -0.775  1.291 -0.775 -0.775  1.291 -0.775]
# mean advantage 0.0 - no critic network anywhere

Two consequences fall out of that line. A problem the model always gets right, or always gets wrong, produces a group with zero standard deviation and therefore no gradient, so the curriculum selects itself towards problems at the edge of the model's ability — which is why these runs are bottlenecked on having problems of the right difficulty. And the reward is the output of a checker, so the usual worry moves from the reward model to the checker: a test suite that can be satisfied by special-casing its inputs will be, and a maths grader that accepts a final answer without a derivation will reward guessing.

Reward hacking, concretely#

• A reward model that slightly prefers longer answers produces a policy that pads everything.
• A code reward that only checks that tests pass can be satisfied by editing the tests or special-casing their inputs.
• A preference model trained on raters who like agreement produces a model that tells people what they want to hear.

Each is the optimiser doing exactly what it was told. The defences are better rewards, penalties for drift, held-out evaluation that the reward never saw, and reading samples.

The first of those in the list is the one the experiment above puts numbers on. Length is not a hypothetical: the fitted model paid 1.245 per hundred tokens, which is a sixth of what it paid for being correct, and that was enough to make a four-hundred-token answer the most likely output at any beta below 2. Length-controlled evaluation exists because of exactly this, and a padded answer is the mildest version. The same mechanism produces confident phrasing on uncertain claims, agreement with a user who has stated a wrong opinion, and answers formatted to look thorough, all of which raters reward and none of which anybody asked for.

The practical checklist is short. Track KL from the starting model during the run and treat a rising KL with a flat evaluation score as over-optimisation in progress. Keep an evaluation set that has never touched reward model training. Measure response length before and after, since it is the cheapest detector of the most common hack. And read a few dozen samples yourself at each checkpoint, because the failure modes that matter are usually visible in one paragraph and invisible in any aggregate.