Lecture 10 · Part 3

Optimal Control and Planning

The course shifts gears from model-free RL to using models — and before models can be learned, you need to know what to do with one. Levine covers planning with known dynamics and no learning at all: black-box optimizers like random shooting and CEM, Monte Carlo tree search for stochastic discrete problems, and derivative-based trajectory optimization via LQR, extended to stochastic and nonlinear systems as iLQR/DDP and deployed inside model predictive control.

▶ Lecture videos (5 parts)

What changes when you know the dynamics

The first nine lectures were model-free: the algorithms only ever sampled from $p(s_{t+1} \mid s_t, a_t)$ , never knew the probabilities, and never asked what would have happened under a different action — Q-learning was explicitly engineered to dodge that question. This lecture asks the opposite: what if the transition probabilities (“transition dynamics”, “dynamics”, “the model” — all names for $p(s_{t+1} \mid s_t, a_t)$ ) are known?

Often they are. Atari, chess, and Go have rules programmed or written in a rulebook. Some systems are easy to model by hand — a car’s physics on a dark slippery road is hard, but its kinematics on a clean road without slippage is a few equations of motion that serve well in practice. Simulators technically come with their dynamics. And unknown dynamics can often be learned: system identification fits unknown parameters (masses, motor torques) into a known model scaffold, and fitting general-purpose models to transition data is where the model-based RL lectures are headed.

With no policy in the picture, the objective is over actions directly, and the dependence of future states on past actions enters as a constraint:

$\min_{a_1, \ldots, a_T} \sum_{t=1}^{T} c(s_t, a_t) \quad \text{s.t.} \quad s_{t+1} = f(s_t, a_t)$

Open loop, closed loop, and the math exam

In the stochastic case the natural generalization is to condition a state distribution on the action sequence, $p(s_{1:T} \mid a_{1:T}) = p(s_1) \prod_t p(s_{t+1} \mid s_t, a_t)$ (no policy term — the actions are given), and choose $a_{1:T}$ maximizing the expected reward. Reasonable — and, Levine claims, sometimes a very bad idea.

Closed-loop planning means responding with a policy $\pi(a_t \mid s_t)$ , and the objective becomes exactly the RL objective — but the policy class need not be a neural network. A neural net is a global policy; if you’ll stay near a planned trajectory — a rocket perturbed by wind, corrected quickly — a local policy suffices, such as time-varying linear feedback that pushes back proportionally to the deviation. That form is much more common in optimal control, and LQR will hand us exactly it.

Black-box planning: guess-and-check and CEM

The first family of open-loop planners makes minimal assumptions — dynamics can be discrete or continuous, stochastic or deterministic, non-differentiable. These stochastic optimization or black-box methods abstract the temporal structure away entirely: concatenate the action sequence into one variable $A = (a_1, \ldots, a_T)$ and maximize some $J(A)$ .

The simplest version is guess and check, a.k.a. random shooting: sample $A_1, \ldots, A_N$ from some distribution (even uniform) and pick $\arg\max_i J(A_i)$ . It sounds silly but works well for low-dimensional systems and short horizons, takes minutes to implement, and is extremely GPU-friendly: the $N$ candidates are a mini-batch through a (later, neural-network) model, and the argmax is a max reduction. The disadvantage is equally plain — you are relying on getting lucky.

The cross-entropy method (CEM) keeps the benefits and samples smarter, iteratively:

p = initial_distribution()          # e.g. uniform / broad Gaussian over A
repeat:
    A_1..A_N ~ p                    # sample action sequences
    evaluate J(A_1) .. J(A_N)       # rollouts through the model, in parallel
    elites = top M of N by J        # e.g. the best 10%
    p = fit(elites)                 # max-likelihood refit, e.g. a Gaussian

