# Multi-Agent Game Abstraction via Graph Attention Neural Network

## introduction

* MARL 在序列決策問題上取得巨大的成功,但在大規模的MARL系統中, 龐大的 agent 數量和複雜的交互則會對策略學習過程帶來重大的挑戰
* 早期這方面是通過 game abstraction 和知識轉移等技術來加速 MARL, 但在大規模 MARL 環境中, agent 通常與其他 agent 相關聯, 所以學到單一 agent 策略的使用受到限制
* 近期則是通過預定義規則, 但在大規模 MARL 系統中這麼做是很困難的
* 作者提出基于通信的 MARL 算法 GA-Comm 和基于 actor-critic（AC）的算法 GA-AC

## background

### attention mechanism
* soft-attention

>用於計算元素的重要性分布. soft-attention是可微的, 因此可以通過端到端的反向傳播來訓練. 常見的激活函數為 softmax

* hard-attention

>hard attention 從輸入元素中選擇子集, 強制模型專注選出來的重要元素

### Deep Multi-Agent Reinforcement Learning
* CommNet
>CommNet 允許 agnet 在通道上進行通信，其中一个 agent被提供其他 agent 的隐藏狀態表示的平均值作为通信信號

* IC3Net
>可以根據們控機制學習何時進行通信，門控機制允許 agent 阻止其通信，并且可以被視為簡單的硬注意力

* MADDPG
>MADDPG採用了集中式訓練和分散式執行的框架，讓策略在訓練時使用額外的資訊。其中 critic 使用其他智能體的額外信息，而 actor 只能訪問局部信息

* MAAC
>MAAC學習具有軟注意力機制的集中式 critic。該機制能夠動態選擇每個時間步驟要關注的智能體。

## 方法

1. G2ANet：基於兩階段注意力的遊戲抽象：

* 提出了G2ANet模型，透過兩階段注意力機制實現遊戲抽象。
* 第一階段使用硬注意力機制，將智能體之間的關係表示為子圖，每個智能體只與需要協調的智能體相連。
* 第二階段採用軟注意力機制，學習子圖中每條邊的權重。

2. 學習演算法：

* 將G2ANet模型與策略網路和Q值網路結合，提出了兩種學習演算法：
* GA-Comm：基於通訊模型的策略網絡，考慮所有其他智能體的通訊向量來做出決策。
* GA-AC：基於演員-評論家模型的評論家網絡，考慮所有其他智能體的狀態和動作資訊來計算Q值。
3. 子圖編碼：

* 利用圖神經網路（GNN）對子圖進行編碼，為每個智能體獲取聯合編碼，描述了其他智能體對當前智能體的貢獻。
4. 優勢：

* 透過遊戲抽象，簡化了學習過程，使智能體只需與需要協調的智能體進行交互，減少了計算成本。
* 結合了硬注意力和軟注意力機制，使模型能夠充分利用智能體之間的關係資訊。
* 提出了通用的機制，可應用於不同的多智能體環境和學習任務。
---

### G2ANet: Game Abstraction Based on Two-Stage Attention
**Definition 2**（agnet 協調圖）：agent 之間的關係定義為一個無向圖G =（N；E），由節點集 N 和邊集 E 組成，其中E是N的元素的無序對。每個節點表示一個智能體入口，邊表示兩個相鄰智能體之間的關係。*(Definition 1 為 Markov game)*

soft attention 主要的思想是使用 softmax 函數學習其他 agent 對於當前 agent 的重要性分佈：


e_k 是 agent k 的特徵向量, T 是當前 agent 的特徵向量, w_k 是 agent k 的重要性權重

但 softmax 的輸出是相對值, 對於不相關的 agent 也會給一個極小的值, 減少真正重要的 agent 的權重, 所以作者提出 2-state attention 來解決上述問題.

考慮部分可觀察環境, 每個時間步 t, 每個agent i 都會接收到一個局部觀察 o^t_i, 這是 agent i 在 agent 協調圖 G 中的特性. 然後通過 MLP 編碼成 特徵向量 h^t_i. 使用特徵向量通過 attention 來學習 agent 之間的關係.

在過程中, 先使用 hard-attention 輸出一個 one-hot vector 來確定圖 G 中的節點 i 和 j 是否存在邊, 以及每個 agent 需要與那些 agent 進行交互.

