增強(qiáng)協(xié)作多智能體強(qiáng)化學(xué)習(xí)中的全局信用分配機(jī)制

姚興虎　 宋光鑫

摘 要：針對協(xié)作多智能體強(qiáng)化學(xué)習(xí)中的全局信用分配機(jī)制很難捕捉智能體之間的復(fù)雜協(xié)作關(guān)系及無法有效地處理非馬爾可夫獎勵信號的問題，提出了一種增強(qiáng)的協(xié)作多智能體強(qiáng)化學(xué)習(xí)中的全局信用分配機(jī)制。首先，設(shè)計(jì)了一種新的基于獎勵高速路連接的全局信用分配結(jié)構(gòu)，使得智能體在決策時(shí)能夠考慮其所分得的局部獎勵信號與團(tuán)隊(duì)的全局獎勵信號;其次，通過融合多步獎勵信號提出了一種能夠適應(yīng)非馬爾可夫獎勵的值函數(shù)估計(jì)方法。在星際爭霸微操作實(shí)驗(yàn)平臺上的多個復(fù)雜場景下的實(shí)驗(yàn)結(jié)果表明：所提方法不僅能夠取得先進(jìn)的性能，同時(shí)還能大大提高樣本的利用率。

關(guān)鍵詞：深度學(xué)習(xí);強(qiáng)化學(xué)習(xí);多智能體系統(tǒng)

中圖分類號：TP181????? 文獻(xiàn)標(biāo)識碼：A

Enhancing Global Credit Assignment Mechanism for Cooperative

Multi-Agent Reinforcement Learning

YAO Xing-hu1，SONG Guang-xin2

（1.College of Computer Science and Technology， Nanjing University

of Aeronautics and Astronautics， Nanjing， Jiangsu 211106， China;

2.College of Science， Nanjing University of Aeronautics and Astronautics， Nanjing， Jiangsu 211106， China）

Abstract：In order to solve the problem that the global credit assignment mechanism in cooperative multi-agent reinforcement learning is difficult to capture the complex cooperative relationship among agents and cannot effectively deal with non-Markov reward signals， an enhanced global credit assignment mechanism in cooperative multi-agent reinforcement learning is proposed. Firstly， a new global credit assignment structure based on reward highway connection is designed， which enables each agent to consider the local reward signal and the team's global reward signal when making decisions. Secondly， by integrating multi-step rewards， a new value function estimation method which can adapt to non-Markov rewards is proposed. The experimental results of several complex scenarios on the StarCraft multi-agent challenges show that the proposed method can not only achieve state-of-the-art performance， but also greatly improve the sample efficiency.

Key words：deep learning; reinforcement learning; multi-agent systems

現(xiàn)實(shí)世界中的很多問題都可以建模為多智能體強(qiáng)化學(xué)習(xí)問題。比如：多玩家電子游戲[1]，多無人車輛控制[2]，以及網(wǎng)絡(luò)路由包的傳輸[3]。然而，完全合作的多智能體強(qiáng)化學(xué)習(xí)問題面臨著兩個主要的挑戰(zhàn)：首先，智能體的聯(lián)合動作空間隨著智能體數(shù)量的增加，這使得直接利用單智能體算法進(jìn)行聯(lián)合建模會帶來維數(shù)災(zāi)難;其次，當(dāng)環(huán)境給出的獎勵信號是針對所有智能體的全局獎勵信號時(shí)，如何將這一全局獎勵信號進(jìn)行合理分配也是一個需要解決的問題。

對于上述問題，目前的主流方法是采用“中心訓(xùn)練-分散執(zhí)行”的框架[4][5]。這類方法的核心是如何建立中心化值函數(shù)與非中心化值函數(shù)之間結(jié)構(gòu)約束關(guān)系。值函數(shù)間約束關(guān)系的復(fù)雜程度直接影響了獎勵分配機(jī)制的好壞。簡單的約束關(guān)系不能夠捕捉智能體之間的復(fù)雜協(xié)作關(guān)系，而復(fù)雜的值函數(shù)結(jié)構(gòu)則會大大增加訓(xùn)練成本并降低樣本的利用效率。

