基于改進(jìn)ELM的遞歸最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法及其應(yīng)用

徐圓，黃兵明，賀彥林

?

基于改進(jìn)ELM的遞歸最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法及其應(yīng)用

徐圓，黃兵明，賀彥林

（北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院，北京 100029）

針對值函數(shù)逼近算法對精度及計(jì)算時(shí)間等要求，提出了一種基于改進(jìn)極限學(xué)習(xí)機(jī)的遞歸最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法。首先，將遞推方法引入到最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法中消去最小二乘中的矩陣求逆過程，形成遞推最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法，減少算法的復(fù)雜度及其計(jì)算量。其次，考慮到LSTD(0)算法收斂速度慢，加入資格跡增加樣本利用率提高收斂速度的算法，形成LSTD()算法，以保證在經(jīng)歷過相同數(shù)量的軌跡后能收斂于真實(shí)值。同時(shí)，考慮到大部分強(qiáng)化學(xué)習(xí)問題的值函數(shù)是單調(diào)的，而傳統(tǒng)ELM方法通常運(yùn)用具有雙側(cè)抑制特性的Sigmoid激活函數(shù)，增大了計(jì)算成本，提出采用具有單側(cè)抑制特性的Softplus激活函數(shù)代替?zhèn)鹘y(tǒng)Sigmoid函數(shù)，以減少計(jì)算量提高運(yùn)算速度，使得該算法在提高精度的同時(shí)提高了計(jì)算速度。通過與傳統(tǒng)基于徑向基函數(shù)的最小二乘強(qiáng)化學(xué)習(xí)算法和基于極限學(xué)習(xí)機(jī)的最小二乘TD算法在廣義Hop-world問題的對比實(shí)驗(yàn)，比較結(jié)果證明了所提出算法在滿足精度的條件下有效提高了計(jì)算速度，甚至某些條件下精度比其他兩種算法更高。

強(qiáng)化學(xué)習(xí)；激活函數(shù)；遞歸最小二乘算法；函數(shù)逼近；廣義Hop-world問題

引 言

強(qiáng)化學(xué)習(xí)是由Watkins等[1-3]提出的基于心理學(xué)的一種全新的機(jī)器學(xué)習(xí)算法，其主要思想是通過智能體與環(huán)境的交互與試錯(cuò)，以環(huán)境的反饋信號作為輸入實(shí)現(xiàn)策略的優(yōu)化。實(shí)現(xiàn)策略優(yōu)化需要正確的策略評價(jià)和策略迭代技術(shù)，而如何正確地估計(jì)函數(shù)值是策略評價(jià)的一個(gè)中心問題。強(qiáng)化學(xué)習(xí)通常采用狀態(tài)空間和動(dòng)作空間離散的馬爾可夫決策過程（Markov decision process，MDPs）[4-7]描述，類似于動(dòng)態(tài)規(guī)劃中的策略評價(jià)方法，可采用表格的形式存儲各個(gè)狀態(tài)的值函數(shù)。由于實(shí)際工程中狀態(tài)空間是連續(xù)且規(guī)模較大的，采用表格形式會造成類似動(dòng)態(tài)規(guī)劃的維數(shù)災(zāi)難。因此為了解決這個(gè)問題，必須加強(qiáng)值函數(shù)逼近算法的研究[8-12]。

值函數(shù)逼近方法可實(shí)現(xiàn)在正確估計(jì)值函數(shù)的同時(shí)避免狀態(tài)空間復(fù)雜所引起的維數(shù)災(zāi)難問題。Sutton[2]首次給出了時(shí)序差分強(qiáng)化學(xué)習(xí)算法(temporal difference，TD)，并通過實(shí)驗(yàn)證明了收斂性，已成為其他強(qiáng)化學(xué)習(xí)算法的基礎(chǔ)。隨著人工智能技術(shù)的發(fā)展，近年來越來越傾向于將神經(jīng)網(wǎng)絡(luò)的函數(shù)逼近能力應(yīng)用于強(qiáng)化學(xué)習(xí)值函數(shù)逼近中[13-17]，Bradtke等提出了最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法（least-squares temporal difference learning，LSTD）[18-19]，提高TD算法數(shù)據(jù)利用率的同時(shí)解決了TD算法過程中步長設(shè)計(jì)困難的問題[20]，該算法已成為目前廣泛應(yīng)用的值函數(shù)逼近算法，其中LSTD中采用徑向基函數(shù)（radial basis functions，RBF）作為逼近模型或者其他狀態(tài)回歸方法。但是這類方法大部分都屬于局部逼近，而局部逼近最主要的潛在限制就是隨著輸入空間維度的增加所需要的特征單元是以指數(shù)形式增加的。

