features of the states φ(s). The feature matrix can be defined in one of the following two ways:

$$\Phi=\begin{pmatrix}-&\phi(s_{1})^{\mathsf{T}}&-\\ -&\phi(s_{2})^{\mathsf{T}}&-\\ &\vdots&\end{pmatrix}\qquad\qquad\Phi=\begin{pmatrix}|&|\\ \phi_{1}&\phi_{2}&\dots\\ |&|\end{pmatrix}$$

The value function v is then represented as v = Φx and the set of representable functions is M = colspan (Φ).

The goal of value function approximation is not just to obtain a good value function v˜ but a policy with a small policy loss. Unfortunately, the policy loss of a greedy policy, as formulated in Definition 5, depends non-trivially on the approximate value function ˜v. Often, the only reliable method of precisely computing the policy loss is to simulate the policy, which can be very costly. Value function approximation methods, therefore, optimize bounds on the policy loss.

Theorem 7. [Robust Policy Loss, e.g. (Williams and Baird, 1994)] Let π *be a greedy policy* with respect to a value function v˜*. Then:*

$$\|v^{*}-v_{\pi}\|_{\infty}\leq\frac{2}{1-\gamma}\|\tilde{v}-L\tilde{v}\|_{\infty}.$$  _Iciy loss is minimized for the speed 
In addition, if v˜ ∈ K*, the policy loss is minimized for the greedy policy and:*

$$\|v^{*}-v_{\pi}\|_{\infty}\leq\frac{1}{1-\gamma}\|\tilde{v}-L\tilde{v}\|_{\infty}.$$
1 − γ
The bounds above ignore the initial distribution and may often be overly conservative. We establish new bounds on the expected policy loss that also consider the initial distribution.

Theorem 8. [Expected Policy Loss] Let π *be a greedy policy with respect to a value function* v˜ and let the state-action visitation frequencies of π be bounded as u ≤ uπ ≤ u¯*. Then:*

$$\begin{array}{c}{{\|v^{*}-v_{\pi}\|_{1,\alpha}=\alpha^{\mathsf{T}}v^{*}-\alpha^{\mathsf{T}}\tilde{v}+u_{\pi}^{\mathsf{T}}\left(\tilde{v}-L\tilde{v}\right)}}\\ {{\qquad\qquad\leq\alpha^{\mathsf{T}}v^{*}-\alpha^{\mathsf{T}}\tilde{v}+\underline{{{u}}}^{\mathsf{T}}\left[\tilde{v}-L\tilde{v}\right]_{-}+\bar{u}^{\mathsf{T}}\left[\tilde{v}-L\tilde{v}\right]_{+}.}}\end{array}$$

The state-visitation frequency uπ depends on the initial distribution α*, unlike* v
∗. In addition, when v˜ ∈ K*, the bound is:*

$$\begin{array}{l}{{\|v^{*}-v_{\pi}\|_{1,\alpha}\leq-\|v^{*}-\tilde{v}\|_{1,\alpha}+\|\tilde{v}-L\tilde{v}\|_{1,\tilde{u}}}}\\ {{\|v^{*}-v_{\pi}\|_{1,\alpha}\leq-\|v^{*}-\tilde{v}\|_{1,\alpha}+\frac{1}{1-\gamma}\|\tilde{v}-L\tilde{v}\|_{\infty}}}\end{array}$$

Here we use [x]+ = max{x, 0} componentwise.

Proof. The bound is derived as follows:

α Tv ∗ − α Tvπ = α Tv ∗ − α Tvπ + (u T π(I − γPπ) − α T)˜v = α Tv ∗ − r T π uπ + (u T π(I − γPπ) − α T)˜v = α Tv ∗ − r T π uπ + u T π(I − γPπ)˜v − α Tv˜ = α Tv ∗ − α Tv˜ + u T π((I − γPπ)˜v − rπ) = α Tv ∗ − α Tv˜ + u T π(˜v − Lv˜).