Solving Factored MDPs via Non-Homogeneous Partitioning

1 Introduction

Markov Decision Processes (MDPs) employing representations that factor states, actions and their associated transition and reward functions in terms of component functions of state variables (fluents) have surfaced as plausible models for planning under uncertainty [Boutilier et al., 1999]. Since the number of states in these factored MDPs (FMDPs) is exponential in the number of fluents, traditional iterative methods that require enumerating states are typically not effective. In this paper, we solve FMDPs by constructing and refining non-homogeneous partitions of the state space. In a homogeneous partition, any two states in a block have the same reward and the same distribution with respect to transitions to other blocks. Non-homogeneous partitions allow variation among the states in a block with regard to rewards and block transition distributions. From a non-homogeneous partition, we construct an aggregate MDP by averaging the transition probabilities and the rewards within blocks.

The algorithm described in this paper solves FMDPs by successive refinement in the space of non-homogeneous partitions. We use factored representations to encode the partitions and the aggregate MDPs we construct from them. We can solve the aggregateMDPs in time polynomial in the number of blocks in the partition. The resulting optimal policies

(optimal for the aggregate MDPs) also serve as policies for the original MDP and the value function for the optimal policy in the aggregate MDP serves as an estimate for the value of the policy in the original MDP. Given this estimate and the current partition, we choose the refinement that yields the greatest improvement and iterate. In the remainder of this paper, we present some background, provide a theoretical motivation for our refinement heuristic, and describe the results of a series of experiments.

2 FactoredMDPs (FMDPs)

Definition 1 (FMDP) An FMDP is defined as a tuple  BP CU DI CGBN BTBN CCBN CACV where

• AF DI CG BP CJCG BD BN BM BM BM BNCG D2 CL is a vector of fluents which collectively define the state. We use AA CG CX to denote the set of values forCG CX . AA CG CX is the sample space of CG CX whenCG CX is considered as a random variable. Thus, the state space for  is AA DI CG BP CX AA CG CX . We use lower case letters DI DC BP CJDC BD BN BM BM BM BN DC D2 CL to denote a particular instantiation of the fluents, and CG CXBND8 and DC CXBND8 denote, respectively, a fluent and its value at a particular time D8.
• AF BT is the set of actions.
• AF CC is the set of transition probabilities, represented as the set of conditional probability distributions, one for each action and fluent:

where paB4CG CXBND8B7BD B5 denotes the set of parents of CG CXBND8B7BD in the graphical model (see below). Note that BKCXBN paB4CG CXBND8B7BD B5 AI CUCG BDBND8 BN BM BM BM BNCG D2BND8 CV.

• AF CA BM DI CG AX BO is the reward function. Without loss of generality, we define the reward to be determined by both state and action (CA BM DI CG A2 BT AX BO).

Figure 1 shows an example of a graphical model for the dynamics governing an action in a toy robot domain with five boolean variables. The robot has to deliver a cup of coffee whenever requested. Unfortunately, the coffee bar is outside the building and the robot receives a small amount of punishment if it gets wet. Each fluent denotes a particular aspect of the world: the weather outside being rainy (CA), the robot having an umbrella (CD), the robot being wet (CF), the robot holding coffee (BV), and someone wanting coffee (CFBV). Note that the probabilistic effect of each fluent at time D8B7BD is conditioned on a small number of fluents (the set of parent fluents, e.g., paB4CF D8B7BD B5 BP CUCA D8 BN CD D8 BNCF D8 CV) at time D8. The conditional probabilities are stored as trees rather than tables for further savings in the size of the representation. Thus, we complete the description of the state dynamics by specifying conditional probability trees (CPTs) [Boutilier et al., 1995] for each fluent and action. Similar representations have been used to model Markovian processes with factored state spaces, e.g., the Two-stage Temporal Bayesian Network (2TBN) [Dean and Kanazawa, 1989] and the Dynamic Bayesian Network (DBN) [Forbes et al., 1995]. The reward function CA is also designated in terms of trees.

FMDPs exploit conditional independence among the fluents given their parents in the graphical model to achieve economy of representation. However, the underlying structure in the domain that makes compact representations possible does not lead necessarily to an efficient FMDP algorithm. There are algorithms modeled after classical MDP algorithms that use dynamic programming to iteratively update a value function represented in a factored form; however, the size of the value functions so represented can easily explode. There are also algorithms that compress the value functions in an effort to prevent an explosion, e.g., using a tree representation for value functions with pruning techniques [Boutilier and Dearden, 1996], or using Algebraic Decision Diagrams (ADDs) for further reduction [Hoey et al., 1999]. These algorithms are examples of Value Function Approximation (VFA) algorithms applied to FMDPs [Gordon, 1995; Tsitsiklis and Van Roy, 1996; Koller and Parr, 1999].

