作者丨王維塤

學校丨天津大學碩士生

研究方向丨DRL & MAS

以彼之道還施彼身

■ 論文 | Maintaining Cooperation in Complex Social Dilemmas Using Deep Reinforcement Learning

■ 連結 | https://www.paperweekly.site/papers/1558

為什麼要叫做以彼之道還施彼身，是因為這篇文章借鑒了 TFT 的思想，擴充套件成 amTFT。而我對 TFT 的第一反應就是姑蘇慕容的以彼之道還施彼身。

這篇文章是 Facebook AI Research 投在今年 ICLR 上面的文章。不算很好，但是想要解決的問題還是很有意義的，所以大家可以辨證地看這篇文章，希望能讓各位有所收穫。

核心問題

1. 研究問題：在 complex social dilemmas 中如何設計出既能考慮 social welfare，又能確保自己 payoff 的 agent。

2. 假設條件：能夠觀察到對手的 action，能夠事先知道環境。

3. 主要想法：如果想要最大化 social welfare，那麼就是在對手能夠合作的時候與對手合作。要確保自己的 payoff，就是在對手背叛的時候，自己也背叛，確保自己不會被對手利用。

4. 解決方案：

事先訓練出 fully cooperative policy 與 safe policy（defection）的策略，同時獲得雙方都合作／競爭時的 Q 與 V；
然後透過對比對手當前 action 的 Q（合作）的值與對手當前 action 的 Q（合作）的值，如果當前 action 的 Q 值更高，就說明對手採用背叛的action；
累積對手背叛的程度，在一定閾值後，採用 K 次背叛的策略（K 的次數類似懲罰，採用 V 值進行計算），然後再切換成合作的策略，再次迴圈。

Background

關於 social dilemma，簡單地說就是 agent 們相互合作能夠得到比較高的 payoff，同時 total payoff 是最高的，但是不論在什麼情況下，採用 selfish 的 action 能夠比採用合作的 action 獲得更高的 payoff，所以 agent 為了自己的 payoff 有動機採用 selfish 的 action。

但是雙方都採用 selfish 的 action 時，payoff 反而比都合作時候的 payoff 低，同時 total payoff 也比較低。

通常對於 social dilemma 的研究環境，我們都採用是 repeat game，就是固定一個矩陣的 game，然後不停地玩這個 game。

在 Deepmind 的 Multi-agent Reinforcement Learning in Sequential Social Dilemmas 中，將 social dilemma 擴充套件到了 sequential 下，因為環境更複雜了也帶來更多的挑戰。

比如 defection 和 cooperative 是體現在一些列 actions 中，我們很難透過 actions 來判斷是合作還是競爭，同時傳統的 ISD 直接的方法不能直接擴充套件到 SSD 下麵。

那麼我們自然會想到使用 DRL。在複雜的 mas 環境中，我們通常使用 DRL+self-play 來訓練 agent，用簡單地話說，self-play 就是不斷重覆模擬 game，在模擬中控制所有的 agent，並不斷地 improving 這些 agent 的策略，並最終獲得訓練好的策略，在面對新的，未知的對手時，採用訓練好的 policy 來應對。

本文思路

但是在 SSD 中，我們並不能簡單地使用 DRL+self-play 來訓練 agent，主要原因是一個一直採用 cooperative policy 的 agent 容易被對手利用，一個一直採用 defection policy 的 agent 最終只能與一個理智的對手達成 social dilemma。

因此我們應該設計出一種演演算法，讓 agent 能夠根據對手的行為來調整採用 cooperative 還是 defection。

一個經典的做法叫做 Tit For Tat（TFT），TFT 就是在第一局採用合作，然後在以後的局面中採用對手上一局採用的 action。

說來簡單，但是 TFT 是一個非常強大的演演算法，能夠與能合作的對手合作，避免被對手利用，同時一旦對手能夠選擇合作，就會選擇合作，並有希望一直保持合作。

從描述中，我們就能很直觀地發現 TFT 並不能直接用在 SSD 的情況下，主要的原因是環境已經從一個矩陣，變成一個需要做序列決策的環境了。

