Dynamic Programming And Optimal Control, Vol. 1

by Dimitri P. Bertsekas

This is a substantially expanded (by about 30%) and improved edition of Vol. 1 of the best-selling dynamic programming book by Bertsekas. (A relatively minor revision of Vol.\ 2 is planned for the second half of 2001.) DP is a central algorithmic method for optimal control, sequential decision making under uncertainty, and combinatorial optimization. The treatment focuses on basic unifying themes and conceptual foundations. It illustrates the power of the method with many examples and applications from engineering, operations research, and economics.

Among its special features, the book:

(a) provides a unifying framework for sequential decision making

(b) develops the theory of deterministic optimal control including the Pontryagin Minimum Principle

(c) describes neuro-dynamic programming techniques for practical application of DP to complex problems that involve the dual curse of large dimension and lack of an accurate mathematical model

(d) provides a comprehensive treatment of infinite horizon problems in the second volume, and an introductory treatment in the first volume

(e) contains many exercises, with solutions of the most theoretical ones posted on the book's www page

Highlights of the revision: (a) Much new material on suboptimal control, including neuro-dynamic programming and rollout algorithms, and their applications in combinatorial optimization and stochastic optimal control. (b) A section on estimation and control of systems with a non-probabilistic (set membership) description of uncertainty. (c) A section on infinite horizon continuous-time (semi-Markov) decision problems. (d) A new appendix dealing with the minimax and expected utility approaches for formulating decision problems under uncertainty.

Genres: Mathematics, Computer Science, Algorithms, Research, Textbooks, Academic

530 pages, Hardcover

First published January 1, 1995

Reviews

[Hyokun Yun · Rating 4 out of 5]

This book provides a very gentle introduction to basics of dynamic programming. I have never seen a book in mathematics or engineering which is more reader-friendly with respect to the presentation of theorems and examples. Most proofs cover almost every case without notorious "this is left to the reader as an exercise", and every example is accompanied with detailed steps for computation. Although this book is targeted for first-year graduate students, undergraduate students would not have much difficulty understanding most of the material.

I can't say much about the coverage of the breadth since I am not an expert on dynamic programming, but the book seems to cover a good range of topics, from basic discrete finite-horizon problems to infinite-horizon problems, continuous-time problems, and approximate control. Unfortunately, the chapter on approximate control, which is the most fashionable topic today and a matter of fact the primary motivation for me to read this book, is focused mostly on delivering very basic intuitions and defers most of serious discussions to Volume II.

I would've loved this book more if it contained numerical exercises as well. Although computational considerations are discussed time to time, most of the examples and exercise problems are analytical ones. This is unfortunate, because implementing an algorithm is often a very good way of understanding it. Since that dynamic programming has a lot of fascinating applications, implementing algorithms for such problems and seeing them work would help students gain interest on this topic. Sutton and Barto's reinforcement learning book certainly does a very good job on this aspect.