2. 反事實多智能體策略梯度法方法（Counterfactual Multi-Agent Policy Gradients, COMA）

在合作式的多智能體學(xué)習(xí)問題中，每個智能體共享獎勵（即在同一個時刻獲得相同的獎勵），此時會存在一個 “置信分配” 問題（credit assignment）：如何去評估每個智能體對這個共享獎勵的貢獻(xiàn)？

COMA 方法在置信分配中利用了一種反事實基線：將智能體當(dāng)前的動作和默認(rèn)的動作進(jìn)行比較，如果當(dāng)前動作能夠獲得的回報高于默認(rèn)動作，則說明當(dāng)前動作提供了好的貢獻(xiàn)，反之則說明當(dāng)前動作提供了壞的貢獻(xiàn)；默認(rèn)動作的回報，則通過當(dāng)前策略的平均效果來提供（即為反事實基線）。在對某個智能體和基線進(jìn)行比較的時，需要固定其他智能體的動作。當(dāng)前策略的平均效果和優(yōu)勢函數(shù)的定義如下：

COMA 方法結(jié)合了集中式訓(xùn)練、分布式執(zhí)行的思想：分布式的個體策略以局部觀測值為輸入、輸出個體的動作；中心化的 critic 使用特殊的網(wǎng)絡(luò)結(jié)構(gòu)來輸出優(yōu)勢函數(shù)值。

具體地，critic 網(wǎng)絡(luò)的輸入包括了全局狀態(tài)信息 s、個體的局部觀測信息 o、個體的編號 a 以及其他智能體的動作，首先輸出當(dāng)前智能體不同動作所對應(yīng)的聯(lián)合 Q 值。然后， 再經(jīng)過 COMA 模塊，使用輸入其中的智能體當(dāng)前策略和動作，計算反事實基線以及輸出最終的優(yōu)勢函數(shù)。

圖 8：(a) COMA 方法中的 actor-critic 框架圖，(b) actor 的網(wǎng)絡(luò)結(jié)構(gòu)，(c) critic 的網(wǎng)絡(luò)結(jié)構(gòu)（包含了核心的 COMA 模塊來提供優(yōu)勢函數(shù)值）。圖源：[10]

2.2 value-based 的方法

在前面提到的 policy-based 方法中，中心化的值函數(shù)是直接使用全局信息進(jìn)行建模，沒有考慮個體的特點。在多智能體系統(tǒng)是由大規(guī)模的多個個體構(gòu)成時，這樣的值函數(shù)是難以學(xué)習(xí)或者是訓(xùn)練到收斂的，很難推導(dǎo)出理想的策略。并且僅依靠局部觀測值，無法判斷當(dāng)前獎勵是由于自身的行為還是環(huán)境中其他隊友的行為而獲得的。

值分解網(wǎng)絡(luò)（value decomposition networks, VDN）由 DeepMind 團(tuán)隊在 2018 年提出，該方法的核心是將全局的 Q(s,a)值分解為各個局部 Qi(si,ai)的加權(quán)和，每個智能體擁有各自的局部值函數(shù)。

這樣的分解方式，在聯(lián)合動作 Q 值的結(jié)構(gòu)組成方面考慮了個體行為的特性，使得該 Q 值更易于學(xué)習(xí)。另一方面，它也能夠適配集中式的訓(xùn)練方式，在一定程度上能夠克服多智能體系統(tǒng)中環(huán)境不穩(wěn)定的問題。在訓(xùn)練過程中，通過聯(lián)合動作 Q 值來指導(dǎo)策略的優(yōu)化，同時個體從全局 Q 值中提取局部的 Qi 值來完成各自的決策（如貪心策略 ai=argmax Qi），實現(xiàn)多智能體系統(tǒng)的分布式控制。

