
| policy                | representation   | hor izon            | problem   | complexity   |
|-----------------------|------------------|---------------------|-----------|--------------|
| Partial observability |                  |                     |           |              |
| stationary            | -pp.             | not unless P=NP     |           |              |
| stationary            | not unless P=NP  |                     |           |              |
| above-avg, value      |                  |                     |           |              |
| time-dependent        | -pp.             | not unless P=NP     |           |              |
| history-dependent     | -pp.             | not unless P=PSPACE |           |              |
| stationary            | not unless P=NP  |                     |           |              |
| -pp.                  |                  |                     |           |              |
| time-dependent        | -p.              | uncomputable        |           |              |
| (Madani et al., 1999) |                  |                     |           |              |
| Unobser vability      |                  |                     |           |              |
| time-dependent        | -pp.             | not unless P=NP     |           |              |
| Full observability    |                  |                     |           |              |
| stationary            | -additive app.   | P-hard              |           |              |
| stationary            | TBN              | -dditive app.       | EXP-hard  |              |

## 1.1 Heuristics And Approximations

The state of the art with respect to POMDP policy-finding algorithms is that there are three types of algorithms in use or under investigation: exact algorithms, approximations, and heuristics. Exact algorithms attempt to find exact solutions. In the finite-horizon cases, they run in worst-case time at least exponential in the size of the POMDP and the horizon (assuming a straightforward representation of the POMDP). In the infinite horizon, they do not necessarily halt, but can be stopped when the policy is within optimal (a checkable condition). Approximation algorithms construct approximations to what the exact algorithms find. (Examples of this include grid-based methods, Hauskrecht, 1997; Love oy, 1991; White, 1991.) Heuristics come in two  avors: those that construct or find actual policies that can be evaluated, and those that specify a means of choosing an action (for example,  most likely state"), which do not yield policies that can be evaluated using the standard, linear algebra-based methods.

The best current exact algorithm is incremental pruning (IP) with point-based improvement (  hang, Lee, &   hang, 1999). Littman's analysis of the witness algorithm (Littman, Dean, & aelbling, 1995; Cassandra, aelbling, & Littman, 1995) still applies: This algorithm requires exponential time in the worst case.  The underlying theory of these algorithms (Witness, IP, etc.) for infinite-horizon cases depends on Bellman's and Sondik's work on value iteration for MDPs and POMDPs (Bellman, 1957; Sondik, 1971; Smallwood & Sondik, 197 ).

The best known family of approximation algorithms is known as grid methods. The basic idea is to use a finite grid of points in the belief space (the space of all probability distributions over the states of the POMDP this is the underlying space for the algorithms mentioned above) to define a policy.  Once the grid points are chosen, all of these algorithms use value iteration on the points to obtain a policy for those belief states, then interpolate to the whole belief space. The difference in the algorithms lies in the choice of grid points. (An excellent survey appears in Hauskrecht, 1997.) These algorithms are called