administrator who has to maintain a network of computers; we **experimented with various**
network architectures, shown in Figure 1. Machines fail randomly, and a faulty machine increases the probability that its neighboring machines will fail. At every time step, the SysAdmin can go to one machine and reboot it, causing it to be working in the next time step with high probability. Recall that the state space in this problem grows exponentially in the number of machines in the network, that is, a problem with m machines has 2m **states.**
Each machine receives a reward of 1 when working (except in the ring, where one machine receives a reward of 2, to introduce some asymmetry), a zero reward is given to faulty machines, and the discount factor is γ = 0.**95. The optimal strategy for rebooting machines**
will depend upon the topology, the discount factor, and the status of the machines in the network. If machine i and machine j are both faulty, the benefit of rebooting i **must be** weighed against the expected discounted impact of delaying rebooting j on j**'s successors.**
For topologies such as rings, this policy may be a function of **the status of every single** machine in the network.

The basis functions used included independent indicators for each machine, with value 1 if it is working and zero otherwise (i.e.**, each one is a restricted scope function of a single** variable), and the constant basis, whose value is 1 for all states. We selected straightforward variable elimination orders: for the "Star" and "Three Legs" topologies, we first eliminated the variables corresponding to computers in the legs, and the center computer (server) was eliminated last; for "Ring," we started with an arbitrary computer and followed the ring order; for "Ring and Star," the ring machines were eliminated first and then the center one; finally, for the "Ring of Rings" topology, we eliminated the computers in the outer rings first and then the ones in the inner ring.

We implemented the factored policy iteration and linear programming algorithms in Matlab, using CPLEX as the LP solver. Experiments were performed on a Sun UltraSPARCII, 359 MHz with 256MB of RAM. To evaluate the complexity of the approximate policy iteration with max-norm projection algorithm, tests were performed with increasing the number of states, that is, increasing number of machines on the network. Figure 14 shows the running time for increasing problem sizes, for various architectures. The simplest one is the "Star," where the backprojection of each basis function has scope restricted to two variables and the largest factor in the cost network has scope restricted to two variables. The most difficult one was the "Bidirectional Ring," where factors contain five variables.

Note that the number of states is growing exponentially (indicated by the log scale in Figure 14), but running times increase only logarithmically in the number of states, or polynomially in the number of variables. We illustrate this **behavior in Figure 14(d), where** we fit a 3rd order polynomial to the running times for the "unidirectional ring." Note that the size of the problem description grows quadratically with the number of variables: adding a machine to the network also adds the possible action of fixing that machine. For this problem, the computation cost of our factored algorithm empirically grows approximately as O
(n · |A|)
1.5, for a problem with n **variables, as opposed to the exponential complexity**
- poly (2n, |A|**) - of the explicit algorithm.**
For further evaluation, we measured the error in our approximate value function relative to the true optimal value function V
∗**. Note that it is only possible to compute** V
∗**for small**
problems; in our case, we were only able to go up to 10 machines. For comparison, we also evaluated the error in the approximate value function produced by the L2**-projection**