基于以上問題，本文提出了一種基于改進(jìn)ELM的遞歸最小二乘差分算法（RLSTD（）-IELM）用于函數(shù)值逼近。一方面，將遞推方法引入到最小二乘算法中，形成遞推最小二乘算法（recursive least-squares temporal difference learning，RLSTD），減少算法的復(fù)雜度及其計(jì)算量。同時(shí)，考慮到LSTD(0)算法收斂速度慢，本文加入資格跡增加樣本利用率提高收斂速度的算法，形成LSTD()算法，以保證在經(jīng)歷過相同數(shù)量的軌跡后能收斂于真實(shí)值。另一方面，由于大部分強(qiáng)化學(xué)習(xí)問題的值函數(shù)是單調(diào)的，在ELM模型結(jié)構(gòu)中，本文采用具有單側(cè)抑制特性的Softplus激活函數(shù)代替?zhèn)鹘y(tǒng)Sigmoid函數(shù)以減少計(jì)算量提高運(yùn)算速度，實(shí)現(xiàn)計(jì)算時(shí)間的降低。最后，本文運(yùn)用廣義Hop-world實(shí)驗(yàn)證明了該算法保證精度的情況下降低了計(jì)算時(shí)間，即提高了資源有效率以及計(jì)算的有效率。

1 基于改進(jìn)ELM的RLSTD（λ）算法

1.1 基于Softplus激活函數(shù)的ELM

極限學(xué)習(xí)機(jī)(ELM)是一種簡單易用、有效的單隱層前饋神經(jīng)網(wǎng)絡(luò)(single-hidden layer feedforward neural networks，SLFNs)學(xué)習(xí)算法[21]。假設(shè)隱含層含有個(gè)單元，則第個(gè)輸出可表示為

其中1≤≤，w為隱含層第個(gè)單元的參數(shù)(權(quán)值和閾值)，h是第個(gè)單元和輸出層連接的權(quán)值，是隱含層激活函數(shù)。

通常，極限學(xué)習(xí)機(jī)隱含層激活函數(shù)采用傳統(tǒng)的Sigmoid函數(shù)，Sigmoid系統(tǒng)在做值判別時(shí)采用雙側(cè)抑制。而大多數(shù)強(qiáng)化學(xué)習(xí)問題中為了更容易得到狀態(tài)集合中每個(gè)狀態(tài)的值函數(shù)通常設(shè)定在未到達(dá)目標(biāo)點(diǎn)之前，根據(jù)策略每采取一個(gè)動(dòng)作，環(huán)境反饋的賞金為負(fù)(正)，而到達(dá)目標(biāo)時(shí)為0，因此值函數(shù)的值通常都為負(fù)或都為正。例如，廣義Hop-world問題的值函數(shù)逼近值是單調(diào)的，若采用雙側(cè)抑制將會增加廢運(yùn)算，由此只需要單邊抑制就足夠了。因此，本文提出采用Softplus函數(shù)替換Sigmod函數(shù)，該激活函數(shù)模型對比Sigmoid模型主要變化有3點(diǎn)：單側(cè)抑制，相對寬闊的興奮邊界以及稀疏激活性。Softplus函數(shù)[22]是ReLu函數(shù)的改進(jìn)，因此它一方面有ReLu函數(shù)運(yùn)算速度快，泛化性能好的特點(diǎn)，另一方面它比傳統(tǒng)的Sigmoid函數(shù)更加接近生物學(xué)激活模型，從而使整個(gè)網(wǎng)絡(luò)模型的平均性能更好。這兩點(diǎn)對算法的兩個(gè)評估標(biāo)準(zhǔn)都有所增益，可增加計(jì)算效率，減少計(jì)算時(shí)間。

Softplus函數(shù)定義為

=ln(1+e) (2)

1.2 遞歸LSTD()-IELM強(qiáng)化學(xué)習(xí)算法

