Abstract
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 are considered. We prove various polynomial complexity results for the considered algorithms, improving upon several known bounds.