雖然 TFT 不能直接用，但是我們可以利用 TFT 的思想來構造一個與 DRL 相互結合的演演算法，也就是這裡的演演算法：APPROXIMATE MARKOV TFT（amTFT）。

TFT 能夠直接用上一局對手的 action 來選擇自己這句的 action 的主要原因就是，在傳統的矩陣形式的 game 中，action，reward，defection，cooperative 這幾個其實可以理解為等價的，一者確定之後，其他就確定了。

比如我選擇 defection 的 action，那麼它的 reward 資訊就大致確定了（因為還與對手的 action 相關），所以在這裡我不嚴謹地說：選擇 action，本質上也就是在利用 reward 的資訊。

那麼就很直觀，在矩陣下麵我利用 reward 的資訊，在一個序列的決策中，我們就可以利用 Q 或者 V 的資訊，amTFT 就是利用 Q 與 V 的資訊。

具體做法

首先，我們採用 selfish 的方式，每個 agent 都是最大化自己的 reward 的方式，來訓練自己的 policy，我們可以得到 agent 的策略 , 相應的 Q function approximations。

然後我們在採用 fully cooperation 的方式，agent 標的是最大化 total payoff 的方式來訓練策略，同樣我們可以得到 agent 的策略, 相應的Q function approximations。

那麼如果我們要衡量在當前 state s 下，我們合作時（假設我們是 agent1 ，對手是 agent2），對手當前 action 是否是合作的？

我們可以使用雙方都合作的時的，假設對手採用合作策略時，和當前採用 action 的 Q 的差值，如果當前 action 的 Q 值，則說明對手採用了競爭的 action，即為下式：

當 d 大於 0 時，我們覺得對手是採用競爭的策略，那麼我們可以變化自己的策略為競爭的策略。

在這裡 amTFT 的實際做法並不是像 TFT 那樣，不停地按照對手的 action 來調整自己的 action，而是變化為 defect 之後，保持 defect k step，然後調整為 cooperation，再次觀察對手的合作程度。

這裡就帶來兩個問題，一個問題是：一次 d 其實並不準確，容易有很大的誤差。另外的問題是：k step 的 k 該如何決定？

第一個問題其實比較好解決，我們可以不停的累積 d，直到 d 的累積和超過一個閾值，我們認為對手是 defect，然後再變換為 defect 的策略。這樣透過累積的方法，更加容忍 d 計算上可能的問題，但是實際上也帶來了一定的延遲性。

第二個問題其實也蠻重要的，因為如果採用固定的 k，容易被對手考慮全域性，在某個 s 下來利用這個性質。所以這裡採用類似懲罰的思想，使用第一個問題中累積的 d，來計算我應該懲罰對手多少局，它才會把這幾次背叛獲得更多的 payoff 損失掉：

其中 α 為超引數，大於 1，代表採用 D k step 後切換成 C。所以這裡其實是定義了一個下界。整體的演演算法如下所示：

實驗

在這裡做了兩個實驗環境：

coin game：在一個 5×5 的格子世界中，有兩個不同顏色的 agent，也有兩個不同顏色的 coin，agent 不論收集到什麼顏色的 coin，agent 都會得到 +1 的 reward，但是如果 agent 收集到了另外顏色的 coin，對應顏色的 agent 會得到 -2 的 reward。

一般情況下，selfish 的 agent 就算不論什麼顏色都收集，合作的 agent 都只會收集自己的顏色的 coin。

Pong Player’s Dilemma (PPD)：就是將 Pong 擴張成 SSD 的情況，贏球的 agent 獲得 +1 的 reward，輸球的agent 獲得 -2 的 reward。所以 selfish 就是努力自己得分，合作就是雙方儘力不得分，在中間傳球。

在這兩個環境中，amTFT 達到了我們的目的：與合作的合作，與競爭的競爭，相互直接合作。

然後我們研究如果固定一個 agent 的策略，另外一個 agent 用 selfish 的角度，從頭開始學會怎麼樣（結果如上圖）。

這裡採用的固定的 agent 的策略為：合作，競爭，amTFT。面對合作／競爭的 agent 時，selfish 學到利用。面對 amTFT，selfish 最終學到合作。

小無相功

■ 論文 | RL^2: Fast Reinforcement Learning via Slow Reinforcement Learning

