RL foundations, narrated

Welcome. This is a narrated tour of the first nine chapters of the course: the foundations of reinforcement learning, from a robot walking around a grid to PPO, the algorithm used to train the first generation of chat assistants.

The goal is not to replace the chapters. It's to give you the whole arc in one sitting, so that when you read each chapter, you already know where it fits. Every slide links to its chapter, and every chapter has a demo you can play with.

We'll move in three acts. First, values in tables: bandits, Markov decision processes, dynamic programming, and learning from experience. Second, we replace the tables with neural networks, and see why that's harder than it sounds. Third, we stop learning values and optimize the policy directly: policy gradients, actor-critic, and PPO.

Along the way, I'll point out where each idea comes back when we train language models, because that's where this course is headed.

Every reinforcement learning problem has two parts. The agent is the learner. The environment is everything else.

They talk in a loop. At each time step the agent observes a state and picks an action. The environment answers with a reward, a single number saying how good that step was, and a new state. In code, the entire interface is two functions: reset, which starts an episode, and step, which takes an action and returns the next state, the reward, and whether the episode is over.

Three more words complete the vocabulary. A policy, written pi of a given s, is the agent's rule for choosing actions. A value is how much total reward the agent can expect from a state if it keeps following its policy. And a model is the agent's own prediction of what the environment will do.

The goal of RL, stated once: find a policy with the largest expected total reward.

What exactly does the agent maximize? Not the reward right now, but the return: the sum of future rewards, each one discounted by a factor gamma for every step of delay. The return has a recursive form you'll see again and again: the return now is the reward now, plus gamma times the return from the next step.

Here is the gridworld from Chapter 1. There are two routes to the goal. The bridge takes six moves, with pits right underneath it. The long way round takes ten moves and is safe.

With gamma equal to zero point nine and no slipping, the bridge's return is zero point nine to the fifth power, about zero point five nine. The long way is zero point nine to the ninth, about zero point three nine. So the bridge wins.

Now make the floor slippery, so a move sometimes slides sideways. Once the slip probability passes about seven percent, the long way round becomes better. Same map, different dynamics, different best behavior.

Why is this a separate field from supervised learning? Three reasons. First, the feedback is evaluative: it tells you how good your action was, never what the right action would have been. Second, consequences are delayed: a move now may only pay off many steps later. Third, your actions choose your data. A supervised learner gets a fixed dataset. An RL agent only sees the parts of the world its own behavior leads it to.

From these come the three core challenges. Credit assignment: which of my many actions earned this reward? Exploration versus exploitation: should I try something new, or use what already works? And generalization: how do I act well in states I've never seen?

One more warning, which will matter a lot later. An agent optimizes the reward you wrote, not the goal you meant. In a well-known example from twenty sixteen, an agent in the boat-racing game CoastRunners was rewarded by the game score. It found a lagoon where targets kept reappearing, and circled there forever, crashing and catching fire, without ever finishing the race. This is called specification gaming, or reward hacking. It is a central problem when we train language models with RL.

Let's strip RL down to its simplest form. A bandit is a row of slot machines, each with an unknown average payout. There's only one state. You pull an arm, see a reward, and pull again. No delayed consequences, no navigation. All that's left is the tension between exploring and exploiting.

To act well you need an estimate of each arm's value, written q star of a. The natural estimate is the average of the rewards you've seen from that arm. And you can compute that average incrementally: the new estimate is the old estimate plus one over n, times the difference between the latest reward and the old estimate.

Look at the shape of that update, because it's the single most important pattern in this lesson. New estimate equals old estimate, plus a step size, times target minus old estimate. TD learning has this shape. Q-learning has this shape. Every critic we'll train has this shape. The only things that change are what the target is, and how you choose the step size.

So how should you explore? The greedy strategy always pulls the arm with the best current estimate. It fails in a specific way: if a good arm happens to give a low reward early, its estimate drops, you stop pulling it, and that estimate is never corrected.

Epsilon-greedy fixes this with brute force: with a small probability epsilon, pull a random arm. It works, but because it keeps exploring at the same rate forever, its regret, the total reward you lose compared to always playing the best arm, still grows linearly in time.

Smarter methods explore where it's informative. UCB adds an uncertainty bonus to each estimate, the square root of log t over the number of pulls, and picks the arm with the highest optimistic value. Arms you've rarely tried get a big bonus. Thompson sampling keeps a posterior over each arm's mean, draws one plausible world from it, and acts optimally in that world.

