基于可中断option的在线分层强化学习方法-朱斐.pdf

《基于可中断option的在线分层强化学习方法-朱斐.pdf》由会员分享，可在线阅读，更多相关《基于可中断option的在线分层强化学习方法-朱斐.pdf（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第37卷第6期2016年6月通信学报Joumal On CommunicationsVbl37 NO6June 2016doi：lO119590issn1000-436x2016117基于可中断Option的在线分层强化学习方法朱斐L2，许志鹏1，(1苏州大学计算机科学与技术学院，江苏苏州215006；2刘全1上，伏玉琛1，王辉1吉林大学符号计算与知识工程教育部重点实验室，吉林长春130012)摘要：针对大数据体量大的问题，在MacroQ算法的基础上提出了一种在线更新的MacroQ算法(MQIU)，同时更新抽象动作的值函数和元动作的值函数，提高了数据样本的利用率。针对传统的马尔可夫过程模型和抽

2、象动作均难于应对可变性，引入中断机制，提出了一种可中断抽象动作的MacroQ无模型学习算法(IMQ)，能在动态环境下学习并改进控制策略。仿真结果验证了MQlU算法能加快算法收敛速度，进而能解决更大规模的问题，同时也验证了IMQ算法能够加快任务的求解，并保持学习性能的稳定性。关键词：大数据；强化学习；分层强化学习；Option；在线学习中图分类号：TPl81 文献标识码：AOnline hierarchical reinforcement learningbased on interrupting OptionZHU Feil”，XU Zhipen91，LIU Quanl”，FU Yuchenl

3、，WANG Huil(1School ofComputer Science and Technology,Soochow University,Suzhou 215006，China；2Key Laboratory ofSymbolic Computation and Knowledge Engineering ofMinistry ofEducation，Jilin University,Changchun 130012，Chma)Abstract：Aiming at dealing with volume of big data,all online updating algorithm，

4、named by MacroQ with inplaceupdating(MQIU)，which was based on Maero-Q algorithm and takes advantage of in-place updating approach，was proposedThe MQIU algorithm updates both the value function of abstract action and the value function of primitive action，and hence speeds up the convergence rateBy in

5、troducing the interruption mechanism，a modelfree interruptingMacro-O Option learning algorithm(IMQ)，which Was based on hierarchical reinforcement learning，was also introducedto order to handle the variability which Was hard to process by the conventional Markov decision process model and ab-stract a

6、ction SO that IMQ Was able to icam and improve control strategies in a dynamic environmentSimulations verifythe MQIU algorithm speeds up the convergence rate SO that it is able to do with the larger scale of data，and the IMQ algorithm solves the task faster with a stable learning performanceKey word

