for the bound quality, there are no big differences among various heuristics, suggesting a small sensitivity of control to the selection of grid points.

## 4.8  Summary Of Value-Function Approximations

Heuristic value-function approximations methods allow us to replace hard-to-compute exact methods and trade off solution quality for speed. There are numerous methods we can employ, each with different properties and different trade-offs of quality versus speed. Tables 1 and 2 summarize main theoretical properties of the approximation methods covered in this paper. The majority of these methods are of polynomial complexity or at least have efficient (polynomial) Bellman updates. This makes them good candidates for more complex POMDP problems that are out of reach of exact methods.

All of the methods are heuristic approximations in that they do not give solutions of a guaranteed precision. Despite this fact we proved that solutions of some of the methods are no worse than others in terms of value function quality (see Figure 15).  This was one of the main contributions of the paper. However, there are currently minimal theoretical results relating these methods in terms of control performance; the exception are some results for FSM-controllers and FSM-based approximations. The key observation here is that for the quality of control (lookahead control) it is more important to approximate the shape
(derivatives) of the value function correctly. This is also illustrated empirically on gridbased interpolation-extrapolation methods in Section 4.5.9 that are based on non-convex value functions.  The main challenges here are to find ways of analyzing and comparing control performance of different approximations also theoretically and to identify classes of POMDPs for which certain methods dominate the others.

Finally, we note that the list of methods is not complete and other value-function approximation methods or the refinements of existing methods are possible. For example, White and Scherer (1994) investigate methods based on truncated histories that lead to upper and lower bound estimates of the value function for complete information states (complete histories). Also, additional restrictions on some of the methods can change the properties of a more generic method. For example, it is possible that under additional assumptions we will be able to ensure convergence of the least-squares fit approximation.

## 5. Conclusions

POMDPs offers an elegant mathematical framework for representing decision processes in stochastic partially observable domains. Despite their modeling advantages, however, POMDP problems are hard to solve exactly. Thus, the complexity of problem solvingprocedures becomes the key aspect in the sucessful application of the model to real-world problems, even at the expense of the optimality.  As recent complexity results for the approximability of POMDP problems are not encouraging (Lusena et al., 1998; Madani et al., 1999), we focus on heuristic approximations, in particular approximations of value functions.