《强化学习概述(共23页).doc》由会员分享，可在线阅读，更多相关《强化学习概述(共23页).doc（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上第四章 强化学习4.1 强化学习概述智能系统的一个主要特征是能够适应未知环境，其中学习能力是智能系统的关键技术之一。在机器学习范畴内，根据反馈的不同，学习技术可以分为监督学习（Supervised learning）、非监督学习（Unsupervised learning）和强化学习（Reinforcement learning）三大类。其中强化学习是一种以环境反馈作为输入的、特殊的、适应环境的机器学习方法。强化学习又称为增强学习、加强学习、再励学习或激励学习，是一种从环境状态到行为映射的学习，目的是使动作从环境中获得的累积回报值最大。强化学习的思想来源于动物学习心理
2、学。观察生物(特别是人)为适应环境而进行的学习过程，可以发现有两个特点:一是人从来不是静止地被动等待而是主动对环境做试探，二是环境对试探动作产生的反馈是评价性的，人们会根据环境的评价来调整以后的行为。强化学习正是通过这样的试探评价的迭代，在与环境的交互中学习，通过环境对不同行为的评价性反馈信号来改变强化学习系统(RLS或者称为Agent)的行为选择策略以实现学习目标。来自环境的评价性反馈信号通常称为奖赏值(reward)或强化信号（reinforcement Signal)，强化学习系统的目标就是极大化(或极小化)期望奖赏值。强化学习技术是从控制理论、统计学、心理学等相关学科发展而来，最早可以
3、追溯到巴普洛夫的条件反射实验。但直到上世纪八十年代末、九十年代初强化学习技术才在人工智能、机器学习和自动控制等领域中得到广泛研究和应用，并被认为是设计智能系统的核心技术之一。特别是随着强化学习的数学基础研究取得突破性进展后，对强化学习的研究和应用日益开展起来，成为目前机器学习领域的研究热点之一。强化学习围绕如何与环境交互学习的问题，在行动评价的环境中获得知识改进行动方案以适应环境达到预想的目的。学习者并不会被告知采取哪个动作，而只能通过尝试每一个动作自己做出判断。它主要是依靠环境对所采取行为的反馈信息产生评价，并根据评价去指导以后的行动，使优良行动得到加强，通过试探得到较优的行动策略来适应环境
4、。试错搜索和延迟回报是强化学习的两个最显著的特征。但强化学习系统还具有以下更一般的特点：(1) 适应性，即Agent不断利用环境中的反馈信息来改善其性能；(2) 反应性，即Agent可以从经验中直接获取状态动作规则；(3) 对外部教师信号依赖较少。因为Agent只根据强化信号进行学习，而强化信号可从Agent内置的强化机制中获得。一个智能系统面临的环境往往是动态、复杂的开放环境。因此首先需要设计者对环境加以细分。通常情况，我们可以从以下五个角度对环境（或问题）进行分析。表4.1 环境的描述角度1离散状态 vs 连续状态角度2状态完全可感知 vs 状态部分可感知角度3插曲式 vs 非插曲式角度4
5、确定性 vs 不确定性角度5静态vs 动态表4.1中，所谓插曲式（episodic）是指智能系统在每个场景中学习的知识对下一个场景中的学习是有用的。如一个棋类程序对同一个对手时，在每一棋局中学习的策略对下一棋局都是有帮助的。相反非插曲式（non-episodic）环境是指智能系统在不同场景中学习的知识是无关的。角度4是指智能系统所处的环境中，如果状态的迁移是确定的，则可以唯一确定下一状态。否则在不确定性环境中，下一状态是依赖于某种概率分布。进一步，如果状态迁移的概率模型是稳定、不变的，则称之为静态环境；否则为动态环境。显然，最复杂的一类环境（或问题）是连续状态、部分可感知、非插曲式、不确定的动
6、态环境。4.2 强化学习原理一个强化学习系统的基本框架主要由两部分组成，即环境和智能体（Agent）。智能体可以通过传感器（Sensor）感知所处环境，并通过执行器（Actuator）对环境施加影响。从广义上讲，除该智能体之外，凡是与该智能体交互的物体，都可以被称为环境。强化学习是智能体在与动态环境的交互过程中，通过反复试错来学习适当的行为。它介于监督式学习（supervised learning）和无监督式（unsupervised learning）学习之间，是一种策略相关学习，通过与环境的即时交互来获得环境的状态信息，并通过反馈强化信号对所采取的行动进行评价，通过不断的试错和选择，从而学
7、习到最优的策略。强化学习的基本原理是：如果智能体（Agent）的某个行为策略导致环境对智能体正的奖赏（Reward），则智能体以后采取这个行为策略的趋势会加强。反之，若某个行为策略导致了负的奖赏，那么智能体此后采取这个动作的趋势会减弱。图4.1描述了环境与智能体进行交互的一个基本框架。在图4.1中给出的强化学习过程中，Agent不断地与环境进行交互，在每一时刻循环发生如下事件序列：(1) Agent感知当前的环境状态；(2) 针对当前的状态和强化值，Agent选择一个动作执行；(3) 当Agent所选择的动作作用于环境时，环境发生变化，即环境状态转移至新状态并给出奖赏（强化信号）；(4) 奖赏
8、（强化信号r）反馈给Agent。Agent环境奖赏值 R状态 S动作 Action图4.1 强化学习框架图强化学习的过程可以总结如下：Agent 选择一个动作a作用于环境，环境接收该动作后发生变化，同时产生一个强化信号（奖或罚）反馈给Agent，Agent再根据强化信号和环境的当前状态s 再选择下一个动作，选择的原则是使受到正的奖赏值的概率增大。选择的动作不仅影响立即奖赏值，而且还影响下一时刻的状态及最终强化值。强化学习的目的就是寻找一个最优策略，使得Agent在运行中所获得的累计奖赏值最大。强化学习作为一种以环境反馈作为输入的、特殊的、适应环境的机器学习方法，具有如下特点：（1）强化学习是一
9、种弱的学习方式，体现为：Agent通过与环境不断的试错交互来进行学习；强化信息可能是稀疏且合理延迟的；不要求（或要求较少）先验知识；Agent在学习中所使用的反馈是一种数值奖赏形式，不要求有提供正确答案的教师；（2）强化学习是一种增量式学习，并可以在线使用；（3）强化学习可以应用于不确定性环境；（4）强化学习的体系结构是可扩展的。目前，强化学习系统已扩展至规划合并、智能探索、监督学习和结构控制等领域。4.3 强化学习系统的主要组成要素 图4.2 强化学习四要素如图4.2所示，除了Agent和环境，一个强化学习系统还有四个主要的组成要素：策略、奖赏函数、值函数以及可选的环境的模型。（1）策略（P
10、olicy）策略也称决策函数，规定了在每个可能的状态，Agent应该采取的动作集合。策略是强化学习的核心部分，策略的好坏最终决定了Agent的行动和整体性能，策略具有随机性。策略描述针对状态集合S中的每一个状态s，Agent应完成动作集A中的一个动作a，策略：SA是一个从状态到动作的映射。关于任意状态所能选择的策略组成的集合F，称为允许策略集合，F。在允许策略集合中找出使问题具有最优效果的策略*，称为最优策略。（2）奖赏函数（Reward Function）奖赏函数是在与环境交互的过程中，获取的奖励信号，奖赏函数反应了Agent所面临的任务的性质，同时，它也可以作为Agent修改策略的基础。奖
11、赏信号R是对所产生动作的好坏作一种评价，奖赏信号通常是一个标量信号，例如用一个正数表示奖，而用负数表示罚，一般来说正数越大表示奖的越多，负数越小表示罚的越多。强化学习的目的就是使Agent最终得到的总的奖赏值达到最大。奖赏函数往往是确定的、客观的，为策略的选择提供依据。（3）值函数（Value Function）奖赏函数是对一个状态（动作）的即时评价，值函数则是从长远的角度来考虑一个状态（或状态-动作对）的好坏。值函数又称为评价函数。状态st的值，是指Agent在状态st根据策略执行动作at及采取后续策略所得到的积累奖赏的期望，记为。例如，将定义为所有将来奖赏值通过衰减率(0,1)作用后的总和
12、。(4-1)其中，为t时刻的奖赏。对于任一策略，定义值函数为无限时域累积折扣奖赏的期望值，即(4-2)其中，和分别为在时刻t的立即奖赏和状态，衰减系数(0,1)使得邻近的奖赏比未来的奖赏更重要。Q函数是另一种评价函数。在某些时候，记录状态-动作对的值比只记录状态的值更有用，Watkins把状态-动作对的值称为Q值。Q函数的定义：表示在状态s执行动作a，及采取后续策略的折扣奖赏和的期望。可以看出，状态值（Q值）是对奖赏的一种预测，对于一个状态s，如果它的奖赏值低，并不意味着它的状态值（Q值）就低，因为如果s的后续状态产生较高的奖赏，仍然可以得到较高的状态值（Q值）。估计值函数的目的是得到更多的奖
13、赏，然而动作的选择是基于状态值（Q值）判断的。也就是说，Agent选择这样一个动作，以使产生的新状态具有最高状态值（Q值），而不是转移到新状态时有最高的即时奖赏，因为从长远看，这些动作将产生更多的奖赏。然而确定值函数要比确定奖赏难很多，因为奖赏往往是环境直接给定，而状态值（Q值）则是Agent在其整个生命周期内通过一系列观察，不断地估计得出的。事实上，绝大部分强化学习算法的研究就是针对如何有效快速的估计值函数。因此，值函数是强化学习算法的关键。（4）环境的模型环境模型是对外界环境状态的模拟，Agent在给定状态下执行某个动作，模型将会预测出下一状态和奖励信号。利用环境的模型，Agent在作决策
14、的同时将考虑未来可能的状态，进行规划。早期的强化学习主要是一种试错学习，与规划大相径庭的。将模型与规划引入强化学习系统是强化学习的一个较新的发展，使得强化学习方法与动态规划方法紧密的联系起来了。强化学习将试错学习和规划都看成获得经验的一个过程。强化学习的四个元素之间的关系如图4.3所示。PolicyRewardValueModel of Environment图4.3 强化学习主要元素关系图4.4 马尔科夫决策过程（MDP）在强化学习技术中首先对随机的、离散状态、离散时间这一类问题进行数学建模。在实际应用中，最常采用的是马尔可夫模型。表4.2中给出最常用的几种马氏模型。表4.2 常用的几种马氏
15、模型马氏模型是否智能系统行为控制环境状态转移？否是是否环境为部分可感知？否马尔可夫链马氏决策过程是隐马尔可夫模型部分感知马氏决策过程很多强化学习问题基于的一个关键假设就是Agent与环境间的交互可以被看成一个马尔可夫决策过程(MDP)，因此强化学习的研究主要集中于对Markov问题的处理。马尔可夫决策过程的本质是：当前状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。在强化学习过程中，智能体通过观察其与环境交互改善自己的行为。为了方便起见，假定在时刻点t=1，2，3，处观察某个系统，一个有限的Makrov决策过程由5元组组成：其中各个元的含义如下：(1)
16、 s为系统所有可能的状态所组成的非空集，有时也称为系统的状态空间，它可以是有限的、可列的或任意非比空集。在本文中，假定S为有限的，用小写字母s,等来表示状态。(2) 对sS，A(s)是在状态s下所有可能动作集合。(3) 当系统在决策时刻点t处于状态s，执行动作a之后，则系统在下一个决策时刻点t+1时处于状态s的概率为p(s,a,)。称P=p(s,a,)为转移概率矩阵。(4) 当系统在决策时刻点t处于状态s，执行决策a后，系统于本段情节获得的报酬为r(s,a)，常称R=r(s,a)为报酬函数。(5) V为准则(Crietrion)函数(或目标(Objective)函数)，常用的准则函数有期望折扣
17、总报酬、期望总报酬和平均报酬等。若转移概率函数p(s,a,)和报酬函数r(s,a)与决策时刻t无关，即不随时间段的变化而变化，则称是平稳的，此时MDP称为平稳的MDP。当系统在决策时刻点t处于状态，选取的决策为，系统在本段情节获得的报酬为。MDP的历史为由相继的状态和决策组成，其形式为 (4-3)称为系统到时刻t时的一个历史，其全体为H。系统的一个策略是指一个序列，当系统到达某个时刻t时该策略按A()上的概率分布 采取决策。如果了满足条件： (4-4)即(4-4)与历史完全无关，则称(4-4)为Makrov策略。给定策略，为t时刻获得报酬，几种常用准则函数定义如下：(1) 有限时段期望总报酬为
18、： (4-5)这里，N为时段数。在强化学习中，经常讨论无限时段或时段数是随机时的情形。无限时段期望总报酬为: (4-6)当N趋向无穷大时就演变为无限时段，但是可能会发散，所有很少考虑。(2) 无限时段期望折扣总报酬为： (4-7)(3) 期望平均报酬为： (4-8)在以下假设存在的情况下，这个极限是存在的：(1) S是有限的；(2) 是Markov性的和平稳的；(3) 在下MDP是非周期的。定义动作值函数为： (4-9)强化学习的最终目标是发现最优策略，一个从状态集到行动集的映射，以达到最大折扣总报酬。最优策略可以通过鉴别最优值函数而获得。最优值的定义为： (4-10)也可以递归定义为： (4
19、-11)由此可得出最有策略： (4-12)最优动作值函数为： (4-13)从Q值就可以得出最优策略 (4-14)方程4-13和4-14也称为Bellman最优方程，解此方程有各种各样的动态规划方法，如值迭代、策略迭代等。4.5 强化学习的主要算法4.5.1动态规划（Dynamic Programming）在基于MDP模型的环境模型已知的情况下，寻求最优策略的方法统称为动态规划。常规的动态规划方法主要有以下三种：第一种是值函数迭代法，其本质是有限时段的动态规划算法在无限时段上的推广，是一种逐次逼近算法；第二种是策略迭代，这是一种基于Bellman最优方程的算法；第三种是改进的策略迭代法，综合了前
20、面两种算法，也称为一般化策略迭代法，是许多强化学习算法的基本思想来源之一。在动态规划技术中，在已知状态转移概率函数P和奖赏函数R的环境模型知识前提下，从任意设定的策略出发，可以采用策略迭代的方法（式4-15和式4-16）逼近最优的V*和*，如图4.2中的虚线所示。式4-15和式4-16中的k为迭代步数。 （4-15） （4-16）4.5.2蒙特卡罗算法（Monte Carlo Methods）Monte Carlo（简称MC）方法是一种无模型（model-free）的学习方法，不需要系统模型-状态转移函数和报酬函数，只需要通过与环境的交互获得的实际或模拟样本数据（状态、动作、奖赏）序列，从而发
21、现最优策略。MC方法是基于平均化样本回报值来求解强化学习问题的一种方法。由于在无模型强化学习方法中，P函数和R函数未知，系统无法直接通过（4-15）式、（4-16）式进行值函数计算。因而Monte Carlo采用逼近的方法进行值函数的估计，如（4-17）式。其中是指当系统采用某种策略，从状态出发获得的真实的累计折扣奖赏值，。保持策略不变，在每次学习循环中重复地使用（4-17）式，下式将逼近（4-6）式。 （4-17）给定策略，来估计。假定存在终止状态，任何策略都以概率1到达终止状态，而且是在有限步内到达。为了估计值函数，我们需要多次执行策略，并把每一次从开始状态到达终止状态的过程称为一个片段（
22、episode），如图4.4所示。图4.4 MC算法回溯图这个回溯图就是一个片段。当环境状态为终止状态时，将得到的积累回报赋予开始状态s的值函数。从s出发到终止状态t的过程中，s可能出现不止一次，主要的对s的值函数的更新就至少有两种方法：一种是FVMC(first visit MC)，另一种是EVMC(every visit MC)。前者将回报赋予第一次访问的s，后者是将每次访问s到终止状态t的回报平均后赋予s的值函数。二者在理论上是有区别的，但他们都收敛于。MC除了有以上提到的优点外，它在计算一个状态的值函数时不依赖于其它状态的值函数，而恰恰某些问题只需要求解部分状态的值函数，这样可以只计算
23、我们感兴趣的状态。MC算法的另一个优点是它对马尔可夫性要求不是很严格。4.5.3瞬时差分(Temporal Difference, TD)算法TD算法是MC和DP的融合，与MC相似的是它可以直接从原始经验学起，完全不需要外部环境的动力学信息。根据不同的更新公式，可以得到不同的TD学习算法，其中最简单的TD算法是TD(0)算法，其修正公式如下：（4-18）上式中参数称为学习率（或学习步长），为折扣率。实际上在这里，TD的目标是，的更新是在的基础上，就像动态规划对某一状态值函数进行计算时依赖于其后续状态的值函数一样，可以说是一种步步为营的方法。在TD(0)策略赋值中，类似于MC利用样本回报值作为目
24、标值，只不过TD(0) 不需要等到一个片段结束才对值函数进行更新，它在下一时刻点就可以利用下一状态的值函数与即时报酬之和作为目标值进行更新。TD算法中最简单的TD(0)算法的回溯图如图4.5所示。图4.5 TD(0)算法回溯图TD(0)算法如下：Initialize arbitrarily, to the policy to be evaluatedRepeat (for each episode):Initialize s Repeat (for each step of episode):a action given byfor sTake action a; observe reward
25、 r, and next state suntil s is terminal图4.6 TD(0)算法4.5.4 DP、MC和TD方法的比较图4.7比较了动态规划技术、Monte Carlo方法和强化学习方法计算状态值函数的异同。图4.7（a）中，动态规划方法考察环境的概率模型，从而用（4-16）式Bootstrapping方法计算所有可能分支所获得奖惩返回值的加权和；图4.7（b）中，Monte Carlo方法采样一次学习循环所获得的奖惩返回值。然后通过多次学习，用实际获得的奖惩返回值去逼近真实的状态值函数。逼近公式即前述的（4-17）式；图4.7（c）中，TD方法和Monte Carlo方
26、法类似，仍然采样一次学习循环中获得的瞬时奖惩反馈，但同时类似与动态规划方法采用Bootstrapping方法估计状态的值函数。然后通过多次迭代学习，采用（4-18）式去逼近真实的状态值函数。图4.7中蓝线表示每种方法计算值函数时所需要的信息。（a）动态规划方法 （b）Monte Carlo方法 （c）TD方法图4.7 三种不同的计算值函数方法4.5.5 Q学习(Q-Learning)Q学习是由Watkins提出的一种模型无关的强化学习算法，主要求解马尔可夫决策过程MDP环境模型下的学习问题。Watkins于1989年提出并证明收敛性之后，该算法受到普遍关注。单步Q-Learning是简单地从动
27、态规划理论发展而来的，是一种延迟学习的方法。在Q-Learning中，策略和值函数用一张由状态-动作对索引的二维查询表来表示。对于每个状态x和动作a：(4-19)其中，是对状态x执行动作a导致状态转移到y的概率。等式（4-19）符合下面的等式：。Q-Learning算法维护函数的估计值（用表示），它根据执行的动作和获得的奖赏值来调整值（经常简单地叫做值）。值的更新根据Sutton的预测偏差或TD误差即时奖赏时加上下一个状态的折扣值与当前状态-动作对的值的偏差： (4-20)其中，r是即时奖赏值，y是在状态x执行动作a迁移到的下一个状态，。所以，值根据下面的等式来更新：(4-21)其中，是控制学
28、习率的参数，指明了要给相应的更新部分多少信任度。Q-Learning算法使用TD(0)作为期望返回值的估计因子。注意到函数的当前估计值由定义了一个贪婪策略，也就是说，贪婪策略根据最大的估计Q值来选择动作。然而，一阶Q-Learning算法并没有明确指出在每个状态更新它的估计值时Agent应该执行什么样的动作。事实上，所有动作都有可能被Agent执行。这意味着在维护状态的当前最好的估计值时，Q-Learning允许采取任意的实验。更近一步，自从根据状态表面上最优的选择更新了函数之后，跟随那个状态的动作就不重要了。从这个角度来讲，Q-Learning算法不是实验敏感的。为了最终发现最优的Q函数，A
29、gent必须把每个状态的所有可采取的动作试验很多次。实验表明，如果等式(4-21)任意的顺序被重复应用于所有的状态-动作对，使得每个状态-动作对的Q值更新次数达到无穷大，那么将会收敛于，将会收敛于，只要以合适的速率降到0，收敛的概率就是1。Q学习的回溯图如图4.8所示。图4.8 Q学习回溯图一个典型的单步Q学习算法如图4.9所示。Initialize arbitrarilyRepeat (for each episode):Initialize sRepeat (for each step of episode):Choose a from s using policy derived fro
30、m Q (e.g., -greedy)Take action a, observe Until s is terminal图4.9 单步Q学习算法4.5.6 Q学习算法的改进Q学习的目标是学习在动态环境下如何根据外部评价信号来选择较优动作或者最优动作，本质是一个动态决策的学习过程。当Agent对环境的知识一点也不了解时，它必须通过反复试验的方法来学习，算法的效率不高。有时在未知环境中的学习也会冒一定的风险，减少这种风险的一种方法就是利用环境模型。而环境模型可以利用以前执行相关的任务时获得的经验建立，利用环境模型，可以便于动作的选择，而不冒被伤害的危险。环境模型是从状态和动作到下一状态及强化值的
31、函数。模型的建立有以下两种方法：一是在学习的初始阶段，Agent利用提供的数据来离线地建立模型；二是Agent在与环境交互过程中在线地建立或完善环境模型。基于经验知识的Q学习算法是在标准的Q学习算法中加入具有经验知识的函数，此函数影响学习过程中Agent动作选择，从而加速算法收敛速度。经验(experience)用一个四元组来表示，它表示在状态时执行一个动作，产生一个新的状态，同时得到一个强化信号。改进算法中的经验函数中记录状态s下有关执行动作a的相关的经验信息。在算法中加入经验函数的最重要的问题是如何在学习的初始阶段获得经验知识，即如何定义经验函数。这主要取决于算法应用的具体领域。例如在Ag
32、ent路径寻优环境中，当Agent与墙壁发生碰撞时，就可获取到相应的经验知识。即Agent在与环境交互过程中在线地获得关于环境模型的经验知识。Initialize Q(s, a).Repeat:Visit the s state.Select an action a using the action choice ruleReceive r(s, a) and observe the next state Update the values of Q(s, a) according to:Update the s to state.Until some stop criteria is rea
33、ched.Where: 图4.10 基于经验知识的Q学习算法基于经验知识的Q学习算法将经验函数主要应用在Agent行动选择规则中，动作选择规则如下式： (4-22)其中，为一常数，代表经验函数的权重。基于经验知识的Q学习算法如图4.10所示，与标准的Q学习算法比较，可以发现该算法仅在动作选择的策略上有所不同。4.5.7 Q()学习算法Watkinss Q()和Pengs Q()是两种结合“Eligibility traces”和Q学习的不同方法，它们的命名是根据首先提出它们的研究者的姓名而来的。4.5.7.1 Watkinss Q()-Learning算法Q学习是一个策略无关的方法，也就是说用
34、于学习的策略可以不同于用于选择动作的策略。Q-学习方法在学习一个贪心策略时，会采用一种探索性的策略它不时会根据选择次优的动作。假设我们在t时刻更新状态-动作对，并且假设在下两个步骤中Agent选择的是贪心动作（获得即时奖赏值最大的动作），但是在第3个步骤，即时刻t+3时，Agent选择了一个探索性的非贪心动作。在学习贪心策略中的值的时候，只要后面跟随的是贪心策略，我们就可以使用后继的经验。因此，我们可以使用下一步和下两步的返回值，但是在这个情况下，第3步的返回值就不能用了，并且当n3时，所有第n步的返回值对当前贪心策略来说是没有利用价值的。因此，与TD()和Sarsa()不同，Watkinss
35、 Q()不会一直考虑一个阶段结束前的所有步，它只考虑到下一个探索性的动作为止。但是，除了这点不同以外，Watkinss Q()和TD()以及Sarsa()是类似的。TD()和Sarsa()会考虑到未来的所有步，直到一个阶段结束为止，而Watkinss Q()在遇到第一个探索性的动作时停止，或者如果这个阶段没有探索性的动作，它也会在这个阶段结束时停止。更确切地说，Watkinss Q()会利用第一个探索性动作的下一个动作的值来更新那个探索性动作。例如，假设第一个动作at+1是探索的，Watkinss Q()仍然会更新一步来向靠拢。通常，如果是第一个探索性动作，那么最长的后备更新值就是： 图4.1
36、1 Watkinss Q()的回溯图这里我们假设更新是策略无关的。图4.11中的回溯图解解释了Watkinss Q()的预测观点，描述了所有组成部分的回溯情况。Watkinss Q()的追溯机制也十分简单。除了要把探索（非贪心）动作发生时的Eligibility traces设置成0以外，Eligibility traces的使用与Sarsa()中的一样。Trace的更新最好发生在两步以内。首先，所有状态-动作对的trace或者以衰减，或者在遇到探索动作时被设置成0。其次，当前状态和动作的trace最后增加1。于是得到： (4-23)其中，Ixy是一个身份指示函数，如果x=y则等于1，否则等于
37、0。算法的剩余部分则定义如下： 其中。图4.12 用伪代码描述了完整的算法。Initialize Q(s, a) arbitrarily and e(s, a) = 0, for all s, aRepeat (for each episode):Initialize s, aRepeat (for each step of episode):Take action a, observe Choose fromusing policy derived from Q (e.g., -greedy)(if ties for the max, then )For all s, a:If , then
38、 else until s is terminal图4.12 Watkinss Q()-Learning 算法4.5.7.2 Pengs Q()-Learning算法每次截断探索动作的trace会丢失许多使用Eligibility traces的优点。如果探索动作经常发生的话，尤其在学习过程开始的时候，那么只对一、两步作了更新，这样学习速度就不比单步的Q-学习快多少。Pengs Q()是为了减弱这样的情况而提出的Q()的改进版本。Pengs Q()可以被认为是Sarsa ()和Watkinss Q()的合成物。从概念上来讲，Pengs Q()使用的是图4-13中所示的混合回溯方法。与Q-学习不
39、同的是，它没有区分探索和贪心动作。每个备份组成部分都是跨越许多步实际经历的，并且几乎只有最后一个动作才能被最大化。那么这些回溯的组成部分则既不是策略相关的，也不是策略无关的。所以，对于一个固定的非贪心策略，在Pengs Q()方法下既不收敛到也不收敛到，而是收敛到这两者的结合上。但是，如果策略变得越来越贪心，那么这种方法还是会收敛到。Pengs Q()的执行效果比较好，许多研究表明它的性能比Watkinss Q()好，而与Sarsa ()差不多，不过，运用起来没有Watkinss Q()那样简单。图4.13 Pengs Q()的回溯图学习利用了将来一步的信息更新值。也就是说，对的更新包含了下一
40、状态y中可能决策的影响。如果下一决策是一个失败的决策，那么当前的决策也要承担相应的责任，也要把这种影响追加到当前决策上来，因此也就产生了4.5.5节的Q学习算法。表面上看，这是一种一步更新算法，但实际上它也考虑了以后所有决策的影响。因为这种影响是递归的，只不过这种影响并没有在更新规则中显式地表达出来。不妨考虑在Q学习值函数的更新中，显式地利用将来所有决策的影响，这就是Peng的学习。首先定义t时刻的校正n步截断回报为：(4-24)考虑到对00固定的情况下，-Learning算法是实验敏感的。一个解决的办法就是每当一个非贪婪动作被执行时把赋值为0。在每一步，-Learning算法在一个随时间线性
41、增长的状态-动作对集合中循环。在最坏的情况下，这个集合就是整个状态-动作空间。然而，实际上需要更新的状态-动作对的数量可以控制在一个可控的层次上，通过仅仅维护那些活动跟踪显著的状态-动作对，因为当时这个数是成指数下降的。另一种方法是在并行机上实习-Learning系统，这种方法把每个状态-动作对映射到独立的处理器上。4.5.8 Sarsa算法Sarsa算法是Rummery和Niranjan于1994年提出的一种基于模型的算法，最初被称为改进的Q-Learning算法，它采用实际的Q值进行迭代，而不是Q-Learning所采用的值函数的最大值进行迭代。它的迭代公式如式(4-29)（4-29）其中
42、，它的一步Sarsa算法已被SSingh证明是收敛的。4.6强化学习发展趋势强化学习以其独特的优点成为并列于监督学习和非监督学习的一种特有的机器学习方法，现在仍是各国学者研究的热点。强化学习未来发展方向可归结为以下几类：部分感知强化学习、关系强化学习、分层强化学习、多Agent强化学习等。下面给出几个热点方向的研究现状及未来发展情况。4.6.1部分感知强化学习在实际的问题中，Agent往往无法完全感知环境信息。即使环境属于马尔可夫型，但由于感知的不全面，对于状态间的差异也无法区别。因此，部分感知问题属于非马尔可夫型环境。在部分感知问题中，如果不对强化学习算法进行任何处理就加以应用，学习算法将无
43、法收敛。目前，关于部分感知强化学习的最主要研究方法是预测模型法。这种方法是建立在部分可感知马尔可夫决策过程POMDP（partially observable MDP）模型之上的，它将状态转移的历史知识应用于预测模型或用于构建系统内部状态，同时引入对内部状态的置信度，将POMDP问题转化为统计上的MDP求解。对POMDP问题的学习，目前是强化学习中一个非常重要的研究方向。Kaelbling等人根据以上定义，结合了Q-Learning算法给出相应的精确解算法。但由于信度状态MDP模型是一个连续状态的模型，当环境复杂度增加时容易出现“维数灾”问题，算法实际上不可行。因此，如何结合神经网络等函数估计
44、方法来解决部分感知强化学习中的“维数灾”问题也是目前研究的热点课题。4.6.2 关系强化学习近年来，关系强化学习（Relational Reinforcement Leaning，RRL）方法的发展受到了越来越广泛的关注。这个方法是用关系结构将强化学习系统泛化到关系表达的状态和动作上，通过使用一阶逻辑和决策树学习最优策略。通过将强化学习与关系表示相结合，有效地减少了状态空间。在强化学习环境中使用关系表示有很多的优点。首先，可以将在相似环境中的对象和已经学习到的知识泛化到不同的任务中；其次使用关系表示也是一种比较自然的利用先验知识的方式。目前比较常用的方法就是将MDP用一阶AI形式扩展成关系背景，或者扩展成能表达概率和效用的扩展逻辑行为语言。2006年华盛顿州立大学的M. Riehardson和P Domingos提出用马尔苛夫逻辑网（Markov Logic Network，MLN）结合一阶逻辑和概率图模型，这样统一了现实世界学习中的复杂性和不确定性问题。关系强化学习常见的算法有：(1) 模型无关的：TILDE-RT算法、TG算法、RIB