贾庆山，清华大学自动化系副教授，2002年和2006年分别于清华大学自动化系获工学学士、博士学位，同年留校任教。2006、2010、2013年分别任美国哈佛大学、香港科技大学、美国麻省理工学院访问学者。作为负责人先后承担国家自然科学基金青年基金、面上项目、优秀青年基金，参加国家自然科学基金重点项目、重大研究计划培育项目和集成项目。承担多个国际合作项目。任IEEE Transactions on Automation Science and Engineering、Discrete Event Dynamic Systems - Theory and Applications等国际期刊副编辑，IIE Transactions领域编辑。发表国际期刊论文和国际会议论文逾八十篇，合著英文专著一部，合编英文专著一部，合译教材一本。

Dimitri P. Bertsekas是美国麻省理工学院教授、美国工程院院士，在国际优化与控制界享有盛誉。他编写的系列教材被麻省理工学院、斯坦福大学、伊利诺伊大学香槟分校等多所世界知名大学选用。《动态规划与最优控制 ——近似动态规划》共两卷，本书为第 I卷，主要介绍动态规划与最优控制的基本方法，包括最短路径问题、精确和不精确状态信息、有限和无限阶段问题等经典模型，以及近似动态规划等理论方法。本书深入浅出，非常适合控制、优化、电子工程、计算机、工业工程等专业的研究生学习，也适合作为高年级本科生和本领域的研究者的参考书。《动态规划与最优控制 ——近似动态规划》第 II卷中译本已于 2021年由清华大学出版社出版。希望这上下两卷书对本领域的教师、学生、研究人员能有所益处。

特此说明：为了读者阅读方便 (例如参照原版书)，本书中公式、符号、参考文献等采用原版书的格式。

贾庆山李岩

2024年 2月于北京

关于作者

Dimitri P. Bertsekas曾在希腊国立雅典技术大学学习机械与电机工程，获得麻省理工学院系统科学博士学位。曾先后在斯坦福大学工程与经济系统系和伊利诺伊大学香槟分校的电机工程系任教。自 1979年以来，他一直在麻省理工学院电机工程与计算机科学系任教，现任麦卡菲工程教授。

其研究涉及多个领域，包括优化、控制、大规模计算和数据通信网络，并与其教学和著书工作联系紧密。他撰写了众多论文和十四本著作，其中数本著作在麻省理工学院被用作教材。他与动态规划之缘始自博士论文的研究，并通过学术论文、多本教材和学术专著一直延续至今。

Bertsekas教授因其（与 John Tsitsiklis合著的）著作《神经动态规划》在 1997年荣获 INFORMS授予的运筹学与计算机科学交叉领域的杰出研究成果奖， 2000年希腊运筹学国家奖， 2001年美国控制会议 John R. Ragazzini教育奖。2001年，他当选美国工程院院士。

序言

这套书是基于我在斯坦福大学、伊利诺伊大学香槟分校和麻省理工学院逾二十年时间里给一年级研究生讲授“动态规划和最优控制”课程的基础上完成的。这门课程通常由工程学、运筹学、经济学和应用数学专业的学生选修。相应地，这套书的主要目的是面向广大读者统一介绍这个领域。特别地，具有连续性的问题，比如在现代控制理论中很普遍的随机控制问题，与具有离散特点的问题将被一并讨论，比如在运筹学中很普遍的马尔可夫决策问题。进一步，源自多个领域的实际应用和例子也将被讨论。

这本书可被视作由本人所著、 Prentice-Hall出版社于 1987年出版的《动态规划：确定与随机的模型》一书的扩充以及从教育学角度改进的版本。本书中增加了许多关于确定性与随机性最短路径问题的新内容，新增一章讨论从动态规划视角讨论的连续时间最优控制问题和庞特里亚金最大值原理。同时也增加了动态规划所用的基于仿真的近似技术的相当多的内容。这些技术，通常被称作 “神经动态规划 ”或者 “强化学习 ”，代表了将动态规划实际应用于具有大维度和缺乏精确数学模型描述的复杂问题时的一项突破性进展。其他内容也都加以扩充，全面修订，并更新。

