The six-symbol language that every RL algorithm is written in — and the most tempting wrong idea in robotics: just copy the expert. We build the MDP from zero, then watch behavior cloning fall off a cliff.
You're a robot at one end of a narrow hallway. The exit — a charging dock — is at the far end. Every step costs you a little battery. Reaching the dock pays off big. At each tile you face the same plain question: which way do I move?
That sounds trivial until you notice the trap. Moving toward the dock burns battery now, but the reward only arrives later. A short-sighted robot, hating the cost of every step, might just freeze in place to avoid spending anything — and never get paid. A far-sighted robot endures the small costs because it sees the big payoff at the end. The whole art of sequential decision-making lives in that tension: pay now, get rewarded later.
Play with the hallway below. You pick how far-sighted the robot is — that's the discount, our first character. Watch how its total score changes. When the robot barely cares about the future, the distant dock looks worthless and the step costs dominate. When it cares a lot, the dock's payoff shines through and the journey is clearly worth it.
A 6-tile hallway. Each move costs −0.1 battery; the dock pays +1.0. Slide the discount: near 0 the robot is myopic (the far dock looks worthless); near 1 it is far-sighted (the dock is worth the trip).
By the end of this lesson you'll be able to compute that score by hand, prove a value with a single backup, and understand why the obvious shortcut — just record an expert robot and copy it — is a much worse idea than it looks.
To state the hallway problem precisely we need a formal object. That object is the Markov Decision Process (MDP) — the mathematical container for "sequential decisions." It is just a tuple of pieces, and we'll define each one with an analogy before we ever use it.
| Symbol | Name | Analogy |
|---|---|---|
| s | State | The complete situation of the world right now — "where the robot stands, what it's holding." A snapshot. |
| a | Action | The lever the robot pulls — "step left", "step right", a motor torque. |
| r(s,a) | Reward | A scorecard: one number saying how good doing a in s was. Bigger is better. |
| p(s′|s,a) | Transition | The world's rulebook (its dynamics): if I do a in s, where do I land next? |
| π(a|s) | Policy | The robot's habit — its decision rule mapping a state to an action. This is what we learn. |
| γ | Discount | A patience dial in [0,1): how much a reward later is worth compared to one now. |
Formally, the instructor writes an MDP as the tuple (S, A, p, r) — the state space S (all possible states), the action space A (all possible actions), the transition p, and the reward r. The discount γ rides along in the objective. The goal is always the same: learn a policy π(a|s).
The "M" is load-bearing. The Markov property says: the next state depends only on the current state and action, not on the entire history of how you got here. In symbols, the transition is p(s′ | s, a) — just this state and this action, no past.
Real robots rarely see the true state s directly. A camera gives pixels, not "the mug is at coordinate (0.3, 0.5)." So we add an observation o, drawn from the true state through an observation model h(o|s). When the robot must act on observations instead of states, the tuple grows to (S, A, O, p, h, r) — a Partially Observed MDP (POMDP), and the policy becomes π(a|o). For most of today we'll assume the robot can see the state (a plain MDP); just know the observation layer is always lurking underneath.
The five moving parts of one step. Click a button to highlight where it sits in the ring. Notice the arrow that closes the loop: the action feeds the transition, which produces the next state.
We have the pieces; now let's see them in motion. A policy π is the robot's brain: feed it the current state, it hands back an action. It comes in two flavors.
Now run the policy forward. Start in some state, the policy picks an action, the transition lands you in a new state, the policy picks again… The sequence it traces out is a trajectory (also called a rollout or episode):
Read it left to right: state, the action the policy chose there, the resulting next state, its action, and so on. A trajectory is one full life of the robot under one policy. Change the policy and you get different trajectories from the same start.
A policy traces a trajectory, and along that trajectory the robot collects a reward at every step. Add them all up and you get the return — the single number we actually want to make large.
But we don't add them equally. We bring back the discount γ from Chapter 0: a reward arriving t steps in the future is multiplied by γt. The total is the discounted return:
The goal of reinforcement learning and control, stated in full: find the policy that maximizes the expected discounted return. "Expected" because transitions and the policy can be random, so we average over all the trajectories the policy could produce.
Back to the hallway. Say the robot takes 3 steps (each costing −0.1) and then reaches the dock (+1.0). The reward sequence is r = (−0.1, −0.1, −0.1, +1.0). With γ = 0.9, weight each reward by γt:
Look closely at that last term. The dock's +1.0, arriving 3 steps away, is "worth" only 0.729 today — that's exactly 0.9³. The near-term costs bite at nearly full strength; the far-off payoff is shrunk by patience. That arithmetic is the pay-now-rewarded-later tension, made into a number — and it's the objective every RL algorithm in this course tries to maximize.
The return G scores one whole trajectory. But a robot standing in a particular state wants a more useful number: "From right here, following my policy, how much reward should I expect to collect over the rest of my life?" That number is the value of the state.
Read the superscript π carefully: value is always value-under-a-policy. The same tile is worth a lot under a good policy and very little under a bad one. There's no such thing as "the value of a state" in a vacuum — only the value of a state given how you'll behave from there on.
There's a closely related quantity that asks a slightly different question: "If I take action a right now in state s, and then follow π forever after, what's my expected return?" That's the action-value or Q-function, Qπ(s,a). Where V scores a state, Q scores a state-action pair — it lets you compare "step left here" against "step right here." Q is the star of Lecture 9; today we just meet it.
A 6-tile hallway, dock on the right. The number in each tile is V(s) under the "always step toward the dock" policy. Slide the discount and watch the appraisals shift: a patient robot values far tiles highly; a myopic one only values tiles near the dock.
Notice the gradient: value climbs as you near the dock. That smooth uphill toward reward is the signal an RL agent secretly chases. But where do these numbers come from? They aren't guessed — they're computed, by the single most important equation in the field, which we build next.
Here's the trick that makes value computable. The value of a state is not a mysterious sum over all futures. It's just the immediate reward, plus the discounted value of wherever you land next. Reward now, plus a peek one step ahead. That self-referential rule is the Bellman equation.
For a deterministic policy in a deterministic world (one action, one next state s′), it reads simply:
where s′ is the state you transition into. When the world is random, you average the future term over where you might land: V(s) = r + γ · (expected V of the next state). The shape is the same — this step's reward, plus a discounted look at the rest.
Take a tiny 3-state chain: tile A → tile B → DOCK. The policy always steps right. Each step costs r = −0.1; arriving at the dock pays +1.0; the dock is terminal (value 0 once you're done). Use γ = 0.9. Work it backward:
That's it — two Bellman backups and the whole chain is appraised. Notice we computed V(B) first, then fed it into V(A). The information traveled backward from the reward. Now let's do it in code for a longer hallway, sweeping until the values stop moving (a fixed point).
Press Backup to apply one sweep of the Bellman rule across the hallway. Watch the reward at the dock flow leftward, one tile per sweep, until the appraisals stop moving.
We now have a precise language for "good behavior": a policy that maximizes the discounted return. But finding that policy from reward is hard. So here's the tempting shortcut that opens the imitation-learning half of this lecture:
This is not a toy. The 1989 ALVINN system at CMU drove a van by behavior cloning: camera image in, steering angle out, trained on a human driver's demonstrations. Today's Mobile ALOHA and Diffusion Policy use the very same recipe with far bigger models. The data flow is dead simple:
Concretely: suppose the expert's action is roughly a linear function of the state (say, steering ≈ a weighted sum of lane-position features). Behavior cloning then becomes ordinary least-squares regression — find weights so π(s) = w·s matches the expert's actions on the demo data. Let's fit exactly that.
On the demo data, the clone is excellent — the points sit right on the diagonal. So behavior cloning does work… on the states the expert visited. The catastrophe is what happens on the states the expert didn't. That's the next chapter.
Behavior cloning looks exactly like supervised learning: a labeled dataset, a loss, gradient descent. So why does the instructor insist, in bold, that it is NOT standard supervised learning? One assumption breaks — and it breaks everything.
Supervised learning rests on a quiet promise: training and test data are i.i.d. — independent and identically distributed, drawn from the same distribution. Under that promise there's a clean chain: low training error → good test performance. Classify image #5 wrong, and image #6 arrives unchanged, drawn from the same pool. The mistakes don't talk to each other.
The expert data contains only good behavior — a skilled driver basically never drifts toward the curb, so the dataset has almost no examples of being near the curb, let alone recovering from it. Now the cloned policy makes one small error and edges toward the curb. It is now in a state the expert never visited, so the clone never learned what to do there. It guesses, errs again, edges further out… and the small mistake cascades.
The instructor's vivid phrase: statistically, imitation learning is cliff walking. One wrong step and you're off the edge, in territory your training never covered. This is the same distribution shift / compounding error we met in Lecture 1 — but now we see exactly where it comes from: the violated i.i.d. assumption.
The teal band is the states the expert demonstrated. The warm dot is the cloned policy. Raise the per-step error and press Run: once it leaves the demonstrated band, it's in states it never trained on — and it spirals away.
The instructor states a sharp result: for behavior cloning, the test-time cost is quadratic in the number of timesteps — it grows like ε·H², not the ε·H you'd expect from naive supervised reasoning. Let's not take it on faith. Let's measure it.
The logic, made simple: with per-step error ε, the policy first slips off-distribution after about 1/ε steps. From that moment it's on the cliff and stays lost for essentially the rest of the episode. So the expected number of "lost" steps grows with how much episode remains after the first slip — and summing that over a horizon of length H gives the famous H² shape.
The warm curve pulls away from the teal line and bends upward — the quadratic, measured. The longer the episode, the more disproportionately a tiny per-step error hurts. This is the headline result of the imitation-learning half of the lecture, and the whole reason Lecture 6 exists.
You've assembled the entire vocabulary of sequential decision-making and met imitation learning's central drama. Everything later in 16-831 either uses this MDP language or fights the cliff you just measured.
This is Lecture 5 of the 16-831 series. The natural next step is Lecture 6 — Imitation Learning, Part 2, which fixes exactly the cliff you measured here (DAgger, data augmentation, powerful models). To go deeper on individual threads, these companion Gleams expand each idea in full:
"Statistically speaking, imitation learning is cliff walking — once you make one mistake, you are outside of the training distribution."