Belmont (Mass.): Athena Scientific, 2013. - 257 p.A research monograph providing 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: 1) The ramifications of these properties in the context of algorithms for approximate dynamic programming, and 2) The new class of semicontractive models, exemplified by stochastic shortest path problems, where some but not all policies are contractive.
The book has a theoretical research monograph character, but requires a modest mathematical background for all chapters except the last one, essentially a first course in analysis. Of course, prior exposure to DP will definitely be very helpful to provide orientation and context. A few exercises have been included, either to illustrate the theory with examples and counterexamples, or to provide applications and extensions of the theory. Solutions of all the exercises can be found in Appendix D, at the book’s internet site:http://www.athenasc.com/abstractdp.htmland at the author’s WEB site:http://web.mit.edu/dimitrib/www/home.htmlAdditional exercises and other related material may be added to these sites over time.Contents:Introduction.
Contractive Models.
Semicontractive Models.
Noncontractive Models.
Models with Restricted Policies.
Appendix A: Notation and Mathematical Conventions.
Appendix B: Contraction Mappings.
Appendix C: Measure Theoretic Issues.
Appendix D: Solutions of Exercises.
References.
Index.
