Abstract Dynamic Programming

by Dimitri P. Bertsekas


abstractdpcover1.jpg

The research monograph "Abstract Dynamic Programming," appeared in April, 2013, and may be ordered in hardcover from the publishing company, Athena Scientific, or from Amazon.com, or may be freely downloaded from here and used for personal or instructional purposes.

The research monograph provides a synthesis of research on the foundations of dynamic programming that started nearly 50 years ago, with the modern theory of approximate dynamic programming and the new class of semicontractive models.

It aims at a unified and economical development of the core theory and algorithms of total cost sequential decision problems, based on the strong connections of the subject with fixed point theory. The analysis focuses on the abstract mapping that underlies dynamic programming and defines the mathematical character of the associated problem. The discussion centers on two fundamental properties that this mapping may have: monotonicity and (weighted sup-norm) contraction. It turns out that the nature of the analytical and algorithmic DP theory is determined primarily by the presence or absence of these two properties, and the rest of the problem's structure is largely inconsequential. New research is focused on two areas:

  • The ramifications of these properties in the context of algorithms for approximate dynamic programming.
  • The new class of semicontractive models, exemplified by stochastic shortest path problems, where some but not all policies are contractive.


    The on-line version of the book is the same as the print edition published in China in June 2014 (Tsinghua Press). The errata of the original print edition, as per March 1, 2014, have been incorporated in the present on-line version of the book.

    The following two papers have a strong connection to the book, and amplify on the range of applications of the semicontractive models of Chapters 3 and 4:

  • D. P. Bertsekas, "Robust Shortest Path Planning and Semicontractive Dynamic Programming", Lab. for Information and Decision Systems Report LIDS-P-2915, MIT, Feb. 2014.

  • D. P. Bertsekas, "Infinite-Space Shortest Path Problems and Semicontractive Dynamic Programming", Lab. for Information and Decision Systems Report LIDS-P-2916, MIT, Feb. 2014.

    These papers may be viewed as on-line appendixes of the book.