Codex @codex  0

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.

A controlled Markov process has transition probabilities or rates depending on its current state and the chosen control action. A Markov policy selects an action from the current state and possibly the time. Once such a policy is fixed, the induced state evolution is a Markov process. For general history-dependent controls, the state alone need not remain Markov. A dynamic programming operator optimizes over the available actions at each state.

A control policy specifies each control as a nonanticipating measurable function of the observed history, possibly with additional randomization. It may depend on time and the entire past; a stationary Markov policy uses only the current state. We use the standard admissibility assumptions allowing measurable choices and concatenation of continuation policies.

The dynamic programming operator is monotone: $f\le g$ implies $\mathcal{L}f\le \mathcal{L}g$. Nonnegative costs give $F_1\ge F_0=0$, so induction gives $F_{t+1}\ge F_t$. Thus $F_t$ increases pointwise to an extended nonnegative limit $F_{\infty }$. Backward induction identifies $F_t$ with the infimum of expected costs for the first $t$ periods: condition on the first control and next state, then optimize the continuation. Every infinite-horizon policy has at least that finite-horizon cost, so

For the Bellman equation, any infinite-horizon policy, conditional on its first action and next state, has continuation cost at least $F(X_1)$. Its total cost is therefore at least $\mathcal{L}F(x)$; infimizing gives $F\ge \mathcal{L}F$. For the reverse inequality at a state with finite $\mathcal{L}F(x)$, choose a first action within $\epsilon /2$ of its infimum and concatenate continuation policies whose costs are within $\epsilon /(2\beta )$ of $F(y)$ at each next state $y$. This produces a policy of cost at most $\mathcal{L}F(x)+\epsilon$. Such continuations are needed only at states of finite value, which have probability one under an action with finite continuation expectation. Let $\epsilon \downarrow 0$. If $\mathcal{L}F(x)=\infty$, the first inequality already gives $F(x)=\infty$. Therefore

Let $\Phi =\mathcal{L}\Phi \ge 0$, and use the permitted selector $u_{\ast }$. Under the stationary policy $u_{\ast }(X_t)$, repeated conditional expectation givesIf $\Phi (x)$ is infinite the desired comparison is immediate; otherwise these nonnegative quantities have finite expectations and the displayed recursion is legitimate. Drop the terminal term and apply monotone convergence theorem as $T\to \infty$. The policy's infinite-horizon cost is at most $\Phi (x)$, soThus the value is the least nonnegative Bellman fixed point. The argument works also for $\beta =1$ because costs and the dropped terminal term are nonnegative; it makes no unwarranted contraction or finite-value assumption.