# ICML

當前研究背景和動機：
* 多智能體強化學習 (MARL) 在複雜機器人和戰略領域中的重要性
* 通信信息對於多智能體合作的必要性和價值
* 近期多智能體通信領域的研究重要和挑戰 (發什麼消息和發給誰)

有限頻寬問題及現有方法的限制：

* 多智能體學習中面臨的有限頻寬問題，特別是在傳輸過程中。
* 現有解決方法（如調度器）的局限性，仍未解決通訊內容的最佳化問題。

本文的解決方案與貢獻：

* 透過壓縮通訊訊息解決有限頻寬問題。
* 從通訊理論角度，將有限頻寬轉換為對通訊訊息熵的限制。
* 引入Informative Multi-Agent Communication（IMAC）方法，透過學習通訊協定和調度來實現低熵和有用訊息的傳遞。
* 在不同環境下的實驗表明，IMAC方法能夠有效地處理有限頻寬約束，並實現更快的收斂。

## Problem Setting

考慮一個 communicative multi-agent RL 任務, 其 tuple 定義為 (n,S,A,r,P,O,Ω,M,γ),

n 代表 agent 的數量, S 代表 global 狀態空間, A = {A_i} for i=1,...,n, 代表所有 agent 的動作空間, O = {O_i} 代表所有 agent 的觀察空間, M 代表訊息空間. P : S × A → S 代表狀態轉移機率函數. 所有 agent 共享 reward function r : S × A → R. 每個 agent 都有自己的 observation function Ω(s, i) : S → O_i, γ 是 discount factor


每個 agent 接收 o_i 和 scheduling message c_i, 然後輸出 a_i 和 message m_i

scheduler  會接收 messages [m_1, ..., m_n], 然後發送 c_i = (m_1, ..., m_n)

每個 agent 要學 communication protocol和 policy  和 來最大化期望折扣獎勵

___
## Connection between Limited Bandwidth and Multi-agent Communication

### Communication Process


1. 通訊過程的階段：
* 通訊過程包括五個主要階段：類比到數位、編碼、傳輸、解碼和數位到類比。
* 每個階段都有特定的功能和流程，用於確保訊息的順利傳輸和解釋。
2. 模擬到數位（Analog-to-Digital）：
* 智慧體發送連續訊息，並由類比到數位轉換器（ADC）將其轉換為可計數集合。
* ADC 的操作包括取樣和量化，將連續訊號轉換為離散訊號。
3. 編碼（Coding）：
* 編碼階段將量化後的訊息透過來源編碼方法（如 Huffman 編碼）映射為位元流，以便進行傳輸。
4. 傳輸（Transmission）：
* 傳輸器將位元流調製成波，並透過通道傳輸波，然後接收器將波解調至另一個位元流，以解碼訊息。
5. 解碼（Decoding）：
* 解碼是編碼的逆過程，將位元流映射回恢復的訊息，以便最終傳遞給調度器或智慧體。
6. 數位到類比（Digital-to-Analog）：
* 最後，調度器從數位到類比轉換器（DAC）接收到重構的類比訊息，並將其傳遞給相應的接收智慧體。
7. 頻寬限制的影響：
* 這些階段中的每一個都受到頻寬的限制，尤其是在傳輸階段，頻寬限制了資料的傳輸速率和訊息的有效性。
___
### Limited Bandwidth Restricts Message’s Entropy

作者把 m_i 建模為連續隨機向量 M_i, 即從某個分布中採樣連續變量. 長時間而言, 這些 m_i 會遵循某些分布. 將連續變量 quantize (量化) 到 discrete symbols. quantize 這個動作會在離散變量的熵和連續變量的微分熵之間產生差距.
(微分熵是用來形容"連續"變量的熵)

使用 X 代表機率密度函數的連續隨機變量, 我們使用間格 ∆ 量化這個函數成 K 個 level, K = ceil(|X|/∆), 量化變數為 X^∆.

微分熵 H(X) 和熵的差距為一個常數, , 然後要對這些 quantized symbols 進行編碼.

