（计算机应用技术专业论文）分层强化学习方法研究.pdf

分层强化学习方法研究 摘要 强化学习通过试错与环境交互获得策略的改进，其自学习和在线学习的 特点使其成为机器学习研究的一个重要分支。但是，强化学习一直被维数灾 难所困扰。近年来，分层强化学习在克服维数灾难方面取得了显著进展，典 型的成果有o p t i o n 、h a m 和m a x q 等方法，其中o p t i o n 和m a x q 目前使 用较为广泛。o p t i o n 方法便于自动划分子任务( 尤其分区或分段子任务) ，且 子任务粒度易于控制，但利用先验知识划分子任务时，任务划分结果表达不 够明晰，且子任务内部策略难于确定：m a x q 方法在线学习能力强，但自动 分层能力较弱，且分层粒度不够精细，难于对一些规模依然很大的子任务做 出进一步的分解。 本文集成o p t i o n 和m a x q 探讨一种新的分层强化学习方法o m q ， 并深入研究集成过程中所涉及的理论与计算问题，以及该方法在实际应用中 需要进一步解决的问题。 论文完成了以下主要工作： ( 1 ) 提出了o m q 分层强化学习方法，给出了理论框架和学习算法，该 框架集成了o p t i o n 和m a x q 的优势，对学习任务既可以利用先验知识进行 预先分层，也可以在学习过程中自动分层，拓展了任务分层能力；根据随机 逼近理论采用数学归纳法证明了学习算法在与m a x q 相同的收敛条件下能 依概率1 收敛到递归最优解；实验表明o m q 学习算法的性能优于q 学习、 o p t i o n 和m a x q 的学习算法； ( 2 ) 提出了基于免疫聚类的o m q 任务自动分层算法，算法基于a i n e t 人工免疫网络模型及免疫克隆选择算法实现状态空间聚类，以生成的状态聚 类子空间为基础构造子任务，实验表明该算法克服了以往的任务自动分层算 法对状态空间可分割性的高度依赖问题；并借鉴免疫系统二次应答机制对算 法进一步改进，提出了动态自动分层o m q 算法( d o m q ) ，在对状态空间进 行初步探测之后即进行自动分层，并可以根据其后的探测结果对已生成子任 哈尔滨工程大学博士学位论文 务的状态空间进行动态调整，实验表明该算法克服了对状态空间探测程度的 高度依赖问题； ( 3 ) 提出了未知动态环境中的o m q 分层强化学习方法( u d o m q ) ， 利用分层学习特性，仅关注任务各子目标状态及当前子任务内部状态的变化， 将策略更新过程限制在规模较小的局部空间或维数较低的高层空间上，使得 学习算法在未知动态环境中能够几乎处处收敛；将该方法用于移动机器人路 径规划任务中，实验表明该方法克服了现有的动态环境中路径规划方法对全 局环境的静态信息或动态障碍物的运动信息的高度依赖问题； ( 4 ) 提出了多智能体o m q 分层强化学习方法( m o m q ) ，将o m q 任 务图中的顶层子任务作为协作层，每个a g e n t 在该层更新值函数时考虑联合 状态和联合动作，从而实现多智能体的合作，该方法拓展了o m q 方法的适 用范围，同时也探讨了一种具有较好收敛性能的多智能体强化学习方法，实 验表明了算法的可行性和有效性。 o m q 方法既具备m a x q 利用先验知识进行任务分层和良好的在线学习 能力，又具备o p t i o n 自动划分子任务尤其是分区( 分段) 子任务的能力，并 能以较快速度收敛到递归最优解，且很容易拓展到未知、动态、大规模、多 智能体等复杂应用环境中，这对推动强化学习理论的进一步发展无疑是有重 要意义的，同时该方法在智能机器人、多智能体系统等领域也有重要的应用 价值。 关键词：分层强化学习；免疫聚类：自动分层；多智能体分层强化学习 分层强化学习方法研究 a b s t r a c t r e i n f o r c e m e n tl e a r n i n gi sa l la p p r o a c ht h a ta l la g e n tc a r ll e a r ni t sb e h i v o r s t h r o u g ht r i a l a n d e r r o ri n t e r a c t i o nw i t had y n a m i ce n v i m n m e n t i th a sb e e na n i m p o r t a n tb r a n c ho fm a c h i n el e a r n i n gf o ri t ss e l f - l e a r n i n ga n do n l i n el e a r n i n g c a p a b i l i t i e s b u t r e i n f o r c e m e n t l e a r n i n g i sb e d e v i l e d b y t h ec u r s eo f d i m e n s i o n a l i t y r e c e n t l y , 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 h a sm a d eg r e a t p r o g r e s s e st oc o m b a tt h e c u r s eo fd i m e n s i o n a l i t y t h e r ea r es e v e r a lv a l u a b l e w o r k ss u c ha so p t i o n ，h a m ，a n dm a x q w h e r e ，o p t i o na n dm a x qa r eu s e d m o r ep o p u l a r l y i no p t i o nf r a m e w o r k ，i ti se a s yt oa u t o m a t i c a l l yg e n e r a t es u b t a s k s ， e s p b yp a r t i t i o n i n gr e g i o n so rs t a g e s ，a n dt h eg r a n u l a r i t yo fs u b t a s ki se a s yt ob e c o n t r o l l e d b u ti ti sd i f f i c u l tt oc l e a r l yd e s c r i b et h es t r u c t u r eo fs u b t a s k sa n dt o l e a r nt h el o c a ls t r a t e g i e sw h e nt h e s es u b t a s k sa r ec o n s t r u c t e dm a n u a l l ya c c o r d i n g t op r e v i o u sk n o w l e d g e t h em a x qa p p r o a c hh a se n o u g ha b i l i t yf o ro n l i n e l e a r n i n gb u tw e a ka b i l i t yf o ra u t o m a t i c a l l yd i s c o v e r i n gh i e r a r c h i e s a n db e s i d e s ， t h eg r a n u l a r i t yo fs u b t a s ki sn o tf i n ee n o u g h ，a n ds o m el a r g e s c a l es u b t a s k sc a l l h a r d l yb ed e c o m p o s e df m e n i i lt h i sd i s s e r t a t i o n ，an o v e la p p r o a c ho fh 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 a m e do m q ，b yi n t e g r a t i n go p t i o n si n t om a x qi sp r o p o s e d t h et h e o r e t i c a la n d c o m p u t a t i o n a li s s u e si no m q a r ea d d r e s s e da sw e l la st h er i s i n gp r o b l e m si n p r a c t i c e t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r e ： 1 ) t h eo m qa p p r o a c hf o rh 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 gi sp r e s e n t e d a n di t st h e o r e t i c a lf r a m e w o r ka n dl e a r n i n ga l g o r i t h ma r ed i s c u s s e d t h eo m q f r a m e w o r kt a k e so nt h ea d v a n t a g e so fo p t i o na n dm a x q ，i e ，t h eh i e r a r c h i e sn o t o n l yc a l lb ec o n s t r u c t e dm a n u a l l ya c c o r d i n gt ot h ep r e v i o u sk n o w l e d g eb u ta l s o c a nb eg e n e r a t i n ga u t o m a t i c a l l yd u r i n gl e a m i g e m p l o y i n gt h er e s u l tf r o m s t o c h a s t i ca p p r o x i m a t i o nt h e o r y , a l li n d u c t i v ep r o o fi sg i v e nt h a tt h eo m q l e a r n i n ga l g o r i t h mc o n v e r g e sw i t hp r o b a b i l i t y1 t ot h eu n i q u er e c u r s i v e l yo p t i m a l p o l i c yi nt h es a m ec o n v e r g e n c ec o n d i t i o na sm a x q t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h eo m ql e a r n i n ga l g o r i t h mh a sb e t t e rp e r f o r m a n c et h a nt h a to f 哈尔滨工程大学博士学位论文 q l e a r n i n g ，o p i l o n s ，a n dm a x q 2 ) a na l g o r i t h mf o ra u t o m a t i co m qh i e r a r c h yb a s eo ni m m u n ec l u s t e r i n gi s p r e s e n t e d t h es t a t es p a c ec l u s e t e r sa c c o r d i n gt oa i n e t ，a l la r t i f i c i a li m m u n e n e t w o r km o d e l ，a n da ni m m u n ec l o n a ls e l e c t i o na l g o r i t h m t h e nt h es u b t a s k sa r e c o n s t r u c t e db a s e do nt h ec l u s t e r i n g s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e a l g o r i t h ms o l v e st h ep r o b l e mt h a tt h el e a r n i n gp e r f o r m a n c es t r o n g l yd e p e n d so n t h ed i v i s i b i l i t yo fs t a t es p a c e t h ea l g o r i t h mi si m p r o v e db yu s i n gt h es e c o n d r e s p o n s em e c h a n i s mi ni m m u n es y s t e m sf o rr e f e r e n c e a sar e s u l t ，a no m q a l g o r i t h m w i t h d y n a m i ca u t o m a t i ch i e r a r c h y i s p r e s e n t e d n e a u t o m a t i c h i e r a r c h yi sc o n s t r u c t e de a r l i e rw i t h o u te x p l o r i n gt h ew h o l es t a t es p a c ea n dt h e s t a t es p a c e so ft h es u b t a s k sa r em o d i f i e da c c o r d i n gt ot h en e we x p l o r a t i o n t h e e x p e d m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h ms o l v e st h ep r o b l e mt h a tt h el e a r n i n g p e r f o r m a n c es 仃o n g l yd e p e n d so nt h es t a t es p a c ee x p l o r a t i o n 3 ) a no m q b a s e dh 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 ga p p r o a c h ( u d o m q ) a d a p t i n gt ou n k o w nd y n a m i ce n v i r o n m e n t si sp r e s e n t e d u s i n gt h eh i e r a r c h i c a l c h a r a c t e r i s t i co fl e a r n i n g ，t h ea p p r o a c ho n l yt a k e si n t oa c c o u n tt h ec h a n g e st a k i n g p l a c ei nt h es u b g o a ls t a t e so fh i e r a r c h i c a lt a s k so rt h el o c a ls t a t e so fc u r r e n t s u b t a s k s ot h ep r o c e s so fs t r a t e g yu p d a t ei sl i m i t e di nas m a l l s c a l el o c a ls p a c eo r al e s sd i m e n s i o n a lh i g h - l e v e ls p a c e c o n s e q u e n t i a l l y , t h ea l g o r i t h mn e a r l y c o n v e r g e si nu n k o w nd y n a m i ce n v i r o n m e n t s t h ea p p r o a c hi su s e di nm o b i l e r o b o t sf o rp a t hp l a r m i n ga n dt h ep r o b l e mt h a tt h ep r e v i o u sa l g o r i t h m ss t r o n g l y d e p e n do ne i t h e rt h es m i l ei n f o r m a t i o no f t h eg l o b a le n v i r o n m e n to rt h em o v i n g i n f o r m a t i o no ft h ed y n a m i co b s t a c l e si ss o l v e d 4 、a no m q b a s e dm u l t i - a g e n th 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 ga p p r o a c h ( m o m q ) i sp r e s e n t e d t h ea g e n t sl e a r nc o o p e m i l o nb yc o n s i d e r i n gt h ej o i n ts t a t e a n dt h ej o i na c t i o ni nt h et o pl e v e lo ft h eo m qt a s kg r a p h t h ea p p l i c a b i l i t yo f o m q i se n l a r g e da sw e l la sam u l t i - a g e n tr e i n f o r c e m e n tl e a r n i n ga p p r o a c hw i t h b e r e tc o n v e r g e n c ep e r f o r m a n c ei sp r o p o s e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t t h ea l g o r i t h mi sf e a s i b l ea n de f f i c i e n t t h eo m qa p p r o a c hn o to n l yh a st h es a m ea b i l i t yo fc o n s t r u c t i n gt a s k h i e r a r c h i e sa c c o r d i n gt o 埘嘶酾k n o w l e d g ea n dl e a r n i n go n l i n ea st h a to f m a x qa p p r o a c h , b u ta l s oh a st h es a m ea b i l i t yo fa u t o m a t i ch i e r a r c h y , e s p d i v i s i o n a ls u b t a s k , a st h a to fo p t i o na p p r o a c h b e s i d e sa n d n l eo m qa l g o r i t h m 分层鼹化学习方法研究 c a l lq u i c k l yc o n v e r g et ot h er e c t ”s i v e l yo p t i m a lp o l i c y t h eo m q a p p r o a c hi s e a s y t ob ee x t e n d e dt om o r e c o m p l e x ，u n k n o w n ，d y n a m i c ，l a r g e s c a l e e n v i r o n m e n ta n dm u l t i a g e n tc a s e t h e s em a yb es i g n i f i c a n tf o rf a c i l i t a t i n g r e i n f o r c e m e n tl e a r n i n gt h e o r i e s 。a n dt h eo m qa p p r o a c hm a yb eu s e f u li n i n t e l l i g e n tr o b o t i cs y s t e m sa n dm u l t i a g e n ts y s t e m s k e y w o r d s ：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 ；i m m u n ec l u s t e r i n g ；a u t o m a t i c h i e r a r c h y ；m u l t i a g e n tn e 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 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 泡 日期：06 年6 月6 日 第1 章绪论 1 1 研究动机 第1 章绪论 强化学习( i 也：r e i n f o r c e m e n tl e a r n i n g ) 通过试错与环境交互获得策略 的改进，其自学习和在线学习的特点使其成为机器学习研究的一个重要分支 1 1 】【2 】。但强化学习方法一直被维数灾难( c u r s eo f d i m e n s i o n a l i t y ) 所困扰，即 学习参数个数随状态、动作维数成指数级增长 3 1 。 目前，克服维数灾难的方法主要有4 种：状态聚类法【4 】、有限策略空间 搜索法【5 1 ，值函数近似法6 】和分层强化学习( h r l ：h i e r a r c h i c a lr e i n f o r c e m e n t l e a r n i n g ) 方法【3 】。 状态聚类法通过把多个相近状态聚为单一状态有效地缩减了状态空间， 但缩减后的状态空间不具备m a r k o v 性质，导致强化学习系统的摆动期很长 或者不收敛。 有限策略空间搜索法根据可观测到的局部状态直接在有限的策略空间中 寻优，但该方法经常陷入局部最优，求解质量得不到保证。 值函数近似法使用一组特征基函数的线性组合来近似表示值函数，但是 所需的特征只有在具备问题先验知识的前提下才可获取。 h r l 方法引入抽象( a b s t r a c t i o n ) 机制实现状态空间降维，将强化学习 任务分解到抽象内部和抽象间的不同层次上分别实现，从而每层上的学习任 务仅需在低维空间中进行。近年来，h r l 在解决维数灾问题中取得了显著进 展，典型的成果有s u t t o n 提出的o p t i o n 7 、p a r r 提出的h a m 8 1 和d i e t t e r i c h 提出的m a x q r 9 j 。 这几种h r l 方法均以半马氏决策过程( s m d p ：s e m i - m a r k o vd e c i s i o n p r o c e s s ) 【1 川为理论基础，即允许动作在多步时间内完成，于是决策点的时间 间隔不再仅仅是单个时间步，而是一个变量( 时间步的整数倍) 。o p t i o n 方法 哈尔滨工程大学博士学位论文 只在予目标点进行决策，其它时刻按照o p t i o n 内部事先确定好的策略执行， h a m 只对有限状态机中的非确定点进行动作决策，m a x q 方法将任务按照 一定的层次进行组织并只在调用子任务时才进行决策。 o p t i o n 和m a x q 两种方法目前使用较为广泛。二者各具特色。o p t i o n 方法便于自动划分子任务( 尤其分区或分段予任务) ，且子任务粒度易于控制， 但利用先验知识划分子任务时，任务划分结果表达不够明晰，且予任务内部 策略难于确定。m a x q 方法在线学习能力强，但自动分层能力较弱，且分层 粒度不够精细，如在出租车问题【9 】中，m a x q 难于进一步对导航子任务进行 抽象。 o p t i o n 和m a x q 的优缺点表现出一定程度上的互补性，将这两种h r l 方法有机结合起来，有望克服各自的不足。鉴于此，本文集成o p t i o n 和m a x q 探讨一种新的分层强化学习方法o m q ( o p t i o n - m a x q ) ，并深入研究集成 过程中所涉及的理论与计算问题，以及该方法在实际应用中需要进一步解决 的问题。 o m q 方法既具备m a x q 利用先验知识进行任务分层和良好的在线学习 能力，又具备o p t i o n 自动划分子任务尤其是分区( 分段) 子任务的能力，并 能以较快速度收敛到递归最优解，且很容易拓展到未知、动态、大规模、多 智能体等复杂应用环境中，这对推动强化学习理论的进一步发展无疑是有重 要意义的，同时该方法在智能机器人、多智能体系统等领域也有重要的应用 价值。 1 2 研究内容 本文在系统地归纳分析分层强化学习研究现状的基础上，对以下问题进 行了深入的研究： ( 1 ) 研究o m q 方法的理论框架、学习算法、算法收敛性证明及算法性 能实验分析，旨在建立一种集成o 州o n 和m a x q 各自优点并克服各自不足 的h r l 框架，以及与m a x q 同样收敛条件下能依概率1 快速地收敛到递归 最优解的学习算法； 2 第1 章绪论 ( 2 ) 研究o m q 框架下的o p t i o n 自动生成算法，旨在克服以往的自动 分层算法对状态空间可分割性的高度依赖问题；考虑进一步改进算法，以克 服算法对状态空间探测程度的高度依赖问题； ( 3 ) 将o m q 方法推广到未知动态环境中( 实际应用中所面临的往往都 是此类环境) ，研究如何利用o m q 方法的分层特性，保证算法在动态环境中 能够几乎处处收敛； ( 4 ) 将o m q 方法进一步推广到多智能体学习领域，研究如何在o m q 框架下解决多智能体协作协调问题。 1 3 论文结构 全文共6 章，按以下思路组织： 第1 章，绪论：交待作者的研究动机和主要贡献，这是本文的出发点和 落脚点，同时介绍论文的组织结构，便于读者把握各章之间的内容分布及其 相互关系： 第2 章，分层强化学习综述：首先根据阐述本文工作的需要，介绍必要 的强化学习及分层强化学习的基本原理，然后针对本文的研究内容，归纳分 析相关的分层强化学习、任务自动分层及多智能体分层强化学习的研究现状 及存在的问题，这是论文工作的基点； 第3 章与第4 章是本文的核心，这两章完成了对o m q 分层强化学习方 法基本思想的完整表述： 第3 章，o m q 分层强化学习理论框架与学习算法：重点阐述集成o p t i o n 与m a x q 构造o m q 的创新思想，给出o m q 方法的理论框架和学习算法， 并通过理论证明与实验对比论证o m q 算法的收敛性与有效性； 第4 章，基于免疫聚类的o m q 任务自动分层算法：这是对o m q 方法 中任务自动分层这一技术细节的深入研究，主要阐述基于免疫聚类的任务自 动分层算法以及基于免疫二次应答机制的改进算法( d o m q ) ，并通过对比实 验论证了所提算法对状态空间可分割性和状态空间探测程度的依赖性均低于 哈尔滨工程大学博士学位论文 以往的同类算法； 第5 章与第6 章是对o m q 方法做出的迸一步拓展，这两章逐步将o m q 方法从理论基础研究推向应用基础研究： 第5 章，未知动态环境中的o m q 分层强化学习方法：将o m q 方法拓 展到真实世界中广泛存在的未知动态环境中，以移动机器人路径规划为具体 应用背景，阐述未知动态环境中的o m q 分层强化学习方法( u d o m q ) ，并 通过仿真实验验证学习算法在未知动态环境中能够几乎处处收敛； 第6 章，多智能体o m q 分层强化学习方法：将o m q 方法进一步拓展 到多智能体学习领域( m o m q ) ，通过在o m q 任务图中增加协作层来实现多 智能体的合作，并通过实验对比论证了算法的有效性和优越性。 论文的关键内容及其逻辑关系可以用图1 1 来表示。 图1 1 论文关键内容及其结构关系 f i g 1 1t h es t r u c t u r e & m a i nt o p i c s 4 第1 章绪论 最后，在结论部分对论文工作的主要创新点进行了总结，并提出了进一 步研究设想，从而为论文研究工作的延续性开展提供了一个基本思路。 堕堑堡三矍奎兰堕圭堂篁堡苎 2 1引言 第2 章分层强化学习综述 分层强化学习( h r l ) 是为解决强化学习的维数灾问题而提出的，近十 年来取得了显著进展，s u t t o n 、p a r r 和d i e r e r i c h 等从不同的角度探讨了克服 维数灾难的h r l 方法，分别提出了o p t i o n 7 1 、h a m 8 1 和m a x q l 9 等3 种典型 的方法。为了便于在后续章节中阐述论文的研究工作与创新成果，本章首先 介绍h r l 方法的基本原理，然后对h r l 方法的研究现状进行归纳、分析和 评价，最后对h r l 任务自动分层及多智能体分层强化学习这两个热点问题的 研究现状进行综述。 2 2 分层强化学习基本原理 分层强化学习的实质是通过在强化学习的基础上增加“抽象”机制，把整 体任务分解为不同层次上的子任务，使每个子任务在规模较小的子问题空间 中求解，并且求得的子任务策略可以复用，从而加快问题的求解速度。实现 h r l 的抽象技术主要包括状态空间分解( s t a t es p a c ed e c o m p o s i t i o n ) j 、时 态抽象( t e m p o r a la b s t r a c t i o n ) 埘、状态抽象( s t a t ea b s t r a c t i o n ) 【1 3 l 等三种 方法。无论采用何种抽象技术实现的分层强化学习，都可以使用s m d p 0 0 进 行模型化。下面分别介绍强化学习、s m d p 、分层与抽象。 2 2 1 强化学习 强化学习由m i n s k y 在2 0 世纪5 0 年代首次提出【1 4 l ，它是a g e n t 从环境 状态到动作映射的学习，以使动作从环境中获得的积累奖赏值最大。该方法 不同于监督学习技术那样通过正例、反例来告知采取何种行为，而是通过试 第2 章分层强化学习综述 错来发现最优行为策略【2 j 。 标准的强化学习框架结构如图2 1 所示【1 】。a g e n t 由状态感知器i 、学习 器l 和动作选择器p 三个模块组成。状态感知器i 把环境状态5 映射成a g e n t 内部感知f ：动作选择器p 根据当前策略选择动作a 作用于环境w ；学习器l 根据环境状态的奖赏值，以及内部感知f ，更新a g e n t 的策略知识。w 在动作 口的作用下将导致环境状态的变迁s 。强化学习技术的基本原理是：如果a g e n t 的某个动作导致环境正的奖赏( 强化信号) ，那么a g e n t 以后产生这个动作的 趋势便会加强；反之a g e n t 产生这个动作的趋势减弱。 图2 1 强化学习框架 f i g 2 1r e i n f o r c e m e n tl e a r n i n gf r a m e w o r k 强化学习的目标是要获得一个最优行为策略才：s 哼4 ，使a g e n t 选择的 动作能够得到环境的最大奖赏，其中，s 为状态集，4 为动作集。在多数问 题中，往往需要考虑a g e n t 行为的长期影响，因此需要定义一个目标函数来 表明从长期的观点确定什么是最优动作。在值迭代方法中，通常以状态的值 函数或状态动作对的值函数表达此目标函数，状态值函数模型可以分为无限 折扣模型、有限折扣模型和平均奖赏模型3 种形式。其中，无限折扣模型最 为常用，形式如公式( 2 - 1 ) 。 矿8 ( s ，) = ，0 ，1 ( 2 一1 ) t = 0 其中，y 为折扣因子，n 是a g e n t 从环境状态函转移到s t + j 后所接受的奖赏值 值 石+ = a r g 。m a x v ( s ) ， v s s ( 2 2 ) 由于环境的状态转移具有随机性，因此，在策略石的作用下，状态s t 的 矿2 + y p ( 艮tm r ) 矿u - ( 2 - 3 ) 日+ _ e j 其中，p 0 州口d 为环境的状态转移概率。 动态规划理论保证至少有一个策略，满足b e l l m a n 最优方程 1 5 】 旷”嘴卜y 譬咖。) ) ， 学习的任务即是求解石。 通常假定环境是马尔可夫型的，强化学习过程可以使用一个马氏决策过 程( m d p ：m a r k o vd e c i s i o np r o c e s s ) 表示，m d p 由四元组 定 义【1 6 】，其中，s 为状态集，4 为动作集，r ：s 划一鲰为奖赏函数，p ：s 4 一p d ( s ) 为状态转移函数。 马氏决策过程的本质是：当前状态向下一状态转移的概率和奖赏值只取 决于当前状态和选择的动作，而与历史状态和历史动作无关。因此在已知状 态转移概率函数p 和奖赏函数r 的环境模型知识下，可以采用动态规划技术 求解最优策略。而强化学习着重研究在尸函数和r 函数未知的情况下，系统 如何学习最优行为策略。 强化学习算法可分为两类【1 6 1 ，一类强化学习算法先进行模型的学习，再 根据模型知识推导优化策略，这类算法被称为基于模型法( m o d e l b a s e d ) ； 另一类强化学习算法直接计算优化策略，这类算法被称为模型无关法 ( m o d e l f r e e ) 。 常用的强化学习方法有：t d 法( t e m p o r a ld i f f e r e n c em e t h o d ) f i 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 a l g o r i t h m ) b s ，q 学习法( q l e a r n i n g ) 【1 9 1 。其 8 第2 章分层强化学习综述 中，q 学习是由w a t k i n s 提出的一种环境模型无关学习方法，由于其不用建 立环境模型并且在一定的条件下保证收敛的特点，使其成为强化学习方法中 应用最为广泛的一种方法。 在q 一学习方法中使用q 函数表示在状态& 时执行动作口f ，且此后按最优 动作序列执行时的无限折扣累计奖赏值： q ( s ，日。) = + y m a x 9 “+ ，a t + 。) l 口。+ 。a )( 2 5 ) 在q 学习中，a g e n t 经历一系列时间步，在每个时间步中，其学习步骤 如下： 观察现在的状态s t ； 选择并执行一个动作a ，； 观察下一个状态s t + l ： 收到一个立即强化信号n ； 按式( 2 - 6 ) 调整q 值： f ( 1 一q ) q f 。( 暑，q ) + q k + ( s f + 1 ) 】，s = s t , a = q q f ( 墨，q ) 2 q l ( ，q ) ， o t h e r w i s e ( 2 6 ) l 式中，啦为学习率，控制学习速度，r 为对v ( s 川) 的折扣系数， v ( s t “) = m a x q _ ( 5 ，“，口) f 2 7 1 q 学习的收敛条件剧1 9 】： 环境具有m a r k o v 性质； q 函数用l o o k u p 表来表示； 每个状态动作对都可以被无限次重复试验； 正确选择学习率。 9 哈尔滨工程大学博士学位论文 2 2 2 半马氏决策过程 m d p 只关注决策的顺序性而忽略决策的时间间隔。基于m d p 的强化学 习都假设动作在单个时间步完成，因而无法处理需要在多个时间步完成的动 作，研究人员为解决此问题，引入s m d p t l 0 】模型。如图2 2 所示，在s m d p 模型中，每个行为动作的时间间隔作为变量( 整数或实数) ，并进一步可以细 分为连续时间- 离散事件s m d p 2 0 】和离散时间s m d p t l 0 1 两种模型。在后者，行 为决策只在单位时间片的正整数倍做出，较前者模型简单。但基于离散时间 s m d p 的强化学习方法不难推广到连续时间的情况，因此以下的讨论都基于 离散时间s m d p 。 s m d 时间 - - - - - - - 厂八厂。 图2 2 m d p 与s m d p f i g 2 2m d p & s m d p 状 态 设f 是系统在状态5 执行动作口后的随机等待时间，p o ：叫j ，口) 是f 时间步 后执行动作口从状态j 转移到状态s 的状态转移函数， r ( s ，a ) = e r t + y r t + 一+ 一m 为对应的奖赏值。 式( 2 _ 8 ) 、( 2 9 ) 和( 2 1 0 ) 分别是基于s m d p 的值函数b e l l m a n 最优方程、 状态一动作对值函数b e l l m a n 最优方程以及q 学习迭代公式，其中k 为迭代次 数。 l o 第2 章分层强化学习综述 矿+ 0 ) ： q g ，a ) 嘴k i - 小y 雌。川删鹏) 陋s ， j 7 j 胄g ，口) + 萎y 7 p r 旧口) m a x 襞) ( 2 - 9 ) 绞+ 。o ，口) = ( 1 i 口) 9 0 ，a )， + 口k + h + l + y 2 l + 2 + + y “i + 1 + y ri i 野q ( j - ，d ) i ( 2 1 0 ) p a r r 证明了s m d p o 学习在标准q 学习算法的收敛条件下收敛嘲。 b r a d t k e 和d u f f 给出了连续时间s m d p 的o 学习算法口“。 d a s 等开发了平均奖赏算法【捌，此不赘述。 2 2 3 分层与抽象 s i m o n 2 3 1 指出，根据经验，自然界中的大部分复杂系统都表现出分层结 构。从理论角度讲，层次结构为从简单进化为复杂提供了可能性；从动力学 角度讲，分层系统具有可分解性，这一特性可以使其行为过程和描述方式更 加简化。因此，复杂系统的强化学习问题可以通过分层的方法得以简化。 分层是通过抽象实现的，h r l 中常用的抽象技术包括状态空间分斛“1 、 时态抽剩1 2 1 和状态抽象【1 3 1 等，这几种方法从不同的途径产生层次结构，实现 降低状态空间和动作空间的维数或规模，从而加快学习速度，可谓殊途同归。 在一种h r l 方法中可以只采用一种或同时采用几种抽象技术。 状态空间分解法是将状态空间分解为不同的子集，采取分而治之的策略 进行求解，从而每次求解都是在较小规模的子空间中进行；时态抽象法是把 动作序列或动作集分组，即将强化学习中仅考虑的单步动作拓展到多步情形， 从而减少决策次数，降低学习压力；而状态抽象法则是忽略与予任务无关的 若干维变量，从而实现状态变量降维。 时态抽象法是目前最为常用的一种分层技术，已被广泛的应用在经典人 工智能、控制和强化学习等领域中，目前所有的h r l 方法( 包括本文提出的 哈尔滨工程大学博士学位论文 o m q 方法) 中都用到了时态抽象技术，下面稍作展开介绍。 在经典人工智能领域中常使用时态抽象技术对规划问题进行求解，其核 心思想是引入时态抽象动作一宏( m a c r oo p e r a t o r s ) t 2 4 的概念，宏为一个开 环动作序列，其中的动作仍然可以是宏，因此，宏的引入自然形成了任务的 分层规划，降低了复杂度。宏的形式有多种，如过程网( p r o c e d u r a l n e t s ) 2 5 1 、 层次任务网( h i e r a r c h i c a lt a s k n e t w o r k s ) 【2 6 】等，抛开具体形式上的不同，它 们都有一个共性的问题就是要解决宏内部如何选择动作策略的问题以及建立 环境状态转移模型的问题。此外，还有一个关键问题是如何发现有意义的宏， 这些宏可以被重用到不同