非參數化近似策略迭代并行強化學習算法

季 挺,張 華

(南昌大學 江西省機器人與焊接自動化重點實驗室,南昌 330031)

0 概述

近似策略迭代強化學習通過近似計算更新當前的值函數評估策略,并采用貪心方法來改進策略,其是解決傳統強化學習“維數災難”問題的主要方法之一。文獻[1]證明近似策略迭代方法的收斂性,并提出LSPI算法,但該算法為離線算法,計算量較大、收斂速度較慢。文獻[2]提出online LSPI算法,以解決LSPI的在線計算問題。文獻[3]在online LSPI的基礎上提出BLSPI算法,該算法進一步提高了樣本利用率,并在一定程度上降低了計算量,但其依然未能徹底解決在線近似策略迭代強化學習收斂速度較慢的問題。此外,在以上算法中,強化學習的結構、參數均依賴先驗知識或通過反復試湊來確定,使算法不具備自動構建的能力。

并行強化學習是解決經典強化學習算法收斂速度較慢問題的途徑之一。本文將并行強化學習與近似策略迭代強化學習相結合,提出一種非參數化近似策略迭代并行強化學習算法NPAPI-P。將NPAPI-P 算法應用于一級倒立擺平衡控制問題,并通過仿真驗證該算法的有效性和快速收斂能力。

1 并行強化學習

并行強化學習與多智能體強化學習對目標任務分而治之,通過強化學習單元(以下簡稱為學習單元)相互協作提升學習性能的思路不同,其學習單元之間互不影響、各自獨立地在整個狀態空間進行學習[4-5],通過對各單元經驗地融合來加快學習的收斂速度。

文獻[4]對并行強化學習進行了開創性的研究,其采用delta規則實現單個學習單元,采用經驗加權法進行各單元的融合及融合信息的反饋,它的研究成果被用于解決多臂老虎機問題。文獻[6]遵循文獻[4]的研究思路,將并行強化學習用于解決海星機器人沿單軸前進的問題,所不同的是,其采用異步更新的方式實現各學習單元的融合以及融合信息反饋。文獻[7]依舊采用文獻[4]的思路,將并行強化學習用于解決網格尋徑問題,所不同的是,其學習單元采用貝葉斯強化學習算法實現。文獻[8]提出的并行強化學習方法采用Q學習算法實現單個學習單元,采用D-S證據理論對各單元進行融合,融合信息直接反饋成為各單元的策略,同時提出加速比和效率的概念作為評價并行強化學習方法性能的指標,其研究成果被用于解決網格尋徑和機器人避障問題。文獻[9]提出的并行強化學習方法采用Q學習算法實現單個學習單元,采用全局Q表融合各單元的信息,且融合信息不反饋至單個單元,該算法被用來解決交通控制問題并取得了較好的效果。文獻[10-11]提出的并行強化學習方法采用近似SARSA(λ)算法實現單個學習單元,采用部分參數異步更新的方式實現各單元的融合以及融合信息的反饋,其研究成果用于解決網格尋徑、Mountain Car和倒立擺控制問題。 文獻[12]提出的并行強化學習方法采用BP神經網絡實現單個Q學習單元,采用D-S證據理論對各單元進行融合,其研究成果被用于解決路徑規劃問題。

綜上所述,近年來,對并行強化學習的研究較少,多數只用于解決小規模、離散狀態和動作空間中的問題,且并行學習單元數量均需人工確定。

2 NPAPI-P算法結構及其學習步驟

NPAPI-P算法網絡結構由狀態輸入層、學習單元層、票箱層和動作輸出層構成,如圖1所示。

圖1 NPAPI-P算法網絡結構

Σk=ΣPOk

(1)

動作輸出層輸出當前狀態S′下應執行的動作A′,A′采用貪心策略定義為:

(2)

NPAPI-P算法運行時,所有單元獨立地在整個狀態動作空間中進行學習,且各單元在每次嘗試結束后進行一次聯合嘗試,以加快強化學習的收斂速度。NPAPI-P算法具體步驟如下:

步驟1設置強化學習的允許誤差率ε。

步驟2通過學習單元構建樣本采集過程,以確定單元數量,通過學習單元自動構建過程來生成所有學習單元。

步驟3各單元通過學習單元自主學習過程分別進行一次嘗試,若有單元嘗試成功,則該單元策略為算法整體策略,算法結束。否則執行步驟4。