傳統(tǒng)值函數(shù)逼近算法中，例如LSTD-RBF強(qiáng)化學(xué)習(xí)算法，雖然提高了值函數(shù)逼近的精度但是同時(shí)也增加了計(jì)算復(fù)雜度降低了計(jì)算速率，本文結(jié)合1.1節(jié)提出的基于Softplus激活函數(shù)的ELM模型，提出一種帶有資格跡的遞推最小二乘強(qiáng)化學(xué)習(xí)算法(RLSTD())。

強(qiáng)化學(xué)習(xí)問題通?？梢员磉_(dá)成馬可爾夫決策過程(MDP)[23]。MDP模型可以定義為集合{,,,,}，是狀態(tài)集合，為動(dòng)作集合，為賞金函數(shù)即在狀態(tài)s時(shí)執(zhí)行動(dòng)作轉(zhuǎn)移到狀態(tài)s+1得到的反饋信號，為狀態(tài)轉(zhuǎn)移概率函數(shù)即在狀態(tài)s時(shí)執(zhí)行動(dòng)作轉(zhuǎn)移到狀態(tài)s+1，為值函數(shù)。MDP的策略定義為從狀態(tài)空間到動(dòng)作空間的映射：，當(dāng)確定時(shí)，且定義轉(zhuǎn)移函數(shù)為1時(shí)，值函數(shù)()就是在狀態(tài)下執(zhí)行動(dòng)作且以后遵循策略的累積期望折扣回報(bào)，可由式（3）表達(dá)

設(shè)定′為狀態(tài)下執(zhí)行動(dòng)作轉(zhuǎn)移的下一個(gè)狀態(tài)，那么式（4）同樣可以定義為

V()=+V(′) (4)

其中為折扣因子，當(dāng)狀態(tài)空間很小時(shí)，采用表格的形式存儲各個(gè)狀態(tài)的值函數(shù)。但是當(dāng)狀態(tài)空間連續(xù)或者維度很大時(shí)想要得到每個(gè)狀態(tài)確切的值函數(shù)的值很困難，這種情況下就要采用函數(shù)值逼近算法來估計(jì)值函數(shù)的值[8,24]。

假設(shè)有一個(gè)被維的向量參數(shù)化的值函數(shù)逼近模型，那么這個(gè)逼近模型與式(3)相結(jié)合，可以表達(dá)為

=() (5)

()=[()]() (6)

由于線性的參數(shù)逼近模型有一定的理論基礎(chǔ)，所以文中采用線性參數(shù)逼近模型。模型采用個(gè)特征單元或者基本函數(shù)1,…,:和一個(gè)維參數(shù)向量，狀態(tài)的值可計(jì)算為

其中，()=[1(),…,()]，即為特征單元向量。

根據(jù)傳統(tǒng)時(shí)序差分法(TD(0))迭代公式可表示為

式中，表示執(zhí)行策略的第步，r+1是觀測到的賞金值，為折扣因子，為學(xué)習(xí)速率。

TD(0)算法必然收斂但是存在收斂速度慢的問題，最主要原因是它只修改相鄰狀態(tài)的值函數(shù)估計(jì)值，這就減少了樣本利用率。本文引入資格跡以提高收斂速度和樣本利用率，即為TD()算法，迭代公式為

其中，(s)被稱為資格跡，可由式（10）計(jì)算得到

(10)

因此算法的更新原則為

在經(jīng)歷過軌跡(0,1,…,s)，根據(jù)式(11)可以觀察到總的變化，可表達(dá)為

=+(++) (12)

式中，為平均噪聲。因此收斂于滿足式+TD=0的TD。

最小二乘時(shí)序差分法(LSTD)同樣收斂于滿足上面條件的TD，LSTD中構(gòu)造的矩陣(×維)和向量(維)可表示為

經(jīng)歷過個(gè)獨(dú)立軌跡之后，矩陣和向量為和-的無偏差估計(jì)，因此TD可由-1計(jì)算得到。

結(jié)合1.1節(jié)提出的基于Softplus激活函數(shù)的ELM，定義特征單元空間為

()=[(1,),(2,),…,(,)] (14)

因此結(jié)合式(11)～式(13)得到LSTD()-ELM算法的迭代公式

←(s)+(15)

←+((s)-(s+1))T(16)

=-1(17)

一般情況下LSTD算法求解過程采用的是高斯消除法或者奇異值分解來求-1，但是這兩種方法的復(fù)雜度為0(3)。當(dāng)數(shù)據(jù)維度增大或者特征單元增多時(shí)，計(jì)算量和計(jì)算時(shí)間也會以指數(shù)形式上升。所以本文引入了遞歸最小二乘的概念，來提高計(jì)算速度以及實(shí)時(shí)處理能力。

