On the limits of using randomness to break a dynamic program's curse of dimensionality

Rust (1997) discovered a class of dynamic programs that can be solved in polynomial time with a randomized algorithm. Insulated from the curse of dimensionality, this walled garden of tractable dynamic problems is intriguing, if not useful. Unfortunately, I find that the class is more limited than we initially thought, as it requires all but a vanishingly small fraction of state variables to behave arbitrarily similarly to i.i.d. uniform random variables. However, in this special case, his approach can be tremendously powerful