接著使用 soft-attention 獲得邊上的權重. 通過這樣的方式, 可以獲得 agent i 的子圖 G_i, 其中 agent i 只與需要交互的 agetn 相連, 且邊上的權重代表關係的重要性.

子圖 G_i 可以通過 GNN 獲得一個代表其他 agent 對 agent i 的貢獻的向量

---

在這篇論文, 作者使用 LSTM 網路實現 hard-attention

對於 agent i, 作者 merge the embedding vector of agent i, j into a feature (h_i; h_j) and input the feature into LSTM model


f( · ) is a fully connected layer for embedding.

在傳統的LSTM網路中，輸出只取決於當前時間和上一個時間的輸入，而忽略了後續時間的輸入資訊。我們認為這種做法是短視和不合理的。因此，我們選擇了 Bi-LSTM 模型來解決這個問題。例如，agent i 和 agent j 之間的關係權重也取決於環境中 agent k 的信息，其中 agent k ∈ {1,…,n}，且 agent k is not in {i,j}。

此外,由於採樣過程的原因,hard-attention 往往無法實現梯度的反向傳播。

所以作者使用 gumbel-softmax 函數來解決：


gum( · ) 代表 Gumbel-Softmax 函數.

soft attention 權重  將嵌入ej與ei進行比較，使用 query-key 系統將這兩個嵌入之間的匹配值傳遞到 softmax 函數中：


W_k 將 e_j 轉換成 key, W_q 將 e_i 轉換成 query,  是 hard-attention value

### Learning Algorithm Based on Game Abstraction


在上圖, 我們可以為 agent i 獲得一個子圖 G_i, 其中, 中心節點是 agent i.

如果每個節點代表子圖 G_i 中 agent 的編碼，我們可以使用圖神經網路為 agent i 獲取聯合編碼，該編碼定義了所有其他 agent 對當前 agent i 的貢獻。

#### Policy Network Based on Game Abstraction

許多相關工作都集中在學習多智能體通信，其中大部分透過聚合函數實現通信，該函數可以訪問所有其他智能體的通信向量（e.g., average function, maximum function）並將其傳遞給每個智能體 。 透過這種方式，每個智能體可以接收所有智能體的資訊並實現通訊。 然而，在大多數環境中，並不需要每個智能體與所有其他智能體進行通訊。 這意味著頻繁的通訊會導致高計算成本，並增加策略學習的難度。

如同前面提到的，我們基於兩階段注意力的遊戲抽象方法是一個通用機制。在本文中，我們分別將 G2ANet 與策略網路、Q值網路結合，提出了兩種學習演算法：

1. 基於通訊模型的策略網路（GA-Comm）：每個智能體在做出決策時考慮所有其他智能體的通訊向量；
2. 基於演員-評論家模型的評論家網絡（GA-AC）：每個智能體的評論家網絡在計算AC方法中的 Q 值時考慮所有其他智能體的狀態和動作信息。


o_i 代表 agent i 的**觀察**, 它的策略可以寫成：


h_i 代表 agent i 的**觀察特徵**, x_i代表其他 agent 對 agent i 的貢獻.


e( · ) 是由 fully-connected neural network 參數化的 encoder function.

h_i' and s_i' are the hidden and cell states of the LSTM.

對於其他智能體對智能體 i 的貢獻，我們首先使用兩階段注意力機制來選擇智能體 i 需要溝通的智能體並獲得其重要性：


我們就可以透過 GNN 得到其他智能體的貢獻x_i。我們用一個簡單的方法來計算，它是透過兩階段注意力機制對其他智能體的貢獻進行加權求和：


### Actor-Critic Network Based on Game Abstraction

計算 agent i 的 Q value Q_i(o_i, a_i), critic network 接收 o = (o_1,..., o_N), 和 a = (a_1,..., a_N). 公式如下：


f_i 和 g_i 都是 MLP.

對於 x_i, 我們使用一個簡單的方法，它是基於我們的兩階段注意力機制的每個代理值的加權和：


v_j is an embedding of agent j, encoded with an embedding function and then transformed by a shared matrix V and h( · ) is an elementwise nonlinearity.

attention weight w_j is computed by the two-stage attention mechanism.

e_i = g_i(o_i, a_i)