多智能體強化學習筆記 02

09-09

多智能體強化學習筆記 02

來自專欄強化學習知識大講堂17 人贊了文章

前言：

距離上次更新又過去了好久，期間強化學習領域又發生了很多故事：OpenAI 人工智慧在TI8上的慘敗，谷歌推出新型強化學習框架Dopamine等等。對於這些事件不做過多評論，只想說這個領域在默默進步，並繼續在影響著各行各業。

正文：

上次的筆記介紹了多智能體強化學習的基本概念，並闡明馬爾科夫博弈是多智能體強化學習演算法的理論基礎。從馬爾科夫博弈這個辭彙上也能看的出來，經典的多智能強化學習演算法應該包括兩部分：強化學習和博弈論。強化學習基本演算法我們在前面的帖子中已經給出了，並出版了相關方面的書籍《深入淺出強化學習：原理入門》。相信看過前面帖子和書的讀者對強化學習的基本方法如Qlearning的方法已經有所了解。而最早的探索多智能體強化學習的演算法是對Qlearning演算法的修改，即Qlearning+博弈均衡。如果對博弈論並不了解直接講多智能強化學習演算法如：極大極小Qlearning；納什Qlearning，那麼大家肯定會很懵，而且把握不住多智能強化學習演算法的精髓。另外，真正能學到東西，其實是需要循序漸進的。一下子接觸帶有很多知識盲點的理論必定會打擊你學習的熱情和信心，退一步說，就算是硬著頭皮啃下來了，也實現了代碼，但是總覺得還是不踏實。其背後的原因是，你對這個問題缺乏理論上的認識。另外認知是需要一個循序漸進的過程，這個循序漸進的過程就是對相關理論的層層理解，並且這個過程對每個人都是必不可少的（不管你聰明還是不聰明）。所以在這裡需要先介紹一下博弈論。

博弈論博大精深，知友中肯定不乏博弈論方面的專家。在博弈論方面，我也是門外漢，這裡只是給出自己一些非常粗淺的理解，如果有錯誤還請不吝指教。

博弈論英文為game theory.從宏觀上可以將博弈論研究的問題分為：合作博弈和非合作博弈。現代狹義的博弈論一般是指非合作博弈。

非合作博弈根據參與博弈的參與人做決策的先後順序可以分為：靜態博弈和動態博弈。

靜態博弈是指參與人同時做決策，常用標準型（normal form）表述其策略。如兩人零和博弈等。

動態博弈是指參與人有先後順序做決策，且後者能觀察到前者所做的決策，如圍棋等。常用擴展型（extensive form）來表述其策略，常用的擴展型表述為博弈樹。

非合作博弈根據參與人是否已知對方的信息，可以分為：完美信息博弈和不完美信息博弈。

完美信息博弈是指：參與人對相關信息完全已知，如棋類遊戲。玩家知道對方棋子所在的位置。

不完美信息博弈是指：參與人對相關信息並不完全已知。如牌類遊戲，玩家並不知道對手的牌是什麼。

根據上述兩種分類，非合作博弈細分為以下四類：完美信息靜態博弈、完美信息動態博弈、不完美信息靜態博弈、不完美信息動態博弈。

我們只介紹最簡單的完美信息靜態博弈。

完美信息靜態博弈的基本概念：

1. 參與者：參與博弈的智能體，我們一般用小寫字母 $i$ 表示。

2. 動作空間：參與博弈的智能體 $i$ 的動作記為 $a_i$ ，則動作空間 $A_i=left{ a_i ight}$ 表示可供智能體 $i$ 選擇的所有動作的集合。N個參與者的動作的有序集記為 $a=left( a_1,cdots ,a_n ight)$ ，稱為n個智能體的聯合動作。

3. 策略：參與者做決策時，策略為動作空間上的分布。我們用 $pi_i$ 表示第 $i$ 個玩家的策略。

策略可以分為純策略和混合策略兩類。

純策略（pure policy）: 玩家i選擇某一行為的概率為1，而選擇其他行為的概率為0.

混合策略（mixed policy）: 玩家i選擇某一行為的概率小於1，而選擇其他行為的概率不都為0.

比如：玩家1和玩家2在玩剪刀、包袱、錘的尤其。對於玩家1，其純策略是指只出剪刀、或者包袱、或者錘。混合策略是指以一定的概率出剪刀、包袱或錘。如其最優策略是出剪刀、包袱、錘的概率都是1/3.

對於n玩家，它們的聯合策略為n個玩家的策略的有序集，即

$pi =left( pi _1,cdots ,pi _n ight)$

4. 回報函數：參與者i在聯合行為 $a=left( a_1,cdots ,a_n ight)$ 下所獲得的回報記為 $Q_ileft( a_1,cdots ,a_n ight)$

5. 值函數：參與者在聯合策略 $pi =left( pi _1,cdots ,pi _n ight)$ 下的值函數，定義為：

$V_ileft( pi _1,cdots ,pi _n ight) =sum_{a_1,cdots ,a_nin A_1 imes cdots imes A_n}{Q_ileft( a_1,cdots ,a_n ight) pi _1left( a_1 ight) cdots pi _nleft( a_n ight)}$

