SMDP Homomorphisms: An Algebraic Approach to Abstraction in Semi-Markov Decision Processes

1 Introduction

The ability to form abstractions is one of the features that al­ lows humans to operate effectively in complex environments. We systematically ignore information that we do not need for performing the immediate task at hand. While driving, for example, we may ignore details regarding clothing and the state of our hair. Researchers in artificial intelligence (AI), in particular machine learning (ML), have long recognized that applying computational approaches to operating in complex and real-world domains requires that we incorporate the abil­ ity to handle and form useful abstractions. In this article we consider the question of what constitutes a useful abstraction. Since this is a difficult problem when stated in general terms, much of the work in this field is specialized to particular classes of problems or specific modeling paradigms. In this work we will focus on Markov decision processes (MDPs), a formalism widely employed in modeling and solving stochas­ tic sequential decision problems and semi-Markov decision processes (SMDPs), an extension to MDPs recently em­ ployed in modeling hierarchical systems [Sutton eta/., 1999; Dietterich, 2000; Parr and Russell, 1997].

Our objective in this article is to introduce the concept of an SMDP homomorphism and argue that it provides a unified view of key issues essential for a rigorous treatment of ab­ straction for stochastic dynamic decision processes. The con­ cept of a homomorphism between dynamic systems, some­ times called a "dynamorphism" [Arbib and Manes, 1975], has played an important role in theories of abstract automata [Hartmanis and Steams, 1966], theories of modeling and simulation [Zeigler, 1972], and it is frequently used by re­ searchers studying model checking approaches to system val­ idation [Emerson and Sistla, 1996]. Although those study­ ing approximation and abstraction methods for MDPs and SMDPs have employed formalisms that implicitly embody the idea of a homomorphism, they have not made explicit use of the appropriate homomorphism concept. We provide what we claim is the appropriate concept and give examples of how it can be widely useful as the basis of the study of abstraction in a dynamic setting.

Informally, the kind of homomorphism we consider is a mapping from one dynamic system to another that eliminates state distinctions while preserving the system's dynamics. We present a definition of homomorphisms that is appropriate for SMDPs. In earlier work [Ravindran and Barto, 2002] we de­ veloped an MDP abstraction framework based on our notion of an MDP homomorphism. This framework extended the MDP minimization framework proposed by [Dean and Gi­ van, 1997] and enabled the accommodation of redundancies arising from symmetric equivalence of the kind illustrated in Figure I. While we can derive reduced models with a smaller state set by applying minimization ideas, we do not neces­ sarily simplify the description of the problem in terms of the number of parameters required to describe it. But MDPs of­ ten have additional structure associated with them that we can exploit to develop compact representations. By inject­ ing structure in the definition of SMDP homomorphism we can model abstraction schemes for structured MDPs. In this paper we present one simple example of such an abstraction scheme and mention other factored abstraction methods that can be modeled by suitable structured homomorphisms.

In the second part of the paper we extend the notion of SMDP homomorphism to hierarchical systems. In particu­ lar, we apply homomorphisms in the options framework in­ troduced by [Sutton et al., 1999] and show that this facili­ tates employing different abstractions at different levels of

· ·+

a hierarchy. We also argue that homomorphisms allow us to model aspects of symbolic AI techniques in represent­ ing higher level task structure. Finally, we show that the SMDP homomorphism conditions generalize the "safe" state abstraction conditions for hierarchical systems introduced by [Dietterich, 2000].

After introducing some notation (Section 2), we define SMDP homomorphisms and discuss modeling symmetries (Section 3). Then we present a brief overview of our model minimization framework (Section 4), discuss abstraction in factored MDPs (Section 5) and abstraction in hierarchical systems (Section 6). We conclude with some discussion of directions for future research (Section 7).

2 Notation