步驟4所有單元進行一次聯合嘗試。聯合嘗試通過式(1)融合所有學習單元的策略,通過式(2)選擇算法在當前狀態S′下應執行的動作A′,但并不更新各學習單元的參數。若聯合嘗試成功,則各單元聯合策略為算法整體策略,算法結束。否則執行步驟3。

3 學習單元數量確定

在并行算法中,并行單元數量決定了算法的加速比和效率,若并行單元數量較少會使得加速比較低,若數量過多則容易導致算法效率下降,因此,選擇合適的學習單元數量是并行強化學習的關鍵。本文依據強化學習的允許誤差率ε,通過學習單元構建樣本采集過程以確定強化學習單元的數量。學習單元構建樣本采集過程分為局部過程和總體過程2個方面。

3.1 局部過程

局部過程依據預先設置的ε為單個單元自動采集用于單元構建的狀態樣本,其步驟如下:

步驟1采用隨機策略運行一次目標系統。設置采樣次數tm=1,目標系統運行次數tr=1,采樣緩存長度L=step,其中,step為目標系統本次運行持續的時間步數。將本次采樣得到的樣本集合記為samtm,通過式(3)和式(4)分別計算其均值meantm及其在各維分量上的平均絕對離差向量madtm。

(3)

(4)

其中,ns為samtm中樣本的數量,abs()用于計算向量在各維分量上的絕對值。

步驟2開始單次采樣。tm=tm+1,初始化單次采樣,新增非重復樣本數量ln=0,使temp=samtm-1。

步驟3采用隨機策略運行一次目標系統。tr=tr+1,收集本次運行采集到的樣本集合Tsam,同時更新step和rep的值,其中,rep為Tsam與temp中重復樣本的數量。

步驟4使temp=temp∪Tsam,更新ln與L的值。

ln=ln+step-rep

(5)

(6)

若ln

步驟5通過式(3)和式(4)計算meantm和madtm。

步驟6通過式(7)計算samtm相對samtm-1的變化率rate,rate隨samtm對樣本空間覆蓋率的提升而逐漸減小。

rate=‖(rate1,rate2,…,ratei,…,raten)‖2

(7)

fbcl={fci,bci,fli,bli}

fc=meantm-madtm

bc=meantm+madtm

fl=meantm-1-madtm-1

bl=meantm-1+madtm-1

步驟7若rate<ε,獲得一個單元的構建樣本集sam=samtm,局部過程結束。否則,執行步驟2。

3.2 總體過程

總體過程依據ε來確定學習單元數量,其步驟如下:

步驟1新增一個學習單元,使單元數NU=1。通過局部過程獲取其構建樣本集sam,并初始化總體樣本集SAMNU=sam,通過式(3)和式(4)分別計算SAMNU的均值MEANNU及其在各維分量上的平均絕對離差向量MADNU。

步驟2新增一個學習單元,使單元數NU=NU+1。通過局部過程獲取其構建樣本集sam,使SAMNU=SAMNU-1∪sam。

步驟3通過式(3)和式(4)計算MEANNU和MADNU。

步驟4通過式(7)計算SAMNU相對SAMNU-1的變化率RATE,RATE隨SAMNU對樣本空間覆蓋率的提升而逐漸減小。

步驟5若RATE<ε,學習單元不再增加,總體過程結束。否則,執行步驟2。

4 學習單元結構

學習單元由在線近似策略迭代強化學習算法實現,其網絡結構由狀態輸入層、Q值函數逼近器和動作選擇器組成,如圖2所示。

圖2 學習單元網絡結構

4.1 狀態輸入層

4.2 Q值函數逼近器

Q值函數逼近器由基于RBF(Radial Basis Function )的線性逼近結構實現,狀態動作對(S,A)對應的近似Q值計算公式如式(8)所示。

Q(S,A)=ΦT(S)ω(A)

(8)

其中,Φ(S)=(Φ1(S),Φ2(S),…,Φj(S),…,Φm(S))T為狀態S在各基函數下的歸一化隸屬度向量,其元素定義為:

(9)

其中,φ(S)=(φ1(S),φ2(S),…,φj(S),…,φm(S))T為逼近器的狀態基函數向量,其值為狀態S在各狀態基函數下的隸屬度,m為φ(S)的維數。φ(S)的元素使用RBF函數定義為:

(10)

其中,μj=(μ1j,μ2j,…,μij,…,μnj)T和δj=(δ1j,δ2j,…,δij,…,δnj)T分別為基函數φj的中心和半徑,μij和δij分別為φj在第i維狀態分量上的中心和半徑。

ω=(ω1,ω2,…,ωj,…,ωm)T為逼近器的插值參數向量,其意義為在各狀態基函數中心執行所選動作A的Q值,ω的元素利用插值方法[13]定義為:

