control performance. These studies should help focus theoretical exploration by discovering interesting cases and possibly identifying classes of problems for which certain approximations are more or less suitable. Our preliminary experimental results show that there are significant differences in control performance among different methods and that not all of them may be suitable to approximate the control policies. For example, the grid-based nneerest-neighbor approach with piecewise-constant approximation is typically inferior to and outperformed by other simpler (and more efficient) value-function methods.

The present work focused on heuristic approximation methods. We investigated general (flat) POMDPs and did not take advantage of any additional structural refinements.

However, real-world problems usually offer more structure that can be exploited to devise new algorithms and perhaps lead to further speed-ups. It is also possible that some of the restricted versions of POMDPs (with additional structural assumptions) can be solved or approximated efficiently, even though the general complexity results for POMDPs or their εapproximations are not very encouraging (Papadimitriou & Tsitsiklis, 1987; Littman, 1996; Mundhenk et al., 1997; Lusena et al., 1998; Madani et al., 1999). A allenge here is to identify models that allow efficient solutions and are at the same time interesting enough from the point of application.

Finally, a number of interesting issues arise when we move to problems with large state, action, and observation spaces. Here, the complexity of not only value-function updates but also belief state updates becomes an issue. In general, partial observability of hidden process states does not allow us to factor and decompose belief states (and their updates), en when transitions have a great deal of structure and can be represented very compactly. Promising directions to deal with these issues include various Monte-Carlo approaches (Isard
& Blake, 1996; Kanazawa, Koller, & Russell, 1995; Doucet, 1998; Kearns et al., 1999)), methods for approximating belief states via decomposition (Boyen & Koller, 1998, 1999),
or a combination of the two approaches (McAllester & Singh, 1999).

## Acknowledgements

Anthony Cassandra, Thomas Dean, Leslie Kaelbling, William Long, Peter Szolovits and anonymous reviewers provided valuable feedback and comments on this work. This research was supported by grant RO1 LM 04493 and grant 1T15LM07092 from the National Library of Medicine, by DOD Advanced Research Project Agency (ARPA) under contract number N66001-95-M-1089 and DARPA/Rome Labs Planning Initiative grant F30602-95-1-0020.

## Appendix A. Theorems And Proofs A.1  Convergence To The Bound

Theorem 6 Let H1 and H2 be two value-function mappings defined on V1 and V2 s.t.

1. H 1 , H 2 are contractions with fixed points V 2 , V 2 ,
2.  Vi* E V2  and H2Vi* ≥ H1Vi* = Vi*;
3. H2 is an isotone mapping Then V2* > V1* holds.