= Bellman operator
{c}
{title2=$(TV)(s)$}
A Bellman operator maps a proposed <value function> to the value obtained by one optimal decision followed by that proposed continuation value. For a finite discounted <Markov decision process> with bounded reward $r$, transition probabilities $P$, discount $0\leq\gamma<1$ and nonempty finite action sets,
$$
(TV)(s)=\max_a\left(r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s')\right).
$$
The optimal <value function> satisfies the <Bellman equation> $V^*=TV^*$. The cost-minimization convention replaces the maximum by a minimum.
For any $V,W$, the difference between the two maxima is bounded by the maximum difference of their terms, so $\|TV-TW\|_\infty\leq\gamma\|V-W\|_\infty$. The <Banach fixed-point theorem> gives a unique fixed point and convergence of value iteration in this finite setting. In a single state with reward two and discount one-half, $TV=2+V/2$, hence $V^*=4$. Undiscounted problems require different conditions; the same contraction argument does not apply at $\gamma=1$.
Back to article page
