Solving the curses of dimensionality

(c) John Wiley and Sons

Dynamic programming has often been dismissed because it suffers from "the curse of dimensionality." In fact, there are up to three curses of dimensionality: the state space, the outcome space and the action space.

This book brings together dynamic programming, math programming, simulation and statistics to solve complex problems using practical techniques that scale to real-world applications. Even more so than the first edition, the second edition forms a bridge between the foundational work in reinforcement learning, which focuses on simpler problems, and the more complex, high-dimensional applications that typically arise in operations research. Our work is motivated by many industrial projects undertaken by CASTLE Lab, including freight transportation, military logistics, finance, health and energy.

The book is written at a level that is accessible to advanced undergraduates, masters students and practitioners with a basic background in probability and statistics, and (for some applications) linear programming.

The second edition is a major revision, with over 300 pages of new or heavily revised material. The middle section of the book has been completely rewritten and reorganized. (Click here to go to Amazon.com to order the book.)

For more information on the book, please see:

Chapter summaries and comments- A running commentary (and errata) on each chapter. Last updated: July 31, 2011.

Selected chapters -I cannot make the whole book available for download (it is protected by copyright), however Wiley has given me permission to make two important chapters available - one on how to model a stochastic, dynamic program, and one on policies.Chapter 5 - Modeling - Good problem solving starts with good modeling.

Chapter 6 - Policies - The four fundamental policies (but see "cost function approximations" under

Chapter summaries and comments)

Additional readings- Various tutorial articles

Some big problems:ADP has allowed us to solve some truly large scale problems:1) Fleet management at Schneider National: 50,000 variables (dimensions) per time period over 60 time periods.

Simao, H. P. A. George, Warren B. Powell, T. Gifford, J. Nienow, J. Day, "Approximate Dynamic Programming Captures Fleet Operations for Schneider National," Interfaces, Vol. 40, No. 5, pp. 342-352, 2010. (c) Informs - This is a light version of the paper with no equations.

Simao, H. P., J. Day, A. George, T. Gifford, J. Nienow, W. B. Powell, “An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application,” Transportation Science, Vol. 43, No. 2, pp. 178-197 (2009). (c) Informs. - This paper has all the equations.

2) SMART: A stochastic, multiscale model for energy policy. This problem models hourly wind variations in an investment planning problem that spans 20 years (175,000 time periods).

Reviews(of the first edition)

If you came here directly, click here for the CASTLE Lab website for more information.