of other variables. Furthermore, the momentary rewards can **often also be decomposed as**
a sum of rewards related to individual variables or small clusters of variables.

There are two main types of structure that can simultaneously be exploited in factored MDPs: additive and context-specific structure. Additive **structure captures the fact that**
typical large-scale systems can often be decomposed into a combination of locally interacting components. For example, consider the management of **a large factory with many**
production cells. Of course, in the long run, if a cell positioned early in the production line generates faulty parts, then the whole factory may be affected. However, the quality of the parts a cell generates depends directly **only on the state of this cell and the quality of the** parts it receives from neighboring cells. Such additive structure can also be present in the reward function. For example, the cost of running the factory depends, among other things, on the sum **of the costs of maintaining each local cell.**
Context-specific **structure encodes a different type of locality of influence: Although a**
part of a large system may, in general, be influenced by the state of every other part of this system, at any given point in time only a small number of parts **may influence it directly.**
In our factory example, a cell responsible for anodization may receive parts directly from any other cell in the factory. However, a work order for a cylindrical part may restrict this dependency only to cells that have a lathe. Thus, in the context **of producing cylindrical**
parts, the quality of the anodized parts depends directly only **on the state of cells with a** lathe.

Even when a large MDP can be represented compactly, for example, by using a factored representation, solving it exactly may still be intractable: Typical exact MDP solution algorithms require the manipulation of a value function, whose representation is linear in the number of states, which is exponential in the number of state **variables. One approach is**
to approximate the solution using an approximate value function with a compact representation. A common choice is the use of linear **value functions as an approximation - value**
functions that are a linear combination of potentially non-linear basis functions (Bellman, Kalaba, & Kotkin, 1963; Sutton, 1988; Tsitsiklis & Van Roy, 1996b). Our work builds on the ideas of Koller and Parr (1999, 2000), by using factored (linear) value functions**, where**
each basis function is restricted to some small subset of the **domain variables.**
This paper presents two new algorithms for computing linear **value function approximations for factored MDPs: one that uses approximate dynamic programming and another**
that uses approximate linear programming. Both algorithms are based on the use of factored linear value functions, a highly expressive function **approximation method. This**
representation allows the algorithms to take advantage of both **additive and context-specific**
structure, in order to produce high-quality approximate solutions very efficiently. The capability to exploit both types of structure distinguishes these algorithms differ from earlier approaches (Boutilier et al.**, 2000), which only exploit context-specific structure. We provide** a more detailed discussion of the differences in Section 10.

We show that, for a factored MDP and factored value functions, various critical operations for our planning algorithms can be implemented in closed form without necessarily enumerating the entire state space. In particular, both our **new algorithms build upon a** novel linear programming decomposition technique. This technique reduces structured LPs with exponentially many constraints to equivalent, polynomially-sized ones. This decomposition follows a procedure analogous to variable elimination that applies both to additively