Generalizing Plans to New Environments in Relational MDPs

1 Introduction

Most planning methods optimize the plan of an agent in a fixed environment. However, in many real-world settings, an agent will face multiple environments over its lifetime, and its experience with one environment should help it to perform well in another, even with minimal or no replanning.

Consider, for example, an agent designed to play a strate­ gic computer war game, such as the Freecraft game shown in Fig. 1 (an open source version of the popular Warcraft game). In this game, the agent is faced with many scenar­ ios. In each scenario, it must control a set of agents (or units) with different skills in order to defeat an opponent. Most sce­ narios share the same basic elements: resources, such as gold and wood; units, such as peasants, who collect resources and build structures, and footmen, who fight with enemy units; and structures, such as barracks, which are used to train foot­ men. Each scenario is composed of these same basic build­ ing blocks, but they differ in terms of the map layout, types of units available, amounts of resources, etc. We would like the agent to learn from its experience with playing some sce­ narios, enabling it to tackle new scenarios without significant amounts of replanning. In particular, we would like the agent to generalize from simple scenarios, allowing it to deal with other scenarios that are too complex for any effective planner.

The idea of generalization has been a longstanding goal in Markov Decision Process (MDP) and reinforcement learning diately determines a value function for any new environment in the domain, and can be used for acting. Thus, we can com­ pute a set of class subfunctions based on a subset of environ­ ments, and apply them to another one without replanning.

We provide an optimality criterion for evaluating a class­ based value function for a distribution over environments, and show how it can, in principle, be optimized using a linear pro­ gram. We can also "learn" a value function by optimizing it relative to a sample of environments encountered by the agent. We prove that a polynomial number of sampled en­ vironments suffice to construct a class-based value function which is close to the one obtainable for the entire distribution over environments. Finally, we show how we can improve the quality of our approximation by automatically discover­ ing subclasses of objects that have "similar" value functions.

We present experiments for a computer systems admin­ istration task and two Freecraft tasks. Our results show that we can successfully generalize class-based value func­ tions. Importantly, our approach also obtains effective poli­ cies for problems significantly larger than our planning algo­ rithm could handle otherwise.

2 Relational Markov Decision Processes