圖 9：左圖是完全分布式的局部 Q 值網(wǎng)絡(luò)結(jié)構(gòu)，右圖是 VDN 的聯(lián)合動作 Q 值網(wǎng)絡(luò)結(jié)構(gòu)?？紤]兩個智能體，它們的聯(lián)合動作 Q 值由個體的 Q1 和 Q2 求和得到，在學(xué)習(xí)時針對這個聯(lián)合 Q 值進(jìn)行迭代更新，而在執(zhí)行時個體根據(jù)各自的 Qi 值得到自身的動作 ai。圖源：[11]

VDN 對于智能體之間的關(guān)系有較強(qiáng)的假設(shè)，但是，這樣的假設(shè)并不一定適合所有合作式多智能體問題。在 2018 年的 ICML 會議上，有研究者提出了改進(jìn)的方法 QMIX。

QMIX 在 VDN 的基礎(chǔ)上實現(xiàn)了兩點改進(jìn)：1）在訓(xùn)練過程中加入全局信息進(jìn)行輔助；2）采用混合網(wǎng)絡(luò)對單智能體的局部值函數(shù)進(jìn)行合并（而不是簡單的線性相加）。

在 QMIX 方法中，首先假設(shè)了全局 Q 值和局部 Q 值之間滿足這樣的關(guān)系：最大化全局 Q_tot 值對應(yīng)的動作，是最大化各個局部 Q_a 值對應(yīng)動作的組合，即

在這樣的約束條件下，既能夠使用集中式的學(xué)習(xí)方法來處理環(huán)境不穩(wěn)定性問題以及考慮多智能體的聯(lián)合動作效應(yīng)（全局 Q 值的學(xué)習(xí)），又能夠從中提取出個體策略實現(xiàn)分布式的控制（基于局部 Q 值的行為選擇）。進(jìn)一步地，該約束條件可轉(zhuǎn)化為全局 Q 值和局部 Q 值之間的單調(diào)性約束關(guān)系：

令全局 Q 值和局部 Q 值之間滿足該約束關(guān)系的函數(shù)表達(dá)式有多種，VDN 方法的加權(quán)求和就是其中一種，但簡單的線性求和并沒有充分考慮到不同個體的特性，對全體行為和局部行為之間的關(guān)系的描述有一定的局限性。QMIX 采用了一個混合網(wǎng)絡(luò)模塊（mixing network）作為整合 Qa 生成 Q_tot 的函數(shù)表達(dá)式，它能夠滿足上述的單調(diào)性約束。

圖 10：QMIX 網(wǎng)絡(luò)結(jié)構(gòu)。圖源：[12]

在 QMIX 方法設(shè)計的網(wǎng)絡(luò)結(jié)構(gòu)中，每個智能體都擁有一個 DRQN 網(wǎng)絡(luò)（綠色塊），該網(wǎng)絡(luò)以個體的觀測值作為輸入，使用循環(huán)神經(jīng)網(wǎng)絡(luò)來保留和利用歷史信息，輸出個體的局部 Qi 值。

所有個體的局部 Qi 值輸入混合網(wǎng)絡(luò)模塊（藍(lán)色塊），在該模塊中，各層的權(quán)值是利用一個超網(wǎng)絡(luò)（hypernetwork）以及絕對值計算產(chǎn)生的：絕對值計算保證了權(quán)值是非負(fù)的、使得局部 Q 值的整合滿足單調(diào)性約束；利用全局狀態(tài) s 經(jīng)過超網(wǎng)絡(luò)來產(chǎn)生權(quán)值，能夠更加充分和靈活地利用全局信息來估計聯(lián)合動作的 Q 值，在一定程度上有助于全局 Q 值的學(xué)習(xí)和收斂。

結(jié)合 DQN 的思想，以 Q_tot 作為迭代更新的目標(biāo)，在每次迭代中根據(jù) Q_tot 來選擇各個智能體的動作，有：

最終學(xué)習(xí)收斂到最優(yōu)的 Q_tot 并推出對應(yīng)的策略，即為 QMIX 方法的整個學(xué)習(xí)流程。

3. 多智能體強(qiáng)化學(xué)習(xí)的應(yīng)用

