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

(常州大學(xué)阿里云大數(shù)據(jù)學(xué)院,江蘇 常州 213000)

1 引言

在許多具有挑戰(zhàn)性的順序決策問題中,強(qiáng)化學(xué)習(xí)已被廣泛運(yùn)用。但是由于很多現(xiàn)實(shí)世界的決策問題過于復(fù)雜,無法用單一的標(biāo)量獎(jiǎng)勵(lì)來描述[1],因此需要使用多目標(biāo)強(qiáng)化學(xué)習(xí)(Multi-Objective Reinforcement Learning, MORL)算法來解決智能體在復(fù)雜環(huán)境下的順序決策問題[2]。MORL算法是強(qiáng)化學(xué)習(xí)和多目標(biāo)優(yōu)化的結(jié)合,其即刻獎(jiǎng)勵(lì)是向量且向量中的每個(gè)元素對(duì)應(yīng)不同的目標(biāo)[3]。

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

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

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

2 MORL算法模型

2.1 多目標(biāo)優(yōu)化問題

MORL是標(biāo)準(zhǔn)強(qiáng)化學(xué)習(xí)的一種推廣,即使用強(qiáng)化學(xué)習(xí)算法解決多目標(biāo)優(yōu)化問題。多目標(biāo)優(yōu)化問題的一般描述如下,給定決策向量X=(x1,x2,…,xn),它滿足下列約束

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

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

(1)

設(shè)有m個(gè)優(yōu)化目標(biāo),且這些優(yōu)化目標(biāo)是相互沖突的,目標(biāo)函數(shù)可表示為

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

(2)

2.2 單策略MORL算法模型

在MORL問題中,要求智能體能夠?qū)W習(xí)多個(gè)目標(biāo)函數(shù),其一般模型是由馬爾可夫決策過程(Markov Decision Process, MDP)推廣而來的多目標(biāo)馬爾科夫決策過程(Multi Objective Markov Decision Process, MOMDP),智能體在該模型下與環(huán)境交互得到一個(gè)m維的獎(jiǎng)勵(lì)向量R(s,a)

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

(3)

其中,m代表目標(biāo)函數(shù)個(gè)數(shù),且獎(jiǎng)勵(lì)向量中不同分量對(duì)應(yīng)不同的目標(biāo)函數(shù)。類似地,將標(biāo)量的行為價(jià)值Q擴(kuò)展為行為價(jià)值向量Q:

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

(4)

其中,Qi(s,a)代表第i(i=1,2,…,n)個(gè)目標(biāo)函數(shù)的標(biāo)量Q值。

單策略MORL算法分別訓(xùn)練每個(gè)目標(biāo)對(duì)應(yīng)的標(biāo)量Q值,并使用標(biāo)量化方法計(jì)算Q(s,a)和權(quán)重向量w的加權(quán)和

(5)

由于目標(biāo)空間的降維,單策略MORL算法只能學(xué)習(xí)到單一權(quán)重偏好的最優(yōu)策略。

2.3 多策略MORL算法模型

多策略MORL算法能夠同時(shí)學(xué)習(xí)多個(gè)帕累托最優(yōu)策略,一種基礎(chǔ)算法模型是White等[8]提出的一種基于動(dòng)態(tài)規(guī)劃模型的多策略算法,該算法基于向量集的引導(dǎo)更新策略集,且在學(xué)習(xí)過程中不會(huì)發(fā)生目標(biāo)空間的降維,其更新規(guī)則如下:

(6)

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

(7)

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

(8)

Moffaert等[10]的PQL算法是在White工作的基礎(chǔ)上分開存儲(chǔ)即刻獎(jiǎng)勵(lì)和未來折扣獎(jiǎng)勵(lì),并允許兩者分開收斂。在確定性非平穩(wěn)環(huán)境中,更新規(guī)則如下

(9)

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

(10)

Ruiz-Montiel等[12][12]將基于集合引導(dǎo)的思想引入到標(biāo)準(zhǔn)Q學(xué)習(xí)算法框架中,提出了一種無模型的MPQ算法,該算法使用離線策略,其思想是分開存儲(chǔ)采樣過和未采樣過的狀態(tài)轉(zhuǎn)移(s,a,s′)對(duì)應(yīng)的向量集:

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

(11)