此外，環(huán)境給出的獎勵信號往往具有很強(qiáng)的非馬爾可夫性[6][7]。即當(dāng)前狀態(tài)下智能體采取動作后，環(huán)境會經(jīng)過若干個時(shí)間步長的延遲才會給出針對這一動作的獎勵信號，或獎勵信號會在后續(xù)若干個時(shí)間步長持續(xù)給出。而在多智能體環(huán)境中，由于多個智能體之間的復(fù)雜交互以及環(huán)境的動態(tài)特性，這一非馬爾可夫獎勵現(xiàn)象則更為明顯。

在“中心訓(xùn)練-分散執(zhí)行”框架下，設(shè)計(jì)了一種新的全局信用分配結(jié)構(gòu)并提出了一種更適宜處理非馬爾可夫獎勵的值函數(shù)估計(jì)方式。主要貢獻(xiàn)如下：

1） 本文在“中心訓(xùn)練-分散執(zhí)行”的框架下，設(shè)計(jì)了一種新的全局信用分配機(jī)制。利用Q值混合網(wǎng)絡(luò)捕捉智能體之間復(fù)雜的約束關(guān)系，并引入獎勵高速路連接，使得智能體在決策時(shí)能夠同時(shí)考慮全局獎勵信號與其所分得的局部獎勵;

2）針對多智能體環(huán)境中的非馬爾可夫獎勵問題，提出了一種新的值函數(shù)估計(jì)方式。這一方式通過融合多步獎勵信號的方式得到了一種基于λ回報(bào)的時(shí)間差分目標(biāo);

3）通過以上兩個結(jié)構(gòu)與基于深度Q學(xué)習(xí)的多智能體強(qiáng)化學(xué)習(xí)方法建立聯(lián)系，得到了一種新的協(xié)作多智能體強(qiáng)化學(xué)習(xí)算法。這一算法具有更為高效的全局獎勵分配機(jī)制并能很好的處理非馬爾可夫獎勵。在星際爭霸微操作平臺上的多個復(fù)雜場景下的實(shí)驗(yàn)結(jié)果表明，所提出的新算法不僅能夠取得先進(jìn)的性能，并且還能大大提高樣本的利用率。

1 背景知識

1.1 問題定義

完全合作的多智能體強(qiáng)化學(xué)習(xí)問題可以被建模為部分可觀測馬爾可夫決策過程。具體來說，這一任務(wù)可以由七元組G=（S，A，P，r，Z，O，N，γ）來描述[8]。其中，s∈S表示環(huán)境真正的狀態(tài)， A表示每個智能體的動作空間，P（s'|s，a）：S×AN×S→[0，1]表示狀態(tài)轉(zhuǎn)移概率，rs，a：S×AN→R表示全局獎勵函數(shù)，智能體的數(shù)量為N?？紤]一個部分可觀測問題，在每個時(shí)刻，每個智能體i只能通過部分觀測函數(shù)Zs，i：S×N→O得到關(guān)于環(huán)境的部分信息oi∈O，γ∈[0，1]是獎勵折扣因子。在Dec-POMDP上的一個隨機(jī)策略可定義為映射πa|o：O×A→0，1。多智能體強(qiáng)化學(xué)習(xí)任務(wù)的最終目標(biāo)是為了最大化從環(huán)境中獲得的累積獎勵，即：

Es∈S，a∈π∑SymboleB@t=0γtrs，a（1）

其中，a，π分別表示智能體的聯(lián)合動作和聯(lián)合策略。

1.2 “中心訓(xùn)練-分散執(zhí)行”算法

近年來，“中心訓(xùn)練-分散執(zhí)行（central training with decentralized execution， CTDE）”框架由于概念簡單且優(yōu)化高效，成為求解Dec-POMDP的一類主流方法[4][5]。所謂“中心訓(xùn)練”指的是在訓(xùn)練階段通過維護(hù)一個中心化的值函數(shù)或者中心化的“評論家（critic）”來對所有智能體的行為進(jìn)行協(xié)調(diào);所謂“分散執(zhí)行”，指的是每個智能體在執(zhí)行階段，其策略僅依賴于其所觀測得到的部分信息。

