A Comment on "Using Randomization to Break the Curse of Dimensionality". Issue 4 (28th July 2022)

• Record Type: Journal Article
• Authors: Bray, Robert L.
• Is Part Of: Econometrica. Volume 90:Issue 4(2022)
• Page Start: 1915
• Page End: 1929
• Publication Date: 2022-07-28
• Subjects: Markov decision process -- dynamic program -- curse of dimensionality -- random value iteration -- empirical process; Econometrics -- Periodicals; Economics, Mathematical -- Periodicals; Economics -- Periodicals; Économétrie -- Périodiques; Mathématiques économiques -- Périodiques; Économie politique -- Périodiques; 330.05
• DOI: 10.3982/ECTA17664
• Languages: English
• ISSNs: 0012-9682

Abstract

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.