Both reach logarithmic regret, which is the best possible growth rate. In the chapter's demo, Thompson sampling is usually the strongest, with no exploration parameter to tune.

Before we leave bandits, two extensions. First, if a context arrives before each choice, you have a contextual bandit. Now notice what that describes: a language model receives a prompt, which is the context, produces a whole response, which is the arm, and gets a single reward at the end. Reinforcement learning from human feedback on single responses is a contextual bandit. Chapters eleven through sixteen build on exactly this view.

Second, if the rewards drift over time, don't average over all of history. Use a constant step size alpha instead of one over n. That gives an exponentially weighted average that remembers roughly the last one over alpha rewards. You'll see constant step sizes everywhere from here on, for the same reason: in RL, the thing you're estimating keeps changing as the policy improves.

Now add states back. A Markov decision process, or MDP, is a bandit where each action also moves you to a new state. It's defined by five things: the set of states, the set of actions, the transition probabilities P of s prime given s and a, the reward function, and the discount gamma.

The key assumption is the Markov property: the current state contains everything about the past that matters for the future. If your state is missing something, say a pendulum's position without its velocity, the fix is to put more history into the state.

That fix is free for language models. The state of an LLM is the prompt plus every token generated so far, so it's Markov by construction.

One useful way to read gamma: it sets an effective horizon of about one over one minus gamma steps. Gamma of zero point nine looks about ten steps ahead. Gamma of zero point nine nine, about a hundred. And gamma equal to zero only cares about the next reward.

Value functions turn the long-term goal into numbers attached to states. V pi of s is the expected return if you start in state s and follow policy pi. Q pi of s and a is the expected return if you take action a first, and follow pi after that.

They're tied together by two relations. V is the policy-weighted average of Q over actions. And Q is the immediate reward, plus gamma times the expected value of wherever you land.

Q has a particularly useful interpretation. It answers the question: what happens if I deviate from my policy once, right now, and then go back to it? If some action has a higher Q than the policy's own value, that one-time deviation is an improvement. Make that deviation permanent and you've improved the policy. Hold on to that idea: it's the engine of the next chapter.

Plug one relation into the other and you get the Bellman expectation equation. In words: the value of a state is the expected reward now, plus the discounted expected value of the next state. It's the recursion of the return, averaged.

Write it with vectors and matrices, and it's just a linear system. V equals r pi plus gamma P pi times V. So V equals the inverse of the identity minus gamma P pi, applied to r pi. For a small problem, that's one call to a linear solver.

If you expand that inverse as a geometric series, you get a sum over k of gamma to the k, times P pi to the k, times r. Read physically, it's a propagator: the expected reward k steps from now, discounted, summed over all k.

You can also just iterate: start with any guess and keep applying V gets r plus gamma P V. For gamma below one, this converges geometrically. That observation is about to become a theorem.

Chapter three measured a given policy. Chapter four finds the best one.

The optimal value function satisfies the Bellman optimality equation. It's the same equation as before, except the average over the policy's actions is replaced by a max. The best you can do from here is the best one-step lookahead, assuming you act optimally afterwards. The max makes it nonlinear, so there's no single matrix inverse anymore.

But once you have V star, or better, Q star, acting optimally is easy: in every state, take the action with the highest Q star. That greedy policy is optimal everywhere at once, and it's deterministic. This is the deep reason value functions matter: they compress a long-horizon planning problem into a sequence of one-step decisions.

There are two classic ways to solve the optimality equation when you know the model.

Policy iteration alternates two steps. Evaluate the current policy, by solving for its value. Then improve it, by acting greedily with respect to its Q. The policy improvement theorem guarantees the new policy is at least as good everywhere, and strictly better somewhere, unless it's already optimal. Since there are finitely many deterministic policies, this ends in finitely many iterations.

Value iteration skips the full evaluation and just applies the optimality equation as an update, sweep after sweep.

Why does that converge? Because the Bellman operator is a contraction. Apply it to any two value functions, and the largest difference between them shrinks by at least a factor of gamma. By Banach's fixed point theorem, there is exactly one fixed point, and iterating reaches it from any starting guess, with the error shrinking like gamma to the k. A nice practical fact: the greedy policy often becomes optimal well before the values have converged.

