基于可中斷Option的在線分層強化學習方法

朱斐，許志鵬，劉全，伏玉琛，王輝

?

基于可中斷Option的在線分層強化學習方法

朱斐1,2，許志鵬1，劉全1,2，伏玉琛1，王輝1

（1. 蘇州大學計算機科學與技術(shù)學院，江蘇蘇州215006；2. 吉林大學符號計算與知識工程教育部重點實驗室，吉林長春130012）

針對大數(shù)據(jù)體量大的問題，在Macro-Q算法的基礎(chǔ)上提出了一種在線更新的Macro-Q算法(MQIU)，同時更新抽象動作的值函數(shù)和元動作的值函數(shù)，提高了數(shù)據(jù)樣本的利用率。針對傳統(tǒng)的馬爾可夫過程模型和抽象動作均難于應對可變性，引入中斷機制，提出了一種可中斷抽象動作的Macro-Q無模型學習算法(IMQ)，能在動態(tài)環(huán)境下學習并改進控制策略。仿真結(jié)果驗證了MQIU算法能加快算法收斂速度，進而能解決更大規(guī)模的問題，同時也驗證了IMQ算法能夠加快任務的求解，并保持學習性能的穩(wěn)定性。

大數(shù)據(jù)；強化學習；分層強化學習；Option；在線學習

1 引言

在強化學習（RL，reinforcement learning）框架中，用戶給出問題的目標，agent選擇某一個動作，實現(xiàn)與環(huán)境的交互，獲得環(huán)境給出的獎賞作為強化信號，agent根據(jù)強化信號和環(huán)境當前狀態(tài)再選擇下一個動作。Agent的目標是在每個離散狀態(tài)發(fā)現(xiàn)最優(yōu)策略以使期望的折扣獎賞和最大[1]。作為一種具有較高通用性的機器學習框架，強化學習得到了較為廣泛的研究和應用[2]。然而，由于強化學習的算法需要通過不斷地與環(huán)境交互來進行學習，同時還要保存經(jīng)驗數(shù)據(jù)，因此當問題規(guī)模擴大時，算法的復雜度往往會以指數(shù)級上升，導致算法的性能急劇下降，所以強化學習的經(jīng)典算法很難直接用于解決數(shù)據(jù)規(guī)模比較大的問題。研究人員提出了多種改進的強化學習算法來解決大規(guī)模空間的“維數(shù)災”問題，如分層強化學習[3,4]、核方法[5]、函數(shù)逼近方法[6]等。在這些方法中，分層強化學習被用于解決一些大數(shù)據(jù)環(huán)境的任務[7]。

在分層強化學習的算法中，通過分層處理，agent關(guān)注當前局部空間的環(huán)境以及子任務目標狀態(tài)的變化，策略更新的過程限定于局部空間或者高層空間上，相應地，所需解決的問題規(guī)模被限定在agent當前所處的較小規(guī)模的空間或抽象程度較高、維數(shù)較低的空間。這樣不僅可以加快學習的速度，而且可以降低對環(huán)境的依賴性。在動態(tài)變化的環(huán)境中，這種特性有助于解決問題，因此顯得尤為重要。時間抽象的方法是分層強化學習的一類重要方法。利用時間抽象，agent可以關(guān)注更高層策略的選擇，從而降低算法的復雜度，使算法能解決一些大規(guī)模的問題。抽象動作為時間抽象提供了廣泛的框架，其代表性工作是由Sutton等[8]提出的使用“宏動作”作為抽象動作的Option框架。很多方法使用子任務來表達抽象動作，子任務構(gòu)成了整個任務的一部分[9]。也有很多工作尋找與子任務對應的子目標點[10~12]，以及直接從值函數(shù)中得到抽象動作[13,14]。