A relational MDP defines the system dynamics and rewards at the level of a template for a task domain. Given a particu­ lar environment within that domain, it defines a specific MDP instantiated for that environment. As in the PRM framework of [10], the domain is defined via a schema, which speci­ fies a set of object classes C = {C1, ... , Cc}· Each class C is also associated with a set of state variables S[CJ = { C.S1 , . .. , C.Sk}, which describe the state of an object in that class. Each state variable C.S has a domain of possible values Dom[C.SJ. We define Sc to be the set of possible states for an object inC, i.e., the possible assignments to the state variables of C.

For example, our Freecraft domain might have classes such as Peasant, Footman, Gold; the class Peasant may have a state variable Task whose domain is Dom[Peasant.Task] {Waiting, Mining, Harvesting, Building}, and a state variable Health whose domain has three values. In this case, SPeasant would have 4 · 3 = 12 values, one for each combination of values for Task and Health.

The schema also specifies a set of links .C [ CJ { L1 , ... , Lz} for each class representing links between ob­ jects in the domain. Each link C.L has a range p[C.L] = C'. For example, Peasant objects might be linked to Barrack objects - p[Peasant.BuildTarget] = Barrack, and to the global Gold and Wood resource objects. In a more com­ plex situation, a link may relate C to many instances of a class C', which we denote by p[C.LJ = {C'}, for example, p[Enemy.MyJ'ootmen] = {Footman} indicates that an instance of the enemy class may be related to many footman instances.

A particular instance of the schema is defined via a world w, specifying the set of objects of each class; we use O[w][CJ to denote the objects in class C, and O[w] to de­ note the total set of objects in w. The world w also spec­ ifies the links between objects, which we take to be fixed throughout time. Thus, for each link C.L, and for each o E O[w][CJ, w specifies a set of objects o' E p[C.LJ, de­ noted o.L. For example, in a world containing 2 peasants, we would have O[w][Peasant] = {Peasant1, Peasant2} ; if Peasant1 is building a barracks, we would have that Peasantl.BuildTarget = Barrack!.

The dynamics and rewards of an RMDP are also de­ fined at the schema level. For each class, the schema specifies an action C.A, which can take on one of sev­ eral values Dom[C.AJ. For example, Dom[Peasant.A] = {Wait, Mine, Harvest, Build}. Each class C is also associ­ ated with a transition model pC, which specifies the proba­ bility distribution over the next state of an object o in class C, given the current state of o, the action taken on o, and the states and actions of all of the objects linked to o:

For example, the status of a barrack, Barrack.Status', depends on its status in the previous time step, on the task performed by any peasant that could build it (Barrack.BuiltBy.Task), on the amount of wood and gold, etc.

The transition model is conditioned on the state of C.Li, which is, in general, an entire set of objects (e.g., the set of peasants linked to a barrack). Thus we must now provide a compact specification of the transition model that can de­ pend on the state of an unbounded number of variables. We can deal with this issue using the idea of aggregation [10] . In Freecraft, our model uses the count aggregator U, where the probability that Barrack.Status transitions from Unbuilt to Built depends on U[Barrack.BuiltBy.Task = Built], the num­ ber of peasants in Barrack.BuiltBy whose Task is Build.

Finally, we also define rewards at the class level. We as­ sume for simplicity that rewards are associated only with the states of individual objects; adding more global dependencies is possible, but complicates planning significantly. We define a reward function R 0 (Sc, C.A), which represents the con­ tribution to the reward of any object in C. For example, we may have a reward function associated with the Enemy class, which specifies a reward of 10 if the state of an enemy object is Dead: REnemy(Enemy.State = Dead) = 10. We assume that the reward for each object is bounded by Rmax·

Given a world, the RMDP uniquely defines a ground fac­ tored MDP IIw, whose transition model is specified (as usual) as a dynamic Bayesian network (DBN) [3]. The random vari­ ables in this factored MDP are the state variables of the in­ dividual objects o.S, for each o E O[w][CJ and for each S E S[CJ. Thus, the states of the system at a given point in time is a vector defining the states of the individual objects in the world. For any subset of variables X in the model, we de­ fine s[X] to be the part of the instantiations that corresponds to the variables X. The ground DBN for the transition dy­ namics specifies the dependence of the variables at time t + 1 on the variables at time t. The parents of a variable o.S are the state variables of the objects o' that are linked to o. In our example with the two peasants, we might have the random variables Peasant1. Task, Peasant2. Task, Barrack1.Status, etc. The parents of the time t + 1 variable Barrack1.Status' are the time t variables Barrackl.Status', Peasantl.Task, Peasant2.Task, Go!dl.Amount and Woodl.Amount.

The transition model is the same for all instances in the same class, as in (1). Thus, all of the o.Status variables for barrack objects o share the same conditional probability dis­ tribution. Note, however, that each specific barrack depends on the particular peasants linked to it. Thus, the actual parents in the DBN of the status variables for two different barrack objects can be different.

The reward function is simply the sum of the reward func­ tions for the individual objects:

Thus, for reward function for the Enemy class described above, our overall reward function in a given state will be 10 times the number of dead enemies in that state.

It remains to specify the actions in the ground MDP. The RMDP specifies a set of possible actions for every object in the world. In a setting where only a single action can be taken at any time step, the agent must choose both an object to act on, and which action to perform on that object. Here, the set of actions in the ground MDP is simply the union UoEwDom[o.AJ. In a setting where multiple actions can be performed in parallel (say, in a multiagent setting), it might be possible to perform an action on every object in the domain at every step. Here, the set of actions in the ground MDP is a vector specifying an action for every object: x oEwDom[o.AJ. Intermediate cases, allowing degrees of parallelism, are also possible. For simplicity of presentation, we focus on the mul­ tiagent case, such as Freecraft, where, an action is an assign­ ment to the action of every unit.

Example 2.1 (Freecraft tactical domain) Consider a sim­ plified version of Freecraft, whose schema is illustrated in Fig. 2( a), where only two classes of units partici­ pate in the game: C {Footman, Enemy}. Both the footman and the enemy classes have only one state variable each, Health, with domain Dom[Health] {Healthy, Wounded, Dead}. The footman class contains one single-valued link: p[Footman.My.Enemy] = Enemy. Thus the transition model for a footman's health will depend on the health of its enemy: pFootman(s~ootman I Srootman,SFootman.My.Enemy). i.e., if a footman's enemy is not dead, than the probability that a footman will be­ come wounded, or die, is significantly higher. A foot­ man can choose to attack any enemy. Thus each foot­ man is associated with an action Footman.A which se­ lects the enemy it is attacking. 1 As a consequence, an enemy could end up being linked to a set of footmen, p[Enemy.My.Footmen] = {Footman}. In this case, the transition model of the health of an enemy may depend on the number of footmen who are not dead and whose action choice is to attack this enemy: pEnemy(S~nemy I SEnemy , ~[SEnemy.My.Footme/1, Enemy.My..Footmen .A]). Finally, we must define the template for the reward function. Here there is only a reward when an enemy is dead: REnemy(SEnemy)·

1 A model where an action can change the link structure in the

We now have a template to describe any instance of the tactical Freecraft domain. In a particular world, we must define the instances of each class and the links between these instances. For example, a world with 2 footmen and 2 enemies will have 4 objects: {Footman! , Footman2 , Enemy] , Enemy2}. Each footman will be linked to an enemy: Footmanl.My.Enemy Enemy] and Footman2.My.Enemy = Enemy2. Each en­ emy will be linked to both footmen: Enemyl .My.Footmen = Enemy2.My.Footmen = {Footman] , Footman2} . The tem­ plate, along with the number of objects and the links in this specific ("2vs2") world yield a well-defined factored MDP, II2vs2. as shown in Fig. 2(b ). I

3 Approximately Solving Relational MDPs

There are many approaches to solving MDPs [15]. An ef­ fective one is based on linear programming (LP): Let S(II) denote the states in an MDP II and A(II) the actions. If S(II) = {s1, ... , SN }, our LP variables are V1, . .. , VN, where Vi represents V(si), the value of state si . The LP for­ mulation is:

The state relevance weights a(sl), .. . , a(sN) in the objec­ tive function are any set of positive weights, a( si) > 0.

In our setting, the state space is exponentially large, with one state for each joint assignment to the random variables o.S of every object (e.g., exponential in the number of units in the Freecraft scenario). In a multiagent problem, the number of actions is also exponential in the number of agents. Thus this LP has both an exponential number of variables and an exponential number of constraints. Therefore the exact solu­ tion to this linear program is infeasible.

We address this issue using the assumption that the value function can be well-approximated as a sum of local value subfunctions associated with the individual objects in the model. (This approximation is a special case of the factored linear value function approach used in [6] .) Thus we associate a value subfunction Va with every object in w. Most simply, this local value function can depend only on the state of the individual object 8 0 · In our example, the local value subfunction VEnemyi for enemy object Enemy] might associate a numeric value for each assignment to the variable Enemy] .Health. A richer approximation might associate a value function with pairs, or even small subsets, of closely related objects. Thus, the function VFootmanl for Footman] might be defined over the joint assignments of Footmanl.Health and Enemyl.Health, where Footmanl .My..Enemy = Enemy] . We will repre­ sent the complete value function for a world as the sum of the local value subfunction for each individual object in this world. In our example world (w = 2vs2) with 2 footmen and 2 enemies, the global value function will be: V2vs2(FJ .Health, El.Health, F2.Health, E2.Health) VFootmanJ(Fl .Health,El.Health) + VEnemyi(El.Health) + VFootman2(F2.Health,E2.Health) + VEnemy2(E2.Health) .

world requires a small extension of our basic representation. We omit details due to lack of space.

Let T 0 be the scope of the value subfunction of object o, i.e., the state variables that Vo depends on. Given the local subfunctions, we approximate the global value function as:

As for any linear approximation to the value function, the LP approach can be adapted to use this value function rep­ resentation [14]. Our LP variables are now the local compo­ nents of the individual local value functions:

In our example, there will be one LP variable for each joint assignment of Fl .Health and El .Health to represent the com­ ponents of VFootmanl. Similar LP variables will be included for the components of VFootman2· VEnemyl' and VEnemy2·

As before, we have a constraint for each global state s and each global action a:

This transformation has the effect of reducing the number of free variables in the LP ton (the number of objects) times the number of parameters required to describe an object's local value function. However, we still have a constraint for each global state and action, an exponentially large number.

Guestrin, Koller and Parr [6] (GKP hereafter) show that, in certain cases, this exponentially large LP can be solved efficiently and exactly. In particular, this compact solution applies when the MDP is factored (i.e., represented as a DBN), and the approximate value function is decomposed as a weighted linear combination of local basis functions, as above. Under these assumptions, GKP present a decomposi­ tion of the LP which grows exponentially only in the induced tree width of a graph determined by the complexity of the process dynamics and the locality of the basis function.

This approach applies very easily here. The structure of the DBN representing the process dynamics is highly fac­ tored, defined via local interactions between objects. Simi­ larly, the value functions are local, involving only single ob­ jects or groups of closely related objects. Often, the induced width of the resulting graph in such problems is quite small, allowing the techniques of GKP to be applied efficiently.

4 Generalizing Value Functions

Although this approach provides us with a principled way of decomposing a high-dimensional value function in certain types of domains, it does not help us address the generaliza­ tion problem: A local value function for objects in a world w does not help us provide a value function for objects in other worlds, especially worlds with different sets of objects.

To obtain generalization, we build on the intuition that dif­ ferent objects in the same class behave similarly: they share the transition model and reward function. Although they dif­ fer in their interactions with other objects, their local contri­ bution to the value function is often similar. For example, it may be reasonable to assume that different footmen have a similar long-term chance of killing enemies. Thus, we restrict our class of value functions by requiring that all of the objects in a given class share the same local value subfunction.

Formally, we define a class-based local value subfunc­ tion Vc for each class. We assume that the parameteriza­ tion of this value function is well-defined for every object o in C. This assumption holds trivially if the scope of Vc is simply Sc: we simply have a parameter for each as­ signment to Dom[Sc]. When the local value function can also depend on the states of neighboring objects, we must define the parameterization accordingly; for example, we might have a parameter for each possible joint state of a linked footman-enemy pair. Specifically rather than defin­ ing separate subfunctions VFootmanl and VFootman2· we de­ fine a class-based subfunction VFootman. Now the contri­ bution of Footman] to the global value function will be VFootman(Fl.Health,El.Health). Similarly Footman2 will contribute VFootman(F2.Health, E2.Health).

A class-based value function defines a specific value func­ tion for each world w, as the sum of the class-based local value functions for the objects in w:

This value function depends both on the set of objects in the world and (when local value functions can involve related ob­ jects) on the links between them. Importantly, although ob­ jects in the same class contribute the same function into the summation of (5), the argument of the function for an object is the state of that specific object (and perhaps its neighbors). In any given state, the contributions of different objects of the same class can differ. Thus, every footman has the same local value subfunction parameters, but a dead footman will have a lower contribution than one which is alive.

5 Finding Generalized MDP Solutions

With a class-level value function, we can easily generalize from one or more worlds to another one. To do so, we as­ sume that a single set of local class-based value functions Vc is a good approximation across a wide range of worlds w. As­ suming we have such a set of value functions, we can act in any new world w without replanning, as described in Step 3 of Fig. 3. We simply define a world-specific value function as in (5), and use it to act.

We must now optimize Vc in a way that maximizes the value over an entire set of worlds. To formalize this intuition, we assume that there is a probability distribution P( w) over the worlds that the agent encounters. We want to find a sin­ gle set of class-based local value functions {Vc }cEC that is a good fit for this distribution over worlds. We view this task as one of optimizing for a single "meta-level" MDP II*, where nature first chooses a world w, and the rest of the dynam­ ics are then determined by the MDP IIw. Precisely, the state spaceofii* is {so}UUw{(w,s) : s E S(IIw)}. The transi­ tion model is the obvious one: From the initial state s0 , nature chooses a world w according to P(w), and an initial state in w according to the initial starting distribution P~ ( s) over the states in w. The remaining evolution is then done according to w's dynamics. In our example, nature will choose the number of footmen and enemies, and define the links between them, which then yields a well-defined MDP,e.g., II2vs2·

5.1 LP Formulation

The meta-MDP II* allows us to formalize the task of finding a generalized solution to an entire class of MDPs. Specifically, we wish to optimize the class-level parameters for Vc, not for a single ground MDP IIw, but for the entire II*.

We can address this problem using a similar LP solu­ tion to the one we used for a single world in Sec. 3. The variables are simply parameters of the local class-level value subfunctions {Vc(tc ) : C E C,tc E Dom[Tc]}. For the constraints, recall that our object-based LP formulation in (4) had a constraint for each states and each action vector a= {ao}oEO[w)· In the generalized solution, the state space is the union of the state spaces of all possible worlds. Our constraint set for II* will, therefore, be a union of constraint sets, one for each world w, each with its own actions:

where the value function for a world, Vw(s), is defined at the class level as in Eq. (5). In principle, we should have an additional constraint for the state s0 . However, with a natural choice of state relevance weights a, this constraint is elimi­ nated and the objective function becomes:

if P~(s) > 0, Vs. In some models, the potential number of objects may be infinite, which could make the objective function unbounded. To prevent this problem, we assume that the P( w) goes to zero sufficiently fast, as the num­ ber of objects tends to infinity. To understand this assump­ tion, consider the following generative process for selecting worlds: first, the number of objects is chosen according to P(U); then, the classes and links of each object are cho­ sen according to P(w~ I U). Using this decomposition, we have that P(w) = P(U)P(w~ I U). The intuitive assump­ tion described above can be formalized as: Vn, P(U = n) ::; ~~e->.1n; for some~~ 2:: >.~ > 0. Thus, the distribution P(U) over number of objects can be chosen arbitrarily, as long as it is bounded by some exponentially decaying function.

5.2 Sampling worlds

The main problem with this formulation is that the size of the LP - the size of the objective and the number of con­ straints - grows with the number of worlds, which, in most situations, grows exponentially with the number of possible objects, or may even be infinite. A practical approach to ad­ dress this problem is to sample some reasonable number of worlds from the distribution P(w), and then to solve the LP

for these worlds only. The resulting class-based value func­ tion can then be used for worlds that were not sampled.

We will start by sampling a set 'D of m worlds according to P(w). We can now define our LP in terms of the worlds in 'D, rather than all possible worlds. For each world win 'D, our LP will contain a set of constraints of the form presented in Eq. (4). Note that in all worlds these constraints share the variables Vc , which represent our class-based value function. The complete LP is given by:

where P~(To) is the marginalization of P~(So) to the vari­ ables in T 0 · For each world, the constraints have the same form as the ones in Sec. 3. Thus, once we have sampled worlds, we can apply the same LP decomposition techniques of GKP to each world to solve this LP efficiently. Our gener­ alization algorithm is summarized in Step 2 of Fig. 3.

The solution obtained by the LP with sampled worlds will, in general, not be equal to the one obtained if all worlds are considered simultaneously. However, we can show that the quality of the two approximations is close, if a sufficient num­ ber of worlds are sampled. Specifically, with a polynomial number of sampled worlds, we can guarantee that, with high probability, the quality of the value function approximation obtained when sampling worlds is close to the one obtained when considering all possible worlds.

Theorem 5.1 Consider the following class-based value func­ tions (each with k parameters): Vobtainedfrom the LP over all possible worlds by minimizing Eq. (7) subject to the con­ straints in Eq. (6); V obtained from the LP with the sampled worlds in (8); and V* the optimal value function of the meta­ MDP II*. For a number of sampled worlds m polynomial in (1/c, ln 1/ o, 1/(1-1), k, >.~, 1/ ~~), the error is bounded by:

with probability at least 1 - o, for any o > 0 and c > 0; where IIVIIl,Pn = l:w,sES.., P(w)P~(s) IVw(s)l, and Rmax is the maximum per-object reward. I

The proof, which is omitted for lack of space (see online ver­ sion of this paper), uses some of the techniques developed by de Farias and Van Roy [2] for analyzing constraint sampling in general MDPs. However, there are two important differ­ ences: First, our analysis includes the error introduced when sampling the objective, which in our case is a sum only over a subset of the worlds rather than over all of them as in the LP for the full meta-MDP. This issue was not previously ad­ dressed. Second, the algorithm of de Farias and Van Roy re­ lies on the assumption that constraints are sampled according to some "ideal" distribution (the stationary distribution of the optimal policy). Unfortunately, sampling from this distribu­ tion is as difficult as computing a near-optimal policy. In our analysis, after each world is sampled, our algorithm exploits the factored structure in the model to represent the constraints exactly, avoiding the dependency on the "ideal" distribution.

6 Learning Classes of Objects

The definition of a class-based value function assumes that all objects in a class have the same local value function. In many cases, even objects in the same class might play differ­ ent roles in the model, and therefore have a different impact on the overall value. For example, if only one peasant has the capability to build barracks, his status may have a greater impact. Distinctions of this type are not usually known in ad­ vance, but are learned by an agent as it gains experience with a domain and detects regularities.

We propose a procedure that takes exactly this approach: Assume that we have been presented with a set 1) of worlds w. For each world w, an approximate value function Vw = LoEO[w] Va was computed as described in Sec. 3. In addi­ tion, each object is associated with a set of features Fw[o] . For example, the features may include local information, such as whether the object is a peasant linked to a barrack, or not, as well as global information, such as whether this world con­ tains archers in addition to footmen. We can define our "train­ ing data" 1) as { (Fw[o], Va) : o E O[w], wE V}.

We now have a well-defined learning problem: given this training data, we would like to partition the objects into classes, such that objects of the same class have similar value functions. There are many approaches for tackling such a task. We choose to use decision tree regression, so as to con­ struct a tree that predicts the local value function parameters given the features. Thus, each split in the tree corresponds to a feature in Fw[o]; each branch down the tree defines a subset of local value functions in 1) whose feature values are as de­ fined by the path; the leaf at the end of the path is the average value function for this set. As the regression tree learning al­ gorithm tries to construct a tree which is predictive about the local value function, it will aim to construct a tree where the mean at each leaf is very close to the training data assigned to that leaf. Thus, the leaves tend to correspond to objects whose local value functions are similar. We can thus take the leaves in the tree to define our subclasses, where each subclass is characterized by the combination of feature values specified by the path to the corresponding leaf. This algorithm is sum­ marized in Step I of Fig. 3. Note that the mean subfunction at a leaf is not used as the value subfunction for the correspond­ ing class; rather, the parameters of the value subfunction are optimized using the class-based LP in Step 2 of the algorithm.

