王 奇，秦 進(jìn)

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽 550025)

基于動(dòng)作空間劃分的MAXQ自動(dòng)分層方法

王 奇*，秦 進(jìn)

(貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴陽 550025)

(*通信作者電子郵箱wangqi_92@sina.com)

針對分層強(qiáng)化學(xué)習(xí)需要人工給出層次結(jié)構(gòu)這一問題，同時(shí)考慮到基于狀態(tài)空間的自動(dòng)分層方法在環(huán)境狀態(tài)中沒有明顯子目標(biāo)時(shí)分層效果并不理想的情況，提出一種基于動(dòng)作空間的自動(dòng)構(gòu)造層次結(jié)構(gòu)方法。首先，根據(jù)動(dòng)作影響的狀態(tài)分量將動(dòng)作集合劃分為多個(gè)不相交的子集；然后，分析Agent在不同狀態(tài)下的可用動(dòng)作,并識別瓶頸動(dòng)作；最后，由瓶頸動(dòng)作與執(zhí)行次序確定動(dòng)作子集之間的上下層關(guān)系,并構(gòu)造層次結(jié)構(gòu)。此外，對MAXQ方法中子任務(wù)的終止條件進(jìn)行修改，使所提算法構(gòu)造的層次結(jié)構(gòu)可以通過MAXQ方法找到最優(yōu)策略。實(shí)驗(yàn)結(jié)果表明,所提算法可以自動(dòng)構(gòu)造層次結(jié)構(gòu)，而不會受環(huán)境變化的干擾。與Q學(xué)習(xí)、Sarsa算法相比，MAXQ方法根據(jù)該結(jié)構(gòu)得到最優(yōu)策略的時(shí)間更短，獲得回報(bào)更高。驗(yàn)證了所提算法能夠有效地自動(dòng)構(gòu)造MAXQ層次結(jié)構(gòu)，并使尋找最優(yōu)策略更加高效。

強(qiáng)化學(xué)習(xí)；分層強(qiáng)化學(xué)習(xí)；自動(dòng)分層方法；馬爾可夫決策過程；子任務(wù)

0 引言

強(qiáng)化學(xué)習(xí)一般用來解決這樣的問題：一個(gè)可以感知周圍環(huán)境的智能體Agent，通過學(xué)習(xí)來選擇要達(dá)到目標(biāo)的最佳動(dòng)作。通過Agent與環(huán)境的交互和不斷試錯(cuò)，最終得到完成目標(biāo)的最佳策略[1]。強(qiáng)化學(xué)習(xí)在人工智能領(lǐng)域有著廣泛的應(yīng)用，被認(rèn)為是設(shè)計(jì)智能系統(tǒng)的核心技術(shù)之一[2]。近年來提出的深度強(qiáng)化學(xué)習(xí)，即是將強(qiáng)化學(xué)習(xí)的決策能力與深度學(xué)習(xí)的感知能力相結(jié)合，為復(fù)雜系統(tǒng)的感知決策問題提供了新的思路，并在棋類博弈游戲中取得了顯著的成果[3]。但是，強(qiáng)化學(xué)習(xí)方法一直受到“維數(shù)災(zāi)難”的困擾，即學(xué)習(xí)參數(shù)的個(gè)數(shù)隨著狀態(tài)和動(dòng)作維數(shù)的增加呈指數(shù)級增長。為了減小“維數(shù)災(zāi)難”對強(qiáng)化學(xué)習(xí)的影響，研究者們將分層、抽象等機(jī)制引入強(qiáng)化學(xué)習(xí)中, 其基本思想是對狀態(tài)空間進(jìn)行降維，將復(fù)雜的強(qiáng)化學(xué)習(xí)問題分解為多個(gè)具有層次關(guān)系的子任務(wù)，并在較小的低維空間中逐步解決子任務(wù)。

建立在合理的抽象基礎(chǔ)上的分層強(qiáng)化學(xué)習(xí)可以顯著減小存儲空間和計(jì)算量，提高學(xué)習(xí)速度。目前，主要的分層強(qiáng)化學(xué)習(xí)方法有Option算法[4]、MAXQ算法[5]、層次抽象機(jī)(Hierarchies of Abstract Machine, HAM)算法[6]。但是，這些典型的算法都有一個(gè)同樣的問題，就是均需要利用先驗(yàn)知識來構(gòu)造任務(wù)的層次結(jié)構(gòu)。而在實(shí)際應(yīng)用中，學(xué)習(xí)環(huán)境和學(xué)習(xí)任務(wù)的層次結(jié)構(gòu)有時(shí)是未知的，如果依靠專家知識來劃分任務(wù)層次，會花費(fèi)巨大的人力，也無法滿足在動(dòng)態(tài)未知環(huán)境下的應(yīng)用要求。因此，國內(nèi)外的研究者都致力于解決分層強(qiáng)化學(xué)習(xí)的自動(dòng)分層問題，并且提出了各自的方法。Hengst[7]提出的HEXQ方法按照狀態(tài)變量的改變次數(shù)進(jìn)行排序，并認(rèn)為經(jīng)常改變的狀態(tài)變量與低層的子任務(wù)有關(guān)，改變次數(shù)少的變量與高層子任務(wù)有關(guān)。McGovern[8]和 Stolle[9]則通過尋找瓶頸狀態(tài)來劃分子任務(wù)。Mehta等[10]提出HI-MAT(Hierarchy Induction via Models And Trajectories)方法，利用動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)(Dynamic Bayesian Network, DBN)和一條已知的成功軌跡，通過分析動(dòng)作間的因果關(guān)系，構(gòu)建出一條帶因果注釋軌跡(Causally Annotated Trajectory, CAT)，并在CAT上劃分出子任務(wù)的層次。石川等[11]提出利用單向值識別出瓶頸狀態(tài)，以此構(gòu)造Option，并應(yīng)用Option算法尋找最佳策略；但是，基于狀態(tài)進(jìn)行自動(dòng)分層的方法，在狀態(tài)空間沒有明顯的瓶頸狀態(tài)時(shí)或者狀態(tài)空間產(chǎn)生變化時(shí)，效果并不理想。此外，沈晶[12]提出OMQ算法，在MAXQ算法的學(xué)習(xí)過程中針對粗粒度的子任務(wù)自動(dòng)構(gòu)造Option，并將Option作為子任務(wù)插入到MAXQ任務(wù)圖中，使任務(wù)圖細(xì)化，提升了算法的學(xué)習(xí)效果；不過對于初始的任務(wù)圖，仍然需要根據(jù)先驗(yàn)知識人工構(gòu)造。

