
| Method                                         | Bound   | Isotonicity   | Contraction   |
|------------------------------------------------|---------|---------------|---------------|
| MDP approximation                              | upper   |               |               |
| QMDP approximation                             | upper   | >             | >             |
| Fast informed bound                            | upper   | >             |               |
| >                                              |         |               |               |
| UMDP approximation                             | lower   | v             | v             |
| Fixed-strategy method                          | lower   | >             | >             |
| Grid-based interpolation-extrapolation         |         |               |               |
| Nearest neighbor                               | >       |               |               |
| Kernel regression                              | v       | >             |               |
| Linear point interpolation                     | upper   | v             | v             |
| Curve-fitting (least-squares fit)              |         |               |               |
| linear Q-function                              |         |               |               |
| Grid-based linear function method              | lower   |               |               |
| Incremental version (start from a lower bound) | lower   | >             |               |

Table 1: Properties of different value-function approximation methods: bound property, isotonicity and contraction property of the underlying mappings for 0 < γ < 1. (*) Although incremental version of the grid-based linear-function method is not a contraction it always converges.

| Method                                 | Finite-horizon   | Discounted infinite-horizon   |
|----------------------------------------|------------------|-------------------------------|
| MDP approximation                      | P                | P                             |
| QMDP approximation                     | P                | P                             |
| Fast informed bound                    | P                |                               |
| F                                      |                  |                               |
| UMDP approximation                     | NP-hard          | udd and the                   |
| Fixed-strategy method                  | F                | P                             |
| Grid-based interpolation-extrapolation | NA               |                               |
| varies                                 |                  |                               |
| Nearest neighbor                       | F                | P                             |
| Kernel regression                      | P                | P                             |
| Linear point interpolation             | F                | varies                        |
| Fixed interpolation                    | P                | P                             |
| Best interpolation                     | E                |                               |
| Curve-fitting (least-squares fit)      | varies           | NA                            |
| linear Q-function                      | F                | NA                            |
| NA                                     |                  |                               |
| Grid-based linear function method      | P                |                               |
| Incremental version                    | N A              |                               |

Table 2: Complexity of value-function approximation methods for finite-horizon problem and discounted infinite-horizon problem. The objective for the discounted infinitehorizon case is to find the corresponding fixed-point solution.  The complexity results take into account, in addition to components of POMDPs, also all other approximation specific parameters, e.g., the size of the grid G in grid-based methods. ? indicates open instances and NA methods that are not applicable to one of the problems (e.g. because of possible divergence).