1_强化学习介绍翻译

我们在考虑学习时，可能最先想到的是通过与环境的交互来进行学习。一个婴儿在玩耍的时候，不存在明确的某位老师来教他如何晃动手臂或向四周张望，但是确实通过感觉器官与环境直接联系。运用这种联系能够产生一些关于起因和结果、动作的后果以及为达到目的而采取的措施等有价值的信息。在我们的生活中，这样的交互无疑是我们获得关于环境与自身的知识的主要源泉。无论我们在学习开车或是进行谈话时，我们都能准确地意识到环境对我们所做事情的反应，并且我们也会试着用自己的行为来影响环境。从交互中学习几乎是所有关于学习和智能的理论的最基本思想。

在本书，我们探讨一种从交互中进行学习的计算型（computational）方法。我们不是直接探索人和动物如何学习的理论，而是研究理想化的学习场景并评价各种学习方法的效果。也就是说，我们采用的是人工智能研究者或工程师的视线与角度。我们探讨一种能够让机器解决具有科学或经济价值的学习问题的设计方案，通过数学分析或计算实验来评估这些设计方案。这种方法称为强化学习（reinforcement learning），与其他机器学习方法不同的是，它着重于从交互中进行以目标为导向的学习。

1.1强化学习

强化学习就是学习如何将场景（环境状态）映射到动作，以获取最大的、数值的、奖赏信号。与大多数机器学习方法一样，学习者不被告知应该采用哪个动作，而是通过不断地尝试来发现能获得最大奖赏的动作。在最有趣且最具挑战性的例子中，动作不只影响直接奖赏，而且也会影响下一场景，以至于所有的后续奖赏。这样的两个特征：试错搜索和延迟奖赏，是强化学习的最重要特征。

强化学习并不是通过描述它的学习方法而定义的，而是通过描述一个学习问题来定义的。任何适合解决这一学习问题的方法，我们都认为是强化学习方法。虽然要到第3章，我们才能根据马尔可夫决策过程的最优控制理论来完整地描述一个强化学习问题，但是，对于通过与环境的交互而达到目标的学习中的agent，一些基本的概念就能够说明真实问题的最重要的基本思想。显然，这样的agent必须能够在一定程度上感知环境的状态，并且必须能够采取动作，所采取的动作，又会影响环境。这个agent还必须有一个或多个与环境状态有关的目标。这样，为此而设计的公式当中必须包含三个方面——感知能力、动作和目标，这是最简单并缺一不可的可能形式。

强化学习不同于监督学习（supervised learning），监督学习是目前在机器学习、统计模

强化学习Reinforcement Learning

式识别和人工神经网络的研究领域中，最为广泛研究的一种学习。监督学习是从样例学习，而样例是由富有知识的外部监督者提供的。这是一种重要的学习方法，但是它不能单独地用于交互学习。在交互式问题中获得期望行为的样例通常是不切实际的，它们要求既是正确的，又能代表agent的所有场景，在这些场景中，agent采取动作。在一些我们希望学习能够带来利益的未知领域，agent必须能够从自身的经验中学习。

一个在强化学习中存在，而在其他类型学习中不存在的挑战，是探索和利用之间的平衡。为了得到很多奖赏，强化学习agent必须选择它过去已经尝试过的在产生奖赏方面行之有效的动作。而为了发现这样的动作，它又必须去尝试以前没有选择过的动作。为了得到奖赏，agent必须利用它已经知道的信息，同时还必须进行探索，以便将来能选择到更好的动作。令人为难的是，单单采用探索或只有利用都会导致任务失败。agent必须尝试各种动作，并且渐渐趋近于那些表现最好的动作。在一个随机任务中，每个动作都必须被尝试多次才能获得对它的期望奖赏的可靠估计。多年来，数学家们一直在广泛研究探索—利用这一两难问题（见第2章）。现在，我们简单地认为，探索和利用的平衡问题在监督学习中，根本就不存在，正如它所定义的那样（样例学习阶段之后，就只有利用了）。

强化学习的另一个关键特征，是它明确地提出整个问题是一个以目标为导向的agent与不确定的环境之间交互的问题。这种学习与许多其他方法相比，其他方法只考虑了子任务，而没有解决怎样可以把这些子任务整合到一个更大的框架中。例如，我们以前提过，许多与监督学习有关的机器学习研究都没有明确说明这样的能力最终将如何利用。其他研究者发展了一般目标规划的理论，但没有考虑在实时决策中如何进行规划，也没有考虑规划所必需的预测模型将从哪里来的问题。尽管这些方法已经产生了许多有用成果，但是，它们将重点放在孤立的子问题上的做法是一个严重的局限。

强化学习采用相反的方式，它从一个完全的、交互的、目标搜索的agent开始。所有强化学习的agent都有明确的目标，能感知环境中的各个方面，并且能选择动作来影响环境。另外，通常我们从开始就假设：尽管agent面对的是一个它很不了解的环境，但它必须得有所动作。如果强化学习涉及到规划，它必须处理规划和实时动作选择之间的相互影响，同时也要解决怎样获得并改进环境模型的问题。如果强化学习涉及到监督学习，那么，是因为存在着某些特定的原因，这些原因决定了哪些能力（agnet的某些指标）是至关重要的，哪些却不是，这样的区分，需要外界注入（监督）。为了推进关于学习的研究，必须把重要的子问题分割开来并加以研究，尽管不能明晰整个agent中的所有细节，但要明确这些子问题在完全的、交互的、目标搜索的agent中的地位。

