Backward Induction

340. Backward Induction

The standard algorithm for solving finite-horizon dynamic programming problems. Computes the optimal cost-to-go $𝐽_{𝑡} (𝑠)$ from the back ( $𝑡 = 𝑇$ ) toward the start ( $𝑡 = 0$ ).

340.1. Algorithm

For each terminal state s ∈ S:
    J[T][s] ← c_T(s)

For t = T-1, T-2, …, 0:
    For each state s ∈ S:
        J[t][s]  ← min over a of { c_t(s,a) + J[t+1][ f_t(s,a) ] }
        π[t][s]  ← argmin over a of the same expression

Return J[0][s₀] and policy {π[t][s]}

340.2. Why backward

At stage $𝑡$ you need to know $𝐽_{𝑡 + 1}$ to evaluate the Bellman equation:

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

So compute stages in reverse: $𝐽_{𝑇}$ first (base case), then $𝐽_{𝑇 - 1}$ , then $𝐽_{𝑇 - 2}$ , …, then $𝐽_{0}$ .

340.3. Complexity

𝑂 (𝑇 \cdot | 𝒮︀ | \cdot | 𝒜︀ |)

Polynomial in $𝑇$ , not exponential. (Naive enumeration is $| 𝒜︀ |^{𝑇}$ .)

Memory: $𝑂 (𝑇 \cdot | 𝒮︀ |)$ for the full table, or $𝑂 (| 𝒮︀ |)$ if you only need $𝐽_{0}$ and can discard each $𝐽_{𝑡 + 1}$ after using it (but then you lose the policy).

340.4. When backward is the right choice

Finite horizon with a clean terminal cost $𝑐_{𝑇} (𝑠)$
Computing the optimal value from a known start state $𝑠_{0}$
Producing the optimal action at every reachable state (policy)
Dense state graphs: most states are reachable

For sparse reachable sets, memoization (top-down recursive DP with caching) avoids computing unreached states.

340.5. Example: Wagner-Whitin lot-sizing

Demand $𝑑_{𝑡}$ in each period $𝑡 = 1, \dots, 𝑇$ . Setup cost $𝐾$ , holding cost $ℎ$ per unit per period. Choose periods to place orders to minimize total cost.

State: $𝑠_{𝑡} \in {0, 1, \dots, 𝑇}$ = the period of the last order (so demand from $𝑠_{𝑡} + 1$ to $𝑡$ is covered by that order).

The zero-inventory property says it’s optimal to order in period $𝑗$ iff $𝑗$ is a previous “last-order” period: $𝐽_{𝑇} (𝑇)$ = min total cost given the last order was in period $𝑇$ .

Backward induction over $𝑇$ states × $𝑇$ periods → $𝑂 (𝑇^{2})$ . This is the classic Wagner-Whitin algorithm — see Wagner-Whitin.

340.6. Tabulation vs memoization

Two implementations of the same logic:

Tabulation (bottom-up)	Memoization (top-down)
Fill full table $𝐽_{𝑇}, 𝐽_{𝑇 - 1}, \dots, 𝐽_{0}$ in order	Recursive call from $𝐽_{0} (𝑠_{0})$ , cache results
Visits every state	Only states actually reached
Best for dense reachable sets	Best for sparse reachable sets

Both compute the same $𝐽_{𝑡} (𝑠)$ .

340.7. See also

Bellman Equation
Forward Induction — the dual approach
Dynamic Programming