Approximate Dynamic Programming. Solving the Curses of Dimensionality Wiley Series in Probability and Statistics

Editorial Review
A complete and accessible introduction to the real-world applications of approximate dynamic programming

With the growing levels of sophistication in modern-day operations, it is vital for practitioners to understand how to approach, model, and solve complex industrial problems. Approximate Dynamic Programming is a result of the author's decades of experience working in large industrial settings to develop practical and high-quality solutions to problems that involve making decisions in the presence of uncertainty. This groundbreaking book uniquely integrates four distinct disciplines-Markov design processes, mathematical programming, simulation, and statistics-to demonstrate how to successfully model and solve a wide range of real-life problems using the techniques of approximate dynamic programming (ADP). The reader is introduced to the three curses of dimensionality that impact complex problems and is also shown how the post-decision state variable allows for the use of classical algorithmic strategies from operations research to treat complex stochastic optimization problems.

Designed as an introduction and assuming no prior training in dynamic programming of any form, Approximate Dynamic Programming contains dozens of algorithms that are intended to serve as a starting point in the design of practical solutions for real problems. The book provides detailed coverage of implementation challenges including: modeling complex sequential decision processes under uncertainty, identifying robust policies, designing and estimating value function approximations, choosing effective stepsize rules, and resolving convergence issues.

With a focus on modeling and algorithms in conjunction with the language of mainstream operations research, artificial intelligence, and control theory, Approximate Dynamic Programming:
*

Models complex, high-dimensional problems in a natural and practical way, which draws on years of industrial projects
*

Introduces and emphasizes the power of estimating a value function around the post-decision state, allowing solution algorithms to be broken down into three fundamental steps: classical simulation, classical optimization, and classical statistics
*

Presents a thorough discussion of recursive estimation, including fundamental theory and a number of issues that arise in the development of practical algorithms
*

Offers a variety of methods for approximating dynamic programs that have appeared in previous literature, but that have never been presented in the coherent format of a book

Motivated by examples from modern-day operations research, Approximate Dynamic Programming is an accessible introduction to dynamic modeling and is also a valuable guide for the development of high-quality solutions to problems that exist in operations research and engineering. The clear and precise presentation of the material makes this an appropriate text for advanced undergraduate and beginning graduate courses, while also serving as a reference for researchers and practitioners. A companion Web site is available for readers, which includes additional exercises, solutions to exercises, and data sets to reinforce the book's main concepts.
Cached date: AWS Called=true

Customer Reviews

Approximate Dynamic Programming for practioners

2008-02-16
Our consulting firm has successfully collaborated with Dr. Powell for years and I have seen first hand how ADP solves large scale, real world problems that would frankly be intractable by many traditional traditional operations research or optimization techniques. While consulting firms and other business jealously guard their intellectual property, it is terrific for all of us that academics are rewarded for precisely the opposite. I would highly recommend for any serious practitioner to grab a copy of this book and study it. Probably one of the best $100s you will have spent in a while.

Approximate Dynamic Programming for practitioners and education

2007-12-02
In this book Warren nicely blends his practical experience in modeling and solving complex dynamic and stochastic problems occurring in a variety of industries (transportation, the financial sector, energy, etc) with algorithmical and theoretical aspects of approximate dynamic programming. The book can be either used as a textbook in undergraduate or graduate courses, or for practitioners to learn about recent advances in this exciting area. Indeed, I have already used it twice as a textbook for a graduate course, and on the other hand, I have recommended it to several practitioners. Without doubt, this is an important contribution in approximate dynamic programming.

I strongly recommend the book for all practitioners facing large-scale complex dynamic programs. It is also an excellent textbook.

Perspectives from the author

2007-09-10
This book represents a paradigm shift in the presentation of dynamic programming/stochastic optimization. Classical treatments of dynamic programming/neuro-dynamic programming/reinforcement learning typically assume small "action spaces," and often assume the presence of a one-step transition matrix. By contrast, authors working with decision vectors in the presence of uncertainty often turn to stochastic linear programming. But these techniques typically struggle when applied to multistage applications. It is extremely hard to solve most of these problems without taking advantage of the presence of a state variable that captures previous history.

I have adopted the notational style where S is the state of the system, and x is a decision, using the language of math programming. x may have many thousands of dimensions for some problem classes (although the book considers many classical problems where decisions are relatively simple).

The challenge that arises when x is a vector when we use dynamic programming is the expectation within the max/min operator. Bellman's equation is typically written

V(S_t) = max (C(S_t,x) + discount * E{V(S_{t+1})|S_t} )

If x is a vector, we generally need the power of math programming to solve the maximization problem. The challenge is the expectation. We avoid this using the post-decision state variable, which is the state immediately after we have made a decision, but before any time has passed (bringing new information). Denoted S^x_t, the post-decision state variable is a deterministic function of S and x. If V^x(S^x_t) is the value function around the post-decision state variable, we obtain

V(S_t) = max (C(S_t,x) + discount * V^x(S^x_t)

The book provides a number of practical examples of this, but the key is that the maximization problem is now a deterministic problem. The final step is that we have to replace V^x() with a suitably chosen approximation. If our maximization problem is a linear, nonlinear or integer programming problem, we have to choose an approximation for V^x() that allows these algorithmic tools to be used.