Definition 3.2 A projection operator Π is a mapping Π : RN → H. Π **is said to be a**
projection w.r.t. a norm k·k if ΠV = Hw∗such that w∗ ∈ arg minw kHw **− Vk**.

That is, ΠV is the linear combination of the basis functions, that is closest to V **with respect**
to the chosen norm.

Our approximate policy iteration algorithm performs the policy improvement step exactly. In the value determination step, the value function - **the value of acting according to**
the current policy π
(t) **— is approximated through a linear combination of basis functions.**
We now consider the problem of value determination for a policy π
(t)**. At this point,**
it is useful to introduce some notation: Although the rewards are a function of the state and action choice, once the policy is fixed, the rewards become a function of the state only, which we denote as Rπ(t) , where Rπ(t) (x) = R(x, π(t)(x**)). Similarly, for the transition**
model: Pπ(t) (x
′| x) = P(x
′| x, π(t)(x**)). We can now rewrite the value determination step**
in terms of matrices and vectors. If we view Vπ(t) and Rπ(t) as N-vectors, and Pπ(t) **as an**
N × N **matrix, we have the equations:**
Vπ(t) = Rπ(t) + γPπ(t)Vπ(t) .

This is a system of linear equations with one equation for each state, which can only be solved exactly for relatively small N**. Our goal is to provide an approximate solution, within**
H**. More precisely, we want to find:**

w
$$\begin{array}{r l}{{}}&{{}={}}\quad\arg\operatorname*{min}_{\mathbf{w}}\|\mathrm{{H}}\mathbf{w}-(R_{\pi^{(t)}}+\gamma P_{\pi^{(t)}}\mathrm{{H}}\mathbf{w})\|\,;}\end{array}$$
$$\begin{array}{r l}{={}}&{{}\arg\operatorname*{min}_{\mathbf{w}}\left\|\left(\mathrm{H}-\gamma P_{\pi^{(t)}}\mathrm{H}\right)\mathbf{w}^{(t)}-R_{\pi^{(t)}}\right\|.}\end{array}$$
Thus, our approximate policy iteration alternates between **two steps:**
$$\begin{array}{r c l}{{\mathbf{w}^{(t)}}}&{{=}}&{{\arg\operatorname*{min}_{\mathbf{w}}\|\mathbf{H}\mathbf{w}-(R_{\pi^{(t)}}+\gamma P_{\pi^{(t)}}\mathbf{H}\mathbf{w})\|\,;}}\\ {{\pi^{(t+1)}}}&{{=}}&{{G r e e d y(\mathbf{H}\mathbf{w}^{(t)}).}}\end{array}$$
$$\left(2\right)$$
$$\left({\mathrm{3}}\right)$$
3.2.3 Max-norm Projection An approach along the lines described above has been used in various papers, with several recent theoretical and algorithmic results (Schweitzer & Seidmann, 1985; Tsitsiklis & Van Roy, 1996b; Van Roy, 1998; Koller & Parr, 1999, 2000). However, these approaches suffer from a problem that we might call "norm incompatibility." When computing the projection, they utilize the standard Euclidean projection operator with respect to the L2 **norm or a**
weighted L2 norm.1 On the other hand, most of the convergence and error analyses **for MDP**
algorithms utilize max-norm (L∞**). This incompatibility has made it difficult to provide**
error guarantees.

We can tie the projection operator more closely to the error bounds through the use of a projection operator in L∞ norm. The problem of minimizing the L∞ **norm has been**
studied in the optimization literature as the problem of finding the Chebyshev solution2to