7 Experimental results

We evaluated our generalization algorithm on two domains: computer network administration and Freecraft.

7.1 Computer network administration

For this problem, we implemented our algorithm in Matlab, using CPLEX as the LP solver. Rather than using the full LP decomposition of GKP [6], we used the constraint genera­ tion extension proposed in [13), as the memory requirements

I. Learning Subclasses:

• Input:
• A set of training worlds D .
• Asetoffeatures.Fw[o].
• Algorithm:
• (a) For each w E D, compute an object-based value function, as described in Sec. 3.
• (b) Apply regression tree learning on { (Fw [o], Vo) : o E O[w],w ED}.
• (c) Define a subclass for each leaf, characterized by the fea­ ture vector associated with its path.

2. Computing Class-Based Value Function:

• Input:
• A set of (sub)class definitions C.
• A template for {Vc : C E C}.
• A set of training worlds D.
• Algorithm:
• (a) Compute the parameters for {Vc : C E C} that optimize the LP in (8) relative to the worlds in D.

3. Acting in a New World:

• Input:
• A set of local value functions {Vc : C E C}.
• A set of (sub)class definitions C.
• A world w.
• Algorithm: Repeat
• (a) Obtain the current state s.
• (b) Determine the appropriate class C for each o E O[w] ac­ cording to its features.
• (c) Define Vw according to (5).
• (d) Use the coordination graph algorithm of GKP to com­ pute an action a that maximizes R(s, a)+ r I:., P(s' I s,a)Vw(s').
• (e) Take action a in the world.

