Stanford CS221 | Autumn 2025 | Lecture 8： Reinforcement Learning — Annotated Lecture Notes & Key Takeaways

Course Information

Institution: Stanford

Original Course: Stanford CS221 | Autumn 2025 | Lecture 8: Reinforcement Learning

Instructor Bio: This lecture is delivered by Percy Liang, Associate Professor of Computer Science at Stanford University and core faculty of the Stanford Institute for Human-Centered Artificial Intelligence (HAI). Percy Liang leads the Stanford Natural Language Processing Group and the Center for Research on Foundation Models (CRFM). His research spans the theoretical foundations and practical systems of artificial intelligence, including machine learning, natural language processing, AI alignment, and rigorous model evaluation. He received his PhD in Computer Science from the University of California, Berkeley and his BA in Mathematics from Harvard University. His work has been recognized with the NSF CAREER Award, Google Faculty Research Award, and multiple best paper awards at top-tier AI conferences. He has taught CS 221 at Stanford for over a decade, shaping foundational AI education for thousands of students.

Course Description: This lecture builds on MDP theory to introduce reinforcement learning, where agents learn optimal behavior through trial-and-error interaction with the environment rather than complete prior knowledge of transition dynamics. It covers the core exploration-exploitation dilemma, then details model-free RL algorithms including Q-learning and SARSA. The lecture also explains temporal difference learning and how agents can incrementally update value estimates directly from experience.

I went into this lecture expecting reinforcement learning to be a big conceptual leap from the Markov decision processes covered the week before. It turned out to be something gentler: the leap is not in the math but in what you are allowed to know. In an MDP you are handed the whole model. In reinforcement learning​ you are handed nothing, or almost nothing, and you have to poke at the world until a picture of it forms. That single change — from knowing the transition probabilities to having to estimate them — turns out to explain almost every design choice in the rest of the hour.
 

Where the Lecture Starts: A Quick MDP Refresher

 

The first several minutes are a recap, and the lecturer is explicit that it should all be review. An MDP is specified by a start state, a successor function that returns actions with their probabilities, rewards, and next states, an end test, and a discount factor. He walks through the running example he used last time: a "flaky tram" problem where the goal is to get from state 1 to state 10. At each state you can either walk, moving from i to i+1 at a cost of 1, or take a tram, moving from i to 2i at a cost of 2 — except the tram fails 40% of the time and leaves you exactly where you started, still having paid the 2.
 

What I appreciated about the visualization is that it makes the division of labor obvious. The graph has two kinds of nodes. At state nodes the agent decides. At chance nodes nature decides, and the branch it picks is where you collect your reward. Walking costs 1 with certainty; taking the tram costs 2 whether or not it works, which is the detail that makes the problem non-trivial.
 

A solution here is not a sequence of actions the way it was in the search problems earlier in the course. Because of the randomness, you need a policy — a mapping from every state to an action. He shows one candidate policy, "take the tram whenever possible," and then runs it forward to produce a rollout, which is just one sampled path through the graph. The utility of a rollout is the discounted sum of rewards along it; with a discount of 1 that is a plain sum, and with a discount of 0.5 each successive reward gets halved, then quartered, and so on. The value of a policy is the expected utility, which he glosses as what you would get by averaging over infinitely many rollouts.
 

From there it is a short step to the two algorithms. Policy evaluation computes the value of a fixed policy by setting up a recurrence over states and iterating it, very much in the spirit of the dynamic programming from earlier in the term. Value iteration takes the same recurrence and simply inserts a max over actions inside it, which gives you the value of the optimal policy, from which you can read off the policy itself. For the flaky tram the answer is to walk up to state 5 and take the tram from there.
 

There is a small exchange with a student about the word partial in the code, which the lecturer explains as partial function application: the tram policy takes two arguments, an MDP and a state, and calling it with only the MDP returns a function that still expects a state. It is a Python syntax point rather than a conceptual one.
 

The Recurrences as Fixed Points, and Why That Framing Matters

 

After the recap the lecturer re-derives both algorithms from a different angle, and this is where the hour starts to earn its keep for anyone who likes math. The policy evaluation recurrence is drawn as a tree: you stand at a state, you take the action your policy prescribes, nature picks a successor, and the value of where you are is the reward you just collected plus the discounted value of where you landed. Because that equation mentions the value of other states, and those values depend on yours in turn, the whole thing is a fixed point rather than a one-pass computation.
 

The same picture with a max over actions instead of a fixed action gives the value iteration recurrence, which he identifies as the Bellman equation. The point he keeps returning to is that these recurrences are not algorithms yet. They are conditions that the true value function satisfies. An algorithm is what you get when you decide how to go about finding a function that satisfies the condition, and the simplest way is to start with an arbitrary guess and repeatedly apply the right-hand side until the numbers stop moving.
 

One thing I found useful here is the contrast between the two update orders. Policy iteration alternates: evaluate the current policy fully, then improve it by acting greedily with respect to the values you just computed, and repeat. Value iteration skips the separate evaluation phase and does a single sweep of the Bellman update, which implicitly does a little bit of evaluation and a little bit of improvement in the same pass. They converge to the same place; they just take different routes, and the right one depends on how expensive a full evaluation is relative to a single sweep.
 

The Turn: What If Nobody Hands You the Model?

 

The hinge of the lecture is the move from the MDP setting to the reinforcement learning​ setting, and it is framed as a question about knowledge. Everything so far assumed you could call the successor function and get back probabilities. In reinforcement learning you cannot. You can act, and you can observe what reward comes back and which state you end up in, but the underlying probabilities and rewards are hidden.
 

That one subtraction has a cascade of consequences, and the lecturer walks through them one at a time.
 