本文在已有研究的基礎(chǔ)上，提出一種適用于MAXQ學(xué)習(xí)方法的自動(dòng)分層算法,該算法根據(jù)不同動(dòng)作執(zhí)行次數(shù)和所影響狀態(tài)之間的差異，自動(dòng)構(gòu)造出任務(wù)圖; 同時(shí)為了使用MAXQ算法對該任務(wù)圖進(jìn)行學(xué)習(xí)，提出了一種新的判斷子任務(wù)是否結(jié)束的方法。

1 馬爾可夫決策過程與分層強(qiáng)化學(xué)習(xí)

1.1 馬爾可夫決策過程

一個(gè)強(qiáng)化學(xué)習(xí)系統(tǒng)的基本框架由環(huán)境和智能體Agent兩部分組成，Agent與環(huán)境進(jìn)行交互。Agent感知到環(huán)境的當(dāng)前狀態(tài)，然后通過一個(gè)策略選擇合適的動(dòng)作去執(zhí)行。環(huán)境對執(zhí)行的動(dòng)作作出響應(yīng)，更新狀態(tài)并回饋給Agent一個(gè)獎(jiǎng)勵(lì)。對于Agent來說，主要目標(biāo)是努力地使自己在與環(huán)境的交互中積累盡可能多的獎(jiǎng)勵(lì)。在強(qiáng)化學(xué)習(xí)的研究中，一般假設(shè)學(xué)習(xí)任務(wù)滿足馬爾可夫性，將其形式化為馬爾可夫決策過程(Markov Decision Process, MDP)[13]，一個(gè)MDP可以表示為一個(gè)四元組〈S,A,P,R〉。其中：S表示環(huán)境狀態(tài)的集合；A表示Agent可以執(zhí)行的動(dòng)作的集合；P表示狀態(tài)轉(zhuǎn)移概率，即Agent執(zhí)行動(dòng)作a后，環(huán)境狀態(tài)從s轉(zhuǎn)移到另一個(gè)狀態(tài)s′的概率，記為P(s′|s,a)；R為回報(bào)函數(shù)，在某個(gè)狀態(tài)s下，當(dāng)Agent執(zhí)行一個(gè)動(dòng)作a后，使得環(huán)境狀態(tài)發(fā)生改變，此時(shí)Agent會從環(huán)境得到一個(gè)回報(bào)值，記為R(s,a)。此外，策略用π表示，MDP中的策略可以視為一個(gè)從狀態(tài)空間到動(dòng)作空間的映射，在環(huán)境狀態(tài)s下，由策略π決定執(zhí)行的動(dòng)作a，記為a=π(s)。

馬爾可夫決策的一般過程可以描述為：Agent在狀態(tài)s下根據(jù)策略π決定執(zhí)行動(dòng)作a，在完成動(dòng)作a后，環(huán)境狀態(tài)以概率P(s′|s,a)改變?yōu)閟′，Agent得到一個(gè)獎(jiǎng)賞值r=R(s,a)。強(qiáng)化學(xué)習(xí)的目標(biāo)是尋找一個(gè)策略，使Agent在完成目標(biāo)時(shí)所獲得的累積回報(bào)最大。為了確定最優(yōu)策略,通常使用值函數(shù)Vπ(s)表示在狀態(tài)s處執(zhí)行策略π的累積期望回報(bào)。值函數(shù)可以寫為式(1)的形式：

(1)

其中:γ為折扣因子，rt表示t時(shí)刻環(huán)境狀態(tài)改變后Agent所得到的回報(bào)。由于狀態(tài)轉(zhuǎn)移的隨機(jī)性,在狀態(tài)s下，策略π的值函數(shù)可以定義如下：

(2)

(3)

式(3)表示在遵循策略π時(shí)，在狀態(tài)st執(zhí)行動(dòng)作at所得到的期望累積回報(bào)。Q函數(shù)的形式與值函數(shù)類似，同樣也滿足Bellman等式，也就是說存在最優(yōu)策略π*，使得Q值最大。

由于MDP會忽略決策過程的時(shí)間間隔，基于MDP的強(qiáng)化學(xué)習(xí)都假設(shè)動(dòng)作在單個(gè)時(shí)間步完成，因而無法處理需要多個(gè)時(shí)間步完成的動(dòng)作。由于分層強(qiáng)化學(xué)習(xí)會對原始問題進(jìn)行抽象，可執(zhí)行的動(dòng)作會被替換為需要多個(gè)時(shí)間步完成的宏動(dòng)作。為了表示動(dòng)作執(zhí)行的時(shí)間過程，需要引入半馬爾可夫決策過程(Semi-Markov Decision Process, SMDP)[14]。SMDP可以視為MDP一種拓展，圖1展示了MDP與SMDP的區(qū)別。

圖1 SMDP與MDPFig. 1 SMDP and MDP

