A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes

1 Introduction

In the past decade, Markov decision processes (MDPs) and reinforcement learning have become a standard framework for planning and learning under uncertainty within the artificial intelligence literature. The desire to attack problems of increasing complexity with this formalism has recently led researchers to focus particu­ lar attention on the case of (exponentially or even in­ finitely) large state spaces. A number of interesting UC Berkeley ang~cs.berkeley.edu algorithmic and representational suggestions have been made for coping with such large MDPs. Function ap­ proximation [SB98] is a well-studied approach to learn­ ing value functions in large state spaces, and many au­ thors have recently begun to study the properties of large MDPs that enjoy compact representations, such as MDPs in which the state transition probabilities factor into a small number of components [MHK+98] .

In this paper, we are interested in the problem of com­ puting a near-optimal policy in a large or infinite MDP that is given - that is, we are interested in planning. It should be clear that as ail MDP becomes very large, the classical planning assumption that the MDP is given explicitly by tables of rewards and transition probabili­ ties becomes infeasible. One approach to this difficulty is to assume that the MDP has some special structure that permits compact representation (such as the fac­ tored transition probabilities mentioned above), and to design special-purpose planning algorithms that exploit this structure.

Here we take a rather different approach. We consider a setting in which our planning algorithm is given access to a genemtive model , or simulator, of the MDP. Infor­ mally, this is a "black box" to which we can give any state-action pair (s, a), and receive in return a randomly sampled next state and reward from the distributions associated with (s, a). Generative models are a natu­ ral way in which a large MDP might be specified , and are more general than most structured representations, in the sense that many structured representations (such as factored models [MHK+98]) usually provide an effi­ cient way of implementing a generative model. Note also that since a generative model provides less information than explicit tables of probabilities, but more informa­ tion than a single continuous trajectory of experience generated according to some exploration policy, results obtained via a generative model blur the distinction be­ tween what is typically called "planning" and "learning" in MDPs.

Our main result is a new algorithm that accesses the given generative model to perform near-optimal plan­ ning in an "on-line" fashion. From any given state s, the algorithm samples the generative model for many different state-action pairs , and uses these samples to compute a near-optimal action from s. The amount of time required to compute a near-optimal action from any particular state s has no dependence on the num­ ber of states in the MDP, even though the next-state distributions from s may be very diffuse (that is, have large support). The key to our analysis is in showing that appropriate sparse sampling suffices to construct enough information about the environment near s to compute a near-optimal action. The analysis relies on a combination of Bellman equation calculations, which are standard in reinforcement learning, and uniform con­ vergence arguments, which are standard in supervised learning; this combination of techniques was first applied in [KS99] . As mentioned, the running time required at each state does have an exponential dependence on the horizon time, which we show to be unavoidable without further assumptions. However, our results leave open the possibility of an algorithm that runs in time polynomial in the accuracy parameter, which remains an important open problem.

Note that one can view our planning algorithm as sim­ ply implementing a (stochastic) policy - a policy that happens to use a generative model as a subroutine. In this sense, if we view the generative model as providing a "compact" representation of the MDP, our algorithm provides a correspondingly "compact" representation of a near-optimal policy. We view our result as comple­ mentary to work that proposes and exploits particular compact representations of MDPs [MHK+98], with both lines of work beginning to demonstrate the potential fea­ sibility of planning and learning in very large environ­ ments.

The remainder of this paper is structured as follows : In Section 2, we give the formal definitions needed in this paper. Section 3 then gives our main result, an algorithm for planning in large or infinite MDPs, whose per-state running time does not depend on the size of the state space. Finally, Section 4 describes related results and open problems.

2 Preliminaries

We begin with the definition of a Markov decision pro­ cess on a set of N = lSI states, explicitly allowing the possibility of the number of states being (countably or uncountably) infinite.

Definition 1 A Markov decision process M on a set of states S and with actions { a1 , ... , ak} consists of:

