（交通运输规划与管理专业论文）Q学习在单路口交通信号控制中的应用研究.pdf

摘要 当前交通拥堵现象在国内外各种城市中频频发生，要解决这种现象，必然要 加强交通控制与管理。在城市交通中，单路口信号控制构成了交叉口线控和面控 的基础，是国内外研究的热点。 本文针对智能体技术应用于交通信号控制方法展开相关研究，主要工作涉及 以下几个方面： 在充分学习强化学习原理的基础上，主要对利用q 学习算法进行交通信号控 制的5 个关键问题进行了探讨，并重点解决了利用q 学习算法所需要的状态空间 的离散化，同时也构建了基于q 学习的单路l = l 交通信号控制体系。 根据q 学习算法的原理，提出了基于各相位绿灯时间变化的三种动作：增加 当前相位绿灯时间秒，保持不变，减少当前相位绿灯时间秒。各个相位分别 采用三种动作组成的方案，构成状态转化后的控制动作集。采用此控制动作集， 基于周期变化与否，分别建立了以车均延误最小为目的的两个奖惩函数，并提出 两种不同的q 学习交通信号控制算法：固定周期与可变周期的q 学习算法。对该 信号控制算法进行设计后，给出了算法详细步骤。 通过m a t l a b 编程，以一个典型4 相位控制的单路口作为算例，分别以固定周 期与可变周期的q 学习算法进行信号配时，与w e b s t e r 法进行了对比，验证了单 路口利用q 学习进行交通信号控制的算法具有较好的控制效果。 本文最后对研究工作进行了总结，指出了今后需进一步深入研究的问题。 关键词：强化学习；q 学习；智能体；交通信号控制；单路口 a b s t r a c t n o w a d a y st r a f f i cja m so c c u rw i d e l yi nd i f f e r e n tc i t i e sa r o u n dt h ew o r l d t oa v o i d t h i sp h e n o m e n o n ，i ti sn e c e s s a r yt or e i n f o r c et h et r a f f i cc o n t r o la n ds u p e r v i s i o n i n u r b a nt r a f f i c ，t h e s i n g l e i n t e r s e c t i o n s i g n a l c o n t r o li st h eb a s i so fi n t e r s e c t i o n c o o r d i n a t e ds i g n a lc o n t r o la n dn e t w o r k l e v e ls i g n a lc o n t r 0 1 t h e r e f o r e ，i tb e c o m e sah o t r e s e a r c ht o p i c t h et h e s i sa i m st os t u d yt h ea p p l i c a t i o no fa g e n tt e c h n o l o g yi nt r a f f i cs i g n a l c o n t r 0 1 t h ef o l l o w i n gm a i na s p e c t sa r ei n v o l v e di nt h et h e s i s ： o nt h eb a s i so fr e s e a r c ho nt h ep r i n c i p l eo fr e i n f o r c e m e n tl e a r n i n g ，t h et h e s i s d i s c u s s e st h ef i v ek e yp r o b l e m sw h e nq l e a r n i n ga l g o r i t h mi sa p p l i e di nt r a f f i cs i g n a l c o n t r 0 1 i tn o to n l ys o l v e st h ep r o b l e mo fd i s c r e t i z a t i o no fs t a t es p a c en e e d e di n q - l e a r n i n ga l g o r i t h m ，b u ta l s oc o n s t r u c t sas i n g l ei n t e r s e c t i o nt r a f f i cs i g n a lc o n t r o l s y s t e mb a s e do nq l e a r n i n g a c c o r d i n gt o t h et h e o r yo fq l e a r n i n ga l g o r i t h m ，t h ea u t h o rp r o p o s e st h r e e a c t i o n sb a s e do nt h ec h a n g eo fe a c hp h a s eg r e e nt i m e ：i n c r e a s ec u r r e n tp h a s eg r e e n t i m eas e c o n d s ；r e m a i nu n c h a n g e d ；d e c r e a s ec u r r e n tp h a s eg r e e nt i m eas e c o n d s w i t ht h e a p p l i c a t i o no ft h i sp r o g r a m o ft h r e ea c t i o n s ，e a c hp h a s ec o n s t i t u t e sa t r a n s f o r m e dc o n t r o la c t i o ns e t b a s e do i lt h i sc o n t r o la c t i o ns e ta n dp e r i o dc h a n g e ，t w o r e w a r df u n c t i o n sa r ee s t a b l i s h e df o rt h ep u r p o s eo fm i n i m i z i n ga v e r a g ed e l a y a tt h e s a m et i m e ，t w od i f f e r e n tq - l e a r n i n ga l g o r i t h m so ft r a f f i cs i g n a lc o n t r o la r ep r o p o s e d ， w h i c ha r eq - l e a r n i n ga l g o r i t h mw i t hf i x e dc y c l ea n dv a r i a b l ec y c l e a f t e rt h ed e s i g no f t h ea l g o r i t h m ，d e t a i l e ds t e p sa r eg i v e n i nt h et h e s i s ，at y p i c a lf o u rp h a s e c o n t r o l l e di n t e r s e c t i o ni st a k e na sa l le x a m p l e t h r o u g hm a t l a bp r o g r a m m i n g q - l e a r n i n ga l g o r i t h mw i t hf i x e dc y c l ea n dv a r i a b l e c y c l ei su s e df o rs i g n a lt i m i n g c o m p a r e dw i t hw e b s t e rm e t h o d ，b e t t e re f f e c to f q l e a r n i n gf o ras i n g l ei n t e r s e c t i o ns i g n a lc o n t r o li sv e r i f i e d f i n a l l y , t h ea u t h o rs u m m a r i z e sh i sr e s e a r c hw o r ka n dp u t sf o r w a r dp r o b l e m sf o r f u r t h e rs t u d y k e yw o r d s ：r e i n f o r c e m e n tl e a r n i n g ；q l e a r n i n g ；a g e n t ；t r a f f i cs i g n a lc o n t r o l ； s i n g l ei n t e r s e c t i o n i i 长沙理工大学 学位论文原创性声明 本人郑蓖声明：所呈交的论文是本人盔导帅的指导下独立进行研究所 取得的研究成果。除了文中特别力i j 以标注引削的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：彳也转 曰期：加( 。年( 夕月啪 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所将本论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 l 、保密1 3 ，在年解密后适用本授权书二 2 、不保密d 。 ( 请在以上相应方框内打“、”) 作者签名：夕李毛跨日期：9 ，湃乒月锄少日 导师签名：矿 日期：硼。年 ￥月印e l 1 1 选题背景 第一章绪论 随着社会经济发展，我国及世界上许多大中城市交通日益紧张，城市交通系 统难以令人满意，这一方面严重困扰着城市居民生活和工作，同时直接制约着社 会经济发展。面对这种严峻形势，世界上不少国家，为了解决城市交通问题，花 费大量人力物力，先后在治标和治本两方面进行大量研究，尤其是如何采用智能 的交通管理和交通控制手段，达到全方位提高道路应用效率的目的。 大城市交通拥堵的最重要的原因是平面交叉口的通行能力不够，因此，交通 管理中关键的工作是如何优化交通信号控制系统。单个路口是交通网络中最基本 的节点，单路口交通信号控制优化同时是城市交通线控、面控的基础。针对交通 流特征，国内外学者做了大量的研究工作，现状研究比较成熟的理论有感应控制 与定时信号控制两种方式。理论上，人们进行交通信号控制的研究包含两大出发 点： 交通流之所以吸引了从事交通信号控制理论研究的科研人员，将交通信号 优化作为研究对象，发展和研究新的理论构架，是因为交通流自身的特点所吸引， 包括：随机性、时变性、非线性、综合性等。 基于目前交通控制系统中存在的问题与交通流的特殊性，挖掘现有先进控 制技术和控制方法的潜力，并将其应用到实际工作中，对现有交通控制系统进行 研制和改进，以提高适用性和实用性。 改进的城市交通信号控制系统应可以成为动态的分析、预测、优化与决策的 过程，建立相对应的交通元素模型，对交通信号灯的相位绿灯时间、相邻路口信 号灯相位差进行动态协调控制。为此，强化学习采用的a g e n t 技术特别是实时a g e n t 技术可以解决该问题。a g e n t 技术能提供更高层的建模方式、更丰富的交互语义、 通过协调求解以及根据不确定的知识和经验进行决策。a g e n t 具有自主性、适应性、 社会性和智能性，这与网络化的城市交通系统的智能化、动态化和协同化的需求 相适应，当然是构造该类系统的理想技术。 本文立足于研究单路口信号灯控制问题，采用强化学习q 学习算法，对单交 叉口信号灯控制方法进行研究，试图研究和开发解决交叉口信号灯控制的新方法 和新思路。 1 2 强化学习的研究现状 1 2 1 强化学习的理论研究现状 人们研究强化学习的历史可分为两大脉络【1 1 ，在现代强化学习理论诞生之前， 它们之间互不关联。其一起源于动物学习心理学，通过试误( t r i a la n de r r o r ) 实 现学习。该主线贯穿于早期的人工智能研究工作当中，在二十世纪八十年初期推 动强化学习复苏方面起了重要作用。其二是对最优控制( o p t i m a lc o n t r 0 1 ) 的研究 及其解决方法：即值函数( v a l u ef u n c t i o n s ) 和动态规划( d y n a m i cp r o g r a m m i n g ， d p ) ，但其大部分研究成果不涉及“学习 。即使这两大脉络在很大程度上彼此独 立，然而在发展过程中第三条线索渐渐显现，即对时间差分( t e m p o r a ld i f f e r e n c e ， t d ) 方法的研究。三者共同作用，在上世纪八十年代末对强化学习研究产生了强 有力的推动，现代强化学习理论就此诞生。 两大脉络具体如下： 由心理学发展而来。以“试误 方法为核心，该方法最为常见，首创者是 于1 9 1 1 年提出了“效应定律【2 】( l a wo f e f f e c t ) 的e d w a r dt h o m d i k e ，该思想本 质在于对行为的结果优劣进行分级并以之作为行为选择的依据，同时指出若某行 为能获得正面回报，则其被选概率将增加，反之将降低。而最早对该思想进行深 入的研究可能是在1 9 5 4 年由m i n s k y 和f a r l e y 及c l a r k 开始，m i n s k y 提出了 s n a r c s ( s t o c h a s t i cn e u r a l a n a l o gr e i n f o r c e m e n tc a l c u l a t o r s ) 的强化学习计算模 型【3 】，而f a r l e y 和c l a r k 提出了另一个神经网络学习机。m i n s k y 于1 9 6 1 年发表的 论文s t e p st o w a r d a r t i f i c i a li n t e l l i g e n c e ) ) 产生了较大反响，在该文中他对几个与 强化学习相关的主题分别进行了讨论，包括信任分配问题( c r e d i ta s s i g n m e n t p r o b l e m ) 【4 】，该问题是研究强化学习所必需，也是现在所有研究者关注最多的难 点与重点。1 9 6 5 年w a l t z 和f u ，1 9 6 6 年m e n d e l 等分别在各自的工程文献中使用 了“强化和“强化学习【5 】 等词。1 9 5 5 年f a r l e y 和c l a r k 将研究方向由“试误 学习转向泛化和模式识别的研究，即由强化学习转向监督学习 6 1 。开始了强化学习 和监督学习的混合研究状态。而w i d r o w 等人在对监督学习进行研究时，认识到了 二者之间的不同点，并于1 9 7 3 年与g u p t a 和m a i t r a 改正了早先与h o f r 建立的监 督学习规则( l m s 规则) ，代替为可实现强化学习的新规则【7 1 ，即根据正面或负面 的反馈而不是使用训练样本进行学习，即用“有评价的学习一代替“有教师的学 习 。现代强化学习理论由试误学习理论发展而来，而学习自动机对这一过程有着 重要的影响，其中t s e t l i n 在1 9 7 3 年的工作和b a r t o 和a n a n d a n 发展的可联想的学 2 习自动机地位较为显著。早期的很多研究工作是为了显示强化学习和监督学习之 问的不同。 动态规划从五十年代末有了长足进展，代表人物是b e l l m a n 等。他们于1 9 5 6 年提出了动态规划理论，次年又提出了著名的马尔可夫决策过程( m d p ： m a r k o v d e c i s i o np r o c e s s e s ) ，即最优控制问题的离散统计模式 8 】。d p 是唯一可行的解决 常规统计最优控制问题的方法，也是一种最优化过程，非常适用于需要相关决策 序列的问题。同其它方法比较而言，d p 仍然得到了广泛应用而且是特别有效。d m 的不足之处在于，随着状态数量的增多任务数量会成指数式增长，就是所谓的“维 数灾难”( t h ec u r s eo f d i m e n s i o n a l i t y ) 。最优控制与强化学习共同点很多，特别是 m d p 。d p 包括策略迭代、值迭代、g a u s s s e i d e l 方法及异步动态规划【9 】，其中前 两个方法应用较多，是主要的方法。 进入八十年代后，人们对强化学习的研究日趋深入，强化学习逐渐成为机器 学习研究领域中的主导部分之一。这是由于新成果在人工神经网络领域不断涌现， 加之计算机技术的飞跃式发展为其提供了良好的技术支持。 强化学习在控制系统中的实际应用于1 9 8 3 年由b a r t o 首次作了介绍，他构建 了一个评价控制系统，该控制系统由两个单元a s e ( a s s o c i a t i v es e a r c he l e m e n t ) 及a c e ( a d a p t i v ec r i t i ce l e m e n t ) 构成，特点是在多次学习之后，能使倒立摆维持 较长时间。1 9 8 8 年，( ( m a c h i n el e a r n i n g ) ) 刊载了s u t t o n 的一篇经典之作：“l e a r n i n g t op r e d i c tb ym e t h o d so ft e m p o r a ld i f f e r e n c e s ”。s u t t o n 在文中提出了著名的瞬时差 分t d ( t e m p o r a ld i f f e r e n c e s ) 方法，该方法的问世使得强化学习中根据时间序列 进行预测的问题得到了解决，并且t d 方法的收敛性在一些简化条件下也得到了证 明。t d 算法得到了许多学者的分析和改进。强化学习中另一个比较有名的算法： q - l e a r n i n g 【1 0 1 由w a t k i n s 等人提出。他们有机结合了t d 和动态规划，并证明了 q 1 e a r n i n g 的收敛性问题。w a t k i n s 的研究很好地推进了强化学习尤其是人工智能 中机器学习的发展。多步的q l e a r n i n g 方法也由j i n gp e n g 及w l i l i a m s 等人提出 来 11 】；1 9 9 0 年，试误学习与最优控制理论和动态规划在理论上被w e r b o s 等人 有机地联系起来【1 2 】。随着三条线索的紧密结合，现代强化学习理论也取得了重 大突破。替代式适合度轨迹 1 3 】( r e p l a c i n ge l i g i b i l i t yt r a c e s ) 计算方法由s i n g h 采用随机逼近的方法来解决最优控制问题时提出来，他还通过比较分析及实际应 用，证明了这种方法学习速度非常快并且可靠性高。r l e a r n i n g 方法由m a h a d e v a n 在1 9 9 6 年通过采用平均强化值的方法提出 1 4 】，他还用q l e a r n i n g 与r l e a r n i n g 作了比较。基于模型及平均强化值的h l e a m i n g 方法【1 5 】，由t a d e p a l i 及d o k y e o n g 3 于1 9 9 8 年提供，该算法的快收敛速度、较好的鲁棒性也在自主导引车的实际检验 结果中得到了证明。 在国内，强化学习的研究工作进行较晚。阎平凡1 1 6 】于1 9 9 6 年介绍了强化学习 方法的主要算法、原理，并对基于可靠度最优的强化学习算法以及在过程控制上 的应用加以研究。张汝波将强化学习应用在智能机器人避碰行为的研究中【l7 1 。蒋 国飞在研究倒摆控制系统时应用强化学习理论，成功对一级倒立摆【1 8 】实现了控制。 目前，国内关于强化学习的研究明显落后于国外。近年来，一些国内高校和 科研机构已对有关强化学习算法和理论开展了研究，但需要进一步拓展深度与广 度。现在强化学习已经应用于非线性控制、机器人规划、模式识别、人工智能问 题求解、多智能体系统、通讯和数字信号处理和交通信号控制等领域，并取得了 一些成功经验，应用前景十分广阔。 虽然当前对强化学习算法和理论的研究已经获得很大进展，但有许多关键问 题仍没有解决。目前已知的的大多数强化学习算法仅能研究离散状态和离散行为 空间的学习任务，而对于连续、高维空间的m d p 问题仍然未能取得突破。现有的 强化学习泛化方法具有学习时间过长等问题，这就决定了尽管强化学习已经具有 了很多理论，但仍不能在实际应用中满足人们的期望。 1 2 2 强化学习在交通信号控制中的应用 由于强化学习在大空间、复杂非线性系统中具有良好的学习性能，近年来强 化学习在城市道路信号控制领域得到了一定的应用。美国学者t h o r p e t l 9 】等人首先 将在交通信号控制领域应用了强化学习，且提出了强化学习中的s a r s a ( 状态 动作、回报、动作) 算法，基于信号灯的奖惩函数，预测全部进入交叉口车辆的 延误时间，基于神经网络来控制信号灯。加拿大学者a b d u l h a i e 2 0 】建立了以车辆排 队长度最短为目标，采用q 学习对单个独立交叉口进行控制。荷兰学者w i e f i n g 2 l 】 以全部车辆进出城市所通过的信号灯累计延误时间最小为目标，建立了基于车辆 的奖惩函数，将q 学习应用到交通信号控制领域，将车辆选择最优路径和单路口 延误最小进行了优化组合。卢守峰【2 2 】以进入交叉口车辆的总延误最小为目的，验 证了q 学习控制的优越效果。欧海涛【2 3 】提出以一个a g e n t 控制单个交叉口的方式， 实现了交叉口信号控制，采用多a g e n t 协调控制实现对多个信号灯交叉口组成的 道路网络流量优化，从而消除交通堵塞。马寿峰【2 4 】中提出了一个采用q 学习方法 对单个交叉口控制的方法，a g e n t 根据检测到的交通量数据进行决策执行一个动作 ( 动作有两个，一个是停止绿灯相位转变为红灯相位，另一个是维持绿灯不变至 下一次决策时间) ，动作执行后过一段时间( 5 s ) 再检测一次交叉口的交通量数据， 4 并据此掌握交通信号控制拓扑结构的分布式特征，使其很适合于采用多a g e n t 技 术，尤其对于具有较大变化的交通状况( 如交通事故) ，多a g e n t 的分布式处理和 协调技术尤其合适。 1 3q 学习算法的特点及存在的问题 q 学习算法具备两个十分突出的特点：第一，不需要预先知道环境模型，可 用于环境未知或环境模型非常复杂难以建立的学习任务；第二，不需要等到任务 结束时才根据最后的结果进行学习，q 学习采取了步步为营的学习方式，每个时 间步都利用过去获得的经验值对q 值进行更新，可进行全面的在线学习。w a t k i n s 与d a y a n 通过采用随机过程和不动点理论，证明了以上的q 学习过程能够收敛到 最优的状态动作值函数矿，而且给出了以下收敛性条件： ( 1 ) 学习任务应该具有m a r k o v 性质； ( 2 ) 需要无限次遍历每个状态动作对； ( 3 ) 所有状态- 动作对的q 值函数使用l o o k u p 表的形式存储，每个状态动作 对分别对应于一个元素； ( 4 ) 学习步长口，的取值，需要满足一定条件：y a 。= o 。且y 口； - j 算法【3 2 1 等等。其中，应用最 为广泛的是q 学习算法，几乎现有的强化学习算法都可以看作是q 学习算法的变 种。q 学习算法的提出和理论的完善被公认为是强化学 - 3 进入发展时期的一个重 要标志【3 3 1 。现在本文以q 学 - - - j 算法为例，简单介绍强化学习的基本理论。 2 3q 学习算法的基本理论 2 3 1m a r k o v 决策过程模型 m a r k o v 决策过程( m a r k o vd e c i s i o np r o g r e s s ，m d p ) 也是强化学习理论的基 础和核心之一。q 学习算法【2 9 1 首先假设其学 - j 任务可以通过m a r k o v 决策过程模型 来建模。 一个经典的m d p 是由四元组 组成，其中，s 表示环境状态集；a 表 示可执行的动作集；乃s a s 一【0 ，l 】表示状态转移概率函数，r g ，口，j ) 是指在状 态s s 下；执行动作a a 时，环境状态由s s 转变到s s 的概率；r ：s a 贸表 示奖励函数，r s ，口) 是指在状态5 下执行动作a 后，智能系统所得到的奖励。另外， 通常分别使用瑶和彤来表示r g ，口，j ) 和尺g ，口) 。一般我们把状态转移概率函数和奖 励函数一起称作环境模型，反映了环境对智能系统的行为如何响应。 假设事件从时刻0 到时刻t 的发生序列为s o ，a o ，s ，a l ，q ，a ，其中，表示 奖励值，当且仅当式( 2 4 ) 成立，则称该模型具有m a r k o v 性。 e 冬，+ l ，+ l i j o ，口o ，s i , a l , - - - ，s f ，口f = e b f + l ，+ l b f ，口f j ( 2 4 ) 上式意味着：下一个状态s 川和奖励值+ 1 ，仅仅由上一个状态s ，和动作a ，决定， 然而与上一时刻之前发生的事件或状态无关。这也说明了在m d p 模型下，任何时 刻之前( 含该时刻) 的所有相关的有用信息都包含在该时刻的状态里，因此在决 策时过去的历史信息可以不考虑。正如对弈过程中，后续结果只取决于当前棋局， 对弈者根本不用顾及当前棋局是如何形成的。 2 3 2 期望回报函数 在m d p 模型下，智能系统的学习目标是获取尽可能多的累积奖励，为了实现 该目标，智能系统使用期望回报函数来量化这个累积奖励值。回报函数是指智能 系统在未来可能接收到的奖励序列的函数，由于环境的响应具有随机性，导致未 来获得的奖励值不确定，因而奖励值取其期望值。假设时刻t 2 _ 后的某一段时间内， 智能系统获得的奖励序列为乜小彩+ ， ，那么时刻t 的期望回报函数的定义方式 通常有如下3 种： l o ( 1 ) 有限域模型( f i n i t e - h o r i z o nm o d e l ) r7 、 墨= e + 。 ( 2 5 ) k k = oj 最简单的期望回报函数就是有限域模型，它表示在未来r 时间步所接收到的 期望累积奖励值。 ( 2 ) 无限域折扣模型( i n f i n i t e h o r i z o nd i s c o u n t e dm o d e l ) r 帕、 r = e 厂m ( 2 6 ) l t 卸j 式( 2 6 ) 中，7 【o ，l 】是折扣因子，它确保了当轨) 有界时，上式所获得的r 也 是有限的。此外，厂还反映了智能系统对未来后续奖励的重视程度，取值越大，说 明越重视未来的奖励；反之，则只是越在乎眼前的奖励。特殊情况下，当y 取0 时， 表示只重视下一时刻的奖励；当y 取l 时，表示对未来奖励序列中的所有奖励都同 等地对待。 ( 3 ) 有限域折扣模型：( f i n i t e h o r i z o nd i s c o u n t e dm o d e l ) rr、 墨= e 7 m ( 2 7 ) l k = oj 有限域折扣模型是一种通常被应用于片段式( e p i s o d i c ) 强化学习任务的模型。 片段式强化学习由一个个片段( e p i s o d e ) 组成的，在每个片段的开始时刻，环境 状态都要复位到初始状态，直到该片段结束，下一个片段紧接着开始运行，如此 反复。如学习下棋就是一种典型的片段式学习任务，标准强化学习验证问题也都 属于片段式的。这种情况下，r 一般取从时刻t 到该片段结束，所持续的总时间。 2 3 3 状态动作对的q 值函数 奖励是通过执行动作后而获得的，因此，要获取最大的期望回报，选择的动 作就需要依靠最优的动作策略来得到。如果使用函数万：s 么j 【o 1 】来表示动作策 略，则在状态s 下选择动作口的概率表示为如口) 。在q 学习算法中，使用状态动 作对的q 值函数将状态动作对、策略万和期望回报函数厂联系在一起，它表示在某 个状态和策略下，执行某个动作的好坏程度，好坏的标准是相对于期望回报函数 来说的。 在给定状态一动作对 和策略万下，该状态动作对的q 值函数q ”g ，a ) 定义如下： q 石g ，a ) = e , , r t l s ，- s ，q = 口 ( 2 8 ) l - 式o e 的疋 表示在策略万下的期望值，而q ”g ，口) 是指在状态s 下，选择动 作a ，以后始终按照策略万来选择动作，最终所获得的期望回报。策略万下的q 值 函数表示某个状态下执行某个动作的好坏程度。当然，好坏的标准是相对于最终 得到的期望回报来说的。使用一种简单的递归形式来重新描述，如下式【3 4 1 ： 厂 q ”g ，口) = 瑶旧+ y 刀g ，a ) q 4 g ，口) l ( 2 9 ) ，l a e a j 式( 2 9 ) 被称为q ”o ，口) 的b e l l m a n 方程，其构成了q 学习中q 值函数更新操作 的学习基础。 至此，q 学习算法的学习目标明确为：为了找到一个动作策略，并使得该策 略下，所有状态- 动作对对应的q 值函数最大，记作万+ 。般的m d p 至少具有一个 万，而i 虫b e l l m a n 方程可知，不同的万都具有相同的q 值函数，称为最优q 值函数， 记作q 。在式( 2 9 ) 中，用尼来替代7 ，可以得到如下式( 2 ，1 0 ) 的最优b e l l m a n 公式： q g ，口) = 瑶+ 孵q g 口) ( 2 1 0 ) 逆向考虑，假如我们可以通过某种方法得到q ，并使用一个列表的形式来存 储所有状态动作对的最优q 值函数，那么是否能直接由这个表得到一个最优策略 万，来指导智能系统的行为并实现最大化期望回报的目标呢? 答案是肯定的。根 据式( 2 1 0 ) ，对于任意状态j s ，它只需要简单地找出能使q 值函数最大的那个 动作a 即可，数学表达式为： a + = a r g m a x q g ，口) ( 2 1 1 ) 从而可以通过查表的方式，直接获得一个刀+ 如下： 万6 ，口) ：l n 2 嘲1 辫q b ，口) ( 2 1 2 ) 、。l o e l s e 将这个刀称为m d p 的确定性最优策略，简称最优策略。q 学习算法是通过学 习优化这个列表，从而间接获得最优策略的一种强化学习算法，也被称作值函数 学习算法。我们将存储所有状态- 动作对的q 值函数的列表，记作l o o k u p 表，其大 小为i s l xi a i ，是指集合木的规模。 2 3 4 动作选择机制 前文已经介绍了q 学习算法的目标函数q 值函数。在环境模型( t 和r ) 已知的情况下，我们可以采用动态规划的方法进行m d p 模型的求解。但在现实世 界中，丁和尺往往无法直接获得，这时就需要智能系统与环境进行有效的交互， 并从交互结果中获取经验来学习最优q 值函数。在强化学习算法中，智能系统如 何与环境进行有效的交互，主要体现在智能系统如何根据感知到的环境状态来选 择动作并且执行，称为动作选择机制。 1 2 在智能系统的工作和学习过程中，其动作选择机制是不相同的。在工作中， 智能系统假定当前得到的l o o k u p 表是已经最优的，在选择动作时，为了获得尽可 能多的奖励，就在每个状态下，直接查找l o o k u p 表的q 值函数，从而选择使得q 值 函数最大的一个动作。但是在学习中，智能系统不但需要获得尽可能多的奖励， 还需要快速学习获取最优的q 值函数，使l o o k u p 表不断地按照最优的方向更新。 因此，在学习过程中，动作选择机制的设计要同时考虑两个相互矛盾的因素：“探 索( e x p l o r a t i o n ) ”和“利用( e x p l o i t a t i o n ) 。“探索是指a g e n t 要遍历所有的状 态动作对，争取获得全面的经验知识，从而收敛到q ，但过多的“探索 肯定会 带来无用的信息，占用存储资源和计算资源，进而降低学习速度；“利用 则是指 a g e n t 为了获取高的回报函数，主要根据当前的l o o k u p 表选择可以获得高回报的动 作，减少了“探索”可能会产生更高回报的、也可能产生低回报的动作，然而， 过度“利用同样会导致系统总是朝着一个方向进行“探索，从而找不到最优解 q 。因此，为了能快速收到到q ，设计合理的动作选择机制，达到“探索和“利 用 的相对平衡，具有重要的意义。 占一g r e e d y 机制1 3 5 】和b o l t z m a n n 分布机制【3 6 】是当前强化学习领域中应用最为广 泛的两种动作选择机制。它们共同的原理有：通过给各个动作赋予一定的选择概 率来实现对全部动作的尝试。下面是这两种机制的简单介绍： ( 1 ) 占- g r e e d y 机制 对于给定的随机系数占【o ，l 】，利用s g r e e d y 机制选择动作的方法就是按照概 率( 1 一占) 选择具有最大q 值的动作，如果该动作没有被选中，则在可执行动作集 彳中随机地选择一个动作来执行。 ( 2 ) b o l t z m a n n 分布机制 对于给定的随机系数t l ，则在状态s 下，动作a 被选择到概率由下式决定： ，口6 ，口) ，r p rk ，= 口k = s = 寻丽( 2 1 3 ) 厶。 口i e 由式( 2 1 3 ) 可得：p r 缸，= 口k = j = l ，然后按照轮盘赌博的步骤选择将要 执行的动作。为了不失一般性，设置可以执行动作集a - - ( a 。，a ：，口，) ，则轮盘赌博 的操作步骤如下： s t e p h 在【o ，l 】之间产生一个随机数r a n d ；令s u m = 0 ，i = l ； s t e p 2 ：s u m4 - - s u m + p r k f = 口f l q2 s ； s t e p 3 ：若r a n d s u m ，则被选中的动作为江l ，否则转s t e p 2 ，且i 卜f 十1 通常我们将占一g r e e d y 机制中的随机数s 和b o l t z m a n n 分布机制中的温度控制 系数丁都称为探索力度参数，这是因为它们的取值越大，就意味着算法越偏向于 随机“探索”。在智能系统学习早期，l o o k u p 表中的元素并没有达到成熟，“利用 它进行动作决策并不能得到很好回报，应该偏重于“探索”新知识，完善l o o k u p 表中的元素，随着学习的进行，再渐渐转向于依靠l o o k u p 表进行动作决策。据此， g 和r 的取值可以采取随时间推移而递减的形式，以便更好地实现从“前期重探索” 到“后期重利用 的平衡过渡。 2 3 5q 值函数的更新 在有效的交互方式下，智能系统可以从交互结果中获得经验，应用于l o o k u p 表的更新。交互的过程中，q 值函数的更新过程是由最优b e l l m a n 公式引申而来的， 可以使得q 值函数向最优的方向更新。记时刻f 观察到的环境状态为s ，选择一个 动作a ，并执行，在下一时刻t + l ，状态转移到s 州，智能系统得到一个奖励+ l ， 从而构成了一个经验样本 ，则按照式( 2 1 4 ) 更新状态动作对 的q 值函数： q f + ，g ，a ，) = 0 一娩g ，a ，) + 吼i + 。+ ym a xq ，g ，口) l ( 2 t 4 ) l f + i c 门 j 其中，a ， 0 , 1 】为学习算法在时刻t 的学习因子，它主要用于控制学习速度， 其值越大，q 值收敛速度越快，但是容易引起不成熟的收敛：乜+ t + m a x q b ，4 ) j 为更新目标，完全由已获得的知识组成。 2 4 强化学习的其他主要算法 2 4 1 蒙特卡罗算法 蒙特卡罗算法【3 7 , 3 8 】通过评估值函数来发现最优策略，它不需要环境的全部信 息，而只需要经验知识如部分有关状态序列、动作行为集以及同环境交互产生的 奖赏值的信息。 蒙特卡罗算法将取样回报平均化处理来解决强化学习问题，它将解决的问题 分解成幕( e p i s o d e ) 。当环境状态为终止状态时，将得到累积回报赋予开始状态j 的 值函数y ，从s 出发到终止状态t 的过程中，s 可能不止出现一次，对s 的值函数的 更新有两种方法：f i r s tv i s i tm c 和e v e r yv i s i tm c 。f i r s tv i s i tm c 将回报赋予第一 次访问的j ，e v e r yv i s i tm c 将每次访问5 到t 的回报平均后赋予s 的值函数。二者 在理论上是有区别的，它们都收敛到y 4 。值函数更新规则为： z ( s 。) 卜矿g 件。) + 口【r ，一矿g ，) 】( 2 15 ) 其中，r ，为t 时刻的奖赏值，口为步长参数。 1 4 蒙特卡罗算法是直接同环境交互获得经验来优化动作行为，不需建立一个环 境的动态信息模型，该算法中一些状态集的值函数的计算不依赖于其它状态集的 值函数，所以可以只在那些能够精确描述环境信息的状态子集中计算所获得的平 均奖赏值。 2 4 2 瞬时差分学习算法 蒙特卡罗算法并不是强化学习所独有的方法，更能代表强化学习的中心思想 和新意的是瞬时差分( r d ) 算法【3 9 1 ，它是一种增量式学习算法，是动态规划方法与 蒙特卡罗算法的结合。它不需要建立环境的动态信息模型，也不需要等到最终输 出结果输出之后再调整以往学到的经验，而是直接从交互经验中学习。 设观察结果序列为x a ，而，z ，其中是在时刻f 得到的观察向量，z 是 该序列的结果，对每个观测结果序列，相应的预测序列为p ，岛，p 。每个岛， 都是z 的估计，每个观测决定一个变化量w f ，一个完整的序列处理后，权值形可 按下