基于值分布的多智能體分布式深度強化學習算法①

陳妙云,王 雷,盛 捷

(中國科學技術(shù)大學 信息科學與技術(shù)學院,合肥 230027)

1 引言

近年來,強化學習在解決一系列順序決策問題上取得了巨大的成功.Minih 等人[1]將深度學習和強化學習結(jié)合起來,提出了深度強化學習,在眾多領(lǐng)域都得到了廣泛的應(yīng)用.比如機器人控制[2],生命科學[3],自動駕駛[4],5G 通信[5],物聯(lián)網(wǎng)[6],車聯(lián)網(wǎng)[7]等.在深度強化學習的基礎(chǔ)上眾多研究者提出了多項改進來提升算法的收斂速度和穩(wěn)定性.然而這些算法的研究和應(yīng)用大多集中在單智能體領(lǐng)域.現(xiàn)實世界中的任務(wù)和場景通常更加復(fù)雜,涉及到多個智能體之間的合作和競爭.比如工廠中的協(xié)作機器人,交通控制系統(tǒng)和自動軍事系統(tǒng)等.將單智能體強化學習算法簡單地移植到多智能體場景中通常會帶來一些問題和挑戰(zhàn)[8].比如單智能體深度強化學習算法無法表征智能體之間的合作與競爭關(guān)系以及智能體之間共同進化導(dǎo)致環(huán)境非平穩(wěn)性的問題.并且多智能體與復(fù)雜場景會帶來計算量大幅提升,算法收斂速度明顯下降等挑戰(zhàn).

目前,Self-play[9]被證明是一種有效的多智能體訓練范式,并成功的應(yīng)用在了圍棋,象棋以及博弈競爭場景中.Palmer 等人[10]提出了一種基于寬容的DQN 算法,對同伴不合理的行為給予一定的容忍度.Foerster等人[11]提出了反事實的思想,解決了多智能體合作場景中信用分配的問題.這些算法在多智能體場景中都取得了很好的效果.但是只能應(yīng)用在離散動作空間中,并且Self-play 還增加了智能體之間動作集完全一致的限制.Lowe 等人[12]提出了一種集中式訓練,分散式執(zhí)行的算法(multi-agent deep deterministic policy gradient,MA-DDPG),解決了多智能體場景中環(huán)境非平穩(wěn)的問題.并且該算法可以同時應(yīng)用在連續(xù)和離散控制的多智能體場景中,使得應(yīng)用場景更加靈活.

然而對于復(fù)雜的多智能體場景,目前的多智能體深度強化學習算法還有很多問題沒有解決.智能體動作策略的更新質(zhì)量非常依賴于預(yù)期回報的估計,但是多個智能體與環(huán)境交互時,其內(nèi)在的隨機性會導(dǎo)致預(yù)期回報具有不確定性,現(xiàn)有的方法將預(yù)期回報簡單地平均為期望值則會丟失完整的分布信息,導(dǎo)致智能體不能進行有效的學習.并且現(xiàn)有的方法主要基于單步回報,智能體只考慮當下的收益而忽略未來的信息,從而引發(fā)算法不穩(wěn)定.此外現(xiàn)有方法中經(jīng)驗數(shù)據(jù)生成往往和網(wǎng)絡(luò)更新耦合在一起,導(dǎo)致只能串行處理,難以有效利用更多的計算資源.為此,本文提出了基于值分布的多智能體分布式深度確定性策略梯度算法(multi-agent distributed distributional deep deterministic policy gradient,MA-D4PG),引入值分布的思想[13]對預(yù)期回報的分布建模,避免分布信息丟失,使得智能體能夠獲得更加準確的梯度更新,保證學習的有效性;引入多步回報使得智能體能夠從未來的經(jīng)驗中學習,增加智能體的預(yù)見能力,提高算法的穩(wěn)定性;引入分布式數(shù)據(jù)生成框架(APE-X)[14],將智能體與環(huán)境交互生成經(jīng)驗數(shù)據(jù)部分與網(wǎng)絡(luò)更新解耦,使得經(jīng)驗數(shù)據(jù)生成過程和網(wǎng)絡(luò)更新能夠并行進行,充分利用更多的計算資源.

在多個不同的連續(xù)/離散控制的多智能體場景中本文算法的穩(wěn)定性和收斂速度都有了極大的提升,智能體的決策能力也有了明顯的增強.最后本文還做了消融實驗展示每個改進各自的貢獻以及相互作用.

2 相關(guān)工作

2.1 多智能體馬爾可夫決策過程