然而，增加这些新内容之后，这本书的页数也大幅增加，以至于需要分成两卷：一卷讨论有限阶段的问题，另一卷讨论无限阶段的问题。这一划分方法不仅在页数上是一种自然的划分，而且在形式和内容上也是自然的。第 I卷更侧重建模，第 II卷更侧重数学分析和计算。在第 I卷中增加了最后一章介绍无限阶段问题，旨在让第 I卷可供教师在一门课程中主要侧重建模、概念和有限阶段问题，同时涵盖适度的无限阶段问题。

本书的许多内容是相互独立的。比如，第 I卷的第 2章讨论最短路径问题，可被跳过而不失上下文的连贯性；第 I卷的第 3章讨论连续时间最优控制问题，也可类似处理。所以，本书可用于讲授几种不同类型的课程。

(a)两学期的课程涵盖两卷。

(b)一学期的课程主要讲授第 I卷中的有限阶段问题。

(c)一学期的课程主要讲授涵盖第 I卷第 1，4，5，6章和第 II卷第 1，2，4章内容的随机最优控制问题。

(d)一学期的课程涵盖第 I卷第 1章、第 2～ 6章内容的约一半，第 II卷第 1，2，4章内容的 70%。这是在麻省理工学院通常讲授的课程 I。

(e)一学期的工学课程涵盖第 I卷前三章以及第 4～ 6章的一部分内容。

(f)一学期的更侧重数学的课程涵盖第 II卷的无限阶段问题。

本书所需的数学先修内容包括高等代数、概率论导论和矩阵向量代数。附录中总结了这些内容。动态系统理论、控制、优化或者运筹学的相关知识将有助于读者，但以笔者的经验，书中的相关内容是自我完备的。

书中包含了大量习题。认真的读者将通过这些习题深深受益。这些习题的答案已汇编成册，

动态规划与最优控制——近似动态规划 (第 I卷)

教师可直接联系作者获得。这本参考答案得益于多人长时间的贡献，特别是 Steven Shreve、Eric Loiederman、Lakis Polymenakos和 Cynara Wu，在此特别致谢。

动态规划是一项概念简单的技术，可以用基础的分析方法解释得足够清楚。不过对于一般的动态规划的严格的数学分析需要使用复杂的测度论和概率论。作者选择避免使用复杂的数学，尽量让叙述通俗易懂，仅当所涉及的概率空间是可数时才进行严格的讨论。对该领域的严格的数学讨论在笔者的另一本与 Steven Shreve合著由 Academic Press于 1978年出版的学术专著《随机最优控制：离散时间的情形》中进行了讨论。那本学术专著与本书的内容互补，为本书叙述不够严谨的内容提供了坚实的基础。

最后，我要感谢许多为本书做出贡献的个人和集体。我对这一领域的理解通过与 Steven Shreve合著的 1978年的专著变得更加深刻。我与 John Tsitsiklis在随机最短路径和近似动态规划的合作与交流卓有成效。 Michael Caraanis、Emmanuel Fernandez-Gaucherand、Pierre Humblet、Lennart Ljung和 John Tsitsiklis曾使用本书的多种版本授课，并贡献了若干关键性的意见以及习题。一些同事提供了有价值的观点和信息，特别是， David Castanon、Eugene Feinberg和 Krishna Pattipati。美国国家科学基金会提供了研究经费的支持。 Prentice-Hall慷慨地允许我使用 1987年所著书的内容。教学工作以及与麻省理工学院学生的交互让我保持了对这一领域的兴趣与快乐。

Dimitri P. Bertsekas

1995年春

第 1章动态规划算法 1

11概述 1