MDP中離散事件之間只會間隔同樣大小的單個(gè)時(shí)間步，SMDP的事件之間則有不同大小的時(shí)間間隔。根據(jù)時(shí)間類型不同，SMDP又可以分為離散時(shí)間SMDP與連續(xù)時(shí)間SMDP。以離散時(shí)間SMDP為例，時(shí)間間隔為時(shí)間步的整數(shù)倍，用N表示時(shí)間步的數(shù)量，在SMDP中值函數(shù)與Q函數(shù)可以寫為如下形式：

(4)

(5)

1.2 分層強(qiáng)化學(xué)習(xí)

分層強(qiáng)化學(xué)習(xí)對普通的強(qiáng)化學(xué)習(xí)進(jìn)行抽象處理，常用的抽象方法可以分為狀態(tài)抽象[15]、時(shí)態(tài)抽象[4]和狀態(tài)空間分解[16]三類。狀態(tài)抽象方法是對高維的狀態(tài)空間，根據(jù)所要達(dá)到的目標(biāo)，忽略與當(dāng)前問題無關(guān)的狀態(tài)分量，使原始狀態(tài)空間縮小。時(shí)態(tài)抽象方法將單次執(zhí)行的基本動(dòng)作拓展為需要多個(gè)時(shí)間步執(zhí)行的抽象動(dòng)作，Agent從需要考慮每個(gè)時(shí)間步所執(zhí)行的動(dòng)作轉(zhuǎn)變?yōu)橹恍枰紤]抽象動(dòng)作，在當(dāng)前的抽象動(dòng)作執(zhí)行完后再考慮下一個(gè)執(zhí)行的抽象動(dòng)作，減少了決策次數(shù)。狀態(tài)空間分解是將原始的狀態(tài)空間分解為多個(gè)子空間，Agent在這些子空間中尋找各自的策略，由于子空間規(guī)模較小使得Agent更容易找到最優(yōu)策略。

目前典型的分層強(qiáng)化學(xué)習(xí)方法有Option、HAM、MAXQ三種。Option方法的基本思想是將學(xué)習(xí)任務(wù)抽象為若干Option，每個(gè)Option都是一個(gè)為完成子任務(wù)而定義在狀態(tài)空間上的動(dòng)作序列。這些Option作為一種抽象動(dòng)作加入到原來的動(dòng)作集中，Option內(nèi)部可以使用普通的強(qiáng)化學(xué)習(xí)方法決定最優(yōu)的動(dòng)作執(zhí)行序列，Agent只需決定執(zhí)行哪一個(gè)Option，簡化了問題復(fù)雜度。HAM方法將一個(gè)MDP過程分解為多個(gè)子任務(wù)，并將子任務(wù)抽象為隨機(jī)有限狀態(tài)機(jī)，每個(gè)隨機(jī)有限狀態(tài)機(jī)都有自己的內(nèi)部狀態(tài)，根據(jù)當(dāng)前隨機(jī)有限狀態(tài)機(jī)所處的內(nèi)部狀態(tài)可以執(zhí)行動(dòng)作、改變內(nèi)部狀態(tài)、調(diào)用別的隨機(jī)有限狀態(tài)機(jī)或者返回調(diào)用自己的隨機(jī)有限狀態(tài)機(jī)。MAXQ方法將原始學(xué)習(xí)任務(wù)M分解為多個(gè)子任務(wù){(diào)M0,M1,M2,M3,…}，策略π也被分解為{π0,π1,π2,π3,…}，其中πi為子任務(wù)Mi的策略。子任務(wù)被分為兩類： 最基本的是原子型子任務(wù)，這類任務(wù)無法再被分解，其內(nèi)部只含有一個(gè)可以被執(zhí)行的基本動(dòng)作，該動(dòng)作屬于原始學(xué)習(xí)任務(wù)的動(dòng)作集合。第二類是復(fù)合型子任務(wù)，其內(nèi)部含有多個(gè)子任務(wù)，這些子任務(wù)可以是復(fù)合型也可以是原子型子任務(wù)。所有的子任務(wù)組成了一個(gè)以M0為根節(jié)點(diǎn)的層次結(jié)構(gòu)，這個(gè)層次結(jié)構(gòu)被稱為任務(wù)圖。在任務(wù)圖中必須先解決下層子任務(wù)，上層子任務(wù)才會被解決，M0完成后整個(gè)學(xué)習(xí)任務(wù)就完成了。因此MAXQ方法需要根據(jù)學(xué)習(xí)到的策略來依次調(diào)用不同的子任務(wù)。本文所描述的自動(dòng)分層方法，在任務(wù)的層次結(jié)構(gòu)建立后，將會使用MAXQ方法學(xué)習(xí)任務(wù)圖得到最優(yōu)策略。

1.3 MAXQ值函數(shù)分解

MAXQ方法的核心是MAXQ值函數(shù)分解，經(jīng)過對值函數(shù)的分解，使得可以通過對子任務(wù)的值函數(shù)進(jìn)行結(jié)合就可以得到完整的值函數(shù)。由前文的介紹，可以知道Q函數(shù)能夠表示期望累積回報(bào)。而為了在Q值函數(shù)中表現(xiàn)出任務(wù)的分層結(jié)構(gòu)，需要對原始的Q函數(shù)進(jìn)行拓展。在MAXQ方法中，用Qπ(i,s,a)表示在進(jìn)行子任務(wù)Mi，環(huán)境狀態(tài)為s時(shí)執(zhí)行了動(dòng)作a，然后遵循策略π直到Mi終止，所得到的期望累積回報(bào)。a可以是一個(gè)基本動(dòng)作，也可以是Mi的一個(gè)子任務(wù)，則Q函數(shù)可以寫為如下形式：

(6)

完成函數(shù)Cπ(i,s,a)的一般形式如下：

(7)

表示在狀態(tài)s時(shí)執(zhí)行動(dòng)作a后完成子任務(wù)Mi所獲得的期望折扣回報(bào)，其中a既可以是一個(gè)原子任務(wù)也可以是一個(gè)復(fù)合任務(wù)。該回報(bào)值從a開始執(zhí)行時(shí)計(jì)算折扣。根據(jù)以上定義，Q函數(shù)可以寫為如下形式：

