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 widely used equations in applied mathematics. It underlies shortest-path routing on the early internet, the sequence-alignment algorithms of genetics, the Viterbi decoder in mobile phones, the economics of decisions over time, and the reinforcement learning behind AlphaGo. Bellman also coined the phrase “curse of dimensionality” for the method’s main weakness, wrote 619 papers and 39 books, and kept working for a decade after brain surgery left him severely disabled. His best-known story, that he chose the name “dynamic programming” to hide mathematics from a research-hating Secretary of Defense, is his own, and the dates do not quite fit.

Brooklyn, Princeton and Los Alamos

Richard Ernest Bellman was born on 26 August 1920 in New York City. His parents, Pearl and John Bellman, ran a small grocery store in Brooklyn. He went to Abraham Lincoln High School, took a BA in mathematics at Brooklyn College in 1941 and an MA at the University of Wisconsin, and during the Second World War worked in the Theoretical Physics Division at Los Alamos. He returned to Princeton and completed his PhD in 1946 under Solomon Lefschetz, with a dissertation on the boundedness of solutions of nonlinear differential and difference equations. His first career was in the theory of differential equations and stability, and he taught for a time at Stanford.

RAND and the Multi-Stage Problem

In 1949 Bellman began working for the RAND Corporation in Santa Monica, the Air Force’s think tank for the mathematics of the Cold War. RAND’s problems (allocating missiles to targets, scheduling logistics, managing inventories, planning maintenance) shared a structure: decisions are made in stages, and each choice changes the situation facing the next one. Trying every sequence of decisions was hopeless even for small problems.

Bellman’s answer was the principle of optimality, stated in his 1957 book: “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.” It turns one enormous problem into a cascade of small ones solved backwards from the end. If the best way to finish from every possible intermediate state is known, the best first move can be chosen by trying each option and adding the known value of the state it leads to. Where the same subproblems appear in many places, each is solved once and its answer stored, the technique computer science students now learn as memoization.

The method has a compact statement, the Bellman equation: the value of a state equals the best available immediate payoff plus the (discounted) value of the state it leads to. Bellman published “On the Theory of Dynamic Programming” in the Proceedings of the National Academy of Sciences in August 1952, in a paper communicated by John von Neumann, followed by applications to logistics in 1954 and the book Dynamic Programming (Princeton University Press, 1957). In the same year he published “A Markovian Decision Process”, which applied the method to problems in which the outcome of each decision is random. The resulting Markov decision process became the standard mathematical model of sequential decisions under uncertainty.

The book also named the method’s enemy. The number of states grows exponentially with the number of variables describing a state, so a problem that is easy with three variables can be impossible with thirty. Bellman called this the “curse of dimensionality”, and the phrase has since spread to statistics and machine learning for any problem in which high dimensions defeat an otherwise workable method.

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’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 the title of a paper in 1952, and Wilson became Secretary of Defense only in 1953. As Russell and Norvig note, the story “cannot be strictly true.” The name more plausibly follows the ordinary usage of the time, in which a “program” was a schedule or plan (as in linear programming) and “dynamic” marked problems that evolve over time. Bellman was a gifted storyteller, and his best-known anecdote is best read as self-mythology with a grain of truth. See Myths and Misconceptions.

Where the Equation Went

  • Shortest paths and routing. In “On a Routing Problem” (1958) Bellman applied dynamic programming to finding the shortest path between cities: each city repeatedly updates its distance to the destination from its neighbors’ distances, converging after at most N − 1 rounds. Lester Ford Jr. had published the same idea in 1956, and the method is known as the Bellman–Ford algorithm. Unlike Dijkstra’s algorithm it works with negative edge weights. Because each node needs only its neighbors’ information, it can run as a distributed protocol. It was the original routing algorithm of the ARPANET in 1969, and the Routing Information Protocol, standardized in RFC 1058 in June 1988, uses it as “distance-vector” routing.
  • Sequence alignment. The Needleman–Wunsch (1970) and Smith–Waterman (1981) algorithms that compare DNA and protein sequences are dynamic programs over two strings, and so is the edit distance used by spelling checkers and diff.
  • Signals and speech. The Viterbi algorithm (1967) finds the most probable sequence of hidden states by dynamic programming. It decodes convolutional error-correcting codes in modems and mobile phones and was the core of classical speech recognition.
  • Control and economics. The Hamilton–Jacobi–Bellman equation is the continuous-time version of the Bellman equation and the foundation of optimal control. Modern macroeconomics uses recursive Bellman-equation methods to model households and firms planning over time.
  • Reinforcement learning. Value iteration, policy iteration, Q-learning and temporal-difference learning are methods for solving the Bellman equation when the model of the world is unknown and must be learned from experience (see Barto and Sutton). The value networks of AlphaGo estimate a Bellman value function.

Mathematics in Every Direction

Bellman was extraordinarily productive by any measure: over his career he published 619 papers and 39 books. He wrote on stability theory, matrix analysis, invariant imbedding, control theory, mathematical economics and, increasingly, biology and medicine, where he saw problems of drug dosing and physiology as control problems. In 1967 he founded the journal Mathematical Biosciences.

In 1965 he left RAND for the University of Southern California, where he held professorships in mathematics, electrical engineering and medicine. He received the John von Neumann Theory Prize in 1976 and the IEEE Medal of Honor in 1979, cited for dynamic programming; the American Automatic Control Council later named its Richard E. Bellman Control Heritage Award after him.

In 1973 Bellman was found to have a brain tumor. The surgery removed it but left him severely disabled. He continued working, publishing more than a hundred papers in the eleven years that remained to him, and wrote his autobiography, Eye of the Hurricane, published in 1984. He died in Los Angeles on 19 March 1984, aged 63.

Dead End

The curse of dimensionality was the limit Bellman named himself. Dynamic programming in its classical form requires a table with an entry for every possible state, and for most real control and planning problems that table is far too large to compute or store. For decades this confined exact dynamic programming to problems with a few state variables, or to special structures such as strings and graphs where the states are naturally few.

The way out came from approximation rather than from Bellman’s exact method. Operations researchers developed “approximate dynamic programming”, which represents the value function with a compact formula instead of a table, and reinforcement learning researchers learned value functions from samples. In the 2010s deep neural networks became the approximating functions, and systems such as DeepMind’s Atari player and AlphaGo solved Bellman equations over state spaces far too large to enumerate. The equation survived; the table did not.

📚 Sources