easier to manipulate and store, since unlike complete histories, they may not expand with time. For example, in the standard POMDP model it is sufficient to work with belief states that assign probabilities to every possible process state (Astrom, 1965). 2 In this case the Bellman equation reduces to:

$$V(b)=\max_{a\,\in\,\hat{A}}\left\{\sum_{s\,\in\,S}\rho(s,a)b(s)+\gamma\sum_{o\,\in\,\Theta}\sum_{s\,\in\,S}P\big{(}o|s,a\big{)}b(s)V\big{(}\tau(b,o,a)\big{)}\right\}\,,\tag{5}$$

where the next-step belief state V is

$$b^{\prime}(s)=\tau\,(b,o,a)(s)=\beta P(o|s,a)\sum_{s^{\prime}\in S}P(s|a,s^{\prime})b(s^{\prime}).$$

β = 1/P(olb,a) is a normalizing constant.  This defines a belief-state MDP which is a special case of a continuous-state MDP. Belief-state MDPs are also the primary focus of our investigation in this paper.

2.3.2 VALUE-FUNCTION MAPPINGS AND THEIR PROPERTIES
The Bellman equation 2 for the belief-state MDP can be also rewritten in the value-function mapping form. Let V be a space of real-valued bounded functions V : I → R defined on the belief information space I , and let h : I × A × B → IR be defined as

$$h(b,a,V)=\sum_{s\in S}\rho(s,a)b(s)+\gamma\sum_{o\in\Theta}\sum_{s\in S}P(o|s,a)b(s)V(\tau(b,o,a)).$$

Now by defining the value function mapping H : V → V as ( HV )( b ) = max e A h ( b, a, V ),
the Bellman equation 2 for all information states can be written as V* = HV*. It is well known that H (for MDPs) is an isotone mapping and that it is a contraction under the supremum norm (see (Heyman & Sobel, 1984; Puterman, 1994)). Definition 3 The mapping H is isolone, if V, U E V and V ≤ U implies HV ≤ HU. Definition 4 Let ‖.‖ be a supremum norm. The mapping H is a contraction under the supremum norm, if for all V,U E V, || HV - HU || ≤ β || V - U || holds for some 0 ≤ β < 1.

## 2.4 Value Iteration

The optimal value function (Equation 2) or its approximation can be computed using dy -
namic programming techniques. The simplest approach is the value iteration (Bellman, 1957) shown in Figure 3. In this case, the optimal value function V* can be determined in the limit by performing a sequence of value-iteration steps Vi = HVi-1, where Vi is the ith approximation of the value function (ith value function). 3 The sequence of estimates