多智能體馬爾可夫決策過程是馬爾可夫決策過程在多智能體場景下的擴展.其同樣由四元組構(gòu)成:

其中,S表示所有智能體的狀態(tài)集合 {s1,s2,···,sk},k表示智能體的數(shù)量.A表示所有智能體的動作集合{A1,A2,···,Ak}.Pr(S′|S,A) 表示狀態(tài)轉(zhuǎn)移函數(shù),S×A1×···×Ak→P(S′).其中P(S′) 定義了所有智能體的下一個狀態(tài)的概率分布.R表示所有智能體的回報集合 {r1,···,rk}.本文遵循以上符號表示.

對于每一個智能體i,學習相應(yīng)的動作選擇策略 πi:oi→P(Ai).其中oi表示智能體i的局部觀測,P(Ai) 表示選擇動作的概率分布.

智能體的目標是學習一個動作選擇策略以最大化預(yù)期回報如下,其中 γ為折現(xiàn)因子.

2.2 多智能體深度確定性策略梯度

深度策略梯度算法(deep policy gradient,DPG)[15]是一種非常經(jīng)典的深度強化學習算法.該算法使用神經(jīng)網(wǎng)絡(luò)模擬動作策略函數(shù),通過梯度上升法調(diào)整網(wǎng)絡(luò)參數(shù)以最大化目標函數(shù),如式(3)所示:

其中,Q(St,At) 表示狀態(tài)動作對的預(yù)期回報的期望值.相應(yīng)的動作策略網(wǎng)絡(luò)的梯度公式如式(4)所示:

其中,π 表示智能體的隨機動作策略,輸出所有動作的概率分布.

DDPG (deep deterministic policy gradient)[16]是DPG的一種變體,其中動作策略輸出的是確定性動作而不是所有動作的概率分布.可以應(yīng)用于連續(xù)控制的多智能體場景中,相應(yīng)的動作策略網(wǎng)絡(luò)梯度公式如式(5):

其中,μ 表示智能體的確定性動作策略.

而多智能體深度確定性策略梯度算法是DDPG 在多智能體場景的擴展,并且與actor-critic框架相結(jié)合.其中actor 模擬動作選擇策略函數(shù) μ,根據(jù)智能體i的局部觀測oi,輸出動作Ai=μi(oi|θi).critic 模擬動作價值函數(shù)Qi以輸出智能體i某一時刻的狀態(tài)動作對的預(yù)期回報的期望值.Qi是一個集中式的函數(shù),考慮了所有智能體的狀態(tài)動作信息,解決了多智能體場景中智能體共同學習以及相互作用導(dǎo)致的環(huán)境非平穩(wěn).

在MA-DDPG 算法智能體i的actor 網(wǎng)絡(luò)的梯度公式以及critic 網(wǎng)絡(luò)的損失函數(shù)分別如式(6)和式(7):

3 基于值分布的多智能體分布式深度確定性策略梯度算法

本文引入了值分布的思想對預(yù)期回報的分布建模,提出了一種基于值分布的評論家(critic)更新方法;并在此基礎(chǔ)上引入多步回報衡量critic的損失;最后引入了分布式數(shù)據(jù)生成架構(gòu)(APE-X)將智能體與環(huán)境交互生成經(jīng)驗數(shù)據(jù)的部分與網(wǎng)絡(luò)更新解耦.這些將會在本節(jié)進行詳細描述.

3.1 基于值分布的critic 更新

基于值的多智能體深度強化學習算法直接對智能體狀態(tài)動作對的預(yù)期回報的期望建模,不考慮智能體與環(huán)境的交互的內(nèi)在隨機性對預(yù)期回報的影響.這種建模方式損失了關(guān)于預(yù)期回報的完整的分布信息.本文引入值分布的思想,強調(diào)預(yù)期回報的分布信息的重要性,對預(yù)期回報的分布建模,而非對其期望值建模.本文將預(yù)期回報看作隨機變量,記為定義如式(8)所示:

本文使用參數(shù)化的多分類分布對預(yù)期回報的分布建模 {N∈N,Vmin,Vmax∈R},其中N表示分類個數(shù),Vmin表示最小類別值,Vmax表示最大類別值.以此模擬預(yù)期回報的近似分布.其中一系列的類別值分別如式(9):

在actor-critic的框架下,改進的基于值分布思想的critic 網(wǎng)絡(luò)輸出預(yù)期回報的N分類分布,表示各類預(yù)期回報值的概率分布.記pi,j(St,At)為智能體i的critic網(wǎng)絡(luò)所輸出的預(yù)期回報屬于第j類zj的概率.

