强化学习

本书共有19章，分为六大部分，详细介绍了强化学习中各领域的基本理论和新进展，内容包括：MDP、动态规划、蒙特卡罗方法、批处理强化学习、TD学习、Q学习、策略迭代的小二乘法、迁移学习、贝叶斯强化学习、一阶逻辑MDP、层次式强化学习、演化计算、预测性定义状态表示、去中心化的部分可观察MDP、博弈论和多学习器强化学习等内容，并阐述强化学习与心理和神经科学、游戏领域、机器人领域的关系和应用，后提出未来发展趋势及研究热点问题，有助于年轻的研究者了解整个强化学习领域，发现新的研究方向。本书适合作为高等院校机器学习相关课程的参考书，也可作为人工智能领域从业技术人员的参考用书。

马可·威宁，在荷兰格罗宁根大学人工智能系工作，他发表过各种强化学习主题的文章，研究领域包括强化学习、机器学习、深度学习、目标识别、文本学习，进化计算、机器人等。
马丁·范·奥特罗，是荷兰奈梅亨大学认知人工智能小组的一员。主要研究领域是强化学习在环境中的知识表示。

译者序
序言
前言
作者清单
第一部分绪论
第1章强化学习和马尔可夫决策过程2
1.1简介2
1.2时序决策3
1.2.1接近时序决策4
1.2.2在线学习与离线学习4
1.2.3贡献分配5
1.2.4探索-运用的平衡5
1.2.5反馈、目标和性能5
1.2.6表达6
1.3正式的框架6
1.3.1马尔可夫决策过程7
1.3.2策略9
1.3.3最优准则和减量9
1.4价值函数和贝尔曼方程10
1.5求解马尔可夫决策过程12
1.6动态规划：基于模型的解决方案13
1.6.1基本的动态规划算法13
1.6.2高效的动态规划算法17
1.7强化学习：无模型的解决方案19
1.7.1时序差分学习20
1.7.2蒙特卡罗方法23
1.7.3高效的探索和价值更新24
1.8总结27
参考文献27
第二部分高效的解决方案框架
第2章批处理强化学习32
2.1简介32
2.2批处理强化学习问题33
2.2.1批处理学习问题33
2.2.2增长批处理学习问题34
2.3批处理强化学习算法的基础34
2.4批处理强化学习算法37
2.4.1基于核的近似动态规划37
2.4.2拟合Q迭代39
2.4.3基于最小二乘的策略迭代40
2.4.4识别批处理算法41
2.5批处理强化学习理论42
2.6批处理强化学习的实现43
2.6.1神经拟合Q迭代44
2.6.2控制应用中的神经拟合Q迭代算法45
2.6.3面向多学习器的批处理强化学习46
2.6.4深度拟合Q迭代48
2.6.5应用／发展趋势49
2.7总结50
参考文献50
第3章策略迭代的最小二乘法53
3.1简介53
3.2预备知识：经典策略迭代算法54
3.3近似策略评估的最小二乘法55
3.3.1主要原则和分类55
3.3.2线性情况下和矩阵形式的方程57
3.3.3无模型算法的实现60
3.3.4参考文献62
3.4策略迭代的在线最小二乘法63
3.5例子：car-on-the-hill64
3.6性能保障66
3.6.1渐近收敛性和保证66
3.6.2有限样本的保证68
3.7延伸阅读73
参考文献74
第4章学习和使用模型78
4.1简介78
4.2什么是模型79
4.3规划80
4.4联合模型和规划82
4.5样本复杂度84
4.6分解域86
4.7探索88
4.8连续域91
4.9实证比较93
4.10扩展95
4.11总结96
参考文献97
第5章强化学习中的迁移：框架和概观101
5.1简介101
5.2强化学习迁移的框架和分类102
5.2.1迁移框架102
5.2.2分类104
5.3固定状态-动作空间中从源到目标迁移的方法108
5.3.1问题形式化108
5.3.2表示迁移109
5.3.3参数迁移110
5.4固定状态-动作空间中跨多任务迁移的方法111
5.4.1问题形式化111
5.4.2实例迁移111
5.4.3表示迁移112
5.4.4参数迁移113
5.5不同状态-动作空间中从源到目标任务迁移的方法114
5.5.1问题形式化114
5.5.2实例迁移115
5.5.3表示迁移115
5.5.4参数迁移116
5.6总结和开放性问题116
参考文献117
第6章探索的样本复杂度边界122
6.1简介122
6.2预备知识123
6.3形式化探索效率124
6.3.1探索的样本复杂度和PAC-MDP124
6.3.2遗憾最小化125
6.3.3平均损失127
6.3.4贝叶斯框架127
6.4通用PAC-MDP定理128
6.5基于模型的方法130
6.5.1Rmax130
6.5.2Rmax的泛化132
6.6无模型方法138
6.7总结141
参考文献141
第三部分建设性的表征方向
第7章连续状态和动作空间中的强化学习146
7.1简介146
7.1.1连续域中的马尔可夫决策过程147
7.1.2求解连续MDP的方法148
7.2函数逼近149
7.2.1线性函数逼近150
7.2.2非线性函数逼近153
7.2.3更新参数154
7.3近似强化学习157
7.3.1数值逼近157
7.3.2策略逼近162
7.4双极车杆实验168
7.5总结171
参考文献171
第8章综述：求解一阶逻辑马尔可夫决策过程179
8.1关系世界中的顺序决策简介179
8.1.1马尔可夫决策过程：代表性和可扩展性180
8.1.2简短的历史和与其他领域的联系181
8.2用面向对象和关系扩展马尔可夫决策过程183
8.2.1关系表示与逻辑归纳183
8.2.2关系型马尔可夫决策过程184
8.2.3抽象问题和求解184
8.3基于模型的解决方案186
8.3.1贝尔曼备份的结构186
8.3.2确切的基于模型的算法187
8.3.3基于近似模型的算法190
8.4无模型的解决方案192
8.4.1固定泛化的价值函数学习192
8.4.2带自适应泛化的价值函数193
8.4.3基于策略的求解技巧196
8.5模型、层级、偏置198
8.6现在的发展201
8.7总结和展望203
参考文献204
第9章层次式技术213
9.1简介213
9.2背景215
9.2.1抽象动作215
9.2.2半马尔可夫决策问题216
9.2.3结构217
9.2.4状态抽象218
9.2.5价值函数分解219
9.2.6优化220
9.3层次式强化学习技术220
9.3.1选项221
9.3.2HAMQ学习222
9.3.3MAXQ223
9.4学习结构226
9.5相关工作和当前研究228
9.6总结230
参考文献230
第10章针对强化学习的演化计算235
10.1简介235
10.2神经演化237
10.3TWEANN239
10.3.1挑战239
10.3.2NEAT240
10.4混合方法241
10.4.1演化函数近似242
10.4.2XCS243
10.5协同演化245
10.5.1合作式协同演化245
10.5.2竞争式协同演化246
10.6生成和发展系统247
10.7在线方法249
10.7.1基于模型的技术249
10.7.2在线演化计算250
10.8总结251
参考文献251
第四部分概率模型
第11章贝叶斯强化学习260
11.1简介260
11.2无模型贝叶斯强化学习261
11.2.1基于价值函数的算法261
11.2.2策略梯度算法264
11.2.3演员-评论家算法266
11.3基于模型的贝叶斯强化学习268
11.3.1由POMDP表述的贝叶斯强化学习268
11.3.2通过动态规划的贝叶斯强化学习269
11.3.3近似在线算法271
11.3.4贝叶斯多任务强化学习272
11.3.5集成先验知识273
11.4有限样本分析和复杂度问题274
11.5总结和讨论275
参考文献275
第12章部分可观察的马尔可夫决策过程279
12.1简介279
12.2部分可观察环境中的决策280
12.2.1POMDP模型280
12.2.2连续和结构化的表达281
12.2.3优化决策记忆282
12.2.4策略和价值函数284
12.3基于模型的技术285
12.3.1基于MDP的启发式解决方案285
12.3.2POMDP的值迭代286
12.3.3确切的值迭代288
12.3.4基于点的值迭代方法290
12.3.5其他近似求解方法291
12.4无先验模型的决策292
12.4.1无记忆技术292
12.4.2学习内部记忆292
12.5近期研究趋势294
参考文献295
第13章预测性定义状态表示300
13.1简介300
13.1.1状态是什么301
13.1.2哪一个状态表示301
13.1.3为什么使用预测性定义模型302
13.2PSR303
13.2.1历史及测试303
13.2.2测试的预测304
13.2.3系统动态向量304
13.2.4系统动态矩阵305
13.2.5充分的数据集305
13.2.6状态306
13.2.7更新状态306
13.2.8线性PSR307
13.2.9线性PSR与POMDP的关联307
13.2.10线性PSR的理论结果308
13.3PSR模型学习308
13.3.1发现问题308
13.3.2学习问题309
13.3.3估计系统动态矩阵309
13.4规划与PSR309
13.5PSR的扩展310
13.6其他具有预测性定义状态的模型311
13.6.1可观测算子模型311
13.6.2预测线性高斯模型312
13.6.3时序差分网络312
13.6.4分集自动机312
13.6.5指数族PSR313
13.6.6转换PSR313
13.7总结313
参考文献314
第14章博弈论和多学习器强化学习317
14.1简介317
14.2重复博弈319
14.2.1博弈论319
14.2.2重复博弈中的强化学习322
14.3顺序博弈325
14.3.1马尔可夫博弈326
14.3.2马尔可夫博弈中的强化学习327
14.4在多学习器系统中的稀疏交互330
14.4.1多等级学习330
14.4.2协调学习与稀疏交互331
14.5延伸阅读334
参考文献334
第15章去中心化的部分可观察马尔可夫决策过程338
15.1简介338
15.2Dec-POMDP框架339
15.3历史状态与策略340
15.3.1历史状态341
15.3.2策略341
15.3.3策略的结构342
15.3.4联合策略的质量343
15.4有限域的Dec-POMDP的解决方案344
15.4.1穷举搜索和Dec-POMDP复杂性344
15.4.2交替最大化344
15.4.3Dec-POMDP的最优价值函数345
15.4.4前推法：启发式搜索348
15.4.5后推法：动态规划350
15.4.6其他有限域的方法353
15.5延伸阅读353
15.5.1一般化和特殊问题353
15.5.2有限Dec-POMDP354
15.5.3强化学习355
15.5.4通信356
参考文献356
第五部分其他应用领域
第16章强化学习与心理和神经科学之间的关系364
16.1简介364
16.2经典（巴甫洛夫）条件反射365
16.2.1行为365
16.2.2理论366
16.2.3小结和其他注意事项367
16.3操作性（工具性）条件反射368
16.3.1动作368
16.3.2理论369
16.3.3基于模型的控制与无模型的控制370
16.3.4小结和其他注意事项371
16.4多巴胺371
16.4.1多巴胺作为奖励预测误差372
16.4.2多巴胺的强化信号的作用372
16.4.3小结和其他注意事项373
16.5基底神经节373
16.5.1基底神经节概述374
16.5.2纹状体的神经活动374
16.5.3皮质基神经节丘脑循环375
16.5.4小结和其他注意事项377
16.6总结378
参考文献378
第17章游戏领域的强化学习387
17.1简介387
17.1.1目标和结构387
17.1.2范围388
……