7、s：big data,reinforcement learning，hierarchical reinforcement learning，Option，online learning1 引言在强化学习(RL，reinforcement learning)框架中，用户给出问题的目标，agent选择某一个动作，实现与环境的交互，获得环境给出的奖赏作为强化信号，agent根据强化信号和环境当前状态再选择下收稿日期：20150403：修回日期：20160412通信作者：伏玉琛，yuchenfusucheducn基金项目：国家自然科学基金资助项目(No61303108，No61373094，No612

8、72005，No61472262)：江苏省高校自然科学研究基金资助项目(No13l(m520020)；吉林大学符号计算与知识工程教育部重点实验室基金资助项目(No93K172014K04)：苏州市应用基础研究计划基金资助项目(NoSYG201422)；苏州大学高校省级重点实验室基金资助项目(NoKJSl524)；中国国家留学基金资助项目(No201606920013)Foundation Items：Thc National NaturaI Science Foundation ofChina(No61303108，No61373094，No61272005，No，61472262)，The

9、Higll School Natural Foundation of Jiangsu Province(No1 3KJB520020)，The Key Laboratory of Symbolic Computation andKnowledge Engineering of Ministry of Education of Jilin University(No93K172014K04】，Suzhou Industrial Application of BasicResearch Program(NoSYG20 1 422)Provincial Key Laboratory for Comp

10、uter Information Processing Technology of Soochow Univemity(NoKJSl524)The China Scholarship Council Proiect(No201606920013)20161171万方数据通信学报 第37卷一个动作。Agent的目标是在每个离散状态发现最优策略以使期望的折扣奖赏和最大。作为一种具有较高通用性的机器学习框架，强化学习得到了较为广泛的研究和应用【2J。然而，由于强化学习的算法需要通过不断地与环境交互来进行学习，同时还要保存经验数据，因此当问题规模扩大时，算法的复杂度往往会以指数级上升，导致算法的性能急

11、剧下降，所以强化学习的经典算法很难直接用于解决数据规模比较大的问题。研究人员提出了多种改进的强化学习算法来解决大规模空间的“维数灾”问题，如分层强化学习【34J、核方、法【5I、函数逼近方法161等。在这些方法中，分层强化学习被用于解决一些大数据环境的任务【7J。在分层强化学习的算法中，通过分层处理，agent关注当前局部空间的环境以及子任务目标状态的变化，策略更新的过程限定于局部空间或者高层空间上，相应地，所需解决的问题规模被限定在agent当前所处的较小规模的空间或抽象程度较高、维数较低的空间。这样不仅可以加快学习的速度，而且可以降低对环境的依赖性。在动态变化的环境中，这种特性有助于解决问

12、题，因此显得尤为重要。时问抽象的方法是分层强化学习的一类重要方法。利用时间抽象，agent可以关注更高层策略的选择，从而降低算法的复杂度，使算法能解决一些大规模的问题。抽象动作为时间抽象提供了广泛的框架，其代表性工作是由Suuon掣8】提出的使用“宏动作”作为抽象动作的Option框架。很多方法使用子任务来表达抽象动作，子任务构成了整个任务的一部分91。也有很多工作寻找与子任务对应的子目标点【胁12】，以及直接从值函数中得到抽象动作【l玉14J。一般而言，大数据是指不能在可以容忍的时间内用传统信息科学的技术、软件和硬件完成感知、获取、管理、处理和服务的数据集合【l 5|。大数据具有体量大(vo

13、lume)、多变(variability)、价值高(value)、高速(velocity)等特点。由于大数据体量大，因此很多机器学习的算法无法直接用来解决大数据问题。大数据的多变性也要求机器学习的算法在考虑数据体量的同时，考虑数据的动态变化性。在大数据问题中，当无法直接从整个问题空间上求解最优解时，如何充分利用已有抽象动作来求解是一个需要解决的重要任务。虽然，SuRon等【l 6J对此有过初步的研究，但是，由于其工作是基于模型已知的前提下进行规划，故而在模型未知或环境动态变化的情况下，算法性能和效果会很差，导致算法很难应用于模型无关的任务和在线学习的任务中，更无法在大数据和动态的环境中很好地学

14、习到最优策略。本文的主要工作就是解决动态环境下如何利用时间抽象学习的问题，针对大数据体量大的特点，在MacroQ算法的基础上提出了在线式更新的算法，加快了算法的收敛速度，提高了数据样本的利用率，同时针对大数据可变化的特点，提出了中断式动作抽象的概念，使之能很好地适应环境的变化，并在此基础上提出了一种基于中断动作抽象的无模型学习算法。2相关工作21强化学习大多数的强化学习方法都是基于马尔可夫决策过程(MDP,Markov decision process)。一个MDP可以用一个5元组表示，其中，S和A分别表示有限的状态集和动作集，P0，1】表示迁移概率，R：SxA-)R表示agent得到的立即奖

15、赏，7【0，l】表示折扣因子。在每个时间步，agent观察到系统的状态jS后采取某个动作口彳，然后以概率P(sI s，口)迁移到下一个状态JS，此时agent会得到一个立即奖赏R(s，口)。Agent的目标是通过最大化期望奖赏来找到最优策略：SxAj0，l】。在线学习是一种在学习的过程中需要及时处理收集的数据，进行预测并更新模型的学习方式【l 71。在线式强化学习通过与环境实时的交互来获取样本，然后再通过这些样本更新策略。在线强化学习能够在保证学习效果的前提下，同时给出次优的学习结果，而且在线采样比离线采样更容易。相比之下，离线的算法要求样本已知，只有在样本学完后才能应用学习好的策略。在大数据

16、环境下，由于数据体量大，无法完全装载到内存中处理，因此，大数据环境的很多任务都采用在线学习的方式完成。22抽象动作本文使用马尔可夫抽象动作【1381来描述时间抽象的动作序列。马尔可夫抽象动作和元动作同样是由agent选择的，不同的是抽象动作的执行是一个时间段，是多步完成的，而元动作则是单步完成，所以元动作被视为一种基本动作。在抽象动作执行的过程中，遵循抽象动作的内部策略，直到满足抽象动作的终止条件。一般的抽象动作框架由一个3元组，万方数据第6期 朱斐等：基于可中断Option的在线分层强化学习方法 67其中，S表示抽象动作的输入集，万：Sx A-)【0，1表示策略，：S-)0，1】表示终止条件

