?borealisai

導語

論文 "The Mechanics of n-Player Differentiable Games" 榮獲機器學習頂會 ICML 2018 最佳論文提名獎，它創新性地提出一種可以在普通博弈中尋找穩定不動點的演算法——辛梯度調節演算法（SGA），該演算法與近期提出的在GANs中尋找穩定不動點的演算法有同樣優秀的表現，並且適用於更普遍的博弈問題並保證收斂性。

從多模型優化問題到多玩家博弈

近年來，機器學習的進展很大程度上依賴於梯度下降的使用，梯度下降使得一個目標最終可以收斂到某個局部最小值，從而優化模型參數。然而越來越多的模型需要優化多個目標，如生成對抗網路、分層強化學習、合成梯度等。

生成對抗網路：generative adversarial networks

分層強化學習：hierarchical reinforcement learning合成梯度：synthetic gradients

思考這類問題的正確方法是——將它們解釋為博弈論問題，解決這些問題就是要找到每個目標的納什均衡而不是局部最小值。

目前在博弈中使用基於梯度的方法並沒有得到很好的研究。

梯度下降等無悔演算法能使博弈中的目標收斂到一個近似的相關均衡（coarse correlated equilibria）,但是其動力學計算不能收斂到納什均衡（Nash equilibria），甚至不能穩定下來。已有的用於找到穩定不動點的演算法也局限於兩個玩家的博弈，還不能應用到多玩家的普通博弈中。

隨著對抗性以及多目標的模型架構的發展，這方面的研究將變得越來越重要。

超越GAN的辛梯度條件演算法（SGA）

在這篇論文中，作者提出了一種新的方法來理解與控制普通博弈中的動力學，其關鍵成果是把二階動力學分解為兩個部分。

第一部分與潛博弈（potential games）有關，它隨著隱式函數梯度下降而減小；第二部分與哈密爾頓博弈（Hamiltonian games）有關，這是一類新的遵循守恆定律的博弈，和經典機械系統中的守恆定律類似。

這種分解啟發作者提出了辛梯度調節演算法（Symplectic Gradient Adjustment， SGA），這是一種可以在普通博弈中尋找穩定不動點的新演算法。大量基礎性實驗表明，SGA與近期提出的在GANs中尋找穩定不動點的演算法有同樣優秀的表現，並且適用於更普遍的博弈問題並保證收斂性。

在GANs中尋找穩定不動點的演算法包括梯度下降（gradient descent）、樂觀鏡像下降（optimistic mirror descent, OMD）、同時梯度下降（simultaneous gradient descent）等等，相比之下，SGA 更具競爭力，不僅能夠快速找到穩定不動點，還能夠應用到多玩家博弈問題。

圖1

由圖1可知，梯度下降對學習率的選擇很敏感，學習率為0.01時緩慢收斂，學習率為0.032時緩慢發散，學習率為0.1時快速發散。相比之下，SGA能夠更快、更魯棒地收斂，只有在學習率為0.1時，起始階段稍微偏離穩定不動點，但很快就調整過來，趨向穩定不動點收斂。

圖2

由圖2可知，雖然OMD的峰值表現比SGA好，但是在大部分學習率下，SGA更快收斂。而OMD在學習率為[0.3, 1.2]之外不收斂。SGA允許我們設置更高的學習率，從而使目標更快收斂。

圖3

圖3展示了經過2000、4000、6000、8000次迭代後的結果，可以看到，同時梯度下降會出現模式崩潰和模式跳躍，而沒有進行對齊的SGA平滑收斂，有進行對齊的SGA更快收斂。可見，SGA在性能上優於同時梯度下降，並且對齊調節演算法能使目標更快收斂。

如何在普通博弈中找到穩定不動點？

這篇論文提出的方法是將博弈動力學的二階結構分解為潛博弈和哈密爾頓博弈，然後使用辛梯度調節來找到穩定不動點。

在論文中，作者首先對博弈問題進行數學定義，聲明不限制參數集（例如，概率單純形），不要求損失是凸的，玩家甚至可以通過神經網路進行交互，例如GANs。然後作者指出多玩家博弈的損失不是單一函數，若使用梯度下降，其動力學計算不能收斂到一個不動點。

零和博弈?gnHHbB

作者接著討論了著名的零和雙矩陣博弈（zero-sum bimatrix game）問題，指明同時進行多個目標梯度下降的動力學可以使用哈密爾頓等式重新定義。這樣做的好處是，哈密爾頓函數上的梯度下降可以收斂到納什均衡。

雙矩陣博弈：在博弈論中，雙矩陣博弈是兩個玩家同步進行的博弈，每個玩家持有有限個可能動作。這樣博弈能夠用兩個矩陣（1號玩家的收益矩陣和2號玩家的收益矩陣）來描述，因此被稱為雙矩陣博弈。

零和博弈：零和博弈是博弈論的一個概念，屬非合作博弈。指參與博弈的各方，在嚴格競爭下，一方的收益必然意味著另一方的損失，博弈各方的收益和損失相加總和永遠為"零"，雙方不存在合作的可能。

