

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

LP approach of Section 5. As shown in Figure 16(a), the approximate LP algorithm for factored MDPs is significantly faster than the approximate PI algorithm. In fact, approximate PI with single-variable basis functions variables is more costly computationally than the LP approach using basis functions over consecutive triples of variables. As shown in Figure 16(b), for singleton basis functions, the approximate PI policy obtains slightly better performance for some problem sizes. However, as we increase **the number of basis functions**
for the approximate LP formulation, the value of the resulting policy is much better. Thus, in this problem, our factored approximate linear programming formulation allows us to use more basis functions and to obtain a resulting policy of higher value, while still maintaining a faster running time. These results, along with the simpler **implementation, suggest that**
in practice one may first try to apply the approximate linear programming algorithm before deciding to move to the more elaborate approximate policy iteration approach.

## 9.2 Comparing Table-Based And Rule-Based Implementations

Our next evaluation compares a table-based representation, which exploits only additive independence, to the rule-based representation presented **in Section 8, which can exploit** both additive and context-specific independence. For these **experiments, we implemented** our factored approximate linear programming algorithm with table-based and rule-based representations in C++, using CPLEX as the LP solver. Experiments were performed on a Sun UltraSPARC-II, 400 MHz with 1GB of RAM.

To evaluate and compare the algorithms, we utilized a more complex extension of the SysAdmin problem. This problem, dubbed the Process-SysAdmin **problem, contains three**
state variables for each machine i in the network: Loadi, Statusi and Selectori**. Each computer runs processes and receives rewards when the processes terminate. These processes**
are represented by the Loadi variable, which takes values in {Idle, Loaded, Success}**, and the** computer receives a reward when the assignment of Loadiis Success. The Statusi **variable,**