Mobile Edition
Print
Get the Mag
Weekly UpdatesDynamic programming is a rich area with numerous books already available. Professor Powell's book on approximate dynamic programming sheds a completely new light on this exciting area. Instead of focusing on traditional approaches to dynamic programming, most of the content is devoted to recent advances in solving large-scale dynamic programs. Professor Powell definitely breaks the longstanding myth of the curse of dimensionality by presenting several state-of-the-art solution methodologies capable of solving problems of unthinkable size.
The book exposes the reader to an excellent mixture of operations research, mathematical programming and artificial intelligence techniques. The transitions and the interplay among these three areas are presented in a coherent way, thus making it an extremely readable book.
The spread of topics is also amazing, and yet the book is focused on approximate dynamic programming. Stochastic optimization, machine learning, mathematical programming modeling, finite and infinite time horizon problems, and value function approximations are all nicely blended within a single book.
The material is presented at various levels and several different aspects are addressed. The book can easily be used for either an undergraduate or a graduate course textbook. There is abundant technical material to design a comprehensive graduate level course. The book also includes a wide range of exercises.
Perhaps the most appealing aspect of Professor Powell's book is the fact that it spans both theory and practice. On the theoretical side, treatment of convergence is provided for several algorithms and various technical statements are rigorously proved, including aspects of the optimality equation. On the practical side, an important contribution is the modeling framework. Throughout the book several real-world examples are discussed, from transportation to the energy sector and finance. All of them are presented in the same modeling framework. From a practitioner's perspective, it is perhaps even more important to stress the computational tractability of the presented solution methodologies. Problems deemed intractable a few years ago are now easily solved by using the exhibited techniques in Professor Powell's book. This clears the way to more comprehensive models and to real-time dynamic decision making. I would strongly recommend the book to any practitioner facing complex, dynamic models involving constantly changing information streams.
The first two chapters expose the reader to the basics of dynamic programming. They nicely outline the computational challenges in solving large-scale dynamic programs and several illustrative examples are provided. A more traditional treatment of dynamic programming is provided in the third chapter. The standard value and policy iteration algorithms are the bulk of this chapter. Convergence proofs are also provided.
Modern aspects of approximate dynamic programming span the remaining chapters. The important concept of post-decision modeling is introduced in the fourth chapter. This modeling paradigm is the basis for most of the algorithms. The first exposure to reinforcement learning, and thus artificial intelligence, is also provided in this chapter.
Through the evolution of dynamic programming, several modeling styles have developed. In the fifth chapter the book discusses a brand new modeling approach, suitable for many complex problems, with intriguing decision making and exogenous information processes. Every reader should bear in mind the importance of this modeling approach. It makes the remaining chapters substantially more readable and easier to understand. The modeling principles were developed by focusing on practical aspects and the ease of modeling the ever evolving real-world situations.
Chapter 6 serves as the springboard to the following chapters by covering the stochastic approximation methods. The focus is on the so-called stochastic gradient algorithm. An important parameter of this algorithm is the step size. The book provides a thorough treatment of the step size selection process. In addition to standard step size formulas, a substantial portion of the chapter is devoted to selecting an optimal step size. The chapter is concluded with two convergence results, which are presented in a tutorial fashion, as an introduction to stochastic convergence theory. The two proofs illustrate an older proof technique and a more modern technique.
The main concept behind approximate dynamic programming is the notion of value function approximations. Chapter 7 provides a comprehensive treatment of this topic. A very recent development particularly suited for extremely large-scale problems is introduced in this chapter. By using novel ideas, the book discusses how to intertwine aggregation and value function approximations. A more classical approach of regression is also discussed at length.
Chapters 8 and 9 deal with various aspects of approximate dynamic programming as it pertains to finite and infinite time horizon cases, respectively. The approximate dynamic framework is dissected based on these two properties. In the finite time horizon case, a parallel is drawn between the approximate programming algorithm treated and more standard approaches originating from artificial intelligence.
A well-known phenomenon in computational dynamic programming is the issue of exploration versus exploitation. This is the focus of Chapter 10. Several variations to the basic algorithmic framework are discussed in this chapter.
Many of the examples discussed throughout the book are resource allocation problems, where the decision maker is to allocate limited resources through several steps in time under continuously upcoming exogenous data streams. The current decision impacts future decisions through resource constraints. Chapters 11 and 12 are devoted to such problems. A more in-depth and specific coverage of value function approximations for resource allocation problems is discussed in Chapter 11. The chapter shows how to use linear and piecewise linear approximations to the value function. The concepts are nicely embedded within the algorithms. The convergence of the resulting algorithms is also provided. The modeling framework and algorithmic principles are detailed for several examples in Chapter 12. These include blood management, asset acquisition and fleet management.
The last chapter focuses on implementation issues and challenges, including how to model, set up the underlying algorithm, and tuning.
Reviewed by
Diego Klabjan,
Department of Industrial Engineering and Management Sciences,
Northwestern University, Evanston, IL 60208, USA
E-mail: d-klabjan@northwestern.edu
Warren B. Powell
Wiley, New York, 2007, 488 pages, ISBN 9780470171554, $110
FEED