tional advantages, we can add more basis functions to the approximate linear programming algorithm, obtaining a better policy and still maintaining **a much faster running time than**
approximate policy iteration.

Unlike previous approaches, our algorithms can exploit both additive and contextspecific structure in the factored MDP model. Typical real-world systems possess both of these types of structure. thus, this feature of our algorithms will increase the applicability of factored MDPs to more practical problems. We demonstrated that exploiting context-specific independence, by using a rule-based representation instead of the standard table-based one, can yield exponential improvements in computational time when the problem has significant amounts of CSI. However, the overhead of managing sets of rules make it less well-suited for simpler problems. We also compared our approach to the work of Boutilier et al. **(2000), which exploits only context-specific structure. For problems with**
significant context-specific structure in the value function, their approach can be faster due to their efficient handling of the ADD representation. However, there are problems with significant context-specific structure in the problem representation, rather than in the value function, which require exponentially large ADDs. In some such problems, we demonstrated that by using a linear value function our algorithm can obtain a polynomial-time near-optimal approximation of the true value function.

The success of our algorithm depends on our ability to capture the most important structure in the value function using a linear, factored approximation. This ability, in turn, depends on the choice of the basis functions and on the properties of the domain. The algorithms currently require the designer to specify the factored basis functions. This is a limitation compared to the algorithms of Boutilier et al. **(2000), which are fully automated.**
However, our experiments suggest that a few simple rules can be quite successful for designing a basis. First, we ensure that the reward function is **representable by our basis. A**
simple basis that, in addition, contained a separate set of indicators for each variable often did quite well. We can also add indicators over pairs of variables; most simply, we can choose these according to the DBN transition model, where an indicator is added between variables Xi and each one of the variables in Parents(Xi**), thus representing one-step influences. This**
procedure can be extended, adding more basis functions to represent more influences as required. Thus, the structure of the DBN gives us indications of how to choose the basis functions. Other sources of prior knowledge can also be included for further specifying the basis.

Nonetheless, a general algorithm for choosing good factored basis functions still does not exist. However, there are some potential approaches: First, in problems with CSI, one could apply the algorithms of Boutilier et al. **for a few iterations to generate partial treestructured solutions. Indicators defined over the variables in backprojection of the leaves**
could, in turn, be used to generate a basis set for such problems. Second, the Bellman error computation, which can be performed efficiently as shown in Section 7, does not only provide a bound on the quality of the policy, but also the actual state where the error is largest. This knowledge can be used to create a mechanism to incrementally increase the basis set, adding new basis functions to tackle states with high Bellman error.

There are many other possible extensions to this work. We have already pursued extensions to collaborative multiagent systems, where multiple agents act simultaneously to maximize the global reward (Guestrin et al.**, 2001b), and factored POMDPs, where the**