基于優(yōu)先經(jīng)驗回放的多智能體協(xié)同算法

黃子蓉，甯彥淞，王 莉

(太原理工大學(xué) 大數(shù)據(jù)學(xué)院，山西 晉中 030600)

協(xié)作是多智能體系統(tǒng)的核心，智能體間通過協(xié)調(diào)配合可提高團隊協(xié)作效率且獲得更高的利益。深度強化學(xué)習(xí)結(jié)合了深度學(xué)習(xí)自學(xué)習(xí)、自適應(yīng)的能力和強化學(xué)習(xí)感知試錯能力，在多智能體協(xié)同中取得了階段性成果，如星際爭霸Ⅱ[1]、交通樞紐任務(wù)[2]、飛機編隊[3]等。但基于深度強化學(xué)習(xí)的多智能體協(xié)同算法仍然存在經(jīng)驗數(shù)據(jù)回放、可擴展性和合作性能等諸多方面的挑戰(zhàn)。

On-policy強化學(xué)習(xí)算法中，智能體與環(huán)境交互一次獲得的經(jīng)驗元組(st,at,rt,st+1)僅利用一次便被拋棄。為了重復(fù)利用歷史經(jīng)驗數(shù)據(jù)，DQN(Deep Q-Networks)算法中引入經(jīng)驗回放緩存機制[4-5]，將歷史數(shù)據(jù)存入經(jīng)驗回放緩存池中，極大地提高了經(jīng)驗利用率。但先前的工作采取隨機采樣方式回放經(jīng)驗或僅采樣近期經(jīng)驗數(shù)據(jù)，忽略了經(jīng)驗數(shù)據(jù)的優(yōu)先級，這可能造成成功經(jīng)驗很快被遺忘或成功經(jīng)驗較少的問題。SCHAUL et al[6]研究者提出的PER(prioritized experience replay)算法對經(jīng)驗數(shù)據(jù)進行優(yōu)先級評估和排序，在采樣時選取優(yōu)先級較高的經(jīng)驗進行模型訓(xùn)練。該算法使重要經(jīng)驗被回放的概率增大，增加了模型采樣效率和學(xué)習(xí)效率。但這種算法僅關(guān)注單智能體環(huán)境，隨著科技的發(fā)展，人們不再僅滿足于用深度強化學(xué)習(xí)算法控制單智能體，基于深度強化學(xué)習(xí)的多智能體協(xié)同研究逐步進入人們視野。如何在多智能體環(huán)境中有效利用歷史經(jīng)驗且提高采樣效率和合作性能成為關(guān)鍵研究挑戰(zhàn)。

多智能體合作環(huán)境中，集中訓(xùn)練分散執(zhí)行的框架已被證明是處理智能體間合作的有效范式。訓(xùn)練階段，集中訓(xùn)練的框架允許每個智能體的評判網(wǎng)絡(luò)使用其他智能體的狀態(tài)和動作信息，幫助智能體更好地合作。執(zhí)行階段，分散執(zhí)行的框架使智能體僅依賴它自身的觀測進行決策。這一范式解決了多智能體環(huán)境非平穩(wěn)問題。當面對連續(xù)型環(huán)境時，MADDPG(multi-agent deep deterministic policy gradient)算法[7]成為提升智能體間合作性能的代表性方法。MADDPG算法遵循集中訓(xùn)練分散執(zhí)行框架， 每個智能體有自己獨立的Critic網(wǎng)絡(luò)和Actor網(wǎng)絡(luò)，Critic網(wǎng)絡(luò)以所有智能體的觀測和動作為輸入，解決了多智能體環(huán)境非平穩(wěn)性問題。但當環(huán)境中智能體數(shù)量增多時，狀態(tài)動作空間的大小呈指數(shù)型增長，造成可擴展性差的問題。且MADDPG算法僅選取近期經(jīng)驗進行回放，使之前的經(jīng)驗被遺忘，經(jīng)驗利用率低。MAAC算法[8]嘗試解決上述問題。首先，MAAC算法學(xué)習(xí)帶有注意力機制的Critic網(wǎng)絡(luò)，注意力機制使智能體動態(tài)地選取周邊信息，改善了智能體在復(fù)雜環(huán)境中的合作性能。同時，模型的輸入維度隨智能體的增長呈線性增長趨勢，而非之前工作中的二次增長，一定程度上解決了可擴展性差的問題。其次，MAAC算法采用隨機采樣的方式進行經(jīng)驗回放，利用了歷史經(jīng)驗，但該算法仍忽略了歷史經(jīng)驗的重要程度。本文擴展了MAAC算法，提出一種基于優(yōu)先經(jīng)驗回放的多智能體協(xié)同算法(prioritized experience replayfor multi-agent cooperation，PEMAC)。

