Classical Planning and Optimal Control

Here the initial Bellman residual is one, and the residual after $k$ updates is $\gamma^k$. Reaching tolerance $\epsilon$ therefore takes about $\log(1/\epsilon)/\log(1/\gamma)$ sweeps. In a larger MDP, the observed count also depends on the dynamics, initialization, norm, and stopping rule, but $\gamma$ still controls the worst-case geometric bound.

There is also a practical reason to master these methods before we complicate them. Search shows the computational value of heuristic information through expansions saved. Dynamic programming exposes the cost of enumerating a state space. In LQR, the matrices $Q$ and $R$ jointly shape the trade-off between state regulation and control effort. Nonlinear trajectory optimization with a local solver exposes sensitivity to initialization and constraints. These same design choices remain when hand-built models are replaced by learned ones, but their effects become harder to isolate.

Let's separate the two roles cleanly, because blurring them causes endless confusion.

The transition model answers a predictive question: given a state and an action, what happens next? In notation we have used throughout Part II, it provides $p(s_{t+1} \mid s_t, a_t)$. A learned reward model may also predict the numeric value of an externally defined objective. The transition dynamics are descriptive; the reward or cost supplies the normative criterion used by the planner. A perfect weather simulator predicts well but does not, by itself, specify what an agent should prefer.

The controller or planner answers a normative question: given that predictive machinery, which actions should we take to accumulate the most reward (or the least cost) over some horizon? The planner is prescriptive. It consumes predictions and produces commitments. The two components can be developed and unit-tested separately, but they must be validated jointly because planning changes which parts of the model matter.

The formulation above hides an important choice. An open-loop plan commits to an action sequence before seeing where the actions land, while a closed-loop policy can react to new state measurements or estimates. The basic search and trajectory-optimization forms used here produce open-loop plans; tabular dynamic programming and LQR produce feedback policies. Receding-horizon methods partially close the loop by replanning from new information, which can limit error accumulation but does not guarantee robustness to a bad model.

Two distinctions from earlier chapters matter immediately. First, open-loop prediction quality and closed-loop decision usefulness can diverge. A model can fit one-step transitions in a validation set yet remain biased along the directions a planner exploits. Conversely, a controller can tolerate sizable task-irrelevant or feedback-correctable errors when the resulting closed loop remains stable. Predictive fidelity, representation quality, uncertainty quality, and decision usefulness therefore need separate tests. Second, planning from a model means reasoning about futures that have not been experienced, which is valuable precisely where multi-step model error becomes dangerous.

A useful mental split for this whole chapter:

• Search asks: what is the best single path from here to there?
• Dynamic programming asks: what is the best action from every state?
• LQR asks: what is the optimal feedback law for known linear dynamics and quadratic cost?
• Trajectory optimization asks: what state-and-control trajectory best satisfies the dynamics, objective, and any task constraints?

These four questions sit on a spectrum of scope. The A* example answers one start-goal query. Tabular dynamic programming amortizes work over every represented state. LQR gives a feedback formula under linear-quadratic assumptions. Nonlinear trajectory optimization accepts broader dynamics and costs, but still relies on a finite parameterization and on solver assumptions such as differentiability or constraint regularity.

We now take these in turn, using one running example, a small grid robot, for the discrete methods, and a double integrator plus a pendulum for the continuous ones.

When the world is deterministic and fully observable and the reachable state-action space is represented as a discrete graph, planning can be posed as graph search. States become nodes, actions become edges, and action costs become edge weights. The planner's job is to find a minimum-cost path from the current state to a goal state.

This is a transparent relationship between model and decision: the model is the graph itself, and a rollout is a walk along edges. There is no expectation to average over, no discounting to tune, and no value function to estimate. The planning problem is combinatorial: which of the potentially exponentially many simple paths from start to goal is cheapest?

This abstraction covers route planning, puzzles, symbolic task planning, and motion planning on discretized configuration spaces. Other tasks can be approximated as search when a finite state representation and known transitions are available. Exact search is then a useful baseline when the graph size, costs, and query structure make it tractable.

If all we know is the cost of each action, the right baseline is Dijkstra's algorithm. It maintains a priority queue of frontier states ordered by the cheapest known cost to reach them, and repeatedly expands the cheapest frontier state. When a state is expanded, we can be certain that no cheaper route to it exists, because any other route would have to pass through the frontier, and everything on the frontier is already at least as expensive. When the goal is expanded, the path is therefore guaranteed optimal, provided all costs are nonnegative.