Figure 3: The overall generalization algorithm.

were lower for this second approach. We experimented with the multiagent computer network examples in [6], using vari­ ous network topologies and "pair" basis functions that involve states of neighboring machines (see [6)). In one of these prob­ lems, if we have n computers, then the underlying MDP has gn states and 2n actions. However, the LP decomposition algorithm uses structure in the underlying factored model to solve such problems very efficiently [6] .

We first tested the extent to which value functions are shared across objects. In Fig. 4(a), we plot the value each ob­ ject gave to the assignment Status = working, for instances of the 'three legs' topology. These values cluster into three classes. We used CART® to learn decision trees for our class partition. In this case, the learning algorithm partitioned the computers into three subclasses illustrated in Fig. 4(b): 'server', 'intermediate', and 'leaf'. In Fig. 4(a), we see that 'server' (third column) has the highest value, because a bro­ ken server can cause a chain reaction affecting the whole net­ work, while 'leaf' value (first column) is lowest, as it cannot affect any other computer.

We then evaluated the generalization quality of our class­ based value function by comparing its performance to that of planning specifically for a new environment. For each topol­ ogy, we computed the class-based value function with 5 sam­ pled networks of up to 20 computers. We then sampled a new network and computed for it a value function that used the same factorization, but with no class restrictions. This value function has more parameters - different parameters for each object, rather than for entire classes, which are opti­ mized for this particular network. This process was repeated for 8 sets of networks. The results, shown in Fig. 4(c), in­ dicate that the value of the policy from the class-based value function is very close to the value of replanning, suggesting that we can generalize well to new problems. We also com­ puted a utopic upper bound on the expected value of the opti­ mal policy by removing the (negative) effect of the neighbors on the status of the machines. Although this bound is loose, our approximate policies still achieve a value close to it.