該算法的主要貢獻為：

1) 在多智能體系統(tǒng)中，算法基于TD誤差求出每條經(jīng)驗數(shù)據(jù)的優(yōu)先級，每次采樣均采取優(yōu)先級較高的經(jīng)驗數(shù)據(jù)更新網(wǎng)絡(luò)。PEMAC算法提升了訓(xùn)練數(shù)據(jù)的質(zhì)量，從而提升了模型收斂速度和智能體的合作性能。

2) PEMAC算法使用了基于注意力機制的Critic網(wǎng)絡(luò)學(xué)習(xí)智能體間的合作，使智能體動態(tài)地選取周邊信息，一定程度上實現(xiàn)多智能體系統(tǒng)的可擴展性。算法適用于合作、競爭和合作競爭混合的環(huán)境。

1 相關(guān)工作

深度強化學(xué)習(xí)已有很長的發(fā)展歷史。其中，幾個關(guān)鍵的研究點為：智能體如何使用歷史經(jīng)驗提高經(jīng)驗利用率；智能體如何提高合作性能；面對智能體數(shù)量較多的環(huán)境時模型的可擴展性等。

針對智能體經(jīng)驗利用率問題，MNIH et al[5]提出的DQN算法引入經(jīng)驗回放緩存機制，將經(jīng)驗元組存入經(jīng)驗回放緩存池中，極大地提高了經(jīng)驗利用率。但其對所有數(shù)據(jù)均勻采樣，忽略了經(jīng)驗數(shù)據(jù)的重要程度。SCHAUL et al[6]提出的PER算法對經(jīng)驗數(shù)據(jù)進行優(yōu)先級評估和排序，采樣時選取優(yōu)先級較高的經(jīng)驗進行模型訓(xùn)練，使高優(yōu)先級的經(jīng)驗被回放的概率增大，增加了模型采樣效率和學(xué)習(xí)效率。HOU et al[9]學(xué)者將PER算法引入DDPG(deep deterministic policy gradient)算法中，進一步提高了DDPG算法中經(jīng)驗回放機制的效率，從而加速訓(xùn)練過程。SHEN et al[10]將TD誤差的分布進行分段，然后根據(jù)更新后的TD誤差對經(jīng)驗進行分類，實現(xiàn)相似經(jīng)驗的交換機制，改變經(jīng)驗池中的經(jīng)驗的生命周期。這一算法降低了經(jīng)驗池大小，節(jié)約了系統(tǒng)內(nèi)存。BU et al[11]提出DPSR算法為經(jīng)驗元組中的舊狀態(tài)選擇新動作，計算新的TD誤差，將原始緩存池中TD誤差值最小經(jīng)驗元組替換，解決了模型無法選擇TD誤差較小的經(jīng)驗元組的問題。

