at some point of the belief space and we would like to find the best interpolation (leading to the best values) for all grid points in G . In such a case, the corresponding "optimal" grid-based MDP cannot be found in a single step and iterative approximation, solving a sequence of grid-based MDPs, is usually needed.  The worst-case complexity of this problem remains an open question.

## 4.5.5 Constructing Grids

An issue we have not toued on so far is the selection of grids. There are multiple ways to select grids. We divide them into two classes - regular and non-regular grids.

Regular grids (Lovejoy, 1991a) partition the belief space evenly into equal-size regions. 22 The main advantage of regular grids is the simplicity with which we can locate grid points in the neighborhood of any belief point. The disadvantage of regular grids is that they are restricted to a specific number of points, and any increase in grid resolution is paid for in an exponential increase in the grid size. For example, a sequence of regular grids for a 20-dimensional belief space (corresponds to a POMDP with 20 states) consists of 20, 210, 1540, 8855, 42504,     grid points. 23  This prevents one from using the method with higher grid resolutions for problems with larger state spaces.

Non-regular grids are unrestricted and thus provide for more flexibility when grid resolution must be increased adaptively. On the other hand, due to irregularities, methods for locating grid points adjacent to an arbitrary belief point are usually more complex when compared to regular grids.

## 4.5.6 L Inear P Oint I Nterp Olation

The fact that the optimal value function V* is convex for a belief-state MDPs can be used to show that the approximation based on linear point interpolation always upper-bounds the exact solution (Lovejoy, 1991a, 1993). Neither kernel regression nor nearest neighbor can guarantee us any bound.

Theorem 12 (Upper bound property of a grid-based point interpolation update). Let Vi be a convex value function. Then HVj ≤ HGVj.

The upper-bound property of H c update for convex value functions follows directly from Jensen's inequality. The convergence to an upper-bound follows from Theorem 6.

Note that the point-interpolation update imposes an additional constraint on the choice of grid points. In particular, it is easy to see that any valid grid must also include extreme points of the belief simplex (extreme points correspond to (1,0,0,  ), (0,1,0,  ),