Corollary 4.5 **The solution** (φ
∗, w∗) of a linear program that minimizes φ **subject to the**
constraints in FactoredLP(C, −b,O**) and** FactoredLP(−C, b,O**), for any elimination**
order O **satisfies:**

$\mathbf{w}^{*}\in\arg\min_{\mathbf{w}}\|C\mathbf{w}-\mathbf{b}\|_{\infty}\,,\quad\quad\text{and}\quad\quad\phi^{*}=\min_{\mathbf{w}}\|C\mathbf{w}-\mathbf{b}\|_{\infty}\,.$
The original max-norm projection LP had k **+ 1 variables and two constraints for each**
state x**; thus, the number of constraints is exponential in the number of state variables.**
On the other hand, our new factored max-norm projection LP has more variables, but exponentially fewer constraints. The number of variables and constraints in the new factored LP is exponential only in the number of state variables in the **largest factor in the cost** network, rather than exponential in the total number of state variables. As we show in Section 9, this exponential gain allows us to compute max-norm projections efficiently when solving very large factored MDPs.

## 5. Approximate Linear Programming

We begin with the simplest of our approximate MDP solution algorithms, based on the approximate linear programming formulation in Section 3.3. Using the basic operations described in Section 4, we can formulate an algorithm that is **both simple and efficient.**

## 5.1 The Algorithm

As discussed in Section 3.3, approximate linear program formulation is based on the linear programming approach to solving MDPs presented in Section 3.3. However, in this approximate version, we restrict the space of value functions **to the linear space defined by**
our basis functions. More precisely, in this approximate LP **formulation, the variables are**
w1, . . . , wk **— the weights for our basis functions. The LP is given by:**

Variables: $w_{1},\ldots,w_{k}$ ; Minimize: $\sum_{\mathbf{x}}\alpha(\mathbf{x})\sum_{i}w_{i}\ h_{i}(\mathbf{x})$ ; Subject to: $\sum_{i}w_{i}\ h_{i}(\mathbf{x})\geq[R(\mathbf{x},a)+\gamma\sum_{\mathbf{x}^{\prime}}P(\mathbf{x}^{\prime}\mid\mathbf{x},a)\sum_{i}w_{i}\ h_{i}(\mathbf{x}^{\prime})]\quad\forall\mathbf{x}\in\mathbf{X},\forall a\in A$. (14)  In other words, this formulation takes the LP in (7) and substitutes the explicit state value 
function with a linear value function representation Pi wi hi(x**). This transformation from**
an exact to an approximate problem formulation has the effect **of reducing the number**
of free variables in the LP to k **(one for each basis function coefficient), but the number** of constraints remains |X| × |A|. In our SysAdmin **problem, for example, the number of**
constraints in the LP in (14) is (m **+ 1)** · 2 m, where m **is the number of machines in the**
network. However, using our algorithm for representing exponentially large constraint sets compactly we are able to compute the solution to this approximate linear programming algorithm in closed form **with an exponentially smaller LP, as in Section 4.2.**
First, consider the objective function Px α(x)Pi wi hi(x**) of the LP (14). Naively**
representing this objective function requires a summation **over a exponentially large state** space. However, we can rewrite the objective and obtain a compact representation. We first reorder the terms: