Efficient Reinforcement Learning in Factored MDPs
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Machine Learning. Pages 740-746.
© 1999 International Joint Conferences on Artificial Intelligence
Abstract
We present a provably efficient and near-optimal algorithm for reinforcement learning in Markov decision processes (MDPs) whose transition model can be factored as a dynamic Bayesian network (DBN). Our algorithm generalizes the recent E 3 algorithm of Kearns and Singh, and assumes that we are given both an algorithm for approximate planning, and the graphical structure (but not the parameters) of the DBN. Unlike the original E 3 algorithm, our new algorithm exploits the DBN structure to achieve a running time that scales polynornially in the number of parameters of the DBN, which may be exponentially smaller than the number of global states.
- [Boutilier et al., 1999] C. Boutilier, T. Dean, and S. Hanks. De- ~ision theoretic planning: Structural assumptions and computa- tiOnal leverage. Journal of Artificial Intelligence Research, 1999. To appear.
- [Boyen and Koller, 1998] X. Boyen and D. Koller. Tractable in- ference for complex stochastic processes. In Proc. UA/, pages 33-42, 1998.
- [Dobrushin, 1956] R.L. Dobrushin. Central limit theorem for non- stationary Markov chains. Theory of Probability and its Applica- tions, pages 65-80, 1956.
- [Forbes eta/., 1995] J. Forbes, T. Huang, K. Kanazawa, and S.J. Russell. The BATmobile: Towards a Bayesian automated taxi. In Proc. IJCAI, 1995. IJCAI
- [Heckerman, 1995] D. Heckerman. A tutorial on learning with Bayesian networks. Technical Report MSR-TR-95-06, Microsoft Research, 1995.
- [Howard and Matheson, 1984] R. A. Howard and J. E. Matheson. Influence diagrams. In R. A. Howard and J. E. Matheson, editors, R. eadings on the Principles and Applications of Decision Analy- SIS, pages 721-762. Strategic Decisions Group, Menlo Park, Cal- ifornia, 1984.
- [Jensenetal., 1989] F.V. Jensen, U. Kjrerulff, K.G. Olesen, and J. Pedersen. An expert system for control of waste water treatment-a pilot project. Technical report, Judex Datasystemer AJS, Aalborg, 1989. In Danish.
- [Je~m and Sinclair, 1993] M. Jerrum and A. Sinclair. Polynomial- time approximation algorithms for the Ising model. SIAM Jour- nal on Computing, 22:1087~1116, 1993.
- [Kearns and Singh, 1998] M. Kearns and S.P. Singh. Near-optimal performance for reinforcement learning in polynomial time. In Proc. ICML, pages 260-268, 1998. [
- Kearns ~tal., 199?
- M. Kearns, Y. Mansour, and A. Ng. A sparse samphng algonthrn for near-optimal planning in large markov decision processes. In these proceedings, 1999.
- [Koller and Parr, 1999] D. Koller and R. Parr. Computing factored value functions for policies in structured MDPs. In these pro- ceedings, 1999. IJCAI
- [Lindvall, 1992] T. Lindvall. Lectures on the Coupling Method. Wi- ley, 1992.
- [Meuleau et al., 1998] N. Meuleau, M. Hauskrecht, K-E. Kim, L. Peshkin, L.P. Kaelbling, T. Dean, and C. Boutilier. Solving very large weakly coupled Markov decision processes. In Proc. AAAI, pages 165-172, 1998.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Kearns and Singh (1998) recently presented a new algo rithm for reinforcement learning in Markov decision pro cesses (MDPs). Their E 3 algorithm (for Explicit Explore or Exploit) achieves near-optimal performance in a running time and a number of actions which are polynomial in the num ber of states and a parameter T, which is the horizon time in the case of discounted return, and the mixing time of the optimal policy in the case of infinite-horizon average return. The E 3 algorithm makes no assumptions on the structure of the unknown MDP, and the resulting polynomial dependence on the number of states makes E 3 impractical in the case of very large MDPs. In particular, it cannot be easily applied to MDPs in which the transition probabilities are represented in the factored form of a dynamic Bayesian network (DBN). MDPs with very large state spaces, and such DBN-MDPs in particular, are becoming increasingly important as reinforce ment learning methods are applied to problems of growing difficulty [Boutilier et at., 1999].
In this paper, we extend the E 3 algorithm to the case of DBN-MDPs. The original E 3 algorithm relies on the abil ity to find optimal strategies in a given MDP - that is, to perform planning. This ability is readily provided by al gorithms such as value iteration in the case of small state spaces. While the general planning problem is intractable in large MDPs, significant progress has been made recently on approximate solution algorithms for both DBN-MDPs in
Daphne Koller
Stanford University koller@cs.stanford.edu
particular [Boutilier et al., 1999], and for large state spaces in general [Kearns et al., 1999; Koller and Parr, 1999]. Our new DBN-E 3 algorithm therefore assumes the existence of a procedure for finding approximately optimal policies in any given DBN-MDP. Our algorithm also assumes that the quali tative structure of the transition model is known, i.e., the un derlying graphical structure of the DBN. This assumption is often reasonable, as the qualitative properties of a domain are often understood.
Using the planning procedure as a subroutine, DBN-E 3 ex plores the state space, learning the parameters it considers relevant. It achieves near-optimal performance in a running time and a number of actions that are polynomial in T and the number of parameters in the DBN-MDP, which in general is exponentially smaller than the number of global states. We further examine conditions under which the mixing timeT of a policy in a DBN-MDP is polynomial in the number of pa rameters of the DBN-MDP. The "anytime" nature ofDBN-E 3 allows it to compete with such policies in total running time that is bounded by a polynomial in the number of parameters.
2 Preliminaries
We begin by introducing some of the basic concepts of MDPs and factored MDPs. A Markov Decision Process (MDP) is defined as a tuple (S, A, R, P) where: Sis a set of states; A is a set of actions; R is a reward function R : S ~ [0 , RmaxL such that R( s) represents the reward obtained by the agent in state s 1 ; P is a transition model P : S x A ~ ~s, such that P(s' Is, a) represents the probability oflanding in states' if the agent takes action a in states.
Most simply, MDPs are described explicitly, by writing down a set of transition matrices and reward vectors - one for each action a. However, this approach is impractical for describing complex processes. Here, the set of states is typically described via a set of random variables X = {X 1 , ... , Xn}, where each X; takes on values in some finite domain Val(X;). In general, for a set of variables Y C X, an instantiation y assigns a value x E Val( X) for every X E Y; we use Val(Y) to denote the set of possible instantiations to Y . A state in this MDP is an assignment x E Val(X); the total number of states is therefore exponentially large in the number of variables. Thus, it is impractical to represent the transition model explicitly using transition matrices.
1 A reward function is sometimes associated with (state,action) pairs rather than with states. Our assumption that the reward depends only on the state is made purely to simplify the presentation; it has no effect on our results.
The framework of dynamic Bayesian networks (DENs) al lows us to describe a certain important class of such MDPs in a compact way. Processes whose state is described via a set of variables typically exhibit a weak form of decoupling- not all of the variables at time t directly influence the transition of a variable X ; from timet to time t + 1. For example, in a simple robotics domain, the location of the robot at timet+ 1 may depend on its position, velocity, and orientation at time t , but not on what it is carrying, or on the amount of paper in the printer. DBNs are designed to represent such processes compactly.
Let a E A be an action. We first want to specify the transition model P(x' I x , a) . Let X; denote the variable X; at the current time and Xf denote the variable at the next time step. The transition model for action a will con sist of two parts - an underlying transition graph associ ated with a, and parameters associated with that graph. The transition graph is a 2-layer directed acyclic graph whose nodes are {X1 , ... ,Xn,Xi , .. . ,X~} . All edges in this graph are directed from nodes in {X 1 , ... , X n} to nodes in {Xi , .. . , X~}; note that we are assuming that there are no edges between variables within a time slice. We denote the parents of XI in the graph by Paa (XI). Intuitively, the tran sition graph for a specifies the qualitative nature of prob abilistic dependencies in a single time step - namely, the new setting of X; depends only on the current setting of the variables in Paa(XI). To make this dependence quantita tive, each node XI is associated with a conditional probabil ity table (CPT) Pa ( x: I Paa ( xm. The transition probability P(x' I x , a) is then defined to be f1; Pa(x; I u;), where u; is the setting in x of the variables in Paa(XI).
We also need to provide a compact representation of the reward function. As in the transition model, explicitly spec ifying a reward for each of the exponentially many states is impractical. Again, we use the idea of factoring the repre sentation of the reward function into a set of localized re ward functions, each of which only depends on a small set of variables. In our robot example, our reward might be com posed of several subrewards: for example, one associated with location (for getting too close to a walJ), one associated with the printer status (for Jetting paper run out), and so on. More precisely, Jet R be a set of functions R1 , .. . , Rk; each function R; is associated with a cluster of variables C; C {X1 , ... , Xn}. such that R; is a function from Val(C;) to JR. Abusing notation, we will use R;(x) to denote the value that R; takes for the part of the state vector corresponding to C;. The reward function associated with the DBN-MDP at a state xis then defi~ed to be R(x) = L~=l R;(x) E (0, Rmax]·
The folJowing definitions for finite-length paths in MDPs will be of repeated technical use in the analysis. Let M be a Markov decision process, and let 1r be a policy in M. A T -path in M is a sequence p ofT+ 1 states (that is, T transi tions) of M: p = xi, ... , xr , XT+I· The probability that pis traversed in M upon starting in state xi and executing policy 7r is denoted PM- (p] = nr=l P(xk+l I Xk' 7r(Xk) ).
There are three standard notions of the expected return en joyed by a policy in an MDP: the asymptotic discounted re turn, the asymptotic average return, and the finite-time aver age return. Like the original E 3 algorithm, our new general ization will apply to all three cases, and to convey the main ideas it suffices for the most part to concentrate on the finite time average return. This is because our finite-time average return result can be applied to the asymptotic returns through either the horizon time 1/ ( 1 - 1) for the discounted case, or the mixing time of the optimal policy in the average case. (We examine the properties of mixing times in a DBN-MDP in Section 5.)
Let M be a Markov decision process, Jet 1r be a policy in M, and let p beaT-path in M . The average return along p inM is
The T -step (expected) average return from state x is UM-(x, T) = Lp PM-(p]UM(P) where the sum is over all T-paths p in M that start at x . Furthermore, we define the optimalT-step average return from x in M by UM(x , T) = max7r{UM-(x, T)} .
An important problem in MDPs is planning: finding the policy 1r* that achieves optimal return in a given MDP. In our case, we are interested in achieving the optimal T-step av erage return. The complexity of all exact MDP planning al gorithms depends polynomially on the number of states; this property renders alJ of these algorithms impractical for DBN MDPs, where the number of states grows exponentially in the size of the representation. However, there has been re cent progress on algorithms for approximately solving MDPs with large state spaces [Kearns et al., 1999], particularly on ones represented in a factored way as an MDP [Boutilier et al., 1999; Koller and Parr, 1999]. The focus of our work is on the reinforcement learning task, so we simply assume that we have access to a "black box" that performs approximate planning for a DBN-MDP.
Definition 2.1 :A J.L-approximation T -step planning algo rithm for a DBN-MDP is one that, given a DBN-MDP M, produces a (compactly represented) policy 1r such that UM-(x, T) 2: (1- J.L)UM(x, T).l
We wilJ charge our learning algorithm a single step of com putation for each calJ to the assumed approximate planning algorithm. One way of thinking about our result is as a re duction of the problem of efficient learning in DBN-MDPs to the problem of efficient planning in DBN-MDPs.
Our goal is to perform model-based reinforcement learn ing. Thus, we wish to Jearn an approximate model from ex perience, and then exploit it (or explore it) by planning given the approximate model. In this paper, we focus on the prob lem of learning the model parameters (the CPTs), assuming that the model structure (the transition graphs) is given to us. It is therefore useful to consider the set of parameters that we wish to estimate. As we assumed that the rewards are deterministic, we can focus on the probabilistic parameters. (Our results easily extend to the case of stochastic rewards.) We define a transition component of the DBN-MDP to be a distribution Pa(XI I u) for some action a and some partic ular instantiation u to the parents Paa (XI) in the transition model. Note that the number of transition components is at most La; IVal(Paa(XI))I, but may be much lower when a variable ' ~ behavior is identical for several actions.
3 Overview of the Original E 3
Since our algorithm for learning in DBN-MDPs will be a di rect generalization of the E 3 algorithm of Kearns and Singh -hereafter abbreviated KS- we begin with an overview of that algorithm and its analysis. It is important to bear in mind that the original algorithm is designed only for the case where the total number of states N is small, and the algorithm runs in time polynomial in N.
E 3 is what is commonly referred to as an indirect or model based algorithm: rather than maintaining only a current pol icy or value function, the algorithm maintains a model for the transition probabilities and the rewards for some subset of the states of the unknown MDP M. Although the algo rithm maintains a partial model of M , it may choose to never build a complete model of M, if doing so is not necessary to achieve high return.
The algorithm starts off by doing balanced wandering: the algorithm, upon arriving in a state, takes the action it has tried the fewest times from that state (breaking ties randomly). At each state it visits, the algorithm maintains the obvious statis tics: the reward received at that state, and for each action, the empirical distribution of next states reached (that is, the estimated transition probabilities).
A crucial notion is that of a known state - a state that the algorithm has visited "so many" times that the transition probabilities for that state are "very close" to their true val ues in M. This definition is carefully balanced so that "so many" times is still polynomially bounded, yet "very close" suffices to meet the simulation requirements below. An im portant observation is that we cannot do balanced wandering indefinitely before at least one state becomes known: by the Pigeonhole Principle, we will soon start to accumulate accu rate statistics at some state.
The most important construction of the analysis is the known-state MDP. If S is the set of currently known states, the known-state MDP is simply an MDP Ms that is nl;lturally induced on S by the full MDP M. Briefly, all transitions in M between states in S are preserved in Ms, while all other transitions in M are "redirected" in Ms to lead to a single new, absorbing state that intuitively represents all of the un known and unvisited states. AlthoughE 3 does not have direct access to Ms, by virtue of the definition of the known states, it does have a good approximation Ms.
The KS analysis hinges on two central technical lemmas. The first is called the Simulation Lemma, and it establishes that Ms has good simulation accuracy: that is, the expected T-step return of any policy in Ms is close to its expected T step return in Ms. Thus, at any time, Ms is a useful partial model of M, for that part of M that the algorithm "knows" very well.
The second central technical lemma is the "Explore or Ex ploit" Lemma. It states that either the optimal (T -step) policy in M achieves its high return by staying (with high proba bility) in the set S of currently known states, or the optimal policy has significant probability of leavingS within T steps. Most importantly, the algorithm can detect which of these two is the case; in the first case, it can simulate the behavior of the optimal policy by finding a high-return exploitation policy in the partial model Ms, and in the second case, it can replicate the behavior of the optimal policy by finding an exploration policy that quickly reaches the additional absorbing state of the partial model Ms . Thus, by performing two off-line plan ning computations on Ms, the algorithm is guaranteed to find either a way to get near-optimal return for the next T steps, or a way to improve the statistics at an unknown or unvisited state within the next T steps. KS show that this algorithm ensures near-optimal return in time polynomial in N .
4 The DBN-E 3 Algorithm
Our goal is to derive a generalization of E 3 for DBN-MDPs, and to prove for it a result analogous to that of KS - but with a polynomial dependence not on the number of states N, but on the number of CPT parameters f in the DBN model. Our analysis closely mirrors the original, but requires a sig nificant generalization of the Simulation Lemma that exploits the structure of a DBN-MDP, a modified construction of Ms that can be represented as a DBN-MDP, and a number of al terations of the details.
Like the original E 3 algorithm, DBN-E 3 will build a model ofthe unknown DBN-MDP on the basis of its experience, but now the model will be represented in a compact, factorized form. More precisely, suppose that our algorithm is in state x, executes action a, and arrives in state x'. This experience will be used to update all the appropriate CPT entries of our model- namely, all the estimates J\(x; I u;) are updated in the obvious way, where as usual u; is the setting of Paa (Xi) in x. We will also maintain counts Ca(x; , u;) of the number of times Pa(x; I u;) has been updated.
Recall that a crucial element of the original E 3 analysis was the notion of a known state. In the original analysis, it was ob served that if N is the total number of states, then after O(N ) experiences some state must become known by the Pigeon hole Principle. We cannot hope to use the same logic here, as we are now in a DBN-MDP with an exponentially large number of states. Rather, we must "pigeonhole" not on the number of states, but on the number of parameters required to specify the DBN-MDP. Towards this goal, we will say that the CPT entry Pa ( x; I u;) is known if it has been visited "enough" times to" ensure that, with high probability
We now would like to establish that if, for an appropriate choice of a, all CPT entries are known, then our approximate DBN-MDP can be used to accurately estimate the expected return of any policy in the true DBN-MDP. This is the de sired generalization of the original Simulation Lemma. As in the original analysis, we will eventually apply it to a gener alization of the induced MDP Ms, in which we deliberately restrict attention to only the known CPT entries.
4.1 The DBN-MDP Simulation Lemma
Let M and M be two DBN-MDPs over the same state space with the same transition graphs for every action C::· and with the same reward functions. Then we say that M is an a approximation of M if for every action a and node Xf in the transition graphs, for every setting u of Paa (XI), and for every possible value xi of Xi,
where Pa(· I ·) and Fa(· I -)"are the CPTs of M and M, respectively.
Lemma 4.1: Let M be any DBN-MDP over n state variables with l CPT entries in the transition model, and let M be an a-approximation of M, where a = O((E/(T 2 lRmax)) 2 ) . Then for any policy 1r, and for any state x, IUX1(x, T) - Ui:r(x, T)l:::; E.
Proof: (Sketch) Let us fix a policy 1r and state x. Recall that for any next state x' and any action a, the transition probabil ity factorizes via the CPTs as P(x' I x , a) = fl Pa(xi I u;). where u; is the setting of Paa (XI) in x. Let us say that P(x' I x , a) contains a /3-small factor if any of its CPT fac tors Pa(xi I u;) is smaller than /3. Note that a transition probability may actually be quite small itself (exponentially small inn) without necessarily containing a /3-small factor. ,
Our first goal is to show that trajectories in M and M that cross transitions containing a /3-small CPT factor can be "thrown away" without much error. Consider a random tra jectory ofT steps in M from state x following policy 1r. It can be shown that the probability that such a trajectory will cross at least one transition P ( x' I x, a) that contains a /3small factor is at most Tl/3. Essentially, the probability that at any step, any particular /3-small transition (CPT factor) will be taken by any particular variable X; is at most /3. A sim ple union argument over the CPT entries and the T time steps gives the desired bound. Therefore, the total contribution to the difference IUX1(x, T)- Ui:r(x, T)l by these trajectories can be shown to be at most T 2 Rmaxl( a + /3). We will thus ignore such trajectories for now.
The key advantage of eliminating /3-small factors is that we can convert additive approximation guarantees into mul tiplicative ones. Let p be any path of length T. If all the relevant CPT factors are greater than /3, and we let .::l = aj /3, it can be shown that
In other words, ignoring /3-small CPT factors, the distribu tions on paths induced by 1r in M and M are quite similar. From this it follows that, for the upper bound, 2
For the choices /3 = fo, a = O((E/(T 2 lRmax)) 2 ) the lemma is obtained. I
2 The lower bound argument is entirely symmetric.
Returning to the main development, we can now give a precise definition of a known CPT entry. It is a simple ap plication of Chernoff bounds to show that provided the count Ca(xi, u;) exceeds 0(1/a 2 log(1/o)), Fa(xi I u;) has addi tive error at most a with probability at least 1 - o. We thus say that this CPT entry is known if its count exceeds the given bound for the choice a= 0( ( Ej(T 2 nvRmax)) 2 ) specified by the DBN-MDP Simulation Lemma. The DBN-MDP Simula tion Lemma shows that if all CPT entries are known, then our approximate model M can be used to find a near-optimal policy in the true DBN-MDP M.
Note that we can identify which CPT entries are known via the counts C a (xi, u;). Thus, if we are at a state x for which at least one of the associated CPT entries Pa (xi I u;) is unknown, by taking action a we then obtain an experience that will increase the corresponding count Ca(xi, u;). Thus, in analogy with the original E 3 , as long as we are encoun tering unknown CPT entries, we can continue taking actions that increase the quality of our model - but now rather than increasing counts on a per-state basis, the DBN-MDP Simu lation Lemma shows why it suffices to increase the counts on a per-CPT entry basis, which is crucial for obtaining the run ning time we desire. We can thus show that if we encounter unknown CPT entries for a number of steps that is polyno mial in the total number l of CPT entries and 1/E, there can no longer be any unknown CPT entries, and we know the true DBN-MDP well enough to solve for a near-optimal policy.
However, similar to the original algorithm, the real diffi culty arises when we are in a state with no unknown CPT entries, yet there do remain unknown CPT entries elsewhere. Then we have no guarantee that we can improve our model at the next step. In the original algorithm, this was solved by defining the known-state MDP Ms, and proving the afore mentioned "Explore or Exploit" Lemma. Duplicating this step for DBN-MDPs will require another new idea.
4.2 The DBN-MDP "Explore or Exploit" Lemma
In our context, when we construct a known-state MDP, we must satisfy the additional requirement that the known-state MDP preserve the DBN structure of the original problem, so that if we have a planning algorithm for DBN-MDPs that ex ploits the structure, we can then apply it to the known-state MDp3. Therefore, we cannot just introduce a new "sink state" to represent that part of M that is unknown to us; we must also show how this "sink state" can be represented as a set ting of the state variables of a DBN-MDP.
We present a new construction, which extends the idea of "known states" to the idea of "known transitions". We say that a transition component Pa(Xf I u) is known if all of its CPT entries are known. The basic idea is that, while it is impossible to check locally whether a state is known, it is easy to check locally whether a transition component is known.
Let T be the set of known transition components. We de fine the known-transition DBN-MDP Mr as follows. The model behaves identically toM as long as only known transi tions are taken. As soon as an unknown transition is taken for some variable x:, the variable x: takes on a new wandering value w, which we introduce into the model. The transition model is defined so that, once a variable takes on the value w, its value never changes. The reward function is defined so that, once at least one variable takes on the wandering value, the total reward is nonpositive. These two properties give us the same overall behavior that KS got by making a sink state for the set of unknown states.
3 Certain approaches to approximate planning in large MDPs do not require any structural assumptions [Keams et al., 1999], but we anticipate that the most effective DBN-MDP planning algorithms eventually will.
Definition 4.2:Let M be a DBN-MDP and letT be any sub set of the transition components in the model. The induced DBN-MDP on T, denoted MT, is defined as follows :
- MT has the same set of state variables as M; however, in M7 , each variable X; has, in addition to its original set of values Va!M (X;), a new value w.
- M7 has the same transition graphs as M. For each a, i, and u E Va!M (Paa(Xi)), we have that Pttr(x: I u) = Ptt (X: I u) if the corresponding transition com ponent is in T; in all other cases, Pttr ( w I u) = 1, and Pttr(x; I u) = 0 for all x; E Va!M (X;).
- MT has the same set n as M. For each i = 1, ... , k and c E Va!M (C;), we have that R~T (c) = Rf! (c). For other vectors c, we have that R~ T (c) = - Rmax. I
With this definition, we can prove the analogue to the "Ex plore or Exploit" Lemma (details omitted).
Lemma 4.3:Let M be any DBN-MDP, letT be any subset of the transition components of M, and let MT be the induced MDP on M. For any x E S, any T, and any 1 > T > 0, either there exists a policy rr in MT such that UMr (x, T) ~ UM(x, T) - T, or there exists a policy rr in MT such that the probability that a walk ofT steps following rr will take at least one transition not in T exceeds T / ( ( k + 1 )T Rmax ).
This lemma essentially asserts that either there exists a pol icy that already achieves near-optimal (global) return by stay ing only in the local model MT, or there exists a policy that quickly exits the local model.
4.3 Putting It All Together
We now have all the pieces to finish the description and analy sis of the DBN-E 3 algorithm. The algorithm initially executes balanced wandering for some period of time. After some number of steps, by the Pigeonhole Principle one or more transition components become known. When the algorithm reaches a known state x - one where all the transition com ponents are known- it can no longer perform balanced wan dering. At that point, the algorithm performs approximate off-line policy computations for two different DBN-MDPs. The first corresponds to attempted exploitation, and the sec ond to attempted exploration.
Let T be the set of known transitions at this step. In the attempted exploitation computation, the DBN-E 3 algorithm would like to find the optimal policy on the induced DBN MDP MT. Clearly, this DBN-MDP is not known to the al gorithm. Thus, we use its approximation MT, where the true transition probabilities are replaced with their current approx imation in the model. The definition of MT uses only the CPT entries of known transition components. The Simula tion Lemma now tells us that, for an appropriate choice of a -a choice that will result in a definition of known transition that requires the corresponding count to be only polynomial in 1/f., n, v, and T- the return of any policy rr in MT is within f. of its return in MT. We will specify a choice for f. later (which in turn sets the choice of a and the definition of known state).
Let us now consider the two cases in the "Explore or Ex ploit" Lemma. In the exploitation case, there exists a policy rr in M7 such that UMr (x, T) ~ UM (x, T) - T . (Again, we will discuss the choice ofT below.) From the Simulation Lemma, wehavethatU~r (x,T) ~ UM(x,T)-(r+f.). Our approximate planning algorithm returns a policy rr' whose value in M7 is guaranteed to be a multiplicative factor of at most 1-J.L away from the optimal policy in MT. Thus, we are guaranteed that U1r (x, T) 2': ( 1- J.L)(UM (x, T)- ( T +f.)) . Therefore, in the exploitation case, our approximate planner is guaranteed to return a policy whose value is close to the optimal value.
In the exploration case, there exists a policy rr in MT (and therefore in MT) that is guaranteed to take an unknown tran sition within T steps with some minimum probability. Our goal now is to use our approximate planner to find such a pol icy. In order to do that, we need use a slightly different con struction M!,- (M!,- ). The transition structure of M!,- is iden tical to that of M7 . However, the rewards are now different. Here, for each i = 1, ... , k and c E Va!M (C;), we have that M' M R; r (c) = 0; for other vectors c, we have that R; r (c) = 1. Now let rr' be the policy returned by our approximate planner on the DBN-MDP M!,-. It can be shown that the probability that aT-step walk following rr' will take at least one unknown transition is at least (1- J.L)(rj((k + 1)TRmax)- f.)jkT.
To summarize: our approximate planner either finds an exploitation policy rr in MT that enjoys actual return UM(x,T) 2': (1- J.L)(UM(x,T)- (r +f.)) from our cur rent state x , or it finds an exploitation policy in M!,- that has probability at least p = (1- J.L)( T /( (k + 1)T Rmax)- f.)/ kT of improving our statistics at an unknown transition in the next T steps. Appropriate choices for f. and r yield our main theorem, which we are now finally ready to describe.
Recall that for expository purposes we have concentrated on the case ofT-step average return. However, as for the orig inal E 3 , our main r~sult can be stated in terms of the asymp totic discounted and average return cases. We omit the details of this translation, but it is a simple matter of arguing that it suffices to set T to be either ( 1/ ( 1-1)) log( 1/ f.) (discounted) or the mixing time of the optimal policy (average).
Theorem 4.4: (Main Theorem) Let M be a DBN-MDP with f. total entries in the CPTs.
- (Undiscounted case) LetT be the mixing time of the pol icy achieving the optimal average asymptotic return u· in M. There exists an algorithm DBN-£ 3 that, given ac cess to a J.L-approximation planning algorithm for DBN-
MDPs, and given inputs t , J, f , T and U*, takes anum ber of actions and computation time bounded by a poly nomial in 1/(1- fl) , 1/ t, 1/6, e, T, and Rmax. and with probability at least 1 - J, achieves total actual return exceeding u· - {.
- (Discounted case) Let V* denote the value function for the policy with the optimal expected discounted return in M. There exists an algorithm DBN-P that, given access to a {l-approximation planning algorithm for DBN-MDPs, and given inputs £, J, f and V*, takes a number of actions and computation time bounded by a polynomial in 1/ ( 1 - fl) ' 1/ {' 1/ J, e, the horizon time T = 1/(1 -1), and Rmax. and with probability at least 1 - J, will halt in a state x, and output a policy ir, such that v.tf (x) ~ v· (x) - {.
Some remarks:
- The loss in policy quality induced by the approximate planning subroutine translates into degradation in the running time of our algorithm.
- As with the original E 3 , we can eliminate knowledge of the optimal returns in both cases via search techniques.
- Although we have stated our asymptotic undiscounted average return result in terms of the mixing time of the optimal policy, we can instead give an "anytime" algo rithm that "competes" against policies with longer and longer mixing times the longer it is run. (We omit de tails, but the analysis is analogous to the original E 3 analysis.) This extension is especially important in light of the results of the following section, where we exam ine properties of mixing times in DBN-MDPs.
5 Mixing Time Bounds for DBN-MDPs
As in the original E 3 paper, our average case result depends on the amount of timeT that it takes the target policy to mix. This dependence is unavoidable. If some of the probabilities are very small, so that the optimal policy cannot easily reach the high-reward parts of the space, it is unrealistic to expect the reinforcement learning algorithm to do any better.
In the context of a DBN-MDP, however, this dependence is more troubling. The size of the state space is exponentially large, and virtually all of the probabilities for transitioning from one state to the next will be exponentially small (be cause a transition probability is the product of n numbers that are :::; 1). Indeed, one can construct very reasonable DBN MDPs that have an exponentially long mixing time. For ex ample, a DBN representing the Markov chain of an Ising model [Jerrum and Sinclair, 1993] has small parent sets (at most four parents per node), and CPT entries that are reason ably large. Nevertheless, the mixing time of such a DBN can be exponentially large in n.
Given that even "reasonable" DBNs such as this can have exponential mixing times, one might think that this is the typ ical situation- that is, that most DBN-MDPs have an ex ponentially long mixing time, reintroducing the exponential dependence on n that we have been trying so hard to avoid. We now show that this is not always the case. We provide a tool for analyzing the mixing time of a policy in a DBN-MDP, which can give us much better bounds on the mixing time. In particular, we demonstrate a class of DBN-MDPs and associ ated policies for which we can guarantee rapid mixing.
Note that any fixed policy in a DBN-MDP defines a Markov chain whose transition model is represented as a DBN. We therefore begin by considering the mixing time of a pure DBN, with no actions. We then extend that analysis to the mixing rate for a fixed policy in a DBN-MDP.
Definition S.l:Let Q be a transition model for a Markov chain, and let {X(t)}~ 1 represent the state of the chain. Let 5 = {x1 , . . . ,x$}. Let fli be the stationary probability of xi in this Markov chain. We say that the Markov chain Q is £-mixed at time m if max; ,j IP(X(t) = Xj I X(l) = x;)- flil :S £.1
Our bounds on mixing times make use of the coupling method [Lindvall, 1992]. The idea of the coupling method is as follows: we run two copies of the Markov chain in par allel, from different starting points. Our goal is to make the states of the two processes coalesce. Intuitively, the first time the states of the two copies are the same, the initial states have been "forgotten", which corresponds to the processes having mixed.
More precisely, consider a transition matrix Q over some state space 5. Let Q* be a transition matrix over the state space 5 x 5, such that if { (Y(tl , z(tl)}~ 1 is the Markov chain for Q*, then the separated Markov chains {Y(t) }~1 and {z(t)}~ 1 both evolve according to Q. Let r be the ran dom variable that represents the coupling time- the smallest m for which y ( m) = z( m). The following lemma establishes the correspondence between mixing and coupling times.
Lemma 5.2: For any £, let m be such that for any i, j = 1, .. . ,s, P(r > m I y(l) = x;,z(l) =xi):::;£. Then Q is £-mixed at time m.
Thus, to show that a Markov chain is £-mixed by some time m, we need only construct a coupled chain and show that the probability that this chain has not coupled by time m decreases very rapidly in m.
The coupling method allows us to construct the joint chain over (Y(t), z(tl) in any way that we want, as long as each of the two chains in isolation has the same dynamics as the original Markov chain Q. In particular, we can correlate the transi~ions of the two processes, so as to make their states coincide faster than they would if each was picked indepen dently of the other. That is, we choose y(t+l) and z(t+l) to be equal to each other whenever possible, subject to the constraints on the transition probabilities. More precisely, let y(t) = x; and z(t) = Xj. For any value x E 5, we can make the event y(t+l) = X;, z(t+l) = Xj have a proba bility that is the smaller of P(X' = Xk I X = x;) and P(X' = Xk I X = Xj ). Compare this to the probability of this event if the two processes were independent, which is the product of these two numbers rather than their mini mum. Overall, by correlating the two processes as much as possible, and considering the worst case over the current state of the process, we can guarantee that, at every step, the two processes couple with probability at least
This quantity represents the amount of probability mass that any two transition distributions are guaranteed to have in common. It is called the Dobrushin coefficient, and is the contraction rate for L1-norm [Dobrushin, 1956] in Markov chains.
Now, consider a DBN over the state variables X = {X 1 , ... , X n}. As above, we create two copies of the pro cess, letting Y1, ... , Yn denote the variables in the first com ponent of the coupled Markov chain, and Z1, .. . , Zn denote those in the second component. Our goal is to construct a Markov chain over Y, Z such that both Y and Z separately have the same dynamics as X in the original DBN.
Our construction of the joint Markov chain is very simi lar to the one used above, except that will now choose the transition of each variable pair Y; and Z; so as to maximize the probability that they couple (assume the same value). As above, we can guarantee that Y; and Z; couple at any time t with probability at least
This coefficient was defined by [Boyen and Koller, 1998] in their analysis of the contraction rate of DBNs. Note that {3; depends only on the numbers in a single CPT of the DBN. Assuming that the transition probabilities in each CPT are not too extreme, the probability that any single variable couples will be reasonably high.
Unfortunately, this bound is not enough to show that all of the variable pairs couple within a short time. The problem is that it is not enough for two variables Y;(t) and Z;(t) to couple, as process dynamics may force us to decouple them at subsequent time slices. To understand this issue, consider a simple process with two variables X1,X2, and a transition graph with the edges X 1 -+ X~, X 2 -+ X~, X1 -+X~. Assume that at timet, the variable pair Y 2 (t), z~t) has COUpled With value X2, but y1(t), z}t) has not, SO that Y1(t) = x1 and zit) = x~. At the next time slice, we must select y2(t+ 1 )) z~t+ 1 ) from two different distributions - P(X~ I x1, x2) and P(X~ I x~, x2), respectively. Thus, our sampling process may be forced to give them different values, decoupling them again.
As this example clearly illustrates, it is not enough for a variable pair to couple momentarily. In order to eventually couple the two processes as a whole, we need to make each variable pair a stable pair- i.e., we need to guarantee that our sampling process can keep them coupled from then on. In our example, the pair Y1, Z1 is stable as soon as it first cou ples. And once Y1, Z1 is stable, then Y2, Z2 will also be stable as soon as it couples. However, ifY2, Z2 couples while Y1, Z1 is not yet stable, then the sampling process cannot guarantee stability.
In general, a variable pair can only be stable if their parents are also stable. So what happens if we add the edge X 2 -+ X~ to our transition model? In this case, neither Y1, Z1 nor Y2 , Z2 can stabilize in isolation. They can only stabilize if they couple simultaneously.
This discussion leads to the following definition.
Definition 5.3:Consider a DBN over the state variables X 1, ... , Xn. The dependency graph 1J for the DBN is a di rected cyclic graph whose nodes are X 1 , ... , X n and where there is a directed edge from X; to Xj if there is an edge in the transition graph of the DBN from X; to Xj. I
Hence, there is a directed path from X; to Xj in 1J iff X;(t) influences x;e'l for some t' > t. We assume that the transi tion graph of the DBN always has arcs X; -+ Xf, so that the every node in 1J has a self-loop.
Let r 1, ... , ft be the maximal strongly connected compo nents in 1J, sorted so that if i < j, there are no directed edges from r i to r;. Our analysis will be based on stabilizing the f;'s in succession. (We note that we provide only a rough bound; a more refined analysis is possible.) Let f3 = min; {3; and g = maXj lfj 1- Assume that r1) ... ) ri-1 have all stabi lized by timet. In order for f; to stabilize, all of the variables need to couple at exactly the same time. This event happens at time t with probability ~· f3g. As soon as r; stabilizes, we can move on to stabilizing f;+1. When all the f;'s have stabilized, we are done.
Theorem 5.4:For any f ~ 0, the Markov chain correspond ing to a DBN as described above is E-mixed at time m pro vided
Thus, the mixing time of a DBN grows exponentially with the size of the largest component in the dependency graph, which may be significantly smaller than the total number of vari ables in a DBN. Indeed, in two real-life DBNs- BAT [Fprbes et al., 1995] with ten state variables, and WATER [Jensen et al., 1989] with eight- the maximal cluster size is 3-4.
It remains only to extend this analysis to DBN-MDPs, where we have a policy rr. Our stochastic coupling scheme must now deal with the fact that the actions taken at time t in the two copies of the process may be different. The diffi culty is that different actions at timet correspond to different transition models. If a variable X; has a different transition model in different transition graphs Pa, it will use a different transition distribution if the action is not the same. Hence X; cannot stabilize until we are guaranteed that the same action is taken in both copies. That is, the action must also stabilize. The action is only guaranteed to have stabilized when all of the variables on which the choice of action can possibly de pend have stabilized. Otherwise, we might encounter a pair of states in which we are forced to use different actions in the two copies.
We can analyze this behavior by extending the dependency graph to include a new node corresponding to the choice of action. We then see what assumptions allow us to bound the set of incoming and outgoing edges. We can then use the same a.nalysis described above to bound the mixing time. The outgomg edges correspond to the effect of an action. In many processes, the action only directly affects the transition model of a small number of state variables in the process. In other words, for many variables X; , we have that Paa(X; ) and Pa(X; I Paa(X;)) are the same for all a. In this case, the new action node will only have outgoing edges to the re ~aining variables (those for which the transition model might differ). We note that such localized influence models have a long history both for influence diagram [Howard and Mathe son, 1984] and for DBN-MDPs [Boutilier et al., 1999].
Now, consider outgoing edges. In general, the optimal pol~cy might well be such that the action depends on every ~anable. However, the mere representation of such a pol ICY may be very complex, rendering its use impractical in a DBN-MDP with many variables. Therefore, we often want to restrict attention to a simpler class of policies, such as a small ~nit.e state machine or a small decision tree. If our target pol ICY IS such that the choice of action only depends on a small number of variables, then there will only be a small number of incoming edges into the action node in the dependency graph.
Having integrated the action node into the dependency graph, our analysis above holds unchanged. The only differ ence from a random variable is that we do not have to include the action node when computing the size of the f ; that con tains it: as we do not have to stochastically make it couple; rather, It couples immediately once its parents have coupled.
Finally, we note that this analysis easily accommodates DBN-MDPs where the decision about the action is also decomposed into several independent decisions (e.g. , as in [Meuleau et al., 1998]). Different component decisions can influence different subsets of variables, and the choice of action in each one can depend on different subsets of vari ables. Each decision forms a separate node in the dependency graph, and can stabilize independently of the other decisions.
The analysis above gives us techniques for estimating the mixing rate of policies in DBN-MDPs. In particular, if we want to focus on getting a good steady-state return from DBN-E 3 in a reasonable amount of time, this analysis shows us how to restrict attention to policies that are guaranteed to mix rapidly given the structure Qf the given DBN-MDP.
6 Conclusions
Structured probabilistic models, and particularly Bayesian networks, have revolutionized the field of reasoning under uncertainty by allowing compact representations of complex domains. Their success is built on the fact that this structure c~n be exp~oited effectively by inference and learning algo nthms. This success leads one to hope that similar structure can be exploited in the context of planning and reinforce ment learning under uncertainty. This paper, together with the recent work on representing and reasoning with factored MDPs [Boutilier et al., 1999], demonstrate that substantial computational gains can indeed be obtained from these com pact, structured representations.
This paper leaves many interesting problems unaddressed. Of these, the most intriguing one is to allow the algorithm to learn the model structure as well as the parameters. The recent body of work on learning Bayesian networks from data [Heckerman, 1995] lays much of the foundation, but th~ integrati.on .of ~hese ideas with the problems of explo ratwn/explmtatiOn IS far from trivial.
Acknowledgements
We ~e gra~eful to the members of the DAGS group for use ~ul discussiOns, and particularly to Brian Milch for point mg out a problem in an earlier version of this paper. The work of Daphne Koller was supported by the ARO under the MURI program "Integrated Approach to Intelligent Sys tems," by ONR contract N66001-97-C-8554 under DARPA's HPKB program, and by the generosity of the Powell Founda tion and the Sloan Foundation.
@inproceedings{ijcai1999p106,
title = {Efficient Reinforcement Learning in Factored MDPs},
author = {Kearns, Michael J. and Koller, Daphne},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {740--746},
year = {1999},
note = {Machine Learning},
url = {https://ijcai.org/proceedings/1999/106},
}
TY - CPAPER TI - Efficient Reinforcement Learning in Factored MDPs AU - Kearns, Michael J. AU - Koller, Daphne T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 740 EP - 746 UR - https://ijcai.org/proceedings/1999/106 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: