guarantees about the error it achieves. An alternative is to **use the approximate policy**
iteration described in Section 3.2, which does offer certain **bounds on the error. However,**
as we shall see, this algorithm is significantly more complicated, and requires that we place additional restrictions on the factored MDP.

In particular, approximate policy iteration requires a representation of the policy at each iteration. In order to obtain a compact policy representation, we must make an additional assumption: each action only affects a small number of state variables. We first state this assumption formally. Then, we show how to obtain a compact representation of the greedy policy with respect to a factored value function, under this **assumption. Finally, we describe** our factored approximate policy iteration algorithm using **max-norm projections.**

## 6.1 Default Action Model

In Section 2.2, we presented the factored MDP model, where each action is associated with its own factored transition model represented as a DBN and with its own factored reward function. However, different actions often have very similar transition dynamics, only differing in their effect on some small set of variables. In particular, in many cases a variable has a default evolution model, which only changes if an action affects it directly (Boutilier et al.**, 2000).**
This type of structure turns out to be useful for compactly representing policies, a property which is important in our approximate policy iteration **algorithm. Thus, in this section**
of the paper, we restrict attention to factored MDPs that are defined using a default transition model τd = hGd, Pdi (Koller & Parr, 2000). For each action a, we define **Effects**[a] ⊆ X′
to be the variables in the next state whose local probability model is different from τd, **i.e.**,
those variables X′
i such that Pa(X′
i | **Parents**a(X′
i
)) 6= Pd(X′
i | **Parents**d(X′
i
)).

Example 6.1 In our system administrator example, we have an action ai**for rebooting**
each one of the machines, and a default action d **for doing nothing. The transition model**
described above corresponds to the "do nothing" action, which is also the default transition model. The transition model for aiis different from d **only in the transition model for the**
variable X′
i
, which is now X′
i = **true with probability one, regardless of the status of the**
neighboring machines. Thus, in this example, Effects[ai] = X′
i
.

As in the transition dynamics, we can also define the notion of default reward model**. In**
this case, there is a set of reward functions Pr i=1 Ri(Ui**) associated with the default action**
d. In addition, each action a can have a reward function Ra(Ua**). Here, the extra reward of**
action a has scope restricted to Rewards [a] = Ua i ⊂ {X1, . . . , Xn}**. Thus, the total reward**
associated with action a **is given by** Ra +Pr i=1 Ri. Note that Ra**can also be factored as a**
linear combination of smaller terms for an even more compact **representation.**
We can now build on this additional assumption to define the complete algorithm.

Recall that the approximate policy iteration algorithm iterates through two steps: policy improvement and approximate value determination. We now discuss each of these steps.

## 6.2 Computing Greedy Policies

The policy improvement step computes the greedy policy relative to a value function V
(t−1):
π
(t) = Greedy(V
(t−1)).