Each refit focuses sampling on the region where the good sequences lie. With a large enough initial distribution and enough samples, CEM in general finds the global optimum (though “enough” may be prohibitive); it needs no derivatives, extends to discrete actions via other distribution classes, and CMA-ES adds momentum-style terms for better solutions at smaller population sizes. The hard limit is dimensionality: as a rule of thumb these methods struggle beyond roughly 30–60 dimensions — about 10 action dimensions over 15 time steps, stretched somewhat by correlation between successive steps — and they only ever produce open-loop plans.

Monte Carlo tree search

Discrete, stochastic problems — board games, Atari, poker, games of chance generally — call for a planner that does account for closed-loop feedback. Full tree search finds the optimal action but needs expansions exponential in the horizon $T$ . MCTS approximates a node’s value without expanding the tree below it: expand to some small depth, then run a cheap default policy — even a random one — and take the return of that rollout as a sample-based value estimate.

The generic sketch: (1) find a leaf $s_l$ using the tree policy — not a policy run in the world but a strategy for picking which node to expand; (2) evaluate the leaf with the default policy, re-executing the whole action sequence from the root (the same actions can land in different states, and you want values in expectation); (3) propagate the value and visit count up to the root. Repeat until the compute budget runs out, take the root action with the best average value — and typically replan from scratch at the next step. The standard tree policy is UCT: if a node isn’t fully expanded, expand a new action; otherwise recurse into the child with the best score,

$\text{Score}(s_t) = \frac{Q(s_t)}{N(s_t)} + 2C\sqrt{\frac{2 \ln N(s_{t-1})}{N(s_t)}}$

— average value plus a bonus for rarely visited children: choose the nodes with the best return, but prefer the ones you know least about.

Worked example — Three expansions of a two-action tree

Take $a_1 = 0$ : rollout return 10, so that child holds $Q = 10, N = 1$ . Take $a_1 = 1$ (unexpanded nodes must be tried): return 12, so $Q = 12, N = 1$ . Any reasonable score prefers the right child, so expand a new action under it, get a rollout of 10, and propagate: the leaf holds $Q = 10, N = 1$ and its parent updates to $Q = 22, N = 2$ . Now the root’s children score $10/1$ plus a bonus with denominator 1 versus $22/2 = 11$ plus a bonus with denominator 2 — the left child’s average is lower but its bonus is bigger, so for large enough $C$ you explore left next. These values are noisy samples, not truth: the system is stochastic, and re-taking $a_1 = 0$ might not return 10 again.

MCTS methods are surprisingly hard to analyze — few guarantees — but work very well in practice; Levine recommends the survey “A Survey of Monte Carlo Tree Search Methods.” Learn the default policy, evaluate leaves with value functions, take it to the extreme, and you get essentially what AlphaGo did.

Trajectory optimization with derivatives: LQR

When the dynamics are differentiable, use the derivatives. Notation switches to the optimal control convention — states $x_t$ , actions $u_t$ , costs $c$ instead of rewards. Substituting the constraint into the objective gives an unconstrained problem in the actions alone,

$\min_{u_1, \ldots, u_T} c(x_1, u_1) + c(f(x_1, u_1), u_2) + \cdots + c(f(f(\cdots)\cdots), u_T)$

which you could attack with backpropagation using $df/dx_t$ , $df/du_t$ , $dc/dx_t$ , $dc/du_t$ . In practice first-order gradient descent works very poorly here: the last term multiplies many Jacobians together, so gradients vanish or explode, and the first action affects everything downstream while the last affects almost nothing — a huge spread of Hessian eigenvalues, i.e. terrible conditioning. Methods that optimize over actions only are called shooting methods (the first action “shoots” you across state space); collocation methods optimize over states and actions under constraints, condition much better, and suit first-order methods — but are more complex and set aside here. The classic second-order shooting method is the linear quadratic regulator: dynamics linear, cost quadratic (a linear cost has its minimum at infinity, so quadratic is the minimum interesting case), each possibly different per time step:

