王 奇，秦 進

(貴州大學 計算機科學與技術學院，貴陽 550025)

基于動作空間劃分的MAXQ自動分層方法

王 奇*，秦 進

(貴州大學 計算機科學與技術學院，貴陽 550025)

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

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

強化學習；分層強化學習；自動分層方法；馬爾可夫決策過程；子任務

0 引言

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

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

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

1 馬爾可夫決策過程與分層強化學習

1.1 馬爾可夫決策過程

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

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

(1)

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

(2)

(3)

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

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

圖1 SMDP與MDPFig. 1 SMDP and MDP

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

(4)

(5)

1.2 分層強化學習

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

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

1.3 MAXQ值函數分解

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

(6)

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

(7)

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

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

(8)

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

(9)

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

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

(10)

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

圖2 MAXQ值函數分解Fig. 2 MAXQ decomposition

2 基于動作的層次結構劃分方法

2.1 動作空間劃分的基本思想

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

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

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

FMi=

(11)

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

2.2 自動分層算法描述

為了便于描述，在后文中會將子任務間的隸屬關系，描述為父任務與孩子任務，一個復合任務中最上層的子任務稱為根任務。下面給出自動分層算法的描述。

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

輸出 根任務M0，M0及其下屬的所有子任務構成了完整的任務層次結構。

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

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

3)Agent從起點出發(fā)，依據πrandom執(zhí)行一個隨機動作。

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

5)如果當前狀態(tài)是終止狀態(tài)則轉到第11)步，否則將當前可以執(zhí)行的基本動作組成一個集合U。

6)如果|U|>1，則執(zhí)行一個隨機動作a(a∈U)，將a添加到trail尾部，轉到第5)步。

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

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

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

②如果Mb為復合任務，表示b此時已經加入某個復合任務中。找到b的父任務Mbp，設置集合children表示Mbp當前的子任務集合，并且設置一個空的集合newchildren。對于children中的每個子任務Mi：如果Mi為原子任務，以Mi和Mlower為子任務構造一個新的復合任務Mnew，newchildren=newchildren∪Mnew；如果Mi為復合任務，令Mi成為Mlower的一個子任務。

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

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

10)執(zhí)行瓶頸動作b，轉到第4)步。

11)結束，此時|TaskSet|=1，子任務的層次結構構造完成。

2.3 子任務的終止條件

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

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

2)用集合Act表示子任務M下屬的所有基本動作。

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

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

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

3 實驗與分析

3.1 實驗設置

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

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

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

3.2 實驗結果與分析

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

表1展示了在兩種實驗環(huán)境中進行20次構造層次結構的實驗所得到的結果。可以看出，在添加障礙后，所需的動作執(zhí)行次數增加了。這是因為在本文的算法中，需要先使用隨機策略運行一個完整的episode，通過這個episode的動作執(zhí)行軌跡以及其中每種動作的執(zhí)行次數才可以得到層次結構。由于加入障礙后，隨機執(zhí)行動作去完成一個episode所需的步數提高了，因此使得構造層次結構的時間相應地加長了。

表1 兩種情況構造出層次結構所需基本動作執(zhí)行次數

Tab. 1 Primitive actions for constructing a hierarchy in

Taxi problem with and without obstacles

下面展示使用三種算法得到的學習結果，其中圖5為平均步數的變化，圖6為平均回報的變化。

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

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

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

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

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

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

4 結語

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

本文所提方法仍然存在一些需要完善之處，比如在學習過程中，每次執(zhí)行的步數相近，雖然穩(wěn)定但卻沒有收斂的趨勢。在環(huán)境會隨時發(fā)生變化的情況下效果很好，但在固定不變的環(huán)境中，例如在出租車問題中固定每次乘客出現的位置和目的地位置時，得到的結果并不理想。下一步的研究目標是進一步優(yōu)化學習算法，使之適用于更廣泛的環(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] 陳學松, 楊宜民. 強化學習研究綜述[J]. 計算機應用研究, 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] 趙冬斌, 邵坤, 朱圓恒,等. 深度強化學習綜述:兼論計算機圍棋的發(fā)展[J]. 控制理論與應用, 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] 石川, 史忠植, 王茂光. 基于路徑匹配的在線分層強化學習方法[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] 沈晶. 分層強化學習方法研究[D]. 哈爾濱: 哈爾濱工程大學, 2006: 28-55.(SHEN J. Research on hierarchical reinforcement learning approach[D]. Harbin: Harbin Engineering University, 2006: 28-55.)

[13] 陳興國, 俞揚. 強化學習及其在電腦圍棋中的應用[J]. 自動化學報, 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。

國家自然科學基金資助項目(61562009)；貴州大學引進人才科研項目(貴大人基合字(2012)028號)。

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

1001-9081(2017)05-1357-06

10.11772/j.issn.1001-9081.2017.05.1357

TP181

A