The price is that Dijkstra is uninformed about where the goal lies. On the uniform grid used below, its shortest-distance sublevel set grows like a blob around the start until it reaches the goal. On an irregular weighted graph that set need not resemble a disk, and the same work may be reusable for other queries.

A* fixes this by adding heuristic knowledge. Each frontier state is ranked not by cost-so-far $g(s)$ alone, but by

where:

• $g(s)$: the cheapest known cost to reach $s$ from the start, accumulated along the best path found so far
• $h(s)$: an estimate of the remaining cost from $s$ to the goal
• $f(s)$: the estimated total cost of a solution path passing through $s$, the priority used to rank frontier states

If $h$ were the true remaining cost, A* would avoid nodes that cannot belong to an optimal solution, although ties among equally optimal alternatives can still cause extra expansions. In practice $h$ is a cheap lower bound, such as straight-line distance for a robot or Manhattan distance on a grid. These estimates ignore walls, detours, and dynamics, which makes them optimistic.

Why does optimism translate into optimality? Let $C^*$ be the optimal solution cost. Before the optimal goal is popped, at least one frontier entry $n$ on an optimal path has $g(n)=g^*(n)$; admissibility then gives $f(n)=g^*(n)+h(n)\le C^*$. A suboptimal goal has $h=0$ and therefore $f=C>C^*$. A* cannot pop that goal while the optimal-prefix entry remains. For graph search, consistency or node reopening preserves this invariant when paths merge.

The heuristic is encoded task knowledge that accelerates planning. It approximates remaining cost without simulating the full dynamics. Manhattan distance knows nothing about the walls in our grid, yet it reduces search effort because cost tends to grow with distance. The same pattern, an exact method guided by an approximation of cost-to-go, reappears in learned latent-space planning.

Let's build a small grid world with two walls, each with a gap, and compare A* against Dijkstra.

The picture also shows the heuristic's limits. Many states tie on the same $f$ value, so A* still expands a broad region to the left of the first wall. A wall-aware cost-to-go estimate could reduce that extra work, but tie-breaking and multiple optimal routes still matter.

The finite deterministic shortest-path methods used here are exact under their cost and heuristic conditions. Their basic formulations also make several simplifying assumptions:

• Determinism. Each action has exactly one outcome. Stochasticity does not remove the state graph, but it breaks the single-successor shortest-path formulation and requires expectations or contingent policies over transition distributions.
• Full observability. The planner knows the current node. With partial observability we search over belief states instead, exactly the objects Chapter 2 of this part built for us. Note that the belief space is continuous even when the underlying state space is discrete, so partial observability quietly destroys the discreteness assumption as well.
• Discreteness. Exact Dijkstra or A* needs an explicitly enumerable or lazily generated discrete graph whose successors can be enumerated at each expansion. Sampling-based continuous planners use different constructions and may offer probabilistic-completeness or asymptotic-optimality guarantees; the exact guarantee depends on the algorithm.
• Query scope. The A* run here answers one start-goal query. Dijkstra can compute single-source distances to all reachable nodes, and roadmap methods can amortize preprocessing across queries. Tabular DP goes further by computing a policy for every represented state under stochastic dynamics.

For this example, A* is a one-shot calculation and tabular DP is an amortized investment: it spends more work up front, then supplies an action at every represented state. Neither dominates the other. The right choice depends on query volume, stochasticity, graph size, and whether the model stays fixed.

Dynamic programming (DP) flips the question. Instead of "how do we get from here to the goal?", it asks "what is the value of being in each state, assuming we act optimally from now on?" In a tabular model, the resulting policy is a lookup for every represented state. DP handles stochastic transitions without changing its Bellman structure, whereas ordinary deterministic graph search must be generalized.

The central object is the optimal value function. Recall from Chapter 1 of this part that a policy $\pi$ assigns actions to states and that we score policies by expected discounted return. The optimal value of a state is the best return achievable from it:

where:

• $V^*(s)$: the optimal value of state $s$, the best expected discounted return achievable starting from $s$
• $\pi$: a policy assigning an action distribution to each state, with $\max_\pi$ selecting the best one; in a finite discounted MDP, a deterministic stationary optimum exists
• $\mathbb{E}_\pi$: the expectation over trajectories generated by following $\pi$ under the model's transition dynamics
• $s_0 = s$: the condition that the trajectory starts in state $s$
• $\gamma^t r(s_t, a_t)$: the reward received at step $t$, discounted by one factor of $\gamma$ per step into the future

