

![0_image_0.png](0_image_0.png)

The drawback of this approach is that interpolations may remain unchanged for many update steps, thus slowing down the solution process. An alternative approach is to solve a sequence of grid-based MDPs instead. In particular, at every stage we find the best (minimum value) interpolations for all belief points reachable from grid points in one step, fix cefficients of these interpolations ( λ s ), construct a grid-based MDP and solve it (exactly or approximately). This process is repeated until no further improvement (or no improvement larger than some threshold) is seen in values at different grid points.

## 4.5.8 Improving Grids Adaptively

The quality of an approximation (bound) depends strongly on the points used in the grid.

Our objective is to provide a good approximation with the smallest possible set of grid points. However, this task is impossible to achieve, since it cannot be known in advance
(before solving) what belief points to pick. A way to address this problem is to build grids incrementally, starting from a small set of grid points and adding others adaptively, but only in places with a greater chance of improvement. The key part of this approach is a heuristic for choosing grid points to be added next.

One heuristic method we have developed attempts to maximize improvements in bound values via stochastic simulations. The method builds on the fact that every interpolation grid must also include extreme points (otherwise we cannot cover the entire belief space). As extreme points and their values affect the other grid points, we try to improve their values in the first place. In general, a value at any grid point b improves more the more precise values are used for its successor belief points, that is, belief states that correspond to r(b,a*,o) for a choice of observation o. a* is the current optimal action choice for b.

Incorporating such points into the grid then makes a larger improvement in the value at the initial grid point b more likely. Assuming that our initial point is an extreme point, we have a heuristic that tends to improve a value for that point. Naturally, one can proceed further with this selection by incorporating the successor points for the first-level successors into the grid as well, and so forth.