Next, we wanted to determine if our procedure for learn­ ing classes yields better approximations than the ones ob­ tained from the default classes. Fig. 4(d) compares the max­ norm error between our class-based value function and the one obtained by replanning. The graph suggests that, by learning classes using our decision trees regression tree pro­ cedure, we obtain a much better approximation of the value function we would have, had we replanned.

7.2 Freecraft

In order to evaluate our algorithm in the Freecraft game, we implemented the methods in C++ and used CPLEX as the LP solver. We created two tasks that evaluate two aspects of the game: long-term strategic decision making and local tactical battle maneuvers. Our Freecraft interface, and scenarios for these and other more complex tasks are publicly available at: http' I /dags. stanford.edu/Freecraft/. For each task we designed an RMDP model to represent the system, by consulting a "domain expert". After planning, our policies were evaluated on the actual game. To better visualize our results, we direct the reader to view videos of our policies at a website: http: I / robot ics . stanford . edu/.....,guestrin/Research/Generalization/.

This website also contains details on our RMDP model. It is important to note that, our policies were constructed relative to a very approximate model of the game, but evaluated against the real game.

In the tactical model, the goal is to take out an opposing enemy force with an equivalent number of units. At each time step, each footman decides which enemy to attack. The enemies are controlled using Freecraft's hand-built strategy. We modelled footmen and enemies as each having 5 "health points", which can decrease as units are attacked. We used a simple aggregator to represent the effect of multiple attack­ ers. To encourage coordination, each footman is linked to a "buddy" in a ring structure. The local value functions include terms over triples of linked variables. We solved this model for a world with 3 footmen and 3 enemies, shown in Fig. 4(e). The resulting policy (which is fairly complex) demonstrates successful coordination between our footmen: initially all three footmen focus on one enemy. When the enemy be­ comes injured, one footman switches its target. Finally, when the enemy is very weak, only one footman continues to at­ tack it, while the others tackle a different enemy. Using this policy, our footmen defeat the enemies in Freecraft.