A Markov Decision Process is a tuple (S, A, \li, P, R), where S = { 1, 2, · · · , n} is a set of states, A is a finite set of actions, \li ~ S x A is the set of admissible state-action pairs, P : \li x S ---.. [0, 1] is the transition probability function with P(s, a, s') being the probability of transition from state s to state s' under action a, and R : \li ---.. R is the expected reward function, with R( s, a) being the expected reward for performingactionainstates. LetA8 = {a/(s,a) E \li} ~A denote the set of actions admissible in state s. We assume that for all s E S, A 8 is non-empty.

A discrete time semi-Markov decision process (SMDP) is a generalization of an MDP in which actions can take variable amounts of time to complete. As with an MDP, an SMDP is a tuple (S, A, W, P, R), where S, A and \li are the sets of states, actions and admissible state-action pairs; P : \li x S x 1N ---.. [0, 1] is the transition probability function with P(s, a, s', N) being the probability of transition from state s to state s' under action a in N time steps, and R : \li x 1N ---.. R is the expected discounted reward function, with R(s, a, N) being the expected reward for performing action a in state s and completing it in N time steps. 1

A stochastic policy, 1r, is a mapping from \lito the real in­ terval [0, 1] with LaEA. 1r(s, a) = 1 for all s E S. For any

1 We are adopting the formalism of[Dietterich, 2000].

(s, a) E \li, 1r(s, a) gives the probability of executing action a in states. The value of a state-action pair (s , a) under policy 1r is the expected value of the sum of discounted future re­ wards starting from state s, taking action a, and following 1r thereafter. When the SMDP has well defined terminal states, we often do not discount future rewards. In such cases an SMDP is equivalent to an MDP and we will ignore the tran­ sition times. The action-value function, Q-rr, corresponding to a policy 1r is the mapping from state-action pairs to their values. The solution of an MDP is an optimal policy , 1r* , that uniformly dominates all other possible policies for that MDP.

Let B be a partition of a set X. For any x E X , [x] 8 denotes the block of B to which x belongs. Any function f from a set X to a set Y induces a partition (or equivalence relation) on X, with [x] 1 = [x'] 1 if and only if f(x) = f( x').

3 SMDP Homomorphisms

A homomorphism from a dynamic system M to a dynamic system M' is a mapping that preserves M 's dynamics, while in general eliminating some of the details of the full system M. One can think of M' as a simplified model of M that is nevertheless a valid model of M with respect to the as­ pect's of M's state that it preserves. The specific definition of homomorphism that we claim is most useful for MDPs and SMDPs is as follows:

Definition: An SMDP homomorphism h from an SMDP M = (S, A, \li , P, R) to an SMDP M' = (S', A', w', P', R') is a swjection from \li to w', defined by a tuple of surjections (f,g1,g2 , ···, gn), with h((s, a)) = (f(s), g8 (a)), where f : S ---.. S' and 9s : As ___.. Af(s) for s E S, such that Vs, s' E S, a E As and for all N E lN:

We call M' the homomorphic image of M under h, and we use the shorthand h(s, a) to denote h((s, a)). The swjection f maps states of M to states of M', and since it is gener­ ally many-to-one, it generally induces nontrivial equivalence classes of states s of M: [s] 1 . Each surjection g8 recodes the actions admissible in state s of M to actions admissible in state f(s) of M'. This state-dependent recoding of actions is a key innovation of our definition, which we discuss in more detail below. Condition (1) says that the transition probabili­ ties in the simpler SMDP M' are expressible as sums of the transition probabilities of the states of M that f maps to that same state in M'. This is the stochastic version of the stan­ dard condition for homomorphisms of deterministic systems that requires that the homomorphism commutes with the sys­ tem dynamics [Hartmanis and Steams, 1966]. Condition (2) says that state-action pairs that have the same image under h have the same expected reward. An MDP homomorphism is similar to an SMDP homomorphism except that the condi­ tions (1) and (2) apply only to the states and actions and not to the transition times.

The state-dependent action mapping allows us to model symmetric equivalence in MDPs and SMDPs. For example, if h = (!, 91, 92, · · ·, 9n) is a homomorphism from the grid­ world of Figure 1(a) to that of Figure 1(b), then f(A) = f(B) is the state marked {A, B} in Figure l(b). Also 9A(E) = 9B(N) = E, 9A(W) = 9B(S) = W, and so on. Whereas [Zinkevich and Balch, 2001] defined symmetries ofMDPs by employing equivalence relations on the state-action pairs, we explicitly formalize the notion of SMDP symmetries employ­ ing SMDP homomorphisms and group theoretic concepts.

Definitions: An SMDP homomorphism h (!,91,92,···,9n) from SMDP M (S,A,\J!,P,R) to SMDP M' = (S', A', \II', P', R') is an SMDP isomor­ phism from M to M' if and only iff and 9s, s E S, are bijective. M is said to be isomorphic toM' and vice versa. An SMDP isomorphism from an SMDP M to itself is an automorphism of M.

