The History of AI

Dynamic Programming

Era 2 · AI is born (1943–1979) › Cybernetics, information, and electronic computers

Lineage
Data and learning
Kind
Publication

Who

RAND Corporation

What happened

Richard Bellman, a mathematician at the RAND Corporation, publishes Dynamic Programming with Princeton University Press. It collects the method Bellman had been developing since the early 1950s for multistage decision problems.

Why it mattered

It states the principle of optimality and the functional equation now called the Bellman equation, the mathematical foundation of reinforcement learning.

The full story

At the RAND Corporation, a research center tied to the US Air Force, Bellman studied problems that require a sequence of decisions: how much to produce each month, how to allocate resources over time, what to do at each step of an uncertain process. The number of possible plans grows so fast that comparing them all is impossible.

The central idea is the principle of optimality: "An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision." Put another way, the value of a situation is the best immediate reward plus the value of the situation it leads to. That recursive relation makes it possible to solve the problem backward from the end, stage by stage, instead of examining every plan. Bellman called the underlying difficulty, the explosive growth in the number of states, "the curse of dimensionality."

The first papers on the method came out in 1952 and the book in 1957. That same year Bellman described Markov decision processes, the formal framework in which reinforcement learning is posed today.

In their standard textbook, Sutton and Barto place one of the two roots of reinforcement learning here: Bellman's equations are what the algorithms that learn to play games or control robots approximate.

Leads to

  • Temporal differences (August 1988)

    Documented direct influence

    Sutton and Barto trace one of the roots of reinforcement learning to dynamic programming and the Bellman equation; temporal-difference methods approximate that equation

  • Q-learning (1989)

    Documented direct influence

    Watkins frames reinforcement learning as incremental dynamic programming, and Q-learning is the Bellman equation turned into a learning rule

Threads that pass through here

Sources

Original source

How to cite

“Dynamic Programming.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/bellman-dynamic-programming

This entry was last reviewed on November 13, 2026.

Open in the interactive timeline