一種基于投票法的多策略多目標強化學習算法

王立佳,朱正偉,諸燕平,朱晨陽

(常州大學阿里云大數據學院,江蘇 常州 213000)

1 引言

在許多具有挑戰性的順序決策問題中,強化學習已被廣泛運用。但是由于很多現實世界的決策問題過于復雜,無法用單一的標量獎勵來描述[1],因此需要使用多目標強化學習(Multi-Objective Reinforcement Learning, MORL)算法來解決智能體在復雜環境下的順序決策問題[2]。MORL算法是強化學習和多目標優化的結合,其即刻獎勵是向量且向量中的每個元素對應不同的目標[3]。

MORL算法主要分為單策略和多策略算法[4],單策略MORL算法使用標量化方法將多目標問題降維成單目標問題[5],然而標量化方法往往只能產生單一權重偏好的解決方案[6],在胡的工作中使用了單策略算法解決多個Web服務的組合問題[7]。

多策略MORL算法不對目標空間降維,且智能體可以同時學習一組優策略。White等[8]首先基于動態規劃提出了一種多策略算法,該算法通過更新行為價值向量集來同時學習一組最優的確定性平穩策略,但在確定性非平穩問題中容易導致集合爆炸。因此,Wiering等[9]在White的算法中引入一致性算子減少學習到的策略數量,使算法能夠解決確定性非平穩策略問題。在White工作的引導下,Barret等[10]提出凸包值迭代算法(Convex Hull Value-iteration, CHVI),該算法可以學習帕累托前沿凸包上的確定性平穩策略,然而在非凸解空間問題中,部分解決方案被忽視。這一問題在Moffaert等[10]得到了解決,其提出的基于動態規劃模型的Pareto Q-learning(PQL)算法允許智能體學習整個帕累托前沿的最優策略;陶等[12]的工作進一步驗證了PQL算法解決多目標問題的優異性能;在Moffaert等工作的啟發下,Ruiz-Montiel等[12]提出了基于Q學習算法框架的無模型Multi-Pareto Q-learning(MPQ)算法,該算法也能夠學習到整個帕累托前沿上的最優策略。

在MPQ算法的啟發下,本文遵循Sarsa算法框架提出了一種新的多策略算法MPS,并將投票法引入集合評估機制來提高算法的收斂性能,最后在深海寶藏(Deep Sea Treasure, DST)[14]的實驗環境下測試了算法性能。

2 MORL算法模型

2.1 多目標優化問題

MORL是標準強化學習的一種推廣,即使用強化學習算法解決多目標優化問題。多目標優化問題的一般描述如下,給定決策向量X=(x1,x2,…,xn),它滿足下列約束

gi(X)≤0 (i=1,2,…,k)

hi(X)=0 (i=1,2,…,l)

(1)

設有m個優化目標,且這些優化目標是相互沖突的,目標函數可表示為

f(X)=(f1(X),f2(X),…,fm(X))

(2)

2.2 單策略MORL算法模型

在MORL問題中,要求智能體能夠學習多個目標函數,其一般模型是由馬爾可夫決策過程(Markov Decision Process, MDP)推廣而來的多目標馬爾科夫決策過程(Multi Objective Markov Decision Process, MOMDP),智能體在該模型下與環境交互得到一個m維的獎勵向量R(s,a)

R(s,a)=(R1(s,a),R2(s,a),…,Rm(s,a))

(3)

其中,m代表目標函數個數,且獎勵向量中不同分量對應不同的目標函數。類似地,將標量的行為價值Q擴展為行為價值向量Q:

Q(s,a)=(Q1(s,a),Q2(s,a),…,Qm(s,a))

(4)

其中,Qi(s,a)代表第i(i=1,2,…,n)個目標函數的標量Q值。

單策略MORL算法分別訓練每個目標對應的標量Q值,并使用標量化方法計算Q(s,a)和權重向量w的加權和

(5)

由于目標空間的降維,單策略MORL算法只能學習到單一權重偏好的最優策略。

2.3 多策略MORL算法模型

多策略MORL算法能夠同時學習多個帕累托最優策略,一種基礎算法模型是White等[8]提出的一種基于動態規劃模型的多策略算法,該算法基于向量集的引導更新策略集,且在學習過程中不會發生目標空間的降維,其更新規則如下:

(6)

VND(s′)=ND(∪a′Qset(s′,a′))

(7)

其中,ND操作符移除所有被支配的向量,⊕操作符是在向量v和向量集V之間的求和

(8)