■ 連結 | https://www.paperweekly.site/papers/1560

小無相功可以模擬各種武功，只要你學了，各種武功皆數模仿，就向對 reinforcement learning 做 meta-learning，學會了 reinforcement learning，還有什麼學不會。

核心問題

1. 研究問題：如何對reinforcement learning進行learning，也就是meta-learning。

2. 假設條件：知道想要解決的問題的模型是什麼樣（能夠構造一大組（分佈）MDP）。

3. 主要想法：如果在一大組 MDP 中學習到的 agent，在面對未知（新的）MDP 時，能有不錯的效果，說明 agent 已經學到這類 MDP 的性質，也就是 prior。

4. 解決方案：用 RNN 來學習，用一大組 MDP 訓練出 RNN 的權重（視為 meta-learning），然後面對新的 MDP 時，用不斷產生的 input 來調整 hidden state，將不斷變化的 hidden state 是為當前 MDP 的 reinforcement learning。

思路

通常我們都是針對具體型別的問題設計相應的演演算法，因為是針對具體型別的設計，所以這樣的演演算法必然效能等方面會比較好，但是也因為是對於具體型別設計的，所以必然會有更多的侷限性，對於別的型別可能並不適用。

因此我們會想：能不能有萬能演演算法能夠針對不同型別的問題，學習出相應的型別，然後自己根據問題型別，來學習設計出演演算法？

deep learning 已經具有一定提取特徵的能力了，所以懶惰的我們肯定會想如果 agent 能夠根據問題自己調整齣網路結構那該多好。這有點跑題了，但這也就是這篇文章，或者 meta-learning 所希望有的能力：learning to learn。

不同型別的問題和不同型別的演演算法有不同的學習正規化。對於 Reinforcement Learning 當然最重要的一點是：MDP，因為 RL 的目的是針對特定的 MDP 學習出最優或者不錯的 policy。

那麼我們希望能夠讓 agent 學習到 RL 的能力，那其實就是希望能夠學習到在不同 MDP 中尋找最優 policy 或者不錯 policy 的能力。

這其實有點大，或者說有點難，因為 MDP 的各個部分其實有很多的伸縮性，所以對 training 等方面是有很大的挑戰的。

因此本文其實做了一個假設：我們事先知道要解決是什麼問題，根據這個問題的型別，構造了一堆 MDP，然後在這堆 MDP 中學出 MDP 中的特性，並將其應用在這個問題上，說明我的 agent 已經學習到了這類 MDP 的性質。

具體做法

PRELIMINARIES

discrete-time finite-horizon discounted Markov decision process (MDP) .

RL^2

如果我們使用 RNN 來構造 agent，agent 的輸入為：以前的 rewards，actions，termination flags 和 normal received observations。

同時 RNN 的 hidden state 並不在每次 episode 開始後重置，而是保留，然後使用標準的 RL 演演算法來 training 這個 agent，那麼這個 agent 應該能 capacity to perform learning in its own hidden activations。

這個 agent 在 deployed 時，面對未知的 MDP 應該能夠根據當前的資訊來調整 hidden state，也就是學習到了 RL 的能力，這也正是本文被稱之為 RL^2 的原因。

首先定義一個 MDPs 的知識，也就是在一大堆 MDP 中每個 MDP 被抽樣的機率：，然後每次我們透過這個 M 來抽取MDP，抽取後將這個 MDP 固定 n 個 episode，比如上面的圖就是固定了 2 個 episode，也就是 n=2 。然後再繼續抽取新的 MDP，這樣不斷的學。

這裡的細節是：agent 會使用上一時刻的 reward，上一時刻的action，上一時刻的termination flag（從上圖可知，我們時是固定了一個 MDP n episode，所以需要明顯地知道結束）和當前的state做為agent的輸入的。

另一個重點是：我們是最大化這 n 個 episode 的 expected total discounted reward，這其實等價於 minimizing the cumulative pseudo-regret。

同時因為我們每次都是抽去出的 MDP，所以 agent 並不知道面對的是哪一個 MDP，所以 agent 應該要能夠利用歷史上的 input 推測出這個 MDP 的資訊，然後調整 policy，也就是 hidden state。

MULTI-ARMED BANDITS

