强化学习与最优控制

本书的目的是考虑大型且具有挑战性的多阶段决策问题，这些问题原则上可以通过动态规划和最优控制来解决，但它们的精确解决方案在计算上是难以处理的。本书讨论依赖于近似的解决方法，以产生具有足够性能的次优策略。这些方法统称为增强学习，也可以叫做近似动态规划和神经动态规划等。 本书的主题产生于最优控制和人工智能思想的相互作用。本书的目的之一是探索这两个领域之间的共同边界，并架设一座具有任一领域背景的专业人士都可以访问的桥梁。

李宇超，瑞典皇家理工学院决策与控制专业博士在读。博士期间研究课题为强化学习，最优控制，以及相关理论在智能交通领域的应用。他于2015年在哈尔滨工业大学机械制造及其自动化专业获得本科学位，并在1年后从现就读学院的机电一体化专业获得硕士学位。

转而投身于现代计算机的怀抱，让我们放弃所有分析工具。（Turning to the succor of modern computing machines, let us renounce all analytic tools.）

（理查德·贝尔曼[Bel57]）

从目的论的角度来看，任何特定方程组的特定数值解都远不如理解的性质重要。（From a teleological point of view the particular numerical solution of any particular set of equations is of far less importance than the understanding of the nature of the solution.）

（理查德·贝尔曼[Bel57]）

在本书中，我们考虑大规模且具有挑战性的多阶段决策问题。原则上，该类问题可以通过动态规划（dynamic programming，DP）来求解。但是，对于许多实际问题以该方法进行数值求解是难以实现的。本书探讨的求解方法通过采用相关的近似，能够给出满足性能要求的次优策略。此类方法有几个不同的但本质上等价的名称：强化学习（reinforcement learning）、近似动态规划（approximate dynamic programming）和神经元动态规划（neuro-dynamic programming）。在本书中，我们将使用其最通俗的名称：强化学习。

我们所讲的学科从最优控制和人工智能这两个领域的思想碰撞中获益良多。本书的目的之一便是探讨这两个领域的共同边界，从而为具有其中任一领域背景的研究者提供通向另一领域的桥梁。另外一个目的则是挑选出许多在实践中证明有效的且具有坚实的理论与逻辑基础的方法，并将它们有组织地整理起来。鉴于当前相关前沿文献中存在着诸多相左的思路和观念，本书归纳整理的体系可能有助于研究人员和实践者在宛如迷宫的前沿文献中找到出路。

基于动态规划的次优控制方法可以分为两类。第一类是值空间近似（approximation in value space），即通过某种方式采用其他的函数来近似最优展望费用函数。与值空间近似相对的主要替代方法是策略空间近似（approximation in policy space），即我们将注意力集中在某些特定形式的策略上，通常是某种形式的参数族，然后通过优化方式在其中选取策略。某些方案会将这两种近似结合起来，旨在充分利用两者的优势。通常值空间近似与作为动态规划核心思想的值迭代和策略迭代的联系更为紧密，而策略空间近似则主要依赖于类梯度下降的更广泛适用的优化机制。

尽管我们对策略空间的近似给出了大量的讲解，本书的大部分内容还是集中于值空间近似。此类方法通过对有限阶段的费用以及未来最优费用的近似之和进行优化，从而得到每个状态对应的控制。未来最优费用的近似是以将来可能所处的状态为自变量的函数，通常将其记为。该函数可以通过多种不同的方法计算得到，其中可能涉及仿真和/或某种给定的或单独获得的启发式/次优策略。对于仿真的运用使得一些算法在没有数学模型时同样得以实现，而这也将动态规划推广到其传统适用范围之外。

本书有选择地介绍四种获取函数的方法。

（a）问题近似（problem approximation）：此类方法中的是与原问题相关的但相对简单问题的最优费用函数，并且该问题可以通过精确动态规划求解。我们会对此类方法中的确定性等价和强制解耦方法给出一些讲解。

（b）策略前展与模型预测控制（rollout and model predictive control）：此类方法中的? J 是某个已知启发式策略的费用函数。一般求解策略前展所需的费用函数值是通过仿真计算得到的。尽管此类方法可用于求解随机问题，但其依赖于仿真的特征使它们更适用于确定性问题，其中就包括了某些启发式解法已知的、具有挑战性的组合优化问题。策略前展还可以与自适应采样和蒙特卡洛树搜索相结合，并且所得方案已成功应用于西洋双陆棋、围棋、国际象棋等游戏场景中。