The set of all automorphisms of an SMDP M, denoted by AutM, forms a group under composition of homomor­ phisms. This group is the symmetry group of M. In the grid world example of Figure 1, the symmetry group consists of the identity map on states and actions, a reflection of the states about the NE-SW diagonal and a swapping of actions N and E and of actions S and W. Any subgroup of the sym­ metry group of an SMDP induces an equivalence relation on \II, which can also be induced by a suitably defined homo­ morphism [Ravindran and Barto, 200 1]. Therefore we can model symmetric equivalence as a special case of homomor­ phic equivalence.

4 Minimization

The notion of homomorphic equivalence immediately gives us an SMDP minimization framework. In [Ravindran and Barto, 2001] we extended the minimization framework of Dean and Givan [Dean and Givan, 1997; Givan eta!., 2003] to include state-dependent action recoding and showed that if two state-action pairs have the same image under a homo­ morphism, then they have the same optimal value. We also showed that when M' is a homomorphic image of an MDP M, a policy in M' can induce a policy in M that is closely related. Specifically a policy that is optimal in M' can induce an optimal policy in M . Thus we can solve the original MDP by solving a homomorphic image. It is easy to extend these results to SMDP models.

Thus the goal of minimization is to derive a minimal image of the SMDP, i.e. , a homomorphic image with the least num­ ber of admissible state-action pairs. We also adapted an exist­ ing minimization algorithm to find minimal images employ­ ing state-action equivalence. Employing state-dependent ac­ tion recoding allows us to achieve greater reduction in model size than possible with Dean and Givan's framework. For ex­ ample, the gridworld in Figure 1(a) is minimal if we do not consider state-dependent action mappings.

5 Abstraction in Structured MDPs

SMDP homomorphisms can also be used to model various SMDP abstraction frameworks. The definition of homomor­ phism in Section 3 assumed a monolithic representation of the state set. While we can derive an equivalent MDP model with a smaller \II, it does not follow that the description of the state set is necessarily simpler and hence might not lead to a simpler problem representation. Many classes of problems that are modeled as MDPs have some inherent structure. We define structured forms of homomorphisms that can exploit this structure in deriving simpler problem representations.

Factored MDPs are a popular way to model structure in MDPs. A factored MDP is described, as before, by the tuple (S, A , \II, P, R). The state set S is now given by M features or variables, S ~ Il~ 1 S;, where S; is the set of permis­ sible values for feature i. Thus any s E S is of the form s = (s1 , ... , sM), where s; E S; for all i. The elements of S are still uniquely labeled 1 through n. The transition probabilities P are often described by a two-slice temporal Bayesian network (2-TBN) [Dean and Kanazawa, 1989]. A 2-TBN is a two layer directed acyclic graph, whose nodes are {s1 , ... , SM} and {s~, ... , s~ }. Heres; denotes the value of feature i in the present state and s~ denotes the value of feature i in the resulting state. An arc from node s; to node sj indicates that the sj depends on s;. Many classes of struc­ tured problems may be modeled by a 2-TBN in which the arcs are restricted to go from nodes in the first set to those in the second. The state-transition probabilities can be factored as:

where Pre( s~, a) denotes the parents of node s~ in the 2-TBN corresponding to action a and each of the Prob(s~IPre(s~ , a)) is given by a conditional probability table (CPT) associated with node s~. The reward function may be similarly repre­ sented.

