structured value functions (Bertele & Brioschi, 1972) and to value functions that also exploit context-specific structure (Zhang & Poole, 1999). Using these basic operations, our planning algorithms can be implemented efficiently, even though the size of the state space grows exponentially in the number of variables.

Our first method is based on the approximate linear programming algorithm (Schweitzer
& Seidmann, 1985). This algorithm generates a linear, approximate value function by solving a single linear program. Unfortunately, the number **of constraints in the LP proposed** by Schweitzer and Seidmann grows exponentially in the number of variables. Using our LP decomposition technique, we exploit structure in factored **MDPs to represent exactly the** same optimization problem with exponentially fewer constraints.

In terms of approximate dynamic programming, this paper makes a twofold contribution.

First, we provide a new approach for approximately solving MDPs using a linear value function. Previous approaches to linear function approximation typically have utilized a least squares (L2**-norm) approximation to the value function. Least squares approximations**
are incompatible with most convergence analyses for MDPs, which are based on max-norm.

We provide the first MDP solution algorithms - both value iteration and policy iteration —
that use a linear max-norm projection to approximate the value function, thereby directly optimizing the quantity that appears in our provided error bounds. Second, we show how to exploit the structure of the problem to apply this technique to factored MDPs, by again leveraging on our LP decomposition technique.

Although approximate dynamic programming currently possesses stronger theoretical guarantees, our experimental results suggest that approximate linear programming is a good alternative. Whereas the former tends to generate better policies for the same set of basis functions, due to the simplicity and computational advantages of approximate linear programming, we can add more basis functions, obtaining a better policy and still requiring less computation than the approximate dynamic programming **approach.**
Finally, we present experimental results comparing our approach to the work of Boutilier et al. **(2000), illustrating some of the tradeoffs between the two methods. In particular, for**
problems with significant context-specific structure in the value function**, their approach**
can be faster due to their efficient handling of their value function representation. However, there are cases with significant context-specific structure **in the problem, rather than in** the value function, in which their algorithm requires an exponentially large value function representation. In such classes of problems, we demonstrate that by using a value function that exploits both additive and context-specific structure, our algorithm can obtain a polynomial-time near-optimal approximation of the true value function.

This paper starts with a presentation of factored MDPs and approximate solution algorithms for MDPs. In Section 4, we describe the basic operations used in our algorithms, including our LP decomposition technique. In Section 5, we present the first of our two algorithms: the approximate linear programming algorithm **for factored MDPs. The second** algorithm, approximate policy iteration with max-norm projection, is presented in Section 6. Section 7 describes an approach for efficiently computing bounds on policy quality based on the Bellman error. Section 8 shows how to extend our methods to deal with context-specific structure. Our paper concludes with an empirical evaluation in Section 9 and a discussion of related work in Section 10.