針對多智能體合作問題，集中訓(xùn)練分散執(zhí)行的框架已被證明是處理智能體間合作的一個有效范式。集中訓(xùn)練階段，智能體的評判網(wǎng)絡(luò)輸入所有智能體的狀態(tài)和動作，分散執(zhí)行階段智能體僅依賴它自身觀測和策略網(wǎng)絡(luò)進行決策，評判網(wǎng)絡(luò)失效。這一框架中，VDN[12]和QMIX[13]算法學(xué)習(xí)聯(lián)合的動作值函數(shù)，然后將其分解為智能體自身的值函數(shù)，達成智能體間有效的合作。但這些方法僅適用于合作環(huán)境，且很難處理大的動作空間的游戲場景，尤其是具有連續(xù)動作空間的場景。COMA[14]和CoRe[15]算法使用反事實基線方法推斷每個智能體對團隊利益的貢獻，從而達成智能體間合作。每個智能體的反事實基線是通過比較智能體的聯(lián)合動作值函數(shù)和將其他智能體的動作固定后只改變當前智能體的動作獲得的動作值函數(shù)得出的。然而這些方法必須為每個智能體所有給定動作都計算一條基線。當智能體數(shù)量增多或智能體的動作空間較大時，這些方法將更難訓(xùn)練。且上述方法僅從環(huán)境中獲得聯(lián)合獎勵，對純合作環(huán)境適用，但對于競爭和合作競爭共存的環(huán)境不適用。

MADDPG算法同樣遵循集中訓(xùn)練分散執(zhí)行的框架，該算法中每個智能體都有自身的Actor網(wǎng)絡(luò)和Critic網(wǎng)絡(luò)，所以適用于合作、競爭和合作競爭共存的環(huán)境。但MADDPG算法僅選取近期經(jīng)驗進行回放，使之前的經(jīng)驗被遺忘，經(jīng)驗利用率低，且模型無法通過經(jīng)驗學(xué)習(xí)一個智能體間的顯式通信，模型的可擴展性較差。MD-MADDPG算法[16]通過引入存儲設(shè)備，端到端的學(xué)習(xí)智能體間的顯式通信協(xié)議，提高智能體的合作性能。SMARL算法[17]提出一種基于Seq2eq序列多智能體強化學(xué)習(xí)算法，該算法將智能體策略網(wǎng)絡(luò)分解為動作網(wǎng)絡(luò)和目標網(wǎng)絡(luò)兩部分，可以適應(yīng)智能體規(guī)模動態(tài)變化的環(huán)境。BiC-DDPG算法[18]使用雙向RNN結(jié)構(gòu)實現(xiàn)信息通信。當智能體合作時，算法采用了一種映射方法將連續(xù)的聯(lián)合動作空間輸出映射到離散的聯(lián)合動作空間，解決智能體在大型聯(lián)合動作空間上的決策問題。但大多數(shù)環(huán)境中通信信道、通信協(xié)議是不可用的或通信帶寬受限制，使智能體間可進行交流的信息變少。MAAC算法擴展了MADDPG算法，學(xué)習(xí)帶有注意力機制的Critic網(wǎng)絡(luò)，降低模型輸入維度，一定程度上解決了可擴展性差的問題。且該算法采用隨機采樣的方式進行經(jīng)驗回放，利用了歷史經(jīng)驗，但該算法仍忽略了歷史經(jīng)驗的重要程度。本文基于MAAC算法提出一種基于優(yōu)先經(jīng)驗回放的多智能體協(xié)同算法PEMAC.PEMAC算法為每條經(jīng)驗元組計算優(yōu)先級，并基于這一優(yōu)先級選取歷史經(jīng)驗，訓(xùn)練Critic網(wǎng)絡(luò)和Actor網(wǎng)絡(luò)。

2 基于優(yōu)先經(jīng)驗回放的多智能體協(xié)同算法

現(xiàn)實世界中，智能體往往通過不斷試錯，從錯誤經(jīng)驗中學(xué)習(xí)知識，從而實現(xiàn)某一目標。如人類在學(xué)會走路之前經(jīng)過了無數(shù)次摔跤。受這一思想的啟發(fā)，本文提出了PEMAC算法。該算法利用TD誤差評估經(jīng)驗元組的優(yōu)先級，然后選取優(yōu)先級大的經(jīng)驗訓(xùn)練Actor網(wǎng)絡(luò)和Critic網(wǎng)絡(luò)。同時考慮到智能體和環(huán)境交互時會選擇性地關(guān)注周邊智能體中的一些重要信息，這樣智能體能更好地做出決策。PEMAC算法在Critic網(wǎng)絡(luò)部分引入多頭自注意力機制，動態(tài)地選擇其要關(guān)注智能體的哪些信息，從而提高多智能體在復(fù)雜環(huán)境中的交互性能，網(wǎng)絡(luò)框架如圖1所示。