其中,St={s1,t,···,sk,t} 表示所有智能體的狀態(tài)信息,At={A1,t,···,Ak,t}表示所有智能體的動作信息.

基于值分布的critic的損失函數(shù)定義如式(11)和式 (12):

以上所述引入了值分布的思想對critic的更新進行改進,相應(yīng)的actor 更新也引入預(yù)期回報的分布信息,本文通過引入Z分布的期望來實現(xiàn),則actor 網(wǎng)絡(luò)更新的梯度公式如式(13)所示:

3.2 多步回報

本小節(jié)在第3.1 節(jié)所述的基于值分布的critic 更新的基礎(chǔ)上引入多步回報來計算critic的TD (temporaldifference)誤差.利用多步回報可以使得智能體從未來的經(jīng)驗中學習,而不是只考慮當下的收益.多步回報的思想已經(jīng)廣泛的應(yīng)用在眾多單智能體強化學習算法[17,18]中.類似的修正也可以應(yīng)用在多智能體深度強化學習算法中.基于多步回報的貝爾曼方程定義如式(14)和式(15)所示:

其中,Ri,t表示時刻t智能體i的N步回報.

3.3 分布式數(shù)據(jù)生成和網(wǎng)絡(luò)更新

針對模型耦合度高無法充分利用計算資源的問題,本文引入了分布式數(shù)據(jù)生成的框架(APE-X)將多智能體場景中智能體與環(huán)境交互生成經(jīng)驗數(shù)據(jù)和網(wǎng)絡(luò)更新兩部分進行解耦.負責數(shù)據(jù)生成的部分稱為Actor,負責從經(jīng)驗回放池中采樣數(shù)據(jù)進行網(wǎng)絡(luò)更新的部分稱為Learner.Actor的網(wǎng)絡(luò)結(jié)構(gòu)與Learner 完全一致,只負責與環(huán)境交互得到經(jīng)驗數(shù)據(jù)存入經(jīng)驗回放池中,不執(zhí)行梯度計算進行參數(shù)更新,而是定期復(fù)制Learner的網(wǎng)絡(luò)參數(shù).Learner 只負責從經(jīng)驗回放池中采樣數(shù)據(jù)進行網(wǎng)絡(luò)更新而不負責與環(huán)境進行交互.本文算法并行運行多個獨立的Actor,分別與環(huán)境進行交互得到經(jīng)驗數(shù)據(jù){St+1-N,At+1-N,Rt+1-N,St+1},寫入同一個經(jīng)驗緩沖池中.Learner 從該經(jīng)驗緩沖池中隨機采樣M批經(jīng)驗數(shù)據(jù)進行網(wǎng)絡(luò)更新.具體的算法框架圖如圖1所示.其中St+1-N={s1,t+1-N,···,sk,t+1-N},At+1-N={A1,t+1-N,···,Ak,t+1-N},Rt+1-N={R1,t+1-N,···,Rk,t+1-N}.

圖1 分布式數(shù)據(jù)生成框架示意圖

3.4 本文算法小結(jié)

本文算法的偽代碼如算法1和算法2 所示.Learner中actor-critic的網(wǎng)絡(luò)都采用梯度下降法進行網(wǎng)絡(luò)參數(shù)更新.actor和critic的學習率分別是αt,βt,均采用Adam優(yōu)化器[19],利用動量和自適應(yīng)學習率來加快收斂速度.該算法偽代碼中同時包含了Actor和Learner的偽代碼,多個Actor 初始化為相同的多智能體環(huán)境,并行與環(huán)境交互生成經(jīng)驗數(shù)據(jù)并將其存入經(jīng)驗回放池中.

算法1.經(jīng)驗數(shù)據(jù)生成-Actor 1)初始化 值,智能體數(shù)量K,經(jīng)驗回放池B,初始化軟更新頻率TAU(θ1:k N Actor,ω1:kActor)←(θ1:kLearner,ω1:kLearner)2)初始化Actor 網(wǎng)絡(luò)參數(shù)3)初始化States,Actions,Rewards,Terminals為大小為的deque j=1,···,Episode_num N+1 4)For do 5)Clear (States,Actions,Rewards,Terminals)S 0←6)Env.Reset()S 0 7)States.Add()t=1,···,max_step 8)For do A1,t-1,···,Ak,t-1←μ1(s1,t-1),···,μk(sk,t-1)9)r1,t-1,···,rk,t-1,S t,termt← At-1+OU 10)Env.Step()11)States.Add()At-1 S t Actions.Add(){r1,t-1,···,rk,t-1}Rewards.Add()termt Terminals.Add()12)If States.full then NRt-N 13)根據(jù)式(15)計算 步回報14)B.Add(States[0],Actions[0],Rt-N States[N],Terminals[N–1])15)PopLeft(States,Actions,Rewards,Terminals)16)End If termt 17)If break 18)End For 19)End For