Structuring the state space representation allows us to con­ sider morphisms that are structured, i. e. smjections from one structured set to another. An example of a structured mor­ phism is a simple projection onto a subset of features. Here the state set of the homomorphic image is described by a sub­ set of the features, while the rest are ignored. We introduce some notation, after [Zeigler, 1972], to make the following definitions easier. Given a structured set X ~ Il~1 X;, the i-th projection of X is a mapping p; : X --+ X;, de­ fined by p;((x1, ... ,xM)) = x;. We extend this defini­ tion to that of a projection on a subset of features. Given a set J ~ {1, ... , M} the ]-projection of X is a mapping PJ :X --+ IljEJ Xj, defined by PJ = IljEJ Pi·

Definition: A simple projection homomorphism h from a structured MDP M = (S, A, \II, P, R) to a structured MDP M' = (S', A', \II', P', R') is a smjection from \II to \II', defined by a tuple of surjections (!,91,92, · · · ,9n), with h(s,a) = (f(s),9s(a)), where f = PF : S --+ S', where F ~ {1, ... , M} and 9s : As --+ Af(s) for s E S, such that Vs ,s' E S,a E As:

The first condition implies that the subset F should be cho­ sen such that the features chosen are sufficient to describe the block transition dynamics of the system. In other words, the subgraph of the 2-TBN described by the projection should in­ clude all the incoming arcs incident on the chosen nodes. The second condition requires that all the parents and the incom­ ing arcs to the reward node are also included in the subgraph. To find such homomorphic projections, we just need to work back from the reward node including arcs and nodes, until we reach the desired subgraph. Such an algorithm will run in time polynomial in the number of features. It is evident that the space of such simple projections is much smaller than that of general maps and in general may not contain a ho­ momorphism reducing a given MDP. Without suitable con­ straints, often derived from prior knowledge of the structure of the problem, searching for general structured homomor­ phisms results in a combinatorial explosion. Abstraction al­ gorithms developed by Boutilier and colleagues can be mod­ eled as converging to constrained forms of structured mor­ phisms assuming various representations of the CPTs-when the space of morphisms is defined by boolean formulae of the features [Boutilier and Dearden, 1994], when it is defined by decision trees on the features [Boutilier et al., 1995] and when it is defined by first-order logic formulae [Boutilier et a/., 2001].

6 Abstraction in Hierarchical Systems

In the previous section we showed that SMDP homomor­ phisms can model various abstraction schemes in "flat" MDPs and SMDPs. SMDP homomorphisms are a convenient and powerful formalism for modeling abstraction schemes in hierarchical systems as well. Before we explore various ab­ straction approaches we first introduce a hierarchical archi­ tecture that supports abstraction.

6.1 Hierarchical Markov Options

