in the partition of leaf i**. Thus, the set of value functions that can be represented by a** tree with k **leaves is a subset of the set of value functions that can be represented by a** value function with k **basis functions. Our experimental results in Section 9.3 highlight this**
difference by showing an example problem that requires exponentially many leaves in the value function, but that can be approximated well using a linear value function.

The main advantage of tree-based value functions is that their structure is determined dynamically during the solution of the MDP. In principle, as **the value function representation is derived automatically from the model description, this approach requires less insight**
from the user. In problems for which the value function can be **well approximated by a relatively small number of values, this approach provides an excellent solution to the problem.**
Our method of linear value function approximation aims to address what we believe to be the more common case, where a large range of distinct values is required to achieve a good approximation.

Finally, we note that Schuurmans and Patrascu (2001), based **on our earlier work on**
max-norm projection using cost networks and linear programs, independently developed an alternative approach to approximate linear programming **using a cost network. Our** method embeds a cost network inside a single linear program. **By contrast, their method**
is based on a constraint generation approach, using a cost network to detect constraint violations. When constraint violations are found, a new constraint is added, repeatedly generating and attempting to solve LPs until a feasible solution is found. Interestingly, as the approach of Schuurmans and Patrascu uses multiple calls to variable elimination in order to speed up the LP solution step, it will be most successful when the time spent solving the LP is significantly larger than the time required **for variable elimination. As** suggested in Section 9.2, the LP solution time is larger for the table-based approach. Thus, Schuurmans and Patrascu's constraint generation method will probably be more successful in table-based problems than in rule-based ones.

## 11. Conclusions

In this paper, we presented new algorithms for approximate linear programming and approximate dynamic programming (value and policy iteration) for factored MDPs. Both of these algorithms leverage on a novel LP decomposition technique, analogous to variable elimination in cost networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one.

Our approximate dynamic programming algorithms are motivated by error analyses showing the importance of minimizing L∞ **error. These algorithms are more efficient and**
substantially easier to implement than previous algorithms based on the L2**-projection. Our**
experimental results suggest that they also perform better **in practice.**
Our approximate linear programming algorithm for factored **MDPs is simpler, easier to**
implement and more general than the dynamic programming approaches. Unlike our policy iteration algorithm, it does not rely on the default action assumption, which states that actions only affect a small number of state variables. Although this algorithm does not have the same theoretical guarantees as max-norm projection approaches, empirically it seems to be a favorable option. Our experiments suggest that approximate policy iteration tends to generate better policies for the same set of basis functions. However, due to the computa-