The factors generated in our planning algorithm grow ex­ ponentially in the number of units, so planning in larger mod­ els is infeasible. Fortunately, when executing a policy, we instantiate the current state at every time step, and action se­ lection is significantly faster [6] . Thus, even though we can­ not execute Step 2 in Fig. 3 of our algorithm for larger sce­ narios, we can generalize our class-based value function to a world with 4 footmen and enemies, without replanning using only Step 3 of our approach. The policy continues to demon­ strate successful coordination between footmen, and we again beat Freecraft's policy. However, as the number of units in­ creases, the position of enemies becomes increasingly impor­ tant. Currently, our model does not consider this feature, and in a world with 5 footmen and enemies, our policy loses to Freecraft in a close battle.

In the strategic model, the goal is to kill a strong enemy. The player starts with a few peasants, who can collect gold or wood, or attempt to build a barrack, which requires both gold and wood. All resources are consumed after each Build ac­ tion. With a barrack and gold, the player can train a footman. The footmen can choose to attack the enemy. When attacked, the enemy loses "health points", but fights back and may kill the footmen. We solved a model with 2 peasants, I barrack, 2 footmen, and an enemy. Every peasant was related to a "cen­ tral" peasant and every footman had a "buddy". The scope of our local value function included triples between related objects. The resulting policy is quite interesting: the peasants gather gold and wood to build a barrack, then gold to build a footman. Rather than attacking the enemy at once, this foot­ man waits until a second footman is built. Then, they attack the enemy together. The stronger enemy is able to kill both footmen, but it becomes quite weak. When the next footman is trained, rather than waiting for a second one, it attacks the now weak enemy, and is able to kill him. Again, planning in large scenarios is infeasible, but action selection can be per­ formed efficiently. Thus, we can use our generalized value function to tackle a world with 9 peasants and 3 footmen, without replanning. The 9 peasants coordinate to gather re­ sources. Interestingly, rather than attacking with 2 footmen, the policy now waits for 3 to be trained before attacking. The 3 footmen kill the enemy, and only one of them dies. Thus, we have successfully generalized from a problem with about 10 6 joint state-action pairs to one with over 10 13 pairs.

