 Bellman operator

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\le \gamma <1$ and nonempty finite action sets,The optimal value function satisfies the Bellman equation $V^{\ast }=T{V}^{\ast }$. 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 $\Vert TV-TW{\Vert }_{\infty }\le \gamma \Vert V-W{\Vert }_{\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^{\ast }=4$. Undiscounted problems require different conditions; the same contraction argument does not apply at $\gamma =1$.