這裡需要注意的是值函數是在策略給定時計算出來的，這一點跟回報函數不同。當策略不同時，值函數不同。而且智能體i的值函數不僅與自身的策略有關，還跟其他智能體的策略有關。

參與者，動作空間、回報函數完全描述了一個博弈問題。現在舉一個博弈論中必講的一個例子：囚徒困境

圖1 囚徒困境

如圖1為囚徒困境。參與者為：囚徒A和囚徒B。動作空間為：{坦白、抵賴}，回報函數由矩陣給出。即：

當囚徒A和囚徒B都坦白時，囚徒A被判處3年有期徒刑、囚徒B也被判處3年有期徒刑。

當囚徒A坦白、囚徒B抵賴時，囚徒A被當場釋放、囚徒B被判處5年有期徒刑

當囚徒A抵賴、囚徒B坦白時，囚徒A被判處5年有期徒刑、囚徒B當場釋放

當囚徒A抵賴、囚徒B抵賴時，囚徒A和B都被判處1年有期徒刑。

對於這樣一個囚徒博弈問題，囚徒該如何選擇呢？是選擇坦白還是抵賴？

很明顯，如果兩個囚徒都選擇抵賴，那麼它們總的懲罰最低。然而，選擇抵賴對於囚徒個人來說是理性的嗎？

答案是：選擇抵賴對於個人來說並不理性。因為，就個人而言，囚徒並不知道另外一個囚徒選擇的策略是什麼。在這種情況下，選擇坦白對於個人來說是理性的，而且是最優的。

即，不管其他囚徒選擇什麼動作，選擇坦白總比選擇抵賴要優。

比如，對於囚徒A來說：

當囚徒B選擇坦白時，如果囚徒A選擇坦白被判處3年有期徒刑；而這時如果A選擇抵賴則被判處5年有期徒刑，所以這時囚徒A選擇坦白要好。

當囚徒B選擇抵賴時，如果囚徒A選擇坦白，則當場釋放；而這時如果A選擇抵賴，則被判處1年有期徒刑，所以這時囚徒A選擇坦白要好。

綜合這兩種情況，對於囚徒A不管囚徒B如何選擇，選擇坦白都是最好的。

在該例中（坦白，坦白）是佔優策略（dominated strategy）。所謂佔優策略是指如果一方在任何情況下從某種策略中得到的回報均大於從另外一種策略得到的回報，那麼我們稱為這種策略為佔優策略。在囚徒困境博弈中，「坦白」對於囚徒1是和囚徒2都是佔優策略。當存在佔優策略時，參與者選擇佔優策略。

如果單從博弈矩陣來看，所謂佔優策略是指在博弈矩陣中存在一行所有的值比其他行對應的元素都大，該行所對應的動作記為佔優策略。

一般來說，佔優策略只出現在特殊的博弈問題中，只適用於擁有佔優行的博弈矩陣。在博弈中更一般的策略不是佔優策略而是納什均衡策略。

下面，我們講解博弈論中最重要的概念：納什均衡策略。

納什均衡策略假設參與博弈的參與者都是個人理性的，即每個參與者都採用對自己來說最優的策略，同時要求沒有玩家能通過單獨偏離當前的最優策略可以改善它自身的回報。我們用 $pi _{i}^{*}$

表示納什均衡策略，那麼納什均衡策略應該滿足以下不等式： $V_ileft( pi _{1}^{*},cdots ,pi _{i}^{*},cdots ,pi _{n}^{*} ight) ge V_{ ext{i}}left( pi _{1}^{*},cdots ,pi _{ ext{i}},cdots ,pi _{ ext{n}}^{*} ight)$

關於納什均衡策略需要說明以下幾點：

1. 納什均衡策略是一個極值點，任何單個玩家偏離該點時，該玩家的回報都會受損。

這裡的關鍵詞是單個玩家，也就是說當其他的玩家都採用納什均衡策略，而該玩家不採用納什均衡策略，那麼此時該玩家的利益相比於該玩家採用納什均衡策略要小。

我們依然以囚徒困境為例。（坦白，坦白）是納什均衡策略。

我們以囚徒A為例，如果囚徒A不選擇坦白而選擇抵賴，那麼這時的策略為（抵賴，坦白），此時囚徒A所得到的回報是-5，小於納什均衡策略（坦白，坦白）的回報-3。

以囚徒B為例，如果囚徒B在囚徒A選擇坦白時而選擇抵賴，那麼囚徒B的回報是-5，小於納什均衡策略（坦白，坦白）的回報-3.

2. 納什均衡策略並非合理的。

在不知對手如何決策時，納什均衡策略是一個比較保守的極值點。但是當知道對手的策略時，納什均衡策略並不是最優的。比如，當知道對手採用的是抵賴這個策略，那麼最優的策略是抵賴，而非坦白。

3. 納什均衡策略並不唯一

在很多博弈問題中，納什均衡點並非唯一的。

根據博弈任務進行分類，可以將博弈分為：

1. 完全競爭（零和博弈）

2. 完全協作

3. 混合競爭與協作

本節更新到這裡，下一節我們講已知博弈矩陣，如何求解納什均衡點。再下一節會講，納什均衡如何應用到多智能體強化學習中。