强化学习(第2版)

译者序
“思想总是走在行动的前面，就好像闪电总是走在雷鸣之前。”德国诗人海涅的诗句再恰当不过地描述了我次读到本书英文原版时的感受。
纵观人工智能技术的发展历史，就是一部思想、理论、算法、工程应用的成就交替出现而又交相辉映的历史。传统人工智能领域的三大学派：以逻辑推断和贝叶斯学习为代表的符号主义学派、以神经网络为代表的联结主义学派以及以控制论和强化学习为代表的行为主义学派，在不同的历史阶段都产生了很多绝妙的思想和理论成果，而技术应用的水平和范围也让它们受到的关注度起起落落。 20世纪 40年代到 50年代，行为主义的控制论因其在航空、航天、机械、化工等领域的巨大成功受到了极大重视，也独立产生了自动控制等技术学科，甚至连早期的计算机专业也都是从控制相关的专业中分出来的，但其应用往往不被认为是一种“智能”，因而长期独立发展，游离于人工智能研究者的视野之外；而 20世纪 50年代人工智能的概念被正式提出以后，符号主义的数理逻辑以及贝叶斯学习等经典机器学习理论一直一枝独秀，引领着人工智能的研究和应用，尤其是专家系统和经典机器学习理论的大量成功应用，使得它成为 20世纪在人工智能研究中占据统治地位的主流学派；联结主义的神经网络的发展则一波三折， 20世纪 60年代类脑模型的研究和 80年代反向传播算法的提出都使得神经网络的研究在短时间内出现过热潮，然而理论局限和应用瓶颈一次又一次地把神经网络的研究打入冷宫，直到 21世纪初，深度学习理论被提出，借助 GPU等计算机硬件的算力飞跃并与大数据结合，迅速产生了巨大的产业技术红利，使得联结主义一跃成为当前人工智能研究炙手可热的学派。而无论技术应用如何风云变幻，产业发展如何潮起潮落，在人工智能的发展历程中，始终有一批思想的先行者以近乎顽固的执着态度在不同时代的“非主流”方向上进行着思考和探索，而正是这些执着甚至孤独的思想者，在技术应用热潮冷却后的暗夜里保留了火种，照亮了人类不停息的探索之路。
本书的两位作者 Richard S. Sutton和 Andrew G. Barto就是这样的思想先行者，而本书所介绍的“强化学习”，则是后深度学习时代技术发展的重要火种之一。以联结主义的神经网络为代表的深度学习毫无疑问是 21世纪初人工智能领域的重要、实用意义的技术突破之一，它为基础研究走向产业应用做出了巨大贡献，也相应地赢得了巨大的声誉和关注。然而，如火如荼的产业应用掩盖不住冷静的研究者们对人工智能未来走向的担忧，越来越多的研究者把深度学习的改良性研究视为工业界的应用技巧，而开始关注与联结主义的经典深度学习不同的人工智能范式探索。这其中，不同学派的思想融合产生了两个重要趋势。一个是将联结主义与符号主义融合起来，将神经网络的“黑箱学习”与先验知识、符号推理和经典机器学习结合，实现可解释、可推理、可操控的新一代“白箱学习”；另一个则是将联结主义与行为主义融合起来，将基于静态数据和标签的、数据产生与模型优化相互独立的“开环学习”，转变为与环境动态交互的、在线试错的、数据（监督信号）产生与模型优化紧密耦合在一起的“闭环学习”。强化学习就是“闭环学习”范式的典型代表，正如本书中所介绍的，它与传统的预先收集或构造好数据及标签的有监督学习有着本质的区别，它强调在与环境的交互中获取反映真实目标达成度的反馈信号，强调模型的试错学习和序列决策行为的动态和长期效应。这使得强化学习在人工智能领域的一些难题，如我本人所从事的认知型人机口语对话系统的研究中，具有无可替代的重要地位。而这些宝贵的思想，也为联结主义的深度学习在小数据、动态环境、自主学习等方面的进一步发展提供了重要的基础。在 AlphaGo战胜李世石之后， AlphaZero以其完全凭借自我学习超越人类在各种棋类游戏中数千年经验的能力再次刷新了人类对人工智能的认识，也使得强化学习与深度学习的结合受到了学术界和产业界的前所未有的关注。
《强化学习》的英文第 2版正是在这样的背景下出版的。本书并非一本实用主义的算法普及材料，而是一本强化学习思想的深度解剖之作，是强化学习基础理论的经典论述。本书没有从复杂的数学角度对强化学习的相关理论和方法给以极其严格的形式化推导，而是从强化学习的基本思想出发，深入浅出而又严谨细致地介绍了马尔可夫决策过程、蒙特卡洛方法、时序差分方法、同轨离轨策略等强化学习的基本概念和方法，并以大量的实例帮助读者理解强化学习的问题建模过程以及核心的算法细节。自 1998年第 1版出版以来，本书就一直是强化学习领域的经典导论性教材。在第 2版中，原作者又加入了很多新的内容，包括对深度强化学习应用（如 AlphaGo）的介绍，以及更新的思想和理解等，使得本书既保持对核心理论的清晰简明的讲解，又包含了与时俱进的应用成果和作者的思想。本书既可以作为一到两学期的强化学习课程的初级教材，也可以作为研究者自学的入门教程。在本书的翻译过程中， Richard S. Sutton和 Andrew G. Barto还特意为中国读者写了一段寄语，其中提到希望本书的中文译本能够促进中国学生产生更多的新思想，为世界范围的强化学习的研究繁荣做出贡献。这一期望也使我倍感荣幸，希望本书的中文译本能够让他们的思想为更多的中国研究者所了解，并作为一个种子，在中国孕育并产生人工智能前沿研究的新思想。 
本书的翻译得到了上海交通大学计算机系智能语音实验室同学们的大力支持，尤其是刘奇、陈志、陈露和吴越同学付出了大量的精力进行组织和排版整理，卞天灵、曹瑞升、杜晨鹏、黄子砾、金凯祺、兰鸥羽、李晨达、李大松、李福斌、李杰宇、李沐阳、刘辰、刘啸远、卢怡宙、马娆、盛佩瑶、王晨、王鸿基、王巍、吴嫣然、吴章昊、徐志航、杨闰哲、杨叶新、叶子豪、张王优、赵晏彬、周翔等同学都为本书的翻译做出了贡献。同时，也特别感谢苏州大学刘全教授，陆军军医大学王晓霞博士，清华大学刘乐章同学和北京交通大学张智慧同学对翻译稿进行了试读并帮助审校。本书的翻译也得到了电子工业出版社的大力支持，在此一并表示衷心的感谢。翻译过程难免存在疏漏和错误，欢迎读者批评指正。
俞凯 
2019年 4月 

