# Multi-agent RL
## Introduction
### Multi-agent vs. Single-agent

multi-agent跟single-agent最大的差別在single agent只需要根據環境的互動來做學習

但multi-agent除了跟環境的互動外其他agents的動作也會影響到自己，且multi-agent的行為在訓練中是不可預期的，所以會比single agent要來的複雜許多

### Multi-agent的分類

- Anlysis of emergent behaviors : 簡單來說是把所有的agent直接灑到環境中，不溝通也不共享訊息，各自學習的一種訓練方式
- Learning communicate :在學習的過程中agent彼此間會傳輸訊息或是共享訊息來學會如何溝通而達到更好的結果
- Learning cooperation : 在學習的過程中agent透過學習互相合作而達到更好的結果
- Agent modeling agents: 若agent間並沒有溝通，但是agent透過看到其他agent的一些外在結果來去model自己的訊息

### Centralized vs. Decentralized

Centralized : 只透過一個agent決定所有的actions

Decentrailzied : 會有多個agents，且各自的agent透過學習得出各自的action

## Action Branching Architectures for Deep Reinforcement Learning

### Abstract + Intro

舉例：若一個路口會輸出綠燈時間0-30秒，共30個action可以選，那若今天有三個路口那action space就會增長為30*30*30個，是exponential成長，透過Action branch能達到線性成長 變30+30+30=90。

拿這篇paper的架構Branching Dueling Q-network，是透過一層share layer接到各自對應的branch上

經由這個share layer來去調空各個branch的action。

BDQ可以在一個把continuos action space 切成6.5*10^25的 discrete action space後玩的比DDPG好

BDQ跟IDQ做比較（IDQ是完全沒有共用參數）得到IDQ隨著維度增加很快就爆了

這種對控制的部份分佈其實在自然界中也能看到：例如章魚的腳

### Branching Dueling Q-Network

如果可以直接不管其他agent各自練各自的，每個agent只自己做優化那就可以大幅減少action space

但直接這樣練顯然有問題，為了解決它提出了一個結合Dueling DQN的演算法 稱之為BDQ


透過三種方法去改善DQN這個演算法

### Double Q-learning + DDQN

原本的Q learning會有 overestimation的問題 透過Double Q learning改善這問題

Double-Q 可以解決 select max的問題

DDQN 透過target network解決bootstrapping問題


### Prioritized Experience Replay

sample時不要uniform選，而是透過Loss去優先選一些比較重要的buffer來提昇訓練的結果

### Dueling Network Architecture


透過這公式去實作出同時能產生state vlaue 跟 advantage的網路去估計Q值

而實驗顯示扣掉mean A*結果較好

### Methods

- Common State-Value Estimator

在架構上每個branch的使用的state value都是同一個

而實驗上得出(無理論)證明扣掉mean A*結果較1.不扣、2.扣maximum好

- Temporal-Difference Target

TD target的計算按照理論上也是用max action去預估下一個state的Q值

但實驗上得出去取mean也會比max來的好

- Loss function

把每個branch的predict 跟target的error取決對值加起來取平均當作loss是最值觀的作法

但實驗上得出square error的效果比直接取error更好

- Gradient Rescaling

因為是所有branch會更新到同一個share memory上所以要rescaling

除以N+1的原因是因為還有考慮State Value

- Error for Experience Prioritization

透過所有branch的target跟predict的絕對值累加當作priority的error

error越大代表預測的越不準，代表還有很大的進步空間所以需要比較高的優先權來sample

### Experiments

拿去跟沒有變形的Dueling DDQN比也在連續環境中去跟DDPG比

而為了要讓演算法能在連續環境上使用，使用到切割的技巧把連續的空間切成N等份變成離散空間

### Custom Reaching Environments

去客製化reacher v1這個遊戲 擴張成維度3 4 5 的情況下去看Dueling跟BDQ的表現誰比較好

在延伸去把個別dimension的action space分成n = 5跟n= 9的情況下作考慮 若N=5 n= 9 就有9^5種state可以選

結果可以看到BDQ隨著N跟n增長的表現會比較穩定