納什均衡：任何一方採取的策略都是對其餘所有方採取策略組合下的最佳對策；當所有其他人都不改變策略時，為了讓自己的收益最大，任何一方都不會（或者無法）改變自己的策略，這個時候的策略組合就是一個納什均衡。在數學領域中，納什均衡在博弈函數中就是鞍點。

納什均衡?wikipedia

然後作者對Helmholtz分解定理進行推廣，推導出任何博弈的Hessian矩陣都可以分解為對稱矩陣和反對稱矩陣。

前者就是眾所周知的潛博弈，是梯度下降收斂的博弈，已經得到深入的研究，很容易解決。後者被作者稱為哈密爾頓博弈，同樣很容易解決。

對於雙矩陣問題，哈密爾頓博弈等價於零和博弈；對於非線性的損失或者多玩家參與的問題，哈密爾頓博弈與零和博弈有所區別。作者同時證明了哈密爾頓博弈遵循守恆定律，這使我們能夠通過對守恆量進行梯度下降來解決哈密爾頓博弈。

Helmholtz分解定理：空間區域上的任意矢量場，如果它的散度、旋度和邊界條件已知，則該矢量場可以表示為一個無散矢量場和一個無旋矢量場的疊加。

潛博弈：在博弈論中，如果所有參與者改變策略的激勵可以使用單個全局函數來表達，則這種博弈被稱為潛博弈，這個全局函數被稱為潛函數。這個概念起源於Dov Monderer和Lloyd Shapley在1996年的一篇論文中（Monderer, Dov; Shapley, Lloyd (1996). "Potential Games". Games and Economic Behavior. 14: 124–143. doi:10.1006/game.1996.0044）。

哈密爾頓博弈：本文作者首次給出定義，並命名，其概念與1992 Lu等人提出的哈密爾頓遊戲不同。哈密爾頓矩陣是反對稱矩陣，玩家之間的所有成對相互作用都是零和的。

一般來說，哈密爾頓博弈與零和博弈相關但不同，作者在文中給出三個具體例子來幫助理解哈密頓博弈的含義：既是零和博弈又是哈密頓博弈的實例、是零和博弈但不是哈密頓博弈的實例、是哈密頓博弈但不是零和博弈的實例。在某些條件下，哈密爾頓守恆量的梯度下降法能找到納什均衡。

作者接著證明了穩定不動點是局部納什平衡。因此設計一種能夠找到穩定不動點的演算法，就能使目標的動力學計算收斂到納什均衡。

SGA演算法

於是作者提出辛梯度調節演算法，這是一種基於梯度的方法，能夠在普通博弈中找到穩定不動點。SGA滿足一些基本要求，它不僅兼容原有的動力學，還能保證在潛博弈和哈密爾頓博弈中找到穩定均衡，甚至避開不穩定均衡。

對於所有博弈，正確選擇調節的符號是非常重要的，因為它決定了目標在穩定均衡和不穩定均衡附近的行為。因此作者討論了如何設置調節的符號能使得目標收斂到穩定不動點。作者還發現，對齊調節演算法允許我們設置更高的學習率，從而使目標更快、更魯棒地收斂。

應用：解決多玩家博弈問題

梯度下降能夠找到局部極小值，但對於優化多個互相影響的目標來說，我們不需要找到局部極小值，而是要找到穩定不動點，因此關鍵是要理解和控制互相影響的損失之間的動力學。並且，提出的解決方法不僅僅是針對兩個玩家的對抗性博弈問題，而是能夠應用到處理多玩家問題。

廣義Helmholtz分解為博弈動力學提供了強大的新視角，這種分析方式與玩家數量無關，它是損失的同時梯度與二階項的對稱和反對稱矩陣之間的相互作用，能指導演算法設計並控制梯度調整的動力學。

辛梯度調節演算法是Helmholtz分解的直接應用，這不是找到穩定不動點的唯一或最佳方法。深入理解潛分量和哈密爾頓分量之間的相互作用有助於找到更有效的演算法，特別是不使用Hessian矢量積的純一階方法。

論文最後提出一個哲學觀點，這篇論文的目標是找到穩定不動點（例如，這種狀態下的GANs能產生令人滿意的樣本）,而不關心博弈中玩家本身的損失。梯度調整可能導致玩家增加損失，犧牲自身利益，但這有利於收斂到穩定不動點，因此這是合理的。

作者：王佳純

論文下載：proceedings.mlr.press/v補充材料：proceedings.mlr.press/v

推薦閱讀

遊戲博弈論：小遊戲背後的納什均衡

神經網路與圖靈機的複雜度博弈

網路科學如何打開深度學習的黑箱？

作為複雜網路的深度學習系統

加入集智，一起複雜！

推薦課程

campus.swarma.org/gpac= (二維碼自動識別)

PC端：campus.swarma.org/gpac=

集智俱樂部QQ群｜877391004

商務合作及投稿轉載｜[email protected]

◆ ◆ ◆

搜索公眾號：集智俱樂部

加入「沒有圍牆的研究所」


推薦閱讀：
相关文章