$f(x_t, u_t) = F_t \begin{bmatrix} x_t \\ u_t \end{bmatrix} + f_t, \qquad c(x_t, u_t) = \frac{1}{2}\begin{bmatrix} x_t \\ u_t \end{bmatrix}^\top C_t \begin{bmatrix} x_t \\ u_t \end{bmatrix} + \begin{bmatrix} x_t \\ u_t \end{bmatrix}^\top c_t$

LQR base case: the last action in closed form

Only the final cost term depends on $u_T$ , so choosing $u_T$ means minimizing a quadratic. Split $C_T$ into blocks $C_{xx}, C_{xu}, C_{ux}, C_{uu}$ (symmetric, so $C_{xu} = C_{ux}^\top$ ) and $c_T$ into $c_x, c_u$ ; setting $\nabla_{u_T} Q(x_T, u_T) = C_{ux}x_T + C_{uu}u_T + c_u = 0$ gives

$u_T = K_T x_T + k_T, \qquad K_T = -C_{uu}^{-1} C_{ux}, \qquad k_T = -C_{uu}^{-1} c_u$

The optimal last action is a linear function of the last state. Substituting it back into $Q$ eliminates $u_T$ and leaves the value function $V(x_T)$ — still quadratic, with terms collected into a matrix $V_T$ and vector $v_T$ . “The actual derivation is very, very simple” — it just takes a long time to write.

The same move recurses backward: at step $T-1$ , $Q(x_{T-1}, u_{T-1}) = c(x_{T-1}, u_{T-1}) + V(f(x_{T-1}, u_{T-1}))$ ; substituting the linear dynamics into the quadratic $V$ yields another quadratic, and the solve is identical in form to the base case with $C, c$ replaced by $Q, q$ .

Code walkthrough — LQR: backward recursion, then forward recursion

Backward pass, for $t = T$ down to $1$ (with $V_{T+1} = 0,\ v_{T+1} = 0$ ):

Q_t = C_t + F_t.T @ V_{t+1} @ F_t            # quadratic term of Q
q_t = c_t + F_t.T @ V_{t+1} @ f_t + F_t.T @ v_{t+1}
K_t = -inv(Q_uu) @ Q_ux                       # blocks of Q_t, q_t
k_t = -inv(Q_uu) @ q_u
# substitute u_t = K_t x_t + k_t into Q to get V_t, v_t; recurse

The Q-function’s quadratic term is the next $V$ “hit on either side by the dynamics matrix,” plus the cost. At $t = 1$ the recursion bottoms out on the one thing we actually know — $x_1$ — so run the forward pass, for $t = 1$ to $T$ :

u_t = K_t @ x_t + k_t
x_{t+1} = f(x_t, u_t)                         # roll the dynamics forward

Unzip backward, expressing every action in terms of its state; zip forward, plugging in states as they materialize. Here $Q$ and $V$ really are the Q-function and value function: total cost-to-go acting optimally from here on.

Stochastic and nonlinear: LQG, iLQR, DDP, and MPC

Gaussian noise costs nothing. If $p(x_{t+1} \mid x_t, u_t) = \mathcal{N}(F_t[x_t; u_t] + f_t,\ \Sigma_t)$ , exactly the same control law is optimal — a Gaussian is symmetric, so left-and-right deviations cancel in the quadratic cost (derivable via the closed form for a quadratic’s expectation under a Gaussian). But the states you visit are now random, so there is no single open-loop sequence — instead $u_t = K_t x_t + k_t$ is a genuine closed-loop policy, a time-varying linear controller, and it is the optimal one in this linear-quadratic-Gaussian (LQG) setting. LQR quietly produces closed-loop plans.