3 Stochastic Bisimulation Equivalence

Dean and Givan [1997] introduce the notion of stochastic bisimulation homogeneity for FMDPs. It is an extension of the state equivalence relation for minimizing Finite State Automata (FSA) to that of probabilistic FSAs. Dean and Givan's model minimization algorithm for FMDPs partitions the state space into stable blocks.

Definition 2 (Stable Block and Homogeneous Partition)

A block BV of a partition  is said to be stable with respect to a block BU of  and an action CP if and only if every state in BV has the same transition probability of ending up in block BU by action CP. Mathematically,

where

We say that BV is stable if BV is stable with respect to every block of  and action in BT.  is said to be homogeneous if and only if every block is stable.

Given a homogeneous partition of an FMDP, we can define an aggregate MDP that is equivalent to the original FMDP. Every state within a block of a homogeneous partition has the same state dynamics with respect to any policy, i.e., the transition probability of moving into a block is the same for every state in the same block. Thus, if every state within a block of a homogeneous partition has the same reward, the partition yields a reduced model of the original FMDP.

Givan et al. [2000] introduce AF-homogeneity for finding an approximately homogeneous partition with few blocks. We say that a block BV is AF-stable with respect to BU and CP if

If every block of partition  is AF-stable with respect to every other block of  and every action, we say  is an AFhomogeneous partition. Qualitatively speaking, by relaxing the equality to be approximately equal with error within AF, we get a smaller partition than if we required strict homogeneity. The error in the optimal value function computed from an AFhomogeneous partition is discussed in the work of Singh and Yee [1994] and White and Eldeib [1994]. Most of the previous work on computing approximate solutions of FMDPs follow similar analyses [Boutilier and Dearden, 1996; St-Aubin et al., 2000].

4 Non-Homogeneous Partitions for FMDPs

There are two important questions remaining to be answered concerning partition refinement techniques for FMDPs. First, what class of functions should we allow to represent block formulae? If we restrict the representational power of the formulae too much, we may end up with large partitions but with easily manipulable block formulae. If we allow arbitrary functions, manipulating block formulae is NP-hard (see [Goldsmith and Sloan, 2000] for recent analysis.) though we can compute the coarsest homogeneous partition which may be small. Second, what if the coarsest homogeneous partition is still exponentially large compared to the description size of the FMDP? Calculating AF-homogeneous partition helps, but note that we don't have a fine control over the size of the partition - all we know is that increasing AF will generally reduce the size of the partition and decreasing it will generally do the opposite.

Based on the above observation, we describe a new state aggregation algorithm that does not search for the coarsest homogeneous partition. In fact, the technique is not driven by the notion of stochastic bisimulation homogeneity. Given an initial non-homogeneous partition of the state space, the algorithm iteratively decides which block to refine so that it produces at the end an approximately optimal policy without generating a huge partition. Thus, given a partition, the algorithm has to determine which block to refine with respect to which fluent. Note that the partitions we consider are not AF-homogeneous given that the transition probabilities can widely differ.

We show that the optimal value functions calculated on non-homogeneous partitions provide the basis for an effective heuristic for selecting the block-fluent pair to chop. First, we define how we construct the MDP from a non-homogeneous partition.

Definition 3 (MDP from Non-Homogeneous Partition)

Given an FMDP  BP B4 DI CGBN BTBN CCBN CAB5 and a non-homogeneous partition  of the state space AA DI CG , the aggregate MDP induced by  , denoted as   BP B4BN BTBN CC  BN CA  B5, is defined as

for all BUBNBV BE  and CP BE BT. CE A3  denotes the optimal value function of   , which is a mapping from AA DI CG to BO. Note that for any DI DC and DI DC BC in the same block of , CE A3  B4DI DCB5 BP CE A3  B4DI DC BC B5 and AP A3 B4DI DCB5 BP AP A3 B4DI DC BC B5.

Given a partition , the algorithm selects block BV and fluent CG for generating a refined partition  BC .  BC has the same blocks as  except for BV which is replaced by CHOPB4BN BVBN CGB5. Figure 2 illustrates how the CHOP operator generates refined blocks of BV. Recalling that D2 is the number of fluents in the domain, we note that there are at most D2CYCY different refined partitions that can be obtained by the CHOP operator. For each refined partition  BC generated by the CHOP operator, the algorithm constructs   BC and calculates the optimal value function CE A3  BC .