圖1 PEMAC算法框架圖Fig.1 Architecture of PEMAC

具體地，在經(jīng)驗存儲和采樣階段，先初始化所有智能體在t時刻的狀態(tài)，將狀態(tài)作為智能體的局部觀測o，o=s=(s1,t,…,sn,t)，用參數(shù)θ={θ1,…,θn}初始化策略網(wǎng)絡(luò)，策略網(wǎng)絡(luò)生成策略集π={π1,…,πn}，然后智能體根據(jù)局部觀測和策略集做出t時刻的決策a，a=(a1,t,…,an,t)，智能體在狀態(tài)s，執(zhí)行動作a，與環(huán)境交互獲得了獎勵r，r=(r1,t,…,rn,t)，且智能體轉(zhuǎn)移到t+1時刻狀態(tài)s′=(s1,t+1,…,sn,t+1).之后將每個智能體的游戲軌跡四元組(si,t,ai,t,ri,t,si,t+1)和經(jīng)驗優(yōu)先級Pi,t存入經(jīng)驗回放緩存區(qū)～U(D).其中經(jīng)驗優(yōu)先級Pi,t初始時刻均賦值為最大概率1.最后本文從U(D)中選取Pi,t值最大的一個批次的經(jīng)驗作為模型訓(xùn)練數(shù)據(jù)集。

在模型訓(xùn)練階段，每個智能體將自己t時刻的狀態(tài)和動作輸入各自評判網(wǎng)絡(luò)的全連接編碼器中，智能體i的編碼信息為ei,t，ei,t=gi(si,t,ai,t).gi為一層的MLP編碼器。然后對智能體的編碼信息進行多頭自注意力選取，選取后的信息為(x1,t,…,xn,t).其中，

xi,t=∑j≠iαjvj=∑j≠iαjh(Vej,t).

(1)

式中：V為一個共享的線性變換矩陣，h為非線性函數(shù)(本文選取ReLU函數(shù))，注意力權(quán)重αj為智能體i的信息編碼ei,t與線性變換矩陣Wq相乘后得到的鍵碼與鄰居智能體j的鍵碼求相似度得到，即：

(2)

接著將智能體i的編碼信息ei和其他智能體經(jīng)過注意力選取后的信息xi,t輸入到一個兩層的全連接網(wǎng)絡(luò)fi中，進而得出智能體i的動作值函數(shù)Qi，即:

(3)

(4)

(5)

其中α是在獎勵值部分加入最大熵后的超參，遵循SAC算法模型。然后可通過TD誤差更新智能體i在t時刻的經(jīng)驗元組的采樣概率Pi,t，具體地：

(6)

pi=|LQi(ψ)|+ε.

(7)

其中指數(shù)σ決定使用多少優(yōu)先級，當σ=0時為均勻采樣。參數(shù)μ和β是結(jié)合貪婪優(yōu)選算法和隨機選擇的優(yōu)點，保證經(jīng)驗元組的更新概率是單調(diào)的，同時也保證了所有經(jīng)驗元組以較高的概率更新經(jīng)驗回放緩存池，而低優(yōu)先級的經(jīng)驗元組也可以一定概率更新緩存池。ε為正數(shù)，防止TD誤差逼近0時，經(jīng)驗元組的采樣概率逼近于0.此時策略網(wǎng)絡(luò)的更新變?yōu)椋?/p>

(8)

上述策略網(wǎng)絡(luò)更新中，PEMAC算法用反事實機制方法解決信度分配問題，即排除其他智能體對當前智能體期望收益的影響。b(o,ai)是反事實基線，為：

(9)

3 實驗

