Using randomization to break the curse of dimensionality

This paper introduces random versions of successive approximations and multigrid algorithms for computing approximate solutions to a class of finite and infinite horizon Markovian decision problems (MDPs). We prove that these algorithms succeed in breaking the ''curse of dimensionality'' for a subclass of MDPs known as discrete decision processes (DDFs).