controllers based on Vi: the lookahead controller and the direct action controller, and VCLA,,
VCDR, be their respective value functions. Then V, < VCLA, and V, < VCDR, hold.

We note that the same property holds for the incremental version of exact value iteration.

That is, both the lookahead and the direct controllers perform no worse than Vi obtained after i incremental updates from some V 0 corresponding to a FSM controller C 0 .

## 4.7.3 Selecting Grid Points

The incremental version of the grid-based linear-function approximation is flexible and works for an arbitrary grid. 26  Moreover, the grid need not be fixed and can be changed on line. Thus, the problem of finding grids reduces to the problem of selecting belief points to be updated next. One can apply various strategies to do this. For example, one can use a fixed set of grid points and update them repeatedly, or one can select belief points on line using various heuristics.

The incremental linear function method guarantees that the value function is always improved (all linear functions from previous steps are kept unless found to be redundant). The quality of a new linear function (to be added next) depends strongly on the quality of linear functions obtained in previous steps. Therefore, our objective is to select and order points with better chances of larger improvement. To do this we have designed two heuristic strategies for selecting and ordering belief points.

The first strategy attempts to optimize updates at extreme points of the belief simplex by ordering them heuristically. The idea of the heuristic is based on the fact that states with higher expected rewards (e.g. some designated goal states) backpropagate their effects
(rewards) locally. Therefore, it is desirable that states in the neighborhood of the highest reward state be updated first, and the distant ones later. We apply this idea to order extreme points of the belief simplex, relying on the current estimate of the value function to identify the highest expected reward states and on a POMDP model to determine the nighbor states.

The second strategy is based on the idea of stochastic simulation. The strategy generates a sequence of belief points more likely to be reached from some (fixed) initial belief point.

The points of the sequence are then used in reverse order to generate updates. The intent of this heuristic is to "maximize" the improvement of the value function at the initial fixed point. To run this heuristic, we need to find an initial belief point or a set of initial belief points. To address this problem, we use the first heuristic that allows us to order the extreme points of the belief simplex. These points are then used as initial beliefs for the simulation part. Thus, we have a two-tier strategy: the top-level strategy orders extremes of the belief simplex, and the lower-level strategy applies stochastic simulation to generate a sequence of belief states more likely reachable from a specific extreme point.

We tested the order heuristics and the two-tier heuristics on our Maze20 problem, and compared them also to two simple point selection strategies: the fixed-grid strategy, in which a set of 40 grid points was updated repeatedly, and the random-grid strategy, in which points were always chosen uniformly at random. Figure 25 shows the bound quality