其中,Nn-1(s,a)存儲(chǔ)新的狀態(tài)轉(zhuǎn)移對(duì)應(yīng)的向量集,Nn-1(s,a)存儲(chǔ)已經(jīng)采樣過的狀態(tài)轉(zhuǎn)移對(duì)應(yīng)的向量集,Nn-1(s,a)存儲(chǔ)更新過程中向量集中額外產(chǎn)生的向量估計(jì)。

2.4 集合評(píng)估機(jī)制

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

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

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

2) C:向量集中非支配解的個(gè)數(shù)越多則向量集優(yōu)先級(jí)越高;

3) Pareto:如果向量集中有一個(gè)向量支配其它向量集,則認(rèn)為該向量集更優(yōu)。

在集合評(píng)估機(jī)制下,智能體可以同時(shí)學(xué)習(xí)多個(gè)策略,但在執(zhí)行時(shí)只遵循其中的一個(gè)策略,因此在訓(xùn)練結(jié)束后需要使用跟蹤算法跟蹤向量集中的每個(gè)向量來重現(xiàn)學(xué)習(xí)到的帕累托最優(yōu)策略[13]。

3 MPS算法

MPS算法是基于標(biāo)準(zhǔn)Sarsa算法框架提出的一種在線算法,并使用本文提出的基于投票法的集合評(píng)估機(jī)制指導(dǎo)智能體選擇行為。

3.1 Sarsa算法

Sarsa算法是一種經(jīng)典的基于值函數(shù)更新的無模型算法,并使用在線策略更新值函數(shù),更新規(guī)則如下

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

(12)

其中,Q(s,a)是狀態(tài)行為對(duì)(s,a)的行為價(jià)值,智能體通過行為策略在狀態(tài)s下執(zhí)行行為a后轉(zhuǎn)移到狀態(tài)s′,并從環(huán)境中得到即刻獎(jiǎng)勵(lì)r,接著智能體通過行為策略選擇一個(gè)行為a′作為下一時(shí)間步的行為,α和γ分別是學(xué)習(xí)率和折扣因子。

3.2 MPS算法更新規(guī)則

MPS算法學(xué)習(xí)行為價(jià)值向量集Qset,而不是標(biāo)量形式的Q值,其更新規(guī)則如下

(13)

(14)

3.3 基于投票法的集合評(píng)估機(jī)制

由于算法在現(xiàn)有的集合評(píng)估機(jī)制下性能不佳,提出了一種基于投票法的集合評(píng)估機(jī)制。投票法是一種有效的群體決策方法,決策者通過聚集個(gè)體的偏好來確定群體的偏好。Mazzuchi等[15]首先在多目標(biāo)任務(wù)中使用投票法來區(qū)分一組向量的優(yōu)劣,而本文則是將投票法應(yīng)用到集合評(píng)估機(jī)制中,然后評(píng)估一組向量集。

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

表1 Copeland voting流程

圖1中給出了一個(gè)基于投票法的集合評(píng)估機(jī)制的實(shí)例,其中Qset(s,a1)、Qset(s,a2)、Qset(s,a3)和Qset(s,a4)代表行為空間中4個(gè)行為對(duì)應(yīng)的行為價(jià)值向量集,基于投票法的集合評(píng)估機(jī)制的任務(wù)是輸出這4個(gè)行為對(duì)應(yīng)的標(biāo)量得分,智能體根據(jù)得分結(jié)果選擇行為,其步驟可總結(jié)如下:

圖1 基于投票法的集合評(píng)估機(jī)制流程實(shí)例

1)求解當(dāng)前狀態(tài)下所有行為對(duì)應(yīng)向量集的并集,并進(jìn)一步計(jì)算并集的非支配集ND(∪a′Qset(s′,a′));

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

3)將ScoreND(∪a′Qset(s′,a′))中的得分映射到對(duì)應(yīng)行為的得分,如圖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],然后計(jì)算每個(gè)行為的總得分Scorea,最后根據(jù)每個(gè)向量集Qset(s,·)中的向量在ND(∪a′Qset(s′,a′))中的保留個(gè)數(shù)k:{a1:3,a2:2,a3:1,a4:4}來計(jì)算行為的平均得分Ave＿scorea;

4)最后智能體選擇Ave＿scorea中最大得分對(duì)應(yīng)的行為a2執(zhí)行。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 仿真環(huán)境和參數(shù)設(shè)置

