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

摘要

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) or an arbitrary MDP, performs on-line, near-optimal planning with a per-state running time that has no dependence on the number of states.