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

陳妙云,王 雷,盛 捷

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

1 引言

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

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

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

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

2 相關工作

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

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

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

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

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

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

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

其中,Q(St,At) 表示狀態動作對的預期回報的期望值.相應的動作策略網絡的梯度公式如式(4)所示:

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

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

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

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

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

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

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

3.1 基于值分布的critic 更新

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

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

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

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

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

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

3.2 多步回報

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

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

3.3 分布式數據生成和網絡更新

針對模型耦合度高無法充分利用計算資源的問題,本文引入了分布式數據生成的框架(APE-X)將多智能體場景中智能體與環境交互生成經驗數據和網絡更新兩部分進行解耦.負責數據生成的部分稱為Actor,負責從經驗回放池中采樣數據進行網絡更新的部分稱為Learner.Actor的網絡結構與Learner 完全一致,只負責與環境交互得到經驗數據存入經驗回放池中,不執行梯度計算進行參數更新,而是定期復制Learner的網絡參數.Learner 只負責從經驗回放池中采樣數據進行網絡更新而不負責與環境進行交互.本文算法并行運行多個獨立的Actor,分別與環境進行交互得到經驗數據{St+1-N,At+1-N,Rt+1-N,St+1},寫入同一個經驗緩沖池中.Learner 從該經驗緩沖池中隨機采樣M批經驗數據進行網絡更新.具體的算法框架圖如圖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 分布式數據生成框架示意圖

3.4 本文算法小結

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

算法1.經驗數據生成-Actor 1)初始化 值,智能體數量K,經驗回放池B,初始化軟更新頻率TAU(θ1:k N Actor,ω1:kActor)←(θ1:kLearner,ω1:kLearner)2)初始化Actor 網絡參數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)根據式(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.網絡更新-Learner 1)初始化采樣批次M,最大更新步數T(θ1:k Learner,ω1:kLearner)2)隨機初始化網絡參數target,ω1:ktarget)←(θ1:kLearner,ω1:kLearner)3)初始化目標網絡參數(θ1:k 4)For do BM t=1,···,T 5)If len()

4 實驗分析

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

1×106

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

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

4.1 實驗環境配置

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

表1 本文實驗環境配置

4.2 實驗場景

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

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

圖2 實驗場景示意圖

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

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

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

表2 本文實驗場景的超參數

4.3 實驗結果分析

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

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

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

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

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

圖3 本文算法性能對比圖

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

5 結論與展望

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