• Trahsition Probabilities: For each state-action pair (s, a), a next-state distribution P,a(s') that specifies the probability of transition to each state s' upon execution of action a from state s.
• Reward Distributions: For each state-action pair (s , a), a distribution R,a on real-valued rewards for executing action a from states. We assume rewards are bounded in absolute value by Rmax.

For simplicity, we shall assume in this paper that all rewards are in fact deterministic - that is, the reward distributions have zero variance, and thus the reward received for executing a from s is always exactly R·a· However, all of our results have easy generalizations for the case of stochastic rewards, with an appropriate and necessary dependence on the variance of the reward dis­ tributions.

Throughout the paper, we will primarily be interested in MDPs with a very large (or even infinite) number of states, thus precluding approaches that compute directly on the full next-state distributions . Instead, we will as­ sume that our planning algorithms are given M in the form of the ability to sample the behavior of M. Thus, the model given is simulative rather than explicit. We call this ability to sample the behavior of M a generative model.

Definition 2 A generative model for a Markov deci­ sion process M is a randomized algorithm that, on input of a state-action pair ( s, a), outputs R,a and a state s', where s' is randomly drawn according to the transition probabilities P,a ( ·).

We think of a generative model as falling somewhere in between being given explicit next-state distributions, and being given only "irreversible" experience in the MDP (in which the agent follows a single, continuous trajectory, with no ability to reset to any desired state). On the one hand, a generative model may often be avail­ able when explicit next-state distributions are not ; on the other, a generative model obviates the important issue of exploration that arises in a setting where we only have irreversible experience. In this sense, planning results using generative models blur the distinction be­ tween what is typically called "planning" and what is typically called "learning" .

Following standard terminology, we define a (stochas­ tic) policy to be any mapping 1l' : S >--t {a1 , ... , ak}· Thus 7r(s) may be a random variable, but depends only on the current state s . We will be primarily concerned with discounted reinforcement learning 1 , so we assume we are given a number 0 :S 1 < 1 called the discount factor , with which we then define the value function v11' for any policy 1!':

where r; is the reward received on the ith step of exe­ cuting the policy 1!' from state s, and the expectation is over the transition probabilities and any randomization in 1!'. Note that for any s and any 71', IV,.(s)l :S Vmax, where we define Vmax = Rmax/(1 -1).

We also define the Q-function for a given policy 71' as

1 However, our results can be generalized to the undis­ counted finite-horizon case for any fixed horizon H [MS99a].

(where the notations' "'Psa(·) means that s' is drawn according to the distribution Psa ( ·)). We will later de­ scribe an algorithm A that takes as input any states and (stochastically) outputs an action a, and which there­ fore implements a policy. When we have such an al­ gorithm, we will also write VA and QA to denote the value function and Q-function of the policy implemented by A. Finally, we define the optimal value function and the optimal Q-function as v· ( s) = sup .. v .. ( s) and Q*(s, a) = sup,. Q .. (s, a), and the optimal policy 1r· , 1r*(s) = argmaxaQ*(s,a) for all s E S.

3 Planning in Large or Infinite MDPs

Usually one considers the planning problem in MDPs to be that of computing a near-optimal policy, given as input the transition probabilities P,a (-) and the rewards R,a (for instance, by solving the MDP for the optimal policy). Thus, the input is a complete and exact model, and the output is a total mapping from states to actions . Without additional assumptions about the structure of the MDP, such an approach is clearly infeasible in very large state spaces, where even reading all of the input can take N 2 time, and even specifying a general policy requires space on the order of N. In such MDPs, a more fruitful way of thinking about planning might be an on­ line view, in which we examine the per-state complexity of planning. Thus, the input to a planning algorithm would be a single state, and the output would be which single action to take from that state. In this on-line view, a planning algorithm is itself simply a policy (but one that may need to perform some nontrivial computation at each state).

Our main result is the description and analysis of an algorithm A that, given access to a generative model for an arbitrary MDP M, takes any state of M as input and produces an action as output, and meets the following performance criteria:

• The policy implemented by A is near-optimal in M;
• The running time of A (that is, the time required to compute an action at any state) has no dependence on the number of states of M.

This result is obtained under the assumption that the input state to A requires only 0(1) space, a standard assumption known as the uniform cost model [AHU74], that is typically adopted to allow analysis of algorithms that operate on real numbers (such as we require to al­ low infinite state spaces). The uniform cost model es­ sentially posits the availability of infinite-precision regis­ ters (and constant-size circuitry for performing the basic arithmetic operations on these registers). If one is un­ happy with this model, then algorithm A will suffer a dependence on the number of states only equal to the space required to name the states (at worst log(N) for N states).

3.1 A Sparse Sampling Planner

Here is our main result:

Theorem 1 There is a randomized algorithm A that, given access to a generative model for any MDP M , takes as input any state s E S and any value c > 0, outputs an action, and satisfies the following two conditions:

• (Efficiency) The running time of A is 0( (kG) H) , where

In particular, the running time depends only on Rmax, /, and €, and does not depend on N =lSI. If we view Rmax as a constant, the running time bound can also be written

• (Near-Optimality) The value function of the stochastic policy implemented by A satisfies

simultaneously for all states s E S.

As we have already suggested, it will be helpful to think of algorithm A in two different ways. On the one hand, A is an algorithm that takes a state as input and has access to a generative model, and as such we shall be interested in its resource complexity - its running time, and the number of calls it needs to make to the generative model (both per state input). On the other hand, A produces an action as output in response to each state given as input, and thus implements a (possibly stochastic) policy.

The proof of Theorem 1 is given in Appendix A, and detailed pseudo-code for the algorithm is provided in Figure 1. We now give some high-level intuition for the algorithm and its analysis.

Given as input a state s, the algorithm must use the generative model to find a near-optimal action to per­ form from state s. The basic idea of the algorithm is to sample the generative model from states in the "neigh­ borhood" of s . This allows us to construct a small "sub­ MDP" M' of M such that the optimal action in M' from s is a near-optimal action from s in M 2 . There will be no guarantee that M' will contain enough information to compute a good action from any state other than s. However, in exchange for this limited applicability, the MDP M' will have a number of states that does not depend on the number of states in M'.

The graphical structure of M' will be given by a di­ rected tree in which each node is labeled by a state, and each directed edge to a child is labeled by an action and Function: EstimateQ(h, C, -y, G, s)

2 M' will not literally be a sub-MDP of M, in the sense of being strictly embedded in M, due to the variations of ran­ dom sampling. But it will be very "near" such an embedded MDP.

Input: depth h, width C, discount -y, A generative model G, state s.

Output: A list ( Q~( s, a1 ), Q~ ( s, a2) , ... , Q~( s, ak)) , of estimates of the Q* (s , a;).

1. If h = 0, return (0, .. . , 0) .
2. For each a E A, use G to generate C samples from the next-state distribution P,a(·). Let Sa be a set containing these C next-states.
3. For each a E A, let our estimate of Q*(s ,a) be

1. Return (Q~(s,at) , Q~(s , a2 ) , ... , Q~(s , ak)) .
2. Let (Q~(s , at), Q~(s, a2) , ... , Q~(s , ak)) := EstimateQ(h, C, -y, G, s).
3. Return maxae{a 1 , . .. ,akdQ~(s, a)} .

Function: EstimateV(h, C, -y, G, s)

Input : depth h, width C, discount -y, generative model G, state s.

Output: A number \\*(s) that is an estimate of Vh*(s).

Input : tolerance ~:, discount -y , max reward Rmax , generative model G, state so.

Function: Algorithm A(~:, -y, Rmax, G, so) Output: An action a.

1. Let the required horizon H and width C parameters be calculated as given as functions of t, 'Y and Rmax in Theoreml.
2. Let (QH(s, at), QH(s, a2) , ... , QH(s, ak)) := EstimateQ(H, C, -y, G, so).
3. Return argmaxae{a 1 , .. . ,ak}{QH(s,a)} .

Figure 1: Algorithm A for planning in large or infinite state spaces. Estimate V finds the v,; described in the text, and EstimateQ finds analogously defined Q~. Algorithm A implements the policy.

a reward. For the sake of simplicity, let us consider only the two-action case here, with actions a1 and a2. Each node will have C children in which the edge to the child is labeled a1, and C children in which the edge to the child is labeled a2.

The root node of M' is labeled by the state of interest s, and we generate the 2C children of s in the obvious way: we call the generative model C times on the state­ action pair ( s, a 1 ) to get the a 1 -children, and on C times on (s , a2) to get the a2-children. The edges to these children are also labeled by the rewards returned by the generative model , and the child nodes themselves are labeled by the states returned. We will build this (2C)­ ary tree to some depth to be determined. Note that M' is essentially a sparse look-ahead tree.

We can also think of M' as an MDP in which the start state is s, and in which taking an action from a node in the tree causes a transition to a (uniformly) random child of that node with the corresponding action label; the childless leaf nodes are considered absorbing states. Under this interpretation, we can compute the optimal action to take from the root s in M'. Figure 2 shows a conceptual picture of this tree for a run of the algorithm from an input state s0 , for C = 3. (C will typically be much larger.) From the root s0 , we try action a1

three times and action a2 three times. From each of the resulting states, we also try each action C times, and so on down to depth H in the tree. Zero values assigned to the leaves then correspond to our estimates of V 0 *, which are "backed-up" to find estimates of Vt for their parents , which are in turn backed-up to their parents , and so on, up to the root to find an estimate of V.ff(s0 ) .

The central claim we establish about M' is that its size can be independent of the number of states in M, yet still result in our choosing near-optimal actions at the root . We do this by establishing bounds on the required depth H of the tree and the required degree C.

Recall that the optimal policy at s is given by rr* ( s) = arg maXa Q* ( s, a) , and therefore is completely deter­ mined by, and easily calculated from, Q*(s, ·). Esti­ mating the Q-values is a common way of planning in MDPs . From the standard duality between Q-functions and value functions , the task of estimating Q-functions is very similar to that of estimating value functions . So while the algorithm uses the Q-function, we will , purely for expository purposes, actually describe here how we estimate v· ( s).

There are two parts to the approximation we use. First , rather than estimating V*, we will actually es­ timate, for a value of H to be specified later, the h-step expected discounted reward, for h 2: 1,

where r; is the reward received on the ith time step upon executing the optimal policy 1r* from s. Moreover, we see that the v; ( s), for h 2: 1, are recursively given by

where a* is the action taken by the optimal policy from state s, and V 0 *(s) = 0. The quality of the approxima­ tion in Equation (9) becomes better for larger values of h , and is controllably tight for the largest value h = H we eventually choose. One of the main efforts in the proof is establishing that the error incurred by the re­ cursive application of this approximation can be made controllably small by choosing H sufficiently large.

Thus, if we are able to obtain an estimate Vh*- 1 (s') of v;_1(s') for any s', we can inductively define an algo­ rithm for finding an estimate v; ( s) of v; ( s) by making use of Equation (9). Our algorithm will approximate the expectation in Equation (9) by a sample of C random next states from the generative model, where Cis a pa­ rameter to be determined (and which, for reasons that will become clear later , we call the "width"). Recur­ sively, given a way of finding the estimator v;_1 (s') for any s'' we find our estimate vh· ( s) of v; ( s) as follows:

1. For each action a, use the generative model to get Rsa and to sample a set Sa of C independently sam­ pled states from the next-state distribution Psa ( ·).
2. Use our procedure for finding v;_1 to estimate v;_1 ( s') for each state s' in any of the sets Sa.
3. Following Equation (9) , our estimate of Vh* ( s) 1s then given by

To complete the description of the algorithm, all that remains is to choose the depth H , depth, and C, which controls the width of the tree. Bounding the required depth H is the easy and standard part . It is not hard to see that if we choose depth H = log 1 <(1- 1)/ Rmax (the so-called <-horizon time) , then the discounted sum of the rewards that is obtained by considering rewards beyond this horizon is bounded by <.

The central claim we establish about C is that it can be chosen independent of the number of states in M, yet still result in choosing near-optimal actions at the root. The key to the argument is that even though small samples may give very poor approximations to the next-state distribution at each state in the tree, they will , nevertheless, give good estimates of the expectation terms of Equation (9) , and that is really all we need. For this we apply a careful combination of uniform con­ vergence methods and inductive arguments on the tree depth. Again, the technical details of the proof are in Appendix A.

In general, the resulting tree may represent only a van­ ishing fraction of all of the H -step paths starting from so that have non-zero probability in the MDP - that is, the sparse look-ahead tree covers only a vanishing part of the full look-ahead tree. In this sense, our al­ gorithm is clearly related to and inspired by classical look-ahead search techniques [RN95]. Our main contri­ bution is in showing that in very large stochastic en­ vironments, clever random sampling suffices to recon­ struct nearly all of the information available in the (ex­ ponentially or infinitely) large full look-ahead tree. Note that in the case of deterministic environments, where from each state-action pair we can reach only a single next state, the sparse and full trees coincide (assuming a memoization trick described below), and our algorithm reduces to classical deterministic look-ahead search.

3.2 Practical Issues and Lower Bounds

Even though the running time of algorithm A does not depend on the size of the MDP, it still runs in time ex­ ponential in the <-horizon time H, and therefore expo­ nential in 1/(1- 1). It would seem that the algorithm would be practical only if 1 is not too close to 1. In a moment, we will give a lower bound showing it is not possible to do much better without further assumptions on the MDP. Nevertheless, there are a couple of sim­ ple tricks that may help to reduce the running time in certain cases, and we describe these tricks first.

The first idea is to allow different amounts of sampling at each level of the tree. The intuition is that the further we are from the root, the less influence our estimates will have on the Q-values at the root (due to the discounting). Thus, we can sample more sparsely at deeper levels of the tree without having too adverse an impact on our approximation.

We have analyzed various schemes for letting the amount of sampling at a node depend on its depth. None of the methods we investigated results in a running time which is polynomial in 1/f. However, one specific scheme that reduces the running time significantly is to let the number of samples per action at depth i be C; = 1 2 iC, where the parameter C now controls the amount of sam­ pling done at the root. The error in the Q-values using such a scheme does not increase by much , and the run­ ning time is the square root of our original running time.

Another way in which significant savings might be achieved is through the use of memoization in our sub­ routines for calculating the· Vh' ( s) 's. In Figure 2, this means that whenever there are two nodes at the same level of the tree that correspond to the same state, we collapse them into one node (keeping just one of their subtrees). While it is straightforward to show the cor­ rectness of such memoization procedures for determin­ istic procedures, one must be careful when addressing randomized procedures. We can show that the impor­ tant properties of our algorithm are maintained under this optimization.

In implementing the algorithm, one may wish not to specify a targeted accuracy f in advance, but rather to try to do as well as is possible with the computational re­ sources available. In this case, an "iterative-deepening" approach may be taken. This would entail simultane­ ously increasing C and H by decreasing the target f. Also, as studied in Davies et. a!. [DNM98], if we have access to an initial estimate of the value function, we can replace our estimates V 0 * ( s) = 0 at the leaves with the estimated value function at those states. Though we shall not do so here, it is again easy to make for­ mal performance guarantees depending on C, Hand the supremum error of the value function estimate we are using.

Unfortunately, despite these tricks, it is not difficult to prove a lower bound that shows that any planning algorithm with access only to a generative model, and which implements a policy that is f-close to optimal in a general MDP, must have running time at least exponen­ tial in the f-horizon time. We now describe this lower bound.

Theorem 2 Let A be any algorithm that is given access only to a generative model for an MDP M, and inputs s (a state in M) and f. Let the stochastic policy imple­ mented by A satisfy

simultaneously for all states s E S. Then there ex­ ists an MDP M on which A makes at least 0(2H) = 0((1/f)(lflog(lj-y))) calls to the generative model.

Proof: Let H = log"' f = log(1/f)/log(1/'Y). Con­ sider a binary tree T of depth H. We use T to define an MDP in the following way. The states of the MDP are the nodes of the tree. The actions of the MDP are { 0, 1}. When we are in state s and perform an action b we reach (deterministically) state Sb, where Sb is the b-child of s in T. If s is a leaf ofT then we move to an absorbing state. We choose a random leaf v in the tree. The reward function for v and any action is Rmax, and the reward at any other state and action is zero.

Algorithm A is given s0 , the root ofT. For algorithm A to compute a near optimal policy, it has to "find" the node v, and therefore has to perform at least 0(2H) calls to the generative model. 0

4 Summary and Related Work

We have described an algorithm for near-optimal plan­ ning from a generative model, that has a per-state run­ ning time that does not depend on the size of the state space, but which is still exponential in the f-horizon time. An important open problem is to close the gap between our lower and upper bound. Our lower bound shows that the number of steps has to grow polyno­ mially in 1/ f while in the upper bound the number of steps grows sub-exponentially in 1/f, more precisely (1/f)O(Iog(l/,)). Closing this gap, either by giving anal­ gorithm that would be polynomial in 1/f or by proving a better lower bound, is an interesting open problem.

Two interesting directions for improvement are to al­ low partially observable MDPs (POMDPs) , and to find more efficient algorithms that do not have exponential dependence on the horizon time. As a first step to­ wards both of these goals, in a separate paper [KMN99] we investigate a framework in which the goal is to use a generative model to find a near-best strategy within a restricted class of strategies for a POMDP. Typi­ cal examples of such restricted strategy classes include limited-memory strategies in POMDPs, or policies in large MDPs that implement a linear mapping from state vectors to actions. Our main result in this framework says that as long as the restricted class of strategies is not too "complex" (where this is formalized using ap­ propriate generalizations of standard notions like VC di­ mension from supervised learning), then it is possible to find a near-best strategy from within the class, in time that again has no dependence on the size of the state space. If the restricted class of strategies is smoothly parameterized, then this further leads to a number of fast, practical algorithms for doing gradient descent to find the near-best strategy within the class, where the running time of each gradient descent step now has only linear rather than exponential dependence on the hori­ zon time.

Another approach to planning in POMDPs that is based on the algorithm presented here is investigated by McAllester and Singh [MS99b], who show how the approximate belief-state tracking methods of Boyen and Koller [BK98] can be combined with our algorithm.

Acknowledgements

We thank David McAllester, Satinder Singh and Rich Sutton for many enlightening discussions and numerous insights on the ideas presented here.