We used the fact that u T
π(I−γPπ)−α T = 0, which follows from the definition of state-action visitation frequencies and that v
∗ ≥ vπ. The inequalities for ˜v ∈ K follow from Lemma 38, Lemma 43, and the trivial version of the Holder's inequality:

$$\begin{array}{l}{{\alpha^{\mathsf{T}}v^{*}-\alpha^{\mathsf{T}}\hat{v}=-\|v^{*}-\hat{v}\|_{1,\alpha}}}\\ {{\ }}\\ {{u_{\pi}^{\mathsf{T}}\left(\hat{v}-L\hat{v}\right)\leq\|u_{\pi}\|_{1}\,\|\hat{v}-L\hat{v}\|_{\infty}=\frac{1}{1-\gamma}\|\hat{v}-L\hat{v}\|_{\infty}\ .}}\end{array}$$
7
Notice that the bounds in Theorem 8 can be minimized even without knowing the optimal v
∗. The optimal value function v
∗is independent of the approximate value function v˜ and the greedy policy π depends only on ˜v.

Remark 9. The bounds in Theorem 8 generalize the bounds established by de Farias (2002, Theorem 1.3), which state that whenever v ∈ K:

$$\square$$
$$\|v^{*}-v_{\pi}\|_{1,u}\leq\frac{1}{1-\gamma}\|v^{*}-\tilde{v}\|_{1,(1-\gamma)u}.$$

This bound is a special case of Theorem 8 because α

$$\alpha^{\mathsf{T}}v^{*}-\alpha^{\mathsf{T}}\tilde{v}\leq0\ \mathrm{and}\ \cdot$$
$\|\tilde{v}-L\tilde{v}\|_{1,u}\leq\|v^{*}-\tilde{v}\|_{1,u}\leq\frac{1}{1-\gamma}\|v^{*}-\tilde{v}\|_{1,(1-\gamma)u}$,  The proof of Theorem 8 shows the proof of Theorem 8.  
from v
∗ ≤ Lv˜ ≤ v˜. The proof of Theorem 8 also simplifies the proof of Theorem 1.3 in
(de Farias, 2002).

The methods that we propose require the following standard assumption.

Assumption 10. All multiples of the constant vector 1 are representable in M. That is, for all k ∈ R we have that k1 ∈ M.

Notice that the representation set M satisfies Assumption 10 when a first column of Φ
is 1. The impact of including the constant feature is typically negligible because adding a constant to the value function does not change the greedy policy.

Value function approximation algorithms are typically variations of the exact algorithms for solving MDPs. Hence, they can be categorized as approximate value iteration, approximate policy iteration, and approximate linear programming. The ideas of approximate value iteration could be traced to Bellman (1957), which was followed by many additional research efforts (Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 1998; Powell, 2007). Below, we only discuss approximate policy iteration and approximate linear programming, because they are the most closely related to our approach.

Approximate policy iteration (API) is summarized in algorithm 1. The function Z(π)
denotes the specific method used to approximate the value function for the policy π. The two most commonly used methods - *Bellman residual approximation* and *least-squares approximation* (Lagoudakis and Parr, 2003) - minimize the L2 norm of the Bellman residual.

The approximations based on minimizing L2 norm of the Bellman residual are common in practice since they are easy to compute and often lead to good results. Most theoretical analyses of API, however, assume minimization of the L∞ norm of the Bellman residual:

$${\mathcal{Z}}(\pi)\in\arg\operatorname*{min}_{v\in{\mathcal{M}}}\|(\mathbf{I}-\gamma P_{\pi})v-r_{\pi}\|_{\infty}$$
k(I − γPπ)v − rπk∞ (3)