Bellman Equation

339. Bellman Equation

The recursion at the heart of dynamic programming. Defines the optimal cost-to-go $𝐽_{𝑡} (𝑠)$ — minimum cost to complete the problem from stage $𝑡$ in state $𝑠$ — as a function of cost-to-go from the next stage.

339.1. Principle of optimality (Bellman, 1957)

> “An optimal policy has the property that whatever the initial state and initial decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.”

Restated: if $(𝑎_{0}^{*}, 𝑎_{1}^{*}, \dots, 𝑎_{𝑇 - 1}^{*})$ is optimal from $𝑠_{0}$ , then $(𝑎_{1}^{*}, \dots, 𝑎_{𝑇 - 1}^{*})$ is optimal from $𝑠_{1} = 𝑓_{0} (𝑠_{0}, 𝑎_{0}^{*})$ .

Why true (contradiction): if the suffix weren’t optimal, swap it for the better one → strictly lower total cost → contradicts optimality of the full plan. ∎

339.2. Deriving the recursion

The total cost decomposes:

𝐽^{𝜋} (𝑠_{0}) = \underset{stage 0}{\underset{⏟}{𝑐_{0} (𝑠_{0}, 𝑎_{0})}} + \underset{sub-problem of same kind, from 𝑠_{1}}{\underset{⏟}{\sum_{𝑡 = 1}^{𝑇 - 1} 𝑐_{𝑡} (𝑠_{𝑡}, 𝑎_{𝑡}) + 𝑐_{𝑇} (𝑠_{𝑇})}}

The bracketed remainder is the same problem starting from $𝑠_{1}$ . By the principle of optimality, the optimal remainder is $𝐽_{1} (𝑠_{1})$ — the optimal cost-to-go from $𝑠_{1}$ .

So at stage $𝑡$ in state $𝑠$ , you pay $𝑐_{𝑡} (𝑠, 𝑎)$ now and face the optimal-remaining problem from $𝑓_{𝑡} (𝑠, 𝑎)$ :

𝐽_{𝑡} (𝑠) = min_{𝑎 \in 𝒜︀ (𝑠)} {𝑐_{𝑡} (𝑠, 𝑎) + 𝐽_{𝑡 + 1} (𝑓_{𝑡} (𝑠, 𝑎))}

This is the Bellman equation — direct consequence of additivity + principle of optimality.

339.3. Base case

𝐽_{𝑇} (𝑠) = 𝑐_{𝑇} (𝑠)

(no decisions left; the only cost is the terminal one.)

339.4. Optimal action

𝑎_{𝑡}^{*} (𝑠) = arg min_{𝑎} {𝑐_{𝑡} (𝑠, 𝑎) + 𝐽_{𝑡 + 1} (𝑓_{𝑡} (𝑠, 𝑎))}

The optimal total cost from $𝑠_{0}$ is $𝐽_{0} (𝑠_{0})$ .

339.5. Worked example: shortest path through a layered graph

Stages $0 \to 1 \to 2 \to 3$ , states ${𝑆}, {𝐴, 𝐵}, {𝐶, 𝐷}, {𝐺}$ . Edge costs:

from\to	A	B	C	D	G
S	4	2
A			5	3
B			1	6
C					2
D					4

Stage 3 (base case): $𝐽_{3} (𝐺) = 0$ .

Stage 2:

$𝐽_{2} (𝐶) = 2 + 0 = 2$
$𝐽_{2} (𝐷) = 4 + 0 = 4$

Stage 1:

$𝐽_{1} (𝐴) = min {5 + 2, 3 + 4} = min {7, 7} = 7$ (tie)
$𝐽_{1} (𝐵) = min {1 + 2, 6 + 4} = min {3, 10} = 3$ , action: go to $𝐶$

Stage 0:

$𝐽_{0} (𝑆) = min {4 + 7, 2 + 3} = min {11, 5} = 5$ , action: go to $𝐵$

Optimal path: $𝑆 \to 𝐵 \to 𝐶 \to 𝐺$ , cost $5$ .

339.6. Two variants

Backward induction: solve $𝐽_{𝑇} \to 𝐽_{𝑇 - 1} \to \dots \to 𝐽_{0}$ .
Forward induction: dual recursion on cost-to-arrive $𝑉_{𝑡} (𝑠)$ .

Both compute the same optimum — choose whichever fits the data flow.

339.7. Stochastic case

When transitions are random ( $𝑠_{𝑡 + 1} \sim 𝑃_{𝑡} (\cdot | 𝑠_{𝑡}, 𝑎_{𝑡})$ ), the Bellman equation becomes:

𝐽_{𝑡} (𝑠) = min_{𝑎} {𝑐_{𝑡} (𝑠, 𝑎) + \sum_{𝑠^{'}} 𝑃_{𝑡} (𝑠^{'} | 𝑠, 𝑎) 𝐽_{𝑡 + 1} (𝑠^{'})}

— expectation over the next state replaces the deterministic transition. See Stochastic DP.

339.8. See also

Dynamic Programming — the broader framework
Backward Induction — algorithm
Stochastic DP — random case