One subtlety worth pausing on: the maximum is over policies, which map states to action distributions; deterministic policies are the action-valued special case. The Bellman equation decomposes this global optimization into linked per-state action comparisons.

What makes DP work is that the value function satisfies a self-referential equation. If we act optimally, our first action must be the one that maximizes immediate reward plus the discounted optimal value of wherever we land:

where:

• $a$: a candidate action available in state $s$, with $\max_a$ selecting the best one
• $r(s, a)$: the immediate reward for taking action $a$ in state $s$
• $s'$: a possible successor state after taking action $a$ in state $s$
• $p(s' \mid s, a)$: the model's transition probability, its prediction of where action $a$ from state $s$ lands
• $\gamma \sum_{s'} p(s' \mid s, a)\, V^*(s')$: the discounted expected optimal value of the successor state

This is the Bellman optimality equation. Read it as a statement about consistency across time: the value of being somewhere equals the best one-step payoff plus the value of the future. In a Markov problem with an additive return, the principle of optimality says that an optimal continuation must itself be optimal from the successor state. That is what licenses the replacement of "the best policy from here on" with "the best action now, assuming optimality thereafter." The recursion turns a global policy problem into local action comparisons linked through the value function. Many methods in model-based RL solve this equation, or an approximation to it, but not every planner is organized around an explicit Bellman equation.

For a fixed policy $\pi$, the maximization drops out and we get the Bellman expectation equation, a linear system in $V^\pi$:

where:

• $V^\pi(s)$: the value of state $s$ when the agent follows the fixed policy $\pi$ from $s$ onward
• $\pi(a \mid s)$: the probability that policy $\pi$ assigns to choosing action $a$ in state $s$
• $r$, $p$, and $\gamma$: the same reward, transition model, and discount factor as in the optimality equation above

The linearity of this equation is more useful than it may first appear. A finite-state version can be solved by linear algebra or converged to by iteration. With sampled transitions, Monte Carlo and temporal-difference methods instead estimate the same policy value or its Bellman fixed point without forming the full transition matrix. Learned critics extend that idea with function approximation.

For bounded rewards and $0 \le \gamma < 1$, the Bellman optimality operator is a $\gamma$-contraction in the max-norm: applying it to any two bounded value functions leaves them at most $\gamma$ times as far apart. Two value functions that differ by at most $\epsilon$ in every state therefore cannot differ by more than $\gamma\epsilon$ after one backup. The contraction mapping theorem gives a unique fixed point, $V^*$. We can start from any bounded guess, say $V_0 = 0$, and repeatedly apply the operator:

where $V_k$ is the value estimate after $k$ sweeps of the operator, with the starting guess $V_0 = 0$, and $V_{k+1}$ is the result of one more application.

This is value iteration, and the contraction property guarantees geometric convergence to $V^*$. With $\gamma = 0.95$, the worst-case value error after a backup is at most 95 percent of the preceding error. To reduce an initial error bound by a factor $\epsilon$, the usual worst-case count scales like $\log(\epsilon)/\log(\gamma)$. A large discount factor therefore expresses a long planning horizon and also gives a slower worst-case contraction. It does not, by itself, set a planner's noise floor.

Let's make the iteration concrete on our grid world, where rewards are $-1$ per step, the goal is terminal with value $0$, and $\gamma = 0.95$. Consider a free cell exactly one step from the goal. Its best action reaches the goal, so one sweep of the operator gives

A cell three steps away needs three sweeps before the goal's influence propagates back, and its converged value is the geometric sum

You can already see the mechanism: value flows backward from the goal through the Bellman operator, one step of lookahead per sweep. After $k$ sweeps, every state within $k$ steps of the goal has a correct value, and after convergence, every state does. This backward flow is the discrete cousin of the Riccati recursion we will meet in the LQR section. It is also related to backpropagation through time in trajectory optimization. A forward rollout computes states from controls; the reverse-mode gradient pass then propagates cost sensitivities backward through those dynamics. Bellman backups propagate value information backward across predecessor relationships. The objects differ, but both algorithms exploit temporal composition.

Now implement it. The environment transition is embedded in a small step function that bumps the agent back if it would leave the grid or hit a wall.

The left panel shows value flowing toward the goal, brightest at the terminal state and darkest in the far corner. Notice how the contours bend around the walls: value is a distance-like field, but it is a distance through the navigable space, so the walls leave visible ridges in it. The right panel shows why value functions are so useful in practice: the policy is a vector field, a complete answer to "what should we do?" available at every state, computed once, queried forever. If the robot is picked up and dropped somewhere new, no replanning is needed; the field already covers that location. This "compute once, query forever" property is exactly what a learned world-model agent tries to approximate when it trains a policy network against rollouts from a latent dynamics model.

The catch is enumeration. If each state-action pair has at most $b$ possible successors, a Bellman sweep costs $O(|S||A|b)$; deterministic transitions give the $O(|S||A|)$ special case, while a dense table costs $O(|S|^2|A|)$. Our grid has 84 free states. A robot arm with 10 joints discretized at 10 values each has $10^{10}$ state combinations, and 50 binary variables give $2^{50}$. This Cartesian growth is the curse of dimensionality.

At fixed resolution per coordinate, the table grows exponentially in the number of factored state dimensions, not in any direct measure of task difficulty. A ten-joint arm does not need $10^{10}$ qualitatively different behaviors; sensible behaviors may occupy a much smaller structured subset of that grid. Tabular representations cannot exploit such smoothness or structure, so the curse is partly representational. Function approximation attacks that problem, though it introduces new approximation and optimization errors.

Every escape route changes the problem. Discretization loses precision. Function approximation replaces the unconditional tabular contraction guarantee with guarantees that require additional assumptions about the architecture, objective, sampling, and update rule. Exploiting known structure, which is what LQR does next, restricts the problem class but buys exact and efficient solutions within it. Learned latent models make a different wager: that a compact representation preserves enough task structure for approximate planning to be useful.

The exponential character of the curse is easier to feel as a picture than as a sentence.

A ten-dimensional system at ten values per dimension already sits at $10^{10}$ states, far beyond any table. This curve is the quantitative face of the curse, and it is the reason the next section's structural assumptions, and later chapters' learned compact representations, are not conveniences but necessities.

Finite tabular DP needs an enumerable state set. Continuous-state dynamic programming also exists, but representing an arbitrary value function is difficult. The linear-quadratic regulator (LQR) is a foundational, widely used special case in which the Bellman equation reduces to Riccati equations. Iterative LQR and differential dynamic programming, in turn, build local trajectory updates from LQR-like subproblems.

The setting is:

• Linear dynamics (from Chapter 3's system identification, or first-principles modeling):

  $$x_{t+1} = A x_t + B u_t,$$

  where $x_t$ is the state, $u_t$ the control input, $A$ the state-transition matrix describing how the current state carries into the next, and $B$ the input matrix describing how the control changes the next state.

• Quadratic cost, penalizing deviation from zero and control effort:

  $$J = \sum_{t=0}^{T-1} \left( x_t^\top Q x_t + u_t^\top R u_t \right) + x_T^\top Q_f x_T,$$

  where:

  • $x_t^\top Q x_t$: the per-step cost in state directions weighted by $Q$; it is positive for every nonzero deviation only when $Q \succ 0$
  • $u_t^\top R u_t$: the per-step control cost, penalizing control effort
  • $x_T^\top Q_f x_T$: the terminal cost on the final state $x_T$
  • $Q$, $R$, $Q_f$: symmetric cost matrices with $Q, Q_f \succeq 0$ and $R \succ 0$, so state costs are nonnegative while control is strictly penalized

Why quadratic? Squared error is a natural penalty for regulation, and, together with linear dynamics, it gives a value-function family that is closed under Bellman backups: if $V(x) = x^\top P x$, the next backup is quadratic too. A probabilistic interpretation is available when the quadratic terms are proportional to negative log densities of Gaussian state preferences and control priors, but that interpretation needs those modeling assumptions; it is not intrinsic to every LQR problem. The closure property is the computational trick: we solve for the finitely many entries of $P$ rather than for an arbitrary function.

Guess that the value function is quadratic, $V(x) = x^\top P x$, and run one step of the Bellman backup:

where:

• $P$: the matrix of the current quadratic value estimate $V(x) = x^\top P x$
• $P'$: the updated matrix after one backup, defining the next value iterate
• $Ax + Bu$: the model's prediction of the next state under the linear dynamics
• $\min_u$: optimization over all candidate controls $u$, selecting the one with the smallest one-step cost plus successor value

The expression inside the min is a quadratic in $u$, so it can be minimized analytically by setting its gradient to zero:

Solving this linear equation for $u$ gives the optimal feedback law

Two things just happened that are worth savoring. First, the optimal policy came out linear in the state, with the gain matrix $K$ as the only unknown. We did not restrict the policy class; we allowed arbitrary (measurable) functions from state to action, and the optimizer chose a linear one because the problem's structure made it optimal. Second, the minimizing $u$ can be computed in closed form, no search over actions needed. Compare this with the grid world, where every action had to be enumerated and evaluated at every state. Here the entire maximization over a continuum of controls collapses to solving a small linear system. Structure bought us the same thing the heuristic bought A*: a way to skip most of the work. Now substitute $u^*(x) = -Kx$ back into the backup, so that $Ax + Bu^* = (A - BK)x$:

Reading off the matrix and imposing the fixed-point condition $P' = P$ yields

This is the discrete algebraic Riccati equation (DARE). The finite-horizon version is a backward recursion in time: start with $P_T = Q_f$ and step the recursion backward to $t=0$. The infinite-horizon equation has a unique positive semidefinite stabilizing solution under the usual stabilizability and detectability conditions, and the resulting modeled closed-loop matrix $A-BK$ is Schur stable. Along its trajectories,

This is nonpositive in general and strictly negative for every nonzero $x_t$ when $Q+K^\top RK$ is positive definite. Under those conditions, $V(x)=x^\top P x$ is a Lyapunov certificate for the modeled closed loop. The theorem does not automatically certify a different true plant or an approximate nonlinear system.

Let's do this end to end. Following Chapter 3, we fit $A$ and $B$ of a double integrator from noisy transition data, solve the Riccati equation on the estimated model, and deploy the resulting gain on the true system. This identify-plan-deploy chain is one common model-based-control pattern. Later systems may also change the representation, uncertainty treatment, planner, data-collection loop, adaptation rule, and safety architecture.

First, generate data and identify the model by least squares.

As $R$ shrinks, control becomes cheap and the gain grows. The worst eigenvalue magnitude of the true plant is nonmonotone over this sweep, so gain size alone should not be read as a universal speed measure. Every tested true-plant eigenvalue remains below the dotted unit line, but that is a numerical result for this small identification error. The Riccati guarantee applies directly to each estimated-model design; transfer to the true plant requires a robustness margin or an explicit check such as this one.

LQR's limits mirror its strengths: its exact solution needs linear dynamics and quadratic costs. Iterative LQR (iLQR) and differential dynamic programming approximate nonlinear dynamics and costs around a nominal trajectory, compute local feedback updates, roll out a new nominal, and repeat. Model predictive control (MPC) solves a finite-horizon problem at each step, applies the first action, observes the next state, and replans. That feedback can correct some disturbances and model errors before they accumulate across many horizons, but it does not erase within-horizon error or guarantee robustness. Local approximation and receding-horizon replanning form a bridge to the planning agents of Part VII.

LQR gives optimality by exploiting linear-quadratic structure. With nonlinear dynamics, non-quadratic costs, or constraints, trajectory optimization states a finite-horizon problem directly and solves it numerically. These methods still exploit substantial structure: dynamics couple only neighboring time steps, derivatives are sparse, and specialized shooting or collocation solvers use that organization. The result is a flexible framework used throughout robotics and aerospace, with guarantees that depend on the solver, formulation, initialization, and model.

The formulation is direct. Treat the entire future as decision variables:

subject to the dynamics acting as equality constraints,

and the initial condition

plus whatever task constraints apply, for example $u_{\min} \le u_t \le u_{\max}$ from actuator limits or obstacle-avoidance inequalities on the states. The symbols in these two expressions are:

• $\ell(x_t, u_t)$: the running cost incurred at step $t$, encoding objectives such as tracking error and control effort
• $\ell_f(x_T)$: the terminal cost on the final state $x_T$
• $f(x_t, u_t)$: the model's dynamics, predicting the next state from the current state and control
• $x_1, u_0, \dots, x_T, u_{T-1}$: the optimized state-and-control trajectory; $x_0$ is fixed by the initial condition

Search and DP asked for a path or value function; LQR produced a feedback law. Open-loop trajectory optimization instead returns one nominal state-control trajectory. It can be used offline with a tracking controller, or online inside receding-horizon MPC when computation permits. Both pairings add feedback that the nominal trajectory alone does not provide.

For the nonlinear problems emphasized here, two widely used direct formulations are shooting and collocation.

• Direct shooting keeps only the controls $u_0, \dots, u_{T-1}$ as decision variables and simulates the model to produce the states. The dynamics constraints are satisfied by construction, and gradients are obtained by differentiating through the rollout. The downside: the map from early controls to late states becomes long, thin, and poorly conditioned, so gradients through long rollouts can vanish or explode. Intuitively, an early control affects a late state only through a long chain of intermediate states, and the Jacobian of that chain is a product of many Jacobians whose singular values multiply, so the gradient magnitude can shrink or grow exponentially in the horizon length.
• Direct collocation keeps states and controls as joint decision variables and enforces discretized dynamics as explicit constraints at collocation points. This exposes sparse structure and often improves conditioning, at the cost of a larger optimization problem. An NLP solver drives the discrete constraint residuals toward its numerical tolerances; whether the resulting continuous trajectory is feasible also depends on the transcription resolution and model fidelity.

To make this concrete, let's solve a nonlinear task by direct shooting with automatic differentiation and Adam: swinging up a bounded-input pendulum. We use normalized angular dynamics

where:

• $\theta$: the pendulum angle, with $\theta = 0$ hanging down and $\theta = \pi$ the upright target
• $\dot\theta$, $\ddot\theta$: the angular velocity and the angular acceleration
• $\omega_g^2$: the normalized gravity coefficient, with units of inverse seconds squared; $\omega_g^2\sin\theta$ has angular-acceleration units
• $c$: the damping rate
• $u$: the commanded angular acceleration after normalizing motor torque by inertia

In the simulation below the normalized gravity coefficient is $3.0$ while the input bound is $2.0$. A constant saturated input therefore cannot hold the pendulum at horizontal, and the optimizer must exploit momentum to reach the upright. We optimize $u_0,\dots,u_{T-1}$ by reverse-mode differentiation through the discretized rollout, with the input bound represented by clamping.

The loss drops rapidly and then improves more gradually. The curve shows optimization progress, but it does not identify which physical strategy Adam discovered at each iteration; that would require inspecting intermediate trajectories. The later, slower phase is consistent with local refinement of a nonlinear shooting solution, not proof of a universal signature for shooting methods.

This example compresses the chapter's arc into one picture. We had a model, used it predictively to simulate rollouts, and obtained an open-loop control sequence by optimizing the model's outputs. No explicit value table or search tree was needed. The pendulum has one mechanical degree of freedom and a two-dimensional state $(\theta,\dot\theta)$. A comparable transcription gains variables as state and control dimension increase; conditioning, constraint difficulty, and local optima depend on the model, coordinates, objective, and constraint structure. When a nonconvex problem has separate basins, a local optimizer may settle on one gait even if a lower-cost gait lies in another. Better initialization, multiple starts, sampling-based exploration, and learned trajectory priors are common responses.

The key parameters for the planning methods in this chapter are:

• gamma ($\gamma$): The discount factor used in value iteration, set to $0.95$. For bounded discounted problems, it is the Bellman operator's worst-case contraction modulus. Values close to one put more weight on distant rewards and give a slower worst-case convergence bound.
• tolerance: The sweep-stopping threshold, set to 1e-6 on the maximum update. It is a residual threshold; the contraction bound converts it to a value-error bound by dividing by $1-\gamma$.
• Q, R: The state and control cost matrices for LQR, set to $Q = I$ and $R = 0.5I$. Their relative weighting changes the feedback gain and the trade-off between state regulation and control effort; the response need not be a simple proportional scaling.
• u_max: The normalized angular-acceleration input bound for pendulum swing-up, set to 2.0, below the gravity coefficient at horizontal. The optimized solution uses momentum to reach the target under this bound.
• lr: The Adam learning rate, set to 0.05. A value that is too large can make parameter updates unstable, while a very small value may converge slowly. Its useful scale depends on the horizon, dynamics, parameterization, and objective.

Many assumptions behind these methods motivate research questions later in the book.

The deepest shared assumption is that the model is adequate where the planner uses it. Once the model is learned, two new failure modes appear. First is compounding rollout error. Small one-step errors are propagated by the dynamics and can accumulate, cancel, or amplify depending on their bias, correlation, and the system's sensitivity. A systematic error of size $\epsilon$ can contribute a sum of propagated errors over an $H$-step open-loop rollout. In feedback, corrupted states also change later actions. One-step accuracy therefore does not determine multi-step fidelity, so both should be evaluated at the horizons used for decisions.

The compounding mechanism can be illustrated with the double integrator itself.

The injected one-step errors have matched RMS magnitude, yet their rollout errors differ markedly. Independent zero-mean disturbances still accumulate in this marginally stable system, while the fixed velocity bias compounds much faster. This controlled example does not establish a universal growth law; it shows why the temporal structure of model error matters and why rollout fidelity should be measured directly.

Second is model exploitation. Optimization can steer a planner toward inputs where an approximate model is optimistically wrong, especially outside the data distribution. Approximation creates this risk but does not imply that every model will be exploitable on every task. Classical optimizers do not remove the problem when they plan with an approximate model. Practical defenses include uncertainty-aware or robust objectives, conservative penalties, shorter horizons, feedback and replanning, and collecting new data in planner-visited regions. Chapter 6 develops this gap between predictive fidelity and decision usefulness directly.

The second limitation is scale. Cartesian tabular representations grow exponentially in the number of factored dimensions at fixed resolution, although a particular search problem may explore only a small reachable subset. LQR remains efficient by restricting dynamics and costs to the linear-quadratic class. Nonlinear trajectory optimization with a local solver is initialization-sensitive and may reach a local stationary point, an infeasible point, or fail; convex special cases have stronger global guarantees. Discretizing a continuous space exposes a familiar trade-off: fine grids improve resolution but grow combinatorially, while coarse grids may erase task-relevant structure. Part III turns to representations that aim to make approximate planning tractable.

A third limitation is that these planners typically assume full observability and a stationary, Markov environment. We know from Chapter 1 of this part how to restore Markovianity through belief states, and from Chapter 2 how to propagate those beliefs forward. But belief-augmented planning (search over beliefs, DP over beliefs) multiplies the state space again, since a belief is a distribution over states and the space of distributions is vastly larger than the space of states, and making that tractable is an open engineering frontier that connects directly to the memory architectures of Part III.

Under their stated assumptions, these methods do offer strong guarantees: Dijkstra and appropriately configured A* return optimal graph paths; discounted finite-MDP value iteration converges; and infinite-horizon LQR stabilizes its modeled plant under stabilizability and detectability conditions, with a quadratic certificate under the positivity conditions stated above. Learned controllers can also be analyzed or certified in restricted settings, but classical baselines make the assumptions unusually explicit. Hybrid systems often use learning to supply a model or representation and classical optimization to choose actions; how dominant that pattern is depends on the application domain.

The conceptual takeaway is the division of labor: the model predicts and the planner chooses. Search, DP, LQR, and trajectory optimization implement that split differently, trading off model class, planning horizon, computation, and available guarantees. Many later agents can be analyzed in the same trade space even when model and planner are implemented jointly.

• Planning turns a predictive model into a controller. Given $p(s' \mid s, a)$ and a reward, the planner finds actions that maximize expected return. Open-loop plans are action sequences; closed-loop policies are state-dependent and can react to observed outcomes.
• State-space search handles finite graph problems. Dijkstra is uninformed; A* uses a heuristic and is optimal under the admissibility and graph-search conditions stated in the chapter.
• For bounded rewards and $\gamma<1$, tabular dynamic programming solves the Bellman optimality equation and value iteration converges geometrically. Stochastic transitions fit naturally, but state enumeration causes the curse of dimensionality.
• LQR exploits linear dynamics and quadratic costs to obtain $u=-Kx$ from the Riccati equation. Its stability guarantee applies to the modeled system under stabilizability and detectability conditions; certainty-equivalent deployment on an estimated plant needs a robustness check.
• Trajectory optimization computes finite-horizon state-control sequences by shooting or collocation. Numerical hard-constraint satisfaction is tolerance- and discretization-dependent, and local solvers are sensitive to initialization.
• All four methods depend on a model that is adequate in the region used for decisions. With learned models, rollout error and optimizer-induced model exploitation become first-class problems.

The next chapter develops a probabilistic framing of control. Control-as-inference methods introduce optimality or preference variables and infer a posterior over trajectories and actions. Exact inference equivalences are narrow, for example maximum-entropy formulations with suitable deterministic dynamics, while stochastic systems generally require approximations such as variational inference. Uncertainty drives epistemic exploration only when the objective includes terms such as information gain or expected free energy. Those conditions lead into control as inference and active inference.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about classical planning and optimal control.