根據(jù)矩陣求逆定理，當(dāng)∈×n,∈×1,∈1×n且可逆時(shí)，有

(+)-1=-1--1(+-1)-1(18)

則根據(jù)文中狀態(tài)變化可以推導(dǎo)得到遞歸最小二乘更新原則

(20)

此方法消除了矩陣的求逆過程，因此復(fù)雜度相比LSTD-ELM算法，由0(3)降為0(2)，有效提高了計(jì)算速度。

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

本文采用廣義Hop-world問題驗(yàn)證RLSTD()- IELM算法的有效性，并與LSTD-ELM算法、LSTD-RBF算法進(jìn)行比較。由于廣義Hop-world的狀態(tài)空間維度是可以隨意選擇的，所以該實(shí)驗(yàn)很適合評估當(dāng)狀態(tài)變量增加時(shí)各算法的表現(xiàn)。實(shí)驗(yàn)中采用平均絕對誤差和計(jì)算時(shí)間作為算法比較的指標(biāo)。

2.1 廣義Hop-world問題

Hop-world問題最初提出[25]是為了進(jìn)行說明性實(shí)驗(yàn)，后來被應(yīng)用于其他強(qiáng)化學(xué)習(xí)實(shí)驗(yàn)中。圖1為該問題的最初模型，狀態(tài)空間是一維且離散的。如圖1所示，此模型由個(gè)離散狀態(tài)和一個(gè)結(jié)束狀態(tài)構(gòu)成，狀態(tài)空間表示為={0,1,2,…,}。對于每個(gè)軌跡而言，初始狀態(tài)為狀態(tài)0，結(jié)束狀態(tài)為狀態(tài)。當(dāng)前狀態(tài)不為目標(biāo)狀態(tài)時(shí)可以采取兩個(gè)動(dòng)作={0,1}，每一個(gè)動(dòng)作都朝著目標(biāo)狀態(tài)前進(jìn)。狀態(tài)-1到狀態(tài)產(chǎn)生的賞金值為-2/3，其他狀態(tài)轉(zhuǎn)移產(chǎn)生的賞金值為-1。實(shí)驗(yàn)中agent選擇兩個(gè)動(dòng)作的概率是相同的。

而廣義Hop-world問題，其狀態(tài)空間維度是可變的，即為狀態(tài)數(shù)可變的Hop-world問題。參數(shù)表示狀態(tài)空間維度，圖2為狀態(tài)空間維度為2時(shí)的Hop-world問題模型。狀態(tài)個(gè)數(shù)由||=m得到，可選動(dòng)作個(gè)數(shù)由||=2得到。賞金函數(shù)與一維Hop-world問題模型相同。

多維廣義Hop-world問題的狀態(tài)由最初的離散狀態(tài)轉(zhuǎn)移為位于范圍[0,1]的連續(xù)狀態(tài)，但對于每一維它們依舊有2種動(dòng)作可以選擇，使得當(dāng)前狀態(tài)向目標(biāo)狀態(tài)轉(zhuǎn)移，只是此時(shí)動(dòng)作選擇為1倍步長和2倍步長。二維Hop-world問題將起始點(diǎn)和目標(biāo)點(diǎn)設(shè)置在狀態(tài)空間的兩端，即圖3中的0=[0,0]，END=[1,1]，而圖中帶有箭頭的折線就是二維廣義Hop-world問題中的一條典型的軌跡，其中短箭頭代表一倍步長，長箭頭代表兩倍步長。

本文實(shí)驗(yàn)中廣義Hop-world的維度從1變化到3，為了保證每條軌跡的步數(shù)是合理的，其中步長參數(shù)根據(jù)維度的變化而改變，表1列出了3種不同維度對應(yīng)的步長并且本文設(shè)定每種動(dòng)作帶有0.2倍步長的高斯噪聲以增加系統(tǒng)的隨機(jī)性。而智能體與環(huán)境交互的質(zhì)量是由經(jīng)過的軌跡數(shù)控制的。為了得到更精準(zhǔn)的值函數(shù)逼近值，隨著維度的增加軌跡的數(shù)量也必須增加，表1列出了3種不同維度的Hop-world問題所需要的軌跡數(shù)，文中RLSTD- IELM、LSTD-ELM以及LSTD-RBF算法采用相同的軌跡數(shù)。