包括强化学习在内的一个大趋势就是人工智能与工程学科的联系日益紧密。就在不久之前，人工智能还几乎被认为是一个完全于控制理论和统计学之外的领域。它必须处理逻辑和符号而非数字。人工智能就是大的LISP程序，而不是线性代数、微分方程或者统计学。经过几十年，这种观点在逐渐减弱。现代人工智能研究者接受了统计和控制的方法，例如，

简介Introduction

把统计和控制的方法看做相关的竞争方法或者简单地把它们接纳为一种处理工具。以前被忽视的那些介于人工智能和常规工程方法之间的领域现在成为了最活跃的研究领域，包括神经网络、智能控制以及我们现在所谈的话题——强化学习。在强化学习中，我们将把最优控制理论和随机逼近的理念，扩展到更广泛的人工智能目标中，并解决更有挑战性的目标。

1.2例子

理解强化学习的一个好方法，就是考虑一些导致它发展的例子和可能的应用。  一个高明的棋手走棋。抉择取决于两个方面：规划（预计的可能回击和反回击）以及对

特定位置和走棋的可取性的直接、直觉的判断。

 一个实时调整石油提炼操作参数的自适应控制器。该控制器在规定的边际成本基础上优

化产量/成本/质量之间的平衡，而不严格按照工程师的最初设置来执行。  小牛羚在出生后几分钟内挣扎着站起来。半小时后它就能每小时跑20英里。  一个移动机器人决定是进入一个新房间去寻找更多要收集的垃圾，还是寻找一条回去充

电的路。它根据以前找到充电器的快慢和难易程度来作决定。

 Phil准备早餐。仔细考虑一下，即使是这样一个平常的行为，也揭示了一个条件行为和

连锁的目标—子目标之间关系的复杂交织：走向食物柜，打开，选择一个谷物箱，然后伸手去拿燕麦，抓住，拿走。要拿到一个碗、勺子和牛奶瓶需要其他一连串复杂、协调、相互影响的行为。每个步骤包括了一连串眼睛的移动，以获取信息并指导伸手和移动。我们要快速做出判断，如怎样抓住物品或者是否先将其中一些物品放到餐桌上然后再去取其他物品会更好一些。每个步骤都是受目标指导的，如抓住一个勺子或者是走向冰箱，并且为其他目标服务，如一旦麦片准备好了就用勺子吃饭并最终获取营养。

这些例子共同的特征就是：它们是如此基本以至很容易被忽略掉。它们都涉及一个积极作决策的agent和它所处的环境之间的交互，尽管环境是不确定的，但是agent试着寻找并实现目标。agent的动作允许影响环境的未来状态（如下一个棋局，提炼厂的储量，机器人的下一位置等），进而影响agent以后可利用的选项和机会。正确的选择要求我们考虑间接的、延迟的动作序列，因此也可能要求有预见性和规划。

同时，在所有这些例子中，动作的影响不能完全地被预测到，因此agent必须不断监测它所处的环境并且做出恰当的反应。例如，Phil必须注视着他倒入麦片碗中的牛奶以防止溢出来。所有这些例子都包含agent能感知的明确目标，直接根据感觉来判断距离到达目标的进度。棋手知道他是否赢了，提炼厂控制器知道生产了多少石油，移动机器人知道电池什么时候消耗尽，Phil知道他是否享受了这顿早餐。

所有这些例子中，agent可以随时间推移，利用它获得的经验不断提高自己的性能。棋手能改进他估计位置的直觉；小牛羚不断提高它奔跑的效率；Phil则学着流水线地准备他的早餐。从一开始agent带给任务的知识（不管来自于相关任务的先验经验，还是通过设计、进化建立起来）就会对那些有用或容易学的东西有影响，但是，若要利用任务中的某些特征

强化学习Reinforcement Learning

来调整系统的行为，与环境的交互才是至关重要的。

1.3强化学习的基本要素

除了agent和环境之外，我们可以认识一下强化学习系统的四个主要子要素：策略、奖赏函数、值函数和一个可选的环境模型（model）。

策略（policy）定义了学习agent在给定时间内的行为方式。简单地说，一个策略就是从环境感知的状态到在这些状态中可采用动作的一个映射。对应在心理学中被称为刺激—反应的规则或联系的一个集合。在某些情况下策略可能是一个简单函数或查找表，而在其他情况下策略可能还涉及到大量计算，如搜索处理。策略在某种意义上说是强化学习agent的核心，单单只有它就可以决定行为了。一般来说，策略可以是随机的。

奖赏函数（reward function）定义了在强化学习问题中的目标。简单地说，它把环境中感知到的状态（或状态－动作对）映射为单独的一个数字，即奖赏（reward），表示该状态的内在的可取程度。强化学习agent的唯一目标就是最大化在长期运行过程中收到的总奖赏。奖赏函数定义了对agent来说什么是好和坏的事件。在生物系统中，用愉快和痛苦来定义奖赏似乎有些不合适。而奖赏是agent所面对的问题的直接的和规定性的特征。正因为这样，奖赏函数必须是agent所不能改变的。但是它可以是调整策略的基础。例如，如果一个策略所选择的动作带来的奖赏较小，那么策略就可能在将来选择其他动作。一般来说，奖赏函数可以是随机的。

奖赏函数在直接层面上表示一个选择的好坏，而值函数（value function）在长期运行层面界定什么才是好的选择。简单地说，一个状态的值（value）是一个agent从那个状态开始，到将来能预期的累积奖赏的和。奖赏决定了环境状态的直接、内在的可取性，而值表示的是把可能的后续的状态以及在这些状态中可获得的奖赏考虑在内的状态的长期可取性。例如，一个状态可能会总是得到一个低的直接奖赏但仍有较高的值，因为跟在它后面的状态能获得高的奖赏。或者反过来也是可能的。拿人类做类比，奖赏就象快乐（奖赏高）和痛苦（奖赏低），而值就像是我们在一个特定的环境中用更完善、更长远的目光来看我们有多开心或不开心。我们希望这个说法的基本而熟悉的思想能够有助于理解值函数的概念。