就是經典的多臂賭博機，這裡存在很多個臂，然後從這些臂裡面抽取出一些臂做為一個賭博機來學習，每個臂被抽出的機率為 p_i ，所以是可以抽取多個賭博機，這就是上面說的 MDP 的 set，我們的目的是：maximize the total reward obtained over a fixed number of time steps。

這是個單狀態的問題，但是也要平衡探索與利用，因為研究的比較多，同時有 rich theory，可以與一些有理論保證，漸進線形最優的 policy 做對比，If the learning is successful, the resulting policy should be able to perform competitively with the theoretically optimal algorithms.

這裡與幾個 policy 做了對比：

random
gittins index
UCB1
Thompson sampling (TS)
ε-greedy
greedy

同時，我們把所有的 true distribution 提供給上面需要的演演算法（ RL^2 除外）。

還是不錯的，但是因為已有的演演算法 mostly designed to minimize asymptotic regret (rather than finite horizon regret), hence there tends to be a little bit of room to outperform them in the finite horizon settings.

另外發現說在 n=500，k=50 和 index 有一些差距，為了探索是不是學出來的 RL 不夠好，就使用相同網路結構，然後用 index 來生成資料對網路做 SL，發現能學的和 index 差不多，說明 RL 學的還是有提升空間的。

TABULAR MDPS

多臂賭博機是一個單狀態的，但是 RL 是針對 sequential decision making 的，所以這裡就採用隨機生成 tabular MDP 來做測試。

這裡我們限制 state 空間為 10，action 空間為 5，rewards follow a Gaussian distribution with unit variance, and the mean parameters are sampled independently from Normal(1, 1) ，transitions are sampled from a flat Dirichlet distribution，然後 episode 的 horizon 為 T=10。

然後與下麵比較：

random
PSRL
BEB
UCRL2
ε-greedy
greedy

發現還是有一定效果的。

VISUAL NAVIGATION

每個 MDP 是隨機產生的 maze，然後標的是也是隨機的，但在一個 mdp 的不同 episode 下，maze 與終點時固定的。reward 和 cost 設定為：找到標的 reward+1，如果碰牆，cost 掉 -0.001，每個時間 step，cost 掉 -0.04。

先在 5×5 的世界中做 training，n=2，horizon=250。然後 maze 是從 1000 個 configuration 中產生的。在 test 時做了以下工作：1. 在 9×9 與 5×5 裡面看看效果如何；2. 將 agent 執行 5 個 episode 看看怎麼樣。

POLICY REPRESENTATION

輸入 (s, a, r, d) ，透過函式 Φ (s, a, r, d) 做 embedded 後做為 RNN 的輸入，RNN 的 cell 採用 GRU，然後在接一層全連線，再使用 softmax 做為啟用函式，輸入為每個 action 的機率。

另外這裡說引數在每個 episode 開始的時候重置一部分的 hidden state，這樣的目的其實是說開始和結束必然存在一些不一樣，希望學到這部分不一樣，但是實際實驗並沒有效果。

採用 off-the-shelf RL algorithm：rllab and TabulaRL，使用 first-order implementation of Trust Region Policy Optimization (TRPO)，同時To reduce variance in the stochastic gradient estimation, we use a baseline which is also represented as an RNN using GRUs as building blocks. We optionally apply Generalized Advantage Estimation (GAE).

hidden activation: relu
all weights matrices use weight normalization without data-dependent initialization
hidden to hidden weight: orthogonal initializaion
other weight: Xavier initialization
bias: 0
the policy and the baseline uses separate neural networks with the same architecture until the final layer, where the number of outputs differ.

MULTI-ARMED BANDITS

TABULAR MDPS

VISUAL NAVIGATION

40 x 30 RGB image, range [-1, 1]
2 層 Conv：16 個 filter， size 5 x 5， stride 2
將 action embedded 到 256-dimensional vector，然後與 2 的輸出 flattened 後拼接
256 hidden dense

左右互搏：self-play

■ 論文 | Emergent Complexity via Multi-Agent Competition

■ 連結 | https://www.paperweekly.site/papers/861

這篇文章給我們的最大啟發是，在實際工作中如何訓練一個比較複雜的 agent。

實驗效果蠻有趣的：