第二版前言
本书第 1版出版的 20年以来，在机器学习 (包括强化学习 )前沿技术发展的推动下，人工智能取得了重大进展。这些进展不仅归功于这些年迅猛发展起来的计算机强大的计算能力，也受益于许多理论和算法上的创新。面对这些进展，我们早有对 1998年第 1版书进行更新再版的打算，但直到 2012年才开始真正着手编纂。第 2版的目标与第 1版一致：为强化学习的核心概念与算法提供清晰简明的解释，以供所有相关学科的读者学习。这一版仍然是一本概要介绍性的读物，仍然关注核心的在线学习算法，同时增加了一些近年来日趋重要的话题，并拓展了部分内容，给出了更新的理解。强化学习领域可以延伸出很多不同的方向，但我们并不想包罗万象，在此为可能出现的些许遗漏表示歉意。
第 2版记号变化
和第 1版一样，我们没有以严谨的形式化的方式来定义强化学习，也没有采用特别抽象的术语表达，但是为了大家能更深入地理解，有些话题仍然需要用数学来解释。无数学需求的读者可以选择跳过灰色框中的数学原理部分。在教学过程中，我们发现一些新的记号可以消除一些共同的疑惑点，因此本书的部分记号和上一版相比略有差异。首先我们对随机变量进行了区分，以大写字母表示变量本身，小写字母表示对应的实例。比如时刻 t的状态、动作和收益被表示为 St、At和 Rt，而它们可能的取值被表示为 s、a和 r。与之相伴随，我们用小写字母的形式 (例如 vл)来表示价值函数，用大写字母表示其表格型的估计值，比如 Qt (s, a)。近似价值函数是具有随机参数的确定性函数，因此用小写字母表示，比如 v.(s,wt) ≈vл(s)。向量用粗体的小写字母表示 (包括随机变量)，比如权值向量wt (先前用 θt表示 )、特征向量 xt (先前用фt表示 )。大写粗体用以表示矩阵。在第 1版中我们使用了特殊记号Pass′和Rass′来表示转移概率和期望收益。但这种记号并不能完整地表示出收益的动态性，只表示了期望值，因此只适用于动态规划而不适用于强化学习。另一个缺点是上下标的过度使用。因此，在这一版中我们明确采用 p(s′,r |s, a)的记号来表示给定当前状态 s和动作 a后，下一时刻的状态 s′和收益 r的联合概率分布。所有的记号变化都收录在稍后的“符号列表”中。
第 2版内容结构
第 2版在原先的基础上进行了许多拓展，整体结构也有所变化。第 1章是导论性的介绍，其后分为三个部分。第 I部分 (第 2～8章)会尽可能多地用表格型的案例讲解强化学习，主要包括针对表格型案例的学习和规划算法，以及它们在 n步法和 Dyna中的统一表达。这部分介绍的许多算法是第 2版的新增内容，包括 UCB、期望 Sarsa、双重学习、树回溯、 Q(σ)、RTDP和 MCTS。从介绍表格型案例开始，可以在简单的情况下理解算法的核心思想。本书的第 II部分 (第 9～13章)致力于将这些思想从表格型的情况扩展到函数逼近，包含人工神经网络、傅立叶变换基础、 LSTD、核方法、梯度 TD和强调 TD方法、平均收益方法、真实的在线 TD(λ)和策略梯度方法等新内容。第 2版大幅拓展了对离轨策略的介绍，首先是第 5～7章讲解表格型的案例，之后在第 11章和第 12章讲解函数逼近法。另一个变化是，这一版将 n步自举法 (在第 7章中详细阐述 )中的前向视图思想与资格迹 (在第 12章中单独阐述 )中的后向视图思想分开详细讲解。本书的第 III部分加入了大量阐述强化学习与心理学 (第 14章)、神经科学 (第 15章)联系的新章节，更新了针对多种案例，包括 Atari游戏、 Watson的投注策略和围棋人工智能 AlphaGo、AlphaGo Zero (第 16章)的研

