Reinforcement learning algorithms are usually taught as a list. But each one exists because the previous one had a specific, painful problem — and someone found a specific fix. This is that chain, told end to end, with the math kept sparse and every idea drawn or made interactive.
Every algorithm in this story is chasing the same objective. The first honest attempt at it works — and is almost unusable.
Every algorithm in this series is trying to do exactly one thing: find a policy — a strategy for choosing actions — that collects as much reward as possible over time.
We write the policy as \(\pi_\theta(a\mid s)\): given a state \(s\), it gives the probability of taking action \(a\). The loop it lives in is the most famous diagram in RL:
The thing we want to maximize is the expected return — total reward, with future rewards discounted so that reward now counts a bit more than reward later:
$$J(\theta)\;=\;\mathbb{E}\big[\,r_0+\gamma r_1+\gamma^2 r_2+\cdots\big]$$
Here \(\theta\) is the parameters of our policy (the weights of a neural network) and \(\gamma\) is the discount factor — some number like 0.99. It's worth feeling what \(\gamma\) does, because it's the knob that defines how far-sighted your agent is:
That's it. That's the whole objective, and it never changes for the rest of this series. Everything that follows — REINFORCE, actor-critic, TRPO, PPO — is a series of increasingly clever answers to one question: how do we compute a gradient of this thing and follow it without blowing up?
The most direct idea possible: run the policy, watch what happens, and make good outcomes more likely.
Concretely: play out a full episode, add up the total reward \(R\), then nudge the network to increase the probability of every action you took, scaled by \(R\). Good episode? All its actions get reinforced. Bad one? Suppressed.
$$\nabla_\theta J\;\approx\;\sum_t \nabla_\theta \log \pi_\theta(a_t\mid s_t)\cdot R$$
That's REINFORCE (Williams, 1992). It's beautiful because it's legitimate — this really is an unbiased estimate of the true gradient of \(J\). Sample enough episodes and, on average, you're pointing in the right direction.
The problem: the variance is horrendous. "On average correct" hides how wild each individual estimate is:
Two things make it this noisy in practice:
1. Credit is assigned collectively. If the episode scored well, every action gets praised — including the terrible ones that happened to occur in a good episode. The signal for "which specific action was good" is buried under the noise of "how the whole episode went."
2. The scale of \(R\) is arbitrary. Suppose every episode in your game scores between +90 and +100. Then even your worst episodes get a big positive \(R\), and every action ever taken gets pushed up. The gradient spends most of its energy encoding "rewards here are large" rather than "this action was better than that one."
REINFORCE works — it just needs an enormous number of episodes to average the noise away. So the next step in the story isn't a new algorithm at all. It's a fix to this one.
The gradient is honest but drowning in noise, and a +95 episode looks "good" even when it was our worst. We need a way to ask a sharper question than "was this episode good?"
A one-line change that keeps the gradient honest, kills most of the noise — and quietly invents the most important quantity in RL.
Here's the fix, and it's almost suspiciously simple. You can subtract any fixed reference value \(b\) from the return —
$$\nabla_\theta J\;\approx\;\sum_t \nabla_\theta \log \pi_\theta(a_t\mid s_t)\cdot (R-b)$$
— and the expected gradient doesn't change at all. On average you still point in exactly the right direction. But the variance of the estimate can drop dramatically if you pick \(b\) well.
Intuition: instead of asking "was this episode good?", you're now asking "was this episode better than usual?" Watch what happens to the learning signal in that 90–100 game as you raise the baseline:
The useless "everything is positive" component of the gradient is gone. What remains is pure comparison — and comparisons are exactly what a policy needs in order to choose.
So what's the best value for \(b\)? Not one global constant — the natural choice is "how well I usually do from this state." That quantity has a name: the value function,
$$V(s)\;=\;\text{expected return, starting from } s \text{ and following the current policy.}$$
And the gap between what happened and what usually happens also has a name — the advantage:
$$A(s,a)\;=\;\underbrace{\text{return after taking } a}_{\text{what happened}}\;-\;\underbrace{V(s)}_{\text{what usually happens}}$$
It answers: how much better was this particular action than my typical outcome from here? Positive advantage → do it more. Negative → do it less. Its magnitude even tells you how strongly to feel about it.
This reframing is the pivot point of the entire field:
Stop reinforcing actions for being in good episodes. Reinforce actions for being better than expected.
Every algorithm from here to the end of the series — actor-critic, TRPO, PPO, GRPO — keeps this exact idea and only changes how the advantage is estimated or how big a step to take on it.
One problem, though. \(V(s)\) isn't given to us. To subtract "what usually happens from this state," we'd have to know what usually happens from every state — and no one is going to hand us that function.
The perfect baseline is the value function V(s) — a function nobody gives us. If we need it and can't look it up… could we learn it?
If nobody will hand you the value function, train a second network to predict it. Then discover the trap that motivates everything after.
If we need \(V(s)\) and can't look it up… train a second network to predict it. Now there are two networks in the loop:
The actor is the policy \(\pi_\theta(a\mid s)\). It chooses actions. It's trained with the policy gradient from Part 2, weighted by the advantage.
The critic is the value network \(V_\phi(s)\). It predicts expected return, and it's trained by plain regression: predict the returns you actually observe. The critic never picks an action. Its entire job is to make the actor's learning signal cleaner — it supplies the baseline that turns raw returns into advantages.
The critic buys you a second superpower. With REINFORCE you had to wait for an episode to finish before you could compute \(R\). With a critic, you can estimate the future without living it: after a single step,
$$r \;+\; \gamma\, V(s')$$
— "the reward I just got, plus the critic's estimate of everything after" — is already an estimate of the full return. This is called bootstrapping, and it means you can update mid-episode, from short snippets of experience. This family is the A2C / A3C style of algorithm.
Bootstrapping introduces a choice. How many real rewards do you collect before handing off to the critic's estimate? Use many, and your advantage estimates are accurate but noisy (real life is noisy). Hand off after one step, and they're smooth but only as good as the critic — which, early in training, is wrong.
GAE (Generalized Advantage Estimation) refuses to choose: it blends all the hand-off lengths together, weighted by one knob, \(\lambda\). You don't need its formula — you need its feel:
So: variance tamed, updates possible mid-episode, one tidy knob. Are we done?
One bad update can destroy everything. Here's why. Policy gradient methods are on-policy: the data you learn from is generated by the current policy itself. Now imagine the learning rate is a touch too high, or one batch is unlucky, and an update makes the policy noticeably worse.
A worse policy now collects worse data. Worse data produces worse gradient estimates and a worse critic. Which produce a worse policy. Unlike supervised learning — where a bad step just means the next step starts from a slightly worse spot on a fixed dataset — here a bad step poisons your future data. Training doesn't dip. It collapses, and often never recovers.
The obvious fix — "use a tiny learning rate" — doesn't really work, because the right step size varies wildly across states and stages of training. What we actually want is a principled answer to a sharper question.
On-policy learning eats its own cooking: one oversized update ruins the policy, which ruins the data, which ruins everything after. How big a step is safe?
Measure step size where it matters — in behavior, not weights — and never leave the bubble where your estimates can be trusted.
Before the fix, watch the failure. A toy on-policy training run — nudge the step size up and re-run a few times:
TRPO's (Trust Region Policy Optimization, 2015) key insight is diagnostic before it is algorithmic: "learning rate" limits the wrong thing. A small step in parameter space can be a huge step in behavior space — nudge a few weights and a softmax can flip which action it prefers. What we should limit is not how much the weights move, but how much the policy's behavior moves.
So TRPO poses each update as a constrained problem:
Maximize expected advantage — subject to: the new policy's action distribution stays within a small KL-divergence of the old one.
KL divergence is just a measure of how different two probability distributions are. The constraint defines a trust region: a bubble of policies that behave similarly to the current one. Inside the bubble, the gradient estimates you computed from the current policy's data are still valid. Outside it, they're fiction — the data came from a policy that no longer resembles the one you're evaluating.
And it works. TRPO delivered near-monotonic improvement on hard control problems and made deep RL dramatically more stable. For a while, it was the state of the art.
The problem: actually solving that constrained problem is a nightmare. To respect the KL constraint properly, TRPO needs second-order information — the curvature of the KL divergence, a Hessian-like object called the Fisher information matrix. For a network with millions of parameters, you can't even store that matrix, let alone invert it. TRPO works around this with conjugate-gradient tricks to approximate the natural gradient, plus a backtracking line search to enforce the constraint.
It's genuinely elegant math. It is also: hard to implement, easy to get subtly wrong, computationally heavy, and awkward to combine with everyday deep-learning machinery — shared actor-critic layers, dropout, minibatch reuse. The community had a stable algorithm that few people could comfortably use.
The question practically asks itself.
The trust region is the right idea, but enforcing it needs Hessian-scale machinery. Can we get the trust region's effect without the trust region's math?
One of the most effective hacks in modern machine learning — and the group trick that carried the story into the LLM era.
PPO (Proximal Policy Optimization, 2017) answers yes. Instead of constraining the update with second-order machinery, it changes the objective so that large policy changes simply stop being rewarded.
Define the probability ratio between the new and old policy for an action:
$$r=\frac{\pi_{\text{new}}(a\mid s)}{\pi_{\text{old}}(a\mid s)}$$
If \(r=1\), the policy hasn't changed for this action. PPO multiplies the advantage by this ratio — but clips the ratio to stay inside \([1-\varepsilon,\;1+\varepsilon]\) (with \(\varepsilon\approx 0.2\)), and takes the more pessimistic of the clipped and unclipped versions:
$$L \;=\; \min\!\big(\,r\,A,\;\; \mathrm{clip}(r,\,1-\varepsilon,\,1+\varepsilon)\,A\,\big)$$
That formula is easier to see than to read:
In words: once the new policy differs from the old one by more than ~20% on an action, making it differ even more earns you nothing. There is no incentive to leave the neighborhood of the old policy.
And because that's just a modified loss function, everything becomes ordinary again: plain first-order gradient descent, Adam, minibatches, several epochs on the same batch, ~30 lines of core logic. PPO trades TRPO's guarantees for TRPO's spirit at a fraction of the complexity — and empirically it matched or beat TRPO almost everywhere. It became the default workhorse of deep RL, and years later it was the algorithm behind RLHF, the technique used to fine-tune chat models from human feedback.
The pattern — find the bottleneck, fix exactly that — kept going right into the LLM era. When you run PPO on a large language model, the bottleneck turns out to be the critic. Remember why the critic exists (Part 3): it's a variance-reduction device — it supplies the baseline. But for an LLM, the critic is itself a billion-parameter model that must be trained, stored, and evaluated alongside the actor. That's an enormous price for a baseline.
GRPO (Group Relative Policy Optimization, used to train DeepSeek's reasoning models) asks: what if we get the baseline a cheaper way? For each prompt, sample a group of responses from the current policy, score them all, and use the group's average score as the baseline:
The critic is deleted entirely — the group plays its role — while PPO's clipping machinery stays. And notice what happened: the field circled all the way back to the Part 2 insight ("subtract how well I usually do"), just with a new, cheaper way to estimate "usually."
None of these algorithms fell from the sky. Each one is the previous one, plus a patch for its most painful failure. If you ever forget an equation, you can re-derive the shape of it just by remembering which problem it was born to solve — and that's a far more durable kind of understanding than a list.
Where to go from here: this series followed the on-policy, policy-gradient lineage because it's the cleanest single storyline. There's a parallel evolutionary tree on the value-based side (Q-learning → DQN → Double DQN → Rainbow) and an off-policy actor-critic branch (DDPG → TD3 → SAC), each with its own chain of problem-and-fix. Same game, different family.