動機
雙人零和博弈有極小極大值,而無遺憾策略可以逼近最優策略。在一般的多人博弈中,並不存在統一的共同值,也沒有單一的對手。然而,只要每位參與者相對於任何固定行動的遺憾都很小,博弈過程的聯合經驗分佈就滿足一個有用的均衡條件。
由此得到的對象稱為粗相關均衡。一位中介者抽取一個聯合行動組合,並私下向每位參與者推薦一個行動。沒有參與者能夠透過事先承諾某個固定的替代行動而獲得顯著的好處。中介者可以在各參與者的推薦之間引入相關性;所得結果並不自動是納什(Nash)均衡,也不自動抵禦依賴於推薦內容的偏離。
定義與定理
定義 2.2.1
(粗相關均衡)
共有 位參與者。參與者 擁有非空有限行動集 ,並且對每個行動組合有收益 。若對每位參與者 以及每個固定的替代行動 ,聯合分佈 滿足
則稱 為 -粗相關均衡(-coarse correlated equilibrium)。
該替代行動可以依賴於已知的分佈,但不能依賴於實際得到的推薦。這裏 表示其餘所有參與者的行動。
定理 2.2.2
(完全資訊無遺憾構造)
對任意 ,下述同時進行的乘法權重過程能為每個收益在 內的有限博弈構造出一個 -粗相關均衡。它是 個乘積分佈的均勻混合,其中
為正整數,對數取自然對數。若 ,則一輪即可。
定理 2.2.3
(完全資訊遺憾界)
對 個行動、任意損失向量序列 以及 ,取 ,, 的指數權重算法對每個固定行動 滿足
損失向量可以在看到當前分佈之後才選定;序列一旦固定,該不等式是確定性的。我們假設指數權重與期望均採用精確實數運算。有限精度與抽樣的保證需要另行分析。
證明遺憾界
證明
(單一勢函數界住每個固定行動)
令 。對 與 ,初等不等式 給出
對 使用 並對各輪求和,得到
對任意固定行動 ,其最終權重為 ,因此 至少等於該值。由於 ,比較對數形式的下界與上界並整理,即證得所示遺憾不等式。證明中沒有用到各輪之間的任何獨立性。
證明透視
一個勢函數控制所有固定偏離
總權重從上方控制學習者累積的期望損失,而任何單一行動的權重則從下方控制同一個總權重。比較這兩個界便得到針對該固定行動的保證;這一代數推導對每個行動同時成立。
從無遺憾到聯合分佈
證明
(對各輪的乘積分佈取平均)
在第 輪,每位參與者在 上有一個指數權重分佈 。對每個可能的行動 ,透過對其他參與者當前的乘積分佈取平均,定義其完全資訊損失:
這些損失落在 內。每位參與者用自己的損失向量更新所有行動的權重。這是一個關於精確實數分佈的確定性過程;定義更新時無需對行動進行抽樣。令 為各輪聯合乘積分佈 的均勻混合。
對參與者 ,在第 輪乘積分佈下實際承受的期望損失為 。對任意固定的 應用遺憾定理,並把損失換回收益,得到
取 以及整數 。這樣兩項都至多為 ,從而對每位參與者與每個固定偏離證明了粗相關不等式。當 時,任何參與者都沒有替代行動,唯一的行動組合在一輪內即為精確均衡。
中介者揭示的資訊
從 中抽樣的方法是:先均勻地選取一個輪次指標,再從該輪的分佈中獨立地為每位參與者抽取行動。給每位參與者的推薦就是其抽到的行動。粗相關保證比較的是在收到推薦之前選定的固定替代行動;它並不保證參與者無法透過讓偏離依賴於其推薦或隱藏的輪次指標而獲益。
反例模式
乘積分佈的混合不等於其邊際分佈的乘積
以相等概率選取 或 。該分佈是兩個乘積分佈的混合,但其兩個邊際分佈都是均勻分佈,而它們的乘積還會給 與 賦予正概率。把聯合混合替換為平均邊際分佈的乘積會改變該分佈,證明並不支持這樣的替換。
的定義保持了各輪混合的完整性。儘管完整的聯合表可能很大,它仍可由 個參與者分佈列表緊湊地描述。若中介者公開輪次指標,參與者便可依據這一額外資訊選擇替代行動;上述固定行動的界並不自動涵蓋這種更強的偏離。
例題詳解
例題 2.2.4
(單一行動的博弈)
若每位參與者恰有一個行動,則唯一的聯合組合沒有任何不同的單邊替代行動。其點質量分佈是精確的粗相關均衡。特別處理 的情形,避免了對數界出現零輪的詮釋問題。
例題 2.2.5
(相關的協調結果)
兩位參與者在其二元行動一致時獲得收益一,否則為零。對 與 各賦予二分之一概率的分佈使每位參與者的期望收益為一。沒有任何固定偏離能超過一,因此它是精確的粗相關均衡。其推薦之間是相關的。
例題 2.2.6
(輪數預算)
設每位參與者至多有四個行動且 ,取 與 。由於 ,定理適用。顯式遺憾界為每輪 。
例題 2.2.7
(固定的損失序列)
對兩個行動與兩輪,設第一輪損失為 ,第二輪損失為 。儘管最佳行動在兩輪之間改變,遺憾界對任一固定行動仍然適用。它並不是把學習者與可在看到每個損失向量後自由切換的比較者相比。
常見錯誤
常見錯誤
(逐輪更換替代行動)
應用所示遺憾不等式時,每一輪必須使用同一個固定偏離。能看到抽到的輪次或推薦的參與者,可以在不同情形下選擇不同的偏離;那是更強的基準。粗相關均衡的定義恰好與固定行動的比較相匹配。
單輪之內的乘積分佈假設各參與者在給定該輪的條件下獨立抽樣。跨輪的混合可以產生相關性。先取乘積再平均,與先平均再取乘積,是不同的運算,如反例所示。
常見錯誤
(近似粗相關均衡不是納什均衡)
該證明構造的是近似粗相關均衡,不一定是納什均衡,也不一定是依賴於推薦的相關均衡。在雙人零和博弈中,可透過額外的論證提取近似極小極大策略;任意的多人收益則需要各自的結論。
計算與表示
對於顯式列出的標準型博弈,每一輪的損失向量可透過對收益表與當前乘積概率求和來計算。每輪所需的算術運算次數是該顯式表規模的多項式,而所述輪數是 與最大行動數對數的多項式。若博弈僅由簡潔電路或諭示給出,計算這些期望的成本可能不同。
定理假設指數與概率均採用精確實數運算。因此它給出的是算術運算次數與精確的數學分佈,而不是經過認證的多項式位元時間實現。有限精度的實現必須界定累積誤差及其對每個偏離不等式的影響。抽樣版本的博弈還必須考慮抽樣誤差;這兩個問題都沒有被隱含在確定性的期望收益證明之中。
參與者人數可以任意,但顯式收益表對每個聯合行動組合與每位參與者各有一項。當每位參與者都有多個行動時,關於該表規模為多項式的運算次數,仍可能是參與者人數的指數。這是輸入表示方式上的區別,並不與有限輪數的界相矛盾。
展開收益比較
對固定的參與者與輪次,把損失的定義代入學習者的期望損失。由於在給定該輪的條件下,參與者自身的混合行動與其他參與者互相獨立,結果等於一減去完整乘積分佈下的期望收益。固定替代行動的損失則是一減去僅替換該參與者分量後所得的期望收益。相減時兩個一互相抵消。對所得不等式在各輪上取平均,恰好就是 下期望的定義。
同時更新並不產生循環選擇。每一輪開始時,所有分佈都由前幾輪的權重所確定。該過程先由這些當前分佈計算全部期望損失向量,再更新所有權重以進入下一輪。損失向量可能透過其他參與者的選擇而依賴於該參與者當前的分佈,但勢函數的證明對每個一經給定的向量都成立。它不要求有獨立的對手,也不要求各輪損失互相獨立。
作為極限的精確存在性
有限輪數的構造同時給出精確粗相關均衡的存在性論證。取趨於零的序列 ,並對每個取值構造相應的分佈 。所有聯合分佈都位於有限維概率單純形中,該單純形是緊緻的,因此存在子列收斂到某個分佈 。對每位參與者與每個固定的替代行動,粗相關不等式關於聯合分佈是線性且連續的。沿該子列取極限即消去了誤差,表明 是精確的。
這一論證證明至少存在一個極限點滿足要求。它並不說明整個分佈序列收斂,也不提供有限時間內的精確有理表示。近似構造及其有限輪數預算仍是上文所建立的算法性結論。
小型博弈中的偏離檢驗
在二元協調的例子中,承諾永遠出零的參與者,在對方推薦為零時獲得收益一,在對方推薦為一時獲得收益零。因此其偏離的期望收益為二分之一,而遵從推薦的收益為一。永遠出一的情形計算相同。只需檢驗這兩個固定行動即可,因為任何固定混合偏離的收益都是它們收益的凸組合。
最後這一觀察可以推廣:要驗證一個粗相關均衡能抵禦所有固定的混合偏離,只需檢驗每個固定純行動。混合偏離的收益是相應純偏離收益的加權平均,不可能超過其中最大的純偏離收益。這一有限的不等式列表,正是遺憾界所控制的那一列。
概念視角幾何
均衡構成一個多面體
固定一個博弈,並以 表示聯合行動組合上的概率分佈單純形。每個純替代行動 對 貢獻一個線性不等式,即上述條件。因此 -粗相關均衡就是 與 個閉半空間的交集:一個凸多面體,而由上文的構造可知它非空。均衡的混合仍是均衡;在顯式收益表上尋找一個均衡,就是一個線性可行性問題。
總結
指數權重法界定了每位參與者相對於每個固定行動的遺憾。把該界應用於期望的完全資訊損失,並對各輪的乘積分佈取平均,便得到一個近似粗相關均衡。中介者所掌握的資訊、聯合混合以及精確運算的假設,都是該保證的一部分。
練習
快速檢查
(為甚麼遺憾定理允許損失向量依賴於當前的行動分佈?)
看勢函數證明在哪一步用到 。
解答 · 答案
勢不等式對 中每個已實現的損失向量都成立,並不使用其與當前分佈的獨立性。對這些逐點不等式求和即得該界。
快速檢查
(若所有參與者都只有一個行動,為甚麼一輪就能產生精確均衡?)
參與者還能考慮哪個替代行動?
解答 · 答案
不存在不同的單邊行動,因此對唯一的組合,每個粗相關不等式都以等號成立。
快速檢查
(在二元協調的例子中,對角混合下任一參與者的期望收益是多少?)
分別計算支撐集中兩個行動組合的收益。
解答 · 答案
為一:支撐集中的兩個組合行動均一致,收益均為一。
快速檢查
(為甚麼固定偏離的保證並不自動涵蓋依賴於抽到的推薦的偏離?)
比較事先固定的替代行動與看到建議後才選擇的替代行動。
解答 · 答案
這樣的偏離可以在不同的推薦情形下選擇不同的替代行動。定理只與在所有輪次和推薦下都固定不變的單一行動作比較。