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

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

?

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

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

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

關(guān)鍵詞：強(qiáng)化學(xué)習(xí)；Option；連續(xù)空間；隨機(jī)技能發(fā)現(xiàn)

0　引　言

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

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

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

1　分層強(qiáng)化學(xué)習(xí)與Option框架

分層強(qiáng)化學(xué)習(xí)（Hierarchical Reinforcement Learn?ing，HRL）的核心思想是引入抽象機(jī)制對(duì)整個(gè)學(xué)習(xí)任務(wù)進(jìn)行分解。在HRL方法中，智能體不僅能處理給定的原始動(dòng)作集，同時(shí)也能處理高層次技能。

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

簡(jiǎn)單的Option直接定義在MDP上，由三元組o =I，π，β表示。其中s∈I為Option輸入狀態(tài)集，它包含且僅包含Option經(jīng)歷的所有可能狀態(tài)，當(dāng)且僅當(dāng)智能體的當(dāng)前狀態(tài)s∈I時(shí)，Option才可以根據(jù)內(nèi)部策略展開(kāi)執(zhí)行。π:S×A→[0，1]表示Option的內(nèi)部策略；其中AI為I上可以執(zhí)行的動(dòng)作集；β:S→[0，1]是Option結(jié)束的終止判斷函數(shù)，Option在某一狀態(tài)s′依概率β(s′)終止，通常將Option要達(dá)到子目標(biāo)狀態(tài)sG定義為β(sG) = 1。每個(gè)Option在被執(zhí)行時(shí)，動(dòng)作的選擇僅依賴于自身內(nèi)部策略π，即智能體根據(jù)策略π(s，a)選擇下一動(dòng)作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啟動(dòng)后，根據(jù)策略μ依次選擇其他Option執(zhí)行，直到根據(jù)終止條件β結(jié)束，被選中的Option可以按照各自的策略再選擇其他Option執(zhí)行。若將所有Op?tion都展開(kāi)到基本動(dòng)作層，則μ確定了MDP的一個(gè)常規(guī)策略，Sutton稱其為與μ對(duì)應(yīng)的平坦策略，記為flat(μ)。

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

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

式中：r為Option o在整個(gè)執(zhí)行過(guò)程中的累計(jì)折扣獎(jiǎng)賞值。

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

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

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

2.1隨機(jī)Option

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

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

使用標(biāo)準(zhǔn)強(qiáng)化學(xué)習(xí)算法來(lái)學(xué)習(xí)o的策略，采用一個(gè)線性函數(shù)逼近器與一套合適的基函數(shù)來(lái)表示Option的值函數(shù)，如式（3）所示。

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

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

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

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

2.2隨機(jī)技能樹(shù)

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

算法1：Build_a_tree（TS，D）

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

判斷#TS≤nmin成立時(shí)；

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

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

隨機(jī)分割狀態(tài)空間D為兩個(gè)子區(qū)域D1和D2，同時(shí)訓(xùn)練集合TS分割為T(mén)S1和TS2；

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

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

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

2.3RSD算法描述

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

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

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

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

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

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

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

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

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

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

4　結(jié)　語(yǔ)

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

參考文獻(xiàn)

[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ā)式獎(jiǎng)賞函數(shù)的分層強(qiáng)化學(xué)習(xí)方法[J].計(jì)算機(jī)研究與發(fā)展，2011，48（12）：2352?2358.

[11]沈晶，劉海波，張汝波，等.基于半馬爾科夫?qū)Σ叩亩鄼C(jī)器人分層強(qiáng)化學(xué)習(xí)[J].山東大學(xué)學(xué)報(bào)（工學(xué)版），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

中圖分類號(hào)：TN911?34; TP18

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004?373X（2016）10?0014?04

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

收稿日期：2015?10?22

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

作者簡(jiǎn)介：欒詠紅（1971—），女，青島人，副教授，中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）會(huì)員。研究方向?yàn)閿?shù)據(jù)挖掘和強(qiáng)化學(xué)習(xí)。劉全（1969—），男，教授，博士，博士生導(dǎo)師，中國(guó)計(jì)算機(jī)學(xué)會(huì)高級(jí)會(huì)員。研究領(lǐng)域?yàn)橹悄苄畔⑻幚?、自?dòng)推理等。章鵬（1992—），男，碩士研究生。研究方向?yàn)閺?qiáng)化學(xué)習(xí)。