欒詠紅，劉　全，章　鵬（1.蘇州工業(yè)職業(yè)技術(shù)學院，江蘇蘇州　15104；.蘇州大學計算機科學與技術(shù)學院，江蘇蘇州　15006；3.吉林大學符號計算與知識工程教育部重點實驗室，吉林長春　13001）

?

連續(xù)空間中的隨機技能發(fā)現(xiàn)算法

欒詠紅1，2，劉全2，3，章鵬2
（1.蘇州工業(yè)職業(yè)技術(shù)學院，江蘇蘇州215104；2.蘇州大學計算機科學與技術(shù)學院，江蘇蘇州215006；3.吉林大學符號計算與知識工程教育部重點實驗室，吉林長春130012）

摘要：針對大規(guī)模、連續(xù)空間隨著狀態(tài)維度指數(shù)級增加造成的“維數(shù)災(zāi)”問題，提出基于Option分層強化學習基礎(chǔ)框架的改進的隨機技能發(fā)現(xiàn)算法。通過定義隨機Option生成一棵隨機技能樹，構(gòu)造一個隨機技能樹集合。將任務(wù)目標分成子目標，通過學習低階Option策略，減少因智能體增大而引起學習參數(shù)的指數(shù)增大。以二維有障礙柵格連續(xù)空間內(nèi)兩點間最短路徑規(guī)劃為任務(wù)，進行仿真實驗和分析，實驗結(jié)果表明：由于Option被隨機定義，因此算法在初始性能上具有間歇的不穩(wěn)定性，但是隨著隨機技能樹集合的增加，能較快地收斂到近似最優(yōu)解，能有效克服因為維數(shù)災(zāi)引起的難以求取最優(yōu)策略或收斂速度過慢的問題。

關(guān)鍵詞：強化學習；Option；連續(xù)空間；隨機技能發(fā)現(xiàn)

0　引　言

強化學習[1?2]（Reinforcement Learning，RL）是Agent通過與環(huán)境直接交互，學習狀態(tài)到行為的映射策略。經(jīng)典的強化學習算法試圖在所有領(lǐng)域中尋求一個最優(yōu)策略，這在小規(guī)?；螂x散環(huán)境中是很有效的，但是在大規(guī)模和連續(xù)狀態(tài)空間中會面臨著“維數(shù)災(zāi)”的問題。為了解決“維數(shù)災(zāi)”等問題，研究者們提出了狀態(tài)聚類法、有限策略空間搜索法、值函數(shù)逼近法以及分層強化學習等方法[3]。分層強化學習的層次結(jié)構(gòu)的構(gòu)建實質(zhì)是通過在強化學習的基礎(chǔ)上增加抽象機制來實現(xiàn)的，也就是利用了強化學習方法中的原始動作和高層次的技能動作[3]（也稱為Option）來實現(xiàn)。

分層強化學習的主要研究目標之一是自動發(fā)現(xiàn)層次技能。近年來雖然有很多研究分層強化學習的方法，多數(shù)針對在較小規(guī)模的、離散領(lǐng)域中尋找層次技能。譬如Simsek與Osentoski等人通過劃分由最近經(jīng)驗構(gòu)成的局部狀態(tài)轉(zhuǎn)移圖來尋找子目標[4?5]。McGovern和Batro等根據(jù)狀態(tài)出現(xiàn)的頻率選擇子目標[6]。Matthew提出將成功路徑上的高頻訪問狀態(tài)作為子目標，Jong和Stone提出從狀態(tài)變量的無關(guān)性選擇子目標[7]。但是，這些方法都是針對較小規(guī)模、離散的強化學習領(lǐng)域。2009年Konidaris和Barto等人提出了在連續(xù)強化學習空間中的一種技能發(fā)現(xiàn)方法，稱為技能鏈[8]。2010年Konidaris又提出根據(jù)改變子目標點檢測方法[9]來分割每個求解路徑為技能的CST算法，這種方法僅限于路徑不是太長且能被獲取的情況。

