In the above tests we focused on lookahead controllers only. However, an alternative way to define a controller for grid-based interpolation-extrapolation methods is to use Q-function approximations instead of value functions, and either direct or lookahead designs. 25 function approximations can be found by solving the same grid-based MDP, and by keeping values (functions) for different actions separate at the end.

## 4.6  Approximations Of Value Functions Using Curve Fitting (Least-Squares Fit)

An alternative way to approximate a function over a continuous space is to use curve-fitting techniques.  This approach relies on a predefined parametric model of the value function and a set of values associated with a finite set of (grid) belief points G. The approach is similar to interpolation-extrapolation techniques in that it relies on a set of belief-value pairs. The difference is that the curve fitting, instead of remembering all belief-value pairs, tries to summarize them in terms of a given parametric function model. The strategy seeks the best possible match between model parameters and observed point values. The best match can be defined using various criteria, most often the least-squares fit criterion, where the objective is to minimize

$$E r r o r(f)=\frac{1}{2}\sum_{j}\left[y_{j}-\,f(\,b_{j}\,)\right]^{2}\,.$$

Here b i and y i correspond to the belief point and its associated value. The index j ranges over all points of the sample set G.

4.6.1 COMBINING DYNAMIC PROGRAMMING AND LEAST-SQUARES FIT
The least-squares approximation of a function can be used to construct a dynamic-programming agorithm with an update step: Vi+1 = HLSFVi. The approach has two steps. First, we obtain new values for a set of sample points G :

$$\varphi_{i+1}(b)=(H\widehat{V}_{i})(b)=\operatorname*{max}_{a\in A}\left\{\,\sum_{t\in S}\rho(s,a)b(s)+\gamma\sum_{o\in\Theta}\sum_{t\in S}P(o|s,a)b(s)\widehat{V}_{i}(\tau(b,a,o))\right\}\,.$$

Second, we fit the parameters of the value-function model Vi+1 using new sample-value pairs and the square-error cost function. The complexity of the update is O(|G||A||S|2|O|CEval(K)+
CFit(Vi+1,|G|)) time, where CEval(Vi) is the computational cost of evaluating Vi and CF i t (Vi+1, [G]) is the cost of fitting parameters of Vi+1 to [G] belief-value pairs.

The advantage of the approximation based on the least-squares fit is that it requires us to compute updates only for the finite set of belief states. The drawback of the approach is that, when combined with the value-iteration method, it can lead to instability and/or divergence. This has been shown for MDPs by several researers (Bertsekas, 1994; Boyan
& Moore, 1995; Baird, 1995; Tsitsiklis & Roy, 1996).