Step back and look at the pattern. Evaluate a policy, then improve it using those values, then evaluate the new policy, and so on. You don't have to evaluate fully, and you don't have to improve everywhere at once. Any interleaving of the two, in any proportion, still heads toward the optimum. This is called generalized policy iteration, and it's the template for nearly every algorithm in this course, including the ones used to train language models. In PPO, for example, the critic does the evaluating and the policy update does the improving.

Dynamic programming has two big limitations. It needs the model: the transition probabilities and rewards. And it sweeps over every state. Real problems break both. Chapter five removes the need for a model by learning from sampled experience. Chapter six handles huge state spaces with function approximation.

Now we drop the model. The agent only has its own stream of experience.

Monte Carlo learning waits until the episode ends, computes the actual return from each state, and nudges the state's value toward it. Same incremental-update shape as the bandit. The target is unbiased, because it's a real sample of the return. But it's noisy, because it sums up every random event until the end, and you can't update until the episode is over.

Temporal-difference learning, TD for short, doesn't wait. After one step, it uses the reward it just got plus gamma times its current estimate of the next state's value as the target. The gap between that target and the current estimate is called the TD error, delta. Using your own estimate inside your target is called bootstrapping. It makes the target biased, because your estimates may be wrong, but much less noisy, because only one step of randomness is involved. And it updates after every single step.

In between lie n-step returns: n real rewards, then bootstrap. Keep this bias-variance dial in mind; in Chapter eight it becomes GAE.

To control, rather than just predict, learn Q instead of V. With Q in hand, acting greedily needs no model, you just compare the actions' values. And to keep exploring, act epsilon-greedily.

The two classic algorithms differ in one line: the target. SARSA uses the action you will actually take next. So it learns the value of its own exploring behavior. That's called on-policy. Q-learning uses the max over next actions. So it learns the value of the optimal policy, no matter how it's behaving, as long as everything keeps getting tried. That's called off-policy.

The cliff-walking problem shows the difference in one picture. Walking along the edge of the cliff is optimal, thirteen steps. Q-learning learns that path, but while it's still exploring, a random step sends it over the edge, so it falls a lot. SARSA knows it sometimes takes random steps, so it learns a safe detour away from the edge, and earns more while learning.

One caveat: taking a max over noisy estimates is biased upward. Double Q-learning fixes this by using one estimate to choose the action, and another to score it.

Act two. Tables have one entry per state. That's fine for a forty-eight cell cliff, hopeless for Atari screens or language. Worse, a table never generalizes: learning about one state tells you nothing about a nearly identical one.

So we replace the table with a parametric function, linear features or a neural network, and update its parameters. A table turns out to be the special case of linear features that are one-hot.

The natural update is called semi-gradient TD. Compute the TD error as before, and move the weights along the gradient of the predicted value, scaled by that error. It's semi because we treat the bootstrapped target as a fixed label and don't differentiate through it. That means it isn't the gradient of any objective function. Even so, for linear features and on-policy data, it provably converges.

Here's the catch. Combine three ingredients: function approximation, bootstrapping, and off-policy updates. Any two of them together are fine. All three together can diverge. This is called the deadly triad.

The chapter's smallest example makes it concrete. Two states share a single weight: A's value is w, and B's value is two w. The agent only ever updates on the transition from A to B, with zero reward. Each update moves w toward gamma times two w. If gamma is above one half, the target is always bigger than the current value, and the shared weight drags B's value up even further. So w gets multiplied by one plus alpha times two gamma minus one, on every step. It grows geometrically, forever.

If you also update on B, which on-policy data would do, B's own update sees that its value is too high and pulls w back. That's why the off-policy part matters.

DQN, the algorithm that learned Atari games from pixels, is Q-learning with a neural network: all three ingredients of the triad. It works anyway because of a set of stabilizers.

Experience replay stores transitions in a buffer and trains on random mini-batches, which breaks the correlation between consecutive frames and lets each sample be reused. A target network is a frozen copy of the Q network used to compute targets, updated only every C steps, so the regression target stops chasing itself. That makes each phase look like one step of approximate value iteration. The Huber loss and reward clipping keep the gradients bounded. And double DQN removes most of the upward bias of the max.

But value-based methods have a structural limit. To act, you need a max over all actions, and the policy you get is deterministic. That's awkward for continuous actions, and for a language model, whose action space is a vocabulary of a hundred thousand tokens and whose outputs we want to sample. So we change strategy.

