Value iteration ( POMDP, c )
initialize  V for all b ∈ I; repeat V ← V;
update V ← HV' for all b ∈ I;
until sup, | V(b) - V'(b) |≤ c return V;
Figure 3: Value iteration procedure.

converges to the unique fixed-point solution which is the direct consequence of Banach's theorem for contraction mappings (see, for example, Puterman (1994)).

In practice, we stop the iteration well before it reaches the limit solution. The stopping criterion we use in our algorithm (Figure 3) examines the maximum difference between value functions obtained in two consecutive steps - the so-called Bellman error (Puterman, 1994; Littman, 1996). The algorithm stops when this quantity falls below the threshold ε . The accuracy of the approximate solution (ith value function) with regard to V* can be expressed in terms of the Bellman error ε.

Theorem 1  Let ε = sup δ | V ( δ ) − V − 1 ( δ ) | = ‖ V i − V i − 1 ‖ be the magnitude of the Bellman error. Then ‖Vi - V*‖ ≤ ¬ ¬ and ‖Vi-1 - V*‖ ≤ ¬ ⇒ hold.

Then, to obtain the approximation of V* with precision δ the Bellman error should fall below  I
2.4.1 PIECEWISE LINEAR AND CONVEX APPROXIMATIONS OF THE VALUE FUNCTION
The major difficulty in applying the value iteration (or dynamic programming) to beliefstate MDPs is that the belief space is infinite and we need to compute an update Vi = HVi-1 for all of it. This poses the following threats: the value function for the ith step may not be representable by finite means and/or computable in a finite number of steps.

To address this problem Sondik (Sondik, 1971; Smallwood & Sondik, 1973) showed that one can guarantee the computability of the ith value function as well as its finite description for a belief-state MDP by considering only piecewise linear and convex representations of value function estimates (see Figure 4). In particular, Sondik showed that for a piecewise linear and convex representation of V i –1, V i = HV i –1 is computable and remains piecewise linear and convex.

Theorem 2 (Piecewise linear and convex functions).  Let Vo be an initial value function that is piecewise linear and convex.  Then the ith value function obtained after a finite number of update steps for a belief-state MDP is also finite, piecewise linear and convex, and is equal to:

$$V_{i}(b)=\operatorname*{max}_{\alpha_{i}\in\Gamma_{i}}\sum_{s\in S}b(s)\alpha_{i}(s),$$
 - $\frac{1}{2}$ . 
where b and ai are vectors of size ISI and Fi is a finite set of vectors (linear functions) ai