本文介紹了一種在連續(xù)RL域的隨機技能發(fā)現(xiàn)算法。采用Option分層強化學習中自適應(yīng)、分層最優(yōu)特點，將每個高層次的技能定義為一個Option，且隨機定義的，方法的復(fù)雜度與復(fù)雜學習領(lǐng)域的Option構(gòu)建數(shù)量成比例。雖然Option的隨機選擇可能不是最合適的，但是由于構(gòu)建的Option不僅是一個技能樹還是一個技能樹的集合，因此彌補了這個不足之處。

1　分層強化學習與Option框架

分層強化學習（Hierarchical Reinforcement Learn?ing，HRL）的核心思想是引入抽象機制對整個學習任務(wù)進行分解。在HRL方法中，智能體不僅能處理給定的原始動作集，同時也能處理高層次技能。

Option是Sutton提出的一種應(yīng)用比較廣泛的HRL方法，它對學習任務(wù)的分層是一個在狀態(tài)空間上發(fā)現(xiàn)子目標和構(gòu)造Option的過程[10]。Option方法是對MDP （Markov Decision Process）中的基本動作進行擴展，一個Option可以理解為到達子目標而定義在相關(guān)狀態(tài)子空間上的按一定策略執(zhí)行的動作或Option序列，即動作選擇集[11]。

簡單的Option直接定義在MDP上，由三元組o =I，π，β表示。其中s∈I為Option輸入狀態(tài)集，它包含且僅包含Option經(jīng)歷的所有可能狀態(tài)，當且僅當智能體的當前狀態(tài)s∈I時，Option才可以根據(jù)內(nèi)部策略展開執(zhí)行。π:S×A→[0，1]表示Option的內(nèi)部策略；其中AI為I上可以執(zhí)行的動作集；β:S→[0，1]是Option結(jié)束的終止判斷函數(shù)，Option在某一狀態(tài)s′依概率β(s′)終止，通常將Option要達到子目標狀態(tài)sG定義為β(sG) = 1。每個Option在被執(zhí)行時，動作的選擇僅依賴于自身內(nèi)部策略π，即智能體根據(jù)策略π(s，a)選擇下一動作a作用于環(huán)境，使環(huán)境狀態(tài)s轉(zhuǎn)移到s′。

如果將策略定義在Option之上，即μ:S×OI→[0，1]。其中OI為狀態(tài)集I上可以執(zhí)行的Op? tion集；I和β定義不變，則I，μ，β形成分層的Option，初始Option啟動后，根據(jù)策略μ依次選擇其他Option執(zhí)行，直到根據(jù)終止條件β結(jié)束，被選中的Option可以按照各自的策略再選擇其他Option執(zhí)行。若將所有Op?tion都展開到基本動作層，則μ確定了MDP的一個常規(guī)策略，Sutton稱其為與μ對應(yīng)的平坦策略，記為flat(μ)。

利用單步Q?學習算法來對值函數(shù)進行學習，值函數(shù)的每次更新都發(fā)生在Option執(zhí)行結(jié)束之后。Precup引入多時間步模型對傳統(tǒng)的單步模型進行泛化[12]，并證明在標準Q?學習收斂條件下，基于Option的Q?學習算法依概率1收斂到：

式中：R(s，o)為狀態(tài)s下o的獎賞值；P(s′|s，o′)為狀態(tài)轉(zhuǎn)移概率。假設(shè)Option o在狀態(tài)s開始執(zhí)行了τ步后在狀態(tài)s′終止，則Option值函數(shù)Q(s，o)的迭代算法如下：

式中：r為Option o在整個執(zhí)行過程中的累計折扣獎賞值。

基于Option的自動分層方法一般分為兩步：首先，通過對任務(wù)狀態(tài)空間的分割得到各子任務(wù)的狀態(tài)集合；然后，再在此狀態(tài)集上采用強化學習方法學習相應(yīng)的策略[12?13]。學習新的Option算法必須包括確定何時創(chuàng)建一個Option或展開它的起始集，如何定義它的終止條件（技能發(fā)現(xiàn)），以及如何學習它的策略的方法。策略學習通常是由一個離策略強化學習算法，使得智能體可以在采取動作后同時更新多個Option[14]。