### Standard Benchmark Environments

比較BDQ跟IDQ跟DDPG的演算法在4個環境中，值得注意的是DDPG在最複雜的遊戲中輸了

而在其他較簡單的遊戲中則跟BDQ差不多或是略優於BDQ，作者解釋的原因是因為DDPG的探索是用noise的緣故在單前時段能夠做更好的的exploration

而可以發現Dueling DDQN在Reacher還練的起來但到Hopper就不行了 這只多了一個維度N=2 → 3

### Note
BDQ的穩健性整體是比較好的但隨著priority experience replay buffer 的ablation它會嚴重惡化
因此prioritize experience replay仍是未來研究的主題

## Multi-Agent Deep Reinforcement Learning for Large-scale Traffic Signal Control

### Abstract + Intro

早期的交通方法是在解優化問題，但需要透過大量的數學計算，使它們不太好用，且不一定符合現實狀況

因為action space過大的關係所以要透過MARL的方式去處理，但也因此面臨幾項挑戰

環境在各個agent只能看到部份的訊息，因為agent之間的溝通不夠完整。

提出了一個可擴展、decentralized的MARL 方法，將multi-agent 結合A2C

去跟完全獨立的A2C、Q learning做比較，結果證明了與其他最先進的分散式 MARL 算法相比最優

### decentrailized vs. independent

decentrailized代表各個agent中還是各自訓練，並沒有透過一個layer去調控，但有可能去抓取其它agent的資訊來做訓練，但independent就完全是沒有其他agent的任何資訊了

### Method

### Consider latest neighbor agent policy and state

把最新的policy的鄰域也考慮進來，增加local agent觀察的範圍


### Use spatial discount factor adjust the state and reward signal from other.

透過spatial discount factor來去調整從其他agent收進來的reward該如何影響個別agent的決策

α = 0 代表完全只考慮自己的reward (greedy)

α = 1 代表會完全考慮其他neighbor的reward(coopeateive)


### Archeitecture


這邊用LSTM的原因是因為歷史交通資訊對agent來說很重要，因此透過LSTM讓它能有效去recall這些歷史訊息

## CoLight: Learning Network-level Cooperation for Traffic Signal Control

### Problem

- 環境的變化是動態的

把target路口相鄰的路口拉進去考慮時，相鄰的路口若是主要幹道那它對target路口的影響應該要更大，但相鄰的路口對target路口的影響是會隨時間改變的。

例如到早上巔峰A→target→C很塞，晚上下班可能就會是A←target←C很塞，方向會改變

透過Graph attention network 來去學這種動態的影響

- 分享model variable可能會有不相容的問題

因為agent間會透過share model variable來提升訓練效率，但可能會遇到不同intersection所考慮的importance不同衝突

例如：A路口的主要影響會是W,E，因此會把neihbor index成[W,E,S,N]，而B路口的主要影響會是N,S，index成[N,S,W,E]

這篇paper透過定義impotance跟attention，透過attetion wegited來implement index-free model來解決這個問題


### Method


### Cooperation through dynamic communication & Index-free model learning with parameter sharing


- embeded observation

把observation過embeded layer後得到hidden state

- importnace

Wt := embeding parameters for target

Ws := embeding parameters for source

- attetion

把先前定義的importance過一個softmax得到相對的attention value

- representation of several source instersections to target i

經過一次與經過兩次Graph attetion network的結果，可看到第二次更明顯的顯示出了主要幹道上的負載量，經過越多層GAT理論上可以達到更精準的評分結果

### Multi-head Attention


如同上述步驟，但同時做了多種linear projection 用了不同種的{Wt,Ws,Wc}，最後在取平均

實務上5個head attetion的結果最好

### Q-value Prediction

p代表的是有可能的phase數量，像一般的Q-value選擇一樣，最終從q個維度中選值最大的當作output action phase。

## Slide
https://docs.google.com/presentation/d/1WHcdeiRhR18sSfF9Mg-2v2Jldq6AGJ_pknZXYtEOCvM/edit#slide=id.gdcd6917336_0_6