Nonlinear systems: iterate. Approximate the system as linear-quadratic locally by Taylor expansion around the current best trajectory $(\hat{x}_t, \hat{u}_t)$ — first order for the dynamics, second order for the cost — in the deviation variables $\delta x_t = x_t - \hat{x}_t$ , $\delta u_t = u_t - \hat{u}_t$ . Run LQR on the deviations, then run the forward pass with the true nonlinear dynamics — using $u_t = K_t \delta x_t + k_t + \hat{u}_t$ — so the states are the ones that will actually result; set $(\hat{x}, \hat{u})$ to the new trajectory; repeat. This is iterative LQR (iLQR).

Newton-style jumps have a classic failure: the quadratic approximation is only trusted near the expansion point, and its optimum can land somewhere worse than where you started — the trust-region issue from the advanced policy gradients lecture. The fix lives in the forward pass: scale the open-loop term, $u_t = K_t \delta x_t + \alpha k_t + \hat{u}_t$ . At $\alpha = 0$ the first action is exactly $\hat{u}_1$ , hence $x_2 = \hat{x}_2$ , hence every action reproduces the old trajectory; as $\alpha$ grows you deviate more. Search over $\alpha$ — reduce until the cost improves, or until you capture a fraction of the model-anticipated improvement, or bracket — a small change that matters a lot in practice.

Case study. Tassa, Erez, and Todorov’s “Synthesis and Stabilization of Complex Behaviors through Online Trajectory Optimization” runs iLQR inside model predictive control: every time step, observe $x_t$ , plan a full action sequence, execute only the first action, discard the rest, and replan — “a fancy way of saying replan on every single time step.” With known dynamics and zero learning, the controller discovers acrobot swing-up in real time, an undulating swimming gait, a hopper that stands up and survives extreme perturbations, and rudimentary humanoid balancing and stepping (with a heavily engineered cost, since the horizon is short). Constant replanning even forgives a misspecified model — the hopper still hops with double or half the mass the controller believes. That is the motivation for next week: replace the known model with a learned one.

Back of the chalk tray — what to remember

With a known model, decision-making becomes optimization: minimize summed costs over actions subject to $s_{t+1} = f(s_t, a_t)$ — planning, trajectory optimization, optimal control.
Open-loop plans commit to actions before information arrives (the math exam) and are generally suboptimal in stochastic settings; closed-loop planning returns a policy, which can be as simple as time-varying linear feedback.
Random shooting and CEM treat planning as black-box optimization over the concatenated action sequence — trivially parallel, derivative-free, but limited to roughly 30–60 dimensions and open-loop only.
MCTS handles stochastic discrete problems by expanding the search tree where the UCT score (average value plus a rare-visit bonus) directs, evaluating leaves with cheap rollout policies.
LQR solves linear-quadratic control exactly: a backward recursion yields $u_t = K_t x_t + k_t$ per step, and a forward recursion produces the trajectory; under Gaussian noise the same law is the optimal closed-loop policy.
iLQR/DDP extend LQR to nonlinear systems by Taylor expansion around the current trajectory — approximately Newton’s method — with a line search on $\alpha$ for trust; wrapped in MPC (replan every step), it produces striking behaviors with zero learning.

Check yourself

Exercises in the lecture’s spirit — planning, search, and control on paper.

Problem 10.1 open vs. closed loop

A two-step problem: at $t=1$ you are in state $s_1$ and choose $a_1 \in \lbrace L, R \rbrace$ ; nature then flips a fair coin revealing $s_2 \in \lbrace \text{heads}, \text{tails} \rbrace$ , and at $t=2$ you choose $a_2 \in \lbrace L, R \rbrace$ . The reward is 1 if $a_2$ matches the coin ( $L$ for heads, $R$ for tails) and 0 otherwise; $a_1$ has no effect. Compute the best achievable expected reward for (a) an open-loop planner committing to $(a_1, a_2)$ before the coin flip and (b) a closed-loop policy. Which lecture example is this, and what structural feature of the problem creates the gap?

Show solution