3.1. 游戲應(yīng)用

1、分步對抗游戲

這類游戲包括了圍棋、國際象棋、****牌等，MARL 在這幾種游戲中都有相關(guān)的研究進(jìn)展并取得了不錯的成果。其中，著名的 AlphaGo 通過在和人類對戰(zhàn)的圍棋比賽中取得的驚人成績而進(jìn)入人們的視野。圍棋是一種雙玩家零和隨機(jī)博弈，在每個時刻，玩家都能夠獲取整個棋局。它一種涉及超大狀態(tài)空間的回合制游戲，很難直接使用傳統(tǒng)的 RL 方法或者是搜索方法。AlphaGo 結(jié)合了深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的方法：

針對巨大狀態(tài)空間的問題，使用網(wǎng)絡(luò)結(jié)構(gòu) CNN 來提取和表示狀態(tài)信息；

在訓(xùn)練的第一個階段，使用人類玩家的數(shù)據(jù)進(jìn)行有監(jiān)督訓(xùn)練，得到預(yù)訓(xùn)練的網(wǎng)絡(luò)；

在訓(xùn)練的第二個階段，通過強(qiáng)化學(xué)習(xí)方法和自我博弈進(jìn)一步更新網(wǎng)絡(luò)；

在實際參與游戲時，結(jié)合價值網(wǎng)絡(luò)（value network）和策略網(wǎng)絡(luò)（policy network），使用 蒙特卡洛樹搜索（MCTS）方法得到真正執(zhí)行的動作。

圖 11：AlphaGo 在 2016 年擊敗人類玩家。圖源：https://rlss.inria.fr/files/2019/07/RLSS_Multiagent.pdf

2、實時戰(zhàn)略游戲

MARL 的另一種重要的游戲應(yīng)用領(lǐng)域，是實時戰(zhàn)略游戲，包括星際爭霸，DOTA，王者榮耀，吃雞等。該類游戲相比于前面提到的國際象棋、圍棋等回合制類型的游戲，游戲 AI 訓(xùn)練的難度更大，不僅因為游戲時長過長、對于未來預(yù)期回報的估計涉及到的步數(shù)更多，還包括了多方同時參與游戲時造成的復(fù)雜空間維度增大，在一些游戲設(shè)定中可能無法獲取完整的信息以及全局的形勢（比如在星際爭霸中，不知道迷霧區(qū)域是否有敵方的軍隊），在考慮隊內(nèi)合作的同時也要考慮對外的競爭。

OpenAI Five 是 OpenAI 團(tuán)隊針對 Dota 2 研發(fā)的一個游戲 AI [13]，智能體的策略的學(xué)習(xí)沒有使用人類玩家的數(shù)據(jù)、是從零開始的（learn from scratch）?？紤]游戲中隊內(nèi)英雄的協(xié)作，基于每個英雄的分布式控制方式（即每個英雄都有各自的決策網(wǎng)絡(luò)模型），在訓(xùn)練過程中，通過一個超參數(shù) “team spirit” 對每個英雄加權(quán)、控制團(tuán)隊合作，并且使用基于團(tuán)隊整體行為的獎勵機(jī)制來引導(dǎo)隊內(nèi)合作?？紤]和其他團(tuán)隊的對抗，在訓(xùn)練過程中使用自我對抗的方式（也稱為虛擬自我博弈，fictitious self-play， FSP）來提升策略應(yīng)對復(fù)雜環(huán)境或者是復(fù)雜對抗形勢的能力。這種自我對抗的訓(xùn)練方式，早在 2017 年 OpenAI 就基于 Dota2 進(jìn)行了相關(guān)的研究和分析，并發(fā)現(xiàn)智能體能夠自主地學(xué)習(xí)掌握到一些復(fù)雜的技能；應(yīng)用在群體對抗中，能夠提升團(tuán)隊策略整體對抗的能力。