2　隨機技能發(fā)現(xiàn)算法

在小規(guī)模狀態(tài)空間或離散狀態(tài)空間的強化學習任務(wù)中，可以通過層次將學習任務(wù)分解成一系列的子目標，它們的終止狀態(tài)是在關(guān)鍵路徑中，這些關(guān)鍵的狀態(tài)可以由設(shè)計者定義，但是當環(huán)境為連續(xù)或大規(guī)模時，面臨大空間的MDP任務(wù)時，將會帶來很大的計算代價。因此，在連續(xù)狀態(tài)空間中提出了一種隨機技能發(fā)現(xiàn)算法（RSD），該算法引入隨機Option和隨機的技能樹（Skill tree），在算法中對其進行形式化。

2.1隨機Option

Option創(chuàng)建與終止通常都是由目標狀態(tài)識別完成的，它可以創(chuàng)建一個目標狀態(tài)，并在結(jié)束時終止它。

定義1隨機Option對于一個給定的輸入集（狀態(tài)空間區(qū)域），定義o的終止狀態(tài)和獎賞函數(shù)。假定目標狀態(tài)為So，其中對于所有的s∈So至少有一個a∈A，使得s′?Io（其中，s′是在狀態(tài)s處執(zhí)行動作a得到的下一個狀態(tài)）。換句話說，終止狀態(tài)是由輸入集Io的前端定義的。設(shè)置o的獎賞函數(shù)是Option啟動下一個Op?tion完成所獲得的獎賞。

使用標準強化學習算法來學習o的策略，采用一個線性函數(shù)逼近器與一套合適的基函數(shù)來表示Option的值函數(shù)，如式（3）所示。

式中：ω∈Rn為n維的參數(shù)向量；?(s，a) = [?1(s，a) ，?2(s，a) ，…，?n(s，a)]T為狀態(tài)動作對(s，a)的n維特征向量；?1(s，a) ，?2(s，a) ，…，?n(s，a)稱為基函數(shù)（Ba?sis Functions，BFs）。

Option學習中只在一個Option結(jié)束時更新，有時無法確定目標狀態(tài)是Option的終止狀態(tài)，也就說存在一些非終止的Option，其目標狀態(tài)是包含在輸入集中的。在本文算法中采用了intra?option模型。只考慮Markov?Option模型o =I，π，β的intra?option學習，則狀態(tài)Op?tion對(s，o)的值函數(shù)計算如式（4）、式（5）所示。

式中：r是在狀態(tài)s′處的立即獎賞；s′是在狀態(tài)s處執(zhí)行動作a得到的下一狀態(tài)。

根據(jù)式（3）～式（5）可以從狀態(tài)空間區(qū)域中得到所有的樣本。由于o的獎賞函數(shù)是根據(jù)它臨近Option設(shè)置的，則它的學習策略可以在臨近Option的值改變時被更新。隨著狀態(tài)求解路徑的不斷規(guī)劃，最終只有在求解路徑中的那些狀態(tài)可以被導航到學習的策略，而在終止狀態(tài)中剪掉的狀態(tài)不會包含在求解路徑中。

2.2隨機技能樹

本文介紹的隨機技能樹（Random Skill tree）是一個自上而下的，首先從單個子集的劃分開始，然后逐步重新定義子集并進行劃分。它不同于RL中經(jīng)典樹的方法，技能樹中的每個葉子節(jié)點不僅表示某個區(qū)域的值同時也表示了從某個空間區(qū)域的一個Option < I，π，β>。每個Option都有自己的線性函數(shù)逼近器集中在狀態(tài)空間的一個子集中。對于某個指定的連續(xù)空間來說，一個隨機的技能樹開始于一個Option，即樹的根，它的輸入集包含了整個空間。整個技能樹的建立通過不斷地對節(jié)點不同方向的隨機選擇、并對每個隨機方向選擇一個隨機樣本點進行預(yù)分割，將輸入集劃分為2個子集，而新的Option如同原來描述的一樣（但是對于包含目標狀態(tài)的區(qū)域，非終止的Option將會被建立），直到滿足終止條件。從訓練集中建立一個隨機技能樹的過程，每個節(jié)點的剪切點和剪切方向都是隨機選擇的。定義終止條件為訓練集的大小，即為每個空間區(qū)域中的#TS。如果#TS≤nmin，則停止劃分Option節(jié)點，其中，nmin是用于劃分節(jié)點訓練集的最小尺寸。建立隨機技能樹的過程如算法1所示。