从某种意义上说奖赏是主要的，而值是对奖赏的预测，是第二位的。没有奖赏就没有值，而估计值的唯一目的就是获得更多的回报（总奖赏）。然而，我们在做决策和评价决策的时候考虑最多的却是值。动作的选择是根据值来判断的。我们选择带来最高值的动作，而不是带来最高奖赏的动作，因为这些动作在长期运行过程中获得的奖赏总和最多。在决策和规划中，被称为值的衍生量是我们最为关注的事情。遗憾的是，确定值比确定奖赏要难得多。奖赏可以直接由环境给出，但是值却必须从agent整个生命周期所做的观察序列中估计或者重新估计。事实上，几乎所有强化学习算法中最重要的组成部分就是能有效估计值的方法。在过去的几十年中，值估计这个中心任务就是我们所学的有关强化学习中最重要也是最有争议的问题了。

简介Introduction

尽管我们在本书提到的所有强化学习方法都是围绕估计值函数来组织的，但是这不是解决强化学习问题所必须的。例如，如遗传算法、遗传程序设计、模拟退火以及其他函数优化方法等搜索方法都被用于解决强化学习问题。这些方法直接在策略空间中搜索而没有利用值函数。我们把这类方法称为进化方法，因为它们的操作类似于生物进化的方式，通过一种有技巧的行为产生个体，尽管这些个体在它们的生命中并没有学习过这种行为。如果策略空间相当小，或者策略空间被构造得很好，这样策略就很容易找到，那么进化方法就比较有效。另外，在学习agent不能精确感知环境的状态时，进化方法也是有优势的。

然而，我们所说的强化学习涉及到与环境交互时学习，而进化方法不是这样。我们相信，在许多情况下能够利用交互时的个体行为细节的方法要比进化方法更有效。进化方法忽视了强化学习问题中的许多有用结构：它们没有考虑到所搜索的策略是一个从状态到动作的函数；也没有注意一个agent在生命周期中经过的状态及其选择的动作。有些情况下，这些信息可能有误导性（如状态观察错误的时候），但是这些信息在大多数时候都能使得搜索更有效率。虽然进化和学习拥有许多共同特征并且能自然地一起工作，如它们在自然界中那样，但是我们并不认为进化方法自身特别适合强化学习问题。为了简单起见，本书中我们使用术语“强化学习”时，不包括进化方法。

有些强化学习系统中还存在着第四个也是最后一个要素：环境模型。它模拟了环境的行为。例如，给定一个状态和动作，这个模型可以预测必定导致的下一状态和下一奖赏。模型一般用于规划（planning），所谓规划指的是，在一个动作序列中，通过某种方式预测将来的场景。将模型和规划结合到强化学习系统中是一个新的进展。早期的强化学习系统很明确是试错学习者；它们的所做所为几乎与规划完全相反。然而，强化学习方法与动态规划方法有密切的联系这一事实逐渐变得清楚了，它们都可以使用模型，进而也与状态—空间规划方法有关。在第九章我们探讨同时使用试错、学习一个环境模型以及使用模型进行规划的强化学习系统。现代强化学习贯穿了从低水平的试错学习到高水平的深邃的规划。

1.4展开的一个例子：Tic－Tac－Toe

为了说明强化学习的一般思想并与其他方法做比较，我们要更详细地考虑下面一个例子。

思考一个熟悉的儿童游戏井字游戏（tic－tac－toe）。两个玩家轮流在一个三乘三的棋盘上游戏。一个玩家划“×”而另一个划“O”，直到一个玩家在水平、垂直或对角线方向上划上三个标记成为一行，那么他就获胜。如下图中的“×”所示：

如果棋盘上没有一方能添满三个一行，那么就是平局。因为一个有经验的玩家能保证一局都

强化学习Reinforcement Learning

不输，所以我们假设跟我们玩的不是一个非常有经验的玩家，他有时也会做出错误的决策而使我们有机会获胜。这里，我们认为平局和输掉都是对我们不利的事情。我们应该怎样做使得玩家能发现对手的缺陷并最大化获胜机会呢？

尽管这是一个简单问题，但是不容易用合适的经典方法来解决。例如，游戏理论中经典的“极大极小”方法在这里就不适用，因为这种方法假设了对手玩游戏的特殊方式。比如一个使用极大极小方法的玩家永远不会到达一个会导致失败的状态，即使事实上因为对手的失误，极大极小方法玩家总是经常能够在该状态中获胜。经典的用于顺序决策问题的优化方法，如动态规划，能够为任意对手计算一个最优解决方案，但是需要输入该对手的一个完整说明，包括这个对手在每个棋盘状态中做出每种走棋方式的概率。我们假设这些信息在这个问题中不能事先获得，事实上大多数实际问题也确实如此。另外，如果不断地与对手对弈，这样的信息也能从经验中估计出来。解决这个问题的一个最好方法就是首先学习一个对手行为的模型，当到达一定置信度时，再运用动态规划的方法计算一个给定近似对手模型的最优解。最后，这与我们在本书后面提到的强化学习方法是基本一致的。

