Tsitsiklis (1996) unified a large body of work on approximate **dynamic programming under**
the name of Neuro-dynamic Programming**, also providing many novel and general error**
analyses.

Approximate linear programming for MDPs using linear value **function approximation**
was introduced by Schweitzer and Seidmann (1985), although **the approach was somewhat**
deprecated until fairly recently due the lack of compelling **error analyses and the lack of an**
effective method for handling the large number of constraints. Recent work by de Farias and Van Roy (2001a, 2001b) has started to address these concerns with new error bounds and constraint sampling methods. Our approach, rather than **sampling constraints, utilizes** structure in the model and value function to represent all of **the constraints compactly.**

## 10.2 Factored Approaches

Tatman and Shachter (1990) considered the additive decomposition of value nodes in influence diagrams. A number of approaches to factoring of general MDPs have been explored in the literature. Techniques for exploiting reward functions that decompose additively were studied by Meuleau et al. **(1998), and by Singh and Cohn (1998).**
The use of factored representations such as dynamic Bayesian networks was pioneered by Boutilier et al. **(1995) and has developed steadily in recent years. These methods rely** on the use of context-specific structures such as decision trees or analytic decision diagrams (ADDs) (Hoey et al.**, 1999) to represent both the transition dynamics of the DBN and** the value function. The algorithms use dynamic programming **to partition the state space,** representing the partition using a tree-like structure that branches on state variables and assigns values at the leaves. The tree is grown dynamically as part of the dynamic programming process and the algorithm creates new leaves as needed: A leaf is split by the application of a DP operator when two states associated with **that leaf turn out to have**
different values in the backprojected value function. This process can also be interpreted as a form of model minimization (Dean & Givan, 1997).

The number of leaves in a tree used to represent a value function determines the computational complexity of the algorithm. It also limits the number of distinct values that can be assigned to states: since the leaves represent a partitioning of the state space, every state maps to exactly one leaf. However, as was recognized early on, there are trivial MDPs which require exponentially large value functions. This observation led to a line of approximation algorithms aimed at limiting the tree size (Boutilier & Dearden, 1996) and, later, limiting the ADD size (St-Aubin, Hoey, & Boutilier, 2001). Kim and Dean (2001) also explored techniques for discovering tree-structured value functions for factored MDPs. While these methods permit good approximate solutions to some large MDPs, their complexity is still determined by the number of leaves in the representation and **the number of distinct values**
than can be assigned to states is still limited as well.

Tadepalli and Ok (1996) were the first to apply linear value function approximation to Factored MDPs. Linear value function approximation is a potentially more expressive approximation method because it can assign unique values to **every state in an MDP without** requiring storage space that is exponential in the number of **state variables. The expressive**
power of a tree with k leaves can be captured by a linear function approximator with k **basis**
functions such that basis function hi**is an indicator function that tests if a state belongs**