Efficient Approximate Planning in Continuous Space Markovian Decision Problems

Efficient Approximate Planning in Continuous Space Markovian Decision Problems
unpublished ( gzipped Postscript - 128 )

Abstract: In this article we consider Monte-Carlo planning algorithms for planning in continuous state-space, discounted Markovian Decision Problems (MDPs) having a smooth transition law and a finite action space. We prove various polynomial complexity results for the considered algorithms.