2.2 Monte Carlo仿真

Monte Carlo實(shí)驗(yàn)中，在待仿真的狀態(tài)集合中任意取一個(gè)狀態(tài)作為初始狀態(tài)，觀測經(jīng)歷不同軌跡后的反饋值，將所有反饋值取平均值即得到該狀態(tài)值函數(shù)的仿真值。文中采用Monte Carlo仿真實(shí)驗(yàn)的仿真值作為“真實(shí)值”，值函數(shù)逼近值與其作比較得到絕對誤差。Monte Carlo仿真實(shí)驗(yàn)仿真結(jié)果如圖4。

表1 不同維度Hop-world實(shí)驗(yàn)中LSTD算法的各個(gè)參數(shù)

圖4給出了1維Hop-world問題中=0.30，=0.57和=0.90時(shí)Monte Carlo仿真的情況，縱坐標(biāo)表示值函數(shù)仿真值，橫坐標(biāo)表示軌跡數(shù)量。圖中描繪了隨著仿真過程中軌跡數(shù)量的增加得到的估計(jì)值以及95%的置信空間。由圖4可以看到在經(jīng)歷過16000個(gè)軌跡之后，()的估計(jì)值基本保持穩(wěn)定，后面就是重復(fù)相同的步驟達(dá)到固定的軌跡數(shù)。除了定義保證仿真精度軌跡數(shù)之外，必須定義需要仿真的狀態(tài)集合。一方面狀態(tài)集合足夠大，可以表達(dá)所有值函數(shù)；另一方面，狀態(tài)集合要足夠小，可以控制計(jì)算量。3種不同維度的Monte Carlo仿真的軌跡數(shù)量和狀態(tài)集合參數(shù)列于表2。

表2 不同維度廣義Hop-world實(shí)驗(yàn)中Monte Carlo仿真的各個(gè)參數(shù)

2.3 結(jié)果與分析

首先，采用一維Hop-world問題驗(yàn)證基于Softplus激活函數(shù)的ELM相比于基于傳統(tǒng)激活函數(shù)的ELM算法可增加計(jì)算效率，減少計(jì)算時(shí)間。結(jié)合LSTD計(jì)算一條有效軌跡時(shí)間，對比結(jié)果如圖5。

從圖5可看出，基于Softplus激活函數(shù)的LSTD-IELM算法其時(shí)間效率明顯比傳統(tǒng)LSTD-ELM算法高，達(dá)到了減少計(jì)算時(shí)間的目的。

同時(shí)，本文將所提算法與LSTD-RBF算法、LSTD-ELM結(jié)果進(jìn)行對比，驗(yàn)證所提方法的可行性與優(yōu)越性。由于文中LSTD-RBF算法基函數(shù)采用高斯函數(shù)，因此高斯函數(shù)中心點(diǎn)位置()以及寬度()兩個(gè)參數(shù)對算法的結(jié)果有很大的影響。文中采用k-means算法[26]來確定參數(shù)，為了確定參數(shù)，根據(jù)文獻(xiàn)[27]，可以將寬度定義為

是中心點(diǎn)個(gè)數(shù)，max是任意兩個(gè)中心點(diǎn)之間最大的距離。根據(jù)文獻(xiàn)[28-29]，當(dāng)寬度設(shè)置為0.5max和0.33max能得到較好的效果。為了將最好的結(jié)果與本文中所提出算法進(jìn)行比較，將這3種寬度設(shè)置為一個(gè)集合set={Hay,Alp1,Alp2}，并將set，2set，4set一共9種情況都進(jìn)行測試找出效果最好的一個(gè)。

通過一維Hop-world實(shí)驗(yàn)和對比，當(dāng)=4Alp1時(shí)表現(xiàn)出來的效果最好。因此，在下面的比較實(shí)驗(yàn)中，定義=4Alp1。一維Hop-world實(shí)驗(yàn)中，LSTD-RBF、LSTD-ELM以及RLSTD()-IELM算法比較結(jié)果如圖6、圖7所示。

