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

Robert L. Bray

Econometrica, 2022, vol. 90, issue 4, 1915-1929

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.

Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.3982/ECTA17664

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:emetrp:v:90:y:2022:i:4:p:1915-1929

Ordering information: This journal article can be ordered from
https://www.economet ... ordering-back-issues

Access Statistics for this article

Econometrica is currently edited by Guido W. Imbens

More articles in Econometrica from Econometric Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().