We will present the algorithm shortly. But first, we would like to know how good it is to use   to solve the original FMDP. We prove that given any non-homogeneous partition

 , the optimal value function of   , which we define as CE A3  , is within a bounded distance from the true value function CE A3 . To this end, we introduce a definition and a theorem from Gordon [1995] that are used in proving Theorem 2.

Definition 4 (Averager) An approximation function is an averager if, given the target vector CD, the approximation function generates CM CD defined as

where CR CX is a constant and AC CX and AC CXCY are non-negative constants such that BKCXBN AC CX B7  CY AC CXCY BP BD.

Theorem 1 (Gordon) Let CE A3 be the optimal value function for an MDP ,  the update (Bellman backup) operator for value iteration,

and BT the mapping for an averager. Let CE BT be any fixed point of BT. Given CZCE A3 A0 CE BT CZ BD BP AF, the iteration of  Æ BT converges to a value function CE ÆBT so that CZCE A3 A0 CE ÆBT CZ AK BEADAFBPB4BDA0ADB5. Approximate value iteration using BT returns BTCE ÆBT which satisfies CZCE A3 A0BTCE ÆBT CZ AK BEAFB7BEADAFBPB4BD A0 ADB5.

Theorem 2 (Bounded Distance between CE A3 and CE A3  )

Given an FMDP  BP B4 DI CGBN BTBN CCBN
BN CAB5 and a partition  of the state space AA DI CG , the optimal value function of  given as CE A3 and the optimal value function of   given as CE A3  satisfy the bound on the distance

where AF BP D1CXD2 CE  CZCE A3 A0 CE  CZ BD (CE  being any value function such that for any block BU BE  and any DI DC and DI DC BC in BU, CE  B4DI DCB5 BP CE  B4DI DC BC B5).

Proof Recall from the definition that BKDI DC BE BV,

and

We define another value function

To calculate the maximum distance between CE A3 and CQ CE A3 , we define an averager BT  as follows:

Note that each fixed point of BT  assigns the same value to states in the same block. For the example shown in Figure 3, the straight dotted line satisfying CQ CE BT B4DI DC BD B5 BP CQ CE BT B4DI DC BE B5 is the set of fixed points for BT  since DI DC BD and DI DC BE belong to the same block. Since  is a refinement of the reward partition, CQ CE A3 is the fixed point of the mapping ÆBT  , and applying the result from Gordon [1995], we have that

where AF is the distance between CE A3 and the closest fixed point of BT  . The distance between CQ CE A3 and CE A3  is calculated as follows: For any DI DC BE BV,

Since the above inequality holds for BKBV BE  , we have

1. The number of iterations , initial partition  of the state space (reward partition), and the optimal value function CE A3  for   .
2. For each block BV BE  and fluent CG CX BN BD AK CX AK D2, compute   BC where  BC is the same as  except BV is replaced by CHOPB4BN BVBN CG CX B5.
3. For each  BC , compute CE A3  BC and then select  A3 BP CPD6CV D1CPDC  BC CZCE A3  BC A0CE A3  CZ.
4. If Step 2AO3 has been run times, halt and output AP A3  A3 .
5. Set  BP  A3 and go to Step 2.

Figure 4: The algorithm for finding a non-homogeneous partition for an approximately optimal policy

By combining Equation 2 and Equation 3, we have shown that

BE

There are two remarks on the bound in the above theorem. First, AF AH D1CXD2 CE  CZCE A3 A0 CE  CZ BD that appears in the first additive term in Equation 1 measures how fine is the partition . AF is the minimum error that we can achieve by assigning values to the components of CE  , with the restriction that the values should be the same for the components that belong to the same block in . Thus, we naturally expect that a finer partition will achieve a smaller AF, although it depends on how the state space is partitioned. At least, given a partition  and its refinement  BC AI , and letting AF  and AF  BC be the AF of  and  BC respectively, we can say that AF  AL AF  BC . Note also that AF becomes 0 for a homogeneous partition. Second, CZCE A3  A0 CE A3  CZ BD in the second additive term also vanishes as the partition becomes finer. Although there is no guarantee that the error is monotonically smaller for a finer partition and larger for a coarser partition, at least this error serves as an upper bound on the distance.

