（计算机应用技术专业论文）关系强化学习的研究与应用.pdf

摘要 经过几十年发展，强化学习已得到长足的进步，已成为机器学习、人工智 能研究中最活跃的领域之一。在实际问题中，由于状态空间的规模过大以及目前 硬件条件的限制，导致算法的效率不高。现有的大多数算法都采用属性值计算， 不能体现物体间的关系。随着逻辑程序的发展，这种关系可以通过变量来描述， 使得学习任务从复杂的计算中抽象出来。关系强化学习将逻辑程序和强化学习结 合，为强化学习处理大状态空间问题提供了新的方法。 。 本文主要工作内容进行如下： 1 通过分析现有各种算法及运行机制，提出了一种改进的关系强化学习算 法。由于原算法计算重复、迭代次数多、值备份过多，改进算法采用一种增量更 新逻辑决策树的方法实时处理每一个样本点。减少了计算量，提高了算法实时性； 为了弥补子叶节点信息丢失造成收敛速度慢的不足，算法给逻辑谓词赋予了一个 优先级。并在子叶分裂过程中，根据优先级选定候选测试，以提高算法收敛速度。 经实验对比原算法，改进算法的效率有较大提升。 2 概述了现有智能车的智能控制算法；建立了一个基于关系强化学习模型 的自主驾驶系统。系统分为状态分析、策略学习、知识库三个模块。这种模块化 的设计便于针对不同车辆的特点，设置不同的背景知识。充分利用关系强化学习 的学习能力，提高了系统适应性。实验模拟了不同的环境，检测了系统的避障性 能。 关键字：关系强化学习；一阶谓词逻辑；决策树9 自主驾驶系统 r e i n f o r c e m e n tl e a r n i n gh a so b t a i n e ds i g n i f i c a n tp r o g r e s sd u r i n gt h ep a s ts c v - e r a l d e c a d ed e v e l o p m e n ta n db e c o m eo n eo ft h em o s ta c t i v ea r e a si nm a c h i n e l e a r n i n ga n da r t i f i c i a li n t e l l i g e n c e i np r a c t i c e ，b o c a u s eo ft h ee x c e s s i v es c a l e so f s t a t e ss p a c ea n dt h er e s t r i c t i o n si nh a r d w a r ec o n d i t i o n ，t h ee f f i c i e n c yo fa l g o r i t h m s a r en o tw e l le n o u g h , m o s to fw h i c ha d o p tc o m p u t i n go fa t t r i b u t e - v a l u ea n dc a n n o t r e f l e c tr e l a t i o n sa m o n go b j e c t s a l o n g 稍t ht h ep r o g r e s so fl o g i cp r o g r a m m i n g , t h e r e l a t i o nc o u l db ed e s c r i b e db yv a r i a b l e ，w h i c hm a d el e a r n i n gt a s k sa b s t r a c t e df r o m c o m p l i c a t e dc o m p u t a t i o n r e l a t i o n a lr e i n f o r c e m e n tl e a r n i n ga f f o r d san e wm e t h o d f o rd e a l i n gw i t hb i gs t a t e ss p a c eo fr e i n f o r c e m e n tl e a r n i n gb yc o m b i n i n g l o g i cp r o - g r a m m i n ga n dr e i n f o r c e m e n tl e a r n i n g t h i sp a p e rf o c u so nt w ow o r k s ： 1 。p r o p o s et h ei m p r o v e dr e l a t i o n a lr e i n f o r c e m e n tl e a r n i n ga l g o r i t h mt h r o u g h t h ea n a l y s i so fa l lk i n d so fe x i s t i n ga l g o r i t h m sa n do p e r a t i n gm e c h a n i s m s t h ei m p r o v e da l g o r i t h ma d o p t si n c r e m e n t a lk 罾c a ld e c i s i o nt r e e s , d e a l s 奶t he v e r ys a m p l e a n dd e c r e a s e sc a l c u l a t i o nb c c , a u $ et h e r ea r et o om a n yr e p e a t so fc 滋c u l a t i o u sa n di t - e l a t i o n s , a n dd a t ec o p i e si no r i g i n a la l g o r i t h m s i no r d e rt or e c u p e r a t et h el o s to f i n f o r m a t i o no fl e a fi ni n c r e m e n t a lu p d a t e , t h ea l g o r i t h ma s s i g n se a c ho fp r e d i c a t o ra p r i o r i t y s e l e c tc a n d i d a t et e s t si nl e a fs p l i t t i n ga c c o r d i n gt op r i o r i t yl e v e li no r d e rt o i n c r e a s et h ec o n v e r g e n c er a t eo fa l g o r i t h m 。c o n t r a s t st h eo r i g i n a la l g o r i t h mb ye x - p e r i m e n t , t h ei m p r o v e da l g o r i t h mh a sac l e a rp r o m o t i o ni ne f f i c i e n c y 2 o u t l i n et h ec o n t r o la l g o r i t h mo ft h ee x i s t i n gi n t e l l i g e n tc a r sa n de s t a b l i s ha n a u t o n o m o u sd r i v i n gs y s t e mb a s e0 nr e l a t i o n a lr e i n f o r c e m e n tl e a r n i n g t h e a u t o n o m o u sd r i v i n gs y s t e mc o n s i s t so ft h r e ep a r t s ：s t a t ea n a l y s i sm o d e l , p o l i c y l e a r n i n gm o d e la n dk n o w l e d g eb a s e t h e s em o d e l sm a k ei te a s yf o rv e h i c l e sw i t hd i f - f e r e n tc h a r a c t e r i s t i c sb ys e t t i n gd i f f e r e n tb a c k g r o u n d k n o w l e d g e i tt a k e s f u l l a d v a n t a g eo f 曲i l i l yo fr e l a t i o n a lr e i n f o r c e m e n tl e a r n i n g , a n di m p r o v e st h ea d a p t a - b i l i t yo fs y s t e m t h r o u g hs i m u l a t i n gd i f f e r e n te n v i r o n m e n t s , w et e s tt h ep e r f o r m a n c e o fn e wa u t o n o m o u sd r i v i n gs y s t e m ，a n do b t a i nb e t t e rr e s u l t s k e yw o r d s ：r e l a t i o n a lr e i n f o r c e m e n tl e a r n i n g ；f i r s t - o r d e rl o g i c ；d e c i s i o nt r e e s ； a u t o n o m o u sd r i v i n gs y s t e m 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：矾阗镡日期：潮年y 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：胡帆坪 刷醛各亭馓 日期：驴年厂月，夕日 日期：0 2 僻牛月2 ，j 日 第一章绪论 1 1 研究背景 自动化是社会进步的一个重要标志。隧着科技的发展，各囡纷纷致力于自动 化软、硬件技术憋研究以提高生产率。计算机技术正是实现自动化的必备软件， 它的应用使得人们对未来生活充满憧憬：计算机从医疗记录中学习，获取治疗新 疾病的有效方法；交通机器人日夜不停地站在交通要道，自动分析交通状况并进 行疏导：智毙机器入更能胜任在火山、海底等危险地方进行研究的工作。这一些 都离不开计算机的自主学习。机器学习正是在这么一种需求中产生的计算机技 术。虽然我们还不知道怎样使计算机具备和人类一样的学习能力，但针对某些特 定任务的学习算法已经出现，并逐渐发展起来。现在计算机能部分识别人类的讲 话，预测肺炎患者的康复率，在高速公路上自动行驶，与入类最高级别的冠军进 行西洋双陆棋的博弈等等。 在机器学习范畴，根据反馈的不同，学习技术可以分为监督学习、非监督学 习和强纯学习。监督学习是在给定一定标记样本点的情况下进行的，它对样本点 及其标记进行训练，并努力对j 暑标记样本点分类。在样本点少的情况，监督学习 的学习能力将受到限制，可能会作出错误判断而得到不正确的结果。而在样本点 多的情况下虽然可以很好的进行学习，但其计算的复杂度很大，且褥出的结果不 具备推广性。非监督学习是对没有标记的样本点进行分类，以努力发现其中的隐 藏信息。 强化学习【l l ( r e i n f o r c e m e n tl e a r n i n g ) 是一种重要的机器学习方法，早期的 研究将其看成特殊的非监督学习，因为其所需的样本点没有标记信息，但它具有 延时奖赏作用，可被视为一种延时的标记信息。强化学习的出现可以追述到上个 世纪5 0 年代，但是其真正兴起还是在7 0 年代以后，因为在这之前自动化只是程序 化的工作，机器并不具备一定的学习能力，如何从环境中获取知识也还没有得到 人们的足够认识。目前强化学习取得长足的进展，在枕器入路径规划、工监控制 等许多领域得到了应用并逐渐成熟起来，已经是机器学习、人工智能以及神经网 络研究中的最活跃领域之一。所谓强化学习是指从环境状态到行为映射的学习， 以使系统行为从环境中获得的累积奖励值最大。在强化学习中，我们设计算法来 把外界环境转化为最大化奖励，并以此选择动佟，算法并没有直接告诉智能体要 做什么或者要采取哪个动作，智能体通过观测奖励值的大小自己确定动作。智能 体的动作所影响的不仅是立即奖励，还包括接下来的动作和最终的奖励。 由于强化学习只能利用这种不确定的环境奖赏值来确定策略，所以它相对于 监督学习有着明显的不同；强化学习与规划技术也有区别，规划技术假设的是一 个稳定的环境，并且需要构造一个复杂的状态图。其实质是使算法完全理解环境， 以方便规划。而强化学习所理解的是交互所得到的整个或部分环境，它利用自身 的的策略知识和所处环境进行下一步预测。这种交互使得强化学习可以适应动态 的环境：同样强化学习也不同于自适应控制技术，虽然两者都有共同的奖赏函数 形式，但在自适应控制中，系统模型只能是固定的动态模型，其模型可以从统计 数据中进行参数估计。相反强化学习对环境没有要求，可以适应任何未知的复杂 环境，这使得强化学习有着很强的研究及实际应用价值。 ， 试错搜索( t r i a l - a n d e r r o rs e a r c h ) 和延期强化( d e l a y e dr e i n f o r c e m e n t ) 这两个特性 是强化学习中两个最重要的特性。由于智能体不断地自主尝试执行动作并对自己 的行为进行评估，所以它能很好的和环境进行交互，并不断改变自己的策略以适 应环境。在这个过程中，智能体自己学习并获取的知识是从环境中得到的，环境 通常包括状态空间、动作空间以及奖赏值等等。当环境非常复杂时，强化学习通 常面临一些问题。比如：环境复杂意味着状态空间和动作空间比较大，此时算法 应该怎样减少计算量，并保证结果的优越性；在大状态空间下智能体首先要考虑 的是采取什么样的措施：继续对未知状态进行学习；还是利用已有信息作出判断。 特别，当对智能体作出时间及其他限制时，算法的改进将是一个富有挑战性的工 作。关系强化学习正是这样一种改进的强化学习，它的提出是为了使智能体能够 在大空间状态下快速制定较好的策略。 智能车辆1 2 1 又称轮式移动机器人是一个集环境感知、规划决策、自动驾驶等 多种功能于一体的综合系统。除特殊潜在的军用价值外，还因其在公路交通运输 中广阔的应用前景受到西方国家的普遍关注。几个工业发达国家已相继将智能车 辆的研究纳入9 0 年代重点研究开发的“智能运输系统一( 简称i t s ) 和“智能车 路系统 ( 简称w a s ) 的重要组成部分。一个真正具有应用价值的智能车辆系统必 须同时具备实时性、鲁棒性、实用性这三个技术特点。这也是智能车辆研究必须 解决的三个重点课题。实时性要求系统的数据处理必须与车体的高速行驶同步进 行。鲁棒性则要求智能车辆对不同的道路环境( 如高速公路、市区标准公路、普 通公路) ，复杂的路面状况( 路面及车道线的宽度、颜色、纹理、动态随机障碍与 车流) 以及变化的气候条件( 日照及景物阴影、黄昏与夜晚、阴天与雨雪等) 均具有 良好的适应性。这是智能车辆系统研究的难点所在。实用性要求智能车辆系统在 体积与成本等方面能够为普通汽车用户所接受。上述技术的要求构成了智能车辆 系统研究所涉及的传感器信息处理、车体精密定位、行为规划与决策、自动驾驶 与安全监控、综合集成等主要关键技术。值得注意的是，进入9 0 年代来，西方发 达国家在智能车辆研制与开发方面出现了一些引人注目的变化【3 】。几个新型的实 验车和导航平台相继问世。认真分析其中的技术特点和研究动向，对于我f l q 2 1 世纪开展智能车辆研究无疑具有借鉴意义和参考价值。 2 1 2 强化学习的发展 强化学习的发展分为三条主线，在经历了各自不同的进程之后最终形成了现 代强化学习的框架。 第一条主线是原自2 0 世纪5 0 年代的最优控制问题，它的目的是在一个可参 数化的动态模型中设计一个控制器以达到最小化成本的目的。r i c h a r db e l l m a n 扩展了h a m i l t o n 和j a c , o b i 的理论，使用动态系统状态和值函数的概念来定义一 个方程组( b e l l m a n 方程) 。1 9 5 7 年b e l l m a n t 4 ) 使用动态规划的方法解决了这个最 优控制问题，并介绍了称为马尔科夫决策过程( m d p ) 的随机最优控制问题。 随后在1 9 6 0 年r o nh o w a r d l 5 使用策略迭代的方法解决m d p 问题。 动态规划通常被认为是解决随机最优控制问题的唯一可行方法。虽然 b e l l m a n 说明它存在维数灾难问题，但相对其他方法它仍然高效。随后几十年动 态规划得到广泛发展。1 9 9 1 年l 0 v j o 矿叼将其应用到部分可测马尔科夫决策过程； 1 9 8 5 ，1 9 8 8 ，1 9 9 3 年w h i t e f f l 进行了许多实际应用：1 9 9 6 年r u s t 捌引入函数近似 方法；1 9 8 2 年b e r t s e k a s t g 使用异步的方法；p u t e r m a n ；r o s s ；w h i t t l 等学者都对其 进行了各种改进和应用。 现代强化学习的第二条主线主要致力于试错学习。试错学习原自心理学的概 念。e d w a r dt h o r n d i k e 将其称为“l a wo f e f f e c t 一，他的基本思想是动物的意愿与 其本身的舒适度有关，如果动物觉得某种状态比较舒适，它会将这种状态和感觉 联系，并可能使这种状态再次出现。这种思想包含了试错的两个重要特点：选择 性和联合性。选择性就是尝试学习不同动作并比较不同结果；联合性是指可选择 的动作与特定的状态联系在一起。在早期的人工智能研究中，许多学者将试错学 习看成一个工程学原理：m i n s k y , f a r l e y 和c l a r k 在1 9 5 4 年对试错学习进行了细 致研究。m i n s k y 讨论了强化学习的计算模型并提出随机类神经的强化计算过程。 f a r l e y 和c l a r k 讨论了另一种基于试错的类神经学习机。6 0 年代“强化一和“强 化学习 被第一次用于工程学文献。m i n s l , y 于1 9 6 1 年进一步讨论了与强化学习 有关的问题。比如：信任分配问题。在随后f a r l e y 和c l a r k 的研究中试错和监督 学习的界限变得模糊，6 0 到7 0 年代强化学习停滞下来。j o h na n d r e a e 于1 9 6 3 年 提出基于试错和环境进行交互的s t e l l a 模型。d o n a l dm i c h i e 于19 6 3 年提出一 个简单的试错学习系统( m e n a c e ) 并用于t i c - t a e t o e 游戏，m e n a c e y 由一个对 应于每种可能状态的匹配盒( m a t c h b o x ) 组成，盒内包括不同颜色的珠子，每种颜 色对应下一步可能的状态，通过随机选取珠子可以选择下一步动作，并可以在游 戏结束时通过增加和减少珠子来对决策进行奖赏和惩罚。m i c h i e 和c h a m b e r s 于 1 9 6 8 提出另一种用于t i c - t a c - t o e 的强化学习模型g l e e 和一个强化学习控制器 b o x e s ，并将b o x e s 进行应用于倒立摆实验。当杆子倒下或小车撞倒边界时给 3 与惩罚。早在1 9 6 4 年就有w i d r o w 和s m i t h 用监督学习的方法成功实验倒立摆， 但m i c h i e 和c h a m b e r s 的实验是最早将强化学习应用于只包含不完整信息的任 务，并对以后强化学习的发展产生重要影响。w i d r o w ，g u p t a 和m a i t r a 1 0 】于1 9 7 3 年修改l m s 算法，提出了从成功、失败信号中进行学习的强化学习规则以代替 从训练中学习，并将其应用到b l a c k j a c k 实验。他们把这种算法成为“从评判者 学习一，而不是以前的。从老师学习一。 自动学习机的研究对基于试错的强化学习有直接影响。学习自动机用于解决 具有选择性的非联合的简单n - a r m e db a n d i t 问题。j o h nh o l l a n d 于1 9 7 5 年提出基 于选择原理的自适应系统理论，并于1 9 8 6 年介绍了一个真正的包括联合性和值 函数的强化学习系统一分类系统。这种分类系统采用遗传算法来改进表示方式， 随后分类器被许多学者发展( w i l s o n 1 1 】，1 9 9 4 ) 并形成强化学习的一支。 h a r r yk l o p f 对试错强化学习有重要影响。他意识到自适应行为的实质：从 环境中学习并控制环境向有利的结果发胀。这也是试错学习的本质。从此强化学 习和其它学习方法区别开来( b a r t o ，a n a n d a n l l 2 l ，1 9 8 5 ) 。同时有文献指出强化学 习可以解决神经网络的许多问题，特别它可以为多层网络提供学习方法( b a r t o ， a n a n d 锄【1 3 1 ，1 9 8 5 ) 。 强化学习的第三条主线是差分学习，差分学习部分起源于动物学习心理学， 特别是其二次刺激的概念。二次刺激和食物、疼痛等第一刺激对应的刺激，两者 有相同的属性。m i s k y 是第一个意识到第二刺激可以用于人工智能的学者。a r t h u r s a m u e l 于1 9 5 9 年第一次提出基于差分概念的学习并用于西洋跳棋。s a m u e l 并没 有和m i n s k y 的工作联系，其灵感来自于s h a n n o n 的建议：电脑可以通过评估函 数来进行象棋游戏，并通过在线函数提高电脑水平。m 妇b 于1 9 6 1 年在前者的 基础上作了进一步的工作，并揭示了两者的关系。1 9 7 2 年，r a o p f 将试错学习与 差分学习结合起来。他对学习机用于大系统作了研究，并对局部强化学习产生兴 趣。他提出学习系统的子系统可以对其他部分提供支持，并将其称为普遍强化。 随后s u t t o n ，b a r t o 1 4 1 ，h a w k i n s ，k a n d e l 1 5 】等学者作了更多、更为细致的研究。 1 9 8 9 年w a t l d n s 将最优控制和差分学习结合提出了现在广为使用的q 学习算法。 至今又有很多学者【1 6 1 1 那8 】【1 明提出不同的改进算法，并进行了大量应用。 1 3 本文主要研究内容 为了解决强化学习中的大状态空间问题，很多学者提出了很多有效的改进 方法：用神经网络模拟值函数，用聚类方法将状态空间分类，建立优先扫描序列 矗盘 守。 本文的主要研究内容包括： 1 介绍强化学习的发展背景及其基本发展过程。 4 2 阐述强化学习的基本原理，讨论了强化学习的主要算法及运行效率；为了 解决实际问题中的维数灾难问题，对现有解决大状态空间问题的方法做了 相关研究。 3 详细分析了关系强化学习算法，并针对现有算法计算重复、迭代次数大、 值备份过多的问题，提出了改进算法。 4 介绍智能车目前的发展状况，针对自主驾驶的智能控制部分，提出了一个 新的基于关系强化学习的模型。通过建立不同仿真环境测试算法的性能。 5 第二章强化学习 2 1 强化学习模型 强化学习是一种无导师学习，智能体通过与外界进行相互作用产生动作，从 而引起环境状态的改变，并且从外界环境中接受到强化信号。学习的目的就是寻 找优化策略：即找到一个从状态到动作的映射，以求得到强化信号某种量化指标 的最大。强化学习模型基于马尔可夫决策过程( m d p ) 而建立，m d p 模型由以 下几个基本部分组成： ，- 状态集动作集彳，状态转移函数t ：s x 彳- - n ( s ) ，n c s ) 的每个成员都是 s 的一个概率分布( 例如，它从状态映射到概率) 。用r ( s ，a ，s ) 表示在状态s 使 用动作口转移到状态s 的概率。状态转移函数作为环境的当前状态和智能体采取 的动作的函数指明了环境的后继状态。奖赏函数作为环境当前状态和智能体所采 取的动作的函数指明了期望瞬时奖赏。如果状态转移独立于前面任何环境状态或 智能体的动作，那么模型就是马尔可夫模型。 ， 图2 1 强化学习模型 智能体和环境的相互作用是由智能体采取动作引起的( 如图2 1 ) ，同时触发环 境状态的转移，在实际问题中，状态的转移往往不是确定性的，而是随机的。为 了寻找从状态集合到动作集合的优化映射，一般的强化学习都不直接去搜索这种 映射，而是通过计算状态值函数进而获得优化策略，值函数的定义有很多方法， 通常使用长期期望回报。 当给定确切的环境模型，则动态规划技术是一种最基础的强化学习技术。在 动态规划中，通常使用无限水平折扣模型来学习最优策略。对于无限水平折扣模 型有以下结论成立：存在一个最优的、确定的平稳策略。 如果智能体从最优状态开始并执行最优策略，则它所获得的折扣奖赏和期望 为( 万是一个最优决策策略) ： 旷( s ) = m 。a x e ( y o t = o 该最优值函数是唯一的，且根据i v l d p 的定义可以推出如下等式： 6 y o ) = m 。a x ( r ( s , a ) + ，r ( s ，口，s i ) y ( s i ) ) ( 2 1 ) 毒- e s 上式表明，状态s 的值是使用最好动作所得到的瞬时奖赏期望值加上后继状 态的期望折扣奖赏值。当给定最优值函数时，就能指定最优策略： 万( s ) = a r g m a x ( r ( s ，口) + 厂t ( s ，口，s g v o 2 1 1 值迭代 由于最优策略通过最优值函数确定，且最优值函数的计算可以通过一个简单 且收敛的迭代过程来完成，这个迭代过程通常称为“值迭代一过程，它能收敛到 正确的矿值，其算法如下： 初始化矿( s ) 为任意值： 循环( 直到策略足够好) ： 循环( 对于s s ) 循环( 对于a e 彳) q ( s ，口) - - r ( s ，口) + 厂，镪丁( s ，口，s g v ( s 9 y ( s ) 一i im a xq ( s ，口) 循环结束 循环结束 循环结束 但是，上述算法何时停止并没有明确给出，通常把当前贪婪策略的性能作为 判定当前值函数是否最优的标准。即如果连续两个值函数的最大差值小于g ，那 么贪婪策略( 在每个状态使用当前值函数的估计能够选择使得估计折扣奖赏最大 化的动作的策略) 的值不同于最优策略的值函数。另外，r m a n 根据可能导致 较早终止的跨度讨论了另一种停止标准。虽然迭代必须在有限步终止，这可能导 致值函数不能收敛，但贪婪策略可被证明是最优的。通常在实际中，贪婪策略在 值函数收敛之前就已经是最优的了。 一般，上述迭代过程只是一个标准模板，可以将其改进为其他不同形式：假 定每个状态的值被无限地更新，则y 的完成不需要严格的顺序，可以异步进行。 b e n s e k a s 对此做了更为深入地研究证明。 在b e l l m a n 方程中，式2 1 的更新是一种完全备份，因为它们利用所有可能 的后继状态的信息。当每个 被无限的更新时，可以使用下面的公式： q ( s ，口) 净q ( s ，a ) + c t ( r + 厂m a x q ( s , a 9 - q ( s ，口) ) s 根据分布r ( s ，口，s ) 选取，根据平均r ( s ，口) 取值，学习率口随迭代次数递减。 这种采样备份方式对无模型方法非常有效。 7 完全值备份算法中每次迭代的计算复杂度和状态数和动作数相关，它与状态 数呈二次方关系，同动作数呈线性关系。一般地，若转移概率r ( s ，a ，s ) 是稀疏的， 且转移到后继状态的概率是一个非零常数，那么每次迭代的复杂度和状态数呈线 性关系、和动作数也是线性的；如果折扣因子是常数，达到最优值函数需要的迭 代数和状态数、最大奖赏值呈多项式的关系：在最坏的情况下，迭代次数依多项 式1 ( 1 一名) 增长，因此使用折扣因子l 时的收敛速度将很慢。 2 1 2 策略迭代 策略迭代算法直接利用策略的更新找最优策略，而不是通过最优值函数找最 优策略。其算法流程如下： 选择任意策略万 循环： 石# 万 计算策略万的值函数： y ，( s ) = 尺( s ，万( s ) ) + 厂，| 心丁o ，万o ) ，s g v 鼻( s i ) 改进策略： 石 ( s ) ：= a r g m a x 口( r ( j ，o ) + y y ，心丁( s a , s g v f ( s 直到石= 刀 一个策略的值函数是在每个状态上执行该策略所得到的期望无限折扣奖赏。 通常通过解一组线性等式来确定策略的值。一旦知道当前策略下每个状态的值， 可以通过改变动作来提高值的大小。因而无论处于什么情况，都可以采取新的动 作来改变策略，这保证了策略改进的严格递增性，当策略不能改进时，该策略则 达到最优。 4 由于最多只有1 4 p 个不同的策略，而且在每步策略序列都改进，所以算法至 多迭代指数次后终止。在最坏的情况下，策略迭代进行迭代的次数是一个有待解 决的重要问题。 2 1 3 改进的值迭代和策略迭代 值迭代和策略迭代有各自的优势：值迭代的单步迭代速度快，而策略迭代的 总迭代次数少。对于对大状态空间问题，不能直接判定那种迭代更有优势。 p u t e r m a n 2 0 1 提出一种平稳的改进策略迭代算法来减少迭代次数。它基于如下思 想：由于策略迭代中，计算量复杂的部分是求解精确旷值的过程，若能找一个 代替的v 彳值，就能够在值迭代过程中减少迭代次数。在实际中，通常生成矿的 8 线性近似值以获取算法的加速。 2 2 无模型的策略学习 2 2 1t d 算法 动态规划算法要求求解一系列线性方程，这在自适应在线学习中，是无法实 现的。然而智能体的状态值可以通过如下式子进行估计： y ( s ) 车v ( s ) + c t ( r + y v ( s 。) 一矿( s ) ) 这种算法称为自适应启发式评价算法( a h c ) ，又可称为t d ( o ) 算法 2 1 】。 其结构包含了两个组成部分：评价模块和强化学习模块。a h c 在当前固定策略 下给出策略的最优状态值估计，而r l 在固定策略的估计值下优化智能体的策略。 下面给出t d ( 0 ) 的基本算法： i n i t i a l i z ev ( s ) a r b i t r a r i l y , 兀t ot h ep o l i c yt ob ee v a l u a t e d r e p e a t ( f o re a c he p i s o d e ) i n i t i a l i z es r e p e a t ( f o re a c hs t e po fe p i s o d e ) c h o o s eaf z o msu s i n gp o l i c y 似l e r i v e df i o mv ( e g ，一g r e e d y ) t a k ea c t i o na ，o b s e r v e r ，：s v ( s ) - v ( s ) + a i r + y v ( d ) - v ( s ) s 七圣 u n t i lj i s t e r m i n a l 上述算法是t d ( o ) 算法，它只是是1 d ( 九) 算法的一个特例。t d ( o ) 表示智能体 在获得奖赏并调整估计值的时候，只回退一步，即将当前奖赏归结为前面一个动 作行为的结果。t d ( 九) 则比t d ( o ) 更加一般化，在更新状态估计值时可以回退任 意步，如式( 2 2 ) 所示： y o ) ：= y ( j ) + 口( ，+ y v ( s ) 一矿( s ”p o ) ( 2 2 ) 其中p ( 材) 为资格迹，是状态s 在最近被访问的程度，可以定义如下： 吣) = 扣广耻任0 毡 ( 2 3 ) 当智能体收到一个强化时，该强化被用来依据合适程序更新最近访问过的所 有状态。当五取0 时等价于t d ( o ) ，当旯取l 时，等价于运行结束时根据状态被 访问的次数更新所有的状态。可以根据具体情况适当地在线更新合适度。下面给 出t d ( 名) 的基本算法： i n i t i a l i z ev a r b i t r a r i l ya n d 删f o ra l lses r e p e a t ( f o re a c he p i s o d e ) 9 i n i t i a l i z es r e p e a t ( f o re a c hs t e po fe p i s o d e ) 口+ - a c t i o ng i v e nb y 兀f o rs ( e g ，e g r e e d y ) t a k ea c t i o na o b s e r v e rr ，s p ( s ) 4 - - p ( s ) + 1 f o r a l l s y ( ，) 卜矿( f ) + 口万p ( j ) p ( 暑) - t a l c , ) s4 - - - s u n t i lsi st e r m i n a l 2 2 2q 学习算法 q 学习倒是w a t l d n s 于1 9 8 9 年在其博士论文中提出来的，它是一种无模型的 强化学习方法，也可以被看作是一种异步动态规划方法。它通过使得智能体执行 行为序列，来学习在马尔可夫环境下应该如何优化地行动，而不是建立关于环境 的映射。其学习过程如下：在某个状态s 下，智能体试着执行一个行为口，然后 根据智能体所收到的奖赏值和当前状态的估计值来对行为的结果进行评估。对所 有状态下的所有行为进行这样的重复，智能体通过对长期的折扣奖赏的判断，就 可以学习到总体上较优的行为。 q 学习是一种简单的学习形式，但是它是许多其他复杂学习方法的基础，并 且已经证明了q 学习算法对于m d p 是收敛的。设智能体在有限环境下运动，它 的每一个步骤都是从有限的集合中选取行为。这样环境就构成了一个受控的马尔 可夫过程，而智能体就是控制器。在某个步骤，设智能体处于状态s ，并且选择 了相应的行为口，智能体得到奖赏r o ，口) ，并且根据状态迁移概率分布函数 r ( s ，a ，s 。) 迁移到下一个状态s 。在动态规划理论中，上述问题的智能体从状态s 开始执行时，至少存在一个优化的固定策略万。当已知r ( s ，口) 和r ( s ，口，j ) 的值时， 可以利用有模型的学习方法来求解。而q 学习的任务是在不知道这些值的时候 确定一个策略万定义策略万的 值为： i f , 0 ，口) = r ( s ，a ) + v y ：r ( s ，口，s ) 旷( s 。 ( 2 4 ) j q 值表示智能体在状态j 下执行行为口，且此后执行策略万的期望折扣奖赏。 q 学习的目标就是要估计优化行为的q 值。基本算法如下： i n i t i a l i z eq ( s ，a ) a r b i t r a r i l y r e p e a t ( f o re a c he p i s o d e ) 1 0 i n i t i a l i z es r e p e a t ( f o re a c hs t e po fe p i s o d e ) c h o o s eaf r o msu s i n gp o l i c yd e r i v e df r o mq ( e g ，- g r e e d y ) t a k ea c t i o na ，o b s e r v e r ，s q ( s ，口) - q ( 葶，a ) + o t r + y i p 舣一q ( 一口) 一q ( ，口) s 七t u n t i l5i st e r m i n a l 可以证明如果在无限的运行中每个 执行无限次，并且口合适地衰减， 则q 值将以概率l 收敛于矿。由于q 值在每一次迭代循环中都需要考察智能 体的每个行为，从而q 学习本质上不需要其他搜索策略。q 学习的好处在于其 评估函数的定义精确，当前 序列的q 值概括了所有需要的信息，能够确定 状态s 下选择动作a 在将来会获得的折扣累积奖赏，并且无需中间的代价评估步 骤和环境模型的知识。在一定条件下，q 学习只需要采用简单的贪婪策略即可保 证算法的收敛性，q 学习收敛的具体证明在此就不再赘述了，该学习算法是最有 效的无模型强化学习算法之一，同时也是目前应用得最为广泛的强化学习算法。 在上述的三种方法中，学习时都无一例外地要考虑到探索和利用的折衷问 题。在每次选择行为时，智能体应该判断如何做出好的决策：是使用现有的最佳 行为，还是探索别的未知行为，过分强化探索而对已经学习到的知识不加以利用， 虽然可以得到很多信息，但是会耗费大量的时间，带来许多求解效果上的不理想， 这是很不划算的。同时如果是过分地强调利用而不采用探索，则可能会因为由于 缺少必要的信息而不能够找到最优的行为。所以应该合理地确定探索和利用的折 衷问题。 2 3 基于模型的策略学习 在马尔可夫决策过程模型中r 和只为智能体的模型知识，记四元组( s ，a ，s ，r ) 为智能体的学习经验。则t d 算法和q 学习算法可以使智能体直接从经验中学习 优化策略。由于不需要学习丁函数和r 函数，无模型方法每次迭代只需要很少 的计算量，但是由于没有充分利用每一次的学习经验中获取的知识，算法需要很 长的迭代时间才能够得到收敛。 d y n a 2 3 2 4 1 综合了动态规划和t d 算法，智能体分三步学习优化策略。首先 智能体使用学习经验来建立模型，其次使用经验来调节策略，最后使用模型来调 节策略。具体的算法描述如下： s t e p l 在状态，选择动作口； s t e p 2 智能体观察状态转移到和奖赏值，即智能体得到学习经验 o ，a ，s ，) ； ： s t e p 3 根据学习经验集，采用概率统计技术建立关于环境的模型，即t 函 数和r 函数的估计； s t e p 4 利用新模型更新当前策略下状态行为对的值函数估计； s t e p 5 利用新模型更新其他任意k 个状态行为对的值函数估计； s t e p 6 智能体选择一个优化动作，转回s t e p 2 。 2 3 2 优先扫描序列 尽管d y n a 比以前的方法有很大的改进，但它是未受指导的。当目标刚刚 到达或智能体陷入循环时，d y n a 无法解决问题：因为算法会继续更新随机勺， 口 对，导致值函数的增加集中在陷入循环的几个状态中，而不是集中于状态空 问的“感兴趣的一部分。优先扫描则可以有效解决这个问题。 优先扫描算法【捌和d y n a 相似，其更新步骤不再随机选择、现在值和状态 结合( 如值迭代) 也不是状态动作对( 如q 学习) 。为了作出适当的选择，必须 存储模型附加的信息，每个状态记住自己的前一状态，以非零转移概率转移到该 状态的那些状态。另外，每个状态赋予一个优先权，初始时设为0 。 优先扫描更新有最高优先权的k 个状态，而不是的随机k 个 。对于每 个有最高优先权的状态s ，其算法如下： s t e p l 记住该状态的当前值：= y ( j ) s t e p 2 更新状态的值： y ( s ) # m a x ( r ( s ，a ) + r x t ( s ，a ，s ) y 0 。 口 了 s t e p 3 设置状态的优先权为0 s t e p 4 计算值的变化= i - v ( s ) i s t e p 5 用修改状态j 的前辈的优先权。 s t e p 6 如果更新了状态j 的v 值而且它改变了，那么状态s 的前一个状 态被告知该事。任何存在一个动作a 的状态s ，即r ( s ，a ，s 9 0 ，把 自己的优先权提高到a t ( s ，a ，s 9 ，除非自己的优先权已经超过该值。 该算法的思想是当现实世界的状态转移获得很高回报时( 例如，智能体遇到 一个目标状态) ，计算结果被反向传播到与当前状态相关的一些前驱状态上。当 状态转移获得较差回报时( 实际结果与预测的结果的很相似) ，结果不作处理， 计算继续进行。 1 2 优先扫描比d y n a 算法在效率有很大改进。通常情况下，其最优策略的实 现所需步数是d y n a 所需要步数的一半甚至更少。 2 4 大状态空间问题的解决方法 马尔科夫决策过程的基本框架及其相关解决的技术假设所有状态和动作，以 及状态转移矩阵、策略和值函数都是明确表示的。尽管有许多有用的理论对其进 行分析，但在大多数领域，由于问题规模过大而无法精确描述出来。比如，对于 有1 0 5 个