×

Using randomization to break the curse of dimensionality. (English) Zbl 0872.90107

Summary: 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 (DDPs).

MSC:

90C40 Markov and semi-Markov decision processes
90C60 Abstract computational complexity for mathematical programming problems
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI Link