Efficient approximate planning in continuous space Markovian Decision Problems
Csaba Szepesvári · 2001
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. 1 Introduction MDPs provide a clean and simple, yet fairly rich framework for studying various aspects of intelligence, such as, e.g., planning. A well-known practical limitation planning in MDPs is called the curse of dimensionality [1], referring to the exponential rise in the resources required to compute (even approximate) solutions to an MDP as the size of the MDP (the number of state variables) increases. For example, conventional dynamic programming (DP) algorithms, such as value- or policy-iteration scale exponentially with the size even if they are used as subroutines to sophisticated multigrid algorithms [4]. Moreover, the curse of dimensionality is not akin to any kind of special algorithm as shown...