Rust, John Using randomization to break the curse of dimensionality. (English) Zbl 0872.90107 Econometrica 65, No. 3, 487-516 (1997). 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). Cited in 2 ReviewsCited in 49 Documents MSC: 90C40 Markov and semi-Markov decision processes 90C60 Abstract computational complexity for mathematical programming problems 90C39 Dynamic programming Keywords:Bellman operator; maximal inequalities; curse of dimensionality; random versions of successive approximations; multigrid algorithms; finite and infinite horizon Markovian decision problems; discrete decision processes PDFBibTeX XMLCite \textit{J. Rust}, Econometrica 65, No. 3, 487--516 (1997; Zbl 0872.90107) Full Text: DOI Link