Act three. Instead of learning values and acting greedily, parameterize the policy itself, with weights theta, and do gradient ascent on the expected return J of theta. This handles continuous actions, changes the behavior smoothly, can represent stochastic policies, and fits language models perfectly, because a language model already is a policy over tokens.

The problem is that J is an expectation over trajectories whose distribution depends on theta. How do you differentiate that? With the log-derivative trick: the gradient of an expectation of f equals the expectation of f times the gradient of log p. Now it's an expectation again, so you can estimate it by sampling. And f, the reward, doesn't need to be differentiable at all. It can be a game score, a unit test, or a human's thumbs-up.

Apply it to whole trajectories and something lovely happens: the environment's transition probabilities don't depend on theta, so they drop out of the gradient. You need samples from the environment, never its model. The policy gradient is the expected sum, over time steps, of the gradient of log pi of the action taken, times the return.

In code, the policy gradient becomes the algorithm called REINFORCE, and it's only a few lines. Compute the log probability of each action you actually took. Multiply each by its weight, the return, with the weights detached so no gradient flows through them. Take the negative mean as your loss, and backpropagate.

Look at what that is: it's ordinary maximum-likelihood training, like supervised learning, except the training data are your own samples, and each one is weighted by how well it turned out. Good outcomes get their actions made more likely. Bad ones, less likely.

Two consequences. First, it's on-policy. The gradient is only correct for samples from the current policy, so after one update the batch is stale and you have to collect new data. Second, it's noisy, because a single return reflects every random event in the episode. Fixing that noise is the next two slides.

Two tricks remove noise without adding any bias.

First, reward-to-go. An action can't influence rewards that came before it, so weight each action only by the rewards that come after it. Those earlier terms had zero mean anyway, they only added noise.

Second, a baseline. Subtract any function of the state, b of s, from the return. This doesn't change the expected gradient, because the gradient of log pi has zero mean under the policy. So the subtracted term averages to zero. But it can cut the variance enormously. The one rule: the baseline must not depend on the action. A physicist would call this a control variate. A good choice is the expected return from that state, V of s.

And here's the link forward. When you train a language model with RLOO or GRPO, you sample several responses to the same prompt, and use the average reward of the group as the baseline. That's REINFORCE with a clever, critic-free baseline. Chapters fifteen and sixteen are built on this slide.

If V of s is the ideal baseline, then the ideal weight for each action is the return minus V, in expectation: the advantage, Q minus V. It answers exactly one question: was this action better or worse than what the policy usually does here? It averages to zero, and carries only the signal you need.

We don't know V, so we learn it. An actor-critic method trains two things. The critic, a value network, learns V by regression on observed returns or TD targets. The actor, the policy, is updated with the policy gradient, using the critic's advantage estimates as weights.

The simplest advantage estimate is the TD error itself: reward, plus gamma times the critic's value of the next state, minus its value of this state. If the critic were perfect, this would be unbiased. In practice the critic is imperfect, so it's biased, but it has very low variance, since only one step of randomness is involved. Sound familiar? It's the Monte Carlo versus TD trade-off from Chapter five, coming back.

Between one-step TD and full Monte Carlo there's a whole family of n-step advantage estimates. The n-step advantage is just the discounted sum of the next n TD errors. More real rewards means less dependence on the critic, and more variance.

Generalized advantage estimation, GAE, takes an exponentially weighted average of all of them. The result is beautifully simple: the advantage is a sum of future TD errors, weighted by gamma lambda to the power l. You compute it in one backward pass over the rollout: each advantage is this step's TD error, plus gamma lambda times the next advantage, reset to zero at episode ends.

Lambda equal to zero gives one-step TD. Lambda equal to one gives Monte Carlo minus a baseline. So lambda is a dial for how much you trust your critic. The chart shows the weights. With PPO's usual defaults, gamma zero point nine nine and lambda zero point nine five, the weights decay over about seventeen steps. With lambda one half, about two.

This machinery is exactly what's inside PPO-based reinforcement learning from human feedback. Each token is one step. The state is the prompt plus the tokens so far, and a value head on the model predicts the value at every position. The per-token rewards are mostly zero, apart from a small KL penalty at each token and the reward model's score at the very end. GAE turns those into per-token advantages, typically with gamma equal to one, since a response is short and its end is what gets judged.