一般而言，大數(shù)據(jù)是指不能在可以容忍的時間內(nèi)用傳統(tǒng)信息科學的技術(shù)、軟件和硬件完成感知、獲取、管理、處理和服務的數(shù)據(jù)集合[15]。大數(shù)據(jù)具有體量大(volume)、多變(variability)、價值高(value)、高速(velocity)等特點。由于大數(shù)據(jù)體量大，因此很多機器學習的算法無法直接用來解決大數(shù)據(jù)問題。大數(shù)據(jù)的多變性也要求機器學習的算法在考慮數(shù)據(jù)體量的同時，考慮數(shù)據(jù)的動態(tài)變化性。在大數(shù)據(jù)問題中，當無法直接從整個問題空間上求解最優(yōu)解時，如何充分利用已有抽象動作來求解是一個需要解決的重要任務。雖然，Sutton等[16]對此有過初步的研究，但是，由于其工作是基于模型已知的前提下進行規(guī)劃，故而在模型未知或環(huán)境動態(tài)變化的情況下，算法性能和效果會很差，導致算法很難應用于模型無關(guān)的任務和在線學習的任務中，更無法在大數(shù)據(jù)和動態(tài)的環(huán)境中很好地學習到最優(yōu)策略。本文的主要工作就是解決動態(tài)環(huán)境下如何利用時間抽象學習的問題，針對大數(shù)據(jù)體量大的特點，在Macro-Q算法的基礎(chǔ)上提出了在線式更新的算法，加快了算法的收斂速度，提高了數(shù)據(jù)樣本的利用率，同時針對大數(shù)據(jù)可變化的特點，提出了中斷式動作抽象的概念，使之能很好地適應環(huán)境的變化，并在此基礎(chǔ)上提出了一種基于中斷動作抽象的無模型學習算法。

2 相關(guān)工作

2.1 強化學習

大多數(shù)的強化學習方法都是基于馬爾可夫決策過程(MDP, Markov decision process)。一個MDP可以用一個5元組表示，其中，和分別表示有限的狀態(tài)集和動作集，表示遷移概率，表示agent得到的立即獎賞，表示折扣因子。在每個時間步，agent觀察到系統(tǒng)的狀態(tài)后采取某個動作，然后以概率遷移到下一個狀態(tài)，此時agent會得到一個立即獎賞。Agent的目標是通過最大化期望獎賞來找到最優(yōu)策略。

在線學習是一種在學習的過程中需要及時處理收集的數(shù)據(jù)，進行預測并更新模型的學習方式[17]。在線式強化學習通過與環(huán)境實時的交互來獲取樣本，然后再通過這些樣本更新策略。在線強化學習能夠在保證學習效果的前提下，同時給出次優(yōu)的學習結(jié)果，而且在線采樣比離線采樣更容易。相比之下，離線的算法要求樣本已知，只有在樣本學完后才能應用學習好的策略。在大數(shù)據(jù)環(huán)境下，由于數(shù)據(jù)體量大，無法完全裝載到內(nèi)存中處理，因此，大數(shù)據(jù)環(huán)境的很多任務都采用在線學習的方式完成。

2.2 抽象動作

本文使用馬爾可夫抽象動作[1,18]來描述時間抽象的動作序列。馬爾可夫抽象動作和元動作同樣是由agent選擇的，不同的是抽象動作的執(zhí)行是一個時間段，是多步完成的，而元動作則是單步完成，所以元動作被視為一種基本動作。在抽象動作執(zhí)行的過程中，遵循抽象動作的內(nèi)部策略，直到滿足抽象動作的終止條件。

(2)

2.3 半馬爾可夫決策過程

在強化學習中，滿足馬爾可夫性的強化學習任務就被稱為MDP，而一個半馬爾可夫決策過程(SMDP, semi-Markov decision process)可以由一個MDP和一個抽象動作集合組成。經(jīng)典的SMDP理論是與動作相關(guān)的，其中，相關(guān)方法可以擴展到抽象動作中來。這樣，對任意的抽象動作，若表示在時刻狀態(tài)處開始的過程，那么對應獎賞的模型為