模型预测控制最初是为求解涉及目标状态的连续空间的最优控制问题而开发的。譬如经典控制问题中的原点即可被视为目标状态。我们可以将该方法看作一种基于次优优化的特殊形式的策略前展，其控制目标是抵达特定的状态。

（c）参数化费用近似（parametric cost approximation）：此类方法中的? J 是从包含神经网络在内的参数化的函数族中选出的，而其中的参数是通过运用状态-费用的样本对以及某种增量形式的最小二乘/回归算法“优化”或“训练”得到的。这一部分中我们将对近似策略迭代及其多种变体给出一些讲解，其中就包括了多种执行-批评方法。这些方法中涉及的策略评价通常是通过基于仿真的训练方法来实现的，而策略改进则可能依赖于策略空间的近似。

（d）聚集（aggregation）：此类方法中的? J 是与原问题相关的某一类特定问题的最优费用。这就是所谓的聚集问题。与原问题相比，该问题涉及的状态数目更少。我们可以通过多种不同的方式构造聚集问题，并且可以通过精确动态规划进行求解。由此得到的最优费用函数就可以作为并用于有限阶段的优化方法中。在涉及神经网络或基于特征的线性架构的参数化近似方案中，聚集还可以用于改进局部的近似效果。

本书采用了循序渐进的阐述方式，从四个不同的方向展开。

（a）从精确动态规划到近似动态规划（from exact DP to approximate DP）：我们首先讨论精确动态规划算法，讨论实现这些方法时可能存在的难点，并在此基础上介绍相应的近似方法。

（b）从有限阶段到无穷阶段问题（from finite horizon to infinite horizon problems）：在第1~3章，我们介绍相对直观且数学上更为简单有限阶段的精确和近似动态规划算法。对于无穷阶段问题的解法则在第4~6 章给出。

（c）从确定性到随机模型（from deterministic to stochastic models）：我们通常分开介绍确定性和随机问题，这是由于确定性问题更为简单，且对于书中的一些方法而言，其具有某些可以利用的特定优势。

（d）从基于模型的到无模型实现方法（from model-based to model-free implementations）：一直到20 世纪90 年代初之前，经典动态规划算法都是求解相应问题的唯一实现形式。与之相比，强化学习具有显著的潜在优势：它们可以通过使用仿真器/计算机模型而非数学模型来实现。本书首先讨论基于模型的实现方式，然后从中找出通过适当修改就可以利用仿真器的方案。

在第1 章之后，每一类新方法都可以被视为之前讲解方法的更复杂或更一般的版本。此外，我们还会通过示例来说明其中的一些方法，从而有助于理解它们的适用范围。但读者也可以有选择地跳过这些例子，而不会影响整体的连贯性。

本书的数学风格与笔者的动态规划书籍[Ber12a]、[Ber17] 和[Ber18a]，以及笔者与Tsitsiklis 合著并发表于1996 年的神经元动态规划（neuro-dyanmic programming，NDP）研究专著[BT96] 有所不同。尽管针对有限阶段和无穷阶段动态规划理论和相应的基本近似方法，我们给出了严谨（但简短）的数学说明，但我们更多地依赖直观的解释，而较少地依赖基于证明的洞见。此外，本书要求的数学基础相当有限：微积分、矩阵-向量代数的最基本应用，以及基本概率（涉及大数定律和随机收敛的复杂数学论证被直观解释所取代）。

尽管采用了一种更直观而不完全以证明为导向的阐述风格，我们仍然遵循了一些基本原则。其中最重要的原则是在使用自然语言时保持严谨。原因在于，由于省去了完整的数学论证和证明，精确的语言对于保持逻辑一致的阐述至关重要。我们尤其力求明确地定义术语，并避免使用多个实质上意义相同的术语。此外，在条件允许的情况下，我们尽量提供足够的解释或直观说明，以便数学家能够相信相关论述，甚至根据提供的思路来构建出书中并未给出的严谨证明。

值得注意的是，尽管我们介绍的多种方法在实践中通常能取得成功，但其性能表现并不扎实。这反映了该领域当前的技术水平：没有任何方法可以保证适用于所有问题，甚至大多数问题，但对于给定问题，文献中有足够多的方法可供尝试，并且最终成功的机会也不算小1。为了帮助读者选取合理的方法并尽快解决问题，我们首先强调的是培养对每种方法内部工作原理的直观理解。然而，了解该领域的分析原理以及核心计算方法背后的机制仍然很重要。引用来自神经元动态规划专著[BT96]中前言的一句话：“我们能够从文献里令人眼花缭乱的猜测性建议和声明中辨别出有前途的或扎实的算法，主要靠的是理解神经元动态规划方法的数学结构。”

