We can now maximize b out from e8 and e5**, resulting in the following rule and constraints**
respectively:
e10 = ha ∧ c : u7i,
$$\begin{array}{l}{{c_{10}=\langle u\wedge v\rangle}}\\ {{u_{7}\geq u_{5},}}\\ {{u_{7}\geq u_{3}.}}\end{array}$$
Likewise, maximizing b out from e9 and e6**, we get:**
e11 = ha ∧ ¬c : u8i,
$$\begin{array}{l}{{e_{11}=\langle a\rangle}}\\ {{u_{8}\geq u_{3},}}\end{array}$$
u8 ≥ u6; which completes the elimination of variable b **in our rule-based factored LP.**
We have presented an algorithm for exploiting both additive **and context-specific structure in the LP construction steps of our planning algorithms. This rule-based factored LP**
approach can now be applied directly in our approximate linear programming and approximate policy iteration algorithms, which were presented in **Sections 5 and 6.**
The only additional modification required concerns the manipulation of the decision list policies presented in Section 6.2. Although approximate linear programming does not require any explicit policy representation (or the default **action model), approximate policy iteration require us to represent such policy. Fortunately, no major modifications are**
required in the rule-based case. In particular, the conditionals hti, ai, δii **in the decision**
list policies are already context-specific rules. Thus, the **policy representation algorithm in**
Section 6.2 can be applied directly with our new rule-based representation. Therefore, we now have a complete framework for exploiting both additive and context-specific structure for efficient planning in factored MDPs.

## 9. Experimental Results

The factored representation of a value function is most appropriate in certain types of systems: Systems that involve many variables, but where the **strong interactions between** the variables are fairly sparse, so that the decoupling of the influence between variables does not induce an unacceptable loss in accuracy. As argued by Herbert Simon (1981) in "Architecture of Complexity," many complex systems have **a "nearly decomposable,** hierarchical structure," with the subsystems interacting **only weakly between themselves. To** evaluate our algorithm, we selected problems that we believe exhibit this type of structure.

In this section, we perform various experiments intended to **explore the performance**
of our algorithms. First, we compare our factored approximate linear programming (LP)
and approximate policy iteration (PI) algorithms. We also compare to the L2**-projection**
algorithm of Koller and Parr (2000). Our second evaluation compares a table-based implementation to a rule-based implementation that can exploit CSI. Finally, we present comparisons between our approach and the algorithms of Boutilier et al. **(2000).**

## 9.1 Approximate Lp And Approximate Pi

In order to compare our approximate LP and approximate PI algorithms, we tested both on the SysAdmin **problem described in detail in Section 2.1. This problem relates to a system**