(4)

對應的動作值函數(shù)為

(6)

在值函數(shù)的基礎(chǔ)上，可以得到最優(yōu)值函數(shù)。在MDP中，選擇的是最優(yōu)的動作，而這里選擇的是最優(yōu)的抽象動作。使用來定義抽象動作集合，根據(jù)貝爾曼最優(yōu)等式，可以得到最優(yōu)值狀態(tài)函數(shù)和最優(yōu)動作值函數(shù)，分別如式(7)和式(8)所示。

(8)

若抽象動作集合已經(jīng)得到，那么就可以求出最優(yōu)的狀態(tài)值函數(shù)和動作值函數(shù)，最后得出最優(yōu)策略。而且，標準的SMDP理論能夠保證這樣的過程能夠收斂。

3 算法描述

3.1 可中斷Option

抽象動作提高了agent探索的效率，從而使算法收斂速度更快[2]。利用抽象動作在解決相同領(lǐng)域的多任務時效果很好[10]。

傳統(tǒng)應用抽象動作的SMDP方法通常是把抽象動作看作一個不透明、不可分割的整體。然而，要充分地發(fā)揮抽象動作的作用，需要改變抽象動作本身的結(jié)構(gòu)。這里考慮使用中斷抽象動作，即抽象動作在根據(jù)它的終止條件之前，如果有需要就中斷抽象動作的執(zhí)行。如在房間內(nèi)導航的任務中，把agent從房間門入口進入到房間里這個動作序列建模成一個抽象動作，當agent執(zhí)行這個抽象動作到剛剛準備踏入房間的那一瞬間，門突然關(guān)閉了，根據(jù)傳統(tǒng)的SMDP中抽象動作的定義，此時抽象動作不應該終止，而應該繼續(xù)執(zhí)行，因為抽象動作的終止條件還不滿足，而這就與門已經(jīng)處于關(guān)閉狀態(tài)形成了矛盾，導致agent的執(zhí)行效率降低甚至失效。如果采用可中斷Option，就可以解決這一問題。

3.2 可中斷Macro-Q算法

傳統(tǒng)的強化算法agent通過與環(huán)境反復交互的方式來學習值函數(shù)和策略，但是隨著問題規(guī)模的擴大，agent就需要大量的時間和經(jīng)驗來與環(huán)境進行交互以獲得好的策略。使用分層強化學習方法，應用抽象動作能在一定程度上減少對環(huán)境的探索，從而加快算法收斂和保證算法學習前期性能的穩(wěn)定性。經(jīng)典的SMDP方法把抽象動作看作一個不可拆分的整體，一旦抽象動作開始執(zhí)行，就必須執(zhí)行到抽象動作終止，不能中途結(jié)束。事實上，這種方式會面臨以下2個主要問題：首先，在動態(tài)的環(huán)境下，往往在抽象動作還沒結(jié)束時，抽象動作就執(zhí)行不下去，導致算法效果很差；其次，在抽象動作執(zhí)行的過程中，在某些狀態(tài)選擇其他的抽象動作會獲得更好的性能。針對這2種可能出現(xiàn)的情況，本文提出了一種可中斷Macro-Q(IMQ, interrupting Macro-Q)算法。

算法1 可中斷Macro-Q算法

輸入：折扣因子, 學習率, Option集合O

輸出：值函數(shù)

1) 初始化值函數(shù)和隊列

2) for 每個情節(jié) do

3) 以s作為起始狀態(tài)，初始化s

4) repeat

5) 根據(jù)策略從O中選擇一個Option=<,,>

6) 執(zhí)行

7) 根據(jù)(s)選擇動作

11) 將s,,保存到隊列中

12) if(’)=1 or=then

13) forindo

14) 以批量方式更新Q(,)

16) end if

17) else ifV()>Q(,)

18) forindo

19) 以批量方式更新Q(,)

20) 選擇一個新的Option’

22) 終止執(zhí)行

