

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

For these small problems, we can also compare the actual value of the policy generated by our algorithm to the value of the optimal policy. Here, the **value of the policy generated** by our algorithm is much closer to the value of the optimal policy than the error implied by the difference between our approximate value function and V
∗**. For example, for the "Star"**
architecture with one server and up to 6 clients, our approximation with single variable basis functions had relative error of 12%, but the policy we generated had the same value as the optimal policy. In this case, the same was true for the policy generated by the L2 projection. In a "Unidirectional Ring" with 8 machines and pairwise basis, the relative error between our approximation and V
∗ **was about 10%, but the resulting policy only had**
a 6% loss over the optimal policy. For the same problem, the L2 **approximation has a value**
function error of 12%, and a true policy loss was 9%. In other words, both methods induce policies that have lower errors than the errors in the approximate value function (at least for small problems). However, our algorithm continues to outperform the L2 **algorithm,**
even with respect to actual policy loss.

For large models, we can no longer compute the correct value function, so we cannot evaluate our results by computing kV∗ − Hwk∞**. Fortunately, as discussed in Section 7,**
the Bellman error can be used to provide a bound on the approximation error and can be computed efficiently by exploiting problem-specific structure. Figure 15(b) shows that the Bellman error increases very slowly with the number of states.

It is also valuable to look at the actual decision-list policies generated in our experiments.

First, we noted that the lists tended to be short, the length of the final decision list policy grew approximately linearly with the number of machines. Furthermore, the policy itself is often fairly intuitive. In the "Ring and Star" architecture, for example, the decision list says: If the server is faulty, fix the server; else, if another **machine is faulty, fix it.**
Thus far, we have presented scaling results for running times and approximation error for our approximate PI approach. We now compare this algorithm to the simpler approximate