在CTDE算法中，中心化值函數(shù)Qπtot與非中心化值函數(shù)Qi之間的約束關(guān)系直接決定了算法的泛化能力和優(yōu)化代價(jià)。常見的約束關(guān)系為：每個智能體單獨(dú)按照各自的值函數(shù)進(jìn)行決策，得到的局部最優(yōu)動作的聯(lián)合即為全局的最優(yōu)動作，因此在執(zhí)行階段每個智能體可以按照自己的值函數(shù)進(jìn)行動作的選擇。

在這一假設(shè)下的主流算法包括：值分解網(wǎng)絡(luò)[9]（value decomposition network， VDN），單調(diào)值分解網(wǎng)絡(luò)[5]（QMIX）和Q值變換網(wǎng)絡(luò)[10]（QTRAN）。VDN算法假設(shè)所有智能體的聯(lián)合值函數(shù)Qπtot=∑Ni=1Qi;QMIX算法則假設(shè)對每個智能體i都有單調(diào)約束關(guān)系QtotQi≥0成立;QTRAN則通過對Q值進(jìn)行變換構(gòu)造更為復(fù)雜的約束關(guān)系。

1.3 環(huán)境的非馬爾可夫獎勵問題

在馬爾可夫決策過程中，環(huán)境所給出的獎勵信號滿足馬爾可夫性質(zhì)，即獎勵信號rt僅依賴于最近的一個狀態(tài)以及智能體所采取的動作。然而，許多強(qiáng)化學(xué)習(xí)場景中的獎勵信號并不滿足這一性質(zhì)，比如：在足球游戲中，進(jìn)球所獲得的獎勵信號是對之前一段時(shí)間的狀態(tài)和動作的延遲獎勵;多智能體對抗問題下，摧毀敵方設(shè)施后，接下來的一段時(shí)間環(huán)境會針對當(dāng)前動作給出持續(xù)的獎勵信號。

因此，考慮設(shè)計(jì)更適合處理非馬爾可夫獎勵的多智能體算法有助于對全局獎勵信號進(jìn)行更為合理的分配并提高多智能體算法的性能。

2 所提算法

2.1 基于獎勵高速路連接的全局信用分配機(jī)制

隨著深度網(wǎng)絡(luò)隱藏層數(shù)量的增多，網(wǎng)絡(luò)的訓(xùn)練難度會不斷變大。為了解決由于網(wǎng)絡(luò)層數(shù)的增多所導(dǎo)致的退化問題，深度殘差網(wǎng)絡(luò)[11]針對輸入數(shù)據(jù)x深度殘差學(xué)習(xí)不再顯式地去擬合所希望的潛在映射Hx，而利用非線性映射擬合另一個映射Fx=Hx-x。高速路網(wǎng)絡(luò)[12]則通過門結(jié)構(gòu)對數(shù)據(jù)時(shí)直接通過高速路傳輸還是經(jīng)過神經(jīng)網(wǎng)絡(luò)變換進(jìn)行控制。這兩個方法實(shí)現(xiàn)方式簡單并能大大降低深度網(wǎng)絡(luò)的訓(xùn)練難度。

受深度殘差網(wǎng)絡(luò)[11]和高速路網(wǎng)絡(luò)[12]啟發(fā)，通過在獎勵分配網(wǎng)絡(luò)中引入高速路結(jié)構(gòu)來在不增加算法優(yōu)化代價(jià)的同時(shí)進(jìn)行更為靈活的全局獎勵分配。具體來說，提出的獎勵高速路連接能夠使得每個智能體的值函數(shù)估計(jì)過程中能夠接觸到部分的全局獎勵信號，并與原有的全局信用分配機(jī)制相結(jié)合。這樣每個智能體在決策過程中能夠同時(shí)考慮其自身所分得得局部獎勵和整個團(tuán)隊(duì)的全局獎勵。

2.2 融合多步獎勵的值函數(shù)估計(jì)方式

時(shí)間差分（temporaldifference， TD）算法[13]是對動作值函數(shù)進(jìn)行估計(jì)的通用算法，使用TD算法對中心化值函數(shù)Qtotτ，a進(jìn)行估計(jì)的一般形式如下所示：

Qtotτt，at←Qtotτt，at+δt，（2）

其中δt被稱為時(shí)間差分誤差項(xiàng)（TD-error），當(dāng)采用單步TD算法對中心化的值函數(shù)進(jìn)行估計(jì)時(shí)，其TD-error項(xiàng)如下所示：