24) return

算法1是一種基于中斷思想的無模型學習算法，能夠很好地解決環(huán)境變化情況下，抽象動作無法整體使用的問題。

3.3 在線更新的Macro-Q算法

在線學習方法延伸模型的學習過程。在使用過程中，新數(shù)據(jù)的到來會引發(fā)模型的更新。而這種學習方法的一個直接負面影響是采樣代價較高[19]。作為一種在線式的學習算法，經(jīng)典的Macro-Q就需要花費完成采樣。本文改進了Macro-Q算法，采用在線式in-place更新方法，在agent對抽象動作值更新的同時，對執(zhí)行過的元動作也進行更新，如在線更新的Macro-Q(MQIU, macro-Q with in-place updating)算法所示。Macro-Q算法加快了值更新速率，從而加快算法的收斂速度。

算法2 在線更新的Macro-Q算法

輸入：折扣因子, 學習率, Options 集合O

輸出：值函數(shù)

1) 初始化值函數(shù)和隊列

2) for 每個情節(jié) do

3) 以s作為起始狀態(tài)，初始化s

4) repeat

5) 根據(jù)策略從O中選擇一個Option= <,,>

6) 執(zhí)行

7) 根據(jù)(s)選擇動作

11) 將s,,保存到隊列中

13) forindo

16) end if

18) 終止執(zhí)行

20) return

3.4 算法分析

4 仿真實驗

本文在格子世界實驗的基礎(chǔ)上，模擬動態(tài)和靜態(tài)的環(huán)境進行仿真實驗。通過與Q-learning做實驗對比并給出實驗結(jié)果來仿真驗證IMQ的可行性和有效性。在仿真實驗中，agent使用-greedy進行探索，初始探索概率，學習率，值都初始化為0，也可以被隨機初始化。根據(jù)問題規(guī)模的不同，將提供不同的抽象動作集合。

4.1 動態(tài)環(huán)境的描述

到目前為止，強化學習大多數(shù)的研究都用于解決一些簡單的學習任務，如房間導航問題、平衡桿問題、直流電機問題、過山車問題等。但是這些問題大多都是設定為靜態(tài)環(huán)境的。如房間導航問題中，只有固定的墻壁或障礙物。然而，在實際的應用環(huán)境往往是未知的或者會發(fā)生變化。相應地，房間導航問題的設定中，障礙物應該是隨機出現(xiàn)的，而且出現(xiàn)的位置也應該是隨機的。本文的一個目標就是在動態(tài)的、不斷變化的環(huán)境中找到最優(yōu)策略。

在圖1(a)所示的動態(tài)格子世界的仿真實驗中，共有21×21個網(wǎng)格，標記為“S”的格子表示agent的出發(fā)點，標記為“G”的格子表示agent的目標終點，標記為“O”的格子表示障礙物。動態(tài)格子世界環(huán)境是會動態(tài)變化的，包括2種變化的對象：agent和障礙物的位置。對比圖1(a)和圖1(b)可以發(fā)現(xiàn)，在不同的時間，障礙物的位置是不一樣的。

4.2 MQIU在格子世界中的性能

為了衡量MQIU的性能，本文在仿真實驗環(huán)境下同時實現(xiàn)了Macro-Q、Q-learning和MQIU。實驗環(huán)境為一個11×11的格子世界，如圖2(a)所示，agent的出發(fā)點設在左下方，用“S”表示，目標點設在格子頂部的中間，用“G”表示。Agent的任務是從“S”出發(fā)，以最快的方式到達目標點“G”，agent所能采取的元動作為上、下、左和右。在算法Macro-Q和MQUI中，agent所能采取的動作除了上、下、左、右這4個元動作外，對每個狀態(tài)還有4個可選的抽象動作，分別沿4個方向移動，直到碰到墻為止。

