

![0_image_0.png](0_image_0.png) 

We can now eliminate X2**, generating the linear constraints:**

$$u_{X_{1}}^{e_{3}}\geq u_{X_{2}}^{R_{2}}+u_{X_{1},X_{2}}^{e_{2}}+u_{X_{1},X_{2}}^{e_{2}}\;,\;\forall\;X_{1},X_{2}\;.$$  Now, our global non-linear constraint involves only $X_{1}$:
$$0\geq\operatorname*{max}_{X_{1}}u_{X_{1}}^{R_{1}}+u^{c_{0}}+u_{X_{1}}^{e_{3}}\ .$$

As X1 **is the last variable to be eliminated, the scope of the new LP variable is empty and**
the linear constraints are given by:

$$u^{e_{4}}\geq u_{X_{1}}^{R_{1}}+u_{X_{1}}^{e_{3}}\ ,\ \forall\ X_{1}\ .$$

All of the state variables have now been eliminated, turning **our global non-linear constraint**
into a simple linear constraint:
0 ≥ u c0 + u e4, which completes the LP description for the approximate linear programming solution to the problem in Figure 2.

In this small example with only four state variables, our factored LP technique generates a total of 89 equality constraints, 115 inequality constraints and 149 LP variables, while the explicit state representation in Equation (8) generates only 80 inequality constraints and 5 LP variables. However, as the problem size increases, the number of constraints and LP variables in our factored LP approach grow as O(n 2**), while the explicit state approach**
grows exponentially, at O(n2 n**). This scaling effect is illustrated in Figure 7.**

## 6. Approximate Policy Iteration With Max-Norm Projection

The factored approximate linear programming approach described in the previous section is both elegant and easy to implement. However, we cannot, in **general, provide strong**