一組 n 個 quantized symbols 會被編碼成bitstreams. 這些 symbols 可以被視為具有 H(X^Δ) 的離散隨機變量 X^Δ 的 n 個獨立樣本. 令 L 為對 n 個 symbols 進行編碼的平均 bit 數. 最小的 L 滿足 

這定義了編碼階段.

>簡單總結就是原本訊息是連續的, 但我們想做離散的, 要考慮轉換過程前後 訊息 的不同

---

>編碼的部分說完, 接著是傳輸

然後在傳輸中，透過無雜訊頻道，最大頻寬定義為最大資料速率：

### Proposition 1
在無雜訊頻道中，頻道 B 的頻寬限制了 messages’ elements 的熵。

給定一個 message's element X 具有微分熵 H(X) 的 i.i.d 連續隨機變量, 其量化時間序列為 [X^Δ_1, ..., X^Δ_t].

通訊系統的頻寬 B 以及 signal levels K，通訊系統每秒傳送 n 個符號。


最終可以得到


### Proposition 2
在無雜訊頻道中，頻道B的頻寬限制了訊息的熵。(與命題 1 不同於是 message, 而不是 elements, 但同理 1, 故不贅述)
message M_i = [X_1, X_2, ..., X_d]


最終，有限的頻寬 B 強制規定訊息熵
H(M_i) ≤ H_c ∝ B 的上限 H_c。

___

## Measurement of a Message’s Entropy

訊息 M_i 作為獨立同分佈的隨機向量可以遵循任意分佈，因此很難確定訊息的熵。 因此，我們保留訊息的歷史記錄，並找到一個 quantity 來衡量訊息的熵。

### Proposition 3

當有訊息的歷史記錄來估計訊息的平均值 µ 和 標準差 Σ 時，訊息的熵上限為 1/2 log(|Σ|(2πe)^d)，其中 d 是 M_i 的維度。

簡單說證明的原理是根據 最大熵原理. 結論就是 **H(M_i) ≤ 1/2 log(|Σ|(2πe)^d)**

## Informative Multi-agent Communication
如上一節所示，有限的頻寬要求代理程式發送低熵訊息。 在本節中，我們首先介紹我們透過 information bottleneck principle 學習有價值的低熵通訊協定的方法。
### Variational Information Bottleneck for Learning Protocols

作者提出了一種 messages 和 input features 的 **mutual information**(互訊息)的正規化


M_i 是具有機率密度函數 p_M_i(m_i) 的隨機向量, H_i 是具有機率密度函數 p_H_i (h_i) 的隨機向量，h_i為 [oi,ci]。

這種正則化強制代理發送 low-entropy messages。

現在設想 n 個 agent 有策略 , 通訊協定(protocols) , 這兩個的參數表示成 ,

另外還有 schedulers , 其參數表示成 

為了學習在固定 schedulers 下的 protocol, agent i 應該最大化


但實際上, 作者使用 information bottleneck Lagrangian 來最大化


β is the Lagrange multiplier.

互訊息被定義為：


其中 p(h_i, m_i) 為本節開頭說道的兩個機率密度函數的聯合機率.

[互訊息-維基百科](https://zh.wikipedia.org/zh-tw/%E4%BA%92%E4%BF%A1%E6%81%AF#:~:text=%E5%9C%A8%E6%A6%82%E7%8E%87%E8%AB%96%E5%92%8C%E8%B3%87%E8%A8%8A,%E5%96%AE%E4%BD%8D%E9%80%9A%E5%B8%B8%E7%82%BA%E4%BD%8D%E5%85%83%EF%BC%89%E3%80%82)

但由於無法知道的先驗分布, 所以無法計算

作者使用的 Gaussian approximation , 並將視為 multivariate variational encoders.

由於, 我們展開 KL 項獲得
>簡單說就是log分子分母分開成兩項, 接著移項

[Kullback–Leibler divergence](https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence)

接著就得到互訊息的 upper bound：

這為我們要最大化的目標提供了 lower bpund：


所以只要能最大化這個 lower bpund 即可, 其梯度為：

>總結來說, 就是利用 variational information bottleneck, 我們可以控制訊息的分布, 從而用不同的先驗 來控制它的熵, 以滿足訓練階段不同的有限頻寬.
因此
>

### Unification of Learning Protocols and Scheduling