（计算机应用技术专业论文）基于因素化表示的强化学习方法研究.pdf

摘要 强化学习是随机环境中解决决策问题一种有效的方法。然而，在大状态空间， 特别是在复杂随机状态下的应用领域，它仍然没有解决“维数灾难 的问题。目 前，因素化强化学习作为强化学习在时间和空间上的扩展，已经被证明比强化学 习更适合解决大状态随机控制问题，在机器人导航等方面有着广阔的应用前景。 但是，目前的研究工作集中在学习前状态空间的前期处理，对学习过程缺乏深入 研究。本文围绕强化学习前的状态空间的前期处理以及学习过程中值函数的值的 存储和表示，对以下方面进行了研究和探讨： 文章首先介绍了因素化学习的基本学习理论和研究进展，并对四种典型的强 化学习算法作了分析比较，分析了它们的各自特点和适用情况，为后面的工作中 算法的选择提供了基础。 其次提出了改进的基于因素化表示的动态规划方法，针对动态规划方法中求 解精确的y 疗值计算量复杂的问题，提出了改进的使用生成y 。的线性近似值以获取 算法的加速的方法；针对传统强化学习算法使用值函数l 0 0 k u p 表存储和表示值 函数的值存在着的冗余度过高的问题，提出了决策树方法，并在后面的仿真实验 中验证算法效果。 最后提出了一种新的基于因素法方法的t d ( 名) 算法。其基本思想是状态因 素化表示，通过动态贝叶斯网络( d y n a m i cb a y e sn e t w o r k s ，d b n s ) 表示m a r k o v 决策过程( m a r k o vd e c is i o np r o c e s s ，m d p ) 中的状态概率转移函数，结合决策 树( d e c i s i o nt r e e ) 表示t d ( 五) 算法中的状态值函数的值，大大降低了状态空 间的搜索与计算复杂度、以及数据的冗余度，因而适用于求解大状态空间的m d p s 问题，对照实验证明了该表示方法是有效的。 关键词：因素化强化学习；环境模型；动态贝叶斯网络；决策树；t d 算法 a b s t r a c t r e i n f o r c e m e n tl e a m i n gi s 锄e f f e c t i v em e t h o dt os o l v et h ep l a np r o b l e mi nt h e s t o c h a s t i c e n v i r o n m e n t ，h o w e v e r i nt h el a r g e s t a t e s p a c e ，e s p e c i a l f o r a p p l i c a t i o n p r o b l e m sw i t hc o m p i e xs t o c h a s t i cs t a t e s ，t h e “d i m e n s i o nc u r s e p r o b l 啪h a s n tb e e n s o l v e d y e t a tp r e s e n t ，t h e f a c t o rr e i n f o r c e m e n tl e a m i n gw h i c h d e v e l o p s f i r o m r e i n f o r c 锄e n tl e a m i n gi ns t a t es p a c ea n da c t i o ns p a c e ，h a sb e e np r 0 v e nt ob em o r e e f f c c t i v et os o l v et h el a i 苫es c a l es t a t es t o c h a s t i cc o n t r o lp r o b l e m ，a n db ea p p l i c a b l ei n t h ea g v n a v i g a t i o n n o wf o rt h ea l m o s ta l lr e s e a r c h e s n o wa ut h er e s e a r c hf o c u so n t h ed i s p o s i t i o no ft h es t a t es p a c eb e f o r et h er e i n f o r c e m e n tl e a m i n g ，a n dt h e r eh a s b e e nr e l a t i v e l yl i t t l er e s e a r c ho nt h ep r o c e s so fr e i n f o r c e m e n tl e a m i n g b a s e do nt h i s i d e a ，t h ef 0 l l o w i n ga s p e c t sa r ei n v e s t i g a t e da n dd i s s c u s s e d f i r s t ly ，t h eb a s i ct h e o r yb a c k g r o u n da n dd e v e l o p m e n to ff a c t o rr e i n f o c e m e n t l e a m i n ga r ei n t r o d u c e d f o u rt y p i c a lr la l g o r i t h m sa r ed i s c u s s e da n dc o m p a r e d t h e 锄p i r i c a lr e s u l t sa r ep r e s e n t e dt os h o wt h e i rd i f 蚕e r e n c e sa n dc h a r a c t e r i s t i c s ，w h i c h o f f c rab a s i st oc h o o s et h er i g h ta l g o r i t h mi nt h ef o l l o w i n gw o r k s e c o n d l y an e wm e l t h o df o rd y n a m i cp r o g r a m m i n g b a s e do nf a c t o r e d r e p r e s e n t a t i o ni sm e n t i o n e di nt h i sp a p e r w h 吼w eu s ed pm e l t h o dt os o l v ec o m p l e x r lp r o b l e m s ，i t sh a r dt oc o m p u t et h ea c u a t ev a l u eo fy 膏an e wm e l t h o db a s e do n l i n e a ra p p r o x i m a t e l yy 石i sp r o p o s e dt os p e e du pt h ea l g o r i t h m i nt r a d i t i o n a lr l ，w e a l w a y su s el o o k u pt a b l et os t o r e t h ev a l u eo ft h ev a l u e如n c t i o n ，b u ti th a sa p r o b l e m ，t h a ti si t h a sah i g hr e d u n d a n c y ；am e l t h o dd e c i s i o nt r e ei sp r o p o s e d ，t h i s m e t h o dw i l lb ee x 锄c di nt h es i m u l i n ke x p e r i m e n ti nt h i st h e s i s f i n a l l y an e wa l g o r i t h mf o rt d ( 五) b a s e d o nf a c t o r e dr e p r e s e n t a t i o ni sm e n t i o n e d i nt h i sp a p e r t h em a i np r i n c i p l eo ft h ea l g o r i t h mi st h a ts t a t e sa r ef h c t o r e dr e p r e s e n t e d ， a n dm a k i n gu s eo fd y n a m i cb a y e s i a nn e t w o r k s ( d b n s ) t or e p r e s e n tt h ec o n d i t i o n a l p r o b a b i l i t y d i s t b u t i o n si nm a r k o vd e c i s i o np r o c e s s e s ( m d p s ) ， t o g e t h e r w i t h d e c i s i o n t r e e sr e p r e s e n t a t i o no fv a l u e 如n c t i o ni nt h ea l g o r i t h mo ft d ( 五) t ol o w e rt h e s t a t es p a c ee x p l o r a t i o na n dc o m p u t a t i o nc o m p l e x i t y t h e r e f o r et h ea l g o r i t h mi sa p r o m i s ef o rs o l v i n gl a r g e s c a l em d p sp r o b l e m sw h i c ha r eo fah u g es t a t es p a c e t h e v a l i d i t yo ft h i sr e p r e s e n t a t i o ni sd e m o n s t r a t e db ye x p e r i m e n t s k e y w o r d ：f a c t o r e dr l ；m o d e io fe n v i r o n m e n t ；d b n ；d e c i s i o nt r e e ；a l g o r i t h m o ft d i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作：栅 ) 日期：y 口夸月幻日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密由。 ( 请在以上相应方框内打“ ) 作者签名：戴忡 日期砂咯5 月户日 新虢仫场嗍p 户占月乡日 第一章绪论 1 1 本课题的研究背景及意义 智能体( a g e n t ) 作为一种集环境感知、动态决策与规划、行为控制与执行等 多种功能于一体的综合系统，相关研究成果已经在星球探测、军事侦察、医疗服 务、危险及恶劣环境作业等方面得到了广泛应用。在其各项研究和应用中，导航 ( n a v i g a t i o n ) 是最基本和最重要的问题，a g e n t 在其工作环境中必须具有可靠而 灵活的自主移动能力。而在实际应用中由于对外界环境信息的缺乏以及外界环境 自身所存在的不可预知性，a g e n t 自主学习( a u t o n o m o u sl e 啪i n g ) 及相应的智能控 制( i n t e l l i g e n tc o n t r 0 1 ) 成为其能否在未知环境下顺利实现导航任务的关键技术。 强化学习( r e i n f o r c e m e n tl e a m i n g ，r l ) ，又称增强学习或再励学习，作为 一种机器学习方法，为我们提供了一种重要的智能控制方式。强化学习让a g e n t 学习最优策略，即学习一组从状态到动作的映射，这个映射使得a g e n t 从环境中 获得的奖赏最大。强化学习和其他学习的不同之处在于：在强化学习中，外部环 境并不会告知a g e n t 哪个动作是最好的，而是让它自己与环境不断交互，不断地 试错( t r i a l 锄d e r r o r ) ，从环境中得到奖惩信息，积累经验，然后让自己判断那个 动作是最好的。强化学习最吸引人的地方在于环境模型状态和a g e n t 动作的选择 是具有随机性，相比以前将控制问题模拟为确定模型，强化学习显然更符合现实 情况；另外，在一个复杂的决策系统中，可能事先关于环境的信息是很少的，这 样监督学习是不可行的，采用强化学习这种不断试错，从而自己学习的方法是必 要的。强化学习已被证明在很多方面取得了不错的成绩，但是它还是没有摆脱“维 数灾难”的问题，当状态空间变得巨大时，计算量将成指数增长，从而使求解变 得困难。为了解决大状态空间问题，a i ( a r t i f i c i a li n t e i l i g e n c e ) 研究者采取了各 种方法，状态因素化方法是其中之一。 与传统强化学习方法在解决大状态空间问题时采用状态计数表达方式不同， 因素化强化学习是采用状态因素化表达【2 】( f a c t o r e dr e p r e s e n t a t i o n ) 的。这种方法 的核心思想是将系统状态细化为状态因素。其优点在于：缩小状态空间，从而节 省计算时间和存储空间。但当a g e n t 所处的环境非常复杂时，因素化的状态空间 在进行强化学习时依然饱受大状态空间问题的困扰。为了进一步简化状态空间， 降低学习过程中的时间和空间耗费，研究者采取了一系列措施，具有代表性的有： h o e v 的s p u d d 算法【3 1 ，b o u t i l i e r 的决策树【4 】方案以及d e a r d e n 的动态贝叶斯网络 方案【s 】。这些方案的提出大大降低了强化学习的时间和空间复杂度，并且能够较好 的解决百万状态级别的大状态空间问题， 法主要应用于动态规划( d y n a m i c 但我们也不难发现，目前已有的这些算 p r o g r a m m i n g ，d p ) 、线性规划( l i n e a r p r o g r a m m i n g ，l p ) 等算法中。众所周知，使用动态规划和线性规划这些方法进行学 习时，时间和空间的花费都不小，应对规模较小的问题时，还可以从容应对，但 随着应用的深入，状态空间日益庞大，现有的解决方案已经不能够胜任，因此新 算法新方案的提出是必须的，因此有必要深入研究。 1 2 本课题研究领域的研究动态 因素化方法由b o u t i l i e r 等人于2 0 0 0 年引入解决大状态空间问题。让一个系统 忽略与当前任务没有直接关系的一些细节可以有效地减少a g e n t 需要搜索的整个 状态空间。在复杂的环境中，人类通过有意识、系统地忽略一些无关细节，从而 能更有效地解决问题。比如说：当我们外出时，要不要打伞? 我们通常会看一看 外面有没有下雨、紫外线强度怎样? 而不是将温度、空气湿度、风速等不相关的 因素统统看个遍，因为这样费时又费力。人作为一种高智能的生物，在我们做一 件事情前，通常会考虑到一些因素、但绝不是现实生活中的所有因素，因为那是 不可能的，也完全没有必要。在强化学习过程中a g e n t 进行动作选择时，完全可 以有意识的忽略掉一些无价值、无意义的状态信息。上面这个例子中，在没有进 行状态空间优化之前，如果进行强化学习运算，我们需要一个5 5 的方阵才能保 存当前的状态信息，而优化之后，只需要一个2 囊2 的方阵就可以了。当问题变得 更加复杂时，这种优势也将更加明显。针对大状态空间问题中的状态空间的优化 问题，b o u t i l i e r 等人提出了使用动态贝叶斯网络过滤无用状态的方案。陈焕文等 人则根据状态的特征得出状态相似性启发式，再根据该启发式对状态空间进行聚 类【6 】o 经典强化学习中采用了冗余度很高的l 0 0 ku p 表【7 】来存储状态值函数的值。 s u t t o n 证明了在满足一定条件下，表格型的强化学习以概率l 逼近最优解【8 1 。对状 态空间离散化可以很好地与表格型的强化学习算法结合，文献 9 证明了对连续动 作空间离散化后q 学习的收敛性。但是，当状态空间连续而复杂时，离散化使得 维数成指数增长，不可避免地会带来“维数灾难”。b o u t i l i e r 和d e a r d e n 在文献【2 】 中使用了决策树存储状态值函数的值，决策树的提出不仅提高了查找和修改值函 数的效率，而且通过规则提取使得某些具有共同特征因素的一类状态值可以用同 一个状态值表示，这样极大的降低了数据冗余度和计算的复杂度，提高空间的利 用率。h o e y 在文献 3 中采用代数决策表( a l g e b r a i cd e c i s i o nd i a g r a m s ，a d d s ) 存储值函数。 尽管目前因素化表示方法的研究者在解决大状态空间问题上采用的方式多种 2 多样，总体而言是围绕下面三个方向展开：如何有效的精简状态空间：状态 值函数的值的表示和存储，在强化学习算法中应用。 b o u t i l i e r 和d e a r d e n 提出的因素化表示方法使用动态贝叶斯网络来描述状态 转移概率函数( s t a t et r a n s i t i o np r o b a b i l i t yf u n c t i o n ) ，在策略迭代( p o l i c yi t e r a t i o n ， p i ) 和值迭代( v a l u ei t e r a t i o n ) 这些算法中采用决策树结构的策略和值函数表示 方法，使计算倾向于状态空间中必要的部分，避免了不停的穷举。这种方法的重 点是使用决策回归理论( d e c i s i o n t h e o r e t i cr e g r e s s i o n ，d t r ) ，对于解决大状态 空间问题提供了快速有效的解决途径。 s p u d d 算法使用了基于代数决策表结构表示的m d p 状态进行学习，尽管它只 能计算那些仅含两百个不同值的值函数，但解决了具有1 0 8 个状态的大规模m d p 问 题。 g u e s t r i n 等人提出一种类似于使用贝叶斯网络进行无用状态过滤的线性规划 分解的新方法【1 0 】。 d i e t t e r i c h 和f l a n n 提出了类似与s p u d d 的新算法】，这种算法通过突出强 化学习中b e l l m a n 值备份和基于解释的泛化之间的关系来实现。 g i v a n 提出了一种利用随机双仿真尺度来对状态分组的计算方法，分类以动作 转移和奖赏分布为基础进行计算【1 2 】。 k i m 提出的最小化模型方法允许抽取状态具有不同类的值【1 3 】。 陈焕文等人提出了根据状态的特征得出状态相似启发式，再根据启发式对状 态空间进行聚类，极大缩减了状态空间中的状态，较好的解决了大状态空间问题。 因素化方法在强化学习领域的研究正在受到广泛的重视，在动态规划领域， b o u t i l i e r 等人对这类方法进行了全面细致的综述，尽管目前还没有充足的证据表 明该方法优于传统的方法，但已有的迹象表明这是一个很有前途的研究方向。目 前，将因素化方法用于强化学习其他模型才刚刚开始，尚有待于进一步深入地探 索。 1 3 本文的主要研究内容 本文主要讨论因素化方法在强化学习中的应用问题。围绕大状态空间问题中 大量无效状态的过滤，强化学习学习中状态值函数的存储、表示、查找以及修改， 以及因素化方法在强化学习中应用等问题。鉴于目前已有的大状态空间问题解决 方案中存在的强化学习中值函数的l o o k u p 表冗余度过高以及动态规划和线性规 划中存在的时间和空间复杂度过高的的问题，本文将在状态因素化的基础上，通 过d b n s 进一步过滤掉无用的状态因素，降低了智能a g e n t 需要搜索的状态空间； 在强化学习学习过程中，传统的值函数l o o k u p 表将被更加紧凑的决策树或代数 决策表替代，从而更加有利于状态值函数的存储、表示、查找和更新，提高了强 化学习学习的效率。 本文所做的工作包括一下几个方面： l 、对d b n s 理论以及它在非决定性状态因素的过滤方面的应用进行分析和讨 论，并通过实例进行说明。 2 、对几种典型的强化学习算法作了理论上和实验上的比较，分析了它们的各 自特点和适用情况。 3 、对决策树特点进行了分析，对其在强化学习中应用进行详细的介绍，为其 在强化学习中的应用提供了理论基础。 4 、改进了b o u t i l i e r 提出的因素化的动态规划方法，针对d p 算法中时间和空 间复杂度大的不足，提出了一种新的改进的因素化的d p 方法。 5 、针对上述改进的因素化的d p 方法存在迭代过程复杂的不足，提出了一种 新的基于因素化表示的t d ( 九) 算法。 1 4 本文的组织结构 本文的组织结构如下： 第1 章为绪论，介绍了研究因素化方法背景和意义，对因素化强化学习中的 因素化学习理论和相关文献以及基于强化学习的因素化学习做了简单的综述，并 介绍了本文所做的工作和文章的组织结构。 第2 章介绍了因素化强化学习的基本理论框架，包括强化学习的原理和因素 化强化学习的基本理论问题。对强化学习中的三个重要算法( q 学习、s a r s a 算法以 及d y l l a 算法) 作了简介并对t d 算法作了重点讨论。详细介绍了因素化强化学习的 理论思想，包括因素化强化学习的基本思想及其发展、因素化强化学习方法，并 对目前的研究进展及将来应用作了分析。 第3 章主要介绍了d b n s 和决策树的基本概念和原理，重点介绍了其在状态 空间精简以及状态值函数的值的存储上的应用。 第4 章提出了改进的基于因素化表示的动态规划方法，针对动态规划方法中 求解精确的旷值计算量复杂的问题，提出了改进的使用生成旷的线性近似值以获 取算法的加速的方法；针对传统强化学习算法使用值函数l o o k u p 表存储和表示 值函数的值存在着的冗余度过高的问题，提出了决策树方法，并在后面的仿真实 验中验证算法效果。 第5 章提出一种新的基于因素化表示t d ( 九) 算法，这是因素化方法在强化 学习上应用的一种深入研究，主要阐述了d b n s 在精简系统状态空间中的状态以 及使用决策树紧凑表示和存储状态值函数的值上的应用，最后通过与t d ( 九) 算 4 法的结合，并在随后的仿真实验中验证了本算法在解决大状态空间问题上的优越 性。 第6 章，全文的总结：对全文的主要研究工作进行总结，并展望下一步的研 究工作。 第二章强化学习基本理论 强化学习是机器学习研究的一个非常活跃的领域，同时在运筹学、控制工程、 决策理论以及微观经济学等领域也倍受关注。它是不同于监督学习和无监督学习 的另一类机器学习方法。强化学习的基本思想与动物学习心理学中的“试错”学习 的研究密切相关，即强调a g e n t 在与环境的交互中学习，通过环境对不同行为的 评价反馈信号来改变动作而选择策略以实现学习目标。来自环境的评价反馈信号 通常称为奖赏( r e w a r d ) 或强化信号( r e i n f o r c 啪e n ts i g n a l ) 。强化学习系统的目标就 是最大化这个期望奖赏信号。本章将讨论强化学习的一些基本理论问题，分析比 较几种典型的学习算法，并着重对其中的t d ( 九) 算法进行讨论，最后将对因素 化表示方法中的几种重要解决方案作详细的分析。 2 1m ark o v 过程与强化学习 2 1 1m a r k o v 过程 大多数关于强化学习方法的研究都是建立在马尔可夫决策过程( m a r k o v d e c i s i o np r o c e s s e s ，m d p s ) 理论框架之上的【1 4 】【i 5 】【16 1 ，虽然强化学习方法并不局限 于m d p s 【17 1 ，但离散、有限状态的m d p s 框架是强化学习算法的基础。所谓m d p 是指单时间参数的、时间离散的、并具有有限( 通常情况下) 的状态与动作空间的一 个有限决策过程【1 8 l 。它是当今值函数估计强化学习研究的基础，是对一般强化学 习问题求解模型的一种标准简化。在这种框架之下，我们研究强化学习的算法及 其性质非常便利。下面将简单描述一下m d p 模型，以及如何利用该模型进行强化 学习研究。 顺序型强化学习问题可以通过m d p 建模，下面给出了m d p 模型的四元组定 义。 s ， 毛) ，r ( 墨，口，s ，) ，( 丑，口) ，f ，口4 - ) ) ，其中： 环境状态集合s ：用来表达环境的所有可能的状态的集合，在特定的时间步， a g e n t 所处的环境状态为当前状态而s 。 动作集4 ：a g e n t 在当前状态毋所有可能采取的动作的集合，在特定的时间 步，a g e n t 选择的当前动作口，彳( s ，) 。 状态转移概率函数r ( 墨，口，s f ) ( 简称为r 函数) ：a g e n t 在状态墨采用动作口转移到 状态s ，的概率。 6 奖赏函数，( 岛，口) ( 简称为尺函数) ：a g e n t 在状态采用动作口转移到状态s ，是获 得的瞬时奖赏( i m m e d i a t er e w a r d ) ，这个值是根据不同的环境状态事先确定好的。 a g e n t 的最终目标是使获得的累积瞬时奖赏值最大。 在m d p 模型中，在与环境进行交互的每一步f ，f = o ，1 ，2 ，a g e n t 感知环境 的状态i s ，然后选择一个动作口r 4 ，l ，在执行动作口，之后，环境反馈给a g e n t 一个数值型奖赏o 和下一个环境状态s 川，即m d p 的本质是当前状态向下一个状 态转移的概率和奖赏值只取决于当前状态和所选择的动作，而与历史状态和历史 动作无关【憎】。 a g e n t 的目标就是要学习这样一个最优策略万：s 么一【o ，1 】，其中彳= u 脚4 ，) ， 使得目标函数矿满足某一设定的要求。 因此根据m d p 模型，一般来说，在r 函数和r 函数己知的环境模型中，可以 采用动态规划方法求解最优策略；而强化学习则偏重于研究在丁函数和尺函数未知 的情况下，系统如何学习最优行为策略【h 】。 2 1 2 强化学习模型与基本要素 强化学习的标准模型结构如图2 1 所示，假设a g e n t 与环境的交互发生在一系 列的离散时刻f = o ，1 ，2 ，；在每个时刻f ，a g e n t 通过观察环境得到状态s 。s ，s 为 可能的环境状态5 ，s ，s 为可能的环境状态集；据此选择一个动作q 彳( s 。) ，其 中彳( s ，) 为状态j ，下的可能动作集；并达到一个新的状态s 州，学习的目标就是学习 一个最优策略刀：s 彳一【o ，1 】，其中彳= v 。s 4 ，) ，使得a g e n t 所得奖赏总和： y 石( t ) = 7 ，：，o 7 l ( 2 1 ) f = 0 最大( 或最小) ，其中y 为0 到l 之间的一个折扣因子，较小的折扣因子赋予 将来的奖赏值以较小的权值；即a g e n t 考虑长期的奖赏，但将来的奖赏带有折扣。 式( 2 1 ) 给出的是无限折扣模型的目标函数形式，其他形式目标函数将会在下文 介绍到。 在文献 1 】中，s u t t o n 等称此类通过交互进行学习以达到目的的学习问题称为 强化学习问题，而图2 1 也可称为强化学习问题中a g e n t 与环境的交互关系图。 、 图2 1 强化学习模型 7 由强化学习基本模型可以看出，一个强化学习系统除了a g e n t 和环境之外， 主要还有四个基本元素：策略( p o l i c y ) ，值函数( r e w a r df u n c t i o n ) ，奖赏函数( v a l u e f u n c t i o n ) 以及环境的模型( m o d e lo f e n v i r o n m e n t ) ( 非必须) 。四个基本元素之间 的关系如图2 2 所示，强化学习系统所面临的环境由环境模型定义，但由于模型中 状态转移概率函数和奖赏函数未知，a g e n t 只能够依赖于每次通过试错所获得的瞬 时奖赏来选择策略。而在选择行为策略过程中，要考虑到环境模型的不确定性和 目标的长远性，因此在策略和瞬时奖赏之间构造值函数( 即状态的效用函数，又 称评价函数) ，用于策略的选择。 图2 2 强化学习系统的四个基本元素 ( 1 ) 策略 策略是强化学习的目标，是a g e n t 进行动作选择的依据，即指a g e n t 针对特 定环境，在一个给定时间产生动作的方法，具体定义为：策略，描述针对状态集 合s 中的每个状态s ，a g e n t 应完成动作集彳中的一个动作口，策略石：s 寸彳是一 个从状态到动作的映射。在策略集合中找出使问题具有最优效果的策略刀，称为 最优策略【2 们。 ( 2 ) 奖赏函数 奖赏函数定义了一个强化学习问题的目标，它将感知的环境状态( 或状态一动 作对) 映射到一个奖赏信号，对产生的动作的好坏作一种评价。奖赏信号通常是 一个标量，例如用一个正数表示奖赏，而用负数表示惩罚。强化学习的目的就是 使a g e n t 最终获得的总的奖赏值尺达到最大，而奖赏函数往往是确定的、客观的， 可以作为改变强化学习策略的标准。 ( 3 ) 值函数 奖赏函数是对某一时刻的动作做出的即时评价，但在大多数问题中，往往需 要考虑a g e n t 行为的长远影响。因此需要定义一个目标函数来表明从长远的观点 确定什么是优的动作。通常以状态的值函数或者状态动作对的值函数来表示此目 标函数。 状态值函数：状态s ，的值定义为a g e n t 在状态s ，执行动作口，及后续策略万所得 到的累计奖赏的期望值，记为矿( 墨) 。 r = ，；+ l + 厂，：+ 2 + y 2 ，：+ 3 + = ，：+ i + 7 r + l ，o 矿，其 中y 称作局部阀值。若爿是测试属性，则y 称作阀值。要确定彳的局部阀值，首先 对丁中爿属性值已知的样本进行快速排序，依次考察排序后的每对相邻值的中间值 ，以及对应的划分条件和。彳y 和彳 y 。假设样本中彳有聊个不同取值，则存在 册一1 个中间值v ，分别对应所一1 个可能的信息增益率r a t i o ，。若r a t i o ，值最大， 则v 7 就是彳的局部阀值，r a t i o y 就是彳的信息增益率。当考察完所有属性，就可 以得到n 的测试属性x 。若x 是连续的，则须在整个训练集上线性搜索x 值，找到 从低到高最接近于x 的局部阀值的x 值作为阀值。 ( 3 ) e c 4 5 算法 为了减少c 4 5 为连续型测试属性线性搜索阀值而付出的代价，e c 4 5 采用了二 分搜索取代线性搜索。e c 4 5 还提出了3 种不同的计算信息增益与阀值的改进策略， 可以根据实际情况采取其中最佳的一种。但e c 4 5 占用内存比c 4 5 多。 综合三种决策树算法的优缺点，由于c 4 5 算法不仅可以处理离散属性，还可 以处理连续属性。考虑到本文的强化学习当中可能遇到连续属性的情况，因此本 文的决策树运算采用的都是基于c 4 5 算法的运算，而e c 4 5 算法则因为占用内存较 大，不适应于解决大状态空间问题。 3 2 3 决策树的生成和剪枝 决策树算法的分类学习过程包括两个阶段：树构造( t r e eb u i l d i n g ) 和树剪枝 ( t r e ep r u n i n g ) 。 ( 1 ) 树构造阶段。决策树采用自顶向下的递归方式：从根节点开始在每个节点 上按照给定标准选择测试属性，然后按照相应属性的所有可能取值向下建立分枝、 划分训练样本，直到一个节点上的所有样本都被划分到同一个类，或者某一节点 中的样本数量低于给定值时为止。这一阶段最关键的操作是在树的节点上选择最 佳测试属性，该属性可以将训练样本进行最好的划分。选择测试属性的标准有信 息增益、信息增益比、基尼指数( g i n ii n d e x ) 以及基于距离的划分等。此外，测试 属性的取值可以是连续的( c o n t i n u o u s ) ，也可以是离散的( d i s c r e t e ) ，而样本的类属 性必须是离散的。 树的增长算法由以下步骤完成： g e n e r a t et e s t ：给定一个样本集合e ，由此产生一组测试集r 。测试集的产生 依赖于对样本集的描述方式以及样本数据的特征。 o p t i m a ls p l i t ：每一个测试f r ，可产生一个在样本集上的分割 s = q1 日= p eir ( p ) = ) ) ，其中_ 是测试r 可能产生的结果。由某判别标准选取 其中结果最好的测试。 s t o pi n f 0 ：检测分割s 是否满足条件来产生子树，如果不满足，则保存节点其 他信息；否则，转入i ，继续子树的生成。 决策树构建的具体算法如下所示： f u n c t i o nt r e e ( e ：样本集) 返回t r e e r ：= g r o w 二t r e e ( e ) 丁：= p r u n e ( r ) r e t u mr f u n c t i o ng r o wt r e e ( e ：样本集) 返回t r e e ： r ：= g e n e r a t e _ t e s t ( e ) r ：= o p t i m a l s p l i t ( r ，e ) s ：= 通过f 产生的e 上的分割 i f s t o p i n f o ( e ，占) t h e nr e t u ml e a f ( e ) e l s e f o r ( 所有e ，占) f ，：= g r o w t r e e ( e ，) r e t u m 节点( f ， ( j ，f ，) ) ) o p t i m a ls p l i t 过程： 给定测试集r ，o p t i m a i s p l i t 用于计算最优分割和测试。对于不同任务可以使 用不同的标准。在分类中通常使用如下几种标准： i 信息增益( q u i n l a n ，1 9 9 3 ) ： g 叫d 一乏谢鸱) ( 3 6 ) 其中信息熵：s ( d = p ( q ，e ) l o g p ( q ，e ) i i 信息增益比：础= g 届1 0 9 易 ( 3 7 ) 2 1 i i i g i n i 指标： q = g ( 助一搿g ( 互) ， ( 3 8 ) 局e 占l “l 其中 上 g ( 司= l - p ( c f ，e ) 2 ( 3 9 ) f = i 节点信息的保存： 节点信息主要用于对以后样本的预测。对于不同类型的树，将保存不同的信 息：分类树保存观测到的子叶分类模式的值。回归树将保存在子叶中所观测到的 目标变量的平均值。聚类树保存类的中心点。 ( 2 ) 树剪枝阶段。构造过程得到的并不是最简单、紧凑的决策树，因为许多分 枝反映的可能是训练数据中的噪声或孤立点。树剪枝过程试图检测和去掉这种分 枝，以提高对未知数据集进行分类时的准确性。树剪枝主要有先剪枝、后剪枝或 两者相结合的方法。树剪枝方法的剪枝标准有最小描述长度原则( m d l ) 和期望错 误率最小原则等。前者对决策树进行二进位编码，最佳剪枝树就是编码所需二进 位最少的树；后者计算某节点上的子树被剪枝后出现的期望错误率，由此判断是 否剪枝，在决策树剪枝阶段可以分为预剪枝过程和后剪枝过程。 一预剪枝过程： s t o pi n f 0 过程用于判断是否继续子树的生成。最为简单的判定条件是当某个 分割得到的类达到一定结合度，或者通过节点所分割的样本数达到一定阈值。另 外还有一些复杂的判定准则：最小描述长度( m d l ) 和期望错误率最小原则。最 小描述长度基于以下原因产生：解释一组数据的最好理论，应该使得下面两项之 和最小：描述理论所需要的比特长度；在理论的协助下，对数据编码所需要 的比特长度。具体做法为对决策树进行二进位编码，编码所需二进位最少的树即 为“最佳裁剪树” 期望错误率最小原则选择期望错误率最小的子树剪枝，对树中的内部节点计 算其剪枝不剪枝可能出现的期望错误率，比较后加以取舍。 后剪枝过程 由于难以找到一个较好的s t o pi n f 0 算法，许多树往往建造得过于庞大。减少 不必要的枝节将是非常重要的。尽管这一过程将耗费大量计算，但能得到一颗质 量更好的树。剪枝树基于如下准则：奥卡姆剃刀原则如无必要，勿增实体。 即”在与观察相容的理论中，我们应当选择最简单的一个”。决策树越小就越容 易被理解，其存储与传输的代价也就越小。决策树越复杂，节点就越多，每个 节点所包含的训练实例个数就越少，则支持每个节点的假设的实例个数就越少， 可能导致随后错误率较大。但也不是节点越小错误率就越低。所以必需在树的大 小与正确率之间进行平衡。 3 3 因素化强化学习理论 3 3 1 因素化的m d p 状态 m d p 状态因素化，顾名思义就是对m d p 状态内在属性的一种描述。对于m d p 模型中的某一个状态，我们都可以用一个状态向量唬= 噍( 1 ) ，噍( 2 ) ，九，( 聊) 表 示，可以认为状态t 有槐个属性。每一个状态因子都有一个值域，记为面朋以，( _ ，) ) 。 通常情况下，状态因子为布尔型变量。在本文中，它的取值为l ( t m e ) 或者0 ( f a l s e ) 。 通过将每一个状态进行因素化，我们发现可以将状态空间定义为若干状态因子组 成的集合。下面给出了状态因素化的定义： 定义3 3 ( 状态因素化) m d p 状态因素化是通过把原始系统的状态归并为较 小的集结状态集合，从而在更小的维数空间上进行强化学习【4 2 1 。明确地说，我们 把状态空间s 划分为n 个子集一，s ，l ，s 。， s = 墨u 岛u lu 巴 ( 3 1o ) 称之为状态因素化。当问题的特征可知时，我们可以根据特征进行状态集结， 使其有较好的一致性、精确性和适应性，当问题的特征知识难以获得时，如何进 行状态因素化是主要问题。 3 3 2 动态贝叶斯网络与m d p 模型 前面讲到了动态贝叶斯网络的一些基本理论，在这里我们将深入探讨动态贝 叶斯网络在大状态空间问题上的应用。使用动态贝叶斯网络精简m d p 状态空问是 由b o u t i l i e r 等提出来的，这种方法的优势在于能将状态空间精简幅度最大化，但 是也存在者效率不高的问题，下面我们将对其作一个简单的介绍。 系统状态的取值是由集合s 中的每一个状态因子最的取值共同决定的，而且两 者之间构成了一一对应的映射关系，如下所示： s = 阳，( 而) w ，( 屯) ，( s 。) ( 3 1 1 ) 通常贝叶斯网络的应用主要集中在非时间问题领域【4 3 1 ，在本文中我们将其用 来紧凑表示两个时刻之间的因素化概率分布以及随机动作对系统状态施加的影 响。动态贝叶斯是一种有向无循环图，在文中，它的每一个节点对应一个状态因 子，状态因子之间的概率依赖性体现了相邻两个时刻之间的状态转移概率。在实 际的应用当中，相邻时刻的节点与节点之间的状态转移概率是通过具体的数字量 化的，此外对于贝叶斯网络中没有父亲节点的顶点，我们通常赋予它边缘分布概 率。 如图3 2 ( a ) 所示，我们用d b n s 表示系统动作集中某个动作口的丁函数。由 于m d p 的历史无关性，我们只需要用两个时刻就可以表示整个学习过程，图中我 们选用了f 和f + l 两个时刻。前面讲过，这两个时刻状态可以划分为从最到s 的状 态因子集。为了过滤掉一些状态空间中的无用状态因子，我们必须对其中的变量 进行分类。状态因子集合中，按动作a 对状态因子的作用效果，我们可以将其分为 两部分，其中集合a = s ，最，最l 中的变量在执行动作口后，集合中变量的值发生了 改变，这些与动作口相关的变量是必须保留的；相反，集合曰= 只，鼠 ( 力4 ) 中的变量在执行动作口后值保持不变，与动作口是不相关的，则可以过滤掉。根 据以往的经验，在基于状态因素化的d b n s 中，我们发现状态集中的绝大多数的 变量( 如集合曰) 都是可以过滤掉的，只有少数与某个动作相关的变量( 如集合彳) 是必须保留的。 o ( a 浓j 奈转移溉率函数灼d b n 5 农示( b 燃函数的决镶树霰示 图3 2 状态因素化的d b n s 和决策树表示 上文中介绍了使用d b n s 过滤状态空间中无用状态因子的方法，在大多数情 况下，可以状态空间压缩到一个合理的大小。但是在状态空间极端复杂的情况下， 状态空间中的状态因子都是有用的，而且状态因子的数目较为庞大。在这种情况 下，仅仅使用d b n s 过滤无用状态就显得不够了，因此寻找新方法和新算法就成 了当务之急。 3 3 3 决策树与m d p 模型 在状态空间规模较小的时候，经典强化