8 Discussion and Conclusions

In this paper, we have tackled a longstanding goal in planning research, the ability to generalize plans to new environments. Such generalization has two complementary uses: First we can tackle new environments with minimal or no replanning. Second it allows us to generalize plans from smaller tractable environments to significantly larger ones, which could not be solved directly with our planning algorithm. Our experimen­ tal results support the fact that our class-based value function generalizes well to new plans and that the class and subclass structure discovered by our learning procedure improves the quality of the approximation. Furthermore, we successfully demonstrated our methods on a real strategic computer game, which contains many characteristics present in real-world dy­ namic resource allocation problems.

Several other papers consider the generalization problem. Several approaches can represent value functions in general terms, but usually require it to be hand-constructed for the particular task. Others [12; 8; 4] have focused on reusing so­ lutions from isomorphic regions of state space. By compari­ son, our method exploits similarities between objects evolv­ ing in parallel. It would be very interesting to combine these two types of decomposition. The work of Boutilier et al. [ 1] on symbolic value iteration computes first-order value func­ tions, which generalize over objects. However, it focuses on computing exact value functions, which are unlikely to gen­ eralize to a different world. Furthermore, it relies on the use of theorem proving tools, which adds to the complexity of the approach. Methods in deterministic planning have focused on generalizing from compactly described policies learned from many domains to incrementally build a first-order policy [9; 11]. Closest in spirit to our approach is the recent work of Yoon et al. [ 17], which extends these approaches to stochastic domains. We perform a similar procedure to discover classes by finding structure in the value function. However, our ap­ proach finds regularities in compactly represented value func­ tions rather than policies. Thus, we can tackle tasks such as multiagent planning, where the action space is exponentially large and compact policies often do not exist.

