##  [Dynamic Programming](/dynamic-programming-1) 

 Definition

A recursive optimization framework that decomposes multistage decision problems into overlapping subproblems solved by backward or forward induction, centralizing the value function as the object encoding optimal future returns.

 

 

 

 

 

 





## Principle

Principle

Bellman's principle of optimality: an optimal policy has the property that, whatever the initial state and decision, the remaining decisions constitute an optimal policy with regard to the state resulting from the first decision; recursion on value functions implements this.

 

 

 

 

 





## Demonstration

Demonstration

In finite-horizon optimal control, compute the cost-to-go V_t(x) by backward induction: V_T(x)=terminal cost, and V_t(x)=min_u{ stage_cost(x,u)+V_{t+1}(f(x,u)) } until t=0, yielding an optimal sequence of controls.

 

 

 

 

## Misapplication

Misapplication

Treating non-Markov problems as if they were Markov without state augmentation, or attempting exact tabular DP in very high-dimensional spaces without approximation (the curse of dimensionality), leads to incorrect or infeasible solutions.

 

 

 

 

 





## Consequence

Consequence

Correct application yields optimal policies and value functions, tractable decompositions for many structured problems, and foundations for algorithms in control and reinforcement learning, but may require approximation for large-scale problems.

 

 

 

 

## Reversal

Reversal

Greedy or myopic methods make locally optimal choices without solving the recursion and therefore typically fail to find globally optimal multistage strategies when future costs significantly influence current decisions.

 

 

 

 

 





## Boundary

Boundary

Applies when the problem admits stagewise decomposition and a Markovian transition structure or an equivalent state augmentation; excludes directly partially observed problems or non-separable objectives without reformulation.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension with approximate dynamic programming and reinforcement learning: DP provides exact recursion and guarantees when feasible, while approximations trade optimality for tractability and generalization to high-dimensional or stochastic environments.

 

 

 

 

 





## Synthesis

Synthesis

Dynamic Programming = use Bellman's optimality to express global multistage optimization as recursive local problems on value functions, solve by backward/forward induction or iterative backups, and manage complexity via approximation when needed.