Bellman equation ($V_t(s)={\max }_a\{r_t(s,a)+V_{t+1}(F_t(s,a))\}$)

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 $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ 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 $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ 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 $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ 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 $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, 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 $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, 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 $\pi$, bounded reward vector $r^{\pi }$ and $0\le \gamma <1$, splitting the discounted return at its first step gives $V^{\pi }=r^{\pi }+\gamma P^{\pi }{V}^{\pi }$. A stochastic matrix has supremum-norm operator bound one, so ${\sum }_{k\ge 0}(\gamma P^{\pi }{)}^k$ converges and $V^{\pi }=(I-\gamma P^{\pi }{)}^{-1}{r}^{\pi }$. This is policy evaluation, not optimization over actions.

The operator $T^{\pi }V=r^{\pi }+\gamma P^{\pi }V$ performs one exact fixed-policy backup. Since each row of $P^{\pi }$ averages component differences, $\Vert T^{\pi }V-T^{\pi }U{\Vert }_{\infty }\le \gamma \Vert V-U{\Vert }_{\infty }$. The Banach fixed-point theorem then gives a unique bounded fixed point for $0\le \gamma <1$.

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 $\beta \ge 1$. Iterate the one-step inequality, discard the nonnegative terminal value, then apply the monotone convergence theorem to the accumulated reward.

The Hamilton--Jacobi--Bellman equation is the continuous-time Bellman equation. For state dynamics $\dot{x}=f(x,u,t)$, running cost $L(x,u,t)$ and terminal cost $\Phi (x)$, a smooth value function satisfies

For a nonnegative classical solution $V$ of a finite-horizon Hamilton-Jacobi-Bellman equation with nonnegative running reward $r$, the process $V(X_t,t)+{\int }_0^{t}r(X_s,a_s)ds$ 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 linear-quadratic optimal-control problem has linear state dynamics and running and terminal costs defined by quadratic forms. Its value function is quadratic in the state, the optimal feedback is linear, and its coefficient obeys a Riccati equation.

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.