獎勵(reward)是強化學(xué)習(xí)中一個重要的評估指標，它指導(dǎo)智能體優(yōu)化策略且反映了強化學(xué)習(xí)中任務(wù)的完成程度。 為了驗證算法的有效性，本章以獎勵作為評價指標，分別基于合作尋寶[7]和漫游者-發(fā)射塔[8]兩種環(huán)境進行了實驗驗證。合作尋寶和漫游者-發(fā)射塔環(huán)境是完全合作的環(huán)境，本文控制環(huán)境中所有的智能體。

3.1 實驗環(huán)境

合作尋寶環(huán)境中，我方智能體必須在有限的步長內(nèi)協(xié)調(diào)它們的行為盡可能收集到所有寶藏。如圖2(a)所示，粉色的大圓代表我方智能體，其他顏色的小圓代表寶藏。我方智能體能觀察到其他智能體和寶藏的相應(yīng)位置。將智能體到寶藏的相對位置作為智能體的獎勵。這就意味著，我方智能體必須盡可能地尋找與自己距離最近的寶藏，同時避免與其他智能體到達相同的寶藏處。另外，智能體占據(jù)一定的物理空間，當智能體間相互碰撞時會受到一定程度的懲罰。

圖2 實驗環(huán)境Fig.2 Experimental environment

漫游者-發(fā)射塔環(huán)境中總共有2N個智能體，N個為漫游者，N個為發(fā)射塔。另外環(huán)境中設(shè)有N+1個隨機地標。如圖2(b)所示，灰色智能體為發(fā)射塔，大圓表示漫游者，小圓表示隨機地標。每次迭代中，漫游者和塔隨機配對。漫游者無法探知周邊環(huán)境和目標地標位置，其必須依賴于發(fā)射塔的通信。而發(fā)射塔可以定位漫游者的位置以及它們的目標地標。

3.2 實驗設(shè)置

對于合作尋寶環(huán)境來說，為驗證算法在智能體數(shù)量較多的環(huán)境中模型仍適用，本文分別設(shè)置了3個合作的智能體和4個合作的智能體。環(huán)境中目標地標寶藏的數(shù)量與智能體數(shù)量一致，即分別選取了3個寶藏和4個寶藏。各個智能體計算它距離各個寶藏的相對距離，然后智能體以距離它最近的寶藏與當前智能體的相對距離的負值作為獎勵。但當智能體間互相碰撞時，智能體得到-1的懲罰。

對于漫游者-發(fā)射塔環(huán)境，本文設(shè)置了2個漫游者，2個發(fā)射塔，3個目標地標。漫游者以其與目標地標距離的負值作為獎勵，發(fā)射塔以與其配對的漫游者距離目標地表的距離的負值作為獎勵。但當智能體間互相碰撞時，智能體得到-1的懲罰。

另外，本文選取當前運行的進程數(shù)+當前運行次數(shù)×1 000作為隨機種子初始化環(huán)境。每輪游戲設(shè)置了25個步長。為證明算法有效性，本文中每種算法都在所有環(huán)境中獨立運行了5次，獎勵選取5次運行的平均結(jié)果。

3.3 實驗結(jié)果

為驗證PEMAC算法的有效性，本章選取MADDPG算法、MD-MADDPG算法和MAAC算法作為基線模型進行對比試驗。表1顯示了當模型收斂時，所有環(huán)境中智能體所在團隊5次運行結(jié)果的平均獎勵。表中所示結(jié)果為未經(jīng)過平滑的平均獎勵和浮動范圍。圖3顯示了3個智能體的合作尋寶環(huán)境中，每種算法獲得獎勵的變化趨勢，圖4顯示了4個智能體的合作尋寶環(huán)境中獎勵的變化趨勢，圖5顯示了漫游者-發(fā)射塔環(huán)境中獎勵的變化趨勢。所有圖均為經(jīng)過smooth函數(shù)平滑后的獎勵變化趨勢圖。

表1 模型收斂后合作尋寶和漫游者-發(fā)射塔環(huán)境中的平均獎勵Table 1 Average reward per episode after model converging in the cooperative treasure hunt and the rover-tower environments

