require explicit computation or manipulation of the greedy **policy. This difference has two**
important consequences: one computational and the other in **terms of generality.**
First, not having to compute or consider the decision lists makes approximate linear programming faster and easier to implement. In this algorithm, we generate a single LP with one cost network for each action and never need to compute a decision list policy. On the other hand, in each iteration, approximate policy iteration needs to generate two LPs for every branch of the decision list of size L**, which is usually significantly longer than** |A|, with a total of 2L cost networks. In terms of representation, we do not require **the policies**
to be compact; thus, we do not need to make the default action assumption. Therefore, the approximate linear programming algorithm can deal with a more general class of problems, where each action can have its own independent DBN transition model. On the other hand, as described in Section 3.2, approximate policy iteration has stronger guarantees in terms of error bounds. These differences will be highlighted further in our experimental results presented in Section 9.

## 7. Computing Bounds On Policy Quality

We have presented two algorithms for computing approximate **solutions to factored MDPs.**
All these algorithms generate linear value functions which can be denoted by Hwb **, where** wb are the resulting basis function weights. In practice, the agent will define its behavior by acting according to the greedy policy πb = Greedy(Hwb **). One issue that remains is how this**
policy πb **compares to the true optimal policy** π
∗; that is, how the actual **value** Vbπ of policy πb **compares to** V
∗.

In Section 3, we showed some a priori **bounds for the quality of the policy. Another**
possible procedure is to compute an a posteriori **bound. That is, given our resulting weights**
wb , we compute a bound on the loss of acting according to the greedy policy πb **rather than**
the optimal policy. This can be achieved by using the Bellman error **analysis of Williams**
and Baird (1993).

The Bellman error is defined as BellmanErr(V) = kT ∗V − Vk∞**. Given the greedy**
policy πb = Greedy(V**), their analysis provides the bound:**

$$\|\mathcal{V}^{*}-\mathcal{V}_{\pi}\|_{\infty}\leq\frac{2\gamma\mathrm{BellmanErr}(\mathcal{V})}{1-\gamma}.$$
$$(22)$$

. **(22)**
Thus, we can use the Bellman error BellmanErr(Hwb **) to evaluate the quality of our resulting**
greedy policy.

Note that computing the Bellman error involves a maximization over the state space.

Thus, the complexity of this computation grows exponentially with the number of state variables. Koller and Parr (2000) suggested that structure **in the factored MDP can be**
exploited to compute the Bellman error efficiently. Here, we show how this error bound can be computed by a set of cost networks using a similar construction to the one in our maxnorm projection algorithms. This technique can be used for any πb **that can be represented**
as a decision list and does not depend on the algorithm used to **determine the policy. Thus,** we can apply this technique to solutions determined approximate linear programming if the action descriptions permit a decision list representation **of the policy.**
For some set of weights wb **, the Bellman error is given by:**