增強協作多智能體強化學習中的全局信用分配機制

姚興虎　 宋光鑫

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

關鍵詞：深度學習;強化學習;多智能體系統

中圖分類號：TP181????? 文獻標識碼：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

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

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

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

在“中心訓練-分散執行”框架下，設計了一種新的全局信用分配結構并提出了一種更適宜處理非馬爾可夫獎勵的值函數估計方式。主要貢獻如下：

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

2）針對多智能體環境中的非馬爾可夫獎勵問題，提出了一種新的值函數估計方式。這一方式通過融合多步獎勵信號的方式得到了一種基于λ回報的時間差分目標;

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

1 背景知識

1.1 問題定義

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

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

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

1.2 “中心訓練-分散執行”算法

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

在CTDE算法中，中心化值函數Qπtot與非中心化值函數Qi之間的約束關系直接決定了算法的泛化能力和優化代價。常見的約束關系為：每個智能體單獨按照各自的值函數進行決策，得到的局部最優動作的聯合即為全局的最優動作，因此在執行階段每個智能體可以按照自己的值函數進行動作的選擇。

在這一假設下的主流算法包括：值分解網絡[9]（value decomposition network， VDN），單調值分解網絡[5]（QMIX）和Q值變換網絡[10]（QTRAN）。VDN算法假設所有智能體的聯合值函數Qπtot=∑Ni=1Qi;QMIX算法則假設對每個智能體i都有單調約束關系QtotQi≥0成立;QTRAN則通過對Q值進行變換構造更為復雜的約束關系。

1.3 環境的非馬爾可夫獎勵問題

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

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

2 所提算法

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

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

受深度殘差網絡[11]和高速路網絡[12]啟發，通過在獎勵分配網絡中引入高速路結構來在不增加算法優化代價的同時進行更為靈活的全局獎勵分配。具體來說，提出的獎勵高速路連接能夠使得每個智能體的值函數估計過程中能夠接觸到部分的全局獎勵信號，并與原有的全局信用分配機制相結合。這樣每個智能體在決策過程中能夠同時考慮其自身所分得得局部獎勵和整個團隊的全局獎勵。

2.2 融合多步獎勵的值函數估計方式

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

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

其中δt被稱為時間差分誤差項（TD-error），當采用單步TD算法對中心化的值函數進行估計時，其TD-error項如下所示：

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

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

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

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

2.3 優化目標與網絡架構

基于上述分析，提出一種基于獎勵高速路連接與融合多步獎勵的協作多智能體強化學習算法。該算法以QMIX算法為基本框架，在獎勵分配網絡中引入獎勵高速路連接并在估計中心化值函數的過程中采用了融合多步回報的值函數估計方式。具體來說，所提算法可利用基于梯度的優化算法端到端地最小化如下的損失函數：

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

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

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

3 實驗與結果分析

3.1 數據集和實現細節

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

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

3.2 實驗結果分析

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

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

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

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

4 結 論

針對深度多智能體強化學習中的全局獎勵分配問題，首先設計了一種高效進行獎勵分配的獎勵高速路連接結構;其次提出了一種融合多步獎勵的方式來處理多智能體環境中全局獎勵的非馬爾可夫性所帶來的問題。在多個復雜多智能體場景下的實驗結果表明，所提算法能夠取得性能提升，并且還具有很好穩定性。

參考文獻

[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.