
## 4.5 Grid-Based Approximations With Value Interpolation-Extrapolation

A value fun tion over a ontinuous belief spa e an be approximated by a nite set of grid points G and an interpolation-extrapolation rule that estimates the value of an arbitrary point of the belief spa e by relying only on the points of the grid and their asso iated values.

Denition 8 (Interpolation-extrapolation rule) Let f : I ! IR be a real-valued fun
tion dened over the information spa e I, G = fbG
1 ; bG
2 ;    bG
k g be a set of grid points and 	G =
f(bG
1 ; f (bG
1 )); (bG
2 ; f (bG
2 ));    ; (bG
k ; f (bG
k ))g be a set of point-value pairs. A fun
tion RG :
I - (I - IR)

jGj ! IR that estimates f at any point of the information spa
e I using only values asso iated with grid points is al led an interpolation-extrapolation rule.

The main advantage of an interpolation-extrapolation model in estimating the true value fun tion is that it requires us to ompute value updates only for a nite set of grid points G. Let Vbi be the approximation of the ith value fun
tion. Then the approximation for the
(i + 1)th value fun tion bVi+1 
an be obtained as

$$\hat{V}_{i+1}(b)=R_{G}(\,b,\,\Psi_{i+1}^{G}\,),$$

where values asso iated with every grid point bG
j 2 G (and in
luded in 	G
i+1) are:

$$\varphi_{i+1}(b_{j}^{G})=(H\widehat{V}_{i})(b_{j}^{G})=\max_{a\in A}\left\{\rho(b,a)+\gamma\sum_{o\in\Theta}P(o|b,a)\widehat{V}_{i}(\tau(b_{j}^{G},o,a))\right\}.\tag{9}$$

The grid-based update an also be des ribed in terms of a value-fun tion mapping HG:
Vbi+1 = HGVbi. The 
omplexity of su
h an update is O(jGjjAjjSj 2 jjCEval(RG; jGj)) where CEval(RG; jGj) is the 
omputational 
ost of evaluating the interpolation-extrapolation rule RG for jGj grid points. We show later (Se
tion 4.5.3), that in some instan
es, the need to evaluate the interpolation-extrapolation rule in every step an be eliminated.

## 4.5.1 A Family Of Convex Rules

The number of all possible interpolation-extrapolation rules is enormous. We fo us on a set of onvex rules that is a relatively small but very important subset of interpolationextrapolation rules.20 Denition 9 (Convex rule) Let f be some fun
tion dened over the spa
e I, G = fbG
1 ; bG
2 ;    bG
k g be a set of grid points, and 	G = f(bG
1 ; f (bG
1 )); (bG
2 ; f (bG
2 ));    ; (bG
k ; f (bG
k ))g be a set of pointvalue pairs. The rule RG for estimating f using 	Gis 
al led 
onvex when for every b 2 I,
the value b f (b) is:

$$\widehat{f}(b)=R_{G}(b,\Psi^{G})=\sum_{j=1}^{|G|}\lambda_{j}^{b}f(b_{j}),$$  _such that $0\leq\lambda_{j}^{b}\leq1$ for every $j=1,\cdots,|G|$, a and $\sum_{j=1}^{|G|}\lambda_{j}^{b}=1$._

