Dynamic Programming

Authors: Richard Bellman
Year: 1957
Source: Princeton University Press

Contributions

Formulated the Principle of Optimality: the sub-policy of an optimal policy is itself optimal for the corresponding sub-problem
Introduced the Bellman equation: recursive decomposition of value functions that enables sequential decision-making
Coined the term “curse of dimensionality” to describe exponential growth of state space with problem dimensionality
Founded the mathematical framework that underlies modern reinforcement learning (value iteration, policy iteration, Q-learning)

Mathematical analysis of multi-stage decision processes over discrete and continuous time
Reformulated optimization problems as functional equations (Bellman equations)
Proved convergence of value iteration under standard regularity conditions
Applied the framework to control theory, economics, operations research, and engineering problems

Demonstrated that optimal control problems can be solved by backward induction through the state space
Established conditions under which value functions exist and are unique fixed points of the Bellman operator
Showed that stochastic sequential decision problems (Markov Decision Processes) admit tractable solutions via dynamic programming
Created algorithmic tools (value iteration, policy iteration) that remain central to RL today

Exponential growth of the state-action space makes exact dynamic programming intractable for high-dimensional problems (curse of dimensionality)
Requires a known model of the environment (transition probabilities and rewards) — a limitation later addressed by model-free RL
Continuous state-action spaces require discretization or function approximation, introducing approximation error
Assumes the Markov property — full state information — which is violated in partially observable environments