算法1：Build_a_tree（TS，D）

輸入訓練集TS，狀態(tài)空間D；

判斷#TS≤nmin成立時；

Step1：如果目標狀態(tài)不包含在狀態(tài)空間D，則返回一個Op?tion o < I，π，β>，where I：{s|s?falls?in?D}；β：{s|s∈I?and??as′?I}；

Step2：否則根據(jù)式（4）、式（5）建立一個非終止的Option；

隨機分割狀態(tài)空間D為兩個子區(qū)域D1和D2，同時訓練集合TS分割為TS1和TS2；

根據(jù)分割后的樣本集TS1和TS2，遞歸調(diào)用算法1建立技能樹T1和T2；

創(chuàng)建節(jié)點，令T1和T2作為該節(jié)點的左右子樹，并返回該節(jié)點。

該算法首次被調(diào)用是建立整個任務(wù)的一個隨機技能樹，所以第一次調(diào)用TS和D分別表示整個訓練集和整個狀態(tài)空間。然后這個樹將通過遞歸調(diào)用算法來建立。

2.3RSD算法描述

針對給定的一個訓練集，RSD算法建立隨機技能樹集合，參數(shù)為M。每個集合都是在整個訓練集中建立的，如第2.2節(jié)中所描述的，這個訓練集是從單個路徑中或者在整個狀態(tài)空間中隨機獲取的。對于一個狀態(tài)來說，有M個Option可以采用，其中每個Option集合都覆蓋整個任務(wù)。RSD算法的學習規(guī)則，對于無法確定目標狀態(tài)是某些Option的終止狀態(tài)，采用式（4）、式（5）學習Option內(nèi)部策略，生成Option。RSD算法描述如下所示。

算法2：隨機技能發(fā)現(xiàn)算法（RSD算法）

Step3：根據(jù)式（6）使用TSN計算基函數(shù)權(quán)重，確定QN(s，o)。

在本文中，由于考慮的是連續(xù)狀態(tài)空間，主要集中在以大量的數(shù)值型輸入變量和單個的目標變量為特征的離線學習問題上。當值函數(shù)逼近模型為線性模型時，典型的離線訓練方法一般采用最小二乘回歸方法來求解。最小二乘回歸是在一定的樣本集合下，以最小化目標函數(shù)估計值與真實值之差的平方和為目標的回歸優(yōu)化問題。在這個算法中，計算了采用最小二乘方法得到的基函數(shù)權(quán)重，它的目標是獲得合適的權(quán)重去最小化真實數(shù)據(jù)和模型之間的最小二乘誤差，等價于最小化下面的表達式：

3　實驗結(jié)果與分析

為了驗證所提出算法的性能，實驗采用10×10的連續(xù)不規(guī)則障礙柵格空間內(nèi)兩點間最短路徑規(guī)劃為任務(wù)背景，如圖1所示。目標狀態(tài)就是圖1中的紅色格子，黑色柵格表示障礙物，其他網(wǎng)格為可以通行的區(qū)域。學習任務(wù)就是找到智能體各個狀態(tài)到達目標狀態(tài)的最優(yōu)動作策略。在每個位置，智能體有4個可能的動作：向右、向左、向下和向上。當這些動作執(zhí)行完畢后，智能體都會以概率1移動到下一個位置上。如果移動的方向是有障礙物的，則智能體仍然在同一位置上。智能體達到目標時，就能得到一個立即獎賞為+1，否則得到的立即獎賞為0。

圖1　連續(xù)的有障礙柵格空間

