动态规划与最优控制——近似动态规划

序言
这是第II卷的一次重要修订，增加了大量新内容，并对原有内容进行了重新组织。与第三版相比，篇幅增加了逾60%，大部分原有内容被重新组织并/或修订。第II卷现在超过700页，在篇幅上超过了第I卷。这几乎可以被视为一本新书！
近似动态规划已成为第II卷的核心内容，占据全书超过一半的内容（后两章的全部以及第1～3章的大部分内容）。所以，第II卷可被视作我1996年的《神经元动态规划》一书（与JohnTsitsiklis合著）的续作。现在这本书着重关注1996年之后新的研究成果。另一方面，本书保留了作为教科书的体系，一些内容以形象的甚至是不严格的程度来解释，并引用期刊论文或《神经元动态规划》一书参考更数学化的处理。
在扩展与重新组织的过程中，本书的结构变得更加模块化，更适合课堂教学的使用。可在一学期约三分之一至一半时间内讲完的核心内容，包括第1章（除了1.3节、1.4节与特定应用对应的内容），第2章和第6章合在一起自成体系。这些内容集中在折扣问题，可通过第3章和7.1节的随机短路问题的内容进行补充。实际上，这构成了我在麻省理工学院的课堂上讲授的内容的一半（剩下的一半来自第I卷，包括那一卷的第6章，讨论有限阶段近似动态规划问题）。在第5章、7.2节、7.4节中的平均费用问题的内容，正和负动态规划模型的高级内容（7.3节）是后的内容，可由教师根据实际情况选用。
因为本书的重点发生了转移，我将更多的重心放在新近的研究成果上，包括近似动态规划和基于仿真的方法，还包括异步迭代方法，这一方法以仿真为中心视角，因为仿真是天然异步的。许多这些内容源自从前一版发行以来六年时间里我自己以及合作的研究内容。其中一些重点，按照在文中出现的顺序，如下：
(1) 一般的折扣动态规划问题的计算方法（2.5节和2.6节），包括2.5节中近似涉及的误差界，2.6.2节和2.6.3节中的异步乐观策略迭代方法，以及在博弈与极小极大问题，约束策略迭代和Q-学习中的应用。
(2) 涉及不合适策略随机短路问题的策略迭代方法（包括异步乐观的版本）（3.4节）。
(3) 在6.3节～6.6 节中的多种基于仿真的近似值迭代和近似策略迭代方法的大量新增内容。
(4) 乐观策略迭代新的可靠的Q-学习算法（2.6.3节和6.6.2节）。
(5) 多步方法的新的仿真技术，比如几何采样和自由形式采样（6.4.1节和7.3.3节）。
(6) 7.3节中蒙特卡罗线性代数的大量新增内容（主要是大规模线性方程的基于仿真和近似解），这部分内容扩展了近似策略评价的动态规划方法。
(1)～(5) 中的许多研究内容基于我与Janey(Huizhen)Yu的工作，而(6)中的大部分研究是基于我与JaneyYu和MengdiWang的工作。我与Janey和Mengdi的合作对本书有重要影响，在此深表感谢。我们的一些工作只以总结形式涉及，并稍作修改以适应本书的体系与目的；自然地，其表述上的不足应由我承担全部责任。请读者参阅我们的合作以及各自的学术论文，那里更全面地描述了我们的研究，包括本书不能涵盖的内容。
我向在近似动态规划的研究中合作的同事一并致谢，他们以不同形式为这本书做出了贡献，特别是VivekBorkar、AngeliaNedic和BenVanRoy。特别感谢JohnTsitsiklis，我与他在动态规划与异步算法上有着逾三十年的交流与合作。我还想感谢来自许多同事的有益的交流，包括VivekFarias、EugeneFeinberg、WarrenPowell、MartinPuterman、UrielRothblum和BrunoScherrer。后，我想感谢近十年来我动态规划课堂上的诸多学生，他们耐心地使用尚在建设中的教材，并通过涉及广泛应用领域的研究课题贡献了他们的想法和经验。

Dimitri P. Bertsekas    
2012 年春   

本书系统性介绍动态规划，特别是近似动态规划，包括折扣问题的理论与计算方法、随机*短路问题、无折扣问题、平均费用问题、折扣与无折扣问题的近似动态规划等。

本书系统性介绍动态规划，特别是近似动态规划，包括折扣问题的理论与计算方法、随机*短路问题、无折扣问题、平均费用问题、折扣与无折扣问题的近似动态规划等。

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