Qπ(i,s,a)=Vπ(a,s)+Cπ(i,s,a)

(8)

值函數(shù)Vπ(a,s)可以通過式(9)計(jì)算：

(9)

根據(jù)以上描述可以知道，在策略π下，完整的學(xué)習(xí)任務(wù)M可以被分解為多個(gè)子任務(wù)M0,M1,…,Mn，根任務(wù)M0處的值函數(shù)Vπ(0,s)就可以被分解為多個(gè)完成函數(shù)Cπ(i,s,a)，其中i=0,1，…,n。MAXQ值函數(shù)分解的一般形式如下：

Vπ(0,s)=Vπ(am,s)+Cπ(am-1,s,am)+…+Cπ(a1,s,a2)+Cπ(0,s,a1)

(10)

其中a0,a1,a2,…,am表示在任務(wù)圖中根據(jù)策略π，從根任務(wù)到原子任務(wù)的子任務(wù)調(diào)用路徑，圖2是值函數(shù)分解過程的圖形化展示(r1,r2,…,r14表示在時(shí)間點(diǎn)1,2,…,14執(zhí)行基本動(dòng)作獲得的回報(bào)序列)。

圖2 MAXQ值函數(shù)分解Fig. 2 MAXQ decomposition

2 基于動(dòng)作的層次結(jié)構(gòu)劃分方法

2.1 動(dòng)作空間劃分的基本思想

在分層強(qiáng)化學(xué)習(xí)中，很多方法都會對狀態(tài)空間進(jìn)行抽象處理，在這些處理方法中，找出瓶頸狀態(tài)并將其當(dāng)作子目標(biāo)是一種典型的方法，在基于Option的自動(dòng)分層方法中尤為常見。識別子目標(biāo)的常用標(biāo)準(zhǔn)有訪問次數(shù)[17]、訪問次數(shù)落差變化率[18]、單向值[11]等。這些方法在有明顯的可劃分環(huán)境中效果很好，不過在空間較大或者不易劃分的環(huán)境中瓶頸狀態(tài)的識別并不理想。難以達(dá)到劃分學(xué)習(xí)任務(wù)加快學(xué)習(xí)速度的目的，最終的效果也與單純使用Qlearning、Sarsa等方法的效果相近。為了在任何環(huán)境下都可以自動(dòng)劃分出層次結(jié)構(gòu)，本文提出一種不需考慮外部環(huán)境，只通過劃分動(dòng)作空間構(gòu)造分層結(jié)構(gòu)的方法。

在Agent完成目標(biāo)的過程中，環(huán)境狀態(tài)可以視為一個(gè)向量，每一次動(dòng)作的執(zhí)行都會使該向量的某些分量發(fā)生改變。通過記錄每個(gè)動(dòng)作執(zhí)行后，有哪些狀態(tài)變量發(fā)生了改變，就可以將完整的動(dòng)作集劃分為多個(gè)子集。然后利用這些子集來構(gòu)造MAXQ方法中的復(fù)合型子任務(wù)，只要確定了這些子任務(wù)之間的層次結(jié)構(gòu)也就得到了完整的任務(wù)圖。在確定復(fù)合型子任務(wù)之間的上下層關(guān)系時(shí)，遵循的一個(gè)基本規(guī)則是：在完成目標(biāo)過程中，執(zhí)行次數(shù)多的子任務(wù)應(yīng)該在下層，執(zhí)行次數(shù)少的子任務(wù)應(yīng)該在上層。此外，為了構(gòu)造更復(fù)雜的子任務(wù)，需要引入瓶頸動(dòng)作的概念。在完成目標(biāo)的過程中，如果某個(gè)時(shí)刻不執(zhí)行某個(gè)動(dòng)作，整個(gè)任務(wù)就無法進(jìn)行下去或者無法進(jìn)入下一個(gè)階段，那么這個(gè)動(dòng)作就是瓶頸動(dòng)作。根據(jù)瓶頸動(dòng)作的特征，如果在某個(gè)狀態(tài)下只有一個(gè)可以執(zhí)行的動(dòng)作,那就可以認(rèn)定該動(dòng)作是一個(gè)瓶頸動(dòng)作。在完成目標(biāo)的過程中如果記錄每一次動(dòng)作的執(zhí)行，就會發(fā)現(xiàn)動(dòng)作執(zhí)行的軌跡中含有多個(gè)瓶頸動(dòng)作，在相鄰的瓶頸動(dòng)作之間可能會存在多個(gè)普通動(dòng)作。下文中使用b1,b2,…,bi表示瓶頸動(dòng)作，ai,j表示在動(dòng)作軌跡中瓶頸動(dòng)作bi-1后執(zhí)行的第j個(gè)動(dòng)作。動(dòng)作執(zhí)行軌跡的一般形式如下：

a0,1,a0,2,…,a0, j,b1,a1,1,a1,2,…,a1, j,b2,…,ai-1,1,

ai-1,2,…,ai-1, j,bi

將動(dòng)作軌跡中的瓶頸動(dòng)作bi視為子任務(wù)Mi完成的標(biāo)志，那么在前一個(gè)瓶頸動(dòng)作bi-1與bi之間的動(dòng)作ai,j就可以當(dāng)作為了完成Mi而必須先完成的下層子任務(wù)。在構(gòu)造分層結(jié)構(gòu)時(shí)，記錄下瓶頸動(dòng)作之間的動(dòng)作執(zhí)行軌跡(即動(dòng)作a)，以及動(dòng)作a的執(zhí)行次數(shù)fa。由于基本動(dòng)作都已經(jīng)被分組并構(gòu)造為多個(gè)復(fù)合子任務(wù)，那么就可以找到每一個(gè)基本動(dòng)作a在當(dāng)前所屬的子任務(wù)Ma，以及瓶頸動(dòng)作b當(dāng)前所屬的子任務(wù)Mb。對子任務(wù)Mi，假設(shè)Mi有n個(gè)孩子任務(wù)，分別記為m1,m2,…,mn，則子任務(wù)Mi的訪問次數(shù)FMi由式(11)計(jì)算：