在此比較三個智能體：一個是在連續(xù)域中采用原始動作；一個是采用RSD算法中技能發(fā)現(xiàn)；一個是在學習之前使用已定義的Option。每個智能體的訓練集采樣都是從10個簡單路徑上獲取的（所有的都開始于一個隨機位置）。智能體采用Q?學習算法（折扣因子γ= 0.9）并結(jié)合線性函數(shù)逼近。如圖2所示，實驗結(jié)果是三個智能體在連續(xù)迷宮區(qū)域，具有相同的訓練集，從100個不同起始位置到達目標狀態(tài)的平均步數(shù)。在圖2中，可以看到智能體在初始的一些情節(jié)中采用給定的Option表現(xiàn)的更好，遠遠優(yōu)于在沒有任何Option下智能體所學習的結(jié)果，在很多情節(jié)后，它能表現(xiàn)出在平坦策略下的更快的收斂結(jié)果。這表明了Option增加了學習的性能表現(xiàn)，同時也在其他工作也證明了這一點。

圖2同樣也展示了具有不同輸入集下RSD算法得到的性能結(jié)果。智能體采用RSD算法，設(shè)置技能樹集合參數(shù)M = 5，訓練集最小尺寸nmin= 100時，由于在初始情節(jié)中，在沒有Option的情況下執(zhí)行的更差，它的平均步數(shù)維持在一個較大的值，但是它最終收斂到與給定合適的Option情況下的相同質(zhì)量的解。由于Option通過智能體利用RSD算法隨機獲取的，因此，性能表現(xiàn)在每輪迭代中是不穩(wěn)定的。在某些情況下，它能提高性能，但在某些情況下，它也許會降低學習率。從圖2中可以看到，當參數(shù)M = 20時，智能體在初始情節(jié)中表現(xiàn)的很好，然后能以一個更快的收斂速度收斂到一個近似最優(yōu)解。智能體利用RSD算法得到的三條學習曲線，其中參數(shù)M = 20與nmin= 50，比其他兩個利用RSD算法得到的學習曲線效果好些。盡管初始性能不如前面算法，但是能在少數(shù)情節(jié)后獲得連續(xù)的最優(yōu)方法。實驗結(jié)果分析表明，RSD算法能產(chǎn)生好的學習性能，能收斂到與定義合適的給定Option算法相同質(zhì)量的解。性能上的改進也隨著隨機技能樹的集合尺寸的增加變得更好。

圖2　連續(xù)有障礙柵格空間的學習性能

4　結(jié)　語

實驗的性能結(jié)果表明了RSD算法能顯著提高連續(xù)域中RL問題的性能，通過采用隨機技能樹集合和對每個樹葉學習一個低階的Option策略。RSD算法的優(yōu)點，與其他的技能發(fā)現(xiàn)方法相比，可以采用Option框架更好地處理RL連續(xù)域的問題，無需分析訓練集的圖或值自動創(chuàng)建Option。因此，它可以降低搜索特定Option的負擔，能使它更適應(yīng)于大規(guī)?；蜻B續(xù)狀態(tài)空間，能分析一些困難較大的領(lǐng)域問題。

參考文獻

[1]SUTTON R S，BARTO A G. Reinforcement learning：An intro?duction [M]. Cambridge，MA：MIT Press，1998.

[2]KAELBLING L P，LITTMAN M L，MOORE A W. Reinforce?ment learning：A survey [EB/OL]. [1996?05?01]. http：// www.cs. cmu.edu/afs/cs...vey.html.

[3]BARTO A G，MAHADEVAN S. Recent advances in hierarchi?cal reinforcement learning [J]. Discrete event dynamic systems.2003，13（4）：341?379.

[4]SIMSEK O，WOLFE A P，BARTO A G. Identifying useful sub?goals in reinforcement learning by local graph partitioning [C]// Proceedings of the 22nd International Conference on Machine learning. USA：ACM，2005，8：816?823.

[5]OSENTOSKI S，MAHADEVAN S. Learning state?action basis functions for hierarchical MDPs [C]// Proceedings of the 24th International Conference on Machine learning. USA：ACM，2007，7：705?712.

