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 break-ing the "curse of dimensionality" for a subclass of MDPs known as discrete decision processes (DDPs).