
## 4.6.2  On-Line Version Of The Least-Squares Fit

The problem of finding a set of parameters with the best fit can be solved by any available optimization procedure. This includes the on-line (or instance-based) version of the gradient descent method, which corresponds to the well-known delta rule (Rumelhart, Hinton, &
Williams, 1986).

Let f denote a parametric value function over the belief space with adjustable weights w = { w 1 , w 2 , . . , w k }. Then the on-line update for a weight w i is computed as:

$$w_{i}\gets w_{i}-\alpha_{i}(f(b_{j})-y_{j}){\frac{\partial f}{\partial w_{i}}}|_{b_{j}},$$

where α is a learning constant, and b i and y i are the last-seen point and its value. Note that the gradient descent method requires the function to be differentiable with regard to adjustable weights.

To solve the discounted infinite-horizon problem, the stochastic (on-line) version of a least-squares fit can be combined with either parallel (synchronous) or incremental (Gauss-
Seidel) point updates. In the first case, the value function from the previous step is fixed and a new value function is computed from scratch using a set of belief point samples and their values computed through one-step expansion.  Once the parameters are stabilized (by attenuating learning rates), the newly acquired function is fixed, and the process proceeds with another iteration. In the incremental version, a single value-function model is at the same time updated and used to compute new values at sampled points.  Littman et al.  (1995)
and Parr and Russell (1995) implement this approach using asynchronous reinforcement learning backups in which sample points to be updated next are obtained via stochastic simulation.  We stress that all versions are subject to the threat of instability and divergence, as remarked above.

## 4.6.3 Parametric Function Models

To apply the least-squares approach we must first select an appropriate value function model. Examples of simple convex functions are linear or quadratic functions, but more complex models are possible as well.

One interesting and relatively simple approach is based on the least-squares approximation of linear action-value functions (Q-functions) ( Littman et al., 1995).  Here the value function V i +1 is approximated as a piecewise linear and convex combination of Q i +1 functions:

$${\widehat{V}}_{i+1}(b)=\operatorname*{max}_{a\in A}{\widehat{Q}}_{i+1}(b,a),$$

where Qi+1(b, a) is the least-squares fit of a linear function for a set of sample points G. Values at points in G are obtained as

$$\varphi_{i+1}^{a}(\,b\,)=\rho(\,b,a\,)+\gamma\sum_{o\in\Theta}P(\,o|b,a\,)\tilde{V}_{i}\bigl(\,\tau\bigl(b,o,a\,\bigr)\bigr).$$

The method leads to an approximation with | A | linear functions and the coefficients of these functions can be found efficiently by solving a set of linear equations. Recall that other two approximations (the QMDP and the fast informed bound approximations) also work with