We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces. We intro duce a property of state space partitions which we call f-homogeneity. Intuitively, an f-homogeneous partition groups together states that behave approximately the same under all or some subset of policies. Borrow ing from recent work on model minimization in computer-aided software verifi cation, we present an algorithm that takes a factored representation of an MDP and an 0 � f � I and computes a factored f-homogeneous par tition of the state space. This partition defines a family of related MOPs-those MOP's with state space equal to the blocks of the partition, and transition probabilities "appro:X:imately" like those of any (original MDP) state in the source block. To formally study such families of MDPs, we introduce the new notion of a "bounded parameter MDP" (BMDP), which is a fam ily of (traditional) MOPs defined by speci fying upper and lower bounds on the transi tion probabilities and rewards. We describe algorithms that operate on BMDPs to find policies that are approximately optimal with respect to the original MDP. In combination, our method for reducing a large implicit MDP to a possibly much smaller BMDP using an f-homogeneous par tition, and our methods for selecting actions in BMDP's constitute a new approach for an alyzing large implicit MOP's. Among its ad vantages, this new approach provides insight into existing algorithms to solving implicit MDPs, provides useful connections to work in automata theory and model minimization, and suggests methods, which involve vary ing f, to trade time and space (specifically in terms of the size of the corresponding state space) for solution quality. Markov decision processes (MDP) provide a formal ba sis for representing planning problems involving uncer tainty [Boutilier et al., 1995a] . There exist algorithms for solving MDPs that are polynomial in the size of the state space [Puterman, 1994] . In this paper, we are interested in MOPs in which the states are spec ified implicitly using a set of state variables. These MDPs have explicit state spaces which are exponential in the number of state variables, and are typically not amenable to direct solution using traditional methods due to the size of the explicit state space. It is possible to represent some MOPs using space polylog in the size of the state space by factoring the state-transition distribution and the reward function into sets of smaller functions. Unfortunately, this ef ficiency in representation need not translate into an efficient means of computing solutions. In some cases, however, dependency information implicit in the fac tored representation can be used to speed computa tion of an optimal policy [Boutilier and Dearden, 1994 , Boutilier et al., 1995b , Lin and Dean, 1995 . The resulting computational savings can be explained in terms of finding a homogeneous partition of the state space-a partition such that states in the same block transition with the same probability to each of the other blocks. Such a partition induces a smaller, ex plicit MDP whose states are the blocks of the partition; the smaller MDP, or reduced model is equivalent to the original MOP in a well defined sense. It is possible to take an MDP in factored form and find its small est reduced model using a number of "partition split ting" operations polynomial in the size of the resulting model; however, these splitting operations are in gen eral propositional logic operations which are NP-hard and are thus only heuristically effective. The states of the reduced process correspond to groups of states (in the original process) that behave the same under all policies. The original and reduced processes are equiv alent in the sense that they yield the same solutions, i.e., the same optimal policies and state values. The basic idea of computing equivalent reduced pro-
REF introduced the notion of ε-homogeneous partitions and analyzed its properties, but without giving explicit loss bounds.
Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes
ArXiv
ArXiv
Computer Science