（计算机应用技术专业论文）解决强化学习中维数灾问题的方法研究.pdf

，- - 苏州大学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在l 月解密后适用本规定。 非涉密论文口 论文作者签名： 导师签名： 期：建2 坦：么：! f 期：碰! 里：亟：! ! 摘要 针对强化学习任务中存在的“维数灾 ( 即状态空间的大小随着特征数量的增加 而发生指数级的增长) 及收敛速度慢两个普遍且严重的问题，本文分别从奖赏函数、 分层强化学习和函数估计等不同的角度来给出解决方法，提出了基于启发式奖赏函数 的分层强化学习算法和基于神经网络的强化学习算法。同时，在所提理论的基础上， 分别开发了俄罗斯方块、m o u n t a i nc a l 和g r i dw o r l d 等实验平台，将上述算法应用到 实验中，通过实验分析，进一步验证所提算法在解决“维数灾问题方面的正确性和 有效性。 本文的主要研究成果概括为以下五个方面： ( 1 ) 提出了一种基于启发式奖赏函数的分层强化学习算法，并从理论上证明了该 算法的收敛性。该算法通过在子任务中加入启发式奖赏信息，使a g e n t 的探索速度大 大提高。该算法不仅可以部分解决“维数灾 问题，而且可以加快任务的收敛速度。 ( 2 ) 开发了俄罗斯方块游戏的实验平台，并将基于启发式奖赏函数的分层强化学 习算法应用于该平台。实验结果验证了该算法不仅能够大幅度的减少环境状态空间， 能在一定程度上缓解“维数灾 问题，而且还具有很好的收敛速度。 ( 3 ) 针对“维数灾问题，提出了将神经网络应用于强化学习中的一种新算法 q l b p 算法。该算法利用神经网络强大的函数逼近能力，使学习系统不需要遍历每 个状态或状态动作对就可以给出正确的值函数，空间复杂度显著降低。 ( 4 ) 针对q l - b p 算法在实验初期因为样本误差较大而出现的震荡、收敛速度慢以 及在学习后期会出现过拟合现象等问题，提出了一种改进的q l b p 算法。实验表明 改进的q l b p 算法收敛速度更快，学习后期的过拟合现象也基本消除。 ( 5 ) 开发了m o u n t a i nc a l 和g r i dw o r l d 实验平台，在这两个实验平台上应用q l b p 算法以及改进的q l b p 算法。通过实验，验证了这两种算法在空间复杂度方面明显 优于q ( 九) 算法，一定程度上解决了“维数灾 问题。 关键词：强化学习，分层强化学习，神经网络，俄罗斯方块，“维数灾” 作者：闰其粹 指导教师：刘全( 教授) r e s e a r c h e so nt h ec u r s eo f d i m e n s i o n a l i t y i n r e i n f o r c e m e n t l e a r n i n g a b s t r a c t t os o l v et h e “c u r s eo fd i m e n s i o n a l i t y ”( t h a ti s ，t h es t a t e s s p a c ew i l lg r o w e x p o n e n t i a l l yi nt h en u m b e ro ff e a t u r e s ) a n dl o wc o n v e r g e n c es p e e do ft w oc o m m o na n d s e r i o u sp r o b l e mi nr e i n f o r c e m e n tl e a r n i n g ，i nt h i sp a p e r , w ew i l ls o l v et h e s et w o p r o b l e m s f r o mt h er e w a r df u n c t i o n ，h i e r a r c h i c a lr e i n f o r c e m e n tl e a m i n ga n df u n c t i o ne s t i m a t i o n d i f f e r e n ta n g l e s ，p r o p o s e dah e u r i s t i cr e w a r df u n c t i o nm e t h o db a s e do nh i e r a r c h i c a l r e i n f o r c e m e n tl e a r n i n ga n dar 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 mb a s e do nn e u r a ln e t w o r k m e a n w h i l e ，i nt h e s et h e o r e t i c a lf o u n d a t i o n s ，w ed e v e l o p e dt e t r i s ，m o u n t a i nc a ra n dg r i d w o r l da n do t h e re x p e r i m e n t a lp l a t f o r m t h r o u g he x p e r i m e n t sa n da n a l y s i so fe x p e r i m e n t a l d a t a , w ef u r t h e rv a l i d a t et h ec o r r e c t n e s sa n de f f e c t i v e n e s so ft h ea l g o r i t h m t h em a i nr e s e a r c hr e s u l t sa r ec o n c l u d e da sf o l l o w s ： ( 1 ) p r o p o s e dah e u r i s t i cr e w a r df u n c t i o nb a s e do nh i e r a r c h i c a lr e i n f o r c e m e n tl e a r n i n g a l g o r i t h ma n dg i v eat h e o r e t i c a lp r o o fo ft h ea l g o r i t h m sc o n v e r g e n c e h e u r i s t i cr e w a r d w i l lb ea p p l i e dt oh i e r a r c h i c a lr e i n f o r c e m e n tl e a r n i n gs u b t a s k s ，g r e a t l yi n c r e a s e dt h e l e a r n i n gs p e e d o ft h ea g e n t t h e a l g o r i t h m n o to n l yc a ns o l v et h e “c u r s eo f d i m e n s i o n a l i t y p r o b l e m ，b u ta l s oc a ns p e e du pt h ec o n v e r g e n c es p e e do ft h et a s k ( 2 ) w ed e v e l o p e dt h et e t r i sg a m ee x p e r i m e n tp l a t f o r m i nt h i sp l a t f o r m ，w ea p p l yt h e a l g o r i t h mo fh e u r i s t i cr e w a r df u n c t i o nb a s e do nh i e r a r c h i c a lr e i n f o r c e m e n tl e a r n i n g ，t h e e x p e r i m e n t a l r e s u l t ss h o wt h a t ：t h e a l g o r i t h m n o to n l y s i g n i f i c a n t l y r e d u c et h e e n v i r o n m e n t a ls t a t es p a c e ，s o l v et h e c u r s eo fd i m e n s i o n a l i t y p r o b l e mi nac e r t a i ne x t e n t , b u ta l s oh a sg o o dc o n v e r g e n c es p e e d ( 3 ) t os o l v et h e “c u r s o fd i m e n s i o n a l i t y p r o b l e m ，w ea l s op u tf o r w a r dan e w a l g o r i t h mc a l l e dq l b p , w h i c ha p p l i e dt h en e u r a ln e t w o r kt ot h er e i n f o r c e m e n tl e a r n i n g t h i sa l g o r i t h mu s e st h ep o w e r f u lf u n c t i o na p p r o x i m a t i o na b i l i t yo ft h en e u r a ln e t w o r k , s o i l t h a tl e a r n i n gs y s t e m sd on o tn e e dt ot r a v e r s ee a c hs t a t eo rs t a t e a c t i o np a i r sc a nb eg i v e ni n t h ec o r r e c ts t a t e - v a l u ef u n c t i o nv ( s ) o ra c t i o n v a l u ef u n c t i o nq ( s ，a ) ，r e d u c et h es p a c e c o m p l e x i t ys i g n i f i c a n t l y ( 4 ) f o rt h eq l b pa l g o r i t h mh a sd i s a d v a n t a g e sl i k el a r g e rs h o c k ，s l o wc o n v e r g e n c e i nt h ee a r l yt i m ea n dw i l la p p e a rt h ep h e n o m e n o no f o v e r - f i t t i n gp r o b l e m sl a t e ri nt h es t u d y ( b e c a u s eo ft h eb i ge r r o ro ft h ee x p e r i m e n t a ls a m p l e s ) ，w ep r e s e n t sa ni m p r o v e dq l - b p a l g o r i t h m 。e x p e r i m e n t sr e s u l t ss h o wt h a tt h ei m p r o v e dq l b pa l g o r i t h mn o to n l yh a s b e t t e rc o n v e r g e n c es p e e di nt h ee a r l yt i m e ，b u ta l s oe l i m i n a t et h ep h e n o m e n o no f o v e r - f i t t i n gs i g n i f i c a n t l yi nt h el a t e r ( 5 ) d e v e l o p e dt h em o u n t a i nc a ra n dg r i dw o r l de x p e r i m e n tp l a t f o r m w ea p p l i e d q l b pa l g o r i t h m ，t h ei m p r o v e dq l b pa l g o r i t h mt ot h i st w oe x p e r i m e n t a lp l a t f o r m s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h et w oa l g o r i t h m si sb e t t e rt h a nq ( ”a l g o r i t h mi nt e r m so f s p a c ec o m p l e x i t ya n dc a l ls o l v et h e “c u r s eo fd i m e n s i o n a l i t y “p r o b l e mi nac e r t a i ne x t e n t 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 ，h i e r a r c h i c a lr e i n f o r c e m e n tl e a r n i n g ，n e u r a l n e t w o r k s ，t e t r i s ，“c u r s eo fd i m e n s i o n a l i t y i i i w r i t t e nb y ：q i c u iy a n s u p e r v i s e db y ：q u a nl i u 目录 摘蓦要。i a b s t r a c t i i 第一章引言l 1 1 问题的提出1 1 2 国内外研究现状3 1 2 1 国内研究现状。3 1 2 2 国外研究现状。4 1 3 本文的主要工作5 1 4 本文组织6 第二章基础理论7 2 1 强化学习简介。7 2 2 强化学习发展历史8 2 3 强化学习原理1 0 2 4 强化学习的主要算法1 2 2 4 1m o n t ec a r l o 算法1 2 2 4 2t d 算法13 2 4 3q l e a r n i n g 算法。l5 2 5 强化学习发展趋势1 6 2 5 1 部分感知强化学习1 6 2 5 2 关系强化学习17 2 5 3 分层强化学习1 7 2 6 神经网络简介1 8 2 7 神经网络发展历史1 9 2 8 几种典型神经网络2 0 2 8 1b p 神经网络2 0 2 8 2h o p f i e l d 网络2 2 2 8 3c m a c 神经网络2 3 2 9 神经网络的发展趋势2 4 2 10 本章小结2 4 第三章基于启发式奖赏函数的分层强化学习2 5 3 1 引言2 5 3 2 分层强化学习发展状况2 5 3 3 基于启发式奖赏函数的分层强化学习算法2 6 3 3 1 启发式奖赏2 6 3 3 2 广义的m d p 2 7 3 3 3 子任务的定义及最优策略2 8 3 3 4 子任务的特征提取及附加奖赏函数2 9 3 3 5 最优策略3 0 3 3 6 基于启发式奖赏函数的分层强化学习算法3 2 3 4 实验及结果分析3 3 3 4 1 实验平台构成3 4 3 4 2 任务分层3 5 3 4 3 子任务特征提取及参数设置3 5 3 4 - 4 结果及分析3 6 3 5 结论3 8 3 6 本章小结3 9 第四章基于神经网络的强化学习4 0 4 1 引言4 0 4 2 泛化与函数估计4 0 4 2 1 泛化。4 0 4 2 2 函数估计41 4 3 神经网络在强化学习中的应用4 1 4 4 神经网络和强化学习结合的算法：q l b p 算法4 2 4 4 1q l b p 算法4 2 4 4 2 仿真实验4 5 4 5 改进的q l b p 算法一4 8 4 5 1q l b p 存在的问题及解决方法4 8 4 5 2 改进的q l b p 算法流程4 9 4 5 3 仿真实验。5 0 4 6 本章小结5 7 第五章总结与展望5 8 5 1 本文工作总结5 8 5 2 工作展望5 9 参考文献6 0 攻读硕士学位期间参加的科研项目及发表( 录用) 的论文6 5 一、发表( 录用) 的论文6 5 二、参加的科研项目一6 5 蜀c 谢6 6 解决强化学习中维数灾问题的方法研究第一章引言 1 1 问题的提出 第一章引言 研究者发现，生物进化过程中为适应环境而进行的学习有两个特点：一是生物从 来不是静止的被动的等待而是主动的对环境做试探；二是环境对试探动作产生的反馈 是评价性的，生物根据环境的评价来调整以后的动作，是一种从环境状态到行为映射 的学习。具有以上特点的学习应用到计算机领域就称为强化学习( 或称增强学习、再 励学习、评价学习，简记为r l ) 。强化学习是从控制理论、统计学、心理学等相关学 科发展而来，最早可以追溯到巴普洛夫的条件反射实验。但直到上世纪八十年代末、 九十年代初强化学习技术才在人工智能、机器学习和自动控制等领域中得到广泛重 视。因为强化学习具有强大的自学习和在线学习能力等很多优点，所以当前对强化学 习的研究和应用也日益深入，这使得强化学习在人工智能、机器学习领域占有越来越 重要的地位，并被认为是设计智能系统的核心技术之一，也是目前机器学习领域的研 究热点之一【h l 。 强化学习是一种交互式的学习方法，其主要的特点为“试错 和“延迟回报 。 整个过程是a g e n t 与环境之间不断交互的学习过程。a g e n t 做出一个动作，环境对此 动作进行反应并给出相应的评价即回报值，进而a g e n t 根据所得的回报值对相应的动 作进行改进和提高，通过一次次重复直至获得一个最大的回报值。此时，a g e n t 会获 得一个最优的动作序列。按照这个最优动作序列采取行动的策略就是整个学习任务的 最优策略。这个过程与心理学中的概念很类似，所以强化学习的学习理念来源于心理 学。正是这样的学习特点，使得强化学习成为与监督学习和非监督学习相平行的一个 概念。但该方法不同于监督学习或非监督学习之处在于：a g e n t 不是通过正反例被告 知采取何种动作，而是通过试错( t r i a l a n d e r r o r ) 的方法找到最优策略，即它解决 的是一个a g e n t 在缺少环境信息时的学习问题。因此强化学习具有强大的自学习和在 线学习能力。 标准的强化学习算法，虽然在形式上提供了统一的框架，但在实际应用中面临如 下的一些问题： 引言解决强化学习中维数灾问题的方法研究 ( 1 ) 探索利用( 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 是倾向于在未知的状态和动作空间中进行搜索获得新的信息，还是倾向于对 已学状态和动作进行寻优获得高的奖赏。一方面为了获得更多的奖赏，a g e n t 要在已 学状态和动作空间中利用贪心策略来获得最大奖赏值；另一方面为了将来能选择更好 的动作，a g e n t 需要扩大搜索范围尝试以前没有试过的动作。这样a g e n t 就处在了进 退两难的境地。探索利用问题几十年来一直是数学界研究的热点。目前最好的解决 方法是占一g r e e d y 算法或b o l t z m a n n g i b b s 分布方法。这两种方法都能够通过设定不同 的参数来很好的平衡探索和利用的冲突。 ( 2 ) “维数灾 问题：类似动态规划( d p ) 的“维数灾难问题，即在一些具有 大的、连续状态空间的任务中的学习时，状态空间的大小随着特征数量的增加而发生 指数级增长的问题。由于强化学习特有的学习和计算方式，当状态空间不断地增长时， 需要的计算量和存储空间也在不断地增大，以致在面对大规模问题时，传统的强化学 习方法也就无法满足需要了。目前解决“维数灾 问题的主要思想是抽象和逼近，这 些思想又可以细化为四种方法：状态聚类法、有限策略空间搜索法、值函数逼近法以 及分层强化学习方法( h i e r a r c h i c a lr e i n f o r c e m e n tl e a m i n g ，h r l ) 【5 】。值函数逼近法 是一种非常有效的方法，它使用基于值函数逼近器的强化学习算法取代表格型强化学 习算法。但值函数逼近器的设计和算法的收敛性问题目前还没有一个完全成熟的理 论，也是一个值得研究的领域。由于强化学习的思想和学习特点，在大规模状态空间 中存在“维数灾”现象是不可避免的。这是由强化学习的本质所决定的，无法从根本 上消除，只能从方法上加以克服。 ( 3 ) 收敛速度过慢问题：收敛速度和“维数灾”问题有密切的关系。因为，强化 学习系统的收敛是建立在“任意状态要被无限次的访问 这个理论基础之上的，当出 现“维数灾”问题时，很多状态仅被访问很少几次，甚至从来没有被访问到，这必然 会导致收敛速度减慢，甚至无法收敛。因此，在“维数灾 问题得到解决时，学习系 统的收敛速度也可以得到相应的提高。 ( 4 ) 不完全感知问题：在实际的学习任务中，a g e n t 往往无法直接通过观察环境 或其它手段来完全感知环境。从而，a g e n t 对于状态间的差异也无法区别，这将影响 到状态转移概率，从而导致错误的状态迁移。如果不对强化学习算法进行任何处理就 加以应用的话，学习算法将无法收敛【6 】。 2 一 塑 解决强化学习中维数灾问题的方法研究 第一章引言 ( 5 ) 融入a g e n t 的先验知识：一般的强化学习研究中，a g e n t 没有任何先验的启 发知识，这种无任何启发知识的强化学算法收敛非常慢。如何利用a g e n t 的知识来提 高强化学习的收敛速度是强化学习研究算法的热点之一。 针对强化学习中存在的两个主要问题即：“维数灾 问题和收敛速度过慢问题， 本文提出了基于启发式奖赏函数的分层强化学习和基于神经网络的强化学习方法，分 别从分层强化学习、强化学习要素( 奖赏函数) 和函数估计三个不同的角度来解决“维 数灾 和收敛过慢问题。实验方面，本文以e c l i p s e 为开发平台，开发了俄罗斯方块 游戏、g r i dw o r l d 和m o u n t a i nc a r 等实验平台，对提出的算法进行了实验验证。 1 2 国内外研究现状 1 2 1 国内研究现状 近年来，由于强化学习具有诸多优点，所以在国内得到了越来越广泛的重视，成 为在机器学习领域研究的热点。针对“维数灾问题以及强化学习中的其它问题，国 内许多学者从各个不同的层面、采用不同的技术和方法对这个问题进行了大量的研 究，取得了一些成果。 沈晶、顾国昌从分层强化学习入手，提出了很多解决“维数灾 问题的分层强化 学习方法。如提出的动态环境中的分层强化学习思想，用于解决环境不断变化情况下 的强化学习任务：此外，为加快分层强化学习中任务层次结构的自动生成速度，还提 出了一种基于多智能体系统的并行自动分层方法；同时为了解决分层强化学习中现有 的自动分层方法对环境和状态空间特性依赖过强的问题，提出了一种基于免疫聚类的 自动分层强化学习方法【7 0 1 。石川、史忠植等提出了一种基于路径匹配的在线分层强 化学习方法，它能正确发现子目标，并用子目标构建o p t i o n ，实现任务的分割i l 。王 本年等人使用k 聚类方法来自动发现o p t i o n 中的子目标，从而实现基于o p t i o n 的分 层强化学习的自动分层【l2 1 。陈宗海提出了一种基于k 均值聚类算法的强化学习方法， 该方法主要解决的是连续状态空间中自适应划分问题【1 3 】。高阳、黄炳强等对平均奖赏 强化学习方面有深刻的研究，并提出了许多相关的算法和思想【1 4 】。高阳、胡景凯等人 将基于c m a c 网络的强化学习应用到电梯群控调度中，使得乘客的平均等待时间大 解决强化学习中维数灾问题的方法研究 高了电梯运行效率15 1 。林芬，石川等人提出了一种基于偏向信息学习的双 算法，该算法将强化学习过程和偏向信息学习过程结合起来，能够有效利 用先验知识提高学习效率，加快学习的收敛速度【1 6 1 。 除了上述内容之外，许多学者还将其它多种机器学习方法与强化学习结合起来， 并以此克服强化学习的弱点。如陆鑫、王本年等将贝叶斯方法或者人工神经网络的思 想与强化学习方法结合以解决相应的问题 1 7 , 1 8 】。同时近期比较受关注的是关系强化学 习方法( r e l a t i o n a lr e i n f o r c e m e n tl e a m i n g ，r r l ) ，这也是一种解决“维数灾问题 的方法。国内的许多专家在这个方面也投入了大量精力进行研究，目前已经建立了一 定的理论基础【1 9 ，2 0 1 。 1 2 2 国外研究现状 强化学习研究在国外的发展比较早。从其被提出至今，经过众多专家的研究和探 索，已经提出了许多相当重要的理论和方法。对于处理其中的“维数灾”问题，也有 相当多的方法和思想被提出。其中，神经网络以其良好的非线性映射能力而在许多强 化学习系统中得到应用。如c r i t e s 和b a r t o 提出了神经网络与强化学习结合的算法， 并将算法应用到的电梯控制系统中，取得相对其它算法较优的效果1 2 。t e s a u r o 的 t d g a m m o n 算法【2 2 1 ，z h a n g 和d i e , e r i c h 的作业调度算法【矧，l i n 的q c o n 模型2 4 1 ， t o u z e t 的机器人学习模型2 5 】等都是在强化学习系统中应用了神经网络。j o u f f e l 等人 将模糊神经系统和分层强化学习方法结合而提出了两种新的方法【2 们。s u t t o n 等人提出 了多种使用函数估计来学习值函数的方法，如文献【2 7 】中给出的一种时间复杂度为 o ( n ) 的基于线性函数逼近的离策略t d 算法：g t d ( g r a d i e n tt e m p o r a ld i f f e r e n c e ) 算 法。文献 2 8 】中继续给出了对g t d 算法的改进算法g t d 2 算法以及另一种线性梯度 算法：t d c ( 1 i n e a rt dw i t hg r a d i e n tc o r r e c t i o n ) 算法。两种算法都使用了函数逼近的 方法，而且收敛速度都比g d t 算法快。 尽管国内外很多专家都在对强化学习思想，尤其是如何结合其它机器学习方法来 解决强化学习中遇到的“维数灾 、收敛速度等问题，进行了深入的探讨和研究，也 取得了一定的成绩，但是在这个方向上，还是有很多地方值得付出更多的努力去研究， 以取得更大的进步和做出更多的贡献。 4 解决强化学习中维数灾问题的方法研究第一章引言 1 3 本文的主要工作 本文主要是针对强化学习中存在的“维数灾”以及学习收敛速度过慢问题进行分 析研究，主要目的是使用不同的方法或算法在一定程度上解决这两个问题。本文将使 用启发式奖赏、函数逼近等方法，来解决这两个问题，并在不同的实验平台上通过实 验对所提算法的正确性和有效性进行验证。本文的主要研究成果归纳如下： ( 1 ) 分析研究了强化学习中的“维数灾 问题，并在此基础上提出了一种基于启 发式奖赏函数的分层强化学习算法。这种方法首先将大的学习任务分割成小的子任 务，再对每个子任务进行学习。因为学习初期a g e n t 对环境一无所知，所以加入启发 式奖赏函数可以大大提高a g e n t 在学习初始阶段的探索速度，而且在以后的学习过程 中也能利用启发式奖赏函数为学习系统选择最佳动作提供启发式信息。 ( 2 ) 开发了俄罗斯方块游戏实验平台，在此平台上应用基于启发式奖赏函数的分 层强化学习算法，通过对实验中的参数进行设置及对算法性能进行分析，实验结果表 明：采用启发式奖赏函数的分层强化学习算法，不仅能够大幅度的减少环境状态空间， 能在一定程度上解决“维数灾 问题，还具有很好的收敛速度。本文还从理论上证明 了该算法的收敛性。 ( 3 ) 针对强化学习的“维数灾 问题和算法收敛速度过慢问题，提出了一种将神 经网络应用到强化学习中的新算法q l b p 算法。该算法利用神经网络强大的函数逼 近和泛化能力，不需要遍历每个状态或状态动作对就可以给出正确的状态值函数v ( s ) 或行为值函数q ( s ，a ) ，空间复杂度大幅减小，而且具有很好的学习效果。本文还通 过实验将此算法和其它算法进行比较，分析算法的优缺点及算法的适用性。 ( 4 ) 针对q l b p 算法在实验初期因为样本误差较大而出现的震荡、收敛速度慢以 及在学习后期会出现过拟合现象，给出了一种改进的q l 。b p 算法。在实验初期，给 出了三种筛选较优样本的方法；实验后期，采用回滚的方法解决过拟合问题。 ( 5 ) 开发了g r i dw o r l d 和m o u n t a i nc a r ( 具有连续大规模的状态空间) 实验平台， 将w a t k i n sq ( 九) 算法、q l b p 算法和改进的q l b p 算法分别应用到这两个平台上， 通过实验，验证了各算法的有效性，并比较各算法的特点。实验表明：改进的q l b p 算法在解决“维数灾 问题时效果明显优于q l b p 算法。 解决强化学习中维数灾问题的方法研究 本文共五章，具体内容按如下方式组织： 第一章引言。主要介绍了强化学习在国内外的发展现状，以及强化学习中存在 的一些问题，同时给出了本文针对这些问题所做的工作。 第二章基础理论。主要回顾了强化学习和神经网络的发展历史，介绍强化学习 和神经网络的基本原理，给出常用强化学习的算法以及几种典型的神经网络结构，并 对强化学习和神经网络的发展方向予以总结。 第三章介绍了一种基于启发式奖赏函数的分层强化学习算法。启发式奖赏函数 主要解决收敛速度过慢问题，而分层强化学习则主要解决“维数灾问题。本文还在 理论上给出此算法收敛性的证明，并将算法应用到俄罗斯方块实验平台上，通过和一 般的分层强化学习方法和经典的q l e a m i n g 算法的实验效果进行比较，证明了该算 法确实能加快算法收敛速度和部分解决“维数灾 问题。 第四章给出了一种结合b p 神经网络和q ( ”算法的新算法_ q l b p 算法，并 通过实验说明该算法的有效性。同时，对于q l b p 算法中存在的问题，本章给出了 针对性的改进。将改进的算法应用到不同实验平台上，通过和其它算法的实验数据进 行比较，证明了改进的算法在学习的前期和后期都具有更好的性能。 第五章总结与展望。在对全文进行总结的基础上，提出下一步工作可能的研究 方向，并对未来工作进行展望。 6 解决强化学习中维数灾问题的方法研究第一二章基础理论 2 1 强化学习简介 第二章基础理论 智能系统的一个主要特征是能够适应未知环境，其中学习能力是智能系统的关键 技术之一。在机器学习范畴内，根据反馈的不同，学习技术可以分为监督学习 ( s u p e r v i s e dl e a r n i n g ) 、非监督学习( u n s u p e r v i s e dl e a r n i n g ) 和强化学习( r e i n f o r c e m e n t l e a r n i n g ) 三大类。其中强化学习是一种以环境反馈作为输入的、特殊的、适应环境 的机器学习方法。 所谓强化学习，就是指从环境状态到行为映射的学习，目的是使a g e n t 从环境中 获得的累积奖赏值最大。强化学习把学习看作一个试探评价的过程。a g e n t 选择一个 动作作用于环境，环境接受该动作后状态发生变化，同时产生一个强化信号( 奖励或 惩罚) 反馈给a g e n t ，a g e n t 根据强化信号和环境当前状态再选择下一个动作，选择 的原则是使受到正强化值( 奖励) 的概率增大。选择的动作不仅影响立即强化值，而 且影响环境下一时刻的状态及最终的强化值。这种学习方式的特点是：试错 ( t r i a l a n d e r r o r ) 和延迟回报。这也类似于人类的学习方式，同时也是强化学习区别 于监督学习技术( 通过正例、反例来告知采取何种动作) 的主要方面。试错和延迟回 报是强化学习的两个最突出的特点。但强化学习系统还具有以下更一般的特点【2 9 】： ( 1 ) 适应性，即a g e n t 不断利用环境中的反馈信息来改善其性能； ( 2 ) 反应性，即a g e n t 可以从经验中直接获取状态动作规则； ( 3 ) 对外部教师信号依赖较少。因为a g e n t 只根据强化信号进行学习，而强化信 号可从a g e n t 内置的强化机制中获得。 根据环境的性质不同，可以将强化学习问题分为以下几类： 第一类，环境对于给定的输入和输出映射是完全确定的，可以认为强化信号保持 不变。因此，a g e n t 要学习一个确定的输入输出映射。 第二类，环境是随机的，但却是平稳的。此时a g e n t 可按某种概率分布选择动作， 环境对动作的评价代表该动作成功( 奖励) 的概率。此概率只与动作本身有关而与环 境当前状态无关。a g e n t 根据强化信号修改动作的概率分布，以增加后面学习成功的 7 第二章基础理论解决强化学习中维数灾问题的方法研究 概率。 第三类，环境本身可能是由一个复杂的动力系统支配，因而是非平稳的。此时， 选择动作不仅要根据强化信号，还要用到环境的当前状态。a g e n t 相当于在环境状态 空间与动作空问之间实现某种联想映射，最佳映射是使强化信号的期望值达到最大。 这种情况通常称为联想强化学习。强化信号和输入模式都可能是由系统输出的历史决 定的。 目前，强化学习算法多是建立在前两类环境中的，研究趋于成熟，但仍有很多问 题待研究。而对建立在第三类环境上的强化学习系统及算法仍是目前的研究热点。 2 2 强化学习发展历史 强化学习是人工智能领域中既新兴又古老的课题，最早可以追溯到巴普洛夫的条 件反射实验，但直到上世纪八十年代末、九十年代初强化学习技术才在人工智能、机 器学习和自动控制等领域中得到广泛研究和应用，并被认为是设计智能系统的核心技 术之一。 强化学习的研究历史可粗略地划分为两个阶段：第一阶段是5 0 年代至6 0 年代，可 以称为强化学习的形成阶段；第二阶段是8 0 年代以后，可以称为强化学习的发展阶段。 在第一阶段，“强化”和“强化学习 这些术语f l j m i n s k y 首次提出并发表在工程文献 上。当时数学心理学家探索了各种计算模型以解释动物和人类的学习行为。他们认为 学习是随机进行的，并发展了所谓的随机学习模型。在控制理论中，由w a l t z 和傅京 孙于1 9 6 5 年分别独立提出这一概念。在应用方面，最早的应用例子是s a m u e l 的下棋程 序，该程序采用类似值迭代、瞬时差分和q - l e a r n i n g 算法的训练机制，来学习用线性 函数表示的值函数。w i d r o w 及其同事们在研究监督学习时，认识到强化学习和监督 学习之间的不同，并在1 9 7 3 年同g u p t a 和m a i t r a 改正了w i d r o w h o 褴督学习规则( 常 称为l m s 规则) 。新规则可实现强化学习，即根据成功和失败的信号进行学习，代替 原来的使用训练样本进行学习。他们用“有评价的学习 一词代替“有教师的学习 。 在六七十年代，强化学习研究进展比较缓慢。进入八十年代后，随着人们对人工 神经网络的研究不断地深入，以及计算机技术的进步，人们对强化学习的研究又出现 了高潮，逐渐成为机器学习研究中的活跃领域。b a r t o 和他的同事，在只用强化信号 8 解决强化学习中维数灾问题的方法研究 第二章基础理论 ( 而没有用到环境的状态信息) 反馈的条件下，提出了联想奖惩算法( a s s o c i a t e d r e w a r dp e n a l t y ，a r p ) 算法。b a r t o 于1 9 8 3 年介绍了强化学习在实际控制系统中的应 用情况，他利用两个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 c e l e m e n t ) ，构成了一个评价控制系统，经过反复学习，使倒立摆维持较长的时间。实 际上这一思想就是强化学习中的a h c ( a d a p t i v eh e u r i s t i cc r i t i c ) 算法的早期形式。 之后s u t t o n 于1 9 8 4 年，在他的博士论文中提出了a h c 算法，比较系统的介绍了a h c 思 想。文中采用两个神经元形式，对不同的算法进行了大量实验。另外，s u t t o n 于1 9 8 8 年在( ( m a c h i n el e a r n i n g ) ) 上发表了题为“l e a r n i n gt op r e d i c tb yt h em e t h o d so f t e m p o r a l d i f f e r e n c e s 著名论文【3 0 1 ，可以说