δπt=Eπrt+1+γQτt+1，·-Qτt，at.（3）

這種基于單步TD算法的值函數(shù)估計(jì)方式被廣泛應(yīng)于在多智能體強(qiáng)化學(xué)習(xí)問題的中心化值函數(shù)估計(jì)上[5][9][10]。然而，當(dāng)環(huán)境給出的獎勵信號具有很強(qiáng)的非馬爾可夫性時(shí)，這種估計(jì)方式會帶來很大的估計(jì)偏差。所提算法采用一種變種的TD（λ）[13]方法作為中心化值函數(shù)的估計(jì)方式。具體來說，采用如下的時(shí)間差分誤差項(xiàng)Gλt作為中心化值函數(shù)的估計(jì)方式：

Gλt=1-λ∑SymboleB@n=1λn-1Gnt，（4）

其中Gnt=rt+1+γrt+2+…+γnEπQtotτt+n，at+n。

2.3 優(yōu)化目標(biāo)與網(wǎng)絡(luò)架構(gòu)

基于上述分析，提出一種基于獎勵高速路連接與融合多步獎勵的協(xié)作多智能體強(qiáng)化學(xué)習(xí)算法。該算法以QMIX算法為基本框架，在獎勵分配網(wǎng)絡(luò)中引入獎勵高速路連接并在估計(jì)中心化值函數(shù)的過程中采用了融合多步回報(bào)的值函數(shù)估計(jì)方式。具體來說，所提算法可利用基于梯度的優(yōu)化算法端到端地最小化如下的損失函數(shù)：

Lθ=1-αGλt-Qtotτ，a，s;θ，φ2+α∑Ni=1Gλt-Qiτi，ai，θi2（5）

其中Gλt的定義如（4）所示，而α則是控制Gλt流向混合網(wǎng)絡(luò)和獎勵高速路連接比例的超參數(shù)，θ=θ1，θ2，…，θN為所有智能體非中心化值網(wǎng)絡(luò)的參數(shù)集合，φ是中心化結(jié)構(gòu)額外的參數(shù)。

所提算法的結(jié)構(gòu)框架如圖1所示：每個智能體的非中心化的值函數(shù)網(wǎng)絡(luò)的輸入為當(dāng)前智能體的觀測值和上一個時(shí)刻的動作值，之后傳入全連接網(wǎng)絡(luò)進(jìn)行特征變換，變換后的信息傳入GRU模塊與歷史信息進(jìn)行融合，之后利用一層全連接網(wǎng)絡(luò)得到所有當(dāng)前智能體i的所有動作的Q值向量Qiτi，·，然后采用∈貪心算法進(jìn)行策略的選擇。獎勵分配網(wǎng)絡(luò)以每個智能體所采取動作的Q值Qiτi，ai為輸入，然后將經(jīng)過多層非線性變換和獎勵高速路連接得到的兩個數(shù)據(jù)流進(jìn)行融合得到全局的動作值Qtotτ，a。其中，獎勵分配網(wǎng)絡(luò)中對Q值進(jìn)行非線性變換的參數(shù)是由以全局狀態(tài)st為輸入的超網(wǎng)絡(luò)[15]所生成的。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集和實(shí)現(xiàn)細(xì)節(jié)

在星際爭霸微操作平臺[16]上進(jìn)行實(shí)驗(yàn)，選擇該實(shí)驗(yàn)平臺主要基于以下兩個目的：（1） 所提供的星際爭霸環(huán)境中僅有針對所有智能體的全局獎勵信號，因此很適合研究全局獎勵分配問題;（2）星際爭霸中的獎勵信號具有很強(qiáng)的非馬爾可夫性。其中的智能體角色代表如圖2所示，圖中左方為3個潛行者（Stalker），右邊為5個狂熱者（Zealot）。為了充分探究各種算法的魯棒性與樣本有效性，選取了實(shí)驗(yàn)平臺所提供的一個非對稱場景（asymmetric）（a） 2s_vs_1sc（控制同種類的2個智能體）， 和三個復(fù)雜的齊次對稱場景（heterogeneous & symmetric）（b） 3s5z（控制兩個種類的8個智能體）， （c） 1c3s5z（控制三個種類的9個智能體）， （d） 3s6z（控制兩個種類的9個智能體）進(jìn)行了實(shí)驗(yàn)。

