

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

algorithms (see Se tion 2.4.2). However, in the exa t ase, a set of points that over all linear fun tions dening the new value fun tion must be lo ated rst, whi h is a hard task in itself. In ontrast, the approximation method uses an in omplete set of belief points that are xed or at least easy to lo ate, for example via random or heuristi sele tion. We use HGL to denote the value-fun
tion mapping for the grid approa
h.

The advantage of the grid-based method is that it leads to more eÆ
ient updates. The time omplexity of the update is polynomial and equals O(jGjjAjjSj 2 jj). It yields a set of jGj linear fun tions, ompared to jAjji j jj possible fun tions for the exa t update.

Sin e the set of grid-points is in omplete, the resulting approximation lower-bounds the value fun tion one would obtain by performing the exa t update (Lovejoy, 1991a).

Theorem 13 (Lower-bound property of the grid-based linear fun tion update). Let Vbi be a pie ewise linear value fun tion and G a set of grid points used to ompute linear fun tion updates. Then HGLVbi  HVbi.

## 4.7.1 In Remental Linear-Fun Tion Approa H

The drawba k of the grid-based linear fun tion method is that HGL is not a 
ontra
tion for the dis ounted innite-horizon ase, and therefore the value iteration method based on the mapping may not onverge (Lovejoy, 1991a). To remedy this problem, we propose an in remental version of the grid-based linear fun tion method. The idea of this renement is to prevent instability by gradually improving the pie ewise linear and onvex lower bound of the value fun tion.

Assume that Vbi  V is a 
onvex pie
ewise linear lower bound of the optimal value fun tion dened by a linear fun tion set i, and let b be a linear fun
tion for a point b that is omputed from Vbi using Sondik's method. Then one 
an 
onstru
t a new improved value fun tion bVi+1  bVi by simply adding the new linear fun
tion binto i. That is:
i+1 = i [ b. The idea of the in
remental update, illustrated in Figure 23, is similar to in remental methods used by Cheng (1988) and Lovejoy (1993). The method an be
