---
# System prepended metadata

title: Multiagent Reinforcement Learn

---

## Multiagent Reinforcement Learning-Based Cooperative Multitype Task Offloading Strategy for Internet of Vehicles in B5G/6G Network

### system model - network model
![image](https://hackmd.io/_uploads/SkirRXQn6.png)

在一個system上, 會有 M 個 edge server (ES) 使用 ℳ={1,2,3,…,𝑀} 表示

接著, 使用 𝐹={𝑓_1,  𝑓_2,  …,  𝑓_𝑀}表示 ESs 的 computation power, 單位為 CPU frequency

對於每輛車子能發出的任務類型, 使用 𝒯={1,2,…,𝑇} 表示, 實驗方便, 每輛車子一個時間點發出的 𝒯 集合大小相同

對於每個任務類型的特性, ![image](https://hackmd.io/_uploads/BJhR4472a.png), 𝑛∈𝒯, 𝑐_𝑛^𝑡 表示 size of the computation task (CPU cycle), 𝑠_𝑛^𝑡 表示 size of input data, 𝑑_𝑛^(𝑡,𝑡𝑜𝑙𝑒) 表示最大可容忍延遲。任務的大小會影響該任務的負載。

### system model - Offloading model

![image](https://hackmd.io/_uploads/Hk_3NEmhT.png) 表示 ES m 的最大 computation resource.

![image](https://hackmd.io/_uploads/SJB2rVm2p.png), 其中![image](https://hackmd.io/_uploads/B1eK0H47ha.png)表示在 ES m 上的第n個類型的任務在 t 時刻造成的負載, 此外本篇論文假設任務是 fine-grained, 所以可以任意比例的分配給不同的 ES 執行處理任務

![image](https://hackmd.io/_uploads/SkcFUVX3a.png) 表示為 ES m 在時刻 t 的卸載策略, 表示將 nth-type 任務卸載給 ES 𝑚_1 的比例, 𝑚_1∈ℳ,  ![image](https://hackmd.io/_uploads/SyuoIVQ2a.png)

### Delay model - Computation Delay

延遲的部份分成兩個, 一個是計算所需的時間和傳輸任務計算資源的時間, 首先是
#### computation delay

![image](https://hackmd.io/_uploads/rkNDcVm3a.png)
表示 ES m 在 t 時刻的compuation power, 相當於可以同時處理幾個任務, 和前面的![image](https://hackmd.io/_uploads/Hk_3NEmhT.png)不一樣

根據queuing theory 的 W = 𝜌/(𝜇−𝜆) 可以寫下在 ES m 上第 nth-type 的任務在t時刻的 queuing delay：

![image](https://hackmd.io/_uploads/SJbLiNQnT.png)

這是任務在等待列隊中等待的時間, 需要特別注意的地方是分母的減號後面使用了一個假設, 也就是穩定狀態下, 某個edge server把任務分給其他ES的情況相當於其他ES分給本edge server的情況, 原因是, 在原本的queuing theory中 𝜆 代表到達率, sum中的a為ES m 給ES m_1的比例

接著是實際計算的時間, ![image](https://hackmd.io/_uploads/rkCiTNQ3p.png)表示在ES m上第nth-type的任務的computation delay：
![image](https://hackmd.io/_uploads/BkSs64Xhp.png)

所以total delay ![image](https://hackmd.io/_uploads/H1IcPOmhp.png) 為：![image](https://hackmd.io/_uploads/BJEjPdXnp.png)

會有 𝒳2 的原因是, 我們把任務分給其他edge server, 所以一個任務的完成不僅僅只有本地 ES 處理完, 還要等待其他 ES 處理完

#### communication delay

ES 間通過 fiber-wireless 傳輸 data。ES 在通訊時, 會有bandwidth division 和 channel interference 問題。簡單起見, 假設一對 ES 通訊的傳輸速率固定, 使用 ![image](https://hackmd.io/_uploads/r1-cFd7n6.png)表示

通訊時的queuing delay也是根據 W = 𝜌/(𝜇−𝜆) 可以寫下 ![image](https://hackmd.io/_uploads/BJVf5_X3T.png)：![image](https://hackmd.io/_uploads/rk-mqd7np.png)

會有這個 delay 的原因是接收任務也是一個一個接收, 一個一個傳送, 所以也會有排隊的問題, 其中![image](https://hackmd.io/_uploads/HynvcOQ3T.png)

所以total delay如下, ![image](https://hackmd.io/_uploads/H1X9su73p.png)

後半為實際傳輸的時間量

### Delay model – Problem Description

所以將上面兩種 delay 加總如下：
![image](https://hackmd.io/_uploads/B1QcVVV36.png)

所以目標就是最小化這個 delay：
![image](https://hackmd.io/_uploads/ryWXHNN2a.png)
![image](https://hackmd.io/_uploads/r1sHHVV2a.png)

a,b,c 為條件

其中, ![image](https://hackmd.io/_uploads/H1eCBE426.png), 這代表在 ES m 上第nth-type的任務的平均延遲

而分子的部分分別為
![image](https://hackmd.io/_uploads/rywWK242T.png)
![image](https://hackmd.io/_uploads/B1aZt2V26.png)

### MDP
![image](https://hackmd.io/_uploads/r1F0thVn6.png)

C- 為懲罰, 因為我們不希望負載低的 ES 將任務卸載給高負載的 ES, 所以把這些負載的加總作為懲罰

### SAC

梯度公式和以往一樣

![image](https://hackmd.io/_uploads/rJq2c3EhT.png)
![image](https://hackmd.io/_uploads/SJza5n42a.png)
![image](https://hackmd.io/_uploads/r1VTqh43a.png)

#### Offloading Algorithm Based on ISAC

因為車聯網的環境變化快速, 且變化頻繁, 所以使用 priority replay buffer, 學習那些比較需要學習的訓練資料, 並希望快速收斂, 不然 agent 還沒學到怎麼做, 環境又改變了

![image](https://hackmd.io/_uploads/ryBla2Ehp.png) 代表 the complexity of the jth sample in the experience replay buffer, 主要由 ![image](https://hackmd.io/_uploads/HkvWp2E36.png)  和 ![image](https://hackmd.io/_uploads/SkYfpn4hT.png) 定義


![image](https://hackmd.io/_uploads/S1NAn2N36.png)
如果目前 sample 到 jth 資料的頻率較低, 則提高它下次被採樣到的機率

![image](https://hackmd.io/_uploads/B1RAn3436.png)
如果目前 sample 的 jth 資料 Q 值還沒收斂, 下次採樣到的機率也會較高

![image](https://hackmd.io/_uploads/SyCvT3N2T.png)
此項為 TD error

![image](https://hackmd.io/_uploads/HybKa2436.png)
![image](https://hackmd.io/_uploads/B1AEQpEn6.png)

此項為 TD error 的係數, 由於![image](https://hackmd.io/_uploads/rkamQpEh6.png) 的 R_j 必為負數, 而熵必為正, 所以也就是說, 當某個 sample 亂度較大時, 代表這個 sample 更重要, 需要多加訓練, 另外, 延遲和懲罰的加總很小(負值), 則係數不要成長太大, 因為 TD error 可能已經很大

![image](https://hackmd.io/_uploads/r1jBY643a.png)

所以針對每個 sample 的抽取機率如下
![image](https://hackmd.io/_uploads/BJDwtpE26.png)
![image](https://hackmd.io/_uploads/SyIOtTV3a.png)
這個係數主要是避免distribution error的問題, 也就是說抽的sample沒有均勻分佈, 所以導致某部分的sample抽太多了, 導致那部分會overfitting, 而部分的sample反而都沒有抽到

![image](https://hackmd.io/_uploads/B1sF36En6.png)

### ISAC-Based Solution

此部分和以往的SAC差不多

![image](https://hackmd.io/_uploads/SJyp364hT.png)
![image](https://hackmd.io/_uploads/HkVa26Ena.png)
**Offloading strategy**

![image](https://hackmd.io/_uploads/r1E1p6V36.png)
![image](https://hackmd.io/_uploads/B1typ6Enp.png)
![image](https://hackmd.io/_uploads/H1ay6a43p.png)
**Temperature parameter**

![image](https://hackmd.io/_uploads/Byxl6643a.png)

![image](https://hackmd.io/_uploads/HyU-66Nh6.png)

### Distributed Offloading Algorithm Based on ISAC
![image](https://hackmd.io/_uploads/SJCcWh836.png)

這裡使用常見的集中式訓練 critic, 分散式執行 actor, 以下是其tuple

![image](https://hackmd.io/_uploads/r1_hm28nT.png)

要注意, 只有 critic 會看到全域資訊, actor 只能看到本地資訊

### algorithm

![image](https://hackmd.io/_uploads/rkQ4V2In6.png)

這裡要特別注意, 第19行作者有寫錯, 網路的參數更新理應要和第15行的 delta 有直接關係, 但公式 24 並沒有, 以下附上原始版本的 priority replay buffer 算法
![image](https://hackmd.io/_uploads/r1pjG6Uhp.png)

algorithm 2 的第 15 行和 19 行對應 algorithm 1 的 13 行和 15 行

### Performance Evaluation
作者使用自己 OCTDE-ISAC 算法和以下五種算法比較
* **DDPG**：DDPG 可以在連續動作空間中快速收斂，但不適合用於 IoV，因為這是快速變化的隨機環境。
* **RO**：ES randomly offloads local tasks to neighbor ESs.
* **Centralized SAC Offloading (CSACO)**：有一個集中式 agent，其負責訓練所有 ESs 的所有卸載策略，此代理人會	蒐集所有 ESs 的 local state，結合卸載行動，以促進 ES 間的合作。
* **Decentralized SAC Offloading (DSACO)**：和 CSACO  相反，在每個 ES 上都有 SAC 的 offload model，ES 根據 local state 去執行卸載任務。
* **SAC-Based Off-Line Centralized Training Distribution Execution Offloading Algorithm (OCTDE-SAC)**：和	OCTDE-ISAC 類似，但在採樣時沒有考慮樣本間的差異。

![image](https://hackmd.io/_uploads/H1zpuT82a.png)

SAC 優於 DDPG，因為 SAC 會做較多探索。

ISAC 收斂得更快，是因為 priority sample，表現更好的原因是 ISAC 的網路架構更接近 MADDPG，所以agent可以更好的合作。

![image](https://hackmd.io/_uploads/SJtIoT83T.png)


學習率高，收斂速度快，但穩定性差，無法到最優卸載策略

學習率低，收斂速度慢，還沒收斂，環境又變了

![image](https://hackmd.io/_uploads/rybPj6Lhp.png)

其他條件都不變，改變 ES computation capabilities，直觀的延遲都有所降低。

ISAC 優於其他算法的原因是其會考慮樣本的重要性，提高採樣效率、收斂速度和穩定性。

![image](https://hackmd.io/_uploads/SknPoTI3T.png)

即使任務規模增加，ISAC 穩定性較好。

![image](https://hackmd.io/_uploads/SyDujaU2T.png)

![image](https://hackmd.io/_uploads/Bk9ujT8hp.png)

當任務數量增加，部分 ES 會接近滿載。

OCTDE-ISAC 會將不同類型的計算任務卸載到最合適的ES上執行。 這減少了計算任務的延遲並實現ES之間的負載平衡。

![image](https://hackmd.io/_uploads/SkX9ipL2p.png)

平衡 ESs 的負載, 以降低降低任務的平均延遲, 使系統的 throughput 提升

![image](https://hackmd.io/_uploads/BJ9co6L36.png)

## Conclusion

* 本篇為了實現 ES 之間的負載平衡並減少車輛任務的延遲，提出了一種edge-edge協作 MEC 結構。透過考慮任務類型數量、資料大小、延遲容忍度等參數，將多ES計算卸載模型視為MDP。

* 提出一種ISAC演算法來優化系統的平均延遲，並採用自適應權重採樣機制來提高演算法的收斂速度和穩定性。為了減少通訊花費，採用離線集中訓練分散式執行架構，促進 ES 之間的協同卸載。

* 實驗結果表明，對於車聯網高動態場景，OCTDE-ISAC 在延遲、收斂性和效率方面優於現有的運算卸載策略。