從圖2(b)可以看出，MQIU和Macro-Q比Q-learning收斂更快，而且在整個學習過程中MQIU和Macro-Q都保持了很好的性能，平均每個情節(jié)步數(shù)維持在50步內(nèi)。對比Macro-Q可以看出，MQIU在前15個情節(jié)稍差，但是在第15個情節(jié)之后，MQIU算法的性能就好于Macro-Q。產(chǎn)生這種現(xiàn)象的原因是MQIU在對抽象動作更新的同時更新了元動作的值，從而會加快值的收斂速度。

4.3 IMQ在4房間靜態(tài)格子世界中的性能

本文首先對IMQ在靜態(tài)環(huán)境下的表現(xiàn)做了深入的說明，如圖3所示。4個房間靜態(tài)格子世界實驗如圖3(a)所示，其中，“S”代表出發(fā)點，“G”代表目標點。Agent從“S”出發(fā)，經(jīng)過房間之間的通道到達“G”，則一個情節(jié)結(jié)束。為了更好地說明算法的性能，IMQ和Macro-Q所使用的抽象動作是完全一樣的。實驗中的抽象動作設為每個房間內(nèi)2個，一共8個，每個抽象動作能夠把agent從房內(nèi)任意一點帶到房間的出口處。

從圖3(b)中可以看出，在4個房間格子世界中，IMQ和Macro-Q的算法性能比Q-learning好很多。Macro-Q性能較為穩(wěn)定，在整個學習的過程中一直保持很低的學習步數(shù)，然而其收斂速度和Q-learning一樣，在500個情節(jié)后收斂。IMQ注重探索，在前50個情節(jié)性能比Q-learning好，略差于Macro-Q，但是IMQ收斂效果很好，在200個情節(jié)的時候就達到了收斂，并且一直保持很穩(wěn)定。

4.4 IMQ在4個房間動態(tài)格子世界中的性能

4個房間動態(tài)格子世界實驗如圖4(a)所示。由于在這個實驗中，環(huán)境被設置為動態(tài)變化的，因此更能檢驗算法的性能。目標狀態(tài)“G”被放置在右下角的房間，起始狀態(tài)“S”被放置在左上角房間的角落里。每個情節(jié)會隨機初始化25個障礙物“O”，用來表示隨機的環(huán)境。元動作是4個方向的動作：上、下、左和右。Agent在貪心動作（元動作或者抽象動作）的選擇概率為，其他方向上，元動作或者抽象動作的選擇概率為。Agent每走一步的獎賞都是?1，到達目標點的獎賞是0。由于本文關(guān)注的重點是抽象動作在動態(tài)環(huán)境中的應用，因此這里的抽象動作是預先定義好的。實驗中對比了IMQ和Q-learning，沒有對比Macro-Q以及基于規(guī)劃的中斷方法，是因為在動態(tài)環(huán)境下，這2種算法性能都很差。Macro-Q沒有引入中斷機制，導致如果抽象動作的執(zhí)行過程被破壞，那么將無法繼續(xù)按照抽象動作的內(nèi)部策略繼續(xù)執(zhí)行。而基于規(guī)劃的中斷方法用于在線的算法中并不是很合理，而且需要模型，因此這里沒有對比這2種算法。

圖4(b)顯示了在100次重復實驗的基礎(chǔ)上，agent從起始狀態(tài)到達目標狀態(tài)的平均步數(shù)，對比了IMQ和Q-learning在動態(tài)的格子世界中的性能。從圖中可以看出帶有不同抽象動作集合的3種IMQ算法無論是在收斂速度還是在學習時的表現(xiàn)上均好于Q-learning。其中，IMQ with integrated Option在性能上略差于另外2個IMQ算法，IMQ with good Option的性能總體上和IMQ with key Option相當；但是從圖4(c)可以看出，IMQ with key Option僅在前50個情節(jié)略差于IMQ with good Option，從長期學習來看，IMQ with key Option學習效率更高，收斂更快。仿真實驗證明了算法在動態(tài)環(huán)境下的有效性。為了更精確地說明幾種算法的性能對比，在表1中給出了4個房間動態(tài)格子世界中各算法性能的對比數(shù)據(jù)。