另一句来自《纽约时报》文章[Str18] 的陈述，与DeepMind 引人注目的AlphaZero 国际象棋程序有关，同样值得引用：“然而，关于机器学习令人沮丧的一点是，这些算法无法阐述它们在思考什么。我们不知道它们为什么有效，所以我们不知道它们是否值得信赖。AlphaZero 似乎已经发现了关于国际象棋的一些重要原则，但它还不能与我们分享这种理解，至少目前还不能。作为人类，我们想要的不仅仅是答案，我们还想要洞察力。这将成为我们今后与计算机互动时紧张的源头之一。”2对此，我们可以补充说，人类的洞察力只能在某种人类思维的结构中获得，而数学推理与算法模型似乎是实现这一目标的最合适的结构。

我想对为这本书做出直接或间接贡献的许多学生和同事表示感谢。特别要感谢过去25 年来我在这个领域中的主要合作者，尤其是John Tsitsiklis、Janey (Huizhen) Yu 和Mengdi Wang。此外，多年来与Ben Van Roy 分享见解对于塑造我对本领域的理解非常重要。与Ben Recht 的关于策略梯度方法的交流也对我很有帮助。在麻省理工学院（Massachusetts Institute of Technology，MIT）我所教授的动态规划课程中，学生们所做的项目给我带来不少灵感，其中许多都间接地反映在了本书中。我要对许多审阅本书部分内容的读者表示感谢。在这方面，我要特别提到李宇超，他提出了很多有益的意见；还有Thomas Stahlbuhk，他非常仔细地阅读了整本书，并提出了许多有洞察力的建议。

本书成型于2019 年1 月，彼时我在亚利桑那州立大学（Arizona State University，ASU）教授了一门为期两个月的相关课程。该课程的授课视频和课件可以从我的网站（http://web.mit.edu/dimitrib/www/RLbook.html）获取，它们为本书内容提供了有益的补充。在授课期间，亚利桑那州立大学热情友好和激发创造力的环境极大地提高了我的工作效率。为此，我非常感谢Stephanie Gil 以及其他来自该校的同事，包括Heni Ben Amor、Esma Gel、Subbarao (Rao) Kambhampati、Angelia Nedic、Giulia Pedrielli、Jennie Si 和Petr Sulc。此外，Stephanie 与她的学生Sushmita Bhattacharya 和Thomas Wheeler 一起，与我合作进行研究并实现了多种方法，对书中的许多见地有所贡献，并且测试了多种算法的变体。

Dimitri P. Bertsekas

2019 年6 月

1 虽然强化学习是基于动态规划的数学原理，但它也依赖于多个相互影响的近似，并且这些近似在实践中的效果很难预测和量化。我们希望通过进一步的理论和应用研究，该领域的相关理论能得到改善和澄清。然而，可以说，在目前的形式下，强化学习是一个爆炸性发展的领域，复杂、不纯净，并且有些混乱。强化学习当前的状况并非个例。在其他一些重要的优化领域中，类似的状况也存在过相当一段时间

2 这篇序言开头引用的两段贝尔曼在1957 年的表述也表达了这种紧张关系。尽管其中的第一段引言引人注目且被广泛引用，但不可否认的是，它有点脱离了上下文（在他关于实际应用的工作中，贝尔曼一直保持着数学分析学者的本色）。贝尔曼引人入胜的自传[Bel84] 中包含了关于动态规划（以及近似动态规划）起源的许多信息；他的合作者Dreyfus[Dre02] 汇编了这部自传中的一些选段。贝尔曼表示：“为了能够取得进展，我们必须考虑近似技术，尤其是数值算法。最后，在花费了大量时间和精力来分析许多种简单模型却多徒劳无功后，我准备面对新的挑战，即如何将动态规划作为获取数值问题的数值答案的有效工具。”接着，他将自己对数值动态规划工作的动机归因于（在当时还很原始的）数字计算机的出现，并将其称为“巫师的学徒”。

第 1 章 精确动态规划 1

1.1 确定性动态规划 1

1.1.1 确定性问题. 1

1.1.2 动态规划算法 5

1.1.3 值空间的近似 9

1.2 随机动态规划 10

1.3 例子、变形和简化. 13

1.3.1 确定性最短路径问题 14

1.3.2 确定性离散优化问题 15