FMi=

(11)

根據(jù)執(zhí)行次數(shù)與上下關(guān)系的基本規(guī)則，可以認(rèn)為訪問次數(shù)比Mb高的Ma在任務(wù)圖中位于Mb的上層，反之則位于Mb的下層。由這種上下層關(guān)系，就可以將Ma與Mb合并為一個(gè)新的復(fù)合子任務(wù)。為了減少調(diào)序操作，在構(gòu)造新的復(fù)合子任務(wù)時(shí)，優(yōu)先將Mb和位于Mb下層的Ma合并。當(dāng)所有復(fù)合子任務(wù)都合并在一起時(shí)，完整的任務(wù)圖就完成了。

2.2 自動(dòng)分層算法描述

為了便于描述，在后文中會將子任務(wù)間的隸屬關(guān)系，描述為父任務(wù)與孩子任務(wù)，一個(gè)復(fù)合任務(wù)中最上層的子任務(wù)稱為根任務(wù)。下面給出自動(dòng)分層算法的描述。

輸入 動(dòng)作集A，其中包含Agent可以執(zhí)行的所有基本動(dòng)作。

輸出 根任務(wù)M0，M0及其下屬的所有子任務(wù)構(gòu)成了完整的任務(wù)層次結(jié)構(gòu)。

1)執(zhí)行一個(gè)隨機(jī)的策略πrandom，Agent從起點(diǎn)出發(fā)直到完成任務(wù)目標(biāo)。記錄在整個(gè)過程中每個(gè)基本動(dòng)作執(zhí)行的次數(shù)，記為fa，a∈A。根據(jù)各動(dòng)作所影響的狀態(tài)變量，將A劃分為多個(gè)子集A1,A2,…,An。

2)對于每一個(gè)動(dòng)作子集Ai，如果|Ai|>1，構(gòu)造一個(gè)復(fù)合任務(wù)Mi，Ai中的每個(gè)元素都是Mi下屬的原子任務(wù)；如果|Ai|=1，則只構(gòu)造一個(gè)單獨(dú)的原子任務(wù)。M1,M2,…,Mn組成一個(gè)新的集合TaskSet，TaskSet中包含當(dāng)前所有的子任務(wù)。

3)Agent從起點(diǎn)出發(fā)，依據(jù)πrandom執(zhí)行一個(gè)隨機(jī)動(dòng)作。

4)設(shè)置一個(gè)空列表trail，記錄基本動(dòng)作執(zhí)行的軌跡；設(shè)置兩個(gè)空的集合uppertask、lowertask記錄上下層子任務(wù)。

5)如果當(dāng)前狀態(tài)是終止?fàn)顟B(tài)則轉(zhuǎn)到第11)步，否則將當(dāng)前可以執(zhí)行的基本動(dòng)作組成一個(gè)集合U。

6)如果|U|>1，則執(zhí)行一個(gè)隨機(jī)動(dòng)作a(a∈U)，將a添加到trail尾部，轉(zhuǎn)到第5)步。

7)如果|U|=1，則U中的動(dòng)作就是當(dāng)前的瓶頸動(dòng)作b，Mb表示b所屬的根任務(wù)。對trail中的每個(gè)動(dòng)作a，同樣找到它們各自的根任務(wù)Ma，Ma、Mb∈TaskSet。比較Mb與Ma的訪問次數(shù)FMb,FMa：如果FMbFMa，uppertask=uppertask∪Ma。

8)如果|lowertask|≠0，新建一個(gè)復(fù)合任務(wù)Mlower，并使lowertask中的元素全部成為Mlower的子任務(wù)。

①如果Mb為原子任務(wù)，表示b所屬的動(dòng)作子集Ab中只有一個(gè)元素。新建一個(gè)復(fù)合任務(wù)Mnew，令Mb和Mlower為Mnew的子任務(wù)。TaskSet=(TaskSet-Mb-lowertask)∪Mnew。

②如果Mb為復(fù)合任務(wù)，表示b此時(shí)已經(jīng)加入某個(gè)復(fù)合任務(wù)中。找到b的父任務(wù)Mbp，設(shè)置集合children表示Mbp當(dāng)前的子任務(wù)集合，并且設(shè)置一個(gè)空的集合newchildren。對于children中的每個(gè)子任務(wù)Mi：如果Mi為原子任務(wù)，以Mi和Mlower為子任務(wù)構(gòu)造一個(gè)新的復(fù)合任務(wù)Mnew，newchildren=newchildren∪Mnew；如果Mi為復(fù)合任務(wù)，令Mi成為Mlower的一個(gè)子任務(wù)。

最終，如果|newchildren|=1，即children中只有一個(gè)原子任務(wù)(也就是b)，其余都是復(fù)合任務(wù)。則將該元素的子任務(wù)集合作為Mbp的子任務(wù)集合；如果|newchildren|>1，即children中有多個(gè)原子任務(wù)，則將newchildren作為Mbp的子任務(wù)集合。

9)如果|lowertask|=0，并且|uppertask|≠0，說明此時(shí)Mb應(yīng)為uppertask中元素的下層子任務(wù)。對于集合uppertask中的每個(gè)子任務(wù)Mupper，使用一種深度優(yōu)先的方法在Mupper的下屬子任務(wù)中找到訪問次數(shù)比Mb多的子任務(wù)，記為Mre。TaskSet=(TaskSet-Mb)∪Mre，將Mre放回TaskSet，其在Mupper的任務(wù)結(jié)構(gòu)中的位置被替換為Mb。

