Approximate Dynamic Programming
Solving the curses of dimensionality
The Second Edition
(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 - to purchase an electronic copy, click here.) As of January 1, 2015, the book has over 1500 citations.
Audience
Table
of contents
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. My thinking on this has matured since this chapter was written. Please download:
Clearing the Jungle of Stochastic Optimization (c) Informs - This is a tutorial article, with a better section on the four classes of policies, as well as a fairly in-depth section on lookahead policies (completely missing from the ADP book). For a shorter article, written in the style of reinforcement learning (with an energy setting), please download:
Also see the two-part tutorial aimed at the IEEE/controls community:
W. B. Powell, Stephan Meisel, "Tutorial on Stochastic Optimization in Energy I: Modeling and Policies", IEEE Trans. on Power Systems (to appear) Summarizes the modeling framework and four classes of policies, contrasting the notational systems and canonical frameworks of different communities.
W. B. Powell, Stephan Meisel, "Tutorial on Stochastic Optimization in Energy II: An energy storage illustration", IEEE Trans. on Power Systems (to appear) Illustrates the process of modeling a stochastic, dynamic system using an energy storage application, and shows that each of the four classes of policies works best on a particular variant of the problem. A fifth problem shows that in some cases a hybrid policy is needed.
Tutorial articles - A list of articles written with a tutorial style.
Presentations - A series of presentations on approximate dynamic programming, spanning applications, modeling and algorithms.
Applications - Applications of ADP to some large-scale industrial projects.
Computational stochastic optimization - Check out this new website for a broader perspective of stochastic optimization.