算法2.網(wǎng)絡(luò)更新-Learner 1)初始化采樣批次M,最大更新步數(shù)T(θ1:k Learner,ω1:kLearner)2)隨機初始化網(wǎng)絡(luò)參數(shù)target,ω1:ktarget)←(θ1:kLearner,ω1:kLearner)3)初始化目標網(wǎng)絡(luò)參數(shù)(θ1:k 4)For do BM t=1,···,T 5)If len()

4 實驗分析

本文設(shè)置了3 個實驗場景來測試本文算法(MAD4PG)的性能,將在本節(jié)依次描述.在實驗中設(shè)置了一個額外的Actor.該Actor 只利用,而不進行探索,方便在沒有噪聲的情況下測試本文算法的性能.其他Actor 則負責探索環(huán)境,獲得更多關(guān)于環(huán)境的信息,并且與環(huán)境交互生成經(jīng)驗數(shù)據(jù).Learner 每更新N步,將網(wǎng)絡(luò)參數(shù)復(fù)制給Actor.本文將N值設(shè)為5.為了加快訓練模型以及更好的利用資源,Learner 模型在GPU上進行運算,Actor 在CPU 進行運算.強化學習算法性能評價的兩個關(guān)鍵指標是算法收斂所需的步數(shù)以及最終收斂的Episode Reward 值.收斂所需的步數(shù)越少,表示算法的收斂速度越快,最終的收斂的Episode Reward值越大,表示智能體的學習效果越好.本文將根據(jù)這兩個指標對本文算法進行評價.并且本文還做了一些消融實驗,分別刪除本文算法中的單項組件,以確定其特定的貢獻.

1×106

本文實驗中統(tǒng)一使用大小為經(jīng)驗重放池存儲智能體與環(huán)境交互產(chǎn)生的經(jīng)驗數(shù)據(jù).為確保一定的探索性,在智能體的動作策略中添加Ornstein-Uhlenbeck噪聲[19].并且本文實驗中actor和critic的學習率以及采樣批次大小,軟更新頻率統(tǒng)一設(shè)置如下:

α=5×10-5,β=5×10-5,M=256,TAU=0.001

4.1 實驗環(huán)境配置

本文算法中實驗環(huán)境的配置如表1所示.本文采用了PyTorch 作為深度學習框架,在GPU 上使CUDNN加速訓練模型.

表1 本文實驗環(huán)境配置

4.2 實驗場景

本文實驗包含了3 個實驗場景,如圖2所示.這3 個實驗場景分別是多智能體合作清潔,多無人機監(jiān)控,多智能體救援.本節(jié)將對這3 個實驗場景進行簡單描述.

在多智能體清潔場景中,兩個或者多個智能體將合作打掃一個房間,實驗場景如圖2(a)所示.環(huán)境中智能體的任務(wù)是在規(guī)定的時間內(nèi)盡量擴大清潔面積,或者是在最短的時間內(nèi)盡量清潔完所有的區(qū)域.該任務(wù)實際上是一個路徑規(guī)劃任務(wù),智能體之間應(yīng)該合作規(guī)劃具有最小重疊區(qū)域的路徑.每個智能體的局部觀測由周圍8 個方塊的狀態(tài)組成,一共8 維.動作空間是1 維,可以朝上下左右4 個方向移動.

圖2 實驗場景示意圖

多無人機監(jiān)控實驗場景如圖2(b)所示.正方形區(qū)域表示地面,空中有多個無人機使用攝像頭監(jiān)控地面,無人機可以在給定區(qū)域自由飛行.每架無人機都有一個由半徑定義的局部觀測區(qū)域(如圖2(c)所示),無人機只能觀測到該區(qū)域內(nèi)的物體.在該實驗場景中,多個智能體(無人機)的目標是盡量減少視覺區(qū)域的重疊以及監(jiān)控更多的行人.每個智能體的動作空間包含朝上下左右4 個方向移動以及停留原地5 個動作.

多智能體救援實驗場景如圖2(d)所示.方形區(qū)域模擬地震后的廢墟.多個智能體從安全點出發(fā),進入該區(qū)域,找到該區(qū)域的人并帶回安全點.該任務(wù)的目標是智能體盡可能在更短的時間內(nèi)將更多的人帶回安全點.每個智能體的局部觀測范圍是其前方90 度的扇形區(qū)域,半徑為3 個方塊的長度.智能體的動作空間維度大小為4,分別表示沿x軸方向行走 [-0.5,0.5],沿y軸方向行走 [-0.5,0.5],旋轉(zhuǎn) [-10,10],背起/放下人 {0,1,2}.