(a) Any fixed $(a_1, a_2)$ matches the coin with probability $\tfrac{1}{2}$ , so the best open-loop expected reward is $\tfrac{1}{2}$ — the planner must average over $p(s_2 \mid s_1, a_1)$ , and no committed $a_2$ is right in both outcomes. (b) A closed-loop policy observes $s_2$ and plays $L$ on heads, $R$ on tails: expected reward $1$ . This is the math exam in miniature — you know the answer to every question but not which question will be asked. The gap exists exactly because information useful for acting (the coin’s outcome) is revealed between the commitment point and the action; in a deterministic problem $s_2$ is a known function of $(s_1, a_1)$ , nothing new is revealed, and open loop matches closed loop.

Problem 10.2 one CEM iteration

You run CEM on a scalar action with $N = 5$ samples and $M = 2$ elites. The samples and returns are: $a = 1$ with $J = 2$ ; $a = 3$ with $J = 5$ ; $a = 5$ with $J = 9$ ; $a = 7$ with $J = 8$ ; $a = 9$ with $J = 1$ . Fit a Gaussian to the elites (max-likelihood: sample mean and variance) and give the next sampling distribution. Then explain why CEM with a Gaussian can converge prematurely, and what property of the initial distribution the lecture’s global-optimum guarantee relies on.

Show solution

The elites are the top two by return: $a = 5$ ( $J = 9$ ) and $a = 7$ ( $J = 8$ ). The max-likelihood Gaussian has mean $\mu = \tfrac{5+7}{2} = 6$ and variance $\sigma^2 = \tfrac{(5-6)^2 + (7-6)^2}{2} = 1$ , so the next iteration samples from $\mathcal{N}(6, 1)$ — sampling now focuses on the region where the good samples lay. Premature convergence: each refit shrinks the variance toward the spread of the current elites, so if early samples miss a distant better optimum, the distribution can collapse around a local one and the vanishing variance means it effectively never samples far enough away to discover the mistake. The lecture’s guarantee requires a large enough initial distribution (broad enough to cover the optimum) and enough samples per iteration — with too few of either, “enough” is exactly what you lose.

Problem 10.3 UCT arithmetic

A root node has been visited $N = 4$ times and has two children: child A with total value $Q_A = 30$ , $N_A = 3$ , and child B with $Q_B = 12$ , $N_B = 1$ . Using $\text{Score} = Q/N + 2C\sqrt{2\ln N_{\text{parent}}/N_{\text{child}}}$ , which child does UCT descend into for $C = 1$ ? For which values of $C$ does the choice flip? What does each regime of $C$ correspond to?

Show solution

With $\ln 4 \approx 1.386$ : child A scores $\tfrac{30}{3} + 2C\sqrt{2(1.386)/3} = 10 + 2C\sqrt{0.924} \approx 10 + 1.922C$ ; child B scores $\tfrac{12}{1} + 2C\sqrt{2(1.386)/1} = 12 + 2C\sqrt{2.772} \approx 12 + 3.330C$ . At $C = 1$ : A $\approx 11.92$ , B $\approx 15.33$ — descend into B, which has both the higher average (12 vs. 10) and the fewer visits, so the choice holds for every $C \ge 0$ : setting the scores equal gives $10 + 1.922C = 12 + 3.330C$ , i.e. $C = -2/1.408$ , which is negative — no valid $C$ flips it. (If A had the higher average, small $C$ would exploit A while large $C$ would explore B.) Small $C$ weights average return — exploitation; large $C$ weights the rare-visit bonus — exploration. The bonus’s $\ln N_{\text{parent}}$ numerator grows as the parent accumulates visits, so a child left unvisited eventually gets tried no matter how bad it looks.

Problem 10.4 scalar LQR backward pass

Scalar system: dynamics $x_{t+1} = x_t + u_t$ (so $F_t = [1 \;\; 1]$ , $f_t = 0$ ), cost $c(x, u) = \tfrac{1}{2}(x^2 + u^2)$ , horizon $T = 2$ . Run the LQR backward pass by hand: find $K_2, k_2$ , the value function $V(x_2)$ , then $K_1, k_1$ . Then, given $x_1 = 4$ , run the forward pass.