1.3.3 含终止状态的问题 18

1.3.4 预报 20

1.3.5 含不可控状态组分的问题 21

1.3.6 不完整的状态信息和置信状态 25

1.3.7 线性二次型最优控制 28

1.3.8 含未知参数的系统——自适应控制 30

1.4 强化学习与最优控制——一些术语 32

1.5 注释和资源 34

第 2 章 值空间的近似 36

2.1 强化学习中的近似方法. 36

2.1.1 值空间近似的一般问题 39

2.1.2 离线与在线方法 40

2.1.3 针对前瞻最小化的基于模型的简化 40

2.1.4 无模型的离线 Q 因子近似 41

2.1.5 基于值空间近似的策略空间近似 43

2.1.6 值空间的近似何时有效 44

2.2 多步前瞻. 45

2.2.1 多步前瞻与滚动时域 46

2.2.2 多步前瞻与确定性问题 47

2.3 问题近似. 48

2.3.1 强制解耦 49

2.3.2 随机问题中的近似——确定性等价控制 . 54

2.4 策略前展与策略改进原则. 58

2.4.1 针对确定性离散优化问题的在线策略前展 59

2.4.2 随机策略前展与蒙特卡洛树搜索 68

2.4.3 基于专家的策略前展 75

2.5 针对确定性无穷空间问题的在线策略前展——优化类启发式方法 76

2.5.1 模型预测控制 77

2.5.2 目标管道与约束可控性条件 82

2.5.3 模型预测控制的变形 85

2.6 注释与资源 86

第 3 章 参数化近似 90

3.1 近似架构. 90

3.1.1 基于特征的线性与非线性参数架构 90

3.1.2 训练线性与非线性架构 95

3.1.3 增量梯度与牛顿法 96

3.2 神经网络. 107

3.2.1 训练神经网络. 109

3.2.2 多层与深度神经网络 112

3.3 连续动态规划近似 115

3.4 Q 因子参数化近似 116

3.5 基于分类的策略空间参数化近似 119

3.6 注释与资源 122

第 4 章 无穷阶段动态规划 124

4.1 无穷阶段问题概论 124

4.2 随机最短路径问题 126

4.3 折扣问题. 133

4.4 半马尔可夫折扣问题 137

4.5 异步分布式值迭代 141

4.6 策略迭代. 144

4.6.1 精确策略迭代. 144

4.6.2 乐观与多步前瞻策略迭代 148

4.6.3 针对 Q 因子的策略迭代 149

4.7 注释和资源 151

4.8 附录：数学分析. 152

4.8.1 随机最短路径问题的相关证明 152

4.8.2 折扣问题的相关证明 157

4.8.3 精确与乐观策略迭代的收敛性 157

第 5 章 无穷阶段强化学习 160

5.1 值空间近似——性能界 160

5.1.1 有限前瞻. 162

5.1.2 策略前展. 164

5.1.3 近似策略迭代. 167

5.2 拟合值迭代 169

5.3 采用参数化近似的基于仿真的策略迭代 173

5.3.1 自主学习与执行–批评方法 173

5.3.2 一种基于模型的变体 174

5.3.3 一种无模型的变体. 176

5.3.4 实施参数化策略迭代的挑战. 177

5.3.5 近似策略迭代的收敛问题——振荡 180

5.4 Q 学习 183

5.5 附加方法——时序差分 185

5.6 精确与近似线性规划 194

5.7 策略空间近似. 196

5.7.1 通过费用优化执行训练——策略梯度、交叉熵以及随机搜索方法 199

5.7.2 基于专家的监督学习 207

5.7.3 近似策略迭代、策略前展与策略空间近似. 208

5.8 注释和资源 212

5.9 附录：数学分析. 216

5.9.1 多步前瞻的性能界. 216

5.9.2 策略前展的性能界. 218

5.9.3 近似策略迭代的性能界. 220

第 6 章 聚集 223

6.1 包含代表状态的聚集 223

6.1.1 连续控制空间离散化 227

6.1.2 连续状态空间——部分可观察马尔可夫决策问题的离散化 228

6.2 包含代表特征的聚集 230

6.2.1 硬聚集与误差界 232

6.2.2 采用特征的聚集 234

6.3 求解聚集问题的方法 237

6.3.1 基于仿真的策略迭代 238

6.3.2 基于仿真的值迭代. 240

6.4 包含神经网络的基于特征的聚集 241

6.5 偏心聚集. 242

6.6 注释和资源 244

6.7 附录：数学分析. 247

参考文献 250