an overdetermined linear system of equations (Cheney, 1982). The problem is defined as
finding w∗**such that:**
$$\mathbf{w}^{*}\in\arg\operatorname*{min}_{\mathbf{w}}\|C\mathbf{w}-\mathbf{b}\|_{\infty}\,.$$
wkCw − bk∞ . (4)
We use an algorithm due to Stiefel (1960), that solves this problem by linear programming:
Variables: $\quad w_{1},\ldots,w_{k},\phi$ ;  Minimize: $\quad\phi$ ;  Subject to: $\quad\phi\geq\sum_{j=1}^{k}c_{ij}w_{j}-b_{i}\quad$ and  $\quad\phi\geq b_{i}-\sum_{j=1}^{k}c_{ij}w_{j},\quad i=1...N$.  
$$c_{i j}w_{j}-b_{i}|{\mathrm{~for~each~}}i,$$
The constraints in this linear program imply that φ ≥
Pk j=1 cijwj − bi
 for each i**, or**
equivalently, that φ ≥ kCw − bk∞. The objective of the LP is to minimize φ**. Thus, at the** solution (w∗, φ∗) of this linear program, w∗is the solution of Equation (4) and φ **is the** L∞
projection error.

We can use the L∞ **projection in the context of the approximate policy iteration in the**
obvious way. When implementing the projection operation of **Equation (2), we can use**
the L∞ projection (as in Equation (4)), where C = (H − γPπ(t)H) and b = Rπ(t) **. This**
minimization can be solved using the linear program of (5).

A key point is that this LP only has k + 1 variables. However, there are 2N **constraints,**
which makes it impractical for large state spaces. In the SysAdmin **problem, for example,** the number of constraints in this LP is exponential in the number of machines in the network
(a total of 2 · 2 m constraints for m machines). In Section 4, we show that, in factored **MDPs**
with linear value functions, all the 2N **constraints can be represented efficiently, leading to**
a tractable algorithm.

## 3.2.4 Error Analysis

We motivated our use of the max-norm projection within the approximate policy iteration algorithm via its compatibility with standard error analysis techniques for MDP algorithms.

We now provide a careful analysis of the impact of the L∞ **error introduced by the projection step. The analysis provides motivation for the use of a projection step that directly**
minimizes this quantity. We acknowledge, however, that the **main impact of this analysis**
is motivational. In practice, we cannot provide a priori guarantees that an L∞ **projection**
will outperform other methods.

Our goal is to analyze approximate policy iteration in terms **of the amount of error**
introduced at each step by the projection operation. If the error is zero, then we are performing exact value determination, and no error should accrue. If the error is small, we should get an approximation that is accurate. This result follows from the analysis below. More precisely, we define the projection error as the error resulting from the approximate value determination step:

$$\beta^{(t)}=\left\|\mathrm{H}\mathbf{w}^{(t)}-\left(R_{\pi^{(t)}}+\gamma P_{\pi^{(t)}}\mathrm{H}\mathbf{w}^{(t)}\right)\right\|_{\infty}.$$

Note that, by using our max-norm projection, we are finding the set of weights w(t)**that**
exactly minimizes the one-step projection error β
(t)**. That is, we are choosing the best**