338. Dynamic Programming

A method for solving multi-stage decision problems by breaking them into overlapping sub-problems, each solved once and reused.

338.1. When DP applies

Required ingredients:

1. Stages — the problem decomposes into a sequence of decisions $𝑡=0,1,\dots ,𝑇-1$
2. State — a summary of the past sufficient for future decisions (Markov property)
3. Additive cost — total cost = sum of per-stage costs $\sum {𝑐}_{𝑡}\left({𝑠}_{𝑡},{𝑎}_{𝑡}\right)$
4. Known transition — ${𝑠}_{𝑡+1}={𝑓}_{𝑡}\left({𝑠}_{𝑡},{𝑎}_{𝑡}\right)$ deterministic, or ${𝑃}_{𝑡}\left({𝑠}^{\prime }|𝑠,𝑎\right)$ stochastic
5. Tractable state set — table fits in memory (or use approximation)

If any breaks, plain DP doesn’t apply.

338.2. Problem class

At stage $𝑡$ in state ${𝑠}_{𝑡}$:

• Choose action ${𝑎}_{𝑡}\in \mathrm{𝒜︀}\left({𝑠}_{𝑡}\right)$
• Pay immediate cost ${𝑐}_{𝑡}\left({𝑠}_{𝑡},{𝑎}_{𝑡}\right)$
• System transitions to ${𝑠}_{𝑡+1}={𝑓}_{𝑡}\left({𝑠}_{𝑡},{𝑎}_{𝑡}\right)$

After the last decision: terminal cost ${𝑐}_{𝑇}\left({𝑠}_{𝑇}\right)$.

Total cost of a plan $𝜋=\left({𝑎}_0,\dots ,{𝑎}_{𝑇-1}\right)$:

Goal: ${𝜋}^{\ast }=arg{min}_{𝜋}{𝐽}^{𝜋}\left({𝑠}_0\right)$.

338.3. Why naive enumeration fails

$𝐾$ actions per stage, $𝑇$ stages → ${𝐾}^{𝑇}$ plans. $𝐾=5,𝑇=20\to 5^{20}\approx {10}^{14}$. DP shrinks this to $𝑂\left(𝑇\left|\mathrm{𝒮︀}\right||\mathrm{𝒜︀}|\right)$ via the Bellman recursion.

338.4. Core ideas

• Bellman equation — the recursion that breaks the problem into sub-problems
• Backward induction — solve from the end back
• Forward induction — dual direction (cost-to-arrive)
• Stochastic DP — random transitions, expected cost
• Value iteration / Policy iteration — infinite-horizon MDPs

338.5. Curse of dimensionality

State has $𝑑$ components with $𝑛$ values each → $|\mathrm{𝒮︀}|={𝑛}^{𝑑}$. DP cost grows exponentially in dimension, not in $𝑇$.

Mitigations: state aggregation, approximate DP, reinforcement learning, function approximation.

338.6. Common applications

• Shortest path on DAG — $𝑂\left(𝑉+𝐸\right)$
• 0-1 Knapsack — pseudo-polynomial $𝑂\left(𝑛𝑊\right)$
• Equipment replacement
• Inventory: Wagner-Whitin lot-sizing
• Resource allocation across activities
• Optimal stopping — secretary problem, asset selling
• Revenue management — see Bellman applied to capacity-time
• Reinforcement learning — MDP foundation

338.7. See also

• Bellman Equation
• Backward Induction
• Stochastic DP
• Value Iteration
• Policy Iteration