

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

## 4.7  Grid-Based Approximations With Linear Function Updates

An alternative grid-based approximation method can be constructed by applying Sondik's approach for computing derivatives (linear functions) to points of the grid (Lovejoy, 1991a, 1993). Let Vi be a piecewise linear convex function described by a set of linear functions Fi.

Then a new linear function for a belief point b and an action a can be computed efficiently as (Smallwood & Sondik, 1973; Littman, 1996)

$$\alpha^{b,a}_{i+1}(s)=\rho(s,a)+\gamma\sum_{o\in\Theta}\sum_{s^{\prime}\in S}P(\,s^{\prime},o|s,a)\alpha^{\prime}_{i}{}^{(b,a,o)}(\,s^{\prime}),\tag{10}$$

where ι( b,α, σ ) indexes a linear function α in a set of linear functions Γ i (defining V ) that maximizes the expression

$$\sum_{s^{\prime}\in S}\left[\sum_{s\in S}P\left(s^{\prime},o|s,a\right)b\!\left(s\right)\right]\alpha_{i}\!\left(\,s^{\prime}\,\right)$$

for a fixed combination of b, a, o.  The optimizing function for b is then acquired by choosing the vector with the best overall value from all action vectors. That is, assuming Γ f +1 is a set of all candidate linear functions, the resulting functions satisfies

$$\alpha_{i+1}^{b,s}=\arg\operatorname*{max}_{\alpha_{i\,+1}^{b}\in\Gamma_{i\,+1}^{b}}\sum_{s\in S}\alpha_{i\,+1}^{b}(\,s\,)b(\,s\,).$$

A collection of linear functions obtained for a set of belief points can be combined into a piecewise linear and convex value function. This is the idea behind a number of exact