
## 3. Value Function Approximation

This section describes the basic methods for value function approximation. MDPs used in practical applications are often too large for the optimal policy to be computed precisely. In these cases, we first calculate an approximate value function ˜v and then take the greedy policy π with respect to it. The quality of such a policy can be characterized using its value function vπ in one of the following two main ways.

Definition 5 (Policy Loss). Let π be a policy computed from value function approximation.

The *expected policy loss* measures the expected loss of π, defined as follows:

$$\|v^{*}-v_{\pi}\|_{1,\alpha}=\alpha^{\mathsf{T}}v^{*}-\alpha^{\mathsf{T}}v_{\pi}$$
$$\left(1\right)$$
$$=\sum_{i}|c(i)x(i)|.$$
$$\left(2\right)$$
Tvπ (1)
where kxk1,c denotes the weighted L1 norm: ||xk1,c =Pi|c(i)x(i)|.

The *robust policy loss* measures the worst-case loss of π, defined as follows:

$$\|v^{*}-v_{\pi}\|_{\infty}=\operatorname*{max}_{s\in{\mathcal{S}}}|v^{*}(s)-v_{\pi}(s)|$$

∗(s) − vπ(s)| (2)
The expected policy loss captures the total loss of discounted reward when following the policy π instead of the optimal policy assuming the initial distribution. The robust policy loss ignores the initial distribution and, in some sense, measures the difference for the worst-case initial distribution.

A set of state features is a necessary component of value function approximation. These features must be supplied in advance and must capture the essential structure of the problem. The features are defined by mapping each state s to a vector φ(s) of features. We denote φi: S → R to be a function that maps states to the value of feature i:

$$\phi_{i}(s)=(\phi(s))_{i}.$$

The desirable properties of the features depend strongly on the algorithm, samples, and attributes of the problem; the tradeoffs are not yet fully understood. The function φi can also be treated as a vector, similarly to the value function v.

Value function approximation methods compute value functions that can be represented using the state features. We call such value functions *representable* and define them below.

Definition 6. Given a *convex* polyhedral set M ⊆ R
|S|, a value function v is *representable*
(in M) if v ∈ M.

Many methods that compute a value function based on a given set of features have been developed, such as neural networks and genetic algorithms (Bertsekas and Ioffe, 1997). Most of these methods are extremely hard to analyze, computationally complex, and hard to use.

Moreover, these complex methods do not satisfy the convexity assumption in Definition 6.

A simpler, more common, method is *linear value function approximation*. In linear value function approximation, the value function of state s is represented as a linear combination of *nonlinear features* φ(s). Linear value function approximation is easy to apply and analyze.

Linear value function approximation can be expressed in terms of matrices as follows.

Let the matrix Φ : *|S|×*m represent the features for the state-space, where m is the number of features. The rows of the feature matrix Φ, also known as the *basis*, correspond to the