Classical Planning and Optimal Control › Dynamic Programming and Bellman Equations

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:

$$V^*(s) = \max_\pi \, \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t r(s_t, a_t) \,\Big|\, s_0 = s \right].$$

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:

$$V^*(s) = \max_{a} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a)\, V^*(s') \right].$$

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$:

$$V^\pi(s) = \sum_a \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a)\, V^\pi(s') \right].$$

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:

$$V_{k+1}(s) = \max_a \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a)\, V_k(s') \right].$$

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

$$V_1(s) = -1 + 0.95 \times 0 = -1.$$

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

$$V^*(s) = -(1 + 0.95 + 0.95^2) \approx -2.85.$$

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.