圖6表示一維Hop-world問題中當(dāng)寬度為=4Alp1的LSTD-RBF算法，LSTD-ELM算法，RLSTD()-IELM算法在單元個(gè)數(shù)從5變化到45時(shí)的估計(jì)值平均絕對誤差曲線，圖7表示3種算法分別在一維實(shí)驗(yàn)中單元個(gè)數(shù)增加時(shí)每步算法完成需要的時(shí)間曲線?？梢钥闯鯨STD-ELM算法與RLSTD()-IELM算法估計(jì)值的平均誤差曲線幾乎重疊，而很明顯都小于LSTD-RBF算法，所以在精度上本文所提出的算法是滿足要求的。而從時(shí)間曲線上可以看出RLSTD()-IELM算法比LSTD-RBF高，比LSTD-ELM低。因此可以看出本文所提算法在計(jì)算速度和計(jì)算精度上都有優(yōu)異的表現(xiàn)。

二維Hop-world問題實(shí)驗(yàn)結(jié)果對比如圖8、圖9所示。

從平均絕對誤差上來看，在單元個(gè)數(shù)增加到50之前，本文所提算法精度高于其他兩種算法，單元個(gè)數(shù)增加到50之后估計(jì)值平均絕對誤差雖然略高于LSTD-ELM算法但仍明顯低于LSTD-RBF算法。而從計(jì)算時(shí)間上來看，在單元個(gè)數(shù)增加為80之后低于其他兩種算法，所以該算法在某種特定條件下可以做到精度高于LSTD-ELM算法，計(jì)算速度高于LSTD-RBF算法。從一維和二維實(shí)驗(yàn)已經(jīng)證明該算法的優(yōu)勢，為了證明其可解決高維問題作了三維廣義Hop-world實(shí)驗(yàn)，即定義=3。

圖10、圖11為三維Hop-world問題實(shí)驗(yàn)比較結(jié)果。

圖10 三維Hop-world問題中RLSTD(λ)-IELM、LSTD-ELM以及LSTD-RBF 3種算法隨單元個(gè)數(shù)增加時(shí)的估計(jì)值平均絕對誤差曲線對比(d=3, l =0.85)

結(jié)合上述一維、二維、三維Hop-world問題上的對比實(shí)驗(yàn)，3種算法在不同單元個(gè)數(shù)對應(yīng)的估計(jì)精度及計(jì)算時(shí)間如表3所示。

表3 不同維度廣義Hop-world實(shí)驗(yàn)中RLSTD(λ)-IELM、LSTD-ELM以及LSTD-RBF 3種算法對比

當(dāng)維度增加為3時(shí)本文所提算法的優(yōu)勢也越來越明顯，無論在精度和計(jì)算速度上都有優(yōu)異的表現(xiàn)。表3表示一維廣義Hop-world實(shí)驗(yàn)中取特征單元個(gè)數(shù)為10、15、20、25，二維廣義Hop-world實(shí)驗(yàn)中取特征單元個(gè)數(shù)為60、70、80、90，以及三維廣義Hop-world實(shí)驗(yàn)中取特征單元個(gè)數(shù)為300、350、400、450時(shí)L(LSTD)，RL-IE（RLSTD()-IELM）以及L-E（LSTD-ELM）3種算法分別在平均絕對誤差以及計(jì)算時(shí)間兩個(gè)指標(biāo)上表現(xiàn)結(jié)果的對比。通過結(jié)果的對比可以看出，RLSTD()-IELM算法在達(dá)到相同精度時(shí)所需要的資源少于LSTD-RBF算法，而在時(shí)間上來說隨著維度和單元個(gè)數(shù)的增加，本文所提算法顯示出的優(yōu)勢越來越明顯，計(jì)算速度高于其他兩種算法，證明了該算法的可行性和優(yōu)越性。

3 結(jié) 論

本文針對值函數(shù)逼近算法對精度和計(jì)算時(shí)間等要求，提出了一種基于改進(jìn)極限學(xué)習(xí)機(jī)的遞歸最小二乘時(shí)序差分強(qiáng)化學(xué)習(xí)算法(RLSTD()-IELM)。在廣義Hop-wprld實(shí)驗(yàn)中與傳統(tǒng)LSTD-RBF算法和LSTD-ELM算法進(jìn)行比較，隨著單元個(gè)數(shù)的增加，本文所提算法在提高樣本利用率的同時(shí)減少了算法復(fù)雜度，減少了計(jì)算量從而提高了計(jì)算速度。在低維廣義Hop-world問題實(shí)驗(yàn)中，本文算法在精度上高于傳統(tǒng)LSTD-RBF算法甚至在某種條件下高于LSTD-ELM算法，在計(jì)算速度上高于LSTD-ELM。在高維廣義Hop-world問題實(shí)驗(yàn)中，結(jié)果表明在解決高維度問題上文中所提算法表現(xiàn)更優(yōu)于其他算法，有效證明了本文算法的可行性和優(yōu)越性。