Recently several hierarchical reinforcement learning frame­ works have been proposed [Parr and Russell, 1997; Sutton et a/., 1999; Dietterich, 2000] all of which use the SMDP for­ malism. In this article the hierarchical framework we adopt is the options framework [Sutton et al. , 1999], though the ideas developed here are more generally applicable. Options are actions that take multiple time steps to complete. They are usually described by: the policy to follow while the option is executing, the set of states in which the option can begin exe­ cution, and the termination function (3 which gives the prob­ ability with which the option can terminate in a given state. The resulting systems are naturally modeled as SMDPs with the transition time distributions induced by the option poli­ cies. We present an extension to the options framework that readily facilitates modeling abstraction at multiple levels of the hierarchy using SMDP homomorphisms.

We consider the class of options known as Markov options, whose policies satisfy the Markov property and that terminate on achieving a certain sub-goal. In such instances it is possi­ ble to implicitly define the option policy as the solution to an option MDP, or an option SMDP if the option has access to other options. Accordingly we define a hierarchical Markov sub-goal option:

Definition: A hierarchical Markov sub-goal option of an SMDP M = (S,A, ii!,P,R) is the tuple 0 = (Mo,I,(J), where I<;; Sis the initiation set of the option, (3 : S __, [0, 1], is the termination function and Mo is the option SMDP.

The state set of Mo is a subset of Sand constitutes the do­ main of the option. The action set of M o is a subset of A and may contain other options as well as "primitive" actions in A. The reward function of Mo is chosen to reflect the sub-goal of the option. The transition probabilities of Mo are induced by P and the policies of lower level options. We assume that the lower-level options are following fixed poli­ cies which are optimal in the corresponding option SMDPs. The option policy 7l' is obtained by solving Mo, treating it as an episodic task with the possible initial states of the episodes given by I and the termination of each episode determined by the option's termination function (3.

For example, in the gridworld task shown in Figure 2(a), an option to pick up the object and exit room I can be defined as the solution to the problem shown in 2(b ), with a suitably defined reward function. The domain and the initiation set of the option are all states in the room and the option terminates on exiting the room with or without the object.

6.2 Option Specific Abstraction

The homomorphism conditions (1) and (2) are very strict and frequently we end up with trivial homomorphic images when deriving abstractions based on a non-hierarchical SMDP. But it is often possible to derive non-trivial reductions if we re­ strict attention to certain sub-problems, i.e., certain sub-goal options. In such cases we can apply the ideas discussed in Sections 4 and 5 to an option SMDP directly to derive abstrac­ tions that are specific to that option. The problem of learning the option policy is transformed to the usually simpler prob­ lem of learning an optimal policy for the homomorphic im­ age.

6.3 Relativized Options

Consider the problem of navigating in the gridworld environ­ ment shown in Figure 2(a). The goal is to reach the central corridor after collecting all the objects in the environment. No non-trivial homomorphic image exists of the entire prob­ lem. But there are many similar components in the problem, namely, the five sub-tasks of getting the object and exiting roomi. We can model these similar components by a "par­ tial" homomorphic image-where the homomorphism con­ ditions are applicable only to states in the rooms. One such partial image is shown in Figure 2(b ). Employing such an ab­ straction lets us compactly represent a related family of op­ tions, in this case the tasks of collecting objects and exiting each of the five rooms, using a single option MDP. We refer to this compact option as a relativized option. Such abstrac­ tions are an extension of the notion of relativized operators introduced by [lba, 1989]. Formally we define a relativized option as follows:

Definition: A relativized option of an SMDP M (S, A, ii!, P, R) is the tuple 0 = (h,Mo,I,(J), where I<;; Sis the initiation set, (3 : S' --> [0, 1] is the termination func­ tion and h = (f,g1,g2, · · · ,gn) is a partial homomorphism from the SMDP (S, A, ii!, P, Ro) to the option SMDP Mo with Ro chosen based on the sub-task.

Here the state set of Mo isS' = f(So), where So is the domain of the option, and the admissible state-action set is h(w) . Going back to our example in Figure 2(a), we can now de~ne a sing~e get-object-and-leave-room relativized option us_mg t~e optiOn MOP of Figure 2(b ). The policy learned in t~Is option MOP can then be suitably lifted to M to provide different policy fragments in the different rooms. Figure 3 demonstrates the speed-up in performance when using a sin­ gle relativized option as opposed to five regular options. In this experiment the option policies and the higher level pol­ icy were learned simultaneously. 2

6.4 Modeling Higher Level Structure

SMOP homomorphisms have the power to model a broader class of abstractions, those not supported by the base level dynamics of the system but which can be induced at some intermediate levels of the hierarchy. For example, consider a multi-link assembly line robot arm that needs to move ob­ jects from one assembly line to another. The state of the sys­ tem is described by the joint angles and velocities, object­ shape, object-o_rien~ation, and Boolean variables indicating :vhether the object Is firmly-grasped and whether the object IS at-target-location. The primitive actions are various joint torques. Depending on the configuration of the arm and the shape and orientation of the object, this task requires different sequ~nces of actions, or policies, even though conceptually the h1gh~r level task has the same "structure"-grasp object, move object, and place object.

_w_e can ~ode! this higher level task structure using a rel­ ~tiv1zed optiOn. First, we define suitable grasp-object op­ tiOns, such as grasp-cylinder, grasp-block etc. , and simi­ lar options for moving and placing objects. Then we form a partial homomorphic image of the resulting SMDP-the state set of the image is described by the two Boolean fea­ tures and the action set consists of grasp, move and place actions. The partial homomorphism, which applies only to the admissible state-option pairs of the SMOP, consists of f = P J, where J = { firmly-grasped, at-target-location } and 9 (-,object-shape) (grasp-object-shape) =grasp for all object-shape and similarly for the move-object and place­ object options. A relativized option with this partial image and partial homomorphism as the option MOP and option homomorphism, respectively, captures the desired conceptual ~truc~re. Executing the optimal policy for this option results m ac~IOn sequences of the form: grasp, move, place, . . .. Oe­ pen~mg on the object-shape these abstract actions get bound to ~1fferent lower level options. While techniques in sym­ bolic AI have long been able to model such higher level task structure, the reinforcement learning community lacked an obvious mechanism to do the same. Our work gives us new tools to model conceptual task structure at various temporal and spatial scales.

2 In [Ravindran and Barto, 2002] we have reported more detailed experiments in this setting.

6.5 Relation to MaxQ Safe State-abstraction

[Oietterich, 2000] introduced safe state-abstraction condi­ tions for the MaxQ architecture, a hierarchical learning framework related to the options framework. These condi­ tions ensure that the resulting abstractions do not result in any loss of performance. He assumes that the sub-problems at dif­ ferent levels of the hierarchy are specified by factored MOPs. The MaxQ architecture employs a form of value function de­ composition ~nd some of the safe abstraction conditions ap­ ~ly ~nly to th1s _form of decomposition. The following condi­ tiOn 1s more umversal and applies to the hierarchical Markov options framework as well:

Definition: A Projection PJ is safe if: (i) for all (s a) in \[J and s' inS, ~(s,a,s' , N) ~ Prob(p1 (s'),Nip1 (s),a) x Prob(PM-J(s )ls,a), and (u) for all (s,a),(t ,a) in \[J , if PJ(s) = PJ(t), then R(s, a, N) = R(t, a, N).

Condition (i) states that the transition probability can be ex~ressed as a pr~duct of two probabilities, one of which de­ scnbes the evolution of a subset of the features and depends only on that subset. Condition (ii) states that if two states ?roject_ to the same abstract state, then they have the same 1mmed1ate reward. From equations 1-4, it is evident that the above conditions are equivalent to the SMOP homomorphism conditions if we restrict our attention to simple projection ho­ momorphisms and do not consider action remapping. Thus th~ SM~P h?momorphism conditions introduced here gener­ alize 01ettench's safe state-abstraction condition as applica­ ble to the hierarchical Markov option framework.

7 Discussion

The equivalence classes induced by SMDP homomorphisms satisfy the stochastic version of the substitution property [Hartmanis and Steams, 1966]. This property is also closely related to lumpability in Markov chains [Kemeny and Snell, 1960] and bisimulation homogeneity [Givan eta!., 2003] in MDPs. We chose the SMDP homomorphism as our basic formalism because we believe that it is a simpler notion and provides a more intuitive explanation of various abstraction schemes.

The homomorphism conditions (1) and (2) are very strict conditions that are often not met exactly in practice. One ap­ proach is to relax the homomorphism conditions somewhat and allow small variations in the block transition probabil­ ities and rewards. We have explored this issue [Ravindran and Barto, 2002], basing our approximate homomorphisms on the concept of Bounded-parameter MDPs developed by [Givan eta!., 2000]. We are currently working on extending approximate homomorphisms to hierarchical systems so as to accommodate variations in transition-time distributions.

Although SMDP homomorphisms are powerful tools in modeling abstraction, finding a minimal image of a given SMDP is an NP-hard problem. While taking advantage of structure allows us to develop efficient algorithms in special cases, much work needs to be done to develop efficient gen­ eral purpose algorithms. Currently we are investigating meth­ ods that allow us to determine homomorphisms given a set of candidate transformations in a hierarchical setting.

In this article we presented a novel definition of SMDP homomorphism that employs state-dependent recoding of ac­ tions. This allows us to extend existing minimization and ab­ straction methods to a richer class of problems. We developed notions of equivalence specialized to factored representations and hierarchical architectures. We have shown that SMDP homomorphism can serve as the basis for modeling a variety of abstraction paradigms.

Acknowledgments

We wish to thank Dan Bernstein and Mike Rosenstein for many hours of useful discussion and Bob Givan and Matt Greig for clarifying certain ideas from their work. This mate­ rial is based upon work supported by the National Science Foundation under Grant No. ECS-0218125 to Andrew G. Barto and Sridhar Mahadevan. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.