10)執(zhí)行瓶頸動(dòng)作b，轉(zhuǎn)到第4)步。

11)結(jié)束，此時(shí)|TaskSet|=1，子任務(wù)的層次結(jié)構(gòu)構(gòu)造完成。

2.3 子任務(wù)的終止條件

在MAXQ算法及一些基于MAXQ的改進(jìn)算法中，在對已知的分層結(jié)構(gòu)進(jìn)行學(xué)習(xí)時(shí)，判斷子任務(wù)是否終止，通常的方法是判斷當(dāng)前狀態(tài)是否為相應(yīng)子任務(wù)的終止?fàn)顟B(tài)(也稱為離開狀態(tài))。不過由于在上述自動(dòng)分層算法構(gòu)造分層結(jié)構(gòu)的過程中，很難記錄子任務(wù)的每個(gè)終止?fàn)顟B(tài)，所以需要一種新的判斷子任務(wù)是否終止的方法。本文提出一種通過比較當(dāng)前狀態(tài)的可用動(dòng)作和當(dāng)前子任務(wù)包含的基本動(dòng)作，判斷是否終止當(dāng)前子任務(wù)的方法。假設(shè)當(dāng)前執(zhí)行的子任務(wù)為M，所處的狀態(tài)為s，下面給出判斷M是否終止的方法流程描述：

1)用集合Actset表示當(dāng)前狀態(tài)s處的所有可用基本動(dòng)作。

2)用集合Act表示子任務(wù)M下屬的所有基本動(dòng)作。

3)如果M的子任務(wù)中有復(fù)合任務(wù)，并且Actset中存在Act中的元素，則此時(shí)M還不能終止。

4)如果M的子任務(wù)中有復(fù)合任務(wù)，但是Actset中沒有Act中的元素，則M終止。

5)如果M的子任務(wù)中只有原子任務(wù)，并且正是由于執(zhí)行了其中的某個(gè)原子任務(wù)而到達(dá)了狀態(tài)s，則M終止; 否則M繼續(xù)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證本文算法自動(dòng)分層的有效性，以及該層次結(jié)構(gòu)適用于MAXQ方法并能提升尋找最優(yōu)策略的效率，本文的實(shí)驗(yàn)使用強(qiáng)化學(xué)習(xí)研究中常見的出租車問題作為任務(wù)背景。Agent所處的環(huán)境如圖3所示，在一個(gè)10×10網(wǎng)格環(huán)境中，在4個(gè)角有4個(gè)站臺A、B、C、D，出租車會出現(xiàn)在整個(gè)環(huán)境中的一個(gè)隨機(jī)位置，乘客會隨機(jī)出現(xiàn)在四個(gè)站臺中的一個(gè)，乘客會在另外三個(gè)站臺中隨機(jī)選擇一個(gè)作為目的地。出租車的任務(wù)就是從起點(diǎn)出發(fā)，接乘客上車，將乘客送到目的地下車。

圖3 出租車問題圖示Fig. 3 Graphical representation of Taxi problem

實(shí)驗(yàn)中出租車可以執(zhí)行7個(gè)基本動(dòng)作，分別是東、西、南、北、加燃料、接乘客和放下乘客。在實(shí)驗(yàn)中，執(zhí)行東、西、南、北4個(gè)動(dòng)作會使出租車向相應(yīng)方向移動(dòng)一格，并獲得-1的回報(bào)，如果因?yàn)槭艿綁Ρ诨蛉剂舷拗贫鵁o法移動(dòng)則獲得-10的回報(bào)。在移動(dòng)5次后，燃料會用盡，此時(shí)必須執(zhí)行加燃料動(dòng)作，否則就無法移動(dòng)，執(zhí)行加燃料動(dòng)作后獲得-1的回報(bào)。在乘客所在位置必須執(zhí)行接乘客動(dòng)作，在目的地則必須要執(zhí)行放下乘客的動(dòng)作，成功接到乘客或放下乘客后會獲得20的回報(bào)，如果沒有在正確位置執(zhí)行“接乘客”與“放乘客”動(dòng)作會得到-10的回報(bào)。為了對比自動(dòng)分層后的學(xué)習(xí)效率，分別使用QLearning、Sarsa和已經(jīng)得到層次結(jié)構(gòu)的MAXQ方法三種強(qiáng)化學(xué)習(xí)方法尋找出租車問題的最優(yōu)策略。在學(xué)習(xí)過程中統(tǒng)一設(shè)定學(xué)習(xí)因子α=0.2，折扣因子γ=0.9，探索策略ε=0.8。每次實(shí)驗(yàn)運(yùn)行100個(gè)episode，每個(gè)episode代表出租車從起點(diǎn)出發(fā)，然后接到乘客，最后在目的地放下乘客的完整過程。為了增加環(huán)境的復(fù)雜性，設(shè)定在每個(gè)episode開始時(shí)，有30%的概率重新選擇出租車的起點(diǎn)、乘客所在的站臺和目的地。

3.2 實(shí)驗(yàn)結(jié)果與分析

在上述環(huán)境中，經(jīng)過自動(dòng)分層算法得到如圖4(b)所示層次結(jié)構(gòu)，可以看出該層次結(jié)構(gòu)符合出租車問題的一般過程。除了上文所述無障礙物環(huán)境，在圖4(a)所示環(huán)境中也可以構(gòu)造同樣的層次結(jié)構(gòu)，這說明使用本文算法，環(huán)境的變化不會影響層次結(jié)構(gòu)的構(gòu)造。