17、。若sI，那么抽象动作在s处即为可用的。一个马尔可夫抽象动作执行过程如下：如果agent在状态S处选择了抽象动作O，那么agent将会根据O的策略7来选择下一个动作，即q卜x(s，)。环境的状态将会迁移Nsr+l，即(s，石)生哼Jr+l，在s处，agent会根据终止条件口来判断是否终止O的执行，如果p(S)一0，将会一直执行抽象动作O直到满足终止条件(sM)一1。这样，对所有的元动作，都有p(s)j 0。当一个抽象动作终止时，agent可以选择另外的一个抽象动作继续执行，或元动作执行。接下来，定义在抽象动作概念下的策略。设在状态s，处可用的抽象动作集合定义为p，当agent从状态S，处出发，

18、马尔可夫策略v会以v(s，D)的概率选择抽象动作O，其中，Oq。随后，将会根据O的策略1来选择动作，直到O在Sm终止。然后再根据，(sM)选择下一个抽象动作O，继续执行这一过程。实际上定义在抽象动作O上的策略v决定了一个定义在动作上的策略U，即U=厂(1，)。可得V。(J，)=Ert+l+”+2+fr,+3+J e(u，s，f)(1)其中，e(u，s，f)表示策略掰在t时刻从状态J，处开始的这个过程。由于式(1)是建立在元动作上的，而策略U是由v决定的，所以有V”(s，)=Vf(v)(s，)。这样，类似得到Q”(s，0)=E，；+1+7r,+2+广+3+I e(vo，S，f)(2)其中，e(v

19、o，S，t)表示策略v首先选择了抽象动作0，直到0终止，然后再根据y选择其他抽象动作的过程。23半马尔可夫决策过程在强化学习中，满足马尔可夫性的强化学习任务就被称为MDP，而一个半马尔可夫决策过程(SMDP,semiMarkov decision process)可以由一个MDP和一个抽象动作集合组成。经典的SMDP理论是与动作相关的，其中，相关方法可以扩展到抽象动作中来。这样，对任意的抽象动作O，若e(o，s，t)表示O在t时刻状态s，处开始的过程，那么对应奖赏的模型为鬈=Ert+l+”+2+矿，；+3+矿_1+I l(D，5，f)(3)其中，t+k表示O的终止时刻。类似地，转移概率的模型为