前    言Reinforcement Learning: State-of-the-Art强化学习研究者们经常会被学生或同事问：“最近有没有一些强化学习方面的好书可以推荐给我？”    我们编写这本书的目的就是给这个问题提供一个答案。    一本关于强化学习的书10年前上面的问题是很容易回答的，在那个时候，有两本时兴的权威书籍。一本是由Rich Sutton和Andy Barto在1998年编写的优秀的强化学习导论书籍。这本书从人工智能的角度出发，采用教科书式的写作风格，一直被广泛使用（截至目前引用了一万次）。另一本是1996年由Dimitri Bertsekas和John Tsitsiklis撰写的《神经动力学编程》（neuro-dynamic programming）。这本书从运筹学的角度出发，以精确的数学方法讲述了动态规划和强化学习，特别强调了求近似解的体系结构。其中Sutton和Barto总是最大化回报，谈及价值函数、回报，并偏向于使用π增加的字母表中的{V, Q, S, A, T, R}部分；而Bertsekas和 Tsitsiklis谈及代价函数（cost-to-go-functions），总是最小化成本，并且使用希腊符号μ增加的字母表中的{J, G, I, U}部分。尽管它们有着表面（符号）差异、不同的写作风格和背景，可能这些书的读者也不同，但这两本书都试图对这个令人兴奋的新研究领域进行全面介绍，并成功地做到了这一点。当时运筹学和人工智能方法在行为优化方面的深入合并仍然在进行，这种交叉产生了丰硕的成果。最近，虽然已引入了Q学习和TD学习等强大的思想和算法，但仍有很多未知有待探索。    例如，算法和函数逼近器的组合的收敛问题出现了。包括算法收敛性、保证性能所需的样本数量以及强化学习技术在更大的智能体系结构中的适用性等许多理论和实验问题都没有得到解答。事实上，出现了许多新的问题并导致了越来越多的研究问题，这些都有待聪明的、年轻的博士生们来回答。尽管Sutton和Barto、Bertsekas和Tsitsiklis都很擅长介绍这个领域，并充分地描述了它的基本方法论和问题，但是，这个领域变得如此之大，需要新的教科书来记录所有新的研究进展。所以，这本书就是尝试填补这个空白的。    这是第一本介绍强化学习各主要子领域研究进展的书。但是，我们也提到其他一些有趣的介绍或描述各种强化学习主题的书籍。这些书包括Leslie Kaelbling于1996年编辑的合集和Puterman编著的马尔可夫决策过程手册的新版本。其他几本书涉及近似动态规划的相关概念。最近，又出现了一些关于马尔可夫决策过程、强化学习、函数逼近和强化学习的关系型知识表示的书籍。针对那些对强化学习课程感兴趣的人员，上述书只是强化学习相关著作的一部分。    强化学习：一个逐渐成熟的领域在过去的15年中，强化学习领域发展迅猛。然而最近的书中并没有反映出这段时间的最新研究，而是更多地关注丰富的、坚实的理论研究，提升算法的适用性、向上扩展性、与（概率）人工智能的结合，以及大脑理论和一般的适应性系统的联系。现代强化学习的创始人之一Richard Sutton，在1999年提出了强化学习发展的三个不同部分：过去、现在和未来。    过去的强化学习指的是1985年以前，在这个阶段，试错学习（trial-and-error learning）的思想得到了发展。这个时期强调使用积极探索的学习器（agent，也称智能体），并开发了利用标量回报信号来指定学习器目标的关键思想，称为回报假说。这些方法通常只学习策略，一般不能有效地处理延迟回报。    现在的强化学习指的是价值函数形成的时期。价值函数是强化学习的核心，几乎所有的方法都集中在价值函数的逼近上，以便计算（最优）策略。价值函数假说认为价值函数的逼近是智能化的主要目的。    目前，我们正处于强化学习的未来阶段。Sutton对这个时期的方向做出了预测，并写道：“正如现在强化学习离开回报的最终目标向价值函数迈了一步，未来的强化学习可能会进一步把重点放在研究能够对价值函数进行估计的结构上……在心理学中，积极创造世界的表征的开发思维的方法称为建构主义。我预计在未来几十年中，强化学习将集中在建构主义上。”事实上，正如我们在本书中所看到的那样，这一领域的许多新进展都与能够实现价值函数逼近的新结构有关。此外，许多进展都是关于这些新结构的性能及收敛的性质、能力和保证的。贝叶斯框架、高效线性逼近、关系型知识表示以及分层和多学习器性质的分解都构成了当今强化学习方法中所采用的新结构。    目前强化学习是一个已经确立的研究领域，通常归于机器学习。然而，由于其专注于行为学习，它与心理学、运筹学、数学优化等其他领域有着许多联系。在人工智能领域，它与概率论和决策论规划有很大的重叠，因为它与规划社区（例如国际自动规划系统会议（ICAPS））有许多共同的目标。在最新的国际规划竞赛（IPC）中，源于强化学习文献的方法已经参赛，并且在概率规划问题和最近的“学习规划”（learning for planning）方面都有着非常好的表现。    强化学习的研究在人工智能的广泛领域中几乎随处可见，因为它既是行为优化的一般方法，也是一套计算工具。现在所有主要的人工智能期刊都发表关于强化学习的文章，并且已经持续很长时间了。强化学习的应用领域从机器人、电脑游戏到网络路由和自然语言对话系统，强化学习论文也出现在跟这些主题相关的论坛上。大量的论文每年（或每两年）出现在人工智能领域的顶级会议上（如IJCAI、ECAI和AAAI），还有许多统计机器学习领域的顶级会议上（如UAI、ICML、ECML和NIPS）。此外，关于人工生命（Alife）、自适应行为（SAB）、机器人（ICRA、IROS、RSS）、神经网络和进化计算（如IJCNN和ICANN）的会议也有强化学习的研究工作。最后但同样重要的一点是，在过去的10年中，所有主要的人工智能会议都出现了许多专业化的强化学习研讨会和教程。    尽管强化学习已经为其他许多领域做出了巨大贡献，并且强化学习的论文无处不在，但强化学习领域的现状使得它很自然地在强化学习方法的某个特定焦点上形成论坛。欧洲强化学习研讨会（EWRL）已经逐渐成为这样一个论坛，每隔一年就会有一次相当大的发展，2008年在南锡举办并在2011年与ECML一起举办。此外，IEEE自适应动态规划与强化学习（ADPRL）研讨会也成为研究人员展示和讨论其最新研究成果的一个会议。EWRL和ADPRL一起表明，这一领域已经有了很大的进展，需要有自己的社区和事件。    在强化学习的实践方面以及更重要的是在基准、评估和比较方面也有了很多进展。除了规划比赛（例如IPC）之外，一些强化学习比赛也已成功举办。参赛者不仅在几个经典领域进行竞赛（例如平衡杆），而且在电脑游戏“俄罗斯方块”和“超级马里奥”等新兴领域进行竞赛。这些比赛可以促进代码共享和重用，建立该领域的基准，并用于评估和比较具有挑战性的领域中的算法。另一个代码和解决方案重用的倡导者是RL-Glue框架，它提供了一个抽象的强化学习框架，用于在研究人员之间共享方法。RL-Glue适用于大多数常用的编程语言，从而为实验提供了系统和语言独立的软件框架。比赛和RL-Glue促进了强化学习领域的成熟，使得可以应用更好的科学方法来测试、比较和重用强化学习方法。    本书的目的和目标读者如前所述，我们试图让本书回答这个问题：“你会推荐什么样的书来学习目前的强化学习？”每个可能提出这个问题的人都是本书的潜在读者，这包括博士和硕士生、强化学习的研究人员，以及其他任何想了解强化学习领域的研究人员。书中关于当前强化学习主要研究领域的文献为研究人员提供了一个很好的起点去继续拓展该领域，把强化学习应用到新问题，并将主要的行为学习技术引入到他们自己的智能系统和机器人中。    当我们开始编著本书时，我们首先创建了一个长长的主题列表，并对它们进行了分组，最后选出了近20个比较大的强化学习子领域，这些子领域在过去10年里发布了许多新成果。这些子领域不仅包括比较成熟的子领域（如演进强化学习），还包括更新的主题（如关系型知识表示方法、贝叶斯学习和规划框架）。此外，我们还专门用了一章来介绍分层方法，形成了第一个子领域——它是在前面提到的两本书之后出现的，因此当时没有讨论。    本书的理念是让所有的作者反映这个领域青春和活跃的本质。为此，我们主要选择并邀请了刚开始工作的年轻研究人员。他们中的许多人最近刚获得博士学位，这就确保了他们在自己的强化学习子领域是活跃的专家，并对这个子领域充满了想法和热情。而且，这也给了他们一个在更大的研究领域内推广其子领域研究成果的好机会。此外，我们还邀请了几位经验丰富的研究人员，他们在强化学习的几个子领域取得了先进的研究成果。这一切使得关于这个主题的不同观点得到了很好的结合。正如我们所希望的那样，提交的内容初稿质量非常高。为了有一套确保高质量内容的完整程序，编辑组成员连同一批专家作为审稿人，对每章进行了至少三次审核。成书内容得到了进一步的改进，而且使书中包含了每个子领域的大量的参考文献。    本书的最终版本包含19章，其中第1章包含强化学习的基础知识、动态规划、马尔可夫决策过程和基础的算法（如Q学习和值迭代）。最后一章回顾了书中的内容，讨论了遗漏的东西，并指出了进一步研究的方向。另外，这一章还包含个人对这个领域的思考和预测。构成本书核心的17章中，每一章都是自成一体的，包含对强化学习子领域的介绍和概述。下面我们将会给出本书结构及各章的概要。本书共有30位作者，他们分别来自于不同的机构和不同的国家。    本书结构这本书包含了19篇关于强化学习基础概念和各个子领域的综述，并分为四个主要的类别，我们接下来会对这些类别进行简要的说明。第1章由Martijn van Otterlo和Marco Wiering执笔，涵盖对基础概念与算法的介绍性材料。这一章讨论马尔可夫决策过程，及其对应的基于模型的和无模型的求解算法。这一章的目的是给读者提供一个快速了解强化学习方法主要构成的概述，同时该章也为其余各章提供了必要的背景知识。本书中的所有综述都建立在第1章的背景介绍的基础之上。本书的最后一章也是由Marco Wiering和Martijn van Otterlo执笔的，它回顾本书各章的内容，并列举了本书尚未讨论到的主题以及未来的研究发展方向。另外，通过汇总其他章部分作者的简要表述，列举了个人对强化学习领域的一些思考与预测。本书共有六个部分，其主体