= Bellman equation
{c}
{title2=$V_t(s)=\max_a\{r_t(s,a)+V_{t+1}(F_t(s,a))\}$}
{wiki}
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> is
$$
V_T(s)=g(s),\qquad
V_t(s)=\max_{a\in A_t(s)}\{r_t(s,a)+V_{t+1}(F_t(s,a))\},
\quad t=T-1,\ldots,0.
$$
Here $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 https://ocw.mit.edu/courses/6-231-dynamic-programming-and-stochastic-control-fall-2015/2beec55b0de261096962e514febe3b5c_MIT6_231F15_Lec2.pdf[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> becomes
$$
V_T(s)=g(s),\qquad
V_t(s)=\max_{a\in A_t(s)}\left\{r_t(s,a)+\beta\mathbb E[V_{t+1}(S_{t+1})\mid S_t=s,\ a_t=a]\right\}.
$$
The <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'\mid s,a)$, the continuation term is $\beta\sum_{s'}p_t(s'\mid s,a)V_{t+1}(s')$. Taking $\beta=1$ gives the undiscounted finite-horizon problem. With a <discount factor> $0\leq\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)|\leq M$, and a <discount factor> $0\leq\beta<1$, the optimal <value function> satisfies
$$
V(s)=\max_{a\in A(s)}\left\{r(s,a)+\beta\sum_{s'}p(s'\mid s,a)V(s')\right\},
\qquad |V(s)|\leq\frac{M}{1-\beta}.
$$
In 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 https://ocw.mit.edu/courses/6-231-dynamic-programming-and-stochastic-control-fall-2015/ec7b70a77571e2f2c48a5a0fa5fa23d5_MIT6_231F15_Lec15.pdf[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.
Back to article page
