

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

for comparison.
extended to handle a set of grid points G in a straightforward way. Note also that after adding one or more new linear functions to Γ i , some of the previous linear functions may become redundant and can be removed from the value function. Techniques for redundancy checking are the same as are applied in the exact approaches (Monahan, 1982; Eagle, 1984).

The incremental refinement is stable and converges for a fixed set of grid points. The price paid for this feature is that the linear function set Γ i can grow in size over the iteration steps. Although the growth is at most linear in the number of iterations, compared to the potentially exponential growth of exact methods, the linear function set describing the piecewise linear approximation can become huge. Thus, in practice we usually stop incremental updates well before the method converges.  The question that remains open is the complexity (hardness) of the problem of finding the fixed-point solution for a fixed set of grid points G.

Figure 24 illustrates some of the trade-offs involved in applying incremental updates compared to the standard fixed-grid approach on the Maze20 problem. We use the same grid of 40 points for both techniques and the same initial value function. Results for 1-10 update cycles are shown. We see that the incremental method has longer running times than the standard method, since the number of linear functions can grow after every update. On the other hand, the bound quality of the incremental method improves more rapidly and it can never become worse after more update steps.

## 4.7.2 Minimum Expected Reward

The incremental method improves the lower bound of the value function. The value function, say Vi, can be used to create a controller (with either the lookahead or direct-action choice). In the general case, we cannot say anything about the performance quality of such controllers with regard to . . However, under certain conditions the performance of both controllers is guaranteed never to fall below . The following theorem (proved in the Appendix) establishes these conditions.

Theorem 14 Let V, be a value function obtained via the incremental linear function method, starting from Vo, which corresponds to some fixed strategy Co. Let CLA, and CDR, be two