20、式，=p(s，k)f (4)k=l其中，p(s，七)表示0在k个时间步后在状态S。终止的概率。然后根据贝尔曼等式，对任意的马尔可夫策略U，状态值函数为y“(_)=o。o()鬈+。磋，(s)】(5)对应的动作值函,u数St为,OVQ”(0，D)=鬈+。磋，V”(s) (6)在值函数的基础上，可以得到最优值函数。在MDP中，选择的是最优的动作，而这里选择的是最优的抽象动作。使用0来定义抽象动作集合，根据贝尔曼最优等式，可以得到最优值状态函数和最优动作值函数，分别如式(7)和式(8)所示。y(q)=max。吼鬈+，磋。y。(51) (7)Q(啪)=鬈+。磋。，V。(s)=+。略max嗍，Q。(s，D

21、) (8)根据最优值函数，得到Q值的更新公式为Q“(s，0)6-Qlf(s，0)+讲鬈+矿max。Q”(Jm，03一矿(St，D) (9)若抽象动作集合已经得到，那么就可以求出最优的状态值函数和动作值函数，最后得出最优策略。而且，标准-的SMDP理论能够保证这样的过程能够收敛。3算法描述31可中断Option抽象动作提高了agent探索的效率，从而使算法收敛速度更快f2】o利用抽象动作在解决相同领域的多任务时效果很好10】。传统应用抽象动作的SMDP方法通常是把抽象动作看作一个不透明、不可分割的整体。然而，要充分地发挥抽象动作的作用，需要改变抽象动作本身的结构。这里考虑使用中断抽象动作，即抽象

22、动作在根据它的终止条件之前，如果有需要就中断抽象动作的执行。如在房间内导航的任务中，把agent从房间门入口进入到房间里这个动作序列建模成一个抽象动作，当agent执行这个抽象动作万方数据通信学报 第37卷到刚刚准备踏入房间的那一瞬间，门突然关闭了，根据传统的SMDP中抽象动作的定义，此时抽象动作不应该终止，而应该继续执行，因为抽象动作的终止条件还不满足，而这就与门已经处于关闭状态形成了矛盾，导致agent的执行效率降低甚至失效。如果采用可中断Option，就可以解决这一问题。32可中断MacroQ算法传统的强化算法agent通过与环境反复交互的方式来学习值函数和策略，但是随着问题规模的扩大，

23、agent就需要大量的时间和经验来与环境进行交互以获得好的策略。使用分层强化学习方法，应用抽象动作能在一定程度上减少对环境的探索，从而加快算法收敛和保证算法学习前期性能的稳定性。经典的SMDP方法把抽象动作看作一个不可拆分的整体，一旦抽象动作开始执行，就必须执行到抽象动作终止，不能中途结束。事实上，这种方式会面临以下2个主要问题：首先，在动态的环境下，往往在抽象动作还没结束时，抽象动作就执行不下去，导致算法效果很差；其次，在抽象动作执行的过程中，在某些状态选择其他的抽象动作会获得更好的性能。针对这2种可能出现的情况，本文提出了一种可中断Macro-Q(IMQ，interrupting Macr

24、oQ)算法。假设已经得到了策略U的抽象动作值函数Q“(s，D)，其中，U是全局策略，s，O是状态,Option对。Q“(J，D)这个状态一Option的值函数不仅可以评估当前采用的策略U好坏，而且可以评估当前每一步动作实施的好坏。假设在t时刻，根据策略暂的选择，agent当前正在跟随抽象动作O，这时可以比较按照O执行得到的(J，O)和中断O选择新的抽象动作得到的值函数为y。(s)=。u(s，o-)Q“(s，03如果V“(s，)Q。(s，0)，说明此时选择其他抽象动作得到的回报会更高，这时就中断0，然后再根据策略“选择其他抽象动作是完全可行的，如算法1所示。算法1可中断MacroQ算法输入：折扣

25、因子)，学习率仅，Option集合哝输出：Q值函数1)初始化Q值函数和队列缈2)for每个情节d03) 以品作为起始状态，初始化S，4) repeat51 根据策略甜从og中选择一个OptionoIq，冗，86) 执行O7) 根据顽Jf)选择动作口8) 观察S，r9) 万-，+?max。Q(s，a9一Q(s，口)10) Q(s，口)卜Q(s，口)+ag11) 将S，S，保存到队列妒中12) iffl(s1=1 orJ=sthen13) forJ inQEdo14) 以批量方式更新矿Q，o)15) 选择一个新的Option O16) endif17) else ifO)矿O，O)18) fors

