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

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

Abstract: A critical issue for the application of Markov decision processes (MDPs) to realistic problems is how the complexity of planning scales with the size of the MDP. In stochastic environments with very large or infinite state spaces, traditional planning and reinforcement learning algorithms may be inapplicable, since their running time typically grows linearly with the state space size in the worst case. In this paper we present a new algorithm that, given only a generative model (a natural and common type of simulator) for an arbitrary MDP, performs on-line, near-optimal planning with a per-state running time that has no dependence on the number of states. The running time is exponential in the horizon time (which depends only on the discount factor γ and the desired degree of approximation to the optimal policy). Our algorithm thus provides a different complexity trade-off than classical algorithms such as value iteration—rather than scaling linearly in both horizon time and state space size, our running time trades an exponential dependence on the former in exchange for no dependence on the latter.

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. Practical implementations 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.

Introduction

Traditional planning algorithms for Markov Decision Processes (MDPs), such as Value Iteration or Policy Iteration, suffer from the "curse of dimensionality." Their complexity typically scales linearly with the number of states ($N$). In real-world applications—like robotics, logistics, or complex games—the state space can be exponentially large or even continuous, making these classical approaches computationally infeasible.

This paper, authored by Michael Kearns, Yishay Mansour, and Andrew Y. Ng, introduces a "Sparse Sampling" algorithm that performs near-optimal planning in MDPs with massive or even infinite state spaces. Crucially, the algorithm's running time is completely independent of the number of states, relying instead on a generative model (simulator) to build a small, representative look-ahead tree.

The Sparse Sampling Algorithm

The core idea of the Sparse Sampling Planner is to move away from global planning (computing a policy for every state) to local, "on-line" planning (computing the best action for the current state). The algorithm relies on two primary components:

  1. Generative Model: The algorithm assumes access to a "black box" simulator. Given a state and an action, the simulator returns a reward and a randomly sampled next state according to the underlying transition probabilities.
  2. Sparse Look-ahead Tree: To decide on an action at state $s$, the algorithm builds a tree of depth $H$ (the horizon). Instead of branching on every possible next state—which could be infinite—it samples a fixed number of next states ($C$) for every possible action.
A sparse look-ahead tree of depth H. From the root state $s_0$, the algorithm samples a fixed number of next states for each action to estimate values recursively.

The algorithm uses two recursive functions, EstimateQ and EstimateV, to back up values from the leaves of the tree to the root. By using uniform convergence arguments, the authors prove that a relatively small number of samples ($C$) is sufficient to ensure the estimated value at the root is close to the true optimal value.

Theoretical Results and Insights

The paper provides a rigorous mathematical foundation for the algorithm's performance, shifting the computational burden from the breadth of the state space to the depth of the planning horizon.

  • State-Space Independence: The most profound insight is that the complexity of near-optimal planning does not have to depend on the size of the world. The "width" of the tree ($C$) depends on the desired accuracy ($\epsilon$) and the discount factor ($\gamma$), but not on the total number of states ($N$).
  • Efficiency and Optimality: Theorem 1 proves the algorithm's running time is $O((kC)^H)$, where $k$ is the number of actions. It also proves the algorithm implements a policy that is at most $\epsilon$ away from the optimal value function $V^*$ for all states simultaneously.
  • Fundamental Lower Bounds: Theorem 2 shows that any algorithm relying solely on a generative model must have a running time exponential in the horizon $H$ to guarantee near-optimality. This confirms that while the algorithm escapes the dependence on state space size, the exponential dependence on the horizon is a fundamental theoretical barrier.

Discussion and Limitations

While the algorithm provides a breakthrough in state-space independence, it faces the "Horizon Bottleneck." The exponential dependence on the horizon $H$ makes it computationally expensive for problems with very long planning horizons (i.e., when the discount factor $\gamma$ is very close to 1).

Furthermore, there is a technical gap between the upper bound (sub-exponential in $1/\epsilon$) and the lower bound (polynomial in $1/\epsilon$). Finding an algorithm polynomial in $1/\epsilon$ remains an important open problem. In practice, the authors suggest techniques like memoization and varying the sampling rate by depth to improve real-world performance. The principles established here also extend to Partially Observable MDPs (POMDPs), providing a framework for finding near-best strategies in even more complex environments.

Summary updated

Abstract

A critical issue for the application of Markov decision processes (MDPs) to realistic problems is how the complexity of planning scales with the size of the MDP. In stochastic environments with very large or infinite state spaces, traditional planning and reinforcement learning algorithms may be inapplicable, since their running time typically grows linearly with the state space size in the worst case. In this paper we present a new algorithm that, given only a generative model (a natural and common type of simulator) for an arbitrary MDP, performs on-line, near-optimal planning with a per-state running time that has no dependence on the number of states. The running time is exponential in the horizon time (which depends only on the discount factor γ and the desired degree of approximation to the optimal policy). Our algorithm thus provides a different complexity trade-off than classical algorithms such as value iteration—rather than scaling linearly in both horizon time and state space size, our running time trades an exponential dependence on the former in exchange for no dependence on the latter. 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. Practical implementations 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 (Kearns, Mansour, & Ng. Neural information processing systems 13, to appear).
BibTeX
@inproceedings{kearns1999sparse,
  author = {Michael J. Kearns and Yishay Mansour and Andrew Y. Ng},
  title = {{A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure