「博弈論」這個詞可能對于一些僅僅緻力于機器學習前沿算法的人并不算熟悉。其實，有意無意的，博弈論的思想一直存在于很多機器學習的探索過程中，不管是經典的 SVM，還是大火的 GAN，這些模型的背後都有博弈論的影子。
近年來，随着機器學習的發展，機器學習要應用的場景越來越複雜，開始有人有意識的将博弈論與機器學習聯系起來。總的來說，博弈論在機器學習研究中的作用主要有三個：(1) 解釋機器學習模型的原理與思想；(2) 建立合适的學習政策；(3) 預測人類參與者（人機互動時）的行為。基于這三個方面，本文首先解釋了博弈論的基本概念及其如何解釋機器學習中的一些模型，然後介紹了博弈論在 Multi-Agent Reinforcement Learning（MARL）中的應用，最後介紹了博弈論與機器學習結合所産生的新分支——博弈機器學習。 博弈論是什麼
嚴格來說，博弈論主要是研究理性決策者之間的沖突與合作的數學模型。這個定義有些抽象，沒接觸過博弈論的人也很難很直覺的從「博弈論」這個名字知曉博弈論到底是什麼。這個詞可以拆開來看，「博弈」這個詞很多時候是出現在圍棋、戰争等場景中，再看一下博弈論的英文——「Game Theory」，那麼博弈論就很好了解了，就是一個研究怎麼合理玩好這個世界中存在的各種遊戲的學科。
具體來說，博弈論涉及到的「遊戲」主要可以根據 5 個特征分類：合作性（遊戲中人是否可以與他人聯合）、對稱性（玩家們是否有相同的目标）、資訊完整性（能否知道其他玩家的決策與動向）、同步性（玩家的動作是同時進行的，還是一個玩家的動作是在另一個玩家的動作之後的）以及零和性（一個玩家得分是否會導緻另外一個玩家減分）。以撞球（斯諾克）為例，這個遊戲是無法與他人合作的（非合作性），玩家們具有相同的目标（将桌上的球按一定規則擊入袋中，對稱性），玩家可以知道對面玩家的動向（資訊完整性），每個玩家需要在另一個玩家擊球失敗後開始自己的擊球（非同步性），因為紅球數是一定的，從某種程度上來說，一個玩家的得分會導緻另外一個玩家得分期望的減少，故而本遊戲是零和遊戲。基于這些分類，不同的方法論可以應用在不同的遊戲中，比如納什均衡（後文會解釋）在對稱性遊戲中更容易達到。
要注意的是，這裡的「遊戲」不一定隻指傳統意義上的遊戲，如下圖所示，它包括很多方面。很多問題都可以被看作是「遊戲」，這在本質上跟人工智能就是互通的了——AI 的終極目的就是讓電腦也能玩轉人類正在玩或者将要開始玩的一些遊戲。看一下下圖，博弈論所研究的領域與 AI 正在研究的領域何其相似，再回憶在群眾間打響 AI 名聲的 AlphaGo，也正是從遊戲着手，去學習人類的思考模式。是以當博弈論遇上機器學習，一些很奇妙的「化學反應」就會發生——解釋了一些數學模型的意義、出現了一些新的探索方向，等等。
博弈論與機器學習
很多在博弈論中出現的概念都被引用到了機器學習中，納什均衡（Nash Equilibrium, NE）就是其中一個。這是指的遊戲中的一個狀态，在這個狀态下，在其他玩家決策不變的情況下，如果任何一個玩家改變當下的決策，都無法得到更多的好處。換句話說，如果所有人都把自己的決策告訴其他玩家，其他玩家都不會變更自己的方案，這時候就達到了 NE。這極其類似于機器學習中的最優解。對于 NE，最經典的例子就是囚徒困境 (prisoner's dilemma)，如下圖所示。這個例子中，有兩個犯人被抓住了，這兩個犯人都被單獨提審，無法提前串通。在這種情況下
- 如果兩個囚犯中的一個供認另一個犯了罪，則供認出對方的人将被釋放，而另一個将被判處 10 年徒刑；
- 如果他們倆都不認罪，他們每個人被判一年監禁；
- 如果他們都承認，他們都将被判處 5 年徒刑。
在這個例子中，很容易就可以看出當兩個人都供出對方時達到了本遊戲的 NE。在這個狀态下，任意一個人改變自己的決策，就會面臨 10 年的監禁。
傳統的機器學習大多被看作優化問題，我們需要做的就是找到一個能夠搜尋最優解的算法。但是，機器學習與傳統優化問題的不同在于，我們希望通過機器學習得到的模型不會過度拟合資料，這樣就可以在尚未遇到的情況中也有很好的表現。也就是說，我們希望這些機器對未知數做出預測，這種要求我們一般稱之為泛化，這也是為什麼深度學習中的許多工程需要對優化問題附加限制的原因，這些限制有些文章稱之為「先驗」，在優化問題中則被稱為正則化。
這些正則化來自哪裡，我們如何選擇良好的正則化？我們如何處理不完全的資訊？這個時候，博弈論的思想就很重要了。泛化有時被稱為「結構風險最小化」。換句話說，我們就是不知道驗證集資料的情況下，降低訓練集風險的政策來建構機制來處理泛化。
在機器學習，尤其是分類方法中，很多大家熟悉的傳統方法都有博弈論的影子。SVM 就可以看作一個雙人的零和博弈，這種優化類的機器學習算法就可以看作是尋找一個 NE（每個類選擇一個超平面），在這個平面存在的情況下，可以最好的完成分類任務；線性回歸可以看作是一個非合作博弈，每個類都希望自己的損失最低；Adaboost 則可以看作是利用合作、非同步博弈論進行線上學習。
當然，展現博弈最明顯的算法就是 GAN 中的對抗學習了。先回顧一下 GAN 的結構，GAN 有兩個部分——一個生成器，一個判别器（如下圖所示）。生成器盡自己最大的努力去欺騙判别器，而判别器則是盡自己最大的努力判别圖檔是否是生成器生成的。在提出 GAN 的原始論文中有說明過這是一個 MinMax 遊戲，而最終的目标就是找到這個遊戲的 NE，但論文中并沒有明顯的提及這個遊戲的分類，是以 GAN 雖然有博弈論的影子，但是沒有徹底的繼承博弈論的優點，是以 GAN 很難訓練，而且訓練出的結果也很難判斷是否是鞍點。是以現在也有一些研究開始聚焦如何把 GAN 具象成一個更具體的遊戲，進而使得結果更好。比如在 GANGs: Generative Adversarial Network Games 中，作者就提出了一種 GAN game，明确的将 GAN 定義為零和遊戲。
這個過程非常類似于一個雙人遊戲。在這個遊戲中，我們的玩家（兩個模型）互相挑戰，第一個僞造樣本以混淆另一個玩家，而第二個建立者則試圖在識别正确的樣本方面變得越來越好，并反複重複此遊戲，并在每次疊代中更新學習參數，以減少總損失（有更多的經驗）。而最終訓練的目的是找到這個遊戲的 NE，這個時候兩個模型都已經最大程度上的完成了自己的任務，無法再進行改進了，任何參數的更新都會導緻自己損失的增加。
博弈論與強化學習——Multi-Agent Reinforcement Learning（MARL）
強化學習（Reinforcement Learning，RL）旨在通過與環境（可以是虛拟的也可以是真實的）的互動來使智能體（我們的「模型」）學習。RL 一開始是根據 Markov 過程提出的，我們讓智能體處于不确定的固定環境中，并試圖通過獎勵/懲罰機制來學習到一個最優政策。在單智能體的情況下，這種方法被證明是收斂的。
但是，如果是将多個智能體放置在同一環境中（多智能體強化學習，MARL），情況就複雜多了。假設我們正在試着用智能車來改善城市的交通情況。這時每輛車的決策都會影響其他車的決策與表現，比如智能車與智能車之間很可能會發生沖突，因為可能對于兩輛智能車而言，沿着某條路線行駛都是最友善的（獲得最多的獎勵）。
MARL分類
上面例子中，智能體之間傾向于競争關系。實際生活中，智能體之間的關系還可能是合作關系，或半合作半競争（mixed）。智能體間複雜的關系和智能體之間的影響讓 MARL 變得極其複雜。這個時候，博弈論的引入就會讓模組化變得輕松很多，在這種情況下，我們可以把智能車看作不同的玩家，而此時 NE 則代表不同智能車之間的平衡點。具體來說，MARL 可以分成三種「遊戲」：
-
靜态遊戲 (static games)：
靜态遊戲中，智能體無法知道其他智能體所做的決策，故而我們可以認為所有智能體的決策是同步，互相之間不受影響。
-
動态遊戲 (stage games)：
動态遊戲中有很多不同的階段，每個階段都是一個遊戲（stage game），上面提到的囚徒困境就可以看作其中一個階段的遊戲。
-
重複遊戲 (repeated games)：
如果一個 MARL 系統中各個階段的遊戲都很相似，那麼就可以被稱為重複遊戲。
基于博弈論的 RL 算法（Alphastar）
當下，博弈論除了理論上的作用外，基于博弈論提出的 RL 算法也在大放異彩。比如掌控了星際争霸的 AlphaStar 的開發過程中就充滿了博弈論的影子。星際争霸作為一個遊戲，就像剪刀石頭布一樣，很難得到一個單一的最佳方案，是永遠在博弈中的，要對當下的已有的政策進行學習，并選擇最好的那個。
AlphaStar 所參考的算法就是 Double Oracle Algorithm（DO Algo），這個算法将目标定為尋找當下 stage game 的 NE。DO Algo 的原理如下圖所示。它使用深度神經網絡進行函數逼近，疊代計算子遊戲的收益矩陣（Gt）。這個子遊戲就是上文提到的 stage games。在每個時間 t 處（每個 stage game），都會計算出符合 NE 的回應（σ），并得到最優政策（π），然後添加新的政策來擴充 Gt 為 Gt + 1，繼續重複上述過程。
以下圖為例，開始兩個玩家的收益矩陣 Gt 很像剛剛舉的囚徒案例，π代表各個玩家可以采取的政策，初始的 Gt 中各個玩家隻有兩個政策（比如兩個玩家各有兩個進攻計劃，佯攻和攻擊分礦），然後通過求 NE 響應來獲得兩個玩家在這個場景下能得到的最佳相應 P1，P2。這時，兩個玩家都發現，對現有的進攻計劃都不是很有信心，希望拖入後期，于是玩家繼續從自己的政策庫中選擇政策加入到 Gt 中（比如開分礦），進而得到 Gt+1，然後此時對應的 P1，P2 又被計算出來。總的來說就是在當下的 stage game 中計算 NE 響應，再根據情況擴充遊戲，再計算，直到你對結果變得有信心為止。
當然，星際争霸遠比我現在說的要複雜的多，政策要千變萬化的多，比如假若你真的選擇拖後期，如何選擇後期機關（是巢蟲領主、雷獸、航母、風暴戰艦、雷神或者戰列巡航艦這種很肉又很強力的機關，還是飛蛇、高階聖堂武士或者幽靈這樣輔助性的施法機關），如何跟對方交換中期機關才不導緻自己損失過大，這些都是要考慮的問題。是以如果直接将 DO Algo 應用在星際争霸這樣的遊戲中，在 DO Algo 中使用動作作為政策，那政策會有很多。
是以，在 AlphaStar 所應用的核心算法文獻 A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning 中，他們就将 DO Algo 進行了泛化（Policy-Space Response Oracles，PSRO），政策将不再隻能是單個動作，也可以是戰術或者其它的 meta-solver，同時提出了 Deep Cognitive Hierarchies（DCH）來解決遊戲中政策規模的問題。
其中 PSRO 如下圖所示，該算法首先抽樣一個初始政策并計算效用函數，并初始化元政策（記錄政策分布的函數），元遊戲開始于一個單一的政策，并在每個 epoch 中添加政策（也就是算法名字中的 Oracle），這些政策将盡可能地響應其他玩家的元政策。請注意，該算法存在計算量問題，因為對于每個 epoch、每個 player 和 episode，都需要基于每個 player 計算新的政策 pi 和元政策。不是計算确切的最佳響應，而是使用 RL 計算近似的最佳響應。
強化學習的每一個 step 都可能需要很長時間才能收斂到好結果，而有些已經學過的東西可能會在後面的學習過程中再學一遍，為了解決 PSRO 中計算量過大的問題，這篇論文又提出了 DHC 算法以使得 PSRO 并行化。具體來說，就是不再挨個 epoch 進行訓練，而是預先确定 K 個 level（代替 epoch），并開啟 NK 個線程（N 為玩家數），每個線程訓練一個玩家的一個 oracle，并将結果定期儲存到中央存儲器中。每個線程還會有目前 level 或者更低 level 的政策資訊（類似後面的 epoch 知曉前面 epoch 的訓練結果）。由此可見，DHC 犧牲了準确性（減少了 epoch 數）以換取其可擴充性（減少計算量）。
可以看出，這個算法是博弈論與 RL 算法密切結合的産物，它已經被應用在 AlphaStar 并獲得了巨大的成功，由此可見，博弈論所代表的 RL 學習政策是很值得信賴的。
運算量的簡化
當系統有大量的智能體的時候，模組化可能會變得非常困難，因為智能體數量的增加會使不同智能體間互動方式的數量成倍增加。在這中情況下，博弈論中提出的的 Mean Field Games 為 MARL 模型模組化提供了目前來說最好的方案。MFG 中會假定各個玩家的活動都是相似的，是以如果一個 RL 場景可以被轉換成 MFG 場景，那麼一開始就可以假設所有智能體都具有相似的獎勵方程，這樣就可以大大降低 MARL 模型的複雜性。
很多論文已經在研究這一點，其中在 Reinforcement Learning for Mean Field Game 中，就探究了如何 action coupled 的随機博弈環境中尋找 Mean Field Equilibrium(MFE)。假設其他因素的影響可以通過行為均值的分布來确定，而且所有的智能體都知道行動的分布，并利用近期最佳響應來選擇最優的遺忘政策。文中提出了一種基于後驗抽樣的均值場（Mean Field）博弈強化學習方法，其中每個智能體從之前的轉移矩陣中抽取一個轉移機率。文中證明了政策分布和行為分布分别收斂于最優的遺忘政策和極限分布，并共同構成了一個 MFE。
博弈機器學習
在博弈論中還存在一個概念叫做逆博弈論（Inverse Game Theory）。博弈論旨在了解遊戲的動态，以優化其玩家可能獲得的結果。相反的，逆博弈論旨在根據玩家的政策和目标來設計遊戲。逆博弈論在多智能體 AI 以及人機互動 AI 中都很有用處。
2013 年國際人工智能大會（IJCAI）上，微軟亞洲研究院劉鐵岩博士所在的團隊首次提出了「博弈機器學習」的概念，這是将博弈論與機器學習結合而産生的新分支，即以博弈論的思想對人的動态政策進行顯式模組化，利用行為模型和決策模型相結合的方式來解決這一類難題。有了博弈機器學習，我們的算法就可以比人多想一步、甚至多想很多步，提前預料對方會做出什麼樣的反應，進而在與之博弈的時候占得先機。
劉鐵岩博士在介紹博弈機器學習的文章中寫道：「真實的人類行為既非随機、也非完全理性和對立——事實上人類（智能體）的行為往往會有一定規律可循。與前面提到的這些技術不同，博弈機器學習就是利用了這樣一個簡單的常識。無論是人與人之間的互動，還是人與計算機之間的互動都是可以被模組化的，這樣我們就能夠知道這些人為的資料是如何産生的，進而在學習的過程中對此加以利用，進而在和人類博弈的過程中占得先機。」
由此可見，博弈機器學習可以在廣告競價、社交媒體、衆包管理、交通疏導等很多領域中被應用。一旦我們在機器學習的過程中，對人的行為模型做出學習和描述，就可以知道我們的算法機制發生改變之後，人們的行為會怎麼去改變，進而知道在很長時間以後當人的行為趨于穩定（均衡态），我們取得的結果是好是壞。
在 A Game-theoretic Machine Learning Approach for Revenue Maximization in Sponsored Search 中，劉鐵岩博士就是用博弈機器學習在廣告競價任務上得到了很好的效果。從下面這張圖中可以看出，這個算法使用了雙層優化架構來學習拍賣機制。
具體的算法如下圖所示，首先從曆史資料中學習一個馬爾可夫模型，以描述廣告商如何響應拍賣機制以更改其出價，然後對于任何給定的拍賣機制，都使用學習的模型來預測其相應的未來出價順序。然後就可以通過對預測出價序列進行經驗收益最大化來學習拍賣機制。結果表明，當預測時間接近無窮大時，收益将收斂，并且遺傳算法可以有效地優化該收益。文中的實驗表明，與幾種基準相比，本算法能夠産生更有效的拍賣機制。
總結
「什麼才是人工智能？想要解決這個問題，首先需要為「智能」提出一個定義。如果說過去對于個體智能的研究為計算機賦予了智商（IQ）的話，那麼社會智能則對應着人工智能的情商（EQ）。」
最後還是引用劉鐵岩博士的這句話作為結尾，博弈論的引入讓智能體在過去與環境打交道的基礎上又學會了如何與其他智能體打交道，如何與人打交道。同樣的，博弈論作為研究各種遊戲、人、社會、經濟等的理論，它的思想幾乎無處不在，不僅僅在那些明明白白提出結合博弈論的算法中，一些常見的算法中也常常藏着博弈論思想的影子。或許博弈論也是聯系機器學習走向人和社會的一個橋梁。