The first consequence is that rollouts become the only evidence you have. If you cannot enumerate the successor function, the way you learn about the world is by living in it — taking actions, watching outcomes, and accumulating a running record. This is what makes the problem feel statistical rather than purely computational: you are now estimating quantities from samples, and every estimate carries noise.
 

The second consequence is that the algorithms have to be rewritten to consume samples instead of distributions. The recurrences survive, but the expectations inside them get replaced by averages over what actually happened. A value that used to be computed in one clean pass now has to be nudged gradually toward its target as evidence arrives.
 

The third consequence is the one the lecturer spends the most time on, and it is the part I would flag for anyone reading along: exploration. If you only ever do what currently looks best, you will never discover that some other action is better, because you have no model to tell you what the other action would have done. You have to spend some of your budget on actions that look worse, purely to gather information. That is not a detail you can bolt on afterward; it shapes the whole design.
 

Model-Based Learning: Just Estimate the MDP

 

The first family of approaches he presents is the one that follows most directly from the MDP material: don't fight the unknown, just fill it in. If you act for a while and record every transition — I was in state s, I took action a, I got reward r, I landed in s' — you can count how often each outcome followed each state-action pair and use those frequencies as estimates of the transition probabilities and rewards. Once the estimates are in place you have a concrete MDP, and you can run value iteration or policy iteration on it exactly as before.
 

I like this framing because it makes the structure of the field legible: learn the model, then plan in the model. It is a clean separation of concerns, and it means you get to reuse all the machinery from the previous lecture without modification.
 

The weakness is equally clear from the way he presents it. Your estimate is only as good as your coverage. If a particular state-action pair has never been tried, you have no data about it, and the planner will happily optimize against a guess. If a rare but important outcome has not shown up yet, it is invisible. The lecturer does not dwell on this, but the shape of the problem is visible in the setup: the quality of the resulting policy is bounded by the quality of the exploration that produced the data, and nothing in the "estimate then plan" recipe tells you how to explore well.
 

Model-Free Learning and the Exploration Trade-Off

 

The second family drops the model entirely and tries to learn values or policies directly from experience. Rather than estimating transition probabilities as an intermediate step, you maintain estimates of the quantities you actually care about and update them toward observed returns. This avoids committing to a possibly wrong model, and it is often simpler to implement, but it gives up the ability to plan: you cannot ask "what would happen if I did this?" because there is nothing to simulate the counterfactual in.
 

He then gets to the part that I think is the conceptual heart of the hour. There is a genuine tension between two things you want. Exploitation means taking the action that your current estimates say is best, which maximizes reward right now. Exploration means taking actions whose outcomes are still uncertain, which costs reward now but may reveal something better. You cannot do both with the same action, so every step is a small bet on which one matters more at that moment.
 

The scheme he sketches for managing this is optimism in the face of uncertainty. The idea is to give every state-action pair an optimistic bonus that shrinks as you gather data about it. Actions you have tried many times get a bonus close to zero, so they are judged on their estimated value. Actions you have barely tried get a large bonus, which makes them look attractive even if their current estimate is poor. The effect is that the agent is systematically drawn toward what it does not yet know, and the draw weakens on its own as the ignorance is resolved. It is a neat trick: the same mechanism that drives exploration also guarantees that exploration eventually stops.
 

The question he raises but does not fully settle is whether optimism is the right principle or merely a convenient one. It has the advantage of being analyzable — you can often prove that an optimistic agent will not miss the best action by too much — but it is tied to a particular notion of uncertainty, and there are settings where being optimistic is simply the wrong attitude, particularly where some actions are risky in ways that are not just "unknown yet." He gestures at this rather than resolving it.
 

What I Found Hard to Follow

 

Two places slowed me down. The first is the transition from fixed-point equations to concrete update rules. The recurrences are stated cleanly, and then the sample-based versions appear, and the relationship between the two — which terms are being replaced by averages, and what the step size is doing — goes by faster than I could comfortably track. This is a section that would benefit from a worked example carried all the way through several updates with actual numbers, rather than the general form.
 

The second is the boundary between the model-based and model-free families. The lecture presents them as alternatives, but it is not obvious to me that they are as separate as the presentation implies. Several practical methods sit somewhere in between, using samples both to fit a model and to correct value estimates. The clean two-bucket framing is pedagogically useful, and I suspect that is exactly why it is there, but I came away unsure whether the distinction is a real theoretical fault line or a teaching device.
 

Why the Framing Matters Beyond This Lecture

 

What makes reinforcement learning​ worth a lecture right after MDPs is that it changes the question from "how do I compute the answer" to "how do I arrive at the answer without being told the rules." That shift is what makes the subject feel like learning rather than planning, and it is why exploration shows up as a first-class concern instead of an implementation detail.
 

The connection back to the rest of the course is tighter than it first appears. The recurrences are the same dynamic-programming recurrences from earlier in the term. The difference is that in a search problem the graph is given, in an MDP the graph is probabilistic but known, and in reinforcement learning the graph has to be discovered by interacting with it. Each step removes an assumption and asks what the algorithms look like without it.
 

By the end of the hour the picture I had was this: MDPs give you the target, reinforcement learning describes the situation of not knowing the target, and the space of algorithms is organized by how much structure you are willing to guess at along the way. The flaky tram is a toy, but it is a well-chosen one, because the tension it sets up — the cheap action you understand versus the expensive action that might shortcut everything — is the same tension that exploration has to manage in general.
 

Content Disclaimer:

This article is for general reference only and does not constitute professional R&D guidance, production process advice or quality certification. All material performance data has specific test premises; readers should verify parameters against actual equipment and working conditions.