etc.). Without extreme points one would be unable to cover the whole belief space via interpolation. Nearest neighbor and kernel regression impose no restrictions on the grid.

## 4.5.7  Finding The Best Interpolation

In a general, there are multiple ways to interpolate a point of a belief space. Our objective is to find the best interpolation, that is, the one that leads to the tightest upper bound of the optimal value function.

Let b be a belief point and {( b j , f ( b j )) | b j ∈ G } a set of grid-value pairs. Then the best interpolation for point b is:

$${\widehat{f}}(b)=\operatorname*{min}_{\lambda}\sum_{j=1}^{|G|}\lambda_{j}f(b_{j})$$
subject to $0\leq\lambda_{j}\leq1$ for all $j=1,\cdots,|G|$, $\sum_{j=1}^{|G|}\lambda_{j}=1$, and $b=\sum_{j=1}^{|G|}\lambda_{j}b_{j}^{G}$.  
This is a linear optimization problem. Although it can be solved in polynomial time
(using linear programming techniques), the computational cost of doing this is still relatively large, especially considering the fact that the optimization must be repeated many times. To alleviate this problem we seek more efficient ways of finding the interpolation, sacrificing the optimality.

One way to find a (suboptimal) interpolation quickly is to apply regular grids proposed by Lovejoy (1991a). In this case the value at a belief point is approximated using the convex combination of grid points closest to it.  The approximation leads to piecewise linear and convex value functions. As all interpolations are fixed here, the problem of finding the approximation can be converted into an equivalent grid-based MDP and solved as a finite-state MDP. However, as pointed in the previous section, the regular grids must use a specific number of grid points and any increase in the resolution of a grid is paid for by an exponential increase in the grid size. This feature makes the method less attractive when we have a problem with a large state space and we need to achieve high grid resolution. 24 In the present work we focus on non-regular (or arbitrary) grids. We propose an interpolation approach that searches a limited space of interpolations and is guaranteed to run in time linear in the size of the grid. The idea of the approach is to interpolate a point b of a belief space of dimension [ S ] with a set of grid points that consists of an arbitrary grid point b ′ ∈ G and | S | − 1 extreme points of the belief simplex. The coefficients of this interpolation can be found efficiently and we sear for the best su interpolation. Let V E G be a grid point defining one such interpolation. Then the value at point b satisfies

$${\hat{V}}_{i}(b)=\operatorname*{min}_{b^{\prime}\in G}{\hat{V}}_{i}^{b^{\prime}}(b),$$

where V, b is the value of the interpolation for the grid point V. Figure 17 illustrates the resulting approximation. The function is characterized by its "sawtooth" shape, which is influenced by the choice of the interpolating set.

To find the best value-function solution or its close approximation we can apply a value iteration procedure in which we search for the best interpolation after every update step.