Show solution

Here $C_{xx} = C_{uu} = 1$ , $C_{ux} = 0$ , $c_x = c_u = 0$ at every step. Step $t = 2$ : $u_2$ minimizes $\tfrac{1}{2}(x_2^2 + u_2^2)$ , so $K_2 = -C_{uu}^{-1}C_{ux} = 0$ , $k_2 = 0$ , i.e. $u_2 = 0$ . Substituting back: $V(x_2) = \tfrac{1}{2}x_2^2$ , so $V_2 = 1$ , $v_2 = 0$ . Step $t = 1$ : $Q_1 = C_1 + F_1^\top V_2 F_1 = \begin{bmatrix}1&0\\0&1\end{bmatrix} + \begin{bmatrix}1\\1\end{bmatrix}(1)\begin{bmatrix}1&1\end{bmatrix} = \begin{bmatrix}2&1\\1&2\end{bmatrix}$ , so $Q_{xx} = 2$ , $Q_{ux} = 1$ , $Q_{uu} = 2$ , and $q_1 = 0$ . Then $K_1 = -Q_{uu}^{-1}Q_{ux} = -\tfrac{1}{2}$ , $k_1 = 0$ . Forward pass from $x_1 = 4$ : $u_1 = -\tfrac{1}{2}(4) = -2$ ; $x_2 = x_1 + u_1 = 2$ ; $u_2 = K_2 x_2 = 0$ . Total cost: $\tfrac{1}{2}(16 + 4) + \tfrac{1}{2}(4 + 0) = 12$ . Sanity check on the structure: the controller spends control effort at $t = 1$ to shrink the state it must pay for at $t = 2$ , and it takes no action at the final step because (with no terminal state cost beyond $c(x_2, u_2)$ , where $x_2$ is already fixed) any $u_2 \ne 0$ only adds cost. Note the whole solve never needed $x_1$ until the forward pass — exactly the unzip-backward, zip-forward structure.

Problem 10.5 iLQR line search

In iLQR’s modified forward pass, $u_t = K_t \delta x_t + \alpha k_t + \hat{u}_t$ with $\alpha \in [0, 1]$ . (a) Prove by induction that $\alpha = 0$ reproduces the previous trajectory exactly. (b) Explain what problem the search over $\alpha$ solves, and why the forward pass — not the backward pass — is the right place for it.

Show solution

(a) Base case: $x_1$ is the given initial state, the same in every iteration, so $\delta x_1 = x_1 - \hat{x}_1 = 0$ , and with $\alpha = 0$ , $u_1 = K_1 \cdot 0 + 0 + \hat{u}_1 = \hat{u}_1$ . Inductive step: if $x_t = \hat{x}_t$ and $u_t = \hat{u}_t$ , then $x_{t+1} = f(x_t, u_t) = f(\hat{x}_t, \hat{u}_t) = \hat{x}_{t+1}$ (the forward pass uses the true dynamics, which also generated the old trajectory), so $\delta x_{t+1} = 0$ and $u_{t+1} = \hat{u}_{t+1}$ . By induction the whole old trajectory is reproduced; as $\alpha$ shrinks toward 0 the new trajectory continuously approaches the old one. (b) The backward pass optimizes a Taylor approximation that is only trustworthy near $(\hat{x}, \hat{u})$ ; jumping to the approximation’s optimum — as raw Newton’s method does — can land at a point where the true cost is worse. Scaling $\alpha$ interpolates between the old trajectory and the full step, so reducing it until the true cost improves (or a fraction of the predicted improvement is realized) is a backtracking line search enforcing trust. It must live in the forward pass because only the forward pass evaluates the true nonlinear dynamics and cost — the backward pass only ever sees the linear-quadratic approximation, which by construction believes its own optimum is great.