The algorithm that we describe in the following selects the best refined partition  BC from the current partition  given by the formula

Theorem 2 indicates that by choosing a refinement  BC of  maximizing the distance between CE A3  BC and CE A3  there is reason to believe that we are making significant progress in approaching CE A3 . This is the same sort of argument used to justify the use of discretization strategies for continuous statespace MDPs.

The algorithm runs iteratively by refining the partition for a pre-determined number of iterations so that we end up with a fixed-size policy. Figure 4 shows the algorithm. Note that constructing   BC can be done efficiently. The new transition probability matrix CC  BC typically has many components

0.2

0.4

Figure 5: Calculating CC  BC B4BVBN CPBN BV BC B5 with decision trees.

the same as CC  . By reusing the components already calculated, we can construct the   BC s without computing transition probabilities and rewards for all blocks. For example, if the partition  BC was obtained by chopping a block BU BE  with respect to the fluent CG CX so that BU BP CUBU BD BN BM BM BM BNBU CYAA CG CX CY CV, we have

The remaining components are computed without explicitly enumerating all of the states in the blocks. Figure 5 shows how we calculate the component CC  BC B4BVBN CPBNBV BC B5 using decision trees when BV BE BU or BV BC BE BU. To compute the component, we first graft CPTs and multiply the probabilities in the terminal nodes. Since we are only interested in the transition probability related to blocks BV and BV BC , we can eliminate the branches of the constructed tree that do not intersect with block BV. This greatly reduces the size of the tree. The final step is to take the average of the items in the terminal nodes in the tree, weighted by the sizes of the blocks that the terminal nodes represent.

The reward functionCA  BC for   BC is obtained similarly.

5 Experiments

The test problems used in our experiments are adopted from Hoey et al. [1999] and involve domains with 6 to 17 binary variables (fluents). The initial probabilities are given as a uniform distribution. For each domain, we show the performance of the policy derived from the non-homogeneous partition and the cumulative elapsed time at each iteration. We use CPLEX 6.5 for calculating optimal value functions of aggregate MDPs induced by non-homogeneous partitions, and the CUDD package [Somenzi, 1998] to implement structured versions of iterative algorithms (similar to SPUDD [Hoey et al., 1999]) for evaluating the policies and calculating the optimal value functions. All experiments are run on a Sun Ultra10 with 256Mb of memory.

Figure 6 through Figure 8 illustrate the performance of the algorithm in Figure 4 on three benchmark domains. We ran the algorithm for 100 iterations, except for the COFFEE domain since it consisted of only 64 states. For each figure, the graph on the left side shows the actual performance (actual value of the optimal policy calculated from the aggregated MDP) and the heuristic value (the optimal value of the aggregated MDP) after each iteration. The values are obtained assuming uniform starting probabilities on the states. The graphs on the right sides show the plots of cumulative elapsed time (in seconds) after each iteration. Note that in some domains, there is a small gap between the actual performance and the heuristic value even when the policy from the aggregated MDP reached the optimal performance. This is due to the fact that the evaluation is done through an iterative method with the stopping condition CZCE CXB7BD A0CE CX CZ AK Æ, which we set Æ to 0.01.

The optimal value function of the EXPON domain (Figure 7) has thousands of internal nodes even when represented as an ADD. The non-homogeneous partitioning algorithm is not able to find the optimal policy with partition size less than or equal to 113, however, the policy at the end of 100th iteration performs 10 times better than the initial policy from the aggregate MDP induced by the reward partition. The size of the ADD representation for the optimal value function is also quite large in the case of the FACTORY domain (Figure 8). After 100 chops, totaling 126 blocks, the policy from the aggregated MDP has a value of 24.8 which is 87% of the optimal value.

We also experimented on the LINEAR domain (14 variables, 16,384 states). The optimal policy of the aggregate MDP from the reward partition yields the optimal value, i.e., the optimal policy was obtained without any split. It takes 23.28 seconds for 1 iteration. When the algorithm finds out that every refinement  BC of the current partition  yields CZCE A3  BC A0 CE A3  CZ BP BC, then it knows the current optimal policy from the aggregated MDP is indeed optimal. Meanwhile, our implementation of the structured value iteration using CUDD package (which is not as fully optimized as SPUDD) takes 43.58 seconds (15 leaves).

