Econometrica: May 1997, Volume 65, Issue 3
Using Randomization to Break the Curse of Dimensionality
John RustThis 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).
Log In To View Full Content