第1章  折扣问题——理论 1
1.1  总费用小化——介绍 1
1.1.1  有限阶段动态规划算法 3
1.1.2  符号简写与单调性 4
1.1.3  无穷阶段结果的预览 6
1.1.4  随机的和依赖历史的策略 7
1.2  折扣问题——各阶段费用有界 9
1.3  调度与多柄老虎机问题 15
1.3.1  项目的指标 16
1.3.2  项目逐个退出策略 17
1.4  折扣连续时间问题 23
1.5  压缩映射的作用 32
1.5.1  极大模压缩 33
1.5.2  折扣问题——单阶段费用无界 38
1.6  折扣动态规划的一般形式 40
1.6.1  压缩与单调性的基本结论 44
1.6.2  折扣动态博弈 49
1.7  注释、参考文献及习题 50
习题 51
第2章  折扣问题——计算方法 57
2.1  马尔可夫决策问题 57
2.2  值迭代 59
2.2.1  值迭代的单调误差界 59
2.2.2  值迭代的变形 65
2.2.3  Q-学习 67
2.3  策略迭代 69
2.3.1  针对费用的策略迭代 69
2.3.2  Q-因子的策略迭代 72
2.3.3  乐观策略迭代 73
2.3.4  有限前瞻策略和滚动 75
2.4  线性规划方法 79
2.5  一般折扣问题的方法 81
2.5.1  采用近似的有限前瞻策略 83
2.5.2  推广的值迭代 85
2.5.3  近似值迭代 86
2.5.4  推广的策略迭代 87
2.5.5  推广的乐观策略迭代 90
2.5.6  近似策略迭代 94
2.5.7  数学规划 97
2.6  异步方法 98
2.6.1  异步值迭代 98
2.6.2  异步策略迭代 102
2.6.3  具有均一不动点的策略迭代 105
2.7  注释、资源和习题 110
习题 112
第3章  随机短路问题 122
3.1  问题建模 122
3.2  主要结论 124
3.3  基本压缩性质 130
3.4  值迭代 131
3.4.1  有限步终止的条件 131
3.4.2  异步值迭代 133
3.5  策略迭代 134
3.5.1  乐观策略迭代 135
3.5.2  近似策略迭代 136
3.5.3  具有不合适策略的策略迭代 137
3.5.4  具有均一不动点的异步策略迭代 140
3.6  可数状态问题 143
3.7  注释、资源和习题 145
习题 146
第4章  无折扣问题 151
4.1  每阶段的费用无界 151
4.1.1  主要结论 152
4.1.2  值迭代 158
4.1.3  其他计算方法 163
4.2  线性系统和二次费用 163
4.3  库存控制 165
4.4  停止 167
4.5  博弈策略 171
4.6  连续时间问题——排队的控制 177
4.7  非平稳和周期性问题 183
4.8  注释、资源和习题 187
习题 188
第5章  每阶段平均费用问题 196
5.1  有限空间平均费用模型 196
5.1.1  与折扣费用问题的关系 198
5.1.2  Blackwell 策略 203
5.1.3  性条件 210
5.2  所有初始状态的平均费用相等的条件 213
5.3  值迭代 217
5.3.1  单链值迭代 219
5.3.2  多链值迭代 231
5.4  策略迭代 236
5.4.1  单链策略迭代 236
5.4.2  多链策略迭代 240
5.5  线性规划 244
5.6  无穷空间平均费用模型 248
5.6.1  性的充分条件 254
5.6.2  有限状态空间和无限控制空间 255
5.6.3  可数状态——消失的折扣方法 262
5.6.4  可数状态——压缩方法 264
5.6.5  具有二次费用的线性系统 267
5.7  注释、资源和习题 268
习题 270
第6章  近似动态规划：折扣模型 279
6.1  基于仿真的费用近似的一般性问题 280
6.1.1  近似结构 280
6.1.2  基于仿真的近似策略迭代 284
6.1.3  直接和间接近似 288
6.1.4  蒙特卡罗仿真 289
6.1.5  简化 295
6.2  直接策略评价——梯度法 298
6.3  策略评价的投影方程方法 302
6.3.1  投影贝尔曼方程 303
6.3.2  投影方程的矩阵形式 305
6.3.3  基于仿真的估计方法 308
6.3.4  LSTD、LSPE 和TD(0) 方法 310
6.3.5  乐观版本 312
6.3.6  多步基于仿真的方法 313
6.3.7  提要 320
6.4  策略迭代问题 322
6.4.1  基于几何采样的搜索增强 324
6.4.2  基于离线策略方法的搜索增强 332
6.4.3  策略振荡——震颤 334
6.5  聚集方法 339
6.5.1  基于聚集问题的费用近似 344
6.5.2  通过增广问题的费用近似 346
6.5.3  多步聚集 350
6.5.4  异步分布聚集 351
6.6  Q-学习 353
6.6.1  Q-学习：随机值迭代算法 353
6.6.2  Q-学习和策略迭代 355
6.6.3  Q-因子近似和投影方程 356
6.6.4  停止问题的Q-学习 358
6.6.5  Q-学习和聚集 362
6.6.6  有限阶段Q-学习 364
6.7  注释、资源和习题 365
习题 370
第7章  近似动态规划：无折扣模型及推广 380
7.1  随机短路问题 380
7.2  平均费用问题 384
7.2.1  近似策略评价 384
7.2.2  近似策略迭代 391
7.2.3  平均费用问题的Q-学习 392
7.3  一般问题和蒙特卡罗线性代数 395
7.3.1  投影方程 401
7.3.2  矩阵逆合迭代方法 406
7.3.3  多步方法 412
7.3.4  停止的Q-学习的推广 418
7.3.5  方程误差方法 420
7.3.6  倾斜投影 424
7.3.7  推广聚集 426
7.3.8  奇异线性系统的确定性方法 428
7.3.9  奇异线性系统的随机方法 436
7.4  在策略空间的近似 445
7.4.1  梯度公式 445
7.4.2  通过仿真计算梯度 446
7.4.3  梯度评价的关键特征 448
7.4.4  策略和值空间的近似 450
7.5  注释、资源和习题 450
习题 453
附录A  动态规划中的测度论问题 460
A.1  两阶段例子 460
A.2  可测问题的解决方法 463
参考文献 470

本书系统性介绍动态规划，特别是近似动态规划，包括折扣问题的理论与计算方法、随机*短路问题、无折扣问题、平均费用问题、折扣与无折扣问题的近似动态规划等。

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