智能體的非中心化網(wǎng)絡(luò)部分包括一個維度為64維的全連接網(wǎng)絡(luò)，全連接網(wǎng)絡(luò)的輸出被傳入一個GRU[17]模塊用來整合歷史信息，之后連接一個維度為64的全連接層，激活函數(shù)為ReLU[18]，最后輸出所有動作的Q值。中心化結(jié)構(gòu)部分引入了獎勵高速路連接來降低網(wǎng)絡(luò)的學(xué)習(xí)難度，與QMIX的結(jié)構(gòu)相同，中心化的網(wǎng)絡(luò)結(jié)構(gòu)同樣利用超網(wǎng)絡(luò)來產(chǎn)生混合網(wǎng)絡(luò)的參數(shù)。表達(dá)式（4）中的參數(shù)λ=0.8，損失函數(shù)（5）中的超參數(shù)α=0.2。實(shí)驗(yàn)中的所有算法均采用同樣的超參數(shù)，優(yōu)化器均為RMSprop，其中學(xué)習(xí)速率lr=0.0005。

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

將所提出的算法與當(dāng)前在這一平臺上的五種先進(jìn)算法QTRAN[10]，QMIX[5]，VDN[9]，COMA[4]和IQL[14]進(jìn)行對比。為保證公平性，所有算法在2s_vs_1sc和1c3s5z兩個場景中訓(xùn)練兩百萬個時(shí)間步長，在3s5z和3s6z上訓(xùn)練三百萬個時(shí)間步長。我們采用在訓(xùn)練過程中的測試勝率以及每局游戲中所獲得的累積獎勵值來進(jìn)行算法的性能評估。所提算法與對比算法的性能比較結(jié)果如圖3和圖4 所示。圖中實(shí)線和陰影區(qū)域表示獨(dú)立運(yùn)行10次算法所得的勝率均值和保留了95%置信區(qū)間的方差。

圖3的實(shí)驗(yàn)結(jié)果表明，所提出的方法在多個復(fù)雜場景下能夠取得最優(yōu)的性能。具體來說，在針對智能體數(shù)量較少的2s_vs_1sc場景，所提算法能夠取得有競爭力的結(jié)果。但隨著智能體數(shù)量的不斷增加，場景越來越復(fù)雜，從而使得已有的算法性能急劇下降且具有很大的偏差，而所提算法在能夠取得優(yōu)異性能的同時(shí)還具有很低的偏差。此外，圖3實(shí)驗(yàn)結(jié)果同樣表明，更為復(fù)雜的獎勵分配結(jié)構(gòu)不一定能夠帶來算法性能上的提升。事實(shí)上，具有較為復(fù)雜獎勵分配結(jié)構(gòu)的COMA算法和QTRAN算法在復(fù)雜的3s5z，3s6z以及1c3s5z場景下并沒有優(yōu)勢，而所提算法所采用的獎勵高速路結(jié)構(gòu)并沒有帶來額外的優(yōu)化代價(jià)，因此并不會增加算法的復(fù)雜度，從而能夠靈活擴(kuò)展到更為復(fù)雜的多智能體環(huán)境。

圖4的實(shí)驗(yàn)結(jié)果表明，所提出的算法有助于智能體在決策過程中獲得更多的累積獎勵。并且在環(huán)境變得越來越復(fù)雜時(shí)，其他先進(jìn)的算法所獲得的累積獎勵劇烈減少，而所提算法在面臨復(fù)雜環(huán)境時(shí)仍能獲得較多的累積獎勵值。這意味著采用融合多步獎勵的值函數(shù)估計(jì)方式和獎勵高速路結(jié)構(gòu)能夠使得智能體的策略更適合復(fù)雜環(huán)境下的非馬爾可夫獎勵。

圖3和圖4中的陰影面積大小可以作為算法穩(wěn)定性優(yōu)劣的一種衡量方式?？梢钥闯?，在2s_vs_1sc這一較為簡單的場景下，所有算法的性能方差并沒有顯著差異。而隨著智能體數(shù)量和種類的增多，基準(zhǔn)算法的性能波動明顯，尤其是在具有8個智能體的3s5z環(huán)境以及9個智能體的1c3s5z環(huán)境，QMIX算法的性能方差不斷增大。而所提出的方法則具有很好的穩(wěn)定性。