《强化学习（第2版）》作为强化学习思想的深度解剖之作，被业内公认为是一本强化学习基础理论的经典著作。它从强化学习的基本思想出发，深入浅出又严谨细致地介绍了马尔可夫决策过程、蒙特卡洛方法、时序差分方法、同轨离轨策略等强化学习的基本概念和方法，并以大量的实例帮助读者理解强化学习的问题建模过程以及核心的算法细节。《强化学习（第2版）》适合所有对强化学习感兴趣的读者阅读、收藏。

Sutton目前是阿尔伯塔大学计算机科学教授和人工智能研究员，Deepmind的杰出科学家，领导Deepmind在加拿大的人工智能实验室。专注于强化学习领域理论与实务研究，被称为“强化学习之父”。＜BR＞俞凯，思必驰联合创始人、首席科学家、上海交通大学计算机系研究员，译有《解析深度学习：语音识别实践》一书。

目录 
第1 章导论· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 
1.1 强化学习· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 1 
1.2 示例· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 4 
1.3 强化学习要素· · · · · · · · · · · · · · · · · · · · · · · · · · · · 5 
1.4 局限性与适用范围· · · · · · · · · · · · · · · · · · · · · · · · · · 7 
1.5 扩展实例：井字棋· · · · · · · · · · · · · · · · · · · · · · · · · · 8 
1.6 本章小结· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 12 
1.7 强化学习的早期历史· · · · · · · · · · · · · · · · · · · · · · · · · 13 
第I 部分表格型求解方法· · · · · · · · · · · · · · · · · · · · · · · · · · · 23 
第2 章多臂赌博机· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 25 
2.1 一个k 臂赌博机问题· · · · · · · · · · · · · · · · · · · · · · · · 25 
2.2 动作-价值方法· · · · · · · · · · · · · · · · · · · · · · · · · · · · 27 
2.3 10 臂测试平台· · · · · · · · · · · · · · · · · · · · · · · · · · · · 28 
2.4 增量式实现· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 30 
2.5 跟踪一个非平稳问题· · · · · · · · · · · · · · · · · · · · · · · · · 32 
2.6 乐观初始值· · · · · · · · · · · · · · · · · · · · · · · · · · · · · 34 
2.7 基于置信度上界的动作选择· · · · · · · · · · · · · · · · · · · · · 35 
2.8 梯度赌博机算法· · · · · · · · · · · · · · · · · · · · · · · · · · · 37 
2.9 关联搜索(上下文相关的赌博机) · · · · · · · · · · · · · · · · · · 40 
2.10 本章小结· · · · · · · · · · · · · · · &mi