表1 4個房間實驗中，不同抽象動作集IMQ和Q-learning的對比實驗結(jié)果數(shù)據(jù)

4.5 IMQ在6個房間動態(tài)格子世界中的性能

作為IMQ的第3個實驗，在更大規(guī)模的環(huán)境下進行實驗驗證。本文使用6個房間的動態(tài)格子世界來進行仿真實驗。Agent的任務和前面描述的基本一樣，從起始點狀態(tài)“S”走到目標狀態(tài)“G”。實驗的環(huán)境如圖5(a)所示，其中，起始狀態(tài)“S”靠近左上角，目標狀態(tài)靠近右邊。隨機環(huán)境以及元動作的設定和前面介紹的一樣，隨機生成25個障礙物，用“O”表示。提供的抽象動作和前一節(jié)介紹的一樣，但是由于房間的增多，這里提供的抽象動作的數(shù)量也會相應的變化。

圖5(b)顯示了在100次重復實驗的基礎(chǔ)上，agent從起始狀態(tài)到達目標狀態(tài)的平均步數(shù)，這個圖與4個房間實驗中的圖相比，區(qū)別在于狀態(tài)的增多、環(huán)境的復雜度更高，導致agent在學習的前期到達目標點所需的步數(shù)的增加，同時收斂速度也有所減緩。從圖5可以看出，隨著環(huán)境規(guī)模的增大，各算法間的區(qū)別更加明顯。實驗圖5(b)表明，3種IMQ算法表現(xiàn)均優(yōu)于Q-learning，其中，IMQ with key Option達到收斂所需的總步數(shù)最少，情節(jié)數(shù)也最少，這說明，關(guān)鍵的抽象動作能夠更有效地加快agent的學習效率。

5 結(jié)束語

本文的工作主要包括以下幾個方面。首先，針對傳統(tǒng)SMDP方法不能解決動態(tài)環(huán)境下的學習和控制問題，本文提出一種在線學習的使用可中斷動作抽象的算法——IMQ。借助于分層強化學習的方法，IMQ算法能夠有效解決大數(shù)據(jù)環(huán)境下一般強化學習算法由于時間復雜度過高而不能解決的問題。相比于離線算法，IMQ算法能夠在線地進行學習和采樣，從而在加快學習效率的同時又保證了算法的性能。實驗結(jié)果表明，IMQ算法比Q-learning算法和Macro-Q算法具有更快的收斂速度。

其次，針對Macro-Q算法樣本利用率不高的問題，本文提出了一種基于同步替代更新的算法——MQIU算法。在算法中，對抽象動作的值函數(shù)進行更新的同時，也更新元動作的值函數(shù)。實驗結(jié)果表明，MQIU算法較Macro-Q效果略好，收斂速度上略快。

第三，針對傳統(tǒng)的抽象動作不能很好地解決動態(tài)環(huán)境的問題，本文將中斷的方式引入抽象動作的概念中，提出了中斷式動作抽象的概念，使之能很好地適應環(huán)境的變化，并在此基礎(chǔ)上提出了一種基于中斷動作抽象的無模型學習算法。實驗結(jié)果表明，在動態(tài)的環(huán)境下，適當?shù)乩贸橄髣幼髂軌蚣涌烊蝿盏那蠼?，并且有助于agent在學習的過程中保持性能的穩(wěn)定。

然而，在本文中的抽象動作是預先定義好的，如何快速有效地自動發(fā)現(xiàn)合適的抽象動作來加快長期學習agent的學習效率，是將要研究的一個重要內(nèi)容。另外，在動態(tài)的環(huán)境下，如何充分利用樣本的模型學習以及如何將抽象動作用于多任務、多agent協(xié)作也是主要的一項工作。

