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

Abstract

An issue that is critical for the application of Markov decision processes (MDPs) to r ea listic problems is how the complexity of planning scales with the size of the MDP . In stochastic environments with very large or even infinite state spaces, traditional planning a nd r einforcement learning algorithms are often inapplicable, since their running time typi ca lly scales linearly with the state space size. In this paper we present a new algorithm that, given only a g enem tive model (simulator) for an arbitrary MDP , performs near-optimal planning with a running time that has no dependence on the number of states. Although the running time is exponential in the horizon time (which depends only on the discount factor 1 and the d es ired degree of approximation to th e optimal policy), our results establish for the first time that there are no theoretical barriers to computing near-optimal policies in arbitrarily larg e, unstructured MDPs. Our algorithm is based on the idea of sparse sampling. We prove that a randomly sampled look-ahead tree that covers only a vanishing fraction of the full look-ahead tree nevertheless suffices to compute near-optimal actions from any state of an MDP. Pra ctica l impl ementations of the algorithm are discussed , and we draw ties to our related recent results on finding a near-best strategy from a given class of strategies in very large partially observable MDPs [KMN99].