Skip to content

Richard Bellman and Dynamic Programming

Abstract

In the early 1950s at the RAND Corporation, Richard Bellman created dynamic programming: the principle that a hard multi-stage decision problem can be solved by working backwards, reusing the answers to overlapping subproblems instead of recomputing them. The Bellman equation became one of the most consequential equations in applied mathematics; it schedules airline crews, aligns DNA sequences, decodes your phone’s error-correcting codes, and sits at the mathematical core of the reinforcement learning behind AlphaGo. Bellman also left computing one of its best-loved naming stories (that he chose the deliberately meaningless name “dynamic programming” to hide mathematics from a research-hating Secretary of Defense) a story that is his own, and probably not quite true.

RAND and the Multi-Stage Problem

Richard Ernest Bellman (1920–1984), a Brooklyn-born mathematician with a Princeton PhD, joined the RAND Corporation in Santa Monica in the late 1940s, when RAND was the Air Force’s think tank for the mathematics of the Cold War. The problems RAND cared about (allocating missiles, scheduling logistics, controlling inventories) shared a structure: decisions unfold over stages, and each choice changes the situation facing the next choice.

Bellman’s insight, developed in a stream of papers from the early 1950s and consolidated in his book Dynamic Programming (1957), was the principle of optimality: an optimal policy has the property that, whatever the first decision, the remaining decisions must be optimal for the state that results. This turns one enormous problem into a cascade of small ones, solved backwards from the end. Where subproblems overlap, each is solved once and its answer stored, the memoization pattern every computer science student now learns.

The compact statement of this recursion is the Bellman equation: the value of a state equals the best available immediate payoff plus the (discounted) value of the state it leads to. He also coined the term for the method’s great enemy: the “curse of dimensionality”, the exponential explosion of state spaces as problems grow realistic.

The Name

Myth: “Dynamic programming” was named to fool a math-hating Secretary of Defense

The story comes from Bellman’s own 1984 autobiography Eye of the Hurricane: Secretary of Defense Charles Wilson “had a pathological fear and hatred of the word ‘research,’” so Bellman chose a name to shield RAND’s mathematics from Washington: “dynamic” because it was impossible to use pejoratively (“it’s impossible to use the word dynamic in a pejorative sense”), “programming” as in planning; “something not even a Congressman could object to.” The trouble is chronology: Bellman used the term in print by 1952, and Wilson only became Secretary of Defense in 1953, as Russell and Norvig note, the story “cannot be strictly true.” The name more plausibly follows the era’s ordinary usage, in which a “program” was a schedule or plan (exactly as in linear programming) and “dynamic” flagged problems evolving over time. Bellman was a superb raconteur; his best-known anecdote is best read as self-mythology with a grain of truth. See Myths and Misconceptions.

The Equation That Ate the World

Few pieces of 1950s military mathematics have compounded like this one:

  • Shortest paths. The Bellman–Ford algorithm (with Lester Ford Jr.) finds shortest paths even with negative edge weights, and (as “distance-vector routing”) ran the early Internet’s routing protocols. Its greedy cousin is Dijkstra’s algorithm.
  • Sequence alignment. The Needleman–Wunsch and Smith–Waterman algorithms of bioinformatics are dynamic programming on strings; so is the edit distance underlying every spell checker and diff.
  • Signals and codes. The Viterbi algorithm (dynamic programming over hidden states) decodes convolutional codes in every modem and phone, and drove classical speech recognition.
  • Control and economics. Optimal control’s Hamilton–Jacobi–Bellman equation and the recursive methods of modern macroeconomics are the continuous-state descendants.
  • Reinforcement learning. Value iteration, Q-learning, and the temporal-difference methods behind AlphaGo and modern RL are algorithms for solving the Bellman equation when the model is unknown. Every “value function” in an RL paper is Bellman’s value function.

The Second Act

In 1965 Bellman left RAND for the University of Southern California. He was staggeringly prolific, over 600 papers and around 40 books, on subjects stretching into mathematical biology and medicine. In 1973 he underwent surgery for a brain tumor; the operation’s complications left him severely disabled, yet he continued working for the remaining decade of his life, dictating mathematics he could no longer write. He received the IEEE Medal of Honor in 1979, cited specifically for dynamic programming. He died on March 19, 1984.

His method’s fate is an irony he would have appreciated: conceived to plan Cold War logistics under a name chosen (at least in legend) to mean nothing, “dynamic programming” is now among the most-searched terms in computer science, mostly by students preparing for coding interviews at companies whose recommendation engines run on his equation.

📚 Sources