The many approximation methods and their combinations can be divided into two often very closely related classes: value-function approximations and policy approximations.

## 3.1 Value-Function Approximations

The main idea of the value-function approximation approach is to approximate the optimal value function V : I → R with a function V : I → R defined over the same information space. Typically, the new function is of lower complexity (recall that the optimal or nearoptimal value function may consist of a large set of linear functions) and is easier to compute than the exact solution. Approximations can be often formulated as dynamic programming problems and can be expressed in terms of approximate value-function updates H. Thus, to understand the differences and advantages of various approximations and exact methods, it is often sufficient to analyze and compare their update rules.

## 3.1.1 Value- Function  Bound S

Although heuristic approximations have no guaranteed precision, in many cases we are able to say whether they overestimate or underestimate the optimal value function. The information on bounds can be used in multiple ways.  For example, upper- and lowerbounds can help in narrowing the range of the optimal value function, elimination of some of the suboptimal actions and subsequent speed-ups of exact methods. Alternatively, one can use knowledge of both value-function bounds to determine the accuracy of a controller generated based on one of the bounds (see Section 3.1.3). Also, in some instances, a lower bound alone is sufficient to guarantee the control choice that always achieves an expected reward at least as high as the one given by that bound (Section 4.7.2).

The bound property of different methods can be determined by examining the updates and their bound relations.

Definition 5 (Upper bound). Let H be the exact value-function mapping and H its approximation.  We say that H upper-bounds H for some V when ( HV )( b ) ≥ ( HV )( b ) holds for every b E I.

An analogous definition can be constructed for the lower bound.

## 3.1.2 Convergence Of Approximate Value Iteration

Let H be a value-function mapping representing an approximate update. Then the approximate value iteration computes the ith value function as Vj = HVj_j. The fixed-point solution V* = HV* or its close approximation would then represent the intended output of the approximation routine. The main problem with the iteration method is that in general it can converge to unique or multiple solutions, diverge, or oscillate, depending on H and the initial function V . Therefore, unique convergence cannot be guaranteed for an arbitrary mapping H and the convergence of a specific approximation method must be proved.

Definition 6 (Convergence of H). The value iteration with H converges for a value function Vo when limn→∞(HnVo) exists.