---
title: "A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes"
authors:
  - "Michael J. Kearns"
  - "Yishay Mansour"
  - "Andrew Y. Ng"
doi: ""
url: "https://ijcai.org/proceedings/1999/188"
pdf: "https://ijcai.org/proceedings/1999/0188.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "1324-1230"
track: "Uncertainty and Probabilistic Reasoning"
keywords:
---

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

Michael J. Kearns, Yishay Mansour, Andrew Y. Ng

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 1324-1230.

## 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].