What if you don't have clean equations — only a learned, black-box model you can poke and sample? You plan by trying many action plans, scoring each, and steering your sampling toward the good ones. From sampling-based MPC to learned-model RL, and the one idea that keeps the planner honest: uncertainty.
In Part 1 we lived in a world of clean equations. The dynamics were given to us — a tidy formula for where the robot lands next — and we solved for the optimal action sequence with calculus: LQR, iLQR, sequential convex programming. Take the gradient, set up the Riccati recursion, get a controller. Beautiful, exact, and fast.
Now strip that luxury away. Suppose your "model" of the world is one of these:
In every one of these, you can do exactly one thing cheaply: ask "what happens if I do this?" You feed in a candidate action sequence, roll it forward through the model, and read off the total cost. You cannot easily differentiate it. You can only sample it.
That single recipe — sample, roll out, score, refit, repeat — is the spine of everything here. The Cross-Entropy Method (CEM) and MPPI are two ways to do the "refit" step. And once we can plan against any model we can sample, the obvious next move is to learn the model from data — which opens model-based RL: PILCO, PETS, MBPO. The whole second half is about one danger that lurks the moment the model is learned rather than given: the planner will happily exploit the model's mistakes, and uncertainty is how we stop it.
Let's watch the core loop before we name a single algorithm. The widget below is a planner trying to reach a goal past an obstacle. It samples a cloud of candidate trajectories (faint), keeps the cheapest few (bright), and refits its sampling distribution to them. Press Refit and watch the cloud tighten around a path that curves around the wall.
The planner samples candidate trajectories from a distribution, scores each by how close it gets to the goal without hitting the obstacle, keeps the cheapest "elite" few (warm), and refits. Press Refit one round a few times, or Run to convergence.
Notice two things. The cloud started fat and dumb — trajectories everywhere, most of them slamming into the wall. After a few refits it is a tight ribbon hugging a path around the obstacle. No equation for "curve around the wall" was ever written. The planner discovered it by trying, scoring, and concentrating. That is the power and the price of sampling: it asks nothing of the model except many evaluations.
Before we sample anything, we need the loop that all of this lives inside. It is the single most important control idea of the lecture: Model Predictive Control (MPC), also called receding-horizon control.
The full problem is daunting. The robot must act for a long time — a horizon T of maybe thousands of steps — minimizing the total cost over the whole episode. Solving for all T actions at once is expensive and brittle: the moment reality deviates from your plan (and it will), the tail of the plan is worthless. MPC's answer is a piece of genuine engineering wisdom: don't.
Concretely, at time t, with the robot truly at state xt, MPC solves an H-step trajectory optimization: choose actions ut, ut+1, …, ut+H−1 that minimize the sum of step costs over the next H steps, subject to the dynamics. It gets back a whole optimal sequence. Then it does something that feels wasteful but is exactly right:
Two consequences make MPC the workhorse of modern robotics.
It is implicitly closed-loop. Because the first action depends on the freshly-measured state xt, MPC is feedback control even though each inner solve is "open-loop planning." A gust of wind shoves the robot; next step it re-measures, sees the new state, and the fresh plan pushes back. We solve open-loop look-aheads, but the replanning loop makes the overall behavior react. That is the whole reason we throw the plan away — the rest of it was computed from a state we are no longer in.
The terminal cost matters enormously. A short horizon H is cheap, but it is short-sighted — it can't see past the window's edge. So MPC tacks a terminal cost V(xt+H) onto the end of the window: an estimate of "how much more it'll cost from wherever you end up." That terminal cost is a value function (Lecture 7's V), and it can come from heuristics, from offline data, or from a learned value network. A good terminal cost lets you shrink H dramatically — you don't need to plan far if you have a decent estimate of the future at the horizon's edge.
A cart must reach the target. The open-loop controller plans once at t=0 and executes the whole plan blindly. The MPC controller replans every step from where it actually is. Crank the disturbance and watch open-loop drift while MPC re-aims.
Inside the MPC window we need to solve a planning problem we cannot differentiate. The simplest possible idea is almost embarrassing, and yet it is the foundation everything else refines.
Random shooting: draw N action sequences completely at random, roll each one through the model, total up its cost, and keep the single cheapest one. That's it. Execute the first action of the winner, then (in MPC) throw it away and redraw next step.
Let's make the data flow concrete, because this is the template for CEM and MPPI too.
The appeal is total generality. The model f can be a neural network, a contact-rich simulator, a piecewise-defined mess — the planner never looks inside it. It only calls "roll out and tell me the cost." Non-differentiable cost? Fine. Discrete actions? Fine. And every one of those N rollouts is independent, so you can run them in parallel on a GPU, evaluating thousands of plans at once.
The weakness is just as plain. Random shooting throws darts blindly. If the good region of action-space is a thin sliver — a narrow gap between two obstacles, say — you'll almost never hit it by chance, and pumping up N pays off slowly. You're wasting the vast majority of rollouts on hopeless plans, and you learn nothing from one round to the next: every redraw starts from the same blind distribution.
Below, the lab pits random shooting against pure random guessing on a 1-D control problem: pick an action that drives a noisy system to a target. Your job is the one line that makes "shooting" smarter than "guess once" — selecting the best of many rollouts.
The Cross-Entropy Method (CEM) is random shooting with a memory. Instead of sampling from a fixed blind distribution forever, CEM keeps a Gaussian sampling distribution over action sequences — a mean μ (the current best guess for the plan) and a covariance Σ (how much it's still exploring) — and tightens it round after round.
Here is the whole algorithm. It fits in one breath:
Read step 4 slowly, because it is the heart of CEM. We do not move μ toward all the samples — only toward the elites, the cheapest K. We literally throw away everything but the top performers and pretend they are our new training data for the distribution. The mean slides toward where the good plans clustered; the variance shrinks because the elites are, by construction, close to each other.
Why does this converge to a good plan? Each round, the elite set is a slightly better-than-average slice of the current cloud. Refitting to it nudges the whole distribution into that better region. Next round's samples are drawn from there, so the new elites are better still. The cloud chases its own best tail downhill, and the variance shrinks as the elites bunch up — until Σ is tiny and μ is your plan.
The price of this elegance: CEM is greedy. By tightening only around the elites it can collapse onto a local optimum and never discover a far-off better region — the same risk the gradient methods of Part 1 face. The cure is to keep N large, K not too small, and to inflate Σ a little each round (or floor it) so the cloud doesn't strangle itself before it has explored.
Each candidate is a 2-D "plan parameter" (think: aim point). The cloud is the current Gaussian's samples; elites are the K cheapest (closest to the goal); the ellipse is N(μ, Σ). Press Iterate and watch μ slide to the goal while Σ shrinks.
Slide the elite fraction up to 0.5 (keep half the samples) and the cloud barely tightens — you're averaging in mediocre plans. Slide it down to 0.05 (keep just a couple) and it tightens fast but risks collapsing onto a fluke. That tension — tighten fast vs. stay safe — is the one knob CEM really has.
Algorithms only become yours when you push real numbers through them. Let's do exactly one CEM iteration with a pencil, in 1-D, so you can see the mean move and the variance shrink with your own eyes.
Setup. We're searching for a single scalar control u. The cost is C(u) = (u − 3)2, so the true optimum is u = 3 with cost 0. We don't know that — we only get to evaluate C. Start with a wide Gaussian: μ = 0, σ = 2 (so σ² = 4). We'll sample N = 6 candidates and keep the K = 3 cheapest as elites.
Step 1 — sample. Suppose our 6 draws from N(0, 4) come out (rounded) as:
Step 2 — score. Plug each into C(u) = (u − 3)2:
| u | −1.0 | 0.5 | 1.5 | 2.5 | 3.5 | 4.5 |
|---|---|---|---|---|---|---|
| C(u)=(u−3)² | 16.0 | 6.25 | 2.25 | 0.25 | 0.25 | 2.25 |
Step 3 — select elites. The K = 3 cheapest costs are 0.25, 0.25, and 2.25. Two ways to tie-break give the same lesson; take the three lowest: u = 2.5 (cost 0.25), u = 3.5 (cost 0.25), and u = 1.5 (cost 2.25). The elite set is:
Step 4 — refit. New mean is the average of the elites:
New variance is the (population) variance of the elites about that new mean. The deviations are (1.5 − 2.5, 2.5 − 2.5, 3.5 − 2.5) = (−1, 0, +1), so:
Now we'll do the same thing in code — but this time you write the refit. The lab samples, scores, and selects the elites for you; you supply the one step that is CEM: recompute μ and Σ from the elite set, and verify the mean moved toward the optimum while the variance shrank.
CEM makes a hard cut: a sample is either elite (counts fully) or not (counts zero). MPPI — Model Predictive Path Integral control — replaces that hard cut with a soft one. Instead of throwing away the non-elites, MPPI gives every sample a weight and takes a weighted average. Cheap plans get heavy weight; expensive plans get nearly zero. Nothing is discarded; everything votes, but the good ones vote louder.
The weighting is an exponential of the negative cost. For each sampled sequence with cost C(i), its weight is:
Read it piece by piece. The lower the cost, the bigger exp(−C/λ), so cheap plans get more weight. The denominator just normalizes the weights to sum to 1 (it's a softmax over negative costs). And λ (lambda) is the temperature — the one knob that controls how sharply MPPI prefers the best plans:
The new control sequence is just the weighted average:
That's the whole update. Sample N sequences from N(μ, Σ), roll them out, weight by exp(−C/λ), average. Like CEM it's an MPC inner loop: do this each step, execute the first action, shift the mean by one for warm-starting, replan.
Why is MPPI everywhere in real-time robotics? Because the soft average is smooth and the whole thing parallelizes brutally well. The original paper runs MPPI with a neural-network dynamics model for aggressive off-road driving; on the deck, the instructor notes a GPU implementation hitting 8192 samples, a 40-step horizon, at ~80 Hz on a laptop GPU. Thousands of full rollouts, eighty times a second. That throughput is why sampling-based MPC went from "the dumb baseline" to the method flying drones and racing cars.
N sampled controls (bars), each shaded by its weight w = exp(−cost/λ). The warm marker is the weighted-average control μ; the teal curve is the cost. Drag λ: low temperature concentrates weight on the cheapest plan; high temperature flattens it toward a plain average.
Concretely the weighted average pulls toward the cheap plans: with mostly-far samples around the optimum at u = 3, an exponential weighting yields a control near 2–3, while a plain unweighted mean of the same samples sits down near 0. The exponential of the negative cost is what does the work — it is a softmax over the rollout costs, and the temperature λ sets how sharply that softmax peaks on the cheapest plan. (You built exactly this softmax in the Lecture 7 spirit of "score, then weight by score.")
Everything so far assumed the model f was given — a simulator or known dynamics we could roll out. The whole point of robot learning is that often we don't have it. So we learn the dynamics from data: collect transitions (state, action, next-state) by running the robot, then fit a model fθ to predict the next state. Now we can plan against the learned model with all the tools above. This is model-based reinforcement learning (MBRL).
The promise is enormous: sample efficiency. A learned model lets you "imagine" thousands of rollouts in your head without touching the real, slow, fragile robot — the firehose-of-data problem from Lecture 1, attacked head-on. PILCO learns a cart-pole from scratch in a handful of trials; PETS matches model-free methods with eight-to-a-hundred times less real-world data. When every real episode costs seconds and risks hardware, that efficiency is the whole game.
But a learned model is a liar, and the planner is a relentless exploiter of lies. Here is the failure that haunts all of MBRL:
Why does the model lie precisely where the planner looks? Because the planner pushes toward regions of high reward, which are often regions it has never visited — exactly where the model has no data and its predictions are arbitrary. PILCO's authors draw the picture sharply: given a handful of observed transitions, many different functions could have produced them. A model that commits to one specific function makes confident predictions far from the data — and those predictions are essentially arbitrary, yet asserted with full confidence. That overconfidence is the trap.
The true dynamics (dashed) are known only at the training points. A single model draws one confident curve everywhere. An ensemble of models agrees near data and fans out where data is missing (the shaded band). Toggle between them and watch where the planner's "best" point lands — the single model invites exploitation in the data desert.
The single model's "best" point sits out in the data desert, confident and wrong — the planner would happily chase it. The ensemble's disagreement there warns the planner off: if your models can't agree, you have no business trusting any of them. That single idea — represent what you don't know, and let the planner respect it — is what separates the three methods we'll meet next. PILCO uses a Gaussian process to put error bars everywhere. PETS uses an ensemble of networks. MBPO keeps its imagined rollouts short so the model never has time to lie too far.
PETS draws a distinction worth holding onto, because it tells you which uncertainty an ensemble fixes:
| Uncertainty | What it is | Does more data kill it? |
|---|---|---|
| Aleatoric | Inherent randomness of the system — sensor noise, process noise. The world is genuinely stochastic. | No — it's irreducible. Capture it by predicting a distribution (mean + variance), not a point. |
| Epistemic | Your own ignorance — you just haven't seen enough data to pin down the dynamics here. | Yes — it vanishes with infinite data. This is what an ensemble's disagreement measures, and what model exploitation feeds on. |
PILCO (Probabilistic Inference for Learning COntrol, Deisenroth & Rasmussen 2011) was the breakthrough that made "learn from scratch in a handful of trials" real. Its recipe is the purest answer to model exploitation: never let the model be overconfident in the first place.
PILCO has three deliberate choices, each aimed at model bias.
1. The dynamics model is a Gaussian process (GP). A GP is non-parametric and Bayesian: instead of fitting one curve, it places a distribution over functions consistent with the data. Near observed transitions it is confident (tight error bars); far from them it widens out (huge error bars). It cannot be confidently wrong in the data desert because it explicitly says "I don't know here." This is exactly the picture from Chapter 6 — uncertainty that grows away from data, built in.
2. Policy evaluation is done in closed form. This is the surprising part. PILCO doesn't Monte-Carlo a thousand rollouts. It propagates the uncertainty analytically: starting from a Gaussian over the current state, it pushes that distribution one step forward through the GP, approximates the (non-Gaussian) result as a Gaussian again ("moment matching"), and repeats. The output is a closed-form predicted cost-to-go for the whole horizon, with the model's uncertainty folded in. Plans that pass through uncertain regions automatically incur uncertain (and thus penalized) cost — the GP's honesty propagates into the plan's score.
3. Policy improvement uses analytic policy gradients. Because the predicted cost is a closed-form, differentiable function of the policy parameters, PILCO can compute the exact gradient of long-term cost with respect to the policy and do gradient descent on it. No sampling-based policy search, no high-variance estimates — an analytic gradient straight down the cost surface.
The catch. Gaussian processes are gorgeous but they scale poorly — their cost grows roughly with the cube of the number of data points, and the squared-exponential kernel assumes smooth dynamics. That smoothness assumption breaks on the discontinuous, contact-rich dynamics of real robots (a foot hitting the ground is not smooth). PETS, next, keeps PILCO's obsession with uncertainty but swaps the GP for neural networks that scale to big data and rough dynamics.
PETS (Probabilistic Ensembles with Trajectory Sampling, Chua et al. 2018) scales PILCO's uncertainty discipline to deep networks and contact-rich dynamics. The name is the algorithm: a probabilistic ensemble for the model, plus trajectory sampling to plan with it. Two pieces, each capturing one flavor of uncertainty from Chapter 6.
Each model in the ensemble is a probabilistic neural network: it does not output a single next state, it outputs a distribution — a mean and a variance for the next state. That variance captures aleatoric uncertainty (the world's inherent noise). The network is trained to maximize the likelihood of the observed transitions, i.e. to predict both where the next state lands and how noisy that landing is.
Then PETS trains several such networks (the paper uses B = 5), each on a bootstrap of the data — a resampled copy. Where the data is plentiful, all five learn the same thing and agree. Where data is scarce, each extrapolates differently and they disagree. That disagreement across the ensemble is the epistemic uncertainty — the "I haven't seen enough here" signal. So a single ensemble captures both flavors at once: each member's predicted variance is aleatoric; the spread between members is epistemic.
How do you turn an ensemble into a single cost for the CEM planner to minimize? You can't just average the means — that throws away the disagreement. PETS instead does trajectory sampling: launch a population of "particles" from the current state, and propagate each particle forward by sampling. At each step a particle picks one ensemble member and samples a next state from that member's predicted distribution. Over the horizon, particles that wander into uncertain regions scatter (because the members disagree there); particles in well-known regions stay tight. The cost of an action sequence is the average cost over all particles — so uncertainty inflates the cost exactly where the model is unsure.
Wrap it in MPC: at each real step, run CEM (Chapter 3) over action sequences, scoring each by trajectory sampling through the probabilistic ensemble, execute the first action, replan. The result matches model-free methods like Soft Actor-Critic and PPO on hard benchmarks while using 8× to 125× fewer real-world samples.
Let's quantify the key signal: does ensemble disagreement actually grow as you leave the training data? The lab fits a tiny ensemble of linear models to data on one interval and measures their disagreement (variance of predictions) as you move away. You compute the disagreement; the check confirms it explodes in the data desert.
PILCO and PETS plan with the model at every step (sampling-based MPC). MBPO (Model-Based Policy Optimization, Janner et al. 2019) does something different: it uses the learned model to generate extra training data for a model-free RL algorithm. The model is a data factory, not a planner. And it confronts the model-error problem with a beautifully simple insight.
That is the branched rollout. Picture the robot's real trajectory as a trunk. At many points along that trunk — real, visited states — MBPO branches off a short (k-step, often just 1) imagined rollout under the learned model and the current policy. Because the branch starts from a real state and runs only a few steps, the model never has time to drift far. These short branches generate a flood of cheap, mostly-accurate synthetic transitions.
The payoff is that the policy can take 20–40 gradient updates per single real environment step — far more than is stable for a model-free method on real data alone, because the model manufactures the extra transitions. MBPO surpasses prior model-based methods' sample efficiency, matches the best model-free methods' final performance, and — crucially — scales to long-horizon tasks that make other model-based methods fail entirely, precisely because it never asks the model for a long prediction.
Two design choices keep MBPO honest, and both are familiar now:
You now own the second half of optimal control: how to plan and learn when you can't write down the dynamics, only sample them. Everything in this lecture hangs on the spine from Chapter 0 — sample, roll out, score, update, replan — and on the one danger that appears the moment the model is learned: model exploitation, which uncertainty defeats.
| Method | How it uses the scores | One-line idea |
|---|---|---|
| Random shooting | Keep the single argmin | Throw N darts, keep the best. Blind, but trivially parallel. |
| CEM | Hard cut: top-K elites | Refit a Gaussian to the cheapest K; tighten round by round. |
| MPPI | Soft cut: exp(−cost/λ) weights | Weighted vote of all samples; temperature sets greediness. ~80 Hz on a GPU. |
| Method | Model | How the model is used | Uncertainty trick |
|---|---|---|---|
| PILCO | Gaussian process | Closed-form planning + analytic policy gradient | Error bars everywhere; smooth, low-data, doesn't scale |
| PETS | Probabilistic ensemble (NNs) | Sampling-based MPC (CEM + trajectory sampling) | Ensemble disagreement = epistemic; per-model variance = aleatoric |
| MBPO | Probabilistic ensemble (NNs) | Generate short branched rollouts to train a model-free policy | Short rollouts cap error; ensemble blocks exploitation |
This lesson is Part 2 of the optimal-control pair and the gateway to model-based RL. Continue along the 16-831 spine and dig deeper with the companion Gleams:
"When you can't differentiate the world, you negotiate with it — one sampled plan at a time."