(11)

(12)

其中,η為Q值函數逼近器的平均學習率,由學習單元的初始狀態基函數構建過程確定,Δ為TD誤差,定義為:

(13)

其中,rt為即時獎勵,γ為折扣率。

狀態基函數向量φ的參數和維數、插值參數向量ω的維數由Q值函數逼近器自動構建過程依據采樣樣本確定,并在學習過程中自適應調整。

4.3 動作選擇器

動作選擇器采用貪心策略定義為:

(14)

其中,POk是學習單元對在當前狀態S下執行動作ak的投票結果,其計算表達式為:

(15)

5 學習單元自動構建過程

學習單元自動構建過程的核心是構建Q值函數逼近器,其由核心狀態聚類生成過程和初始狀態基函數構建過程組成。

5.1 核心狀態聚類生成

核心狀態聚類生成過程基于相對準則和輪廓指標,采用K均值聚類算法實現,其目的是為構建初始狀態基函數提供初值,具體步驟如下:

(16)

步驟2遍歷num,對當前遍歷的聚類數numv運行K均值聚類算法,得到聚類結果clusv及其相應的聚類有效性valv,valv采用輪廓指標[15]計算,如下:

(17)

步驟3若num遍歷結束,則通過式(18)輸出sam的最佳聚類結果CLU,并將CLU作為核心狀態聚類,執行步驟4。否則,執行步驟2。

CLU=clusID

(18)

步驟4計算CLU中每個聚類的中心和半徑,并將其存入核心聚類中心矩陣cen和半徑矩陣rad中。CLU中單個聚類C的中心Cc為C中所有元素的均值,通過式(19)計算;半徑Cr為C中每個元素與其中心Cc在各維分量上的距離均值向量,通過式(20)計算。

(19)

(20)

其中,Cz為聚類C中的一個元素,nc為聚類C中元素的數量。

5.2 初始狀態基函數構建

狀態基函數的形式如式(10)所示。為提升狀態基函數對樣本空間的覆蓋率,使其盡可能完整地反映狀態空間的分布,本文提出一種以樣本空間完全覆蓋為目標的模糊估計方法,以計算逼近器的狀態基函數和平均學習率。具體步驟如下:

步驟1利用核心聚類中心矩陣cen和半徑矩陣rad初始化基函數向量φ的中心和半徑。

步驟2遍歷構建樣本集sam。通過歐氏距離獲取與當前遍歷樣本Csam最鄰近的基函數φnear。若Csam在各維上的分量均落在φnear內部,則繼續執行步驟2;否則,結束本次遍歷,執行步驟3。若sam中所有樣本均在最鄰近基函數內部,則表明狀態基函數完成了對樣本空間的完全覆蓋,執行步驟5。

步驟3新增一個狀態基函數,將其中心初始化為Csam,并加入φ中。

步驟4通過式(21)和式(22)調整φ中所有基函數的中心和半徑,執行步驟2。

(21)

(22)

其中,behj為樣本(sam)h到狀態基φj的歸一化隸屬度。

步驟5通過式(23)計算學習單元的強化學習率η,初始狀態基函數構建過程結束。

(23)

其中,X=(X1,X2,…,Xj,…,Xm)T為各基函數的構建樣本數向量,其元素表示為:

6 學習單元自主學習過程

學習單元自主學習過程的重點是實現逼近器狀態基函數和參數的自適應調整。其中,參數的自適應調整如式(12)所示,狀態基函數的自適應調整如下。

6.1 狀態基函數的自適應調整

狀態基函數的自適應調整步驟為:

步驟1若輸入狀態S屬于狀態基函數的構建樣本集sam,則繼續執行步驟1判定下一輸入狀態;否則,將S加入構建樣本集sam,執行步驟2。

步驟2通過歐式距離獲取與S最鄰近的基函數φnear。

步驟3若φnear為初始狀態基函數,TD誤差率RΔ>ε(RΔ的計算如式(24)),且S的任意一維分量落在φnear外部,則新增狀態基函數φnew,并初始化其中心μnew=S,半徑δnew=δnear,執行步驟4;否則直接執行步驟4。

(24)

步驟4采用delta規則調整狀態基函數的中心和半徑,對φj有:

μj=μj+ηRΔBEj(S-μj)

(25)

δj=δj+ηRΔBEj(abs(S-μj)-δj)

(26)

本次調整結束后執行步驟1,開始下一次狀態基函數調整過程。

6.2 學習單元的學習步驟