AlphaStar 是 OpenAI 團(tuán)隊另一個針對星際爭霸 2（Starcraft II）研發(fā)的游戲 AI，其中在處理多智能體博弈問題的時候，再次利用了 self-play 的思想并進(jìn)一步改進(jìn)，提出了一種聯(lián)盟利用探索的學(xué)習(xí)方式（league exploiter discovery）。使用多類個體來建立一個聯(lián)盟（league），這些個體包括主智能體（main agents）、主利用者（main exploiters）、聯(lián)盟利用者（league exploiters）和歷史玩家（past players）四類。這幾類智能體的策略會被保存（相當(dāng)于構(gòu)建了一個策略池），在該聯(lián)盟內(nèi)各類智能體按照一定的匹配規(guī)則與策略池中的其他類智能體的策略進(jìn)行對抗，能夠利用之前學(xué)會的有效信息并且不斷增強(qiáng)策略的能力，解決普通的自我博弈方法所帶有的 “循環(huán)學(xué)習(xí)” 問題（“Chasing its tail”）。

圖 12：聯(lián)盟利用者探索（league exploiter discovery）的學(xué)習(xí)框架。圖源：[14]

3.2. 多機(jī)器人避碰

在現(xiàn)實生活中，多機(jī)器人的應(yīng)用場景主要是通過多個機(jī)器人的協(xié)作來提升系統(tǒng)的性能和效率，此時多智能體強(qiáng)化學(xué)習(xí)的關(guān)注重點主要在于機(jī)器人（智能體）之間的合作。

在移動機(jī)器人方面，自主避障導(dǎo)航是底層應(yīng)用的關(guān)鍵技術(shù)，近幾年通過強(qiáng)化學(xué)習(xí)的方法來學(xué)習(xí)單機(jī)器人導(dǎo)航策略這方面的工作成果比較多；而當(dāng)環(huán)境中存在多個移動機(jī)器人同時向各自目標(biāo)點移動的時候，需要進(jìn)一步考慮機(jī)器人之間的相互避碰問題，這也是 MARL 在多機(jī)器人導(dǎo)航（multi-robot navigation）領(lǐng)域的主要研究問題。Jia Pan 教授團(tuán)隊 [13] 在控制多機(jī)器人避碰導(dǎo)航問題上使用了集中式學(xué)習(xí)和分布式執(zhí)行的機(jī)制，在學(xué)習(xí)過程中機(jī)器人之間共享獎勵、策略網(wǎng)絡(luò)和值函數(shù)網(wǎng)絡(luò)，通過共享的經(jīng)驗樣本來引導(dǎo)相互之間達(dá)成隱式的協(xié)作機(jī)制。

圖 13：多機(jī)器人向各自目標(biāo)點移動過程中的相互避碰。倉庫物件分發(fā)是該問題的常見場景，多個物流機(jī)器人在向各自指定的目標(biāo)點移動過程當(dāng)中，需要避免和倉庫中的其他物流機(jī)器人發(fā)生碰撞。圖源：[15]

另外，不僅有機(jī)器人和機(jī)器人之間的避碰問題，有一些工作還考慮到了機(jī)器人和人之間的避碰問題，如 SA-CADRL（socially aware collision avoidance deep reinforcement learning） 。根據(jù)該導(dǎo)航任務(wù)的具體設(shè)定（即機(jī)器人處在人流密集的場景中），在策略訓(xùn)練是引入一些人類社會的規(guī)則（socially rule），相當(dāng)于要讓機(jī)器人的策略學(xué)習(xí)到前面 1.2.3 部分提到顯式的協(xié)調(diào)機(jī)制，達(dá)成機(jī)器人與人的行為之間的協(xié)作。

圖 14：左圖展示了相互避碰時的兩種對稱規(guī)則，上面為左手規(guī)則，下面為右手規(guī)則。右圖是在 SA-CADRL 方法中模型引入這樣的對稱性信息，第一層中的紅色段表示當(dāng)前智能體的觀測值，藍(lán)色塊表示它考慮的附近三個智能體的觀測值，權(quán)重矩陣的對稱性是考慮了智能體之間遵循一定規(guī)則的對稱行為。圖源：[16]