The key assumption in our method is interchangeability between objects of the same class. Our mechanism for learn­ ing subclasses allows us to deal with cases where objects in the domain can vary, but our generalizations will not be successful in very heterogeneous environments, where most objects have very different influences on the overall dynam­ ics or rewards. Additionally, the efficiency of our LP solu­ tion algorithm depends on the connectivity of the underlying problem. In a domain with strong and constant interactions between many objects (e.g., Robocup), or when the reward function depends arbitrarily on the state of many objects (e.g., Blocksworld), the solution algorithm will probably not beef­ ficient. In some cases, such as the Freecraft tactical domain, we can use generalization to scale up to larger problems. In others, we could combine our LP decomposition technique with constraint sampling [2] to address this high connectiv­ ity issue. In general, however, extending these techniques to highly connected problems is still an open problem. Finally, although we have successfully applied our class-value func­ tions to new environments without replanning, there are do­ mains where such direct application would not be sufficient to obtain a good solution. In such domains , our generalized value functions can provide a good initial policy, which could be refined using a variety of local search methods.

We have assumed that relations do not change over time. In many domains (e.g., Blocksworld or Robocup) , this as­ sumption is false. In recent work, Guestrin et al. [7] show that context-specific independence can allow for dynamically changing coordination structures in multiagent environments. Similar ideas may allow us to tackle dynamically changing relational structures.

In summary, we believe that the class-based value func­ tions methods presented here will significantly further the ap­ plicability of MDP models to large-scale real-world tasks.

Acknowledgements We are very grateful to Ron Parr for many useful discussions. This work was supported by the DoD MURI program, administered by the Office of Naval Research under Grant N00014-00-l-0637, and by Air Force contract F30602-00-2-0598 under DARPA's TASK program.