步驟1學習單元開始一次嘗試。初始化當前狀態St=S0。若本次嘗試未結束,循環執行下列步驟:

1)使用式(10)計算St在各狀態基函數的隸屬度向量φ(St)。使用式(9)計算St在各基函數下的歸一化隸屬度向量Φ(St)。

2)使用式(15)計算當前狀態下執行動作ak的投票結果,使用式(14)選擇當前狀態下應采取的動作At,獲取即時獎勵r,且環境轉移到下一狀態St+1。

3)依據式(12)調整Q值函數逼近器參數向量進行策略改進,依據狀態基函數的自適應調整過程更新構建樣本集和狀態基函數。設置當前狀態St=St+1。

步驟2若本次嘗試成功,則學習單元學習結束。否則,執行步驟1再次進行嘗試。

從以上步驟可以看出,單個學習單元在學習階段的計算復雜度主要由策略評估復雜度O(Km)、策略選擇復雜度O(K)、策略改進復雜度O(K+Km+K2m)以及基函數調整復雜度O(m)組成,即總體復雜度為O(2K+(K2+2K+1)m),遠小于其他近似策略迭代強化學習算法的時間復雜度O(m3)[3],說明該過程可以更好地滿足在線計算的要求。

7 一級倒立擺平衡控制實驗

7.1 實驗描述

一級倒立擺平衡控制問題是強化學習的標準測試問題,本文通過對該問題的仿真實驗來驗證NPAPI-P算法在不同測試條件下的有效性。另外,由于本文提出的學習單元由近似策略迭代強化學習算法實現,因此采用文獻[1]方法,如式(27)所示,建立倒立擺系統模型。

(27)

仿真時間步長設置為0.1 s,折扣率γ=0.95。在仿真中,若擺桿偏離垂直方向角度超過90°,則失敗；若擺桿在上述約束條件下保持指定時間步長不倒,則成功。相應的即時獎勵r計算表達式如式(28)所示。

(28)

7.2 評價指標

加速比和效率是并行算法的重要評價指標,NPAPI-P算法每次運行時的加速比JSB和效率XL分別由式(29)和式(30)定義。

(29)

(30)

其中,NLT為各學習單元平均收斂嘗試次數,NPT為并行學習收斂嘗試次數,NL為學習單元數量。由上述定義可知,若并行算法不具備加速效果,則JSB∈[0,1],XL∈[0,1/NL],其中,1/NL稱為臨界效率。

7.3 實驗結果

設置實驗目標為倒立擺運行3 000時間步長不倒,實驗最大嘗試次數為300,當ε=0.1時,離散動作集合分別取2個離散值{-50 N,+50 N}、3個離散值{-50 N,0,+50 N}、4個離散值{-50 N,-25 N,+25 N,+50 N}、5個離散值{-50 N,-25 N,0,+25 N,+50 N}、6個離散值{-50 N,-33 N,-16 N,+16 N,+33 N,+50 N}、7個離散值{-50 N,-33 N,-16 N,0,+16 N,+33 N,+50 N}、8個離散值{-50 N,-37.5 N,-25 N,-12.5 N,+12.5 N,+25 N,+37.5 N,+50 N}、9個離散值{-50 N,-37.5 N,-25 N,-12.5 N,0,+12.5 N,+25 N,+37.5 N,+50 N}、10個離散值{-50 N,-40 N,-30 N,-20 N,-10 N,+10 N,+20 N,+30 N,+40 N,+50 N}、11個離散值{-50 N,-40 N,-30 N,-20 N,-10 N,0,+10 N,+20 N,+30 N,+40 N,+50 N}。在以上離散動作集合取值下分別進行100次獨立仿真運算,實驗結果如表1所示。

表1 在不同離散動作集合取值下的實驗結果

從表1可以看出,不論離散動作集合如何取值,NPAPI-P算法均具有較快的收斂速度,能夠在較短嘗試次數內學習到一級倒立擺系統的平衡控制策略,并且在保持較高加速比(與1比較)的同時具有較高的效率(與平均臨界效率比較),從而驗證了NPAPI-P算法在離散動作集合不同取值下的有效性。

接下來,設置實驗目標為倒立擺運行3 000時間步長不倒,實驗最大嘗試次數為300,當離散動作集合取3個離散值{-50 N,0,+50 N}、ε取0.5、0.1、0.05、0.01,分別進行100次獨立仿真運算,實驗結果如表2所示。

表2 在不同ε取值下的實驗結果

