Bellman’s Principle of Optimality

Bellman’s “Principle of Optimality” [Bel57] belongs to the core knowledge we expect from every computer science graduate.

– Towards a Discipline of Dynamic Programming; Giegerich et al.

[Bel57] R. Bellman. Dynamic Programming. Princeton University Press, 1957.

From a Wikipedia page for Bellman equations:

A Bellman equation (also known as a dynamic programming equation), named after its discoverer, Richard Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. Almost any problem which can be solved using optimal control theory can also be solved by analyzing the appropriate Bellman equation. The Bellman equation was first applied to engineering control theory and to other topics in applied mathematics, and subsequently became an important tool in economic theory.

[mathematical formulation]

[Bellman’s] principle asserts that if [a] policy function is optimal for the infinite summation, then it must be the case that whatever the initial state and decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from that first decision (as expressed by the Bellman equation). The principle of optimality is related to the concept of optimal substructure, and problems that exhibit optimal substructure can often be solved with dynamic programming.