4. 總結(jié) 

多智能體強(qiáng)化學(xué)習(xí)（MARL）是結(jié)合了強(qiáng)化學(xué)習(xí)和多智能體學(xué)習(xí)這兩個領(lǐng)域的重要研究方向，關(guān)注的是多個智能體的序貫決策問題。本篇文章主要基于智能體之間的關(guān)系類型，包括完全合作式、完全競爭式和混合關(guān)系式，對多智能體強(qiáng)化學(xué)習(xí)的理論和算法展開介紹，并在應(yīng)用方面列舉了一些相關(guān)的研究工作。在未來，對 MARL 方面的研究（包括理論層面和應(yīng)用層面）仍然需要解決較多的問題，包括理論體系的補(bǔ)充和完善、方法的可復(fù)現(xiàn)性、模型參數(shù)的訓(xùn)練和計算量、模型的安全性和魯棒性等 [15]。

參考文獻(xiàn)：

[1] Sutton R S, Barto A G. Reinforcement learning: An introduction[M]. MIT press, 2018.

[2] Zhang K , Yang Z , Baar T . Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms[J]. 2019.

[3] L. Busoniu, R. Babuska, and B. De Schutter, “A comprehensive survey of multi-agent reinforcement learning,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 38, no. 2, pp. 156–172, Mar. 2008.

[4] Littman M L. Markov games as a framework for multi-agent reinforcement learning[C]. international conference on machine learning, 1994: 157-163.

[5] Hu J, Wellman M P. Nash Q-learning for general-sum stochastic games[J]. Journal of machine learning research, 2003, 4(Nov): 1039-1069.

[6] Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pp. 746–752, 1998.

[7] S. Kapetanakis and D. Kudenko. Reinforcement learning of coordination in cooperative multi-agent systems. American Association for Artificial Intelligence, pp. 326-331, 2002.

[8] Yang Y, Luo R, Li M, et al. Mean Field Multi-Agent Reinforcement Learning[C]. international conference on machine learning, 2018: 5567-5576

[9] Lowe R, Wu Y, Tamar A, et al. Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments[C]. neural information processing systems, 2017: 6379-6390.

[10] Foerster J, Farquhar G, Afouras T, et al. Counterfactual Multi-Agent Policy Gradients[J]. arXiv: Artificial Intelligence, 2017.

[11] Sunehag P, Lever G, Gruslys A, et al. Value-Decomposition Networks For Cooperative Multi-Agent Learning.[J]. arXiv: Artificial Intelligence, 2017.

[12] Rashid T, Samvelyan M, De Witt C S, et al. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning[J]. arXiv: Learning, 2018.

[13] OpenAI Five, OpenAI, https://blog.openai.com/openai-five/, 2018.

[14] Vinyals, O., Babuschkin, I., Czarnecki, W.M. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350–354 (2019).

[15] P. Long, T. Fan, X. Liao, W. Liu, H. Zhang and J. Pan, "Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning," 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, QLD, 2018, pp. 6252-6259, doi: 10.1109/ICRA.2018.8461113.

[16] Y. F. Chen, M. Everett, M. Liu and J. P. How, "Socially aware motion planning with deep reinforcement learning," 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, 2017, pp. 1343-1350, doi: 10.1109/IROS.2017.8202312.

[17] Hernandez-Leal P , Kartal B , Taylor M E . A survey and critique of multiagent deep reinforcement learning[J]. Autonomous Agents & Multi Agent Systems, 2019(2).

分析師介紹：

楊旭韻，工程碩士，主要研究方向是強(qiáng)化學(xué)習(xí)、模仿學(xué)習(xí)以及元學(xué)習(xí)。現(xiàn)從事工業(yè)機(jī)器人相關(guān)的技術(shù)研究工作，主要負(fù)責(zé)機(jī)器學(xué)習(xí)算法落地應(yīng)用的工作。