[1] OTTERLO M V, WIERING M. Reinforcement learning and Markov decision processes[J]. Adaptation Learning & Optimization, 2012, 206(4):3-42.

[2] VAN H H. Reinforcement learning: state of the art[M]. Berlin: Springer, 2007.

[3] 沈晶, 顧國昌, 劉海波. 未知動態(tài)環(huán)境中基于分層強化學習的移動機器人路徑規(guī)劃[J]. 機器人, 2006, 28(5):544-547. SHEN J, GU G C, LIU H B. Mobile robot path planning based on hierarchical reinforcement learning in unknown dynamic environment[J]. ROBOT, 2006, 28(5): 544-547.

[4] 劉全, 閆其粹, 伏玉琛, 等. 一種基于啟發(fā)式獎賞函數(shù)的分層強化學習方法[J]. 計算機研究與發(fā)展, 2011, 48(12): 2352-2358. LIU Q, YAN Q C, FU Y C, et al. A hierarchical reinforcement learning method based on heuristic reward function[J]. Journal of Computer Research and Development, 2011, 48(12): 2352-2358.

[5] 陳興國, 高陽, 范順國, 等. 基于核方法的連續(xù)動作Actor-Critic學習[J]. 模式識別與人工智能, 2014(2): 103-110. CHEN X G, GAO Y, FAN S G, et al. Kernel-based continuous-action actor-critic learning[J]. Pattern Recognition and Artificial Intelligence, 2014(2):103-110.

[6] 朱斐, 劉全, 傅啟明, 等. 一種用于連續(xù)動作空間的最小二乘行動者-評論家方法[J]. 計算機研究與發(fā)展, 2014, 51(3): 548-558 ZHU F, LIU Q, FU Q M, et al. A least square actor-critic approach for continuous action space[J]. Journal of Computer Research and Development, 2014, 51(3): 548-558.

[7] 唐昊, 張曉艷, 韓江洪, 等. 基于連續(xù)時間半馬爾可夫決策過程的Option算法[J]. 計算機學報, 2014(9): 2027-2037. TANG H, ZHANG X Y, HAN J H, et al. Option algorithm based on continuous-time semi-Markov decision process[J]. Chinese Journal of Computers, 2014(9): 2027-2037.

[8] SUTTON R S, PRECUP D, SINGH S. Between MDPs and semi-MDPs: a framework for temporal abstraction in reinforcement learning[J]. Artificial Intelligence, 1999, 112(1): 181-211.

[9] MCGOVERN A, BARTO A G. Automatic discovery of subgoals in reinforcement learning using diverse density[J]. Computer Science Department Faculty Publication Series, 2001(8):361-368.

[10] ?IM?EK ?, WOLFE A P, BARTO A G. Identifying useful subgoals in reinforcement learning by local graph partitioning[C]//The 22nd International Conference on Machine Learning. ACM, c2005: 816-823.

[11] ?IM?EK ?, BARTO A G. Using relative novelty to identify useful temporal abstractions in reinforcement learning[C]//The Twenty-first International Conference on Machine Learning. ACM, c2004: 751-758.

[12] CHAGANTY A T, GAUR P, RAVINDRAN B. Learning in a small world[C]//The 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems. c2012: 391-397.

[13] SUTTON R S, SINGH S, PRECUP D, et al. Improved switching among temporally abstract actions[J]. Advances in Neural Information Processing Systems, 1999: 1066-1072.

[14] CASTRO P S, PRECUP D. Automatic construction of temporally extended actions for mdps using bisimulation metrics[C]//European Conference on Recent Advances in Reinforcement Learning. Springer-Verlag, c2011: 140-152.

[15] 何清, 李寧, 羅文娟, 等. 大數(shù)據(jù)下的機器學習算法綜述[J]. 模式識別與人工智能, 2014, 27(4): 327-336.

HE Q, LI N, LUO W J, et al. A survey of machine learning algorithms for big data[J]. Pattern Recognition and Artificial Intelligence, 2014,27(4): 327-336.