表1展示了在兩種實(shí)驗(yàn)環(huán)境中進(jìn)行20次構(gòu)造層次結(jié)構(gòu)的實(shí)驗(yàn)所得到的結(jié)果?？梢钥闯?，在添加障礙后，所需的動(dòng)作執(zhí)行次數(shù)增加了。這是因?yàn)樵诒疚牡乃惴ㄖ?，需要先使用隨機(jī)策略運(yùn)行一個(gè)完整的episode，通過這個(gè)episode的動(dòng)作執(zhí)行軌跡以及其中每種動(dòng)作的執(zhí)行次數(shù)才可以得到層次結(jié)構(gòu)。由于加入障礙后，隨機(jī)執(zhí)行動(dòng)作去完成一個(gè)episode所需的步數(shù)提高了，因此使得構(gòu)造層次結(jié)構(gòu)的時(shí)間相應(yīng)地加長了。

表1 兩種情況構(gòu)造出層次結(jié)構(gòu)所需基本動(dòng)作執(zhí)行次數(shù)

Tab. 1 Primitive actions for constructing a hierarchy in

Taxi problem with and without obstacles

下面展示使用三種算法得到的學(xué)習(xí)結(jié)果，其中圖5為平均步數(shù)的變化，圖6為平均回報(bào)的變化。

圖4 有障礙出租車問題及其任務(wù)圖Fig. 4 Taxi problem with obstacles and it’s task graph

圖5 隨著episode增加平均步數(shù)的變化情況Fig. 5 Change of average steps with episode increase

圖6 隨著episode增加平均回報(bào)的變化情況Fig. 6 Change of average reward with episode increase

在平均步數(shù)的變化趨勢中可以看出，經(jīng)過自動(dòng)分層的MAXQ方法在整個(gè)實(shí)驗(yàn)過程中變化趨勢較為平穩(wěn)。在學(xué)習(xí)前期的episode中就可以通過比較少的動(dòng)作執(zhí)行數(shù)完成任務(wù)，同一時(shí)期QLearning和Sarsa方法都需要執(zhí)行更多的動(dòng)作。在運(yùn)行20次episode后，三種算法都趨于平穩(wěn)，最終的平均執(zhí)行次數(shù)比較相近。之所以會有這樣的結(jié)果，主要是因?yàn)槭褂肕AXQ方法時(shí)，學(xué)習(xí)任務(wù)被分為多個(gè)子任務(wù)，在完成子任務(wù)的過程中可以忽略那些和完成該子任務(wù)無關(guān)的動(dòng)作。比如，在“導(dǎo)航”子任務(wù)中就可以直接忽略“接乘客”和“放乘客”這兩個(gè)動(dòng)作，在“移動(dòng)”子任務(wù)又可以忽略“加燃料”動(dòng)作。由于在每一階段的子任務(wù)中所考慮的動(dòng)作數(shù)減少了，所以從一開始MAXQ方法就可以通過更少的執(zhí)行次數(shù)完成目標(biāo)。而QLearning和Sarsa在前期使用接近隨機(jī)策略的方法探索實(shí)驗(yàn)環(huán)境，在積累了多個(gè)episode的經(jīng)驗(yàn)后，才逐漸收斂到最優(yōu)策略。通過平均回報(bào)的變化趨勢，可以看出MAXQ方法的平均回報(bào)明顯優(yōu)于其他兩種方法。這也是由于層次結(jié)構(gòu)的存在使得在學(xué)習(xí)過程中執(zhí)行動(dòng)作的隨機(jī)性下降了，執(zhí)行錯(cuò)誤動(dòng)作得到-10懲罰的次數(shù)減少很多。

圖7展示了在相同實(shí)驗(yàn)環(huán)境下完成100次episode平均時(shí)間的變化趨勢?？梢园l(fā)現(xiàn)MAXQ與Sarsa方法所用時(shí)間明顯少于QLearning，即使在任務(wù)后期episode的平均步數(shù)相近時(shí)，QLearning中episode所用的平均時(shí)間仍明顯多于MAXQ與Sarsa。

圖7 隨著episode增加平均時(shí)間的變化情況Fig. 7 Change of average time with episode increase

4 結(jié)語

本文在現(xiàn)有的分層強(qiáng)化學(xué)習(xí)的基礎(chǔ)上，提出了一種基于動(dòng)作空間劃分的自動(dòng)分層MAXQ方法。利用在隨機(jī)探索過程中，動(dòng)作執(zhí)行時(shí)所影響的狀態(tài)分量劃分動(dòng)作集。根據(jù)動(dòng)作執(zhí)行的次序，推導(dǎo)出動(dòng)作子集之間的層次關(guān)系。此外，對MAXQ方法中判斷子任務(wù)終止的條件進(jìn)行了修改，使通過動(dòng)作空間得到的層次結(jié)構(gòu)適用于MAXQ學(xué)習(xí)算法。通過出租車問題的實(shí)驗(yàn)，驗(yàn)證了分層的有效性，也證明了該方法得到的層次結(jié)構(gòu)可以通過MAXQ方法找到最優(yōu)策略。

本文所提方法仍然存在一些需要完善之處，比如在學(xué)習(xí)過程中，每次執(zhí)行的步數(shù)相近，雖然穩(wěn)定但卻沒有收斂的趨勢。在環(huán)境會隨時(shí)發(fā)生變化的情況下效果很好，但在固定不變的環(huán)境中，例如在出租車問題中固定每次乘客出現(xiàn)的位置和目的地位置時(shí)，得到的結(jié)果并不理想。下一步的研究目標(biāo)是進(jìn)一步優(yōu)化學(xué)習(xí)算法，使之適用于更廣泛的環(huán)境。

References)

[1] KHAN S G, HERRMANN G, LEWIS F L, et al. Reinforcement learning and optimal adaptive control: an overview and implementation examples[J]. Annual Reviews in Control, 2012, 36(1): 42-59.

[2] 陳學(xué)松, 楊宜民. 強(qiáng)化學(xué)習(xí)研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(8):2834-2838.(CHEN X S, YANG Y M. Reinforcement learning: survey of recent work[J]. Application Research of Computers, 2010, 8(27): 2834-2838.)

