A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let be a dynamic programming state, the allowed actions at time , the immediate reward, and the next dynamic programming state. With terminal time and terminal reward , the deterministic finite-horizon Bellman equation isHere measures total reward from time through the terminal reward. Start with and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.
In a Markov decision process, the next dynamic programming state is random. If denotes the expected immediate reward and is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities , the continuation term is . Taking gives the undiscounted finite-horizon problem. With a discount factor , rewards steps ahead carry a factor , including the terminal reward. A maximizing action for each specifies a Markov policy, which contains decisions rather than just optimal scores.
For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards , and a discount factor , the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and , the Bellman equation is merely , so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.
For a finite Markov decision process under fixed policy , bounded reward vector and , splitting the discounted return at its first step gives . A stochastic matrix has supremum-norm operator bound one, so converges and . This is policy evaluation, not optimization over actions.
The operator performs one exact fixed-policy backup. Since each row of averages component differences, . The Banach fixed-point theorem then gives a unique bounded fixed point for .
This one-step operator combines immediate cost with optimized discounted continuation. It is monotone. For nonnegative costs, iterating it from zero produces increasing finite-horizon values bounded above by the infinite-horizon value. If a nonnegative fixed point has a minimizing measurable selector, repeated conditional expectation and dropping the nonnegative terminal value show that the corresponding stationary policy costs no more than that fixed point. Thus the infinite-horizon value, when the Bellman equation holds, is the least nonnegative fixed point.
For nonnegative rewards, a nonnegative value satisfying the maximizing Bellman equation dominates every competing policy, even for . Iterate the one-step inequality, discard the nonnegative terminal value, then apply the monotone convergence theorem to the accumulated reward.
For a controlled ordinary differential equation , running cost and terminal cost , a smooth optimal value function satisfiesThis is the continuous-time Bellman equation. Split the cost into a short initial interval and the optimal continuation. Expanding the continuation by the chain rule, dividing by the interval length and taking its limit yields the equation. The optimization acts on the control at the current state and time.
For and running cost , the minimized expression is . Completing the square gives the minimizing control and the equation . The quadratic ansatz leads to linear-quadratic optimal control. [ref]
Underactuated Robotics by Russ Tedrake. Underactuated Robotics, chapter8, basic HJB derivation and finite-horizon formulation
For a controlled diffusion process , the corresponding equation adds inside the infimum. A value function need not be differentiable; the viscosity solution formulation handles many such cases. A classical verification argument additionally requires the candidate feedback to be admissible and to attain the indicated infimum.
For a nonnegative classical solution of a finite-horizon Hamilton-Jacobi-Bellman equation with nonnegative running reward , the process is a local supermartingale under every admissible control. The Itô formula gives nonpositive drift because the chosen control cannot exceed the supremum in the equation. Stop where the stochastic integral becomes a true martingale, take expectations and apply the Fatou lemma. Nonnegativity prevents loss of a lower bound when removing the stops, giving the verification upper bound. A maximizing control attains the bound when its stopped reward processes are uniformly integrable.
A standard finite-horizon linear-quadratic problem uses linear dynamics and minimizeswhere are symmetric positive semidefinite matrices and is positive-definite. The control input is unrestricted in Euclidean space. These hypotheses, rather than the word quadratic alone, make the control minimization well posed.
The value function has the quadratic form . Substitution into the Hamilton-Jacobi-Bellman equation and completion of the control square giveThus a backward matrix Riccati equation gives a linear feedback control. [ref]
Underactuated Robotics by Russ Tedrake. Underactuated Robotics by Russ Tedrake, chapter8, Finite-horizon LQR
For the scalar system , terminal cost zero and running cost , the solution is and . Differentiation verifies . Infinite-horizon formulas need additional stabilizability and detectability conditions; they do not follow from an arbitrary quadratic cost.
A backward scalar or matrix recurrence for the quadratic coefficients in a value function for a linear-quadratic optimal control problem. It results from completing the control square in the Bellman equation. Multiplicative noise modifies the quadratic coefficients through its second moments.
Articles by others on the same topic
The Bellman equation is a fundamental concept in dynamic programming and reinforcement learning, named after Richard Bellman. It describes the relationship between the value of a decision and the value of future decisions in a given state. The equation provides a recursive way to compute the optimal policy and the value function for a Markov Decision Process (MDP).