仿真環(huán)境DST是一個(gè)驗(yàn)證多目標(biāo)強(qiáng)化學(xué)習(xí)算法性能的基準(zhǔn)問題[14],它是一個(gè)10行11列的網(wǎng)格世界,且網(wǎng)格中有10個(gè)不同價(jià)值的寶藏地點(diǎn)。該環(huán)境模擬潛艇在深海中執(zhí)行搜尋寶藏的任務(wù),搜尋任務(wù)需要實(shí)現(xiàn)兩個(gè)相互沖突的目標(biāo),第一個(gè)目標(biāo)是潛艇到達(dá)寶藏消耗盡可能少的時(shí)間步,第二個(gè)目標(biāo)是盡可能找到更大價(jià)值的寶藏,如圖2。

圖2 DST環(huán)境

搜尋任務(wù)是階段性的,每個(gè)回合潛艇從網(wǎng)格的左上角開始搜尋,當(dāng)?shù)竭_(dá)寶藏時(shí)該回合結(jié)束。潛艇有四個(gè)行為,分別是向上、向下、向左和向右移動(dòng),如果潛艇執(zhí)行一個(gè)動(dòng)作后將移出網(wǎng)格,那么潛艇的位置保持不變。潛艇每移動(dòng)一步會(huì)得到一個(gè)二維的獎(jiǎng)勵(lì)向量,向量的第一個(gè)分量是時(shí)間步消耗-1,第二個(gè)元素是寶藏價(jià)值,若潛艇未搜尋到寶藏則為0。

算法的超體積參考點(diǎn)、折扣因子和學(xué)習(xí)率等參數(shù)如表2。

表2 算法的參數(shù)設(shè)置

4.2 實(shí)驗(yàn)結(jié)果

仿真對(duì)比了MPS算法和已有的PQL、MPQ算法在不同集合評(píng)估機(jī)制下的收斂性能和超體積性能。

4.2.1 收斂性能

在Moffaert等[11]在PQL算法訓(xùn)練過程中引入跟蹤算法,旨在讓智能體在某個(gè)狀態(tài)下一致性地選擇行為,然而這可能導(dǎo)致智能體對(duì)環(huán)境探索不夠。本文則是在三種算法訓(xùn)練結(jié)束后再使用跟蹤算法跟蹤初始狀態(tài)向量集中的向量來找到所有的帕累托最優(yōu)策略。

以回合數(shù)為橫坐標(biāo),時(shí)間步為縱坐標(biāo),來比較三種多策略算法分別在不同集合評(píng)估機(jī)制下的收斂情況,如圖3。

圖3 收斂性能比較

由圖3的實(shí)驗(yàn)結(jié)果可得:在PQL算法下,HV-PQL和C-PQL不收斂,而PO-PQL收斂和Copeland-PQL收斂。在MPQ和MPS算法下,只有HV-MPQ是不收斂的,其它三種機(jī)制下的算法均收斂。表3歸納了三種算法在不同集合評(píng)估機(jī)制下的收斂情況。

表3 三種算法在集合評(píng)估機(jī)制下的收斂情況

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

當(dāng)Voting-MPS算法訓(xùn)練結(jié)束后,使用跟蹤算法從初始狀態(tài)跟蹤向量集中的每個(gè)向量,最終找到了10個(gè)非支配策略,且跟蹤算法記錄了智能體在非支配策略下每一時(shí)間步選擇的行為,如表4。

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

由表4結(jié)果可得:MPS作為一種新的多策略算法可以學(xué)習(xí)多個(gè)帕累托最優(yōu)策略,且這10個(gè)非支配策略在目標(biāo)空間形成了非凸的帕累托前沿,如圖4。

圖4 非凸帕累托前沿

4.2.2 超體積性能

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

以回合數(shù)為橫坐標(biāo),超體積為縱坐標(biāo),來比較MPQ和MPS算法在基于投票法的集合評(píng)估機(jī)制下的超體積性能,如圖5。

圖5 超體積性能比較

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

5 結(jié)束語

本文提出了基于Sarsa算法框架的多策略在線算法MPS,該算法使用基于投票法的集合評(píng)估機(jī)制作為行為策略,可以在目標(biāo)空間找到多個(gè)帕累托最優(yōu)策略,且仿真驗(yàn)證了該算法且具有優(yōu)秀的收斂性能和超體積性能。

由于基于表格法的強(qiáng)化學(xué)習(xí)的維度限制,下一步工作將研究多目標(biāo)深度強(qiáng)化學(xué)習(xí),并結(jié)合進(jìn)化策略來解決多目標(biāo)優(yōu)化問題。