A Comment on Using Randomization to Break the Curse of Dimensionality
成果类型：
Article
署名作者：
Bray, Robert L.
署名单位：
Northwestern University
刊物名称：
ECONOMETRICA
ISSN/ISSBN：
0012-9682
DOI：
10.3982/ECTA17664
发表日期：
2022
页码：
1915-1929
关键词：
摘要：
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.