第 1章强化学习概述
学习是人类智能的重要表现之一，人之所以能适应环境的变化并不断提高解决问题的能力，其原因在于人能通过学习积累经验，总结规律，以增长知识和才能，从而更好地改善自己的决策与行为。使计算机具有学习的能力，模拟或实现人类学习活动为目的的机器学习，是人工智能的一个重要研究领域，它的研究对于人工智能的进一步发展有着举足轻重的作用。机器学习 (mAchine leArning)一般定义为一个系统的自我改进的过程，以知识的自动获取和产生为研究目标 [1]。机器学习的研究吸收了不同学科的成果和概念，包含了心理学、生理学、生物学、控制论、信息论、统计学以及人工智能在内的多种学科的交叉，具有很强的挑战性。
在机器学习范畴，依据从系统中获得反馈的不同，机器学习可以分为监督学习、无监督学习和强化学习三大类 [2]。
监督学习 (supervised leArning)，也称有导师的学习。这种学习方式需要外界存在一个 “教师 ”，它可对给定的一组输入提供应有的输出结果，而这种已知的输入–输出数据称为训练样本集，学习的目的是减少系统产生的实际输出和期望输出之间的误差，所产生的误差反馈给系统以指导学习。例如，在神经网络学习中，使用的是最小误差学习规则。在这种方法中，学习系统完成的是与环境没有交互的记忆和知识重组的功能。典型的监督学习方法包括以 BP算法为代表的监督式神经网络学习、归纳学习和基于实例的学习等。
无监督学习 (unsupervised leArning)，又称无导师学习。它是指系统在不存在外部教师指导的情形下来构建其内部表征。这种类型的学习完全是开环的，例如在自组织特征映射神经网络中，网络的权值调节不受任何外来教师指导，但在网络内部能对基性能进行自适应调节。无监督学习中，系统的输入仅包含环境的状态信息，而不存在与环境的交互。无监督学习方法主要包括各种自组织学习方法，如聚类学习、自组织神经网络学习等。
研究者发现，生物进化过程中为适应环境而进行的学习有两个特点：一是人从来不是静止的被动地等待，而是主动地对环境作试探；二是环境对试探动作产生的反馈是评价性的，生物根据环境的评价来调整以后的行为，是一种从环境状态到行为映射的学习，具有以上特点的学习就是强化学习 (reinforcement leArning)，或称再励学习、增强学习 [3,4]。
这里需要指出的是，强化学习是一种与监督学习、无监督学习对等的学习模式，而不是一种具体的计算方法，如神经网络、模糊推理、遗传算法等，但是这些计算方法可以与强化学习相结合。作为一种重要的机器学习方法，强化学习因不需要给定各种状态下的教师信号，则对于求解复杂的优化决策问题具有广泛的应用前景。
1.1强化学习模型及其基本要素
1.1.1强化学习模型
强化学习要解决的是这样的问题：一个能够感知环境的自治智能体 (Agent)，如何通过学习选择能够达到目标的最优动作，即强化学习 Agent的任务就是学习从环境到动作的映射。强化学习不同于连接主义学习中的监督学习，主要表现在教师信号上，强化学习中由环境提供的强化信号是对 Agent所产生动作的好坏作一种评价 (通常为标量信号 )，而不是告诉 Agent如何去产生正确的动作。由于外部环境提供了很少的信息， Agent必须靠自身的经历进行学习。通过这种方式， Agent在行动–评价的环境中获得知识，改进行动方案以适应环境。
Agent为适应环境而采取的学习如果具有如下特征，则称为强化学习。
(1) Agent不是静止的、被动的等待，而是主动对环境做出试探 [4]；
(2)
环境对试探动作反馈的信息是评价性的 (好或坏)；
(3) Agent在行动 –评价的环境中获得知识，改进行动方案以适应环境，达到预期目的。
强化学习把学习看做是试探的过程，标准的 Agent强化学习模型如图 1-1所示[3,4]。在图 1-1中，强化学习 Agent接收环境状态的输入 s，根据内部的推理机制，输出相应的行为动作 A。环境在动作 A的作用下，变迁到新的状态 s矿，同时产生一个强化信号 (立即回报 )r(奖励或惩罚 )反馈给 Agent，Agent根据强化信号和环境当前状态选择下一个动作，选择的原则是使受到正的回报的概率增大。选择的动作不仅影响立即回报值，而且影响下一时刻的状态及最终强化值。在学习过程中，强化学习技术的基本原理是：如果系统某个动作导致环境正的回报，那么系统以后产生这个动作的趋势便会加强，反之系统产生这个动作的趋势便减弱。这和生理学中的条件反射原理是接近的。
可以看出，Agent在与环境进行交互时，在每一时刻循环发生如下事件序列：
(1) Agent感知当前的环境状态 s；
(2)
针对当前的状态和强化信号值，Agent选择一个动作 A执行；
(3)当 Agent所选择的动作作用于环境时，环境发生变化，即环境状态转移至新状态 s矿并给出强化信号 r；
(4)强化信号 r反馈给 Agent。
图 1-1强化学习模型
强化学习具有如下特点[3]：
(1)
强化学习是一种弱的学习方式，体现为： Agent通过与环境不断地试错交互来进行学习；强化信号可能是稀疏且合理延迟的；不要求 (或要求较少 )先验知识； Agent在学习中所使用的反馈是一种数值回报形式，不要求有提供正确答案的教师，即环境返回的强化信号是 r，而不像监督学习中给出的教师信号 (s, A)；
(2)
强化学习是一种增量式学习，并可以在线使用；
(3)
强化学习可以应用于不确定性环境；
(4)
强化学习的体系结构是可扩展的。目前，强化学习系统已扩展至规划的合并、智能探索、监督学习和结构控制等领域。
1.1.2强化学习基本要素
由强化学习模型可以看出，一个强化学习系统除了 Agent和环境之外，主要还有 4个基本元素：策略、值函数、回报函数和环境模型 (非必需 )。这 4个基本元素及其关系如图 1-2所示 [5]。强化学习系统所面临的环境由环境模型定义，但由于模型中状态转移概率函数和回报函数未知， Agent只能够依赖于每次通过试错所获得的立即回报来选择策略。而在选择行为策略过程中，要考虑到环境模型的不确定性和目标的长远性，因此在策略和立即回报之间构造值函数 (即状态的效用函数 )，用于策略的选择。
图 1-2强化学习基本要素及其关系
1.策略
策略 (policy)定义了 Agent在给定时刻的行为方式，直接决定了 Agent的动作，是强化学习的核心。策略的定义如下：
定义 1.1(策略 ) Agent在与环境交互过程中选择动作的方法称为策略 π : S × A → [0, 1]，S为状态空间， A为动作空间， π(s, A)表示在状态 s下选择动作 A的概率。策略的一个退化形式为 π : S → A，称为确定性策略，表示在状态 s下动作 π(s)的执行概率为 1，其他动作的概率执行均为 0。
关于任意状态所能选择的策略组成的集合 F，称为允许策略集合， π ∈ F。在允许策略集合中存在的使问题具有最优效果的策略 π.称为最优策略。策略与心理学中的刺激 –反射 (stimulus-response)规则相对应，在某些情况下策略可能是一个简单的函数或者查找表 (lookup tAble)；而在另一些情况下则可能需要大量的计算，例如搜索过程等。强化学习方法确定了 Agent怎样根据经验改变其策略。
2.回报函数
回报函数 (rewArd function)定义了一个强化学习问题的目标，它将感知的环境状态 (或状态 –动作对 )映射到一个强化信号 r，对产生的动作的好坏作一种评价。强化信号通常是一个标量，例如用正数表示奖赏，而用负数表示惩罚。强化学习的目的就是使 Agent最终得到的总的回报值达到最大。回报函数往往是确定的、客观的，可以作为改变策略的标准。
3.值函数
回报函数表明眼前哪些是好的，是一种 “近视 ”的表达信号，而值函数 (vAlue function)(即状态的效用函数，又称评价函数 )则是 “远视 ”的表征，它表达了从长远的角度来看哪些是好的。状态的值所表示的意义，大致来说，是从该状态起智能体所能积累的回报的总和。回报是环境给出的立即评价，而值函数则是随后一系列状态所对应的回报的累积。回报和值函数的联系是：没有回报就没有值函数，估计值函数的目的是为了获得更多的回报。举例来说，一个状态可能产生一个较低的立即回报，但是从长远看来可能会带来丰厚的回报和。因此，在选择行为时，通常会依据值函数做出决策而不是回报函数。选择那些能带来最大值函数的行为，而不是选择那些能带来最大回报的行为。但如何确定值函数要比确定回报函数困难得多，回报通常是由环境直接给出的，但值函数一般来说要进行估计。事实上，几乎所有强化学习算法的核心都是如何有效地估计值函数。
4.环境模型
环境模型 (model of environment)是某些强化学习系统的一个可选的组成部分。环境模型就是模拟环境的行为方式。例如，给定一个状态和动作，模型可以预测下一个状态和回报。利用环境的模型， Agent在做决策的同时可以考虑未来可能发生但尚未实际经历的情形，从而进行规划 (plAnning)。将模型和规划加入到强化学习系统是一个比较新的发展方向，它联系了强化学习与动态规划等其他基于模型或部分模型的方法，形成了一些较实用的新方法。
1.2强化学习的发展历史
强化学习的发展主要包括 3条主线：试错 (triAl-And-error)学习、动态规划与最优控制和时间差分 (temporAl di.erence，TD)学习 (图 1-3)。在经历了各自不同的进程之后，最终在 20世纪 80年代形成了现代强化学习的基本框架[6,8]。
图 1-3强化学习的发展主线
1.2.1试错学习
第一条主线源于动物学习的心理学，通过试错达到学习的目的。这条主线贯穿于人工智能早期的研究工作中，也是使 20世纪 80年初期强化学习复苏的重要因素。最早简洁表述 “试错学习 ”的是 Thorndike，他于 1911年提出了 “响应定律”(lAw of e.ect)。Thorndike[9]认为： “对于同一环境所做的几个响应，当那些伴随或紧跟着的响应使动物意愿得到满足且其他的条件相同时，对环境的联系将会被加强，所以，当环境重现时，这些响应重现的概率将更大。当那些同时或紧跟着的响应使动物的意愿受挫且在相同的其他条件下，与环境的联系将会削弱，所以，当环境重现时，它们出现的概率将越小。得到的满足程度越大，响应和环境的联系加强得越多。而不满足的程度越大，响应与环境的联系削弱得越多。 ”
从上述描述可以看出， Thorndike思想的本质是：强调行为的结果有优劣之分并成为行为选择的依据，同时指出能够导致正回报的行为选择概率将增加，而导致负回报的行为选择概率则降低。 Thorndike的思想包含了试错的 2个重要特点：选择性和联想性。选择性就是尝试学习不同动作并比较不同结果；联想性是指将可选择的动作与特定的状态联系在一起。进化学习中的自然选择具有选择性，但不具有联想性；监督学习则仅具有联想性而不具有选择性。另外， “响应定律 ”还反映了强化学习的另两个重要特性，即搜索和记忆。
虽然在心理学和其他学科上，响应定律都曾引起过非常多的争论，但是这些年来，由于其基本思想已被实验所证实，而且从直觉上看非常正确，所以该定律十分具有影响力。这是一种将搜索与记忆相结合的方法，它能够在多种试验动作中搜索，然后记住效果最好的动作。相对于监督学习原则来说， “响应定律 ”是一种依靠选择的学习原则。
最早进行试错学习研究的可能是 Minsky、FArley和 ClArk等于 1954年开始的。 Minsky在他的博士论文中描述了一种叫作 SNARC(stochAstic neurAl-AnAlog reinforcement cAlculAtor)的模拟机 [10]，而 FArley和 ClArk提出了另一个神经网络学习机。 1961年， Minsky进一步讨论了几个与强化学习相关的主题，如信度分配问题 (credit Assignment problem)，这个问题是强化学习必须涉及的，也是至今学者研究最多的难点 [11]。后来， WAltz和傅京逊于 1965年， Mendel于 1966年在工程文献中较早地引用了 “强化 ”和 “强化学习 ”等概念 [12]。1955年， FArley和 ClArk由 “试错学习 ”转向泛化和模式识别的研究，即由强化学习转向监督学习，开始了强化学习和监督学习的混合研究状态 [4]。Widrow及其同事们在研究监督学习的时候，认识到监督学习和强化学习之间的不同。 1973年， Widrow、GuptA和 MAitrA改正了 Widrow和 Ho.的监督学习规则 (常称为 LMS规则 )得到新的学习规则。新规则可实现强化学习，即根据成功和失败的信号进行学习，代替了原来的使用训练样本进行学习的方法，他们用 “有评价的学习 ”一词代替 “有教师的学习 ”[13]。另外，学习自动机对由试错学习发展起来的现代强化学习有着重要的影响，其中较为著名的有 1973年 Tsetlin的工作，以及 BArto和 AnAndAn发展的具有联想的学习自动机 [4]。不过大部分早期的研究工作，主要是显示强化学习和监督学习的不同。
1.2.2动态规划与最优控制
第二条主线是利用值函数和动态规划方法求解最优控制问题。最优控制一词在 20世纪 50年代末被用来描述为最小化动态系统行为的量度值而设计控制器的问题 [14]。这种方法将动态系统的状态和值函数的概念用于定义函数方程 (现在通常被称为 BellmAn方程 )。这类通过求解 BellmAn方程来解决最优控制问题的方法被称为动态规划。动态规划在过去的几十年中已取得了极大的发展，被广泛地认为是求解一般随机最优控制问题的唯一切实可行的方法。但是，动态规划存在 BellmAn所谓的 “维数灾难 ”(curse of dimensionAlity)的问题，也就是说，动态规划的计算量需求随状态变量数目的增加而呈指数级增长。但较其他方法而言，动态规划仍是一个非常有效且应用广泛的方法。动态规划方法与强化学习密切相关，对于马尔科夫决策问题 (MArkov decision process，MDP)，前者主要解决环境的状态转移概率和
展开