如果用进化方法来解决这个游戏问题，它会直接在可能的策略空间中搜索有最高几率赢过对手的一个策略。这里，一个策略就是一个规则，它告诉玩家在每个游戏状态（三乘三棋盘上的每个“×”和“O”的可能布局）中应该如何走棋。对考虑到的每个策略来说，它的获胜概率的估计能从与对手不断的对弈中获得。这个评价能用来指导下一步将采用哪一个或哪几个策略。一个典型的进化算法将在策略空间中爬山，在试图获得增量式改进的尝试中不断地产生和评价策略。或者，可能是用一个遗传类型的算法来维护和评价策略种群。据文献记载有数百种不同的优化方法可以应用。通过直接在策略空间搜索，我们提出完全策略方法，并与以标量评价为基础的方法相比较。

以下是如何利用强化学习和近似的值函数方法来解决tic－tac－toe游戏问题。首先，我们为每个可能的游戏状态建立一个数字表格。表格中的每个数字是从该状态获胜概率的最新估计。我们把这个估计看成是状态值，整个表格就是学习到的值函数。如果状态A的当前获胜概率的估计要高于状态B的获胜概率的估计，那么A的值要高于B的值，或者说状态A比状态B好。假设我们划的是“×”，对所有能在同一直线上形成三个“×”的状态的获胜概率就是1，因为我们已经获胜了。同样，对所有在同一直线上有三个“O”，或“填满”的状态，合适的概率就是0，因为在这些状态下我们赢不了对手。我们把所有其他状态的初始值设为0.5，表示有50%的机会可以获胜。

我们与对手玩很多次游戏。为了选择走棋动作，我们需要考察每个可能走棋（棋盘上的空格之一）带来的结果状态并查找它们在表格中的当前值。在大多数情况下我们采用贪心策略，选择会导致状态值最大的走棋方式，即有最高的估计获胜概率。但是有时候，我们也会随机选择一些其他走棋方式。这些称为探索（exploratory）走棋方式，因为它们会引导我们去经历一些以前没有遇到过的状态。图1.1中所示是游戏过程中所做的或考虑到的走棋序列。

简介Introduction

在游戏中我们玩的时候，我们通过新发现，改变自己所处状态的值。我们尽量使得它们能更精确地估计获胜概率。为了达到这一目的，我们在新的走棋之前，对每一次贪心走棋之后的状态值进行“更新”，如图1.1中的箭头所示。更确切地说，较早状态的当前值被调整为更接近后来状态的值。这可以通过一点点将早期的状态值调整为趋于后来的状态值。如果我们令s表示贪心走棋之前的状态，s'表示走棋之后的状态，那么对s的估计值的更新，记为V(s)，可以写成