從表2可以看出,當ε取0.5時算法失敗,這是由于ε過大,導致學習單元構建樣本集無法反映樣本空間的主要分布特征。當ε滿足學習單元構建要求時,隨著ε減小,NPAPI-P算法能夠更快地學習到一級倒立擺系統的平衡控制策略,并且在保持較高加速比(與1比較)的同時具有較高的效率(與平均臨界效率比較),從而驗證了NPAPI-P算法在ε合理取值下的有效性。在不同ε取值下NPAPI-P算法加速比與效率的關系如圖3所示。

圖3 在不同ε取值下算法加速比與效率的關系

從圖3可以看出,當ε確定后,NPAPI-P算法的學習單元數量(擬合直線的斜率)基本維持穩定,且隨著ε減小,學習單元數量逐漸增加。其中,當ε=0.1時,平均單元數量為3.4個,當ε=0.05時,平均單元數量為4.5個,當ε=0.01時,平均單元數量為10.6個。結合表2中的相關數據可以看出,相較于已有文獻將并行單元數量人為確定為10個～20個的方法,NPAPI-P算法能夠依據實際情況更好地平衡加速比和效率間的關系。在不同ε取值下NPAPI-P算法的加速比與收斂速度的關系如圖4所示。

圖4 在不同ε取值下算法加速比與收斂速度的關系

從圖4可以看出,當ε在合理范圍內取值時,NPAPI-P算法都趨向于在較高加速比下快速收斂,且ε越小,這一趨勢越明顯,表明該算法具有良好地并行加速性能。

最后,設置實驗目標為倒立擺運行3 000時間步長不倒,實驗最大嘗試次數為300,當離散動作集合取3個離散值{-50 N,0,+50 N}、ε取0.1時,進行100次獨立仿真運算,得到算法的學習性能如圖5所示。

圖5 NPAPI-P算法學習性能

在圖5中,算法學習成功的嘗試次數最小為2次,最大為14次。選擇倒立擺進行2次嘗試即成功的典型學習過程,其學習成功的曲線如圖6所示。從圖6可以看出,擺桿的擺動角度基本穩定在[-5°,+5°],角速度基本穩定在[-60°/s,+60°/s]。以上數據驗證了NPAPI-P算法在控制能力上的有效性。

圖6 ε=0.1時3個離散動作的典型學習成功曲線

7.4 與典型在線近似策略迭代強化學習算法對比

在線近似策略迭代強化學習算法的優劣一般通過不同參數條件下獲得控制策略的速度進行評價,收斂速度越快,算法性能越好。將NPAPI-P算法在ε取0.5、0.1、0.05和0.01時進行100次獨立仿真運算的結果,與典型在線近似策略迭代強化學習算法online LSPI、BLSPI的最優實驗結果[3]進行比較,3種算法在不同嘗試次數下的平均平衡時間步長如表3所示。其中,LSTD-Q和LSPE-Q是BLSPI算法采用2種不同策略的評估算法,后者與前者的主要區別在于處理每個樣本數據后都要更新參數。

表3 3種算法在不同條件下的平均平衡時間步長對比

從表3可以看出,當ε≤0.1時,由于學習單元構建樣本集能夠反映一級倒立擺樣本空間的主要分布特征,此時,NPAPI-P算法可在50次嘗試內完全學習到一級倒立擺的平衡控制策略。針對相同的學習目標,BLSPI算法平均需要200次嘗試才能完成,online LSPI算法平均需要300次嘗試才能完成。由此可以得出,NPAPI-P算法的學習速度明顯快于online LSPI算法和BLSPI算法。

3種算法的參數數量情況如表4所示,從表4可以看出,NPAPI-P算法只需指定強化學習允許誤差率ε即可實現算法的自主構建和學習,而BLSPI算法需要手工確定4+m個參數,online-LSPI算法需要手工確定5+m個參數,其中,m為狀態基的數量。由此可見,NPAPI-P算法完全實現了強化學習算法的非參數化,其易用性和自學習能力均超過online LSPI算法和BLSPI算法。

表4 3種算法的參數數量對比

8 結束語

本文提出一種非參數化近似策略迭代并行強化學習算法NPAPI-P。該算法只需指定強化學習的允許誤差率,就能完全自主地構建、調整學習單元,進而快速學習到解決目標問題的控制策略。一級倒立擺平衡控制實驗比較收斂速度、加速比、效率和控制精度等指標,結果表明,相對online-LSPI算法和BLSPI算法,本文算法在不同離散動作和強化學習允許誤差率下均具有有效性,且收斂速度更快。針對NPAPI-P算法收斂性的理論證明,將是今后的研究重點。