【重磅綜述】 多智慧體強化學習算法理論研究
本文使用 Zhihu On VSCode 創作併發布
MARL Ⅰ:A Selective Overview of Theories and Algorithms
翻譯自 Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms
原文作者
Kaiqing Zhang,Zhuoran Yang,Tamer Basar
Image
[TOC]
雖然目前多智慧體強化學習 MARL 在很多領域取得了不錯的結果,但很少有相關的理論分析。本綜述挑選並彙總了
擁有理論支撐的 MARL 演算法
,主要是以下兩種理論框架:
Markov / stochastic games 馬爾可夫/隨機博弈
extensive-form games 形式廣泛的遊戲
並關注以下三種類型的任務:
fully cooperative
fully competitive
a mix of the two
此外,本文還給出了一些MARL理論的新觀點,包括
extensive-form games
,
decentralized MARL with networked agents
,
MARL in the mean-field regime
,
(non-)convergence of policy-based methods for learning in games
, etc
1 Introduction
MARL 演算法的面臨以下問題
由於所有agent同時根據自己的利益改進其策略,每個agent所面對的環境變得
non-stationary
。這打破了single agent環境中大多數理論分析的基本框架並使之無效。
隨著agent數量的增長而呈指數增加的聯合行動空間可能會導致可擴充套件性問題,這被稱為
the combinatorial nature of MARL
(Hernandez-Leal et al。,2018)。
The information structure
(即 who knows)在MARL中也很重要,因為每個agent對他人觀察的訪問均受到限制,從而導致本地決策規則可能欠佳。
2 MARL Background
Image
2。1 Markov/Stochastic Games
Definition 2.1.
Markov Games
由五元組
定義,其中
代表
個 agents,
代表所有 agents 觀測到的狀態空間,
代表 agent
的動作空間和獎勵,
為 discount factor。
值函式
是聯合策略
的函式,聯合策略定義為
, 對於每一個聯合策略
和狀態
因此,MG的解決方案不同於MDP,因為每個agent的最佳效能不僅受其自身策略的控制,而且還受博弈中所有其他玩家的選擇的控制。這方面最重要的理論就是
納什均衡
。
Definition 2.3.
Nash equilibrium of Markov Games
是一個服從下述不等式的聯合策略
,對任意
:
納什均衡
描述了一個均衡策略
,從該均衡點上沒有任何agent有任何偏離的動機。換言之,策略
is the best-response of
,但這樣的點通常可能並不唯一。大多數MARL演算法都試圖收斂到這樣的平衡點。
Cooperative Setting
在完全合作的設定中,所有agents通常共享一個reward function,
。該模型每一個 agent 的值函式和Q函式均相同,因此可以將其看作一個決策智慧體並應用single agent RL演算法。顯然這樣做的全域性合作最佳狀態就能夠達到博弈納什均衡。
另一種合作模型是
team-average reward
,
。平均獎勵模型,它允許agent商之間存在更多的
異質性
。此外還可以
保護agents之間的隱私
,並促進
decentralized MARL
演算法的發展。這種異質性必須將
通訊協議communication protocols
整合到MARL中,並需要
對通訊的效率 communication-efficie MARL 進行分析
。、
Competitive Setting
完全競爭的MARL一般被建模為
zero-sum Markov games 馬爾可夫零和博弈
,
。為了便於演算法的設計和分析,大部分文章只關注兩個agents之間的競爭,一個agent的獎勵正好是另一個的損失。此外,零和博弈還被用於
robust learning
,因為阻礙agent學習過程的uncertainty可以被抽象為在博弈中總是與agent對抗的虛擬對手。
Mixed Setting
混合設定一般也被稱作
general-sum一般和博弈
,其對agents的目標和關係沒有任何限制。每個agent都是自私的,他們的獎勵可能與他人的利益衝突。博弈論中的均衡解決方案概念,例如Nash均衡,對為此通用設定開發的演算法具有最重要的影響。
此外,還有一些研究包同時含 fully cooperative and com- petitive agents 的設定,例如,兩個零和 competitive 團隊,每個團隊中都有 coorperative agent的情況。
2。2 Extensive-Form Games
馬爾可夫博弈的問題在於:
只能處理完全觀察到的情況
,每個智慧體對整個系統的狀態和動作都有很清晰的認識。將馬爾可夫博弈擴充套件到
部分可觀測
的情況可能是適用的,但是即使在合作環境下,這也
具有挑戰性
。
相反,extensive-form games 框架就可以處理資訊不完備的多智慧體決策問題。該框架植根於計算博弈論,並已被證明可以在溫和條件下允許多項式時間複雜度的演算法
Definition 2.4.
extensive-form games 定義為
是被稱為chance or nature 的特殊 agent,它具有固定的隨機策略,該策略指定環境的隨機性。
是所有可能的 history,每個歷史記錄都是從博弈開始就採取的一系列操作。
表示在非終止歷史記錄
之後可用的一組動作。
在所有歷史中,
是代表博弈結束的terminal histories的子集。
是 identification function,指定在每個歷史記錄中哪個agent採取的動作。如果
,那麼 chance agent 根據它的策略
採取動作。
S中的元素稱為 information states。
部分可觀測反映在智慧體無法區分同一資訊集中的歷史記錄。此外,我們始終假設博弈是
回憶完備的 perfect recall
,即每個agent都記住 information states 和導致其當前資訊狀態的動作的順序。更重要的是,根據著名的
庫恩定理 Kuhn’s theorem
,在這樣的假設下,找到納什均衡集,就足以將推導約束為 behavioral policies 集,後者將每個資訊集
對映到
上的機率分佈。對於任何
,令
是 agent i的information states集。
agents 的聯合策略由
表示,其中
是agenti的策略。對於任何歷史h和任何聯合策略π,我們將π下h的
到達機率 reach probability
定義為
它指定當所有agent都遵循π時建立h的機率。類似地,我們將資訊狀態 s 在π 下的到達機率定義為
。Agent i 的 expected utility 為
。為簡單起見,以
來表示。由此可以給出 extensive-form game 框架下的納什均衡定義。
Definition 2.5.
-Nash equilibrium of an extensive-form game 表示為
的聯合策略
,對於每一個智慧體:
時,即為納什均衡。
Various Settings
Extensive-form games 一般用於建模 non-cooperative settings。更重要的是,不同資訊結構的設定也可以透過extensive-form game來表徵。特別是,一個資訊完備的博弈是每個資訊集都是一個單例的博弈,即對於任何
。 資訊不完備的博弈是存在
的博弈。 換句話說,在資訊不完善的情況下,用於決策的資訊狀態代表了不止一種可能的歷史,而agent無法區分它們。
Connection to Markov Games
對於同時移動的馬爾可夫博弈,其他智慧體對動作的選擇對於某一個智慧體是未知的,因此這導致可以將不同的歷史彙總為一個資訊狀態s。這些博弈中的歷史記錄就是聯合動作的序列,而累計折扣獎勵將在博弈結束時例項化utility。相反,透過簡單地將狀態
時agent
設定為
,extensive-form game 簡化為具有 state-dependent 的動作空間的馬爾可夫博弈。
3 Challenges
3。1 Non-Unique Learning Goals 目標不唯一
不同智慧體間,學習的目標不唯一。被設計為收斂到NE的學習動力對於實際的MARLagent來說可能是不合理的。Instead, the goal may be focused on designing the best learning strategy for a given agent and a fixed class of the other agents in the game。
用
convergence
(達到平衡點)作為MARL演算法分析的主要效能標準
還存在爭議
。因為 Zinkevich et al。 (2006) 證實
基於價值的MARL演算法無法收斂到一般性和馬爾可夫博弈的平穩NE
,這激發了
cyclic equilibrium
的新解決方案概念。在該概念下,agent 透過一系列 stationary policies(即不收斂到任何NE策略)嚴格迴圈。或者,將學習目標分為
stable
和
relational
兩個方面,前者在給定預定義的、有針對性的對手演算法的情況下,確保演算法收斂,而後者則要求在其他主體保持穩定時收斂到 best-response。如果所有agent都既穩定又理性,則在這種情況下自然會融合到NE
此外,
regret
的概念為捕捉 agent 的 rationality 引入了另一個角度,與 the best hindsight static strategy 相比,它衡量了演算法的效能(Bowling和Veloso,2001; Bowling,2005)。漸近平均零後悔的
No-regret algorithms
保證了某些博弈的
均衡收斂性
(Hart和Mas-Colell,2001; Bowling,2005; Zinkevich等,2008),這從根本上保證了該 agent 不會被其他 agent 利用。
Kasai等(2008),Foerster等(2016),Kim等(2019)研究了
learning to communicate
的方式,以便 agents 更好地進行協調。
對通訊協議的這種關注自然激發了最近對高通訊效率的MARL的研究
(Chen等,2018; Lin等,2019; Ren和Haupt,2019; Kim等,2019)。其他重要目標包括如何在不過度擬合某些 agent 的情況下進行學習(He等人,2016; Lowe等人,2017; Grover等人,2018),以及如何在惡意/對抗性或失敗/功能失調的情況下
穩健學習
。(Gao等,2018; Li等,2019; Zhang等,2019)。
3。2 Non-Stationarity 非平穩
很明顯,由於多智慧體動作結果的相互影響,agent 需要考慮其他 agents 的 action 並相應地適應 joint action,導致了單智慧體的馬爾可夫假設不適用。
關於這方面的知識,可見 Hernandez-Leal 2017年的綜述,該文章中特別概述瞭如何透過最新的 MARL 學習演算法對其進行建模和解決。
3。3 Scalability Issue 可擴充套件性
為了處理非平穩性,每個 agent 都可能需要考慮聯合動作空間,然而聯合行動的規模會隨著智慧體的增加而成倍的增加。這也被稱為MARL的
combinatorial nature
(Hernandez-Leal et al。,2018)。
一種可能的補救措施是,另外假設
關於動作依賴的價值或獎勵函式的因式分解結構
。
參見Guestrin(2002a,b);Kok和Vlassis(2004)提出了原始的啟發式思想,以及最近的 Sunehag et al。 (2018); Rashid et al。 (2018) 等。 直到最近才建立了相關的理論分析**(Qu and Li,2019)**,該模型考慮了一種特殊的依賴結構,並開發了一種可證明的基於模型的收斂演算法(不是RL)。
3。4 Various Information Structures 不同的資訊結構
Image
中心化 MARL
:大量工作都假設存在一個
centralized controller
,該中央控制器可以收集資訊,例如聯合動作,聯合獎勵和聯合觀察,甚至為所有agent設計策略。(Hansen et al。, 2004; Oliehoek and Amato, 2014; Lowe et al。, 2017; Foerster et al。, 2017; Gupta et al。, 2017; Foerster et al。, 2018; Dibangoye and Buffet, 2018; Chen et al。, 2018; Rashid et al。, 2018)。這種結構催生了流行的
集中學習,分散執行 centralized-learning-decentralized-execution
的學習方案,該方案源於為部分觀察的環境進行規劃的工作,即
Dec-POMDP
。然而,通常這種中央控制器在許多應用中並不存在,除了那些可以輕鬆訪問模擬器的應用之外,例如 video games 和 robotics。
完全去中心 MARL
:為了解決獨立學習中的收斂問題,通常允許agents透過通訊網路與鄰居交換/共享本地資訊。(Kar et al。, 2013; Macua et al。, 2015, 2017; Zhang et al。, 2018,a,b; Lee et al。, 2018; Wai et al。, 2018; Doan et al。, 2019; Suttle et al。, 2019; Doan et al。, 2019; Lin et al。, 2019)。我們將此設定稱為
a decentralized one with networked agents
。這樣一來,就可以在這種情況下進行收斂的理論分析,其難度介於 SARL 和通用MARL演算法之間。
4 MARL Algorithms with Theory
本文僅聚焦 Cooperative Setting 的情況下的詳細理論
,如果想了解 Competitive Setting 和 Mixed Setting,可以自行閱讀標題下的連結。由於 Homogeneous Cooperative Agent 的情況過於 naive,本文就不提了,我比較感興趣的是
Decentralized Paradigm with Networked Agents
,這也是最符合實際的模型。
Decentralized Paradigm with Networked Agents
在許多實際的multi-agent系統中,
coorperative agents 並不總是同質的
。
Agents可能有不同的偏好,即獎勵函式,這時要讓團隊的平均回報
最大化。有時獎勵函式
不能與其他 agents 共享
,因為每個 agent 的偏好都是獨立的。
這種設定常出現於諸如
感測器網路
(Rabbat和Nowak,2004),
智慧電網
(Dall‘Anese等,2013; Zhang等,2018a),
智慧交通系統
(Adler和Blue,2002)和
機器人技術
(Corke等人,2005)等場景。
如果使用 central controller 的方式,上述大多數MARL演算法都可直接適用,因為 central controller 可以收集平均獎勵,並將資訊分發給所有 agents。但是由於
成本、可擴充套件性或健壯性
方面的考慮,在大多數上述應用中可能都不存在這種控制器(Rabbat和Nowak,2004; Dall’Anese等,2013; Zhang等,2019)。
取而代之的是,agents 可以透過
隨時間變化且稀疏的通訊網路與鄰居共享/交換資訊
。
Learning Optimal Policy
如何僅透過網路訪問本地和鄰近資訊來達到最優的聯合策略。具有網路 agents 的MARL 想法可以追溯到Varshavskaya et al。(2009)。第一個
可證明收斂
的MARL演算法是Kar等人提出的(2013),將
consensus + innovation
的思想納入標準的Q學習演算法,產生了具有以下更新的
QD-learning
演算法
其中:
are stepsizes
代表 t 時刻 agent i 的鄰居集
Q-learning 相比,QD-learning 在步長上增加了 innovation 項,該項捕捉了來自其鄰居的Q估計值的差異。With certian conditions on the stepsizes, 演算法可以保證收斂到表格形式下的最優 Q 函式。
對於 policy-based 方法可見這篇文章 Fully decentralized multi-agent reinforcement learning with networked agents,它提出了完全去中心化的 multi-agent actor-critic。每個 agent 透過某個引數
來引數化其自己的政策
,首先得出回報的策略梯度:
是在聯合策略
下對於
的全域性值函式。很明顯,在這個設定中,單個 agent 是沒有辦法估計這個全域性值函式的。因此,我們提出瞭如下的 consensus-based TD learning 用於 critic step 來用區域性
來估計全域性:
is the stepsize
是用
計算出的區域性 TD-error
第一個等式給出了標準的 TD update,第二個是鄰居的加權組合
權重
由
通訊網路的拓撲結構決定
請注意,上述
收斂保證都是漸近
的,即演算法隨著迭代次數達到無窮大而收斂,並且僅限於線性函式近似的情況。當使用有限迭代和/或樣本時,這無法量化效能,
更不用說在利用諸如 DNN 之類的非線性函式時了
。
當考慮更通用的函式逼近進行有限樣本分析時,詳見 Finite-sample analyses for fully decentralized multi-agent reinforcement learning 和 Batch reinforcement learning 的
batch RL
演算法,特別是
the fitted-Q iteration (FQI)
的去中心化變體。
我們研究了FQI變體,既用於與網路代理的協作環境,也用於與兩個團隊的網路代理的競爭環境。在前一種設定中,所有智慧體都透過將
非線性最小二乘法與目標值擬合
來迭代更新全域性Q函式估計。
讓
代表 Q函式的近似函式,
為大小為n的可用於所有 agents 的 batch transitions 資料集,
代表每個 agent 專有的區域性獎勵,
為 local target value。然後,所有agent透過求解下式找到一個共同的Q函式估計:
由於
只有agent i 知道, 因此其符合 distributed/consensus optimization 的公式。
另一個問題:由於是對分散式系統進行
有限次迭代
,agents之間可能無法達成共識,導致了對最優 Q 值的估計偏離了實際值。我們可以根據源於 single-agent batch RL 的
error propagation
分析,建立所提出演算法的有限樣本下的效能評估。例如,演算法輸出的精度多大程度取決於函式
、每次迭代 n 內的樣本數以及 t 的迭代數。
5 Conclusions and Future Directions
Partially observed settings
在許多實際的MARL應用程式中,系統狀態和其他agent的行為的
部分可觀察性
是典型且不可避免的。通常,可以將這些設定建模為 partially observed stochastic game (POSG),在特殊情況下,該遊戲包括具有 common reward function 的協作設定,即Dec-POMDP模型。然而,即使
合作任務也是 NEXP-hard
(Bernstein等,2002),難以解決。
實際上,與只需要相信狀態的POMDPs相比,POSG中用於最佳決策的資訊狀態可能會非常複雜,並且涉及 belief generation over the opponents’ policies(Hansen等人,2004年)。
這種困難主要源於從模型中獲得的自身觀察結果所導致的
agent異質性
,這是第3節中提到的MARL固有的挑戰,原因是資訊結構多種多樣。有可能首先將解決Dec-POMDP的
centralized-learning-decentralized-execution
方案(Amato和Oliehoek,2015; Dibangoye和Buffet,2018)推廣到解決POSGs。
Deep MARL theory
使用DNN進行函式逼近可以解決MARL中的可伸縮性問題。實際上,最近在MARL中獲得的大部分經驗成功都來自DNN的使用(Heinrich和Silver,2016; Lowe等人,2017; Foerster等人,2017; Gupta等人,2017; Omidshafiei等人,2017)。但是,由於
缺乏理論支援
,我們在本章中沒有包括這些演算法的詳細資訊。最近,人們做出了一些嘗試來理解幾種 single agent DRL 演算法的全域性收斂性,例如
neural TD learning
(Cai等,2019)和
neural policy optimization
(Wang等,2019; Liu等2019年)。因此,有望將這些結果擴充套件到多智慧體設定,作為邁向對DMARL的理論理解的第一步。
Model-based MARL
文獻中
很少有基於模型的MARL演算法
。據我們所知,目前僅有的基於模型的MARL演算法包括Brafman和Tennenholtz(2000)中的早期演算法,它解決了單控制器隨機遊戲,一種特殊的 zero-sum MG。後來在Brafman和Tennenholtz(2002)中對zero-sum MG進行了改進,名為R-MAX。這些演算法也建立在面對不確定性時的 principle of optimism 上(Auer和Ortner,2007; Jaksch等,2010),就像前面提到的幾種無模型的演算法一樣。考慮到基於模型的RL的最新進展,尤其是在某些情況下其優於無模型的RL的可證明優勢(Tu and Recht,2018; Sun等,2019),有必要將這些結果推廣到MARL以改進其
sample efficiency
。
Convergence of policy gradient methods
一般MARL中的 vanilla PG 的收斂結果大部分為負,即在許多情況下甚至會避開本地NE點,這本質上與MARL中的非平穩性挑戰有關。儘管已經提出了一些補救措施(Balduzzi等人,2018; Letcher等人,2019; Chasnov等人,2019; Fiez等人,2019)來穩定 general continuous games 的收斂性,但這些假設是即使在最簡單的LQ設定中,也不容易在MARL中進行驗證/滿足(Mazumdar等人,2019),因為它們不僅取決於模型,而且還取決於策略引數化。由於這種微妙之處,
探索基於策略的MARL方法的(全域性)收斂可能很有趣
,可能始於簡單的LQ設定(即一般和LQ遊戲),類似於 zero-sum counterpart 博弈。
MARL with robustness/safety concerns
考慮到多智慧體會有不唯一的學習目標,我們認為
在MARL中考慮穩健性和/或安全性約束是很有意義的
。據我們所知,這仍然是一個相對未知的領域。實際上,
safe RL已被認為是 single agent 中最重大的挑戰之一
(Garcia和Fernandez,2015)。由於可能存在多個目標衝突的代理,因此安全性變得更加重要,
安全要求讓我們必須考慮智慧體間的的耦合
。一種簡單的模型是 constrained multi-agent MDPs/Markov games,其約束條件表徵了安全性要求。在這種情況下,具有可證明的安全保證的學習並非易事,但對於一些對安全性至關重要的MARL應用(如自動駕駛(Shalev-Shwartz等,2016)和機器人技術(Kober等,2013))是必需的。
此外,當然也要考慮
對抗對手的魯棒性
,
特別是在分散/分散式合作MARL環境中
,如Zhang等人所述 Zhang et al。 (2018); Chen et al。 (2018); Wai et al。 (2018)。在這種情況下,
對手可能以匿名方式干擾學習過程-這是分散式系統中的常見情況
。在這種情況下,針對 Byzantine adversaries 的魯棒分散式監督學習的最新發展 (Chen et al。, 2017; Yin et al。, 2018) 可能是有用的。