[6]MCGOVERN A，BARTO A. Autonomous discovery of subgolas in reinfoeremente learning using deverse density [C]// Pro?ceedings of the 8th Intemational Coference on Machine Learning. San Fransisco：Morgan Kaufmann，2001：36l?368.

[7]JONG N K，STONE P. State abstraction discovery from irrele?vant state variables [J]. IJCAI，2005，8：752?757.

[8]KONIDARIS G，BARTO A G. Skill discovery in continuous re?inforcement learning domains using skill chaining [J]. NIPS，2009，8：1015?1023.

[9]KONIDARIS G，KUINDERSMA S，BARTO A G，et al. Con?structing skill trees for reinforcement learning agents from demonstration trajectories [J]. NIPS，2010，23：1162?1170.

[10]劉全，閆其粹，伏玉琛，等.一種基于啟發(fā)式獎賞函數(shù)的分層強化學習方法[J].計算機研究與發(fā)展，2011，48（12）：2352?2358.

[11]沈晶，劉海波，張汝波，等.基于半馬爾科夫?qū)Σ叩亩鄼C器人分層強化學習[J].山東大學學報（工學版），2010，40（4）：1?7.

[12]KONIDARIS G，BARTO A. Efficient skill learning using ab?straction selection [C]// Proceedings of the 21st International Joint Conference on Artificial Intelligence. Pasadena，CA，USA：[S.l.]，2009：1107?1113.

[13]XIAO Ding，LI Yitong，SHI Chuan. Autonomic discovery of subgoals in hierarchical reinforcement learning [J]. Journal of china universities of posts and telecommunications，2014，21 （5）：94?104.

[14]CHEN Chunlin，DONG Daoyi，LI Hanxiong，et al. Hybrid MDP based integrated hierarchical Q?learning [J]. Science Chi?na（information sciences），2011，54（11）：2279?2294.

A random skill discovery algorithm in continuous spaces

LUAN Yonghong1，2，LIU Quan2，3，ZHANG Peng2
（1. Suzhou Institute of Industrial Technology，Suzhou 215104，China；2. Institute of Computer Science and Technology，Soochow University，Suzhou 215006，China；3. MOE Key Laboratory of Symbolic Computation and Knowledge Engineering，Jilin University，Changchun 130012，China）

Abstract：In allusion to the large and continuous space’s“dimension curse”problem caused by the increase of state di?mension exponential order，an improved random skill finding algorithm based on Option hierarchical reinforcement learning framework is proposed. A random skill tree set is generated via defining random Option to construct a random skill tree set. The task goal is divided into several sub?goals，and then the increase of learning parameter exponent due to the increase of the intel?ligent agent is reduced through learning low?order Option policy. The simulation experiment and analysis were implemented by taking a shortest path between any two points in two?dimension maze with barriers in the continuous space as the task. The experiment result shows that the algorithm may have some intermittent instability in the initial performance because Option is de?fined randomly，but it can be converged to the approximate optimal solution quickly with the increase of the random skill tree set，which can effectively overcome the problem being hard to obtain the optimal policy and slow convergence due to“dimension curse”.

Keywords：reinforcement learning；Option；continuous space；random skill discovery

中圖分類號：TN911?34; TP18

文獻標識碼：A

文章編號：1004?373X（2016）10?0014?04

doi：10.16652/j.issn.1004?373x.2016.10.004

收稿日期：2015?10?22

基金項目：國家自然科學基金項目（61303108；61373094；61472262）；江蘇省高校自然科學研究項目資助（13KJB520020）；吉林大學符號計算與知識工程教育部重點實驗室資助項目（93K172014K04）；江蘇省高等職業(yè)院校國內(nèi)高級訪問學者計劃資助項目（2014FX058）

作者簡介：欒詠紅（1971—），女，青島人，副教授，中國計算機學會（CCF）會員。研究方向為數(shù)據(jù)挖掘和強化學習。劉全（1969—），男，教授，博士，博士生導師，中國計算機學會高級會員。研究領(lǐng)域為智能信息處理、自動推理等。章鵬（1992—），男，碩士研究生。研究方向為強化學習。