
## 5.1 Contributions

The paper surveys new and known value-function approximation methods for solving POMDPs. We focus primarily on the theoretical analysis and comparison of the methods, with findings and results supported experimentally on a problem of moderate size from the agent nvigation domain. We analyze the methods from different perspectives: their computational complexity, capability to bound the optimal value function, convergence properties of iterative implementations, and the quality of derived controllers. The analysis includes new theoretical results, deriving the properties of individual approximations, and their relations to exact methods. In general, the relations between and trade-offs among different methods are not well understood. We provide some new insights on these issues by analyzing their corresponding updates. For example, we showed that the differences among the exact, the MDP, the QMDP, the fast-informed bound, and the UMDP methods boil down to simple mathematical manipulations and their subsequent effect on the value-function approximation. This allowed us to determine relations among different methods in terms of quality of their respective value functions which is one of the main results of the paper.

We also presented a number of new methods and heuristic refinements of some existing techniques. The primary contributions in this area include the fast-informed bound, gridbased point interpolation methods (including adaptive grid approaches based on stochastic sampling), and the incremental linear-function method. We also showed that in some instances the solutions can be obtained more efficiently by converting the original approximation into an equivalent finite-state MDP. For example, grid-based approximations with convex rules can be often solved via conversion into a grid-based MDP (in which grid points correspond to new states), leading to the polynomial-complexity algorithm for both the finite and the discounted infinite-horizon cases (Section 4.5.3). This result can dramatically improve the run-time performance of the grid-based approaches. A similar conversion to the equivalent finite-state MDP, allowing a polynomial-time solution for the discounted infinite-horizon problem, was shown for the fast informed bound method (Section 4.2).

## 5.2  Challenges And Future Directions

Work on POMDPs and their approximations is far from complete. Some complexity results remain open, in particular, the complexity of the grid-based approach seeking the best interpolation, or the complexity of finding the fixed-point solution for the incremental version of the grid-based linear-function method. Another interesting issue that needs more investigation is the convergence of value iteration with least-squares approximation. Although the method can be unstable in the general case, it is possible that under certain restrictions it will converge.

In the paper we use a single POMDP problem (Maze20) only to support theoretical findings or to illustrate some intuitions. Therefore, the results not supported theoretically (related mostly to control) cannot be generalized and used to rank different methods, since their performance may vary on other problems. In general, the area of POMDPs and POMDP approximations suffers from a shortage of larger-scale experimental work with multiple problems of different complexities and a broad range of methods. Experimental work is especially needed to study and compare different methods with regard to control quality. The main reason for this is that there are only few theoretical results relating the