Bellman Equation

The Bellman equation is the mathematical expression of the **principle of optimality** that Richard Bellman formalized in his 1957 book (*Dynamic Programming*, Princeton University Press): an optimal policy has the property that whatever the initial state and decision are, the remaining decisions must form an optimal policy with respect to the resulting state. For a finite-horizon deterministic problem it reads V*(s) = max_a { r(s, a) + V*(s') }, where V*(s) is the optimal total return from state s, r(s, a) the immediate reward, and s' the state after action a. For an infinite-horizon discounted problem it reads V*(s) = max_a { r(s, a) + γ E[V*(s')] }, with γ ∈ (0, 1) the discount factor. For stochastic decision processes (Markov Decision Processes, MDP) Bellman and Dreyfus (1962) and Bertsekas (1995) *Dynamic Programming and Optimal Control* are the standard references; the Hamilton-Jacobi-Bellman PDE is the continuous-time differential form of the same principle for stochastic control. Classical solution algorithms for the Bellman equation include value iteration (table-based recursive update), policy iteration (Howard 1960 alternative), and the linear-programming reformulation (Manne 1960). The Bellman equation is the common core of inventory (Wagner-Whitin lot-sizing 1958), equipment replacement (Bellman 1955), travelling salesman (Held-Karp DP 1962), portfolio selection (Merton 1969), and every dynamic-programming application in OR/CS. Stochastic dual dynamic programming (SDDP, Pereira and Pinto 1991) and approximate dynamic programming (Powell 2007) are modern approaches for high-dimensional Bellman equations.