3個實驗場景中的超參數(shù)如表2所示.

表2 本文實驗場景的超參數(shù)

4.3 實驗結(jié)果分析

在框架上,本文較多借鑒了目前性能最好的多智能體深度強化學習算法-多智能體深度確定性策略梯度算法,因此選擇與該算法進行對比實驗.此外還進行了消融實驗,分別確定本文所提每個方法的貢獻.圖3展示了本文算法(MA-D4PG) 以及3 個消融實驗和MA-DDPG 在該實驗環(huán)境中的性能.其中MAD4PG-no distributional 所示曲線表示本文算法去掉第3.1 節(jié)所述改進后的運行效果,MAD4PG-no multistep 所示曲線表示本文算法去掉3.2 節(jié)所述改進的運行效果,MAD4PGno distributed 所示曲線表示本文算法去掉第3.3 節(jié)所述改進的運行效果.

從圖3(a)中可看到在多智能體合作清潔的場景中,本文算法MA-D4PG 在收斂速度和最終收斂的Episode Reward 值這兩個指標上都有最好的表現(xiàn),并且算法的穩(wěn)定性更好.對MAD4PG-no distributional/MAD4PG-no distributed 這兩條曲線進行分析可看出,第3.1 節(jié)和第3.3 節(jié)所述的改進對算法最后收斂的Episode Reward值的提升雖不太明顯,但是加快了算法的收斂速度.

對圖3(b)進行分析可得,在多人機監(jiān)控場景中,相較MA-DDPG 算法,本文算法(MA-D4PG)收斂速度較慢,但是最終收斂的Episode Reward 值約是MA-DDPG的3.6 倍,智能體的決策能力得到了極大地增強.對MAD4PG-no distributional/MAD4PG-no distributed 分析可得,第3.1 節(jié)和第3.3 節(jié)所述改進使得最終收斂的Episode Reward值分別提升了約97%和43%.

對圖3(c)分析可得,在多智能體救援場景中,本文算法(MA-D4PG)的收斂速度約是MA-DDPG 算法的3.75 倍.對MAD4PG-no multistep/MAD4PG-no distributed 兩條曲線分析可得,第3.2 節(jié)和第3.3 節(jié)所述改進使得算法的收斂速度分別提升了約185%和100%.

對圖3(a),圖3(b)的MAD4PG-no multistep 曲線聯(lián)合分析可看出,去掉多步回報的改進,算法性能下降最大,并且去掉該改進會導(dǎo)致算法的穩(wěn)定性顯著下降.這兩個實驗場景中智能體只包含一維的離散動作空間,控制任務(wù)相對簡單.從中可看出在離散控制的多智能體場景中,引入多步回報對算法性能的貢獻最大,而第3.1 節(jié)和第3.3 節(jié)所述改進之間的互補作用較小.

圖3 本文算法性能對比圖

對圖3(c)的MAD4PG-no distributional 曲線分析可得,去掉值分布的改進,算法的收斂速度降低最大,并且算法的穩(wěn)定性也有一定的下降.該實驗環(huán)境中的控制任務(wù)比較復(fù)雜,既包含連續(xù)動作,又包含離散動作,而前兩個實驗場景中智能體只包含一維的離散動作空間.從中可看出在復(fù)雜的控制任務(wù)中,引入值分布對算法性能的貢獻最為突出.

5 結(jié)論與展望

本文的主要貢獻是提出了一種基于值分布的多智能體分布式策略梯度算法,利用值分布替代期望值,進一步區(qū)分智能體行為的好壞,而不是簡單地將其平均為期望值;同時引入了多步回報增加智能體的預(yù)見能力,提高算法穩(wěn)定性;此外引入了分布式數(shù)據(jù)生成框架將多智能體場景中智能體與環(huán)境交互生成經(jīng)驗數(shù)據(jù)和網(wǎng)絡(luò)更新解耦,加快算法的收斂.本文算法在3 個實驗場景中都實現(xiàn)了最好的性能.這3 項改進都有助于提升本文算法(MA-D4PG)的整體性能,在前兩個實驗場景中對性能貢獻最大的改進是多步回報.而在復(fù)雜的任務(wù)場景中,值分布的貢獻變得更加突出.本文的實驗場景都是基于多智能體合作的場景,接下來的研究工作是在競爭場景甚至既有合作又有競爭的混合場景中研究本文算法的性能.