to one action (Figure 12b). The QMDP update rule (for the belief state MDP) for V, with linear functions α ξ ∈ Γ is:

$$\widehat{V}_{i\,+1}(b)=\max_{a\,\in\,A}\,\sum_{s\,\in\,S}\,b(s)\left[\rho(\,s,a\,)+\gamma\,\sum_{s^{\prime}\,\in\,S}P\left(s^{\prime}|s,a\,\right)\max_{\alpha_{i}\,\in\,\Gamma_{i}}\,\alpha_{i}\left(s^{\prime}\right)\right]\,$$ $$=\left(H_{\,Q\,M\,D\!P}\,\widehat{V}_{i}\right)(b).$$

HOMDP generates a value function with | A | linear functions. The time complexity of the update is the same as for the MDP-approximation case - O ( A || S | 2 + | Γ i || S |), which reduces to O ( A ll S l 2 ) time when only QMDP updates are used. H QMDP is a contraction mapping and its fixed-point solution can be found by solving the corresponding fully observable MDP.

The QMDP update upper-bounds the exact update. The bound is tighter than the MDP update; that is, HV; ≤ HQMDPV; ≤ HMDPV; as we prove later in Theorem 9. The same inequalities hold for both fixed-point solutions (through Theorem 6).

To illustrate the difference in the quality of bounds for the MDP approximation and the QMDP method, we use our Maze20 navigation problem. To measure the quality of a bound we use the mean of value-function values.  Since all belief states are equally important we assume that they are uniformly distributed. We approximate this measure using the average of values for a fixed set of N = 2000 belief points. The points in the set were selected uniformly at random at the beginning.  Once the set was chosen, it was fixed and remained the same for all tests (here and later). Figure 13 shows the results of the experiment; we include also results for the fast informed bound method that is presented in the next section. 15 Figure 13 also shows the running times of the methods. The methods were implemented in Common Lisp and run on Sun Ultra 1 workstation.

## 4.1.3 C Ontrol

The MDP and the QMDP value-function approximations can be used to construct controllers based on one-step lookahead. In addition, the QMDP approximation is also suitable for the direct control strategy, whi selects an action corresponding to the best (highest value) Q-function. Thus, the method is a special case of the Q-function approach discussed in Section 3.1.3. 16  The advantage of the direct QMDP method is that it is faster than both lookahead designs.  On other the hand, lookahead tends to improve the control performance. This is shown in Figure 14, which compares the control performance of different controllers on the Maze20 problem.

The quality of a policy be measured by the mean of value-function values for 7 and uniformly distributed initial belief states.  We approximate this measure using the average of discounted rewards for