基于可中斷Option的在線分層強化學(xué)習(xí)方法

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

?

基于可中斷Option的在線分層強化學(xué)習(xí)方法

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

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

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

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

1 引言

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

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

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

2 相關(guān)工作

2.1 強化學(xué)習(xí)

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

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

2.2 抽象動作

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

(2)

2.3 半馬爾可夫決策過程

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

(4)

對應(yīng)的動作值函數(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)策略。而且，標(biāo)準(zhǔn)的SMDP理論能夠保證這樣的過程能夠收斂。

3 算法描述

3.1 可中斷Option

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

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

3.2 可中斷Macro-Q算法

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

算法1 可中斷Macro-Q算法

輸入：折扣因子, 學(xué)習(xí)率, 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是一種基于中斷思想的無模型學(xué)習(xí)算法，能夠很好地解決環(huán)境變化情況下，抽象動作無法整體使用的問題。

3.3 在線更新的Macro-Q算法

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

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

輸入：折扣因子, 學(xué)習(xí)率, 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進行探索，初始探索概率，學(xué)習(xí)率，值都初始化為0，也可以被隨機初始化。根據(jù)問題規(guī)模的不同，將提供不同的抽象動作集合。

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

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

在圖1(a)所示的動態(tài)格子世界的仿真實驗中，共有21×21個網(wǎng)格，標(biāo)記為“S”的格子表示agent的出發(fā)點，標(biāo)記為“G”的格子表示agent的目標(biāo)終點，標(biāo)記為“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ā)點設(shè)在左下方，用“S”表示，目標(biāo)點設(shè)在格子頂部的中間，用“G”表示。Agent的任務(wù)是從“S”出發(fā)，以最快的方式到達目標(biāo)點“G”，agent所能采取的元動作為上、下、左和右。在算法Macro-Q和MQUI中，agent所能采取的動作除了上、下、左、右這4個元動作外，對每個狀態(tài)還有4個可選的抽象動作，分別沿4個方向移動，直到碰到墻為止。

從圖2(b)可以看出，MQIU和Macro-Q比Q-learning收斂更快，而且在整個學(xué)習(xí)過程中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”代表目標(biāo)點。Agent從“S”出發(fā)，經(jīng)過房間之間的通道到達“G”，則一個情節(jié)結(jié)束。為了更好地說明算法的性能，IMQ和Macro-Q所使用的抽象動作是完全一樣的。實驗中的抽象動作設(shè)為每個房間內(nèi)2個，一共8個，每個抽象動作能夠把agent從房內(nèi)任意一點帶到房間的出口處。

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

圖4(b)顯示了在100次重復(fù)實驗的基礎(chǔ)上，agent從起始狀態(tài)到達目標(biāo)狀態(tài)的平均步數(shù)，對比了IMQ和Q-learning在動態(tài)的格子世界中的性能。從圖中可以看出帶有不同抽象動作集合的3種IMQ算法無論是在收斂速度還是在學(xué)習(xí)時的表現(xiàn)上均好于Q-learning。其中，IMQ with integrated Option在性能上略差于另外2個IMQ算法，IMQ with good Option的性能總體上和IMQ with key Option相當(dāng)；但是從圖4(c)可以看出，IMQ with key Option僅在前50個情節(jié)略差于IMQ with good Option，從長期學(xué)習(xí)來看，IMQ with key Option學(xué)習(xí)效率更高，收斂更快。仿真實驗證明了算法在動態(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的任務(wù)和前面描述的基本一樣，從起始點狀態(tài)“S”走到目標(biāo)狀態(tài)“G”。實驗的環(huán)境如圖5(a)所示，其中，起始狀態(tài)“S”靠近左上角，目標(biāo)狀態(tài)靠近右邊。隨機環(huán)境以及元動作的設(shè)定和前面介紹的一樣，隨機生成25個障礙物，用“O”表示。提供的抽象動作和前一節(jié)介紹的一樣，但是由于房間的增多，這里提供的抽象動作的數(shù)量也會相應(yīng)的變化。

圖5(b)顯示了在100次重復(fù)實驗的基礎(chǔ)上，agent從起始狀態(tài)到達目標(biāo)狀態(tài)的平均步數(shù)，這個圖與4個房間實驗中的圖相比，區(qū)別在于狀態(tài)的增多、環(huán)境的復(fù)雜度更高，導(dǎo)致agent在學(xué)習(xí)的前期到達目標(biāo)點所需的步數(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的學(xué)習(xí)效率。

5 結(jié)束語

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

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

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

然而，在本文中的抽象動作是預(yù)先定義好的，如何快速有效地自動發(fā)現(xiàn)合適的抽象動作來加快長期學(xué)習(xí)agent的學(xué)習(xí)效率，是將要研究的一個重要內(nèi)容。另外，在動態(tài)的環(huán)境下，如何充分利用樣本的模型學(xué)習(xí)以及如何將抽象動作用于多任務(wù)、多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)境中基于分層強化學(xué)習(xí)的移動機器人路徑規(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ù)的分層強化學(xué)習(xí)方法[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學(xué)習(xí)[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]. 計算機學(xué)報, 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ù)下的機器學(xué)習(xí)算法綜述[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] 石川, 史忠植, 王茂光. 基于路徑匹配的在線分層強化學(xué)習(xí)方法[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] 王愛平, 萬國偉, 程志全, 等. 支持在線學(xué)習(xí)的增量式極端隨機森林分類器[J]. 軟件學(xué)報, 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

國家自然科學(xué)基金資助項目（No.61303108, No.61373094, No.61272005, No.61472262）；江蘇省高校自然科學(xué)研究基金資助項目（No.13KJB520020）；吉林大學(xué)符號計算與知識工程教育部重點實驗室基金資助項目（No.93K172014K04）；蘇州市應(yīng)用基礎(chǔ)研究計劃基金資助項目（No.SYG201422）；蘇州大學(xué)高校省級重點實驗室基金資助項目（No.KJS1524）；中國國家留學(xué)基金資助項目（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-），男，江蘇蘇州人，博士，蘇州大學(xué)副教授，主要研究方向為機器學(xué)習(xí)、人工智能、生物信息學(xué)等。

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

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

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

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