This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Chang, H. S. Articles by Marcus, S. I. Search for Related Content

An Adaptive Sampling Algorithm for Solving Markov Decision Processes

Department of Computer Science and Engineering, Sogang University, Seoul, Korea
Robert H. Smith School of Business, and Institute for Systems Research, University of Maryland, College Park, Maryland 20742
Department of Electrical and Computer Engineering, and Institute for Systems Research, University of Maryland, College Park, Maryland 20742
Department of Electrical and Computer Engineering, and Institute for Systems Research, University of Maryland, College Park, Maryland 20742
hschang{at}ccs.sogang.ac.kr
mfu{at}rhsmith.umd.edu
jqhu{at}glue.umd.edu
marcus{at}eng.umd.edu

Based on recent results for multiarmed bandit problems, we propose an adaptive sampling algorithm that approximates the optimal value of a finite-horizon Markov decision process (MDP) with finite state and action spaces. The algorithm adaptively chooses which action to sample as the sampling process proceeds and generates an asymptotically unbiased estimator, whose bias is bounded by a quantity that converges to zero at rate (ln N)/N, where N is the total number of samples that are used per state sampled in each stage. The worst-case running-time complexity of the algorithm is O((|A|N)^H), independent of the size of the state space, where |A| is the size of the action space and H is the horizon length. The algorithm can be used to create an approximate receding horizon control to solve infinite-horizon MDPs. To illustrate the algorithm, computational results are reported on simple examples from inventory control.

Subject classifications: dynamic programming/optimal control:Markov finite state.
History: Received June 2002; revision received May 2003; accepted November 2003.