The Bellman equation is a recursive relationship that expresses the value of a sequential decision problem in terms of an immediate reward or cost and the value of the remaining problem. Named after Richard Bellman, it is a foundation of dynamic programming and reinforcement learning. Rather than optimizing an entire sequence of decisions at once, it describes how current choices connect to future outcomes through a value function. Bellman developed this framework during the 1950s, presenting it in his 1957 book Dynamic Programming. (incompleteideas.net)
Principle of optimality
The equation formalizes Bellman’s principle of optimality: after an initial decision and its resulting state, the remaining decisions of an optimal policy must be optimal for the problem beginning at that state. This expresses optimal substructure, which makes recursive solution possible. The criterion ordinarily separates into successive rewards or costs, with a terminal value when applicable. (mit.edu)
The state must contain enough information to determine future possibilities. In a Markov decision process (MDP), the Markov property means that the next-state distribution, conditional on the current state and action, does not additionally depend on earlier history. If necessary information is absent, the state representation may need enlargement before the recursion is valid. (mit.edu)
Policy evaluation
Consider a finite MDP with states (s), available actions (a), transition probabilities (P(s' \mid s,a)), and expected immediate rewards (r(s,a)). A stationary policy (\pi(a\mid s)) specifies the probability of selecting each action. For a discount factor (0\leq\gamma<1), its value is the expected value of the discounted reward sequence:
[ V^\pi(s)= \mathbb E_\pi!\left[ \sum_{k=0}^{\infty}\gamma^k R_{t+k+1} ;\middle|;S_t=s \right]. ]
Separating the first reward from the remaining return gives the Bellman expectation equation:
[ V^\pi(s)= \sum_a\pi(a\mid s) \left[ r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s') \right]. ]
It evaluates a specified policy; it does not optimize over alternative actions. The expectations account for both action selection and uncertain transitions. (incompleteideas.net)
For a finite state space, define the policy-induced transition matrix (P^\pi) and reward vector (r^\pi). Then
[ V^\pi=r^\pi+\gamma P^\pi V^\pi, \qquad (I-\gamma P^\pi)V^\pi=r^\pi. ]
Thus policy evaluation is a system of linear equations, solvable using linear algebra or iterative updates. Here (I) is the identity matrix. (mit.edu)
Optimality equation
The optimal value (V^*(s)) is the greatest expected return achievable from state (s). Its Bellman optimality equation is
[ V^(s)= \max_a \left[ r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^(s') \right]. ]
Unlike policy evaluation, this is generally nonlinear because of the maximization. It reduces sequential optimization to a one-step choice incorporating the optimal continuation value. In a finite discounted MDP, selecting a maximizing action at every state produces an optimal deterministic stationary policy. Different actions can tie, so a unique optimal value does not imply a unique optimal policy. (gradml.mit.edu)
For cost minimization, the analogous equation replaces rewards with costs and (\max) with (\min). In a deterministic system, the expectation over next states reduces to evaluation at the successor state. The equation therefore applies beyond stochastic decision problems. (underactuated.csail.mit.edu)
Horizons and boundary conditions
For a problem ending at time (T), let (g(s)) be its terminal reward. The finite-horizon recursion is
[ V_t^(s)= \max_a\left[ r_t(s,a)+ \gamma\sum_{s'}P_t(s'\mid s,a)V_{t+1}^(s') \right], \qquad V_T^*(s)=g(s). ]
The value and optimal policy may depend on time. Computation proceeds backward from the terminal condition, an instance of backward induction. Unlike an infinite-horizon problem, a finite-horizon problem can use (\gamma=1) without requiring convergence of an infinite reward sum. Boundary conditions also matter in terminating shortest-path problems, where the destination typically has zero remaining cost. (mit.edu)
Fixed points and solution methods
The right-hand side of the optimality equation defines a Bellman operator (T). The equation is consequently a fixed-point condition, (V^=TV^). For finite discounted MDPs with bounded rewards, this operator is a contraction mapping under the maximum norm:
[ |TV-TW|\infty \leq\gamma|V-W|\infty. ]
It therefore has a unique bounded fixed point. Without discounting, or with unbounded rewards, existence and uniqueness require additional assumptions; the equation alone does not guarantee either. (stuff.mit.edu)
Value iteration repeatedly applies (T). Policy iteration instead alternates policy evaluation with improvement by choosing actions that maximize the one-step expression. Both exploit the same recursive structure, but the Bellman equation itself is a characterization of value, not a particular algorithm. (gradml.mit.edu)
Learning, applications, and limitations
When transition probabilities are unknown, temporal-difference learning uses observed transitions to construct sampled Bellman updates. Q-learning applies the optimality relationship to action values, using targets of the form (R+\gamma\max_{a'}Q(s',a')). These methods connect dynamic programming with learning from experience rather than requiring a complete transition model. (web.mit.edu)
In control theory, the continuous-time counterpart is the Hamilton–Jacobi–Bellman equation, a differential equation for optimal value. Bellman-based methods support robotics and other sequential control problems, but large state spaces make exact computation expensive. Function approximation can replace explicit value tables; it also changes the numerical problem, so convergence guarantees for exact discounted updates do not automatically carry over. (underactuated.csail.mit.edu)