12基本问题 8

13算法12

14状态增广和其他重新建模24

15一些数学问题 29

16动态规划和极小化极大控制 32

17注释、参考文献和习题 35

第 2章确定性系统和最短路径问题 44

21有限状态系统和最短路径44

22一些最短路径的应用 47

221关键路径分析 47

222隐马尔可夫模型和瓦特比算法48

23最短路径算法 53

231标签纠正方法 55

232标签纠正变形-A＊算法 60

233分支定界61

234约束与多目标问题 63

24注释、参考文献和习题 67

第 3章确定性连续时间最优控制 72

31连续时间最优控制72

32哈密尔顿-雅可比-贝尔曼方程 74

33庞特里亚金最小值原理 79

331使用 HJB方程的非正式推导 79

332一种基于变分思想的推导 86

333离散时间问题的最小值原理 89

34最小值原理推广 90

341固定的末端状态91

342自由初始状态 93

343自由终止时间 94

344时变系统与费用97

动态规划与最优控制——近似动态规划 (第 I卷)

345奇异问题97

35注释、参考文献和习题 99

第 4章具有精确状态信息的问题 103

41线性系统和二次型费用 103

42库存控制 112

43动态资本分析 119

44最优停止问题 122

45调度与交换的理由 130

46不确定性的集合隶属度描述 133

461集合隶属度估计 133

462具有未知且有界扰动的控制 138

47注释、参考文献和习题 140

第 5章不精确状态信息的问题 152

51化简为精确信息的情形 152

52线性系统和二次型费用 160

53线性系统的最小方差控制 165

54充分统计量 176

541条件状态分布 177

542有限状态系统 180

55注释、参考文献和习题 190

第 6章近似动态规划 198

61确定性等价和自适应控制 199

611谨慎、探测和对偶控制 203

612两阶段控制和识别能力 204

613确定性等价控制和可辨识性 205

614自调节调节器 209

62开环反馈控制 210

63有限前瞻策略 213

631有限前瞻策略的性能界 214

632有限前瞻中的计算问题 217

633问题近似——强化分解 219

634集结 223

635后续费用的参数化近似 227

64滚动算法 234

641离散确定性问题 239

642由仿真评价的 Q-因子 251

目录 IX

643 Q-因子近似 253

65模型预测控制及相关方法 255

651滚动时段近似 255

652模型预测控制中的稳定性问题 257

653结构受限的策略 262

66近似动态规划中的额外主题 266

661离散化 266

662其他近似方法 268

67注释、参考文献和习题 269

第 7章无限阶段问题介绍 280

71概览 280

72随机最短路径问题 282

73折扣问题 290

74每阶段平均费用问题 293

75半马尔可夫问题 303

76注释、参考文献和习题 310

附录 A数学知识复习 320

A1集合 320

A2欧氏空间 321

A3矩阵 321

A4分析 324

A5凸集和凸函数 325

附录 B优化理论 327

B1最优解 327

B2最优性条件 328

B3二次型最小化 329

附录 C概率论 330

C1概率空间 330

C2随机变量 330

C3条件概率 331

附录 D关于有限状态马尔可夫链 333

D1平稳马尔可夫链 333

D2状态分类 334

D3极限概率 334

动态规划与最优控制——近似动态规划 (第 I卷)

D4首达时间 335

附录 E卡尔曼滤波 336

E1最小二乘估计 336

E2线性最小二乘估计 337

E3状态估计——卡尔曼滤波器 342

E4稳定性方面 346

E5高斯-马尔可夫估计器 347

E6确定性最小二乘估计 349

附录 F随机线性系统模型 351

F1具有随机输入的线性系统 351

F2具有有理数谱的过程 352

F3 ARMAX模型 353

附录 G不确定性下的决策问题建模 354

G1不确定性下的决策问题 354

G2期望效用理论和风险 357

G3随机最优控制问题 365

参考文献 369