allow the value function representation to scale with the problem size, we set the maximum ADD size to 4000 + 400n for a network with n **machines. (We experimented with a variety**
of different growth rates for the maximum ADD size; here, as for the other parameters, we selected the choice that gave the best results for Apricodd.) We compared Apricodd with these parameters to our rule-based approximate linear **programming algorithm with**
"single+" basis functions on a Pentium III 700MHz with 1GB of **RAM. These results are** summarized in Figure 20.

On very small problems (up to 4–5 machines), the performance **of the two algorithms is**
fairly similar in terms of both the running time and the quality of the policies generated. However, as the problem size grows, the running time of Apricodd increases rapidly, and becomes significantly higher than that of our algorithm . Furthermore, as the problem size increases, the quality of the policies generated by Apricodd also deteriorates. This difference in policy quality is caused by the different value function representation used by the two algorithms. The ADDs used in Apricodd represent k different values with k **leaves; thus,**
they are forced to agglomerate many different states and represent them using a single value.

For smaller problems, such agglomeration can still represent good policies. Unfortunately, as the problem size increases and the state space grows exponentially, Apricodd's policy representation becomes inadequate, and the quality of the policies decreases. On the other hand, our linear value functions can represent exponentially many values with only k **basis**
functions, which allows our approach to scale up to significantly larger problems.

## 10. Related Work

The most closely related work to ours is a line of research that began with the work of Boutilier et al. (1995). We address this comparison separately below, but we **begin this**
section with some broader background references.

## 10.1 Approximate Mdp Solutions

The field of MDPs, as it is popularly known, was formalized by Bellman (1957) in the 1950's. The importance of value function approximation was **recognized at an early stage**
by Bellman himself (1963). In the early 1990's the MDP framework was recognized by AI
researchers as a formal framework that could be used to address the problem of planning under uncertainty (Dean, Kaelbling, Kirman, & Nicholson, 1993).

Within the AI community, value function approximation developed concomitantly with the notion of value function representations for Markov chains. Sutton's seminal paper on temporal difference learning (1988), which addressed the use of value functions for prediction but not planning, assumed a very general representation of the value function and noted the connection to general function approximators such as neural networks. However, the stability of this combination was not directly addressed at **that time.**
Several important developments gave the AI community deeper insight into the relationship between function approximation and dynamic programming. Tsitsiklis and Van Roy (1996a) and, independently, Gordon (1995) popularized **the analysis of approximate** MDP methods via the contraction properties of the dynamic programming operator and function approximator. Tsitsiklis and Van Roy (1996b) later established a general convergence result for linear value function approximators and T D(λ**), and Bertsekas and**