A Comment on “Using Randomization to Break the Curse of Dimensionality”
Econometrica · 2022 · Volume 90 · Issue 4
Abstract
Rust (1997b) discovered a class of dynamic programs that can be solved in polynomial time with a randomized algorithm. For these dynamic programs, the optimal values of a polynomially large sample of states are sufficient statistics for the (near) optimal values everywhere, and the values of this random sample can be bootstrapped from the sample itself. However, I show that this class is limited, as it requires all but a vanishingly small fraction of state variables to behave arbitrarily similarly to i.i.d. uniform random variables.
Keywords
Markov decision process, dynamic program, curse of dimensionality, random value iteration, empirical process
Enable JavaScript for citation tools and additional paper interactions.