You know the physics. Now plan the entire sequence of controls that minimizes total cost — like throwing a ball to a target in one shot. We derive LQR's backward recursion by hand, then watch iLQR, DDP, and convex programming bend a nonlinear trajectory until it obeys the dynamics and hits the goal.
You are standing at the free-throw line. To sink the basket you don't sense-decide-correct your way there mid-flight — you can't, the ball has left your hand. Instead you commit, before release, to one motion: an angle, a speed, a spin. You plan the whole control up front so that the laws of physics carry the ball to the hoop.
That is the flavor of problem in this lecture. Up to now (Lecture 7) we asked "what is the best action from each state?" — a feedback policy. Today we ask the open-loop cousin: what is the best sequence of controls over time, start to finish, that drives the system to the goal at the smallest cost?
Why "open-loop"? Because the plan is computed once, before you act, assuming the world behaves exactly as your model says. The basketball player's release is open-loop: no corrections after release. Contrast that with the closed-loop feedback policies of Lecture 1 — we'll tie the two together in Chapter 9 (and the next lecture's MPC will re-plan continuously, getting feedback back for free).
The reason this is even tractable is the same reason Lecture 7's gridworld was tractable: cost-to-go. If you know how expensive the rest of the journey will be from any future point, you can pick this step's control by trading off "cost now" against "cost later." Dynamic programming, run backward in time, computes exactly that — and when the problem is linear-quadratic, it has a clean closed-form answer. Let's watch a path get optimized before we write a symbol.
A point mass starts at the left and must reach the target. Press Optimize and watch the planned trajectory iteratively bend: it cannot teleport (the dynamics constrain how fast it turns), and it pays for control effort, so it finds the cheapest physical path. Crank effort cost up and the path goes lazy and straight; down and it whips aggressively to the goal.
Two things to notice. First, the path is not a straight line teleport — the dynamics (the mass has momentum) dictate a curved, physically realizable trajectory. Second, the optimizer trades two costs against each other: get to the goal (reach cost) versus don't burn fuel (effort cost). Every method in this lecture is a different way to solve that trade-off.
Let's give the basketball intuition precise symbols, because every algorithm today is a way of attacking this one optimization. Don't be intimidated — it is four lines and we'll decode each.
Read it slowly:
The instructor draws the fork explicitly:
This lecture assumes f is known. That is the defining assumption of classical optimal control. The next lecture drops it: model-based RL is basically optimal control with an unknown model — you learn f from data, then run today's machinery on it.
Consider driving a mass from (0,0) to (10,0) while avoiding a red obstacle, minimizing control energy. With a double integrator (position-velocity-acceleration, a perfectly linear model) the dynamics constraint is linear — but the obstacle makes the feasible set nonconvex (you must go left OR right around it, and "left or right" is a non-convex choice). With a unicycle (a car that can only drive forward and turn), the dynamics themselves are nonlinear, so the problem is "more" nonconvex. Same cost, same obstacle, wildly different difficulty — dynamics matter a lot.
Before we solve anything, we have to decide what the optimization variables are. There are two classic choices, and the distinction shapes every solver. This is the "Concept + Realization" heart of the lecture: how do you actually represent a trajectory to an optimizer?
In single shooting, the only free variables are the controls u1:T. The states are not variables — you get them by simulating forward: start at x1, apply u1 through f to get x2, apply u2 to get x3, and so on. The states are a deterministic function of the controls, so the dynamics are satisfied automatically, by construction.
The name is from artillery: you pick a firing angle (the controls), shoot, see where the cannonball lands, and adjust. It is simple — the cost is just a function of u, with no equality constraints to enforce. But it has a flaw: a small change in an early control snowballs through the whole rollout (exactly the compounding/sensitivity you met in Lecture 1), so the optimization landscape can be extremely ill-conditioned for long horizons.
In direct collocation, both the states x1:T and the controls u1:T are free variables. But now the dynamics are no longer automatic — you must enforce them as explicit defect constraints:
The "defect" is how badly a candidate trajectory violates physics at step t. The optimizer is free to propose any states it likes, even physically impossible ones mid-iteration, as long as it drives every defect to zero by the end. Picture it as a relay of batons: each segment can be sketched independently, and the constraints demand the baton actually be handed off (the end of segment t must equal the start of segment t+1 under f).
Toggle the mode. In shooting, you nudge the controls and the whole state path is re-simulated forward — physics is always satisfied, but one early nudge swings the far end wildly. In collocation, the states are free knots joined by defect gaps that the optimizer must close; drag the “optimizer progress” slider to watch the defects shrink to zero.
For the rest of the lecture we'll mostly use the shooting view, because it makes the dynamic-programming derivation of LQR clean. But keep collocation in your pocket: the constraint-handling methods (SCP/SQP in Chapter 8) lean on it.
Let's make single shooting concrete: write the cost as a function of a control sequence, then improve that sequence. The simplest improver needs no derivatives at all — just sample, evaluate, and keep the best (the cross-entropy method). You wire up the distribution update.
The general problem is hard. But there is a golden special case where the answer is a clean formula, no iteration needed — and it is the building block of everything that follows. It is the Linear Quadratic Regulator (LQR).
LQR is what you get when you make two assumptions:
Why is this worth a whole chapter? Because of a beautiful fact you already met in Lecture 7: the cost-to-go — the cheapest total cost achievable from a given state to the end — turns out to be also quadratic in the state. Guess that the optimal cost-to-go (value function) has the form:
for some matrix Pt. Pt is the "cost-to-go matrix": a bigger P means "being in this state now is expensive, because of all the cost you'll pay getting home." If we can find Pt for every t, we'll have solved the problem — and the controls fall out for free.
Dynamic programming runs backward from t = T. At the final step there is no future, so the cost-to-go is just the final-step cost: VT(xT) = ½ xTTQTxT. Matching to our guess ½ xTTPTxT gives the boundary condition:
That's the seed. Now we'll propagate it backward, one step at a time, with the Bellman recursion. Each backward step gives us Pt from Pt+1 — and a feedback gain Kt for that step. By the time we reach t = 1 we have the whole solution.
This is the technical heart of the lecture. We'll derive the LQR backward recursion (the Riccati equation) from scratch — no step skipped. Have a pen ready; doing this once is worth ten readings.
The Bellman principle says: the cost-to-go at step t equals the current step's cost plus the cost-to-go at the next state, minimized over the control we pick now:
The last term is the future value evaluated at where this control lands us, xt+1 = Atxt + Btu. Now substitute the quadratic form Vt+1(x) = ½ xTPt+1x and expand the (Atxt + Btu)TPt+1(Atxt + Btu) term:
This is a clean quadratic in u: a bowl. To minimize, take the derivative with respect to u and set it to zero. The gradient is (Rt + BtTPt+1Bt)u + BtTPt+1Atxt = 0. Solve for u:
There it is — the optimal control is linear in the state, u* = −Ktxt, with the feedback gain:
Decode Kt: the term (Rt + BtTPt+1Bt) — call it St — is the "cost of control" (your effort penalty R plus how much control jostles the future via BTPt+1B). The numerator BtTPt+1At is "how much pushing now reduces future cost." So Kt is a trust ratio: how aggressively to push, balancing future savings against present effort — the same trust-slider flavor as the Kalman gain.
Substitute u* = −Ktxt into the expanded value function. After the algebra, everything collects into a quadratic in xt again — confirming our guess — with the new matrix:
This is the discrete-time Riccati equation. Read it as three pieces: Qt (cost you pay now) + AtTPt+1At (future cost if you did nothing) − the big subtracted term (how much you save by applying the optimal control). The subtraction is exactly KtTStKt, so a compact equivalent is Pt = Qt + AtTPt+1At − KtTStKt.
Stochastic noise doesn't change the gains. Add zero-mean i.i.d. noise wt to the dynamics (xt+1 = Atxt + Btut + wt). The optimal Kt is identical; only an additive cost term qt = qt+1 + ½Tr(W Pt+1) appears, tracking the unavoidable cost of the noise. This is the celebrated certainty equivalence: plan as if there were no noise, and you're still optimal.
Complexity scales gracefully. The backward pass costs grow cubically with the state+control dimension (because of the matrix inverse) but only linearly with the horizon T — one cheap matrix update per step. Compare a generic QP solver, whose cost grows cubically with T. This linear-in-horizon scaling is the "power of DP" the instructor emphasizes, and it's why iLQR (Chapter 6) reuses the Riccati machinery.
Time to build the backward pass yourself.
Formulas are slippery until you push real numbers through them. Let's run a complete finite-horizon LQR backward pass by hand on the smallest interesting example, and confirm the answer two ways.
Take a scalar system — one-dimensional state, one-dimensional control — so every matrix is just a number:
Boundary. P3 = Q3 = 1. The cost-to-go at the last step is just the last cost.
Step t = 2. Use P3 = 1:
Step t = 1. Use P2 = 1.5:
The backward pass is done. The gains are K1 = 0.6, K2 = 0.5, and P1 = 1.6. Notice the gains are different at each step — LQR gives a time-varying controller. The last step pushes gently (K2 = 0.5) because there's little future left to protect; earlier steps push harder (K1 = 0.6) because mistakes now cost over the whole remaining horizon.
Start at x1 = 2. Apply u1 = −K1x1 = −0.6·2 = −1.2, landing at x2 = 2 − 1.2 = 0.8. Apply u2 = −0.5·0.8 = −0.4, landing at x3 = 0.8 − 0.4 = 0.4. The total cost is
And the value-function shortcut: V1(x1) = ½P1x12 = ½(1.6)(4) = 3.2. The two roads meet. The cost-to-go matrix really did fold the whole future into one number.
The scalar example above, but you can change the horizon and the effort penalty R. The bars are Pt at each step (filled backward from the right); the line is the gain Kt. With a long horizon, P and K converge to a steady-state value away from the boundary — that's the infinite-horizon LQR (the algebraic Riccati solution).
LQR is exact — but only for linear dynamics and quadratic cost. Real robots are nonlinear (a pendulum's dynamics have a sine; a car can only drive forward). So how do we use this beautiful machinery on a nonlinear problem?
The answer is the single most important idea in nonlinear trajectory optimization, and it's a recipe you can say in one breath: around your current trajectory guess, linearize the dynamics and quadratize the cost — turning the local problem into an LQR — solve that LQR, use its controls to get a better trajectory, and repeat. This is iterative LQR (iLQR).
The two passes are not the same. The backward pass uses the linearized approximation to compute gains cheaply (one Riccati sweep). The forward pass applies those gains to the true nonlinear dynamics — so even though the gains came from an approximation, the trajectory we commit to is genuinely physical. That split is why iLQR is fast and robust.
A subtle but crucial point the instructor stresses: iLQR linearizes around the entire current trajectory, a different (At, Bt) at every step — not around a single fixed equilibrium point. Linearizing once around an equilibrium gives you a controller that's only valid when you're near that point; linearizing around the trajectory tracks the system through big swings (a pendulum going all the way up and over). The linearization moves with the plan.
You could, instead, treat the control sequence as a flat vector and run plain gradient descent on the shooting cost. It works — but badly. Two reasons iLQR wins:
A nonlinear 1D system (a state with a sine-shaped drift) must reach a target. Press Iterate to run one iLQR step: linearize around the current trajectory (gray), solve LQR, forward-roll the new one (warm). Watch the cost plummet in the first couple of iterations — the signature of a second-order method — then flatten as it converges.
Now you implement the core of an iLQR iteration: the backward LQR gains that bend a nominal trajectory toward the target.
Why does iLQR converge so fast? Because under the hood it is approximating Newton's method, the gold standard of fast optimization. Let's make that connection explicit, then meet iLQR's more powerful sibling, DDP.
To minimize a function h(x), Newton's method uses both the slope (gradient g) and the curvature (Hessian H) at the current point. It replaces h with its local quadratic model and jumps to that model's minimum:
Plain gradient descent is the special case H = I/η (it pretends curvature is the identity, scaled by the learning rate η). Using the true curvature is what gives Newton its famous quadratic convergence — few iterations, each one a big, well-aimed step.
Eliminate the states by substituting the dynamics repeatedly (single shooting): the total cost becomes a function of the controls alone,
Each cost term is a deeper and deeper nesting of f. iLQR is an approximation of Newton's method applied to this nested objective — the Riccati backward pass is a structure-exploiting way to assemble and invert the Hessian of this whole thing in one O(T) sweep, instead of forming a giant dense matrix.
iLQR linearizes f (keeps only At, Bt — the first derivatives). To be a full Newton's method, you'd also need the second derivatives of the dynamics — how f itself curves. Adding that term gives Differential Dynamic Programming (DDP):
That last term — the Hessian of the dynamics — is what iLQR drops and DDP keeps. DDP is the true second-order method; iLQR is its cheaper first-order cousin. In practice iLQR is often preferred anyway: the dynamics Hessian is expensive (and sometimes unstable) to compute, and iLQR's convergence is already excellent.
iLQR and DDP are wonderful but share a blind spot: they don't naturally handle constraints — obstacles to avoid (state constraints) or torque limits (control constraints). When constraints matter, the workhorse is Sequential Convex Programming (SCP), and its close relative Sequential Quadratic Programming (SQP).
The idea rhymes with iLQR — approximate the hard problem by an easy one around your current guess, solve, repeat — but the easy sub-problem is a constrained convex program (a QP) instead of an unconstrained LQR.
The affine and quadratic approximations are only accurate near the current guess. If the QP were allowed to jump far away, it might land in a region where the approximation is garbage — possibly worse than where it started, or even infeasible. The trust region ‖x − x(i)‖ ≤ ε is a leash: "improve, but don't wander past where I can still trust my local model." It is the same instinct as iLQR's line search and Newton's method's damping.
When the problem is already convex — in particular a quadratic program (quadratic cost, linear/affine constraints) — it is solved directly and efficiently (solvers like OSQP, Gurobi). The catch: QP complexity grows cubically with the horizon T or control dimension. (Contrast the DP-based iLQR, which is only linear in T — that's exactly why iLQR is attractive when there are no hard constraints.) The QP is the basic building block on which the nonconvex SCP/SQP iterations are built.
A trajectory from start to goal must avoid the red obstacle (a nonconvex constraint). Press SCP step: each iteration convexifies around the current path and re-solves, so the path is pushed out of the obstacle while staying as short as possible. The dashed circle is the trust region limiting each step's movement.
Be honest about what SCP/SQP guarantees: nothing global. It is a local optimization method for a nonconvex problem. The instructor is blunt:
You now own the classical half of optimal control. Step back and see the single skeleton underneath everything you learned.
| Method | Handles | Sub-problem solved each step | Cost in horizon T |
|---|---|---|---|
| LQR | Linear dyn, quadratic cost, no constraints | none — one closed-form backward pass | linear |
| iLQR | Nonlinear dyn, no hard constraints | unconstrained LQR (uses ∇f) | linear |
| DDP | Nonlinear dyn, no hard constraints | unconstrained LQR (uses ∇f and ∇²f) | linear |
| SCP / SQP | Nonlinear dyn + state/control constraints | convex QP + trust region | cubic (per QP) |
This is Part 1 of the optimal-control lecture — the classical, known-model half. The threads continue here:
"Plan as if the world will obey your model — then re-plan, because it never quite does."