表1和圖3的結(jié)果表明，在合作尋寶環(huán)境中，當智能體數(shù)量為3時，智能體在局部觀測情況下，PEMAC算法的性能優(yōu)于MADDPG算法8.7%，優(yōu)于MD-MADDPG算法5.2%，優(yōu)于MAAC算法2.9%.表1和圖4的結(jié)果表明，當智能體數(shù)量為4時，PEMAC算法的性能優(yōu)于MADDPG算法8.4%，優(yōu)于MD-MADDPG算法3.5%，優(yōu)于MAAC算法1.6%.

圖3 合作尋寶環(huán)境中智能體數(shù)量為3時獎勵的變化趨勢Fig.3 Change trend of rewards when the number of agents is three in the cooperative treasure hunt environment

圖4 合作尋寶環(huán)境中智能體數(shù)量為4時獎勵的變化趨勢Fig.4 Change trend of rewards when the number of agents is four in the cooperative treasure hunt environment

表1和圖5的結(jié)果表明，在漫游者-發(fā)射塔環(huán)境中，智能體在局部觀測情況下，PEMAC算法的性能是MADDPG算法的118.09倍，是MD-MADDPG算法的204.11倍，比MAAC算法的性能高3.7%.也證明當環(huán)境較為復(fù)雜時，注意力機制可以使智能體有選擇地關(guān)注周邊信息，從而提升合作性能。

圖5 漫游者-發(fā)射塔環(huán)境中的獎勵變化趨勢Fig.5 Change trend of rewards in the rover-tower environment

由上可知，PEMAC算法整體性能均高于MADDPG算法、MD-MADDPG算法和MAAC算法。引入優(yōu)先經(jīng)驗回放，使重要經(jīng)驗被回放的概率增大，學(xué)習(xí)更有效。智能體可從大量失敗經(jīng)驗中更有效地學(xué)習(xí)到隱藏的成功經(jīng)驗，從而提升算法性能。且由圖3、圖4和圖5可知，PEMAC算法的收斂速度比其他算法的收斂速度快。算法收斂速度由智能體獲得相同獎勵所需要的運行次數(shù)和模型趨于穩(wěn)定所運行的迭代步?jīng)Q定。另外，由表1和圖中的浮動范圍可知，當模型收斂后，智能體使用PEMAC算法獲得的獎勵在平均獎勵附近波動范圍比MAAC算法波動范圍小，因而PEMAC算法可以提高MAAC算法的穩(wěn)定性。

為了更細粒度地顯示注意力機制如何工作，本文對漫游者-發(fā)射塔環(huán)境中漫游者對所有發(fā)射塔的注意力權(quán)重進行了可視化分析。如圖6所示，流浪者1對與其匹配的發(fā)射塔1的關(guān)注度高于對發(fā)射塔2的關(guān)注度。流浪者2對發(fā)射塔2的關(guān)注度高于發(fā)射塔1。經(jīng)過分析可知漫游者在無法探知周邊情況時，學(xué)會了關(guān)注與其配對的塔，并與塔進行通信，從而提高智能體收益。

圖6 漫游者對發(fā)射塔的注意力權(quán)重Fig.6 Attention weights over all tower for a rover in rover-tower environment

4 結(jié)束語

本文提出基于優(yōu)先經(jīng)驗回放的多智能體協(xié)同算法PEMAC.該算法通過使用優(yōu)先經(jīng)驗回放機制，從失敗經(jīng)驗中學(xué)習(xí)隱藏成功經(jīng)驗，提升了模型性能，加快了收斂速度和模型穩(wěn)定性。同時使用注意力機制使智能體可以選擇性的關(guān)注周邊信息，進一步提升了模型性能。最后本文基于合作尋寶和流浪者-發(fā)射塔環(huán)境對算法性能進行對比驗證，實驗結(jié)果表明PEMAC算法具有較優(yōu)的合作性能。

本文雖對智能體數(shù)量增多時模型性能進行了實驗驗證，但環(huán)境規(guī)模仍受限。接下來計劃擴展多智能體環(huán)境規(guī)模和環(huán)境復(fù)雜度，將PEMAC算法推廣到更復(fù)雜的環(huán)境中。