26、in妒do19) 以批量方式更新O，O)20) 选择一个新的Option O21) J-S22) 终止执行O23)until s是终止状态24)returnQ算法1是一种基于中断思想的无模型学习算法，能够很好地解决环境变化情况下，抽象动作无法整体使用的问题。33在线更新的Maero-Q算法在线学习方法延伸模型的学习过程。在使用过程中，新数据的到来会引发模型的更新。而这种学习方法的一个直接负面影响是采样代价较高19】。作为一种在线式的学习算法，经典的MacroQ就需要花费完成采样。本文改进了MacroQ算法，采用在线式in-place更新方法，在agent对抽象动作值更新的同时，对执行过的元动作

27、也进行更新，如在线更新的Macro-Q(MQIU，macro-Q with in-place updating)算法所示。Macro-Q算法加快了Q值更新速率，从而加快算法的收敛速度。算法2在线更新的Macro-Q算法输入：折扣因子7，学习率0【，Options集合q输出：Q值函数1)初始化Q值函数和队列Qe2)for每个情节do3) 以s，作为起始状态，初始化&41 repeat5) 根据策略U从哝中选择一个Option O=万方数据第6期 朱斐等：基于可中断Option的在线分层强化学习方法 69q，7L，胪6) 执行07) 根据7如r)选择动作口8) 观察s，9) 万卜r+ymax。Q(

28、s，口-)一Q(s，a)10) Q(s，a)-Q(s，口)+笳11) 将s，J，保存到队列筘中12) if觑S)=1 then13) for s in QE do14) y卜+1+”+2+矿+。+矿max。，(薯+。，0一Q(s，g)Q(薯g)I重l(薯，D，)+口y15) 选择一个新的Option 016) end if17) S卜S18) 终止执行019)until J是终止状态20)retumQ34算法分析对任意的MDP、任意的Option集合0以及任意的马尔可夫策略U，定义一个新的Option集合D，这2个Option集合之间存在一一映射：对每个0=0定义一个相应的010，其中，当Q”

29、(厅，0)矿”(J)时，=，h表示历史，J表示h的最后一个状态，选择让0在状态s处终止：(s)=1。所有的以这种方式中断的历史称为中断历史。令“作为在0上和“相应的策略，则有u(s，0)=甜(s，D)，那么：1)对所有的JS，有y。(了)V。(s)；2)如果从状态SS出发，存在一个非零的概率遇到中断历史，那么有矿旷(s)V。(S)；3)对所有的Js，OE 0有l嗵+K0)=巧(s)，即算法能够最终收敛到一个不动点。证明对任意的状态s，执行对终止条件改进了的策略U，随后再跟随策略U，即证明下面不等式是成立的。材如，口)誓。+，矿01)】矿)(1 o)其中，矿(s)=。甜(s，D)【誓+，p0V“

30、(s)】。如果不等式(10)成立，扩展左式，重复使用。甜(工，DI)【哆+，V“o-)】替换左式y”(万)。在极限的情况下，左式变成y。，即可证明V。V“。因为“(s，Dt)=u(s，D)，VsS，需要证明哆+。y”o)#+，戚矿“o) (11)令厂表示所有的中断历史厂=办Q：p()(办)。那么式(11)左边可以写为Ep+矿y。(s3 e(o，s)，k仨厂)+Er+矿Ot)I e(o，J)，k，厂)其中，j：，k分别表示下一个状态，立即奖赏及从状态S处跟随Optiono执行的步数，五一表示从状态5到状态s的历史。由于轨迹中碰到了办萑厂而从没有碰到办。厂，所以轨迹会终止，而且在状态S处执行0之后