Moffaert等[10]的PQL算法是在White工作的基礎上分開存儲即刻獎勵和未來折扣獎勵,并允許兩者分開收斂。在確定性非平穩環境中,更新規則如下

(9)

NDt(s,a)=ND(∪a′Qset(s′,a′))

(10)

Ruiz-Montiel等[12][12]將基于集合引導的思想引入到標準Q學習算法框架中,提出了一種無模型的MPQ算法,該算法使用離線策略,其思想是分開存儲采樣過和未采樣過的狀態轉移(s,a,s′)對應的向量集:

Qn(s,a)=Nn-1(s,a)∪Un-1(s,a)∪En-1(s,a)

(11)

其中,Nn-1(s,a)存儲新的狀態轉移對應的向量集,Nn-1(s,a)存儲已經采樣過的狀態轉移對應的向量集,Nn-1(s,a)存儲更新過程中向量集中額外產生的向量估計。

2.4 集合評估機制

由于傳統的行為策略不能直接應用到MORL算法中,因此Moffaert等[10]使用集合評估機制替代傳統的行為策略,其原理是在貪婪地選擇行為時,智能體選擇擁有最大評估值的向量集對應的行為。

已有的三種集合評估機制分別為超體積集合評估機制(Hypervolume set evaluation, HV)、基數集合評估機制(Cardinality set evaluation, C)和帕累托集合評估機制(Pareto set evaluation, Pareto),這三種集合評估機制的原理總結如下:

1) HV:解集中所有點和參考點在目標空間中圍成的超立方體的體積,在二維的目標空間中,超體積是參考點和解集圍成的面積,超體積越大則認為解集越好;

2) C:向量集中非支配解的個數越多則向量集優先級越高;

3) Pareto:如果向量集中有一個向量支配其它向量集,則認為該向量集更優。

在集合評估機制下,智能體可以同時學習多個策略,但在執行時只遵循其中的一個策略,因此在訓練結束后需要使用跟蹤算法跟蹤向量集中的每個向量來重現學習到的帕累托最優策略[13]。

3 MPS算法

MPS算法是基于標準Sarsa算法框架提出的一種在線算法,并使用本文提出的基于投票法的集合評估機制指導智能體選擇行為。

3.1 Sarsa算法

Sarsa算法是一種經典的基于值函數更新的無模型算法,并使用在線策略更新值函數,更新規則如下

Q(s,a)←(1-α)Q(s,a)+α[r+γQ(s′,a′)]

(12)

其中,Q(s,a)是狀態行為對(s,a)的行為價值,智能體通過行為策略在狀態s下執行行為a后轉移到狀態s′,并從環境中得到即刻獎勵r,接著智能體通過行為策略選擇一個行為a′作為下一時間步的行為,α和γ分別是學習率和折扣因子。

3.2 MPS算法更新規則

MPS算法學習行為價值向量集Qset,而不是標量形式的Q值,其更新規則如下

(13)

(14)

3.3 基于投票法的集合評估機制

由于算法在現有的集合評估機制下性能不佳,提出了一種基于投票法的集合評估機制。投票法是一種有效的群體決策方法,決策者通過聚集個體的偏好來確定群體的偏好。Mazzuchi等[15]首先在多目標任務中使用投票法來區分一組向量的優劣,而本文則是將投票法應用到集合評估機制中,然后評估一組向量集。

本文使用的投票法是現有投票系統中的科普蘭投票法(Copeland voting),每個選民任意排列候選人,然后將一個候選人與其他所有候選人進行兩兩選舉,候選人在兩兩比較中獲勝得1.0分,平局獲得0.5分,失敗不得分,最后將每個候選人的累積分數作為最終得分, 累積得分最高的候選人在選舉結束時成為獲勝者,Copeland voting的流程如表1。

表1 Copeland voting流程

圖1中給出了一個基于投票法的集合評估機制的實例,其中Qset(s,a1)、Qset(s,a2)、Qset(s,a3)和Qset(s,a4)代表行為空間中4個行為對應的行為價值向量集,基于投票法的集合評估機制的任務是輸出這4個行為對應的標量得分,智能體根據得分結果選擇行為,其步驟可總結如下:

圖1 基于投票法的集合評估機制流程實例

1)求解當前狀態下所有行為對應向量集的并集,并進一步計算并集的非支配集ND(∪a′Qset(s′,a′));

2)使用Copeland voting來計算非支配向量集ND(∪a′Qset(s′,a′))中每個向量的對應得分ScoreND(∪a′Qset(s′,a′));