But the critic is a whole extra language model to store and train, and learning the value of half-finished reasoning from a single end-of-response score is hard. So GRPO and its relatives drop the critic altogether. They use lambda equal to one, the full reward, and replace V with the average reward of several responses sampled for the same prompt. In this chapter's language, that's GAE at lambda equal to one, with a cheap, critic-free baseline.

Vanilla policy gradient has two problems that PPO was designed to fix. It's fragile and it's wasteful.

Fragile, because distance in parameter space is not distance in behavior. A step that looks small in theta can change the policy dramatically. And in RL, a bad step is worse than in supervised learning: the broken policy collects the next batch of data, so you can fall off a cliff and not climb back.

Wasteful, because each batch of rollouts gives one gradient step, and then it's thrown away.

The fix for waste is importance sampling. Define the ratio rho: the new policy's probability of the action, divided by the old policy's probability. Then the surrogate objective, the average of rho times the advantage, lets you evaluate a new policy using data from the old one. At the old parameters, it matches the true objective in both value and gradient. But the further the new policy moves, the less you can trust it. The ratios get noisy, and the new policy visits states the old data never saw. So we need to limit how far each update moves.

The principled way to limit an update is a trust region. Maximize the surrogate, subject to the KL divergence between the old and new policies staying below some small delta. Now the constraint is on behavior, not on parameters.

Expand the KL to second order around the old policy, and it becomes a quadratic form: one half delta theta transpose, F, delta theta, where F is the Fisher information matrix. If you know information geometry, F is the metric on the space of distributions. Solving the constrained problem gives the natural gradient: F inverse times the ordinary gradient. It's steepest ascent, measured in distribution space.

TRPO implements this. It computes F inverse g with conjugate gradient, without ever forming F, and then does a line search, shrinking the step until the actual KL is within bounds and the surrogate actually improved. It works well, but it's complicated, and awkward to combine with shared networks and large models.

PPO gets most of TRPO's benefit with a one-line change to the loss. Take the surrogate, rho times the advantage. Also compute a clipped version, where rho is squashed into the range one minus epsilon to one plus epsilon, with epsilon typically zero point two. Then take the minimum of the two.

Look at the left panel, a good action with positive advantage. As the update makes that action more likely, rho rises. Once it passes one point two, the objective goes flat, so the gradient for that sample is exactly zero. There's no further incentive to push. The right panel is a bad action, with negative advantage. Once its probability has been cut so that rho falls below zero point eight, again the objective is flat and the gradient is zero.

Everywhere else, you get the ordinary importance-weighted policy gradient. And the min makes it pessimistic: the clip can only remove improvement you might be overestimating, never add any. That's why it's a lower bound on the surrogate.

Here's the full algorithm. Collect a batch of rollouts with the current policy. Compute advantages with GAE and normalize them. Then, for several epochs, loop over mini-batches and minimize a combined loss: the clipped policy loss, plus a weighted value loss for the critic, minus a small entropy bonus to keep exploring. Clip the gradients, and anneal the learning rate.

One subtlety. Clipping removes the incentive to move further, but it's not a hard wall. With big learning rates and many epochs, the policy can still overshoot. So in practice you monitor two numbers: the approximate KL between the old and new policies, and the clip fraction, the share of samples whose ratio is outside the band. If the KL gets too large, stop the epoch loop early.

And one distinction that trips people up when reading LLM papers. This KL, to the old policy, is a trust region between consecutive updates. RLHF adds a different KL, to a fixed reference model, as a leash that stops the model drifting too far from where it started. LLM training uses both.

Let's tie it together with four threads you'll keep pulling on.

One. Estimate plus step size times target minus estimate. It started as a running average for slot machines and became TD learning, Q-learning, and every critic.

Two. Generalized policy iteration. Evaluate, improve, repeat. In PPO, the critic evaluates and the clipped policy update improves.

Three. Bias versus variance. Monte Carlo against TD, the n-step and lambda dials, baselines and advantages. Almost every design choice in modern RL is a position on this trade-off, including GRPO's choice to drop the critic.

Four. Stability. Target networks, trust regions, clipping, and the KL you monitor while training.

From here, Chapter ten surveys the wider landscape, from AlphaZero to offline RL. Then Chapter eleven starts part three, where the language model itself becomes the policy, and everything in this lesson gets put to work. Thanks for listening.