Counterfactual Multi-Agent Policy Gradients
論文連結：https://arxiv.org/pdf/1705.08926.pdf
1. 問題提出（解決了什麼問題？）
在現實世界中，有非常多的問題需要多個機關之間的“合作”才能完成任務，這就需要學習一種
非中心式政策
的控制系統，即每個agent有着屬于自己的決策大腦，而非靠擁有全局資訊的決策系統下達指令（畢竟有時候全局的資訊量過于龐大，并且agent到中心網絡的通信不一定每時每刻都穩定，是以中心式的決策系統很難實作）。是以，該論文提出了一種方法用于學習
非中心式的
、
部分可觀測的
多智能體協同的控制政策。
COMA利用全局評價網絡（critic）來評價Q值，利用非全局行為網絡（actor）來決定agent的行為。由于在訓練時使用的是全局網絡進行評價，并且采用參數共享的方式，使得agent能夠在做行為選擇的時候參考其他agent的狀态再做決定，這就加入了“協同”的功能。
2. 介紹
該論文分為以下三個部分：
- 提出傳統的RL算法在協同任務中不足
若使用傳統的RL算法來解決多智能體的問題，則會存在以下三個不足之處：
- 輸入的action space應該是所有agent的聯合動作空間（joint action space），這個空間會随着agent數量增加而增加。
- 此外，由于部分可觀測性（即單個agent在某一時刻隻能觀測到部分環境的資訊，無法獲得全局資訊，比如一個小兵隻能看到視野範圍内的地圖資訊，視野外的地圖資訊是無法觀測的），使得agent在做決策時隻能依照自己目前的部分觀測資訊（local observation），沒有與其他agent進行資訊共享的能力。
- 使用聯合動作空間獲得的reward是來自所有agent采取的所有action共同得到的reward，這就很難知道每一個agent的action應該得到的多少子回報，這就是原文中提到的 “Individual Reward Assignment”。
- COMA中的主要思想
COMA是一種基于actor-critic的變種方法，其中actor是依照critic評估出來的梯度值進行更新學習的。整個算法共有三個比較核心的思想：
- 學習過程中會有一個中心式評價網絡, 這個網絡主要用于對actor選擇的決策進行好壞評價以此來教會actor如何做一個好的決策。為什麼稱為中心式的網絡？這是因為該網絡可以擷取場景中的全局資訊，包括所有agent在這一時刻采取的行為資訊和觀測資訊。但是，單個agent在利用actor做行為選擇時隻能依照自身的目前觀測資訊和經曆過的曆史資訊進行決策，做決策時是無法獲得全局資訊的。這種方式被稱為“中心式評價，邊緣式決策”。
- COMA引入了一個概念叫做 “反事實準則(counterfactual baseline)” ，這個概念是整篇論文的重點。為了解決 Individual Reward Assignment 的問題，反事實準則提出，每個agent應該擁有不同的reward，這樣才能知道在這一次的全局行為決策中單個agent的action貢獻是多少。而單個agent的reward通過兩個值計算得來：目前情況下的全局reward和将該agent行為替換為一個預設行為後的全局reward。可以這樣了解：該回報值其實計算的是Agent a a a采取行為 u u u 會比采取預設行為 c a c_a ca 要更好（ D a D^a Da > 0）還是更壞（ D a D^a Da < 0）。這個特定agent下特定動作的reward就被稱為counterfactual baseline，COMA使得每一個agent的每一個action都有一個自身的counterfactual baseline。
- 如上面所說，每一個agent的每一個動作都會有一個counterfactual baseline，如果要計算出所有動作的baseline，就需要把每一個行為替換成 ‘預設行為’ 并與環境互動得到一個reward。當agent數目很多且聯合動作空間很大的時候，這種方法顯然是不可取的。是以，COMA提出：使用中心critic網絡來estimate每一個動作的Q值，來代替與環境互動後得到的reward。
- 驗證場景及其結果分析
3. 背景
3.1 數學模組化
論文中将多智能體協同任務想象成一個随機決策的遊戲，這個遊戲 G G G 包含以下幾個因素：
G = < S , U , P , r , Z , O , n , γ > G = <S, U, P, r, Z, O, n, \gamma> G=<S,U,P,r,Z,O,n,γ>
其中，
- S → S \quad \rightarrow \quad S→ 環境狀态集： ∀ s ∈ S \forall s \in S ∀s∈S.
- U → U \quad \rightarrow \quad U→ 所有動作樣本空間：在每一時刻，每個agent采取一個行為 u t a ∈ U u_t^a \in U uta∈U，并組成聯合動作空間 u ∈ U \textbf{u} \in U u∈U.
- P → P \quad \rightarrow \quad P→ 狀态轉移函數：根據目前狀态 s s s和聯合動作空間 u \textbf{u} u，計算一時刻狀态 s ′ s' s′， P ( s ′ ∣ s , u ) P(s'|s, \textbf{u}) P(s′∣s,u).
- r → r \quad \rightarrow \quad r→ 全局回報值： r ( s , u ) r(s, \textbf{u}) r(s,u).
- Z → Z \quad \rightarrow \quad Z→ 局部觀測集：單個agent在每一時刻有一個局部觀測 z ∈ Z z \in Z z∈Z.
- O → O \quad \rightarrow \quad O→ 局部觀測函數：Agent a a a 的局部觀測 z z z 是根據全局環境資訊 s s s 通過 O O O 函數計算得來， z = O ( s , a ) z = O(s, a) z=O(s,a).
- n → n \quad \rightarrow \quad n→ agent的個數，共有 n n n 個.
- γ → \gamma \quad \rightarrow \quad γ→ 折扣因子，用于指定計算未來回報時的衰減強弱.
此外，每個agent有一個 action-observation 的曆史記錄 τ a \tau^a τa，actor在做決策的時候是基于曆史資訊做的決策 π a ( u a ∣ τ a ) \pi^a(u^a|\tau^a) πa(ua∣τa). 其實這裡基于曆史記錄做決策可以了解為：之前在做update決策網絡參數的時候，是基于之前的曆史資訊做的更新，是以用更新後的actor去做決策就可以看作是記住了曆史經驗後做的決策了。
3.2 基本概念回顧
這裡在回顧一下DQN中的一些基本概念，後續内容會用的到：
累計回報： R t = ∑ l = 0 ∞ γ l r t + l R_t = \sum_{l=0}^\infty{\gamma^lr_{t+l}} Rt=∑l=0∞γlrt+l，其中 γ \gamma γ 是折扣因子；
評價函數分為兩個：對目前狀态的評價函數 V π ( s t ) V^\pi(s_t) Vπ(st)，對目前狀态下目前聯合動作空間的評價函數 Q π ( s t , u t ) Q^\pi(s_t, u_t) Qπ(st,ut);
V π ( s t ) = E [ R t ∣ s t ] Q π ( s t , u t ) = E [ R t ∣ s t , u t ] V^\pi(s_t) = E[R_t|s_t] \qquad Q^\pi(s_t, \textbf{u}_t) = E[R_t|s_t, \textbf{u}_t] Vπ(st)=E[Rt∣st]Qπ(st,ut)=E[Rt∣st,ut]
優勢函數： A π ( s t , u t ) = Q π ( s t , u t ) − V π ( s t ) A^\pi(s_t, \textbf{u}_t) = Q^\pi(s_t, \textbf{u}_t) - V^\pi(s_t) Aπ(st,ut)=Qπ(st,ut)−Vπ(st).
Policy Gradient ：Value-Based中主要使用的更新方法——梯度上升法，梯度 g g g 可以表示為：
g = ∑ t = 0 T R t ▽ θ π l o g π ( u t ∣ s t ) g = \sum_{t=0}^TR_t\bigtriangledown_{\theta^\pi}log\pi(u_t|s_t) g=t=0∑TRt▽θπlogπ(ut∣st)
關于Actor-Critic模型：
AC模型中，actor是根據critic所求得的梯度來進行學習的。因為 R t R_t Rt是一個期望值，無法求得精确的值，是以需要用其他的表達式來近似替代 R t R_t Rt。替代 R t R_t Rt一共有兩種方式：
- 優勢函數法：使用 Q ( s t , u t ) − b ( s t ) Q(s_t, u_t) - b(s_t) Q(st,ut)−b(st) 來代替 R t R_t Rt，其中 b b b 為一個基準值，用于保證所有action的Q值有正有負，通常可以用 V ( s t ) V(s_t) V(st) 來代替 b b b 值。也就是用 Q π ( s t , u t ) − V π ( s t ) = A ( s t , u t ) Q^\pi(s_t, u_t) - V^\pi(s_t) = A(s_t, u_t) Qπ(st,ut)−Vπ(st)=A(st,ut) 來代替 R t R_t Rt。
- TD法：使用 r t + γ V ( s t + 1 ) − V ( s t ) r_t + \gamma V(s_{t+1}) - V(s_t) rt+γV(st+1)−V(st) 來代替 R t R_t Rt 。
如何訓練中心評價網絡critic：
在這篇論文中，作者訓練了一個中心評價網絡 f c ( ⋅ , θ c ) f^c(·, \theta^c) fc(⋅,θc)，網絡參數為 θ c \theta^c θc，使用一種稍微改變了下的TD法進行學習—— T D ( λ ) TD(\lambda) TD(λ) 将 n n n 步的reward值進行綜合來得到一個平均值 G t ( n ) = ∑ l = 1 n γ l − 1 r t + l + γ n f c ( ⋅ t + n , θ c ) G_t^{(n)} = \sum_{l=1}^n\gamma^{l-1}r_{t+l} + \gamma^nf^c(·_{t+n}, \theta^c) Gt(n)=∑l=1nγl−1rt+l+γnfc(⋅t+n,θc)。使用梯度下降的方法來更新網絡參數 θ c \theta^c θc， L t L_t Lt表示 t t t時刻的損失函數:
L t ( θ c ) = ( y ( λ ) − f c ( ⋅ t , θ c ) ) 2 L_t(\theta^c) = (y^{(\lambda)} - f^c(_{·t}, \theta^c)) ^ 2 Lt(θc)=(y(λ)−fc(⋅t,θc))2
其中：
y ( λ ) = ( 1 − λ ) ∑ n = 1 ∞ λ n − 1 G t ( n ) G t ( n ) = ∑ l = 1 n γ l − 1 r t + l + γ n f c ( ⋅ t + n , θ c ) y^{(\lambda)} = (1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}G_t^{(n)} \\ G_t^{(n)} = \sum_{l=1}^n\gamma^{l-1}r_{t+l} + \gamma^nf^c(·_{t+n}, \theta^c) y(λ)=(1−λ)n=1∑∞λn−1Gt(n)Gt(n)=l=1∑nγl−1rt+l+γnfc(⋅t+n,θc)
是以，整個公式也可以表示為：
L t ( θ c ) = ( ( 1 − λ ) ∑ n = 1 ∞ λ n − 1 ( ∑ l = 1 n γ l − 1 r t + l + γ n f c ( ⋅ t + n , θ c ) ) − f c ( ⋅ t , θ c ) ) 2 L_t(\theta^c) = ((1-\lambda)\sum_{n=1}^\infty \lambda^{n-1}(\sum_{l=1}^n\gamma^{l-1}r_{t+l} + \gamma^n {\color{red}f^c(·_{t+n}, \theta^c)}) - f^c(·_{t}, \theta^c)) ^ 2 Lt(θc)=((1−λ)n=1∑∞λn−1(l=1∑nγl−1rt+l+γnfc(⋅t+n,θc))−fc(⋅t,θc))2
Note
：公式中一共有兩個 f c ( ⋅ , θ c ) f^c(·, \theta^c) fc(⋅,θc) 網絡，但是前一個 f c ( ) f^c() fc()是estimate出來的目标值 y ( λ ) y^{(\lambda)} y(λ)，為了加快模型的收斂速度，第一個的 f c ( ) f^c() fc() 中的 θ c \theta^c θc 應該被fix住（式子中的紅色部分），若幹個steps後再被update，這和target network的思路是一樣的。
4. 算法分析
4.1 Independent Actor-Critic
IAC方法指每一個agent學習一個獨立的actor-critic，在這篇論文中采用參數共享的方法，使得所有agent共用一個actor和一個critic。在學習的時候，critic隻能根據agent自身的local observation進行估計值，并且也隻能估計該agent的單個動作 u a u^a ua的效用，而不是聯合動作空間 u \textbf{u} u的效用。
論文中對傳統的IAC算法有兩處改變:
- 在估計V值時，每個 agent 的 critic 估計的是 V ( τ a ) V(\tau^a) V(τa)，估計的是這個agent曆史action-observation資料的效用值，而不是傳統的目前狀态的效用值 V ( s t ) V(s_t) V(st)。 V V V評價網絡基于 T D ( λ ) TD(\lambda) TD(λ)方法進行梯度更新，見上面。
- 在估計Q值時，每個agent的critic估計的是 Q ( τ a , u a ) Q(\tau^a, u^a) Q(τa,ua), 也是基于action-observation的曆史資料對目前行為 u a u^a ua進行效用估計。 Q Q Q評價網絡是通過梯度下降優勢函數 A ( τ a , u a ) A(\tau^a, u^a) A(τa,ua)來進行學習的，其中優勢函數的定義為：單個動作産生的Q值減去所有動作産生的Q值，即 A ( τ a , u a ) = Q ( τ a , u a ) − V ( τ a ) A(\tau^a, u^a) = Q(\tau^a, u^a) - V(\tau^a) A(τa,ua)=Q(τa,ua)−V(τa)。其中 V ( τ a ) V(\tau^a) V(τa)定義為：在已知"動作-觀測"曆史資料下，所有動作産生的效用總和，即 V ( τ a ) = ∑ u a π ( u a ∣ τ a ) Q ( τ a , u a ) V(\tau^a) = \sum_{u^a}\pi(u^a|\tau^a)Q(\tau^a, u^a) V(τa)=∑uaπ(ua∣τa)Q(τa,ua)。
IAC的缺陷在于，訓練時隻能依據單個agent的局部觀測和單個action的效用評定，這樣很難學出一套好的協同政策。
4.2 Counterfatual Multi-Agent Policy Gradient
COMA的主要思想有三個：中心式評價網絡，使用反事實準為每一個行為配置設定不同的reward值，高效計算每一個不同的reward值，下面對每一個思想進行介紹講解。
- Center critic
在IAC算法中，訓練評價網絡時隻用到了單個agent的history τ a \tau^a τa。既然這個評價網絡隻會在訓練的時候使用，那麼我們完全可以把全局狀态 s s s 輸入用于訓練，若全局觀測不可獲得，則将目前所有agent的"action-observation"的曆史記錄 τ \tau τ代替全局狀态 s s s，如下圖所示:
圖中，每一個Actor都會給出此刻的決策行為 u t u_t ut，并且環境也會給出此時環境的全局資訊 s t s_t st 以及此刻的回報值 r t r_t rt。
一種很簡單的方式是直接使用TD-Error來進化這個網絡：
g = ▽ θ π l o g π ( u ∣ τ t a ) ( r + γ V ( s t + 1 ) − V ( s t ) ) g = \bigtriangledown_{\theta_\pi}log\pi(u|\tau_t^a)(r+\gamma V(s_{t+1}) - V(s_t)) g=▽θπlogπ(u∣τta)(r+γV(st+1)−V(st))
但是，這樣的方法不能解決 Individual Reward Assignment 的問題，因為TD算出來的Reward是一個全局Reward ，無法推算出每一個action的單獨Reward值。為此，論文提出了"反事實準則"。
- Counterfatual baseline
反事實準則（Conuterfatual Baseline）允許為不同的action獨立配置設定一個不同的獨立reward。這個獨立reward D a D^a Da 需要根據
目前情況下的全局reward
和
将該agent行為替換為一個'預設行為'後的全局reward
兩個值進行計算，
D a = r ( s , u ) − r ( s , ( u − a , c a ) ) D^a = r(s, \textbf{u}) - r(s, (\textbf{u}^{-a}, c_a)) Da=r(s,u)−r(s,(u−a,ca))
其中， u − a \textbf{u}^{-a} u−a 代表聯合動作空間除去目前Agent a a a 這一時刻采取的行為。 ( u − a , c a ) (\textbf{u}^{-a}, c_a) (u−a,ca) 代表目前Agent a a a 采取"預設行為" c a c_a ca 後所有Agent的聯合動作空間。在學習過程中，agent會想辦法最大化回報值 D a D^a Da，這其實就是在想辦法最大化全局的reward r ( s , u ) r(s, \textbf{u}) r(s,u)，因為式子的後項跟agent目前采取什麼行為是沒有關系的。關于 D a D^a Da這個式子可以這樣了解：回報值 D a D^a Da其實計算的是Agent a a a采取行為 u u u 會比采取預設行為 c a c_a ca 要更好（ D a D^a Da > 0）還是更壞（ D a D^a Da < 0）。
這個想法是正确的，但是要想計算出每一個動作的 D a D^a Da值，就需要将每個動作都替換成預設行為 c a c_a ca去與環境互動一次得到最終結果，這樣采樣次數會非常多；此外，預設行為的選取也是無法預測的，到底選擇哪一個行為當作預設行為才是最合适的也是比較難決定的。是以，文中提出使用"函數拟合"的方式來計算 D a D^a Da。
前面提到，中心評價網絡可以評價一個聯合動作空間 u \textbf{u} u 在一個狀态 s s s 下的 Q Q Q 值。由于預設行為很難定義，于是我們把采取 “預設行為” 得到的效用值近似為采取一個Agent “所有可能行為” 的效用值總和。是以， D a D^a Da 就可以用以下等式進行計算：
A a ( s , u ) = Q ( s , u ) − ∑ u a ′ π a ( u ′ a ∣ τ a ) Q ( s , ( u − a , u ′ a ) ) A^a(s, \textbf{u}) = Q(s, \textbf{u}) - \sum_{u_a'}\pi^a(u'^a|\tau^a)Q(s, (\textbf{u}^{-a}, u'^a)) Aa(s,u)=Q(s,u)−ua′∑πa(u′a∣τa)Q(s,(u−a,u′a))
其中， A a ( s , u ) A^a(s, \textbf{u}) Aa(s,u) 就是 D a D^a Da 的等效近似。
- Efficient evaluation of baseline
盡管baseline的方式解決了獨立回報的問題，但是如果要建立一個網絡，接收 s , u s, \textbf{u} s,u兩個輸入，輸出為所有agent的所有action的話，那麼輸出神經元的個數就等于 ∣ U ∣ n |U|^n ∣U∣n（n個agent有|U|個動作）。當agent數目很多或動作空間很大的時候就會造成輸出層無法實作。為此，COMA構造了一種網絡，該網絡接收 u t − a , s t , o t a , a , u t − 1 − a \textbf{u}^{-a}_t, s_t, o_t^a, a, \textbf{u}^{-a}_{t-1} ut−a,st,ota,a,ut−1−a 等參數，輸出為Agent a a a 每一個action的Q-value值，輸出次元由 ∣ U ∣ n |U|^n ∣U∣n 降到了 ∣ U ∣ |U| ∣U∣ ，如下圖所示。
5. 實驗
5.1 實驗場景
該論文使用星際争霸遊戲作為實驗場景，讓算法控制的小隊和遊戲AI控制的小隊進行對戰，并計算勝率。算法小隊中，每一個作戰機關都由一個去中心式的controller進行控制。為了提升遊戲難度，比賽加入了 “部分可觀測” 條件的限制，視野範圍等于攻擊範圍。這意味着當敵人沒有進入攻擊範圍内時，作戰機關是不知道敵人位置資訊的，是以agent不僅要學會如何去探索敵方目标，還需要與隊友共享敵方目标的位置資訊。為了證明加入 “部分可觀測” 限制後問題變得有多複雜，作者做了實驗對比：當不加入觀測限制時，普通的啟發式算法能夠到達98%的勝率；加入限制後，勝率降到了66%。
5.2 動作空間及回報值
每個agent都有着相同的動作空間：{ move[direction]，attack[enemy_id]，stop，noop }。
一次Episode下的全局Reward為：對敵人造成的傷害 D e D_e De 減去我方受到的傷害 D u D_u Du 除以2，此外，若擊毀一個敵方機關獲得10點的回報，即：
R ( t ) = D e − D u 2 + 10 n R(t) = D_e - \frac{D_u}{2} + 10n R(t)=De−2Du+10n
其中， n n n為摧毀敵方機關數。若有一方将敵方團滅，則獲得的回報值為全隊剩餘血量+200。
5.3 狀态特征
算法一共有兩個網絡：actor 和 critic。其中actor接收agent的局部觀測資訊；critic接收全局狀态資訊。
- 局部觀測資訊
由于作戰機關的視野範圍等于攻擊範圍，是以觀測到的視野是以該機關為中心的一個圓。局部觀測資訊是指在視野圓圈内，每一個機關（包括敵方和友方）的以下幾個資訊：distance，relative x，relative y，unit type，shield。其中 unit type 是指作戰機關是何種兵種，shield是為了模拟平A的冷卻（因為t切割的很小，每一時刻Agent都有可能選擇平A這個動作，是以在平A還沒有冷卻好的時候，敵方機關會套上一個無敵的盾來抵消這一次平A受到的傷害）。
疑問：觀測範圍中的機關數量應該是随時間變化而變化的，但網絡的輸入層神經元應該是固定的，怎麼解決變長的問題？(未解決)
- 全局觀測資訊
全局觀測資訊包含了所有機關的relative x，relative y，unit type，shield，healthy point，cooldown資訊，其中 relative 的坐标資訊是相對據地圖中心的相對坐标，不再是針對于某一個特定目标的坐标。
- 喂給獨立回報計算網絡（Q-function critic，用于計算單個動作獨立回報）的資料包括全局觀測資訊 + 被評估agent此刻局部觀測資訊。
- 喂給中心評價網絡（center critic，用于評估全局狀态 V ( s t ) V(s_t) V(st)）的資料包括全局觀測資訊 + 全部agent此刻局部觀測資訊。
5.4 實驗結果
實驗結果如下圖所示，其中3m，5m分别指代一個作戰小隊中包含3個，5個marine（一種兵種）；2d_3z指代一個作戰小隊中包含2條龍和3個狂熱者。