[16] SUTTON R S, PRECUP D, SINGH S P. Intra-option learning about temporally abstract actions[C]//ICML. c1998, 98: 556-564.

[17] 石川, 史忠植, 王茂光. 基于路徑匹配的在線分層強化學習方法[J]. 計算機研究與發(fā)展, 2008, 45(9): 1470-1476 SHI C, SHI Z Z, WANG M G. Online hierarchical reinforcement learning based on path-matching[J]. Journal of Computer Research and Development, 2008, 45(9): 1470-1476.

[18] BOTVINICK M M. Hierarchical reinforcement learning and decision making [J]. Current Opinion in Neurobiology, 2012, 22(6): 956-962.

[19] 王愛平, 萬國偉, 程志全, 等. 支持在線學習的增量式極端隨機森林分類器[J]. 軟件學報, 2011, 22(9):2059-2074. WANG A P, WAN G W, CHENG Z Q, et al. Incremental learning extremely random forest classifier for online learning[J], Journal of Software, 2011, 22(9):2059-2074.

Online hierarchical reinforcement learning based on interrupting Option

ZHU Fei1,2, XU Zhi-peng1, LIU Quan1,2, FU Yu-chen1, WANG Hui1

(1. School of Computer Science and Technology, Soochow University, Suzhou 215006, China; 2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China)

Aiming at dealing with volume of big data, an on-line updating algorithm, named by Macro-Q with in-place updating (MQIU), which was based on Macro-Q algorithm and takes advantage of in-place updating approach, was proposed. The MQIU algorithm updates both the value function of abstract action and the value function of primitive action, and hence speeds up the convergence rate. By introducing the interruption mechanism, a model-free interrupting Macro-Q Option learning algorithm(IMQ), which was based on hierarchical reinforcement learning, was also introduced to order to handle the variability which was hard to process by the conventional Markov decision process model and abstract action so that IMQ was able to learn and improve control strategies in a dynamic environment. Simulations verify the 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 performance.

big data, reinforcement learning, hierarchical reinforcement learning, Option, online learning

TP181

A

10.11959/j.issn.1000-436x.2016117

2015-04-03；

2016-04-12

伏玉琛，yuchenfu@suda.edu.cn

國家自然科學基金資助項目（No.61303108, No.61373094, No.61272005, No.61472262）；江蘇省高校自然科學研究基金資助項目（No.13KJB520020）；吉林大學符號計算與知識工程教育部重點實驗室基金資助項目（No.93K172014K04）；蘇州市應用基礎(chǔ)研究計劃基金資助項目（No.SYG201422）；蘇州大學高校省級重點實驗室基金資助項目（No.KJS1524）；中國國家留學基金資助項目（No.201606920013）

The National Natural Science Foundation of China (No.61303108, No.61373094, No.61272005, No.61472262), The High School Natural Foundation of Jiangsu Province (No.13KJB520020), The Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education of Jilin University(No.93K172014K04), Suzhou Industrial Application of Basic Research Program (No.SYG201422), Provincial Key Laboratory for Computer Information Processing Technology of Soochow University (No.KJS1524), The China Scholarship Council Project (No.201606920013)

朱斐（1978-），男，江蘇蘇州人，博士，蘇州大學副教授，主要研究方向為機器學習、人工智能、生物信息學等。

許志鵬（1991-），男，湖北荊州人，蘇州大學碩士生，主要研究方向為強化學習、人工智能等。

劉全（1969-），男，內(nèi)蒙古牙克石人，博士后，蘇州大學教授、博士生導師，主要研究方向為多強化學習、人工智能、自動推理等。

伏玉?。?968-），男，江蘇徐州人，博士，蘇州大學教授、碩士生導師，主要研究方向為強化學習、人工智能等。

王輝（1968-），男，陜西西安人，蘇州大學講師，主要研究方向為強化學習、人工智能等。