References

[1] WATKINS J C H, DAYAN P. Q-learning[J]. Machine Learning, 1992, 8(1): 279-292.

[2] SUTTON R S. Learning to predict by the methods of temporal differences[J]. Machine Learning, 1998, 3: 10-43.

[3] SUTTON R S, BARTO A G. Reinforcement learning: an introduction[J]. IEEE Transactions on Neural Networks, 1998, 9(5): 1054.

[4] ETESSAMI K, YANNAKAKIS M. Recursive Markovdecision processes and recursive stochastic games[J]. Journal of the Acm, 2005, 62(2): 100.

[5] DUFOUR F. Impulsive control for continuous-time Markov decision processes[J]. Advances in Applied Probability, 2014, 47(1): 129-161.

[6] HALLAK A, CASTRO D D. Contextual Markov decision processes [J]. Computer Science, 2015, 5(4): 220-229.

[7] BEATRIC B, KRISHNENDU C. Probabilistic opacity for Markov decision processes[J]. Information Processing Letters, 2015, 115(1): 52-59.

[8] 劉全, 肖飛. 基于自適應(yīng)歸一化RBF網(wǎng)絡(luò)的Q-V值函數(shù)協(xié)同逼近模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(7): 1386-1396. LIU Q, XIAO F. Collaborative Q-V value function approximation model based on adaptive normalized radial basis function network[J]. Chinese Journal of Computers, 2015, 38(7): 1386-1396.

[9] HACHIYA H, AKIYAMA T, SUGIAYMA M,. Adaptive importance sampling for value function approximation in off-policy reinforcement learning[J]. Neural Networks the Official Journal of the International Neural Network Society, 2009, 22(10): 1399-1410.

[10] AKIYAMA T, HACHIYA H M. Efficient exploration through active learning for value function approximation in reinforcement learning[J]. Neural Networks the Official Journal of the International Neural Network Society, 2010, 23(5): 639-648.

[11] XU X, HUANG Z. A clustering-based graph Laplacian framework for value function approximation in reinforcement learning[J]. Cybernetics, 2014, 44(12): 2613-2625.

[12] ELFWING S, UCHIBE E. From free energy to expected energy: improving energy-based value function approximation in reinforcement learning[J]. Neural Networks, 2016, 84: 17-27.

[13] WANG X S, CHENG Y H, YI J Q. A fuzzy actor-critic reinforcement learning network[J]. Information Sciences, 2007, 177(18): 3764-3781.

[14] YAVUZ E, MAUL P, NOWOTNY T. Spiking neural network model of reinforcement learning in the honeybee implemented on the GPU[J]. Bmc Neuroscience, 2015, 16(S1): 1-2.

[15] FAU?ER S, SCHWENKER F. Selective neural network ensembles in reinforcement learning: taking the advantage of many agents[J]. Neurocomputing, 2015, 169: 350-357.

[16] TANG L, LIU Y J. Adaptive neural network control of robot manipulator using reinforcement learning[J]. Journal of Vibration & Control, 2013, 20(14): 2162-2171.

[17] 蓋俊峰, 趙國榮. 基于線性近似和神經(jīng)網(wǎng)絡(luò)逼近的模型預(yù)測控制[J]. 系統(tǒng)工程與電子技術(shù), 2015, 37(2): 394-399. GAI J F, ZHAO G R. Model predictive control based on linearization and neural network approach[J]. Systems Engineering and Electronics, 2015, 37(2): 394-399.

[18] BRADTKE S J, BARTO A G. Linear least-squares algorithms for temporal difference learning[J]. Machine Learning, 1996, 22(1/2/3): 33-57.

[19] BOYAN J A. Technical update: least-squares temporal difference learning[J]. Machine Learning, 2002, 49(2/3): 233-246.

[20] 王國芳, 方舟. 基于批量遞歸最小二乘的自然Actor-Critic算法[J]. 浙江大學(xué)學(xué)報(bào), 2015, 49(7): 1335-1341. WANG G F, FANG Z. Natural Actor-Critic based on batch recursive least-squares[J]. Journal of Zhejiang University (Engineering Science), 2015, 49(7): 1335-1341.