4 結(jié) 論

針對深度多智能體強(qiáng)化學(xué)習(xí)中的全局獎勵分配問題，首先設(shè)計(jì)了一種高效進(jìn)行獎勵分配的獎勵高速路連接結(jié)構(gòu);其次提出了一種融合多步獎勵的方式來處理多智能體環(huán)境中全局獎勵的非馬爾可夫性所帶來的問題。在多個復(fù)雜多智能體場景下的實(shí)驗(yàn)結(jié)果表明，所提算法能夠取得性能提升，并且還具有很好穩(wěn)定性。

參考文獻(xiàn)

[1]

VINYALS O， BABUSCHKIN I， CZARNECKI W M， et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning[J]. Nature， 2019， 575（7782）： 350-354.

[2] KIUMARSI B， VAMVOUDAKIS K G， MODARES H， et al. Optimal and autonomous control using reinforcement learning： A survey[J]. IEEE Transactions on Neural Networks and Learning Systems， 2017， 29（6）： 2042-2062.

[3] YE Da-yong， ZHANG Min-jie， YANG Yun. A multi-agent framework for packet routing in wireless sensor networks [J].Sensors， 2015， 15（5）： 10026-10047.

[4] FOERSTER J N， FARQUHAR G， AFOURAS T， et al. Counterfactual multi-agent policy gradients [C].AAAI Conference on Artificial Intelligence， 2018：2974-2982

[5] RASHID T， SAMVELYAN M， DE WITT C S， et al. Qmix： monotonic value function factorisation for deep multi-agent reinforcement learning [C]. International Conference on Machine Learning， 2018： 4292-4301.

[6] THIBAUX S， GRETTON C， SLANEY J， et al. Decision-theoretic planning with non-Markovian rewards[J]. Journal of Artificial Intelligence Research， 2006， 25： 17-74.

[7] GAON M， BRAFMAN R. Reinforcement? learning with non-Markovian rewards[C]. AAAI Conference on Artificial Intelligence， 2020， 34（04）： 3980-3987.

[8] OLIEHOEK F A， AMATO C. A concise introduction to decentralized POMDPs[M]. Springer International Publishing， 2016.

[9] SUNEHAG G， LEVER A， GRUSLY S， et al. Value-decomposition networks for cooperative multi-agent learning based on team reward [C]. International Conference on AutonomousAgents and Multi Agent Systems， 2018： 2085-2087.

[10]SONK Yung-hwan， KIM Dae-woo， KANG Wan-ju， et al. Qtran： learning to factorize with transformation for cooperative multi-agent reinforcement learning [C]， International Conference on Machine Learning，2019： 5887-5896.

[11]HE Kai-ming， ZHANG Xiang-yu， REN Shao-qing， et al. Deep residual learning for image recognition [C]. IEEE Conference on Computer Vision and Pattern Recognition， 2016：770-778

[12]SRIVASTAV A， RUPESH K， KLAUS G， et al. Training very deep networks [C]. Advances in Neural Information Processing Systems， 2015：2377-2385

[13]SUTTON R S， BARTO A G. Reinforcement learning： An introduction[M]. MIT Press， 2018.

[14]TAN Ming. Multi-agent reinforcement learning： independent vs. cooperative agents [C]. International Conference on Machine Learning， 1993：330–337.

[15]HA D， DAI A， LE Q V. Hypernetworks[J]. arXiv preprint arXiv：1609.09106， 2016.

[16]SAMVELYAN M， RASHID T， SCHROEDER C， et al. The StarCraft multi-agent challenge[C]. International Conference on Autonomous Agents and MultiAgent Systems. 2019： 2186-2188.

[17]CHUNG Jun-young，GULCEHREC， CHO K， et al.Empirical evaluation of gated recurrent neural networks on sequence modeling[C].In Advances in Neural Information Processing Systems， 2014.

[18]AGARAP A F. Deep learning using rectified linear units （relu）[J]. arXiv preprint arXiv：1803.08375， 2018.