V(s)V(s)[V(s')V(s)]，

其中是一个很小的正小数，称为步长参数，它能影响学习的速度。这个更新规则是时间差分学习（temporal-difference）方法的一个例子，之所以称为时间差分，是因为它的变化是基于两个不同时间的估计之间的差值V(s')V(s)。

图1.1 tic－tac－toe的一连串动作。实线表示游戏中的走棋；虚线表示我们（我们的强化学习玩家）考虑过但是没有做出的走棋。我们的第二个走棋是一个探索性走棋，意味着尽管有另一个同级的走棋能到达e*状态而等级更高。探索性走棋那一步不产生任何学习效果，但是我们的每个其他走棋都可以，导致了如曲线箭头和文章中具体提到的更新。

上面提到的方法在该任务中表现得相当好。例如，对于任何固定的对手，如果步长参数随时间推移而适当减少的话，这个方法在由我方玩家给定最优玩法时，收敛到从每个状态获胜的真实概率。另外，随后所采用的走棋（除了探索性走棋）事实上已经是对付对手的最优走棋方式了。换句话说，这个方法会收敛到这个游戏的一个最优策略。如果步长参数不是随

强化学习Reinforcement Learning

时间而渐渐趋于0的话，这个玩家也会通过慢慢改变他的玩法而取得佳绩。

这个例子说明了进化方法和学习值函数的方法之间的不同。为了评价一个策略，进化方法必须保持策略固定并且多次与对手玩游戏，或使用这个对手的模型来模拟许多次游戏。获胜频率给出了使用该策略获胜的概率的无偏估计，并可以用于指导下一次的策略选择。但是，每一次策略改变只能是在许多次游戏之后，并且只用到了最终结果：游戏过程中发生的事情被忽略掉了。例如，如果玩家赢了，那么他在这次游戏中的所有行为都给予了很高的置信度，而与特定的几步对获胜至关重要的走棋无关。甚至置信度还分配给了那些根本就没有发生的走棋。相反，值函数方法允许对个别状态进行评价。最后，进化方法和值函数方法都是搜索策略空间，但是在游戏过程中，学习值函数方法充分利用了游戏进程中的可用的信息。

这个简单例子说明了强化学习方法的几个关键特征。首先，强调学习时与环境的交互，在本例中就是与对手的交互。第二，有一个清晰的目标，并且正确的行为还需要规划或者提前考虑到某个选择的延时效果。例如，这个简单的强化学习玩家应该学习为目光短浅的对手设置几步陷阱。强化学习方法中一个显著的特点就是，在不使用对手模型并且不在未来可能发生的状态和动作序列中进行明确搜索的情况下，也能获得规划和前瞻的效果。

尽管这个例子说明了强化学习的一些关键特征，但由于问题太简单了，可能给我们一个错觉，就是强化学习的作用比它实际的作用要有限得多。尽管tic－tac－toe是一个双人游戏，但是强化学习也可以应用到没有外部对手的情况中，即“对抗自然游戏”的情况中。tic－tac－toe游戏中，行为被划分为若干孤立的情节（episode，从开始下棋到棋局结束，为一个episode），并且只有在每个情节结束之后才能得到奖赏，强化学习的应用也不局限于这种情形。当行为是无限持续的并且各种大小不同的奖赏可以在任意时候获得时，强化学习方法也同样适用。

Tic－tac－toe游戏有一个相对小的、有限的状态集合，但是强化学习也能在状态集合相当大甚至是无限时使用。例如，Gerry Tesauro（1992，1995）将上面所提的算法与人工神经网络方法结合起来，用于学习玩西洋双陆棋游戏，这个游戏中的状态数目接近10。如此多的状态，即使只是其中的一小部分我们都不可能访问到。Tesauro的学习程序要比以前的任何程序都好得多，现在已经能达到世界上顶级的人类玩家水平（见第11章）。神经网络为程序提供了从经验中进行泛化的能力，这样在一个新的状态中，它依据保存下来的、以前经历过的类似状态的信息进行决策。强化学习系统怎样才能在具有如此大状态集合的问题中有效工作，与它是否能恰当地从过去的经验中泛化有着密切的关系。在这种情况下，我们有必要将监督学习结合到强化学习中来。神经网络不是完成这个任务的唯一或者最好的方法。

在这个tic－tac－toe游戏例子中，除了游戏规则之外，学习是从没有任何先验知识的情况下开始的，但是并不意味着强化学习必须从空空如也开始。相反，先验经验能以多种形式结合到强化学习中，这对提高学习效率来说是关键的。在tic－tac－toe游戏中我们访问的都是真实状态，而强化学习也可以用于一部分状态是隐蔽的情况，或者不同状态以同样的外观

20简介Introduction

出现在学习者面。这些情况就要复杂得多，我们在本书没有明确地包含这种问题。

最后，tic－tac－toe游戏玩家可以预判并知道每种可能走棋导致的结果状态。为了做到这一点，我们必须有一个游戏模型并且允许它“思考”其环境在遇到从来没有遇过的走棋方式时应该做出什么样的反应。许多问题就像这样，但是在另一些问题中，即使是一个短期的动作效果模型也很难得到。这两种情况都可以使用强化学习方法。虽然不是一定需要模型，但是如果模型可用或者可以学到的话，也可以很容易地利用模型。

练习1.1：自我对战 假设前面描述的强化学习算法不是与一个固定的对手对抗，而是与自己对抗。你认为在这种情况下会发生什么事情？它是否会用另一种方式来学习？

练习1.2：对称性 虽然许多tic－tac－toe中的布局看起来不一样，但是实际上是相同的，因为它们是对称的。我们可以怎样利用这个特点改进前面提到的强化学习算法？以什么样的方式来改进？现在重新考虑一下，假设我们的对手没有利用对称性，在这种情况下我们应该怎么办？那么是否对称的布局必定有同样的值？

练习1.3：贪心方法 假设强化学习玩家是贪心的，也就是他总是选择那些他认为会导致最好布局的走棋。与非贪心的玩家相比，这样做是更好还是更差呢？又会产生什么问题呢？ 练习1.4：从探索中学习 假设学习更新发生在所有走棋之后，包括探索性走棋。如果步长参数随时间推移而适当地减少，那么所有的状态值都将收敛到一个概率集合。我们有两种选择：从探索性走棋中学习以及不从探索性走棋中学习，那么这两组概率应该如何计算呢？假设我们不断地进行探索性走棋，哪个概率集合可能学习得更好？哪个能带来更多的胜利？ 练习1.5：其他改进 你能想到其他方法来提高强化学习玩家的水平吗？你能想到更好的方法来解决前面提出的tic－tac－toe问题吗？

1.5总结

强化学习是以计算型的方法来理解、进行自动以目标为导向的学习和决策。它有别于其他计算方法，因为它强调的是个体与环境之间的直接交互学习，而不依靠外界监督或环境的完整模型。我们认为，为获得长期目标而与环境交互学习会产生一些计算型问题，强化学习是第一个严肃对待这些计算型问题的研究领域。

强化学习根据状态、动作和奖赏使用一个形式化的框架定义了一个学习agent与环境的交互。这个框架试图用一种简单方式来表示人工智能问题的本质特征。这些特征包括了原因和结果的概念，不确定性和非决定性的概念，清晰的目标的存在性。

值以及值函数的概念是本书中强化学习的核心特征。我们认为在策略空间中有效搜索就是利用值函数。正是值函数的使用才使强化学习区别于直接在策略空间中搜索的进化方法，进化方法的搜索是根据对整个策略的标量评价进行的。

1.6强化学习的历史

强化学习的历史有两条主要线路，两者在与现代强化学习结合之前各自都已经发

强化学习Reinforcement Learning

展了很长时间，并且已经发展得比较丰富了。一条线路关注于试错学习，它以动物学习心理学为起点。这条线路贯穿了人工智能的早期工作并导致了强化学习在二十世纪八十年代初的复兴。另一条线路则关注最优控制问题以及它使用值函数和动态规划的解决方案。大多数情况下第二个线路并不涉及学习问题。尽管这两条线路在很大程度上是的，但是有一个例外，就是围绕着上述两条线路并与之有细微差别的第三条线路，也就是本章在tic－tac－toe游戏中提到过的时间差分方法。所有这三条线路在二十世纪八十年代后期整合到了一起，形成我们在本书所提的现代强化学习领域。

我们最熟悉并且在本节历史简介中谈论最多的试错学习线路。但是我们在讨论试错学习线路之前，先简单地讨论一下最优控制这条线路。

“最优控制”这个术语最早是在二十世纪五十年代后期开始使用的，它描述的问题是如何设计一个控制器来随时间而最小化动态系统的行为计量。其中一个解决这个问题的方法是Richard Bellman于二十世纪五十年代中期发展起来的，而其他则是对Hamilton和Jacobi在十九世纪提出的方法的扩充。这种方法使用了动态系统中状态和值函数的概念，或者“最优回报函数”来定义一个函数方程，就是现在我们经常所说的Bellman方程。这一类用这个方程来解决最优控制问题的方法后来被称为动态规划（Bellman，1957a）。Bellman（Bellman，1957b）还引入了最优控制问题的离散随机版本，称为马尔可夫决策过程（MDPs），并且Ron Howard（1960）为MDPs引入了策略迭代的方法。所有这些都是现代强化学习理论和算法的本质要素。

动态规划被普遍认为是解决一般性随机最优控制问题的唯一可行方法。但是它受到被Bellman称为“维数灾”问题的困扰，这意味着随着状态数量的增加，它的计算需求量会呈指数级增长。尽管如此，它仍然比其他的一般方法更有效、适用性更广。动态规划在二十世纪五十年代末取得了广泛的发展，包括对部分感知MDPs的扩展（Lovejoy的综述，1991）、许多应用（White的综述，1985，1988，1993）、逼近方法（Rust的综述，1996）以及异步方法（Bertsekas，1982，1983）。许多出色的动态规划的现代处理方法纷纷涌现（例如Bertsekas，1995；Puterman，1994；Ross，1983；Whittle，1982，1983）。Bryson（1996）提供了一个最优控制的权威性历史介绍。

在本书我们把所有最优控制中的问题认为是某种意义上的强化学习问题。我们把任何能有效解决强化学习问题的方法都定义为强化学习，而且现在很清楚这些问题与最优控制问题密切相关，尤其是那些形式为MDPs的问题。因此，我们必须把最优控制的解决方法，如动态规划等也看成是强化学习方法。当然，几乎所有这些方法都需要控制系统的完整知识，由于这个原因似乎把它们看成是强化学习的一部分有些不自然。从另一方面讲，许多动态规划是增量和迭代。与学习方法一样，它们通过连续逼近而逐渐达到正确答案。就像我们在本书其余部分中将讲到的一样，这些相似性远不是表面的问题。这些基于完整和不完整知识的理论和解决方法是密切相关的，因此我们觉得它们必须放在一起作为同一主题来讨论更加合

简介Introduction

适。

现在我们再回到另一条主要线路上来，这条线路以试错学习为中心，导致了强化学习的兴起。该线路源于心理学，其中关于学习的“强化”理论是较常见的。可能第一个简明解释了试错学习本质的人是Edward Thorndike。我们把这个本质看成是这样一种思想：根据动作结果的好坏来改变动作选择的趋向。用Thorndike的话来说就是：

在同一场景的不同反应中，如果某些反应与动物的意志一致或密切相关或者达到其它类似效果，那么这个反应就与这个场景联系越紧密，这样当场景再次发生时，那些反应就越容易再发生；而对于那些与它们意志相反的反应或其他同样的事情，则它们的与这个场景的联系就会减弱，当该场景再次发生时，那些反应就越不容易再发生。满意或者不满意的程度越大，强化联系与削弱联系的作用就越大。（Thorndike，1911，p.244）

Thorndike把这个称作“效果法则”，因为它描述了强化事件在选择动作趋向时的效果。尽管有时有些争议（例如，见Kimble，1961，1967；Mazur，1994），但是这个效果法则仍然被公认为是许多行为的基本原理。

效果法则包括了我们所说的试错学习的两个重要方面。首先是选择性，意味着涉及到尝试各个选择对象并通过比较它们的结果来进行选择。其次是联系性，意味着通过选择所发现的选择对象与特定场景是有联系的。进化中的自然选择是选择过程的一个主要例子，但是它没有联系性。而监督学习有联系性，但是没有选择性。这两者的结合是效果法则和试错学习的本质。另一种说法是，效果法则是一种结合搜索和存储的基本方式：用试探形式进行搜索，并在每个场景的许多动作中进行选择，并且以记住表现最好的动作的形式来存储，把它们与最好场景联系起来。搜索和存储的结合是强化学习的本质。

通过编程使计算机试错学习的思想要追溯到最早的关于计算机和智能的思索（例如，Turing，1950）。最早关于试错学习的详细计算研究是由Minsky和Farley与Clark在1954年发表的。在Minsky的博士论文中，他讨论了强化学习的计算模型，并描述了他所构建的被他称为SNARCs（随机神经-模拟强化计算器）的由部件所组成的一个模拟机器。Farley和Clark描述了另一个被设计为试错学习的神经网络学习机器。二十世纪六十年代，“强化”和“强化学习”这样的术语在工程文献中首次被广泛使用（例如，Waltz和Fu，1965；Mendel，1966；Fu，1970；Mendel和McClaren，1970）。最有影响的是Minsky的论文“通往人工智能的阶梯”（Minsky，1961），这篇文章讨论了有关强化学习的几个问题，其中包括他称为信誉分配的问题：怎样在许多的、与产生成功结果有关的各个决策中分配信誉。从某种意义上讲，本书中我们所提到的所有方法都是直接针对并解决这些问题的。

Farley和Clark的兴趣从试错学习转向泛化和模式识别（1954；Clark和Farley，1955），也就是从强化学习转向监督学习。这引起了几种学习方法之间的关系混乱。许多研究者认为他们似乎在研究强化学习，然而实际上他们研究的是监督学习。例如，神经网络的先驱如

强化学习Reinforcement Learning

Rosenblatt（1962）和Widrow以及Hoff等人确实以强化学习为动机（他们使用了奖赏和惩罚的语言），但是他们研究的系统是适合模式识别和知觉学习的监督学习系统。即使在今天，许多研究者和教科书还经常混淆或者模糊这些学习类型之间的差异。一些现代神经网络教科书使用“试错”这个术语来描述从训练样本学习的网络，因为他们利用了误差信息来更新连接权值。这是一个可理解的概念混乱，但是它实际上丢失了试错学习中的选择性这样一个本质特征。

由于这些混乱原因，使得真正的试错学习在二十世纪六、七十年代研究得很少。在下面的几个段落中，我们要讨论这个趋势下的一些特例和部分性特例。

其中之一就是一个名为John Andreae的新西兰研究者的作品。Andreae（1963）开发了一个通过与环境交互进行试错学习的STeLLA系统。该系统包括了一个环境的内部模型，以及一个后来的用于处理隐藏状态的“内部独白”（Andreae，1969a）。Andreae后来的工作（1977）主要强调有教师的学习，但是仍包括试错。不幸的是，他的开创性研究并不广为人知，并且对后来的强化学习研究也没有多大影响。

比较有影响的是Donald Michie的工作。在1961和1963年，他描述了一个称为MENACE的学习玩tic－tac－toe（或井字游戏）的简单试错学习系统。它由一个对应每种可能游戏布局的方格组成，每个方格里有许多彩色的珠子，不同的颜色代表每一种从该布局可能的走棋。根据当前游戏布局随机取出方格里的一颗珠子，我们就能决定MENACE的走棋。游戏结束时，用珠子的增加或减少来增强或惩罚MENACE在游戏中的决策。Michie和Chambers（1968）描述了另一个称为GLEE的tic－tac－toe游戏的强化学习器和一个称为BOXES的强化学习控制器。他们把BOXES应用在平衡杆的学习任务中，在一辆可移动的手推车上竖立着一根杆子，当杆子倒下或手推车到达轨道末端就算作失败，以此失败信号为基础来平衡杆子。这个任务是从早期的Widrow和Smith的研究改编而来，他们使用的是监督学习方法，假设受到一个已经能够平衡杆子的教师指导。平衡杆任务的Michie和Chambers版本是早期最好的一个在不完整知识条件下的强化学习任务。它对于后来强化学习的研究有着深远的影响（Barto，Sutton，和Anderson，1983；Sutton，1984）。Michie一贯强调试错和学习在人工智能中的重要作用。

Widrow、Gupta和Maitra（1973）修正了Widrow和Hoff的的LMS算法来产生一个能从成功和失败的信号中学习而不是通过训练样本学习的强化学习规则。他们把这种学习称为“选择性bootstrap自适应”并把它描述为“有评论家的学习”而不是“有教师的学习”。他们分析了这个规则并且给出它是如何学习玩21点的。这是Widrow关于强化学习的一次初步尝试，对监督学习的贡献则是影响深远。

学习自动机（learning automata）的研究对导致现代强化学习研究的试错线路有着更直接的影响。这些方法解决的是一个非联系性、纯粹是选择性的学习问题，如模拟的n－臂机或者是“1－臂机”问题，不包括n个操纵杆的情况（见第2章）。学习自动

简介Introduction

机是解决此类问题的简单而又低存储量的机器。学习自动机始于俄罗斯的Tsetlin（1973）的研究，并且从那以后在工程学中得到了很大的发展（见Narendra和Thathachar，1974，19）。Barto和Anandan（1985）则将这些方法扩展到了联系性情况中。

John Holland（1975）以选择性原理为基础概述了自适应系统的一般理论。他的早期研究主要关注于非联系性形式的试错学习，如进化方法和n－臂机问题。1986年，他引入了分类器系统（classifier systems），这是一个真正的包含联系性和值函数的强化学习系统。Holland的分类器系统的关键组成部分通常是一个遗传算法（genetic algorithm），这是一种进化方法，使得有作用的表示得到进化。分类器系统已经被许多研究者充分发展为强化学习的一个重要研究分支（例如，见Goldberg，19；Wilson，1994），但是遗传算法（自身并不是强化学习系统）得到了更多的关注。

复兴人工智能中强化学习试错线路的最具代表性的个人是Harry Klopf（1972，1975，1982）。Klopf开始认识到，当学习的研究者几乎只关注监督学习时已经丢失了自适应行为的本质。根据Klopf的观点，所丢失的是行为的希求快乐的方面，即从环境中达到结果的驱动力，它控制着环境向预定目标发展而远离非预定目标。这个过程是试错学习的基本思想。Klopf的观点对其他作者有着非常大的影响，因为对这些观点的评价（Barto和Sutton，1981a）引起了我们对监督学习和强化学习之间区别的界定，最终使我们关注于强化学习。我们和同事完成的许多早期工作直接表明了强化学习和监督学习之间的实质性区别。其他研究则表明强化学习能够处理神经网络学习中的重要问题，尤其能够为多层网络产生学习算法（Barto，Anderson，和Sutton，1982；Barto和Anderson，1985；Barto和Anandan，1985；Barto，1985，1986；Barto和Jordan，1987）。

现在我们转向强化学习历史的第三条线路，也就是时间差分学习。时间差分学习方法与众不同的是它由对同一个量在时间上的连续估计之差来驱动——例如，tic－tac－toe游戏中的获胜概率。这条线路与其他两条线路的区别更小和更少，但是，在领域中却起到了相当重要的作用，部分原因似乎是因为时间差分方法对强化学习来说比较新颖而且唯一。

时间差分学习从某种程度上说源于动物学习心理，特别是次要强化刺激（secondary reinforcers）的概念。次要强化刺激是与主要强化刺激相配对的一个刺激，如食物或者是痛苦，而作为结果，具有同样的强化性质。Minsky（1954）第一个认识到这样的心理学原理可能对人工学习系统很重要。Arthur Samuel（1959）第一个提出并应用包含时间差分思想的学习方法，作为他著名的跳棋游戏程序的一部分。Samuel没有参考Minsky的研究或者可能的动物学习的联系。他的灵感似乎来自于Claude Shannon（1950）的提议：计算机可以用评估函数来编写下棋游戏，并通过在线修改该函数而改进游戏水平（可能Shannon的思想还影响了Bellman，但是我们没有这方面的证据）。Minsky（1961）在他的“阶梯”论文中详细讨论了Samuel的研究工作，提出了自然和人工的次要强化理论之间的联系。

如我们所描述的那样，在Minsky和Samuel的研究之后十年，关于试错学习的计算工

强化学习Reinforcement Learning

作就做的很少了，并且似乎时间差分学习的计算工作也基本上没有。1972年，Klopf将试错学习和时间差分学习的一个重要组成部分结合在一起。Klopf对能在大规模系统中自动调整的原理比较感兴趣，并且因此对局部强化这个概念引起了好奇心，其中整个学习系统的某个子系统可以强化另一个子系统。他发展了“广义强化”的思想，其中每个组成部分（又称为每个神经元）以强化术语来看待它的所有输入：兴奋输入作为奖赏，抑制输入作为惩罚。这与我们现在所知道的差分学习方法中的思想不太一样，而且与Samuel的研究也相去甚远。另一方面，Klopf把这个思想与试错学习结合起来并与大量动物学习心理学中的实验数据库联系起来。

Sutton（1978a，1978b，1978c）进一步发展了Klopf的思想，尤其是与动物学习理论的联系，该理论描述的学习规则由时间上的预测序列的改变所驱动。他和Barto改进了这些思想并提出了一个基于时间差分学习的经典条件的心理学模型（Sutton和Barto，1981a；Barto和Sutton，1982）。之后还有其他一些有影响的基于时间差分学习的经典条件的心理学模型（例如，Klopf，1988；Moore等人，1986；Sutton和Barto，1987，1990）。根据时间差分学习，当时提出的一些神经学模型得到了很好地解释（Hawkins和Kandel，1984；Byrne，Gingrich，和Baxter，1990；Gelperin，Hopfield，和Tank，1985；Tesauro，1986；Friston等人，1994），尽管大多数情况下它们没有历史上的联系。最近的一个将时间差分学习和神经学思想联系起来的概述是由Schultz，Dayan和Montague提出的。

我们关于时间差分学习的早期研究受到动物学习理论和Klopf工作成果的深刻影响。而与Minsky的“阶梯”论文以及Samuel的跳棋游戏程序之间的关系，似乎是在后来才意识到的。但是，到了1981年，我们充分认识到前面所提到的所有工作都是时间差分和试错线路的一部分。这时，我们提出一种在试错学习时使用时间差分学习的方法，称为行动者－评论家体系结构，并且将这个方法应用到Michie和Chambers的平衡杆问题中（Barto，Sutton，和Anderson，1983）。Sutton在他的博士论文中详细阐述了这种方法，而在Anderson的博士论文中扩展为使用反向传播神经网络方法。差不多同一时间，Holland也把时间差分方法应用到他的分类器系统中。1988年，Sutton做出了关键的一步，他把时间差分学习从控制论中出来，作为一个一般的预测方法，他的该文也介绍了TD(λ)算法并证明了它的收敛方面的属性。

1981年，当我们完成了行动者－评论家体系结构时，我们发现一篇Ian Witten所写的论文，里面包含了我们所知最早发表的时间差分学习规则。他提出了我们现在称为表格式TD(0)方法，做为解决MDPs的自适应控制器的组成部分。Wintten的研究是Andreae的STeLLA早期实验和其他试错学习系统的派生方法。因此，Wintten的1977年的论文是围绕强化学习研究的主要线路（试错学习和最优控制）展开的，这对早期的时间差分学习也确实做出了贡献。

最后，时间差分和最优控制线路在19年被Chris Watkins发展的Q学习完全结合到了

简介Introduction

一起。这项工作扩展并集成了前面所提到的所有三条强化学习研究线路。Paul Werbos（1987）从1977年起在讨论试错学习和动态规划的收敛性时，为这个集成工作做出了贡献。到Watkins做研究时，强化学习研究，主要在人工智能的机器学习子领域，也在神经网络和更多的人工智能领域都得到了巨大的发展。1992年，Gerry Tesauro的西洋双陆棋游戏程序TD－Gammon的成功更加引起了人们对这个领域的注意。其他一些近期历史上的强化学习的重要贡献也数不胜数，无法在本简介中一一提及；我们将单独在每一章的最后列出这些引用出处。

1.7文献目录评论

想要得到更多关于强化学习的信息，我们建议读者参考Bertsekas和Tsitsiklis（1996）以及Kaelbling（1993a）所著的书。关注于强化学习的两篇机器学习杂志的特刊文章：Sutton（1992）和Kaelbling（1996）的文章。以下这些人做了很有用的评述：Barto（1995b）；Kaelbling，Littman和Moore（1996）；以及Keerthi和Ravindran（1997）。

本章的Phil早餐问题可以参考Agre(1988)。我们建议读者直接参考第六章中的时间差分方法来解决所提的tic－tac－toe游戏。

现代强化学习中与神经系统相关的这类算法由Hampson（19），Friston等人（1994），Barto（1995a），Houk、Adams和Barto（1995），Montague、Dayan和Sejnowski（1996），以及Schultz、Dayan和Montague（1997）提出。