A Comment on “Using Randomization to Break the Curse of Dimensionality”
评论了Rust(1997b)发现的可用随机化算法在多项式时间内求解的一类动态规划问题，指出该类问题要求几乎所有状态变量行为近似独立同分布均匀随机变量，因此适用范围有限。
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.