Figure 9 shows the distances between two value functions of successive aggregate MDPs for each domain. We excluded the LINEAR domain since the distances were zero from the onset. Note that in the COFFEE domain, the distance decreases sharply after the optimal policy from the aggregate MDP is actually optimal. However, the distances after that are not zero, which implies the partition is still nonhomogeneous. We do not observe such behavior in the EXPON and FACTORY domain since the algorithm was not able to yield the optimal policy. Although the distances between consecutive value functions are large, we note that the actual performance does not change much in the two domains. It is natural that a big difference in value functions does not necessarily imply a big difference in the actual performance. Sometimes, a block containing states with highly varing transition probabilities is not so important to reach for optimal performance, hence chopping the block does not greatly improve the actual performance of the policy.

We also compare the performance of non-homogeneous partitioning algorithm to APRICODD [St-Aubin et al., 2000]. Figure 10 and Figure 11 summarize the comparison of the two algorithms on the larger domains, EXPON and FACTORY. By trial and error, we tuned the pruning parameter of the APRICODD algorithm so that the size of the approximate value function from the APRICODD algorithm is comparable to that of the non-homogeneous partition at the end of 100 chops. We used "sliding-tolerance" pruning technique with different parameters. We allow two to three times more nodes in the decision diagrams than the number of blocks in the non-homogeneous partition. Often, increasing the pruning parameter so that we get smaller value functions from APRICODD results in non-converging behavior. In fact, APRICODD on the EXPON domain with pruning parameter 0.5 does not converge. In this case, we stopped the algorithm when the value functions between consecutive iterations were oscillating (500 iterations). Note that we are still allowing the APRICODD to search in the space of a much richer representation for value functions - an ADD with 246 nodes can represent a much finer partition than a partition with 113 blocks. In terms of the number of blocks, the non-homogeneous partitioning algorithm performs comparable to the APRICODD algorithm. Note also that our implementation of APRICODD is not fully optimized, and that the running times may be significantly greater than those reported by the original authors.

We are currently exploring heuristics for efficiently selecting block-fluent pairs to chop. We note that solving continuous MDPs faces a similar problem, and we are experimenting on discretization heuristics such as Munos and Moore [Munos and Moore, 1999]. A preliminary result shows that this heuristic is highly effective, yielding approximately 50-fold speed up in some domains. A preliminary report on this experiment appears in [Kim, 2001].

The above experiments show two advantages of using the non-homogeneous partitioning algorithm. First, while in some domains the coarsest homogeneous partition may be quite large, it may not be critical to compute a homogeneous partition to obtain an optimal (or near optimal) policy. Structured value iteration algorithms such as SPUDD or APRICODD may incur a large cost in representing an optimal or near optimal value function, whereas the non-homogeneous partitioning algorithm does not necessarily face such a problem. Second, the algorithm provides a new approach to finding an approximately optimal policy, which allows us to specify the desired size of the policy a priori.

6 Conclusion and RelatedWork

To achieve economy of representation many algorithms aggregate states that have the same (or roughly the same) value; they do so using a variety representations ranging from simple set representations [Bertsekas and Casta˜non, 1989], decision trees [Boutilier et al., 1995; Boutilier and Dearden, 1996] and algebraic decision diagrams [Hoey et al., 1999; St-Aubin et al., 2000], to linear combinations of simple basis functions [Koller and Parr, 1999] and neural networks [Bertsekas and Tsitsiklis, 1996].

While all that is necessary is that the states that are grouped together have the same value, it is often the case that the aggregated states have other properties in common. Structured value iteration [Boutilier et al., 1995] and structured model reduction [Dean and Givan, 1997] group states according to stochastic bisimulation equivalence. This is a sufficient but not necessary criterion and in some cases it can result in partitions that are larger than strictly necessary. In the case of (exact) structured value iteration the leaves of the decision tree constitute the blocks of a partition that is reward and transition homogeneous. The structured model reduction algorithm successively refines an initial partition by splitting non-homogeneous blocks and is guaranteed to terminate with the coarsest homogeneous partition; unfortunately, this partition could have a number of blocks exponential in the number of fluents. This paper provides a method for splitting blocks that provides a global perspective (rather than considering each block in isolation) and for which the objective is to find a non-homogeneous partition that yields an aggregate MDP and corresponding optimal value function that is "close" to the original MDP and its optimal value function. The preliminary experimental results in this paper indicate that our algorithm achieves good performance using a compact representation encoded in terms of a non-homogeneous partition that is a fraction of the size of the representations required by other approaches.

Finding a non-homogeneous partitioning algorithm with a richer representation for blocks (such as ADDs) seems promising, and this task remains as our future work.