Take Action

Home | Faculty & Research Overview | Research

Research Details

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

Abstract

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.

Type

Working Paper

Author(s)

Robert Bray

Date Published

2020

Citations

Bray, Robert. 2020. On the limits of using randomness to break a dynamic program’s curse of dimensionality.

KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more

Take Action