[3] 趙冬斌, 邵坤, 朱圓恒,等. 深度強(qiáng)化學(xué)習(xí)綜述:兼論計(jì)算機(jī)圍棋的發(fā)展[J]. 控制理論與應(yīng)用, 2016, 33(6): 701-717.(ZHAO D B, SHAO K, ZHU Y H, et al. Review of deep reinforcement learning and discussions on the development of computer Go[J]. Control Theory & Applications, 2016, 33(6): 701-717.)

[4] 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/2):181-211.

[5] DIETTERICH T G. Hierarchical reinforcement learning with the MAXQ value function decomposition[J]. Journal of Artificial Intelligence Research, 2000, 13(1):227-303.

[6] PARR R E. Hierarchical control and learning for Markov decision processes[D]. Berkeley: University of California at Berkeley, 1998: 87-109.

[7] HENGST B. Discovering hierarchy in reinforcement learning with HEXQ[C]// Proceedings of the 19th International Conference on Machine Learning. San Francisco, CA: Morgan Kaufmann Publishers Inc., 2002: 243-250.

[8] MCGOVERN E A. Autonomous discovery of temporal abstractions from interaction with an environment[D]. Amherst: University of Massachusetts Amherst, 2002: 26-38.

[9] STOLLE M. Automated discovery of options in reinforcement learning[D]. Montreal: McGill University, 2004: 21-31.

[10] MEHTA N, RAY S, TADEPALLI P, et al. Automatic discovery and transfer of MAXQ hierarchies[C]// Proceedings of the 25th International Conference on Machine Learning. New York: ACM, 2008: 648-655.

[11] 石川, 史忠植, 王茂光. 基于路徑匹配的在線分層強(qiáng)化學(xué)習(xí)方法[J]. 計(jì)算機(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.)

[12] 沈晶. 分層強(qiáng)化學(xué)習(xí)方法研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2006: 28-55.(SHEN J. Research on hierarchical reinforcement learning approach[D]. Harbin: Harbin Engineering University, 2006: 28-55.)

[13] 陳興國, 俞揚(yáng). 強(qiáng)化學(xué)習(xí)及其在電腦圍棋中的應(yīng)用[J]. 自動(dòng)化學(xué)報(bào), 2016, 42(5): 685-695.(CHEN X G, YU Y. Reinforcement learning and its application to the game of go[J]. Acta Automatica Sinica, 2016, 42(5): 685-695.)

[14] BARTO A G, MAHADEVAN S. Recent advances in hierarchical reinforcement learning[J]. Discrete Event Dynamic Systems, 2003, 13(4): 341-379.

[15] JONG N K, STONE P. State abstraction discovery from irrelevant state variables[C]// Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann Publishers Inc., 2005: 752-757.

[16] TAKAHASHI Y, ASADA M. Multi-controller fusion in multi-layered reinforcement learning[C]// Proceedings of the 2001 International Conference on Multisensor Fusion and Integration for Intelligent Systems. Piscataway, NJ: IEEE, 2001: 7-12.

[17] STOLLE M, PRECUP D. Learning options in reinforcement learning[C]// Proceedings of the 5th International Symposium on Abstraction, Reformulation and Approximation. London: Springer-Verlag, 2002:212-223.

[18] 蘇暢, 高陽, 陳世福,等. 基于SMDP環(huán)境的自主生成Options算法的研究[J]. 模式識別與人工智能, 2005, 18(6): 679-684.(SU C, GAO Y, CHEN S F, et al. The study of recognizing Options based on SMDP[J]. Pattern Recognition and Artificial Intelligence, 2005, 18(6):679-684.)

This work is partially supported by the National Natural Science Foundation of China (61562009), the Scientific Research Foundation for Talent Introduction of Guizhou University (2012028).

WANG Qi, born in 1992, M. S. candidate, His research interests include machine learning.

QIN Jin, born in 1978, Ph. D., associate professor. His research interests include computational intelligence.

Automatic hierarchical approach of MAXQ based on action space partition

WANG Qi*, QIN Jin

(CollegeofComputerScienceandTechnology,GuizhouUniversity,GuiyangGuizhou550025,China)

Since a hierarchy of Markov Decision Process (MDP) need to be constructed manually in hierarchical reinforcement learning and some automatic hierarchical approachs based on state space produce unsatisfactory results in environment with not obvious subgoals, a new automatic hierarchical approach based on action space partition was proposed. Firstly, the set of actions was decomposed into some disjoint subsets through the state component of the action. Then, bottleneck actions were identified by analyzing the executable actions of the Agent in different states. Finally, based on the execution order of actions and bottleneck actions, the relationship of action subsets was determined and a hierarchy was constructed. Furthermore, the termination condition for sub-tasks in the MAXQ method was modified so that by using the hierarchical structure of the proposed algorithm the optimal strategy could be found through the MAXQ method. The experimental results show that the algorithm can automatically construct the hierarchical structure which was not affected by environmental change. Compared with the QLearning and Sarsa algorithms, the MAXQ method with the proposed hierarchy obtains the optimal strategy faster and gets higher returns. It verifies that the proposed algorithm can effectively construct the MAXQ hierarchy and make the optimal strategy more efficient.

reinforcement learning; hierarchical reinforcement learning; automatic hierarchical approach; Markov Decision Process (MDP); subtask

2016-09-28;

2016-12-16。

國家自然科學(xué)基金資助項(xiàng)目(61562009)；貴州大學(xué)引進(jìn)人才科研項(xiàng)目(貴大人基合字(2012)028號)。

王奇(1992—)，男，河南開封人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)； 秦進(jìn)(1978—)，男，貴州黔西人，副教授，博士，主要研究方向：計(jì)算智能。

1001-9081(2017)05-1357-06

10.11772/j.issn.1001-9081.2017.05.1357

TP181

A