3)將ScoreND(∪a′Qset(s′,a′))中的得分映射到對應行為的得分,如圖1所示,a1的得分列表為[1.0,1.0,2.0],a2的得分列表為[2.0,2.5],a3的得分列表為[1.5],a4的得分列表為[1.0,2.0,3.0,2.0],然后計算每個行為的總得分Scorea,最后根據每個向量集Qset(s,·)中的向量在ND(∪a′Qset(s′,a′))中的保留個數k:{a1:3,a2:2,a3:1,a4:4}來計算行為的平均得分Ave＿scorea;

4)最后智能體選擇Ave＿scorea中最大得分對應的行為a2執行。

4 實驗及結果分析

4.1 仿真環境和參數設置

仿真環境DST是一個驗證多目標強化學習算法性能的基準問題[14],它是一個10行11列的網格世界,且網格中有10個不同價值的寶藏地點。該環境模擬潛艇在深海中執行搜尋寶藏的任務,搜尋任務需要實現兩個相互沖突的目標,第一個目標是潛艇到達寶藏消耗盡可能少的時間步,第二個目標是盡可能找到更大價值的寶藏,如圖2。

圖2 DST環境

搜尋任務是階段性的,每個回合潛艇從網格的左上角開始搜尋,當到達寶藏時該回合結束。潛艇有四個行為,分別是向上、向下、向左和向右移動,如果潛艇執行一個動作后將移出網格,那么潛艇的位置保持不變。潛艇每移動一步會得到一個二維的獎勵向量,向量的第一個分量是時間步消耗-1,第二個元素是寶藏價值,若潛艇未搜尋到寶藏則為0。

算法的超體積參考點、折扣因子和學習率等參數如表2。

表2 算法的參數設置

4.2 實驗結果

仿真對比了MPS算法和已有的PQL、MPQ算法在不同集合評估機制下的收斂性能和超體積性能。

4.2.1 收斂性能

在Moffaert等[11]在PQL算法訓練過程中引入跟蹤算法,旨在讓智能體在某個狀態下一致性地選擇行為,然而這可能導致智能體對環境探索不夠。本文則是在三種算法訓練結束后再使用跟蹤算法跟蹤初始狀態向量集中的向量來找到所有的帕累托最優策略。

以回合數為橫坐標,時間步為縱坐標,來比較三種多策略算法分別在不同集合評估機制下的收斂情況,如圖3。

圖3 收斂性能比較

由圖3的實驗結果可得:在PQL算法下,HV-PQL和C-PQL不收斂,而PO-PQL收斂和Copeland-PQL收斂。在MPQ和MPS算法下,只有HV-MPQ是不收斂的,其它三種機制下的算法均收斂。表3歸納了三種算法在不同集合評估機制下的收斂情況。

表3 三種算法在集合評估機制下的收斂情況

由表3可得:在超體積集合評估機制下三種算法的收斂性能最差;在基數集合評估機制下只有MPS和MPQ算法收斂性能良好;帕累托集合評估機制和基于投票法的集合評估機制在三種算法下都有不錯的收斂性能。

當Voting-MPS算法訓練結束后,使用跟蹤算法從初始狀態跟蹤向量集中的每個向量,最終找到了10個非支配策略,且跟蹤算法記錄了智能體在非支配策略下每一時間步選擇的行為,如表4。

表4 非支配策略的行為選擇

由表4結果可得:MPS作為一種新的多策略算法可以學習多個帕累托最優策略,且這10個非支配策略在目標空間形成了非凸的帕累托前沿,如圖4。

圖4 非凸帕累托前沿

4.2.2 超體積性能

在無模型的MPQ和MPS算法下,向量集更新會產生額外的非支配向量,因此其超體積的增長是巨大的。

以回合數為橫坐標,超體積為縱坐標,來比較MPQ和MPS算法在基于投票法的集合評估機制下的超體積性能,如圖5。

圖5 超體積性能比較

由圖5仿真結果可得:MPQ算法的超體積在350個回合左右不再增加,而MPS算法的超體積在100次左右不再增加,MPS相比MPQ算法的超體積能夠更快地達到最大值;并且由于MPS算法在估計新的向量集也在探索環境,并產生了額外的向量估計,因此MPS算法比MPQ算法擁有更大的超體積。

5 結束語

本文提出了基于Sarsa算法框架的多策略在線算法MPS,該算法使用基于投票法的集合評估機制作為行為策略,可以在目標空間找到多個帕累托最優策略,且仿真驗證了該算法且具有優秀的收斂性能和超體積性能。

由于基于表格法的強化學習的維度限制,下一步工作將研究多目標深度強化學習,并結合進化策略來解決多目標優化問題。