Atlas record: https://www.aitimeline.dev/en/events/evt-0085/
Research · 1957
Dynamic Programming
Bellman stated the principle of optimality: an optimal solution is made of optimal solutions for the rest of the path.
Why it matters
Sequential decision problems acquired the decomposition that state-value estimation in reinforcement learning is built on.
The book also introduces the phrase curse of dimensionality for the growth of computation with the number of state variables. The Bellman equation later became the basis of temporal-difference methods; Samuel's checkers program used that kind of update, without the name.
The principle itself is older than the book: Bellman states it in RAND paper P-550, dated 30 July 1954, the text of an address to the American Mathematical Society on 2 September 1954 (whatever the initial state and the first decisions, the remaining decisions must form an optimal policy for the state that results). Stuart Dreyfus, in his introduction to the 2010 edition, calls the curse of dimensionality Bellman's phrase and writes that temporal-difference learning, which approximates the optimal value function from observation, was, as far as he knows, never contemplated by Bellman; he does not say that the phrase first appears in this book.
Event record
- Event date
- 1957
- Timeline date
- Event date
- Verification
- Sources gathered automatically · September 17, 2026
- Lines
- ID
- evt-0085
Year of the book.
Sources
- primary Dynamic Programming
Princeton University Press · Published 1957
- primary R. Bellman, The Theory of Dynamic Programming, RAND Corporation Paper P-550, 30 July 1954 (address to the American Mathematical Society, Laramie, 2 September 1954)
The RAND Corporation, Santa Monica · Published July 30, 1954
- secondary S. Dreyfus, Introduction to the 2010 Edition, in R. Bellman, Dynamic Programming, Princeton University Press, 2010, pp. xv-xviii
Princeton University Press · Published 2010
Related events
Later
- Related Some Studies in Machine Learning Using the Game of Checkers 1959links to this record
Updating a position's value from the next position matches Bellman's decomposition.
- Builds on Speech discrimination by dynamic programming 1968links to this record
The paper's title names the method outright, and the 2010 review says the same: Vintsyuk applied dynamic programming to aligning two utterances in time. The machinery is Bellman's.
- Related The Baum-Welch algorithm 1970links to this record
The estimation rests on the same step-by-step decomposition as dynamic programming.
- Related Dynamic time warping 1978links to this record
The alignment is built by dynamic programming.
- Builds on Actor and critic 1983links to this record
The critic implements Bellman's decomposition for sequential decisions.
- Builds on Temporal-difference learning 1988links to this record
The method rests on Bellman's decomposition for sequential decisions.
- Builds on Q-learning 1989links to this record
The algorithm is an incremental approximation of dynamic programming.