[21] HUANG G, ZHU Q. Extreme learning machine: theory and applications[J]. Neurocomputing, 2006, 70: 489-501.

[22] 孫艷豐, 楊新東. 基于Softplus激活函數(shù)和改進(jìn)Fisher判別的ELM算法[J]. 北京工業(yè)大學(xué)學(xué)報(bào), 2015, 41(9): 1341-1347.SUN Y F, YANG X D. ELM algorithm based on Softplus activation function and improved Fisher discrimination[J]. Journal of Beijing University of Technology, 2015, 41(9): 1341-1347.

[23] 高陽, 陳世福, 陸鑫. 強(qiáng)化學(xué)習(xí)研究綜述[J]. 自動(dòng)化學(xué)報(bào), 2004, 30(1): 86-100.GAO Y, CHEN S F, LU X. Research on reinforcement learning technology: a review[J]. Acta Automatica Sinica, 2004, 30(1): 86-100.

[24] PABLO E M, JOSE M M. Least-squares temporal difference learning based on an extreme learning machine[J]. Neurocomputing, 2014, 14: 37-45.

[25] BOYAN J A. Least-squares temporal difference learning in proceedings of the sixteenth international conference[J]. Machine Learning, 1999, 49(2/3): 49-56.

[26] WANG J F, WANG J D, SONG J K. Optimized Cartesian k-means[J]. IEEE Transactions on Knowledge & Data Engineering, 2015, 27(1): 180-192.

[27] HAYKIN S. Neural Networks and Learning Machines: A Comprehensive Foundation[M]. London: Pearson Education, 2010: 800-815.

[28] ALPAYDIN E. Introduction to machine learning[J]. Machine Learning, 2004, 5(8): 28.

[29] ZHAO J, WEI H. Natural gradient learning algorithms for RBF networks[J]. Neural Computation, 2015, 27(2): 481-505.

Recursive least-squares TD () learning algorithm based on improved extreme learning machine

XU Yuan, HUANG Bingming, HE Yanlin

(School of Information Science & Technology, Beijing University of Chemical Technology, Beijing 100029, China)

To meet the requirements on accuracy and computational time of value approximation algorithms, a recursive least-squares temporal difference reinforcement learning algorithm with eligibility traces based on improved extreme learning machine (RLSTD()-IELM) was proposed. First, a recursive least-squares temporal difference reinforcement learning (RLSTD) was created by introducing recursive method into least-squares temporal difference reinforcement learning algorithm (LSTD), in order to eliminate matrix inversion process in least-squares algorithm and to reduce complexity and computation of the proposed algorithm. Then, eligibility trace was introduced into RLSTD algorithm to form the recursive least-squares temporal difference reinforcement learning algorithm with eligibility trace (RLSTD()), in order to solve issues of slow convergence speed of LSTD(0) and low efficiency of experience exploitation. Furthermore, since value function in most reinforcement learning problem was monotonic, a single suppressed approximation Softplus function was used to replace sigmoid activation function in the extreme learning machine network in order to reduce computation load and improve computing speed. The experiment result on generalized Hop-world problem demonstrated that the proposed algorithm RLSTD()-IELM had faster computing speed than the least-squares temporal difference learning algorithm based on extreme learning machine (LSTD-ELM), and better accuracy than the least-squares temporal difference learning algorithm based on radial basis functions (LSTD-RBF).

reinforcement learning; activation function; recursive least-squares methods; function approximation; generalized Hop-world problem

10.11949/j.issn.0438-1157.20161555

TP 29

A

0438—1157（2017）03—0916—09

國家自然科學(xué)基金項(xiàng)目(61573051，61472021)；軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室開放課題(SKLSDE-2015KF-01)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(PT1613-05)。

2016-11-03收到初稿，2016-11-08收到修改稿。

聯(lián)系人：賀彥林。第一作者：徐圓（1983—），女，博士，副教授。

2016-11-03.

HE Yanlin, associate professor, xyfancy@ 163. com

supported by the National Natural Science Foundation of China (61573051, 61472021), the Open Fund of the State Key Laboratory of Software Development Environment (SKLSDE-2015KF-01) and the Fundamental Research Funds for Central Universities of China (PT1613-05).