31、会以同样的概率和相同的期望出现。所以，不等式(11)的右边可以改写为E，+矿矿“(Jf)le(o，s)，纪，芒厂)+E(占)【，-+矿y”(s-)】+(1一(s)，+矿Q。y。4仿真实验本文在格子世界实验的基础上，模拟动态和静态的环境进行仿真实验。通过与Q1earning做实验对比并给出实验结果来仿真验证IMQ的可行性和有效性。在仿真实验中，agent使用Egreedy进行探索，初始探索概率=01，学习率口=O1，Q值都初始化为0，也可以被随机初始化。根据问题规模的不同，将提供不同的抽象动作集合。41动态环境的描述到目前为止，强化学习大多数的研究都用于解决一些简单的学习任务，如房间导航问题、平

32、衡杆问题、直流电机问题、过山车问题等。但是这些问题大多都是设定为静态环境的。如房间导航闽题中，只有固定的墙壁或障碍物。然而，在实际的应用环境往往是未知的或者会发生变化。相应地，房间导航问题的设定中，障碍物应该是随机出现的，而且出现的位置也应该是随机的。本文的一个目标就是在动态的、不断变化的环境中找到最优策略。在图1(a)所示的动态格子世界的仿真实验中，万方数据通信学报 第37卷共有2121个网格，标记为“S”的格子表示agent的出发点，标记为“G”的格子表示agent的目标终点，标记为“O”的格子表示障碍物。动态格子世界环境是会动态变化的，包括2种变化的对象：agent和障碍物的位置。对比图

33、l(a)和图1(b)可以发现，在不同的时间，障碍物的位置是不一样的。(a)实验环境为212 1的格子世界(b)障碍物的位置发生了变化图1 一个2121的网格的动态环境示意42 MQIU在格子世界中的性能为了衡量MQIU的性能，本文在仿真实验环境下同时实现了MacroQ、Qlearning和MQIU。实验环境为一个11 x 11的格子世界，如图2(a)所示，agent的出发点设在左下方，用“S”表示，目标点设在格子顶部的中间，用“G”表示。Agent的任务是从“S”出发，以最快的方式到达目标点“G”，agent所能采取的元动作为上、下、左和右。在算法MacroQ和MQUI中，agent所能采取的

34、动作除了上、下、左、右这4个元动作外，对每个状态还有4个可选的抽象动作，分别沿4个方向移动，直到碰到墙为止。GS(a)实验环境为1111的格子世界情节(b)MQIU、MacroQ以及Qlearning在图2(a)环境F的表现图2 ll11的格子世界中MQIU、Macro-Q和Qlearning的算法性能比较从图2(b)可以看出，MQIU和MacroQ比Q1earning收敛更快，而且在整个学习过程中MQIU和Macro。Q都保持了很好的性能，平均每个情节步数维持在50步内。对比MacroQ可以看出，MQIU在前15个情节稍差，但是在第15个情节之后，MQIU算法的性能就好于MacroQ。产生这

35、种现象的原因是MQIU在对抽象动作更新的同时更新了元动作的Q值，从而会加快值的收敛速度。43 IMQ在4房间静态格子世界中的性能本文首先对IMQ在静态环境下的表现做了深入的说明，如图3所示。4个房间静态格子世界实验如图3(a)所示，其中，“S”代表出发点，“G”代表目标点。Agent从“S”出发，经过房间之间的通道到达“G”，则一个情节结束。为了更好地说明算法的性能，IMQ和MacroQ所使用的抽象动作是完全一样的。实验中的抽象动作设为每个房间内2个，一共8个，每个抽象动作能够把agent从房内任意一点带到房间的出口处。万方数据第6期 朱斐等：基于可中断Option的在线分层强化学习方法S _

36、 1 b-、lT_(a)实验环境为静态的4个房间格子世界情节(b)IMQ、Macro-Q以及Q-learning在4个房间静态格子世界中的表现图3 Macao-Q和Qqeaming在4个房间格子世界中学习性能曲线对比从图3(b)中可以看出，在4个房间格子世界中，IMQ和MacroQ的算法性能比Qlearning好很多。MacroQ性能较为稳定，在整个学习的过程中一直保持很低的学习步数，然而其收敛速度和Q1earning一样，在500个情节后收敛。IMQ注重探索，在前50个情节性能比Q1earning好，略差于MacroQ，但是IMQ收敛效果很好，在200个情节的时候就达到了收敛，并且一直保持很

37、稳定。44 IMQ在4个房间动态格子世界中的性能4个房间动态格子世界实验如图4(a)所示。由于在这个实验中，环境被设置为动态变化的，因此更能检验算法的性能。目标状态“G”被放置在右下角的房间，起始状态“S”被放置在左上角房间的角落里。每个情节会随机初始化25个障碍物“O”，用来表示随机的环境。元动作是4个方向的动作：上、下、左和右。Agent在贪心动作(元动作或者抽象动作)的选择概率为l一+F斗：广，其他方 H。+M，向上，元动作或者抽象动作的选择概率为F年丁。H。+M。Agent每走一步的奖赏都是一1，到达目标点的奖赏是0。由于本文关注的重点是抽象动作在动态环境中的应用，因此这里的抽象动作是

38、预先定义好的。实验中对比了IMQ和Q1earning，没有对比Macro-Q以及基于规划的中断方法，是因为在动态环境下，这2种算法性能都很差。MacroQ没有引(a)4i,-房间动态环境籁蚺太降情节(b)IMQ和Qlearning平均步数对比情节(C)IMQ和Qlearning累计步数对比图4在4个房间动态环境下带有不同抽象动作集合的IMQ算法与Qlearning学习性能比较万方数据通信学报 第37卷入中断机制，导致如果抽象动作的执行过程被破坏，那么将无法继续按照抽象动作的内部策略继续执行。而基于规划的中断方法用于在线的算法中并不是很合理，而且需要模型，因此这里没有对比这2种算法。图4(b)显

39、示了在100次重复实验的基础上，agent从起始状态到达目标状态的平均步数，对比了IMQ和Q1earning在动态的格子世界中的性能。从图中可以看出带有不同抽象动作集合的3种IMQ算法无论是在收敛速度还是在学习时的表现上均好于Q1earning。其中，IMQ with integrated Option在性能上略差于另外2个IMQ算法，IMQ with good Option的性能总体上和IMQ withkey Option相当；但是从图4(c)可以看出，IMQwith key Option仅在前50个情节略差于IMQ withgood Option，从长期学习来看，IMQ with keyO

40、ption学习效率更高，收敛更快。仿真实验证明了算法在动态环境下的有效性。为了更精确地说明几种算法的性能对比，在表1中给出了4个房间动态格子世界中各算法性能的对比数据。表1 4个房间实验中，不同抽象动作集IMQ和Qlearning的对比实验结果数据45 IMQ在6个房间动态格子世界中的性能作为IMQ的第3个实验，在更大规模的环境下进行实验验证。本文使用6个房间的动态格子世界来进行仿真实验。Agent的任务和前面描述的基本一样，从起始点状态“S”走到目标状态“G”。实验的环境如图5(a)所示，其中，起始状态“S”靠近左上角，目标状态靠近右边。随机环境以及元动作的设定和前面介绍的一样，随机生成25

41、个障碍物，用“O”表示。提供的抽象动作和前一节介绍的一样，但是由于房间的增多，这里提供的抽象动作的数量也会相应的变化。图5(b)显示了在100次重复实验的基础上，agent从起始状态到达目标状态的平均步数，这个图与4个房间实验中的图相比，区别在于状态的增多、环境的复杂度更高，导致agent在学习的前期到达目标点所需的步数的增加，同时收敛速度也有所减缓。从图5可以看出，随着环境规模的增大，各算法间的区别更加明显。实验图5(b)表明，3种IMQ算法表现均优于Q1earning，其中，IMQ with keyOption达到收敛所需的总步数最少，情节数也最少，这说明，关键的抽象动作能够更有效地加快a

42、gent的学习效率。(a)64-格子动态环境情节(b)IMQ和Qlearning平均步数对比情节(c)tMQ和Qlearning累计步数对比图5在6个房间动态环境下带有不同抽象动作集合的IMQ算法与Q-learning学习性能比较5结束语本文的工作主要包括以下几个方面。首先，针对传统SMDP方法不能解决动态环境下的学习万方数据第6期 查斐竺：苎三里主堑塑!竺竺垄些坌星塑些兰翌查堡 一：!：_-_-_-_-_-_-_-_。-。_-。-_。-_-_-_-_。_。_。_。一一 一和控制问题，本文提出一种在线学习的使用可中 Research andDevelopment，2011，48(12)：235

43、22358断銎堡尊象的算妻=!曼篓嬖坌星苎竺掌51翁麓霎凳器磊，新2014劬(2)：法10篇瓣Am石泮习的方法，IMQ算法能够有效解决大数据环境下 淼要：二乏磊；：d。IK二1b器。d。ifl。i。一般强化学习算法由于时间复杂度过高而不能解 actorcriticlearning叽PattemRecognition andArtificialIntelligence，决的问题。相比于离线算法，IMQ算法能够在线 2014(2)：103110竺芒至兰翌翌委置从要耋婴等兰要效率的呈翌161喜耄嚣嚣等蕊焉1馘茬,20辨14,5空1(慧3)：548-小55球8行动又保证了算法的性能。实验结果表明，IM

44、Q算法 二f蔷Q一,F”UQ”磊二：=。q。撤。tor-。椭。ppro。chfor比Q1earning算法和Macro-Q算法具有更快的收 。ontinuous acti。n spa。m Joll兀1a1 ofComputer Research and Devel敛速度。 opment,2014，5l(3)：548558，其次，针对MacroQ算法样本利用率不高的问 71唐吴，张晓艳，韩江洪，等基于连续时间半马尔可夫决策过程的题，本文提出了一种基于同步替代更新的算法一 篡耋雹蹴嚣黧1篡裟。，舳铡MQIU算法。在算法中，对抽象动作的值函数进行 continuous-time。mi-Mark。de

45、。i。i。pr。m Chine。e Journal。f更新的同时，也更新元动作的值函数。实验结果表 Computers，2014(9)：20272037明，MQIU算法较MacroQ效果略好，收敛速度上 【8】suTToN R 8，PREcUP D，sNGH sB咖。en脚s and略快。薹=二。慧：篙i：=簧。篙嚣鬻n-冀。?衙眦m第三，针对传统的抽象动作不能很好地解决动 9】McGOVERN A，BARTO A G Automatic discovery of subgoals in态环境的问题，本文将中断的方式引入抽象动作的 reinforcement learning using di

46、verse densityJComputer Science概念中，提出了中断式动作抽象的概念，使之能很DepartmentFacultyPublication Serie8，2001(8)：361-368好地适应环境的变化并在此基础上黜了一种基n：篆=：鬻篙：f篙篡笳=于中断动作抽象的无模型学习算法。实验结果表 I胀m。ion。1 Conferenc。e：n Ma二i三：。m砸1M。2005：明，在动态的环境下，适当地利用抽象动作能够加816823快任务的求解，并且有助于agent在学习的过程中 【11$IMSEK 0，BARTO A G Using relative novelty to

47、identify useful保持性能的靛。：=：篙=：。：盖掣冀岔监：然而，在本文中的抽象动作是预先定义好的， ，礼，张 。如何快速有效地自动发现合适的抽象动作来加快 121 CHAGANTY A T，GAUR PRAVINDRAN BLearning in a small长期学习agent的学习效率，是将要研究的一个重 worldCThe llth International Conference on Autonomous Agents要内容。另外，在动态的环境下，如何充分利用样 and M“1i89ent syste脚+V01岫。1In。m8io“81 Foundation fo。本的

48、模型学习以及如何将抽象动作用于多任务、多 【13】：i：焉：茎UPt Sys。te，m或sc。201三三等二i纰啦agent协作也是主要的一项工作。 aInongtempomlly abstract actionsJAdvancesinNeuralIflfo呻ation参考文献： 141 CAProcseTR0ssingPSysst，emPREs 1c9UP99：1D066Aulot07mt2 ic c。ns订ucti。n 0f teInp。rally，一1】 OTTEIuLO M V，W脚州G MRei晌rceI咖t learning肌d MarkoV Conference on Recent Adv锄c酷 in ReinforcementL