Econometrica: Jul, 2022, Volume 90, Issue 4

A Comment on “Using Randomization to Break the Curse of Dimensionality”

https://doi.org/10.3982/ECTA17664
p. 1915-1929

Robert L. Bray

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.

Supplemental Material