影印版序
本书采用一种简洁的方式介绍动态规划的理论和方法。作者首先把
动态规划的核心问题表述为一类抽象映射的不动点问题；然后将决定不
动点问题求解难度的主要因素概括为上述抽象映射的两个性质：单调性
和压缩性；接着在假设单调性始终成立的前提下．围绕压缩性是否成立，
顺序讨论了各种典型情况下相应不动点问题的主要性质和求解方法。其
中第2章介绍压缩性成立时的结果．第3章介绍压缩性部分成立时的结
果，第4章介绍压缩性不成立时的结果．最后在第5章介绍了策略受限情
况的一些结果。这些内容涉及不动点的存在性、值迭代方法和策略迭代
方法的收敛性以及多种常用近似方法的误差上界等动态规划的基本
问题。
本书作者是美国麻省理工学院电气工程和计算机科学系的资深教
授，在线性规划、非线性规划、动态规划、网络优化、凸分析与优化等众多
优化领域著有十余部专著或教科书。如同作者其他著作一样．本书在描
述问题、定义概念和证明定理时力求清晰、严谨和完整。尽管本书始终以
不动点问题为讨论对象．但每部分内容都给出了相应的动态规划实例。
结合这些例子．很容易理解所获得的结果和动态规划问题的关系。因此，
对于具有一定数学基础的读者，既可以把本书作为深入了解动态规划理
论的专著．也可以将其作为自学动态规划知识的教材。
动态规划是解决复杂优化问题的一种基本方法。同线性规划、非线
性规划、网络优化等其他优化领域的基本理论相比，应用动态规划方法解
决优化问题的原理相对而言比较简单。但对同样的问题，采用不同的建
模和求解策略，所产生的实际效果可能存在很大差异。因此，采用动态规
划方法解决具体问题时具有很大的灵活性。通过阅读本书，系统掌握动
态规划的核心理论和方法，对于更好地应用动态规划思想和方法解决实
际问题，一定大有裨益。
清华大学自动化系
王书宁教授
201 4年3月1 5日
Preface
This book aims at a unificd 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 analy-
sis focuses on the abstract mapping that underlies dynamic programming
(DP for short) and defines the mathematical character of the associated
problem. Our discussion centers on two fundamental properties that this
mapping may have: monotonicity and (weighted sup-norm) contraction.. It
turns out that the naturc 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 inconsequcntial.
In this book, with some minor exceptions, we will assume that mono-
tonicity holds. Consequently, we organize our treatment around the con-
traction property, and we focus on four main classcs of models:
(a)Contractive models. discussed in Chapter 2,which have the richest
and strongest theory: and are the benchmark against which the the-
ory of other models is compared. Prominent among these models are
discoimted stochastic optimal control problems. The development of
these models is quite thorough and includes the analysis of recent ap-
proximation algorithms for large-scale problems (neuro-dynamic pro-
gramming, reinforcement learning) .
(b)Semicontractive models, discussed in Chapter 3 and parts of Chap-
ter 4. The term “scemicontractive” is used qualitatively here: to refer
to a variety of models where some policies have a regularity/contrac-
tion-like property but others do not. A prominent example is stochas-
tic shortest path problems, where one aims to drive the state of
a Markov chain to a termination state at minimum expected cost.
These models also have a strong theory under certain conditions. of-
ten nearly as strong as those of the contractive models.
(c)Noncontractive models, discussed in Chapter 4, which rely on .just
monotonicity. These models are more complex than the preceding
ones and much of the theory of the contractive models generalizes in
weaker form, if at all. For example, in general the associated Bell-
man equation need not have a unique solution, the value iteration
method may work starting with some functions but not with others.
and the policy iteration method may not work at all. Infinite hori-
zon examples of these models are the classical positive and negative
DP problems. first analvzed by Dubins and Savage, Blackwell, and
Strauch, which are discussed in various sources. Some new semicon-
tractive models are also discussed in this chapter, further bridging
the gap betwccn contractive and noncontractive models.
(d) Restricted policies and Borel space models, which are discussed
in Chapter 5. These models are motivated in part by the complex
measurability questions that arise in mathematically rigorous theories
of stochastic optimal control involving continuous probability spaces.
Within this context, the admissible policies and DP mapping are
restricted to have certain measurability properties, and the analysis
of the preceding chapters requires modifications. Restricted policy
models are also useful when there is a special class of policies with
favorable structure. which is “closed” with respect to the standard DP
operations. in the sense that analysis and algorithms can be confined
within this class.
We do not consider average cost DP problems, whose character bears
a much closer connection to stochastic processes than to total cost prob-
lems.We also do not address specific stochastic characteristics underlying
the problem, such as for example a Markovian structure. Thus our re-
sults apply equally well to Markovian decision problems and to sequential
minimax problems. While this makes our development general and a con-
venient starting point for the further analysis of a variety of different types
of problems，it also ignores some of the interesting characteristics of special
types of DP problems that require an intricate probabilistic analysis.
Let us describe the research content of the book in summary. de-
ferring a more detailed discussion to the end-of-chapter notes. A large
portion of our analysis has been known for a long time, but in a somewhat
fragmentary form. In particular, the contractive theory, first developed by
Denardo [Den67], has been known for the case of the unweighted sup-norm,
but does not cover the important special case of stochastic shortest path
problems where all policies are proper. Chapter 2 transcribes this theory
to the weighted sup-norm contraction case. Moreover, Chapter 2 develops
extcnsions of the theory to approximate DP, and includes material on asyn-
chronous value iteration (based on the author's work [Ber82], [Ber83l], and
asynchronous policy iteration algorithms (based on the author's joint work
with Huizhen (Janey) Yu [BeYlOa], [BeYlOb], [YuBlla]). Most of this
material is relatively new, having been presented in the author's recent
book [Ber12a] and survey paper [Ber12b], with detailed references given
there. The analysis of infinite horizon noncontractive models in Chaptcr 4
was first given in the author's paper [Ber77] , and was also presented in the
book by Bertsekas and Shreve [BeS78], which in addition contains much
of the material on finite horizon problems, restricted policies models, and
Borel space models. These were the starting point and main sources for
our development.
The new research presented in this book is primarily on the semi-
contractive models of Chapter 3 and parts of Chapter 4. Traditionally,
the theory of total cost infinite horizon DP has been bordered by two ex-
tremes: discounted models, which have a contractive nature, and positive
and negative models, which do not have a contractive nature,but rely
on an enhanced monotonicity structure (monotone increase and monotone
decrease models, or in classical DP terms, positive and negative models).
Between these two extremes lies a gray area of problems that are not con-
tractive, and either do not fit into the categories of positive and negative
models. or possess additional structure that is not exploited by the theory
of these models. Included are stochastic shortest path problems. search
problems, linear-quaclratic problems, a host of queueing problems, miilti-
plicative and exponential cost models, and others. Together these problems
represent an important part of the infinite horizon total cost DP landscape.
They possess important theoretical characteristics,not generally available
for positive and negative models,such as the uniqueness of solution of Bell-
man's equation within a subset of interest, and the validity of useful forms
of value and policy iteration algorithms.
Our semicontractive models aim to provide a uniflying abstract DP
structure for problems in this gray area between contractive and noncon-
tractive models. The analysis is motivated in part by stochastic shortest
path problems, where there are two types of policics: proper, which are
the ones that lead to the termination state with probability one from all
starting states, and improper, which are the ones that are not proper.
Proper and improper policies can also be characterized through their Bell-
man equation mapping: for the former this mapping is a contraction, while
for the latter it is not. In our more general semicontractive models, policies
are also characterized in terms of their Bellman equation mapping, through
a notion of regularity, which generalizes the notion of a proper policy and
is related to classical notions of asymptotic stability from control theory.
In our development a policy is regular within a certain set if its cost
function is the unique asymptotically stable equilibrium (fixed point) of
the associated DP mapping within that set. We assume that some policies
are regular while others are not, and impose various assumptions to ensure
that attention can be focused on the regular policies. From an analytical
point of view, this brings to bear the theory of fixed points of monotone
mappings. From the practical point of view, this allows application to a
diverse collection of interesting problems, ranging from stochastic short-
est path problems of various kinds. where the regular policies include the
proper policies, to linear-quadratic problems, where the regular policies
include the stabilizing linear feedback controllers.
The definition of regularity is introduced in Chapter 3, and its theoret-
ical ramifications are explored through extensions of the classical stochastic
shortest path and search problems. In Chapter 4. semicontractive models
are discussed in the presence of additional monotonicity structure, which
brings to bear the properties of positive and negative DP models. With the
aid of this structure, the theory of semicontractive models can be strength-
ened and can be applied to several additional problems, including risk-
sensitive/exponential cost problems.
The book has a theoretical research monograph character,but re-
quires 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 oricntation and context. A few
exercises have been included, either to illustrate the theory with exam-
ples and counterexamples, or to provide applications and extensions of the
theory. Solutions of all the exercises can be founcl in Appendix D, at the
book's internet site
http://www.athenasc.com/abstractdp.html
and at the author's web site
http://web.mit.edu/dimitrib/www/home.html
Additional excrcises and other related material may be added to these sites
over time.
I would like to express my appreciation to a few colleagues for inter-
actions, recent and old. which have helped shape the form of the book. My
collaboration with Steven Shreve on our 1978 book provided the motivation
and the background for the material on models with restricted policies and
associated measurability questions. My collaboration with John Tsitsiklis
on stochastic shortest path problems provided inspiration for the work on
semicontractive models. My collaboration with Janey Yu played an im-
portant role in the book's development, and is refilected in our joint work
on asynchronous policy iteration, on perturbation models. and on risk-
sensitive models. Moreover Janey contributed significantly to the material
on semicontractive models with many insightful suggestions. Finally, I am
thankful to Mengdi Wang, who went through portions of the book with
care, and gave several helpful commcnts.
Dimitri P. Bertsckas, Spring 2013
NOTE ADDED TO THE CHINESE EDITION
The crrata of the original cdition, as pcr- March l. 2014. havc bccn incor-
poratcd in the prcscnt cclition of' the book. The f'ollowing two papcrs havc
a strong conncction to the book. and amplifly on the rangc of applications
of the scmicontractivc moclcls of Chaptcrs 3 ancl 4:
(l) D. P. Bcrtsckas. ::Robust Shortcst Path Planning and Scmicontractivc
Dynamic Programming: Lab. for- Information and Dccision Systcms
Rcport LIDS-P-2915. MIT. Fcb. 2014.
(2) D. P. Bcrtsckas. "Infinitc-Spacc Shortcst Path Problcms and Scmicon-
tractivc Dynamic Programming: Lab. f'or Inf'ormation and Dccision
Systcms Rcport LIDS-P-2916. MIT. Fcb. 2014.
Thcsc papcrs may bc vicwcd as "oii-linc appcndixcsn of the book. Thcy
can bc downloadcd from the book's intcrnct sitc ancl the author's wcb pagc.
