反事實後悔(CFR)與Bellman方程(持續更新)

大佬的論文是用來膜拜的！！

之前我寫過一篇強化學習中的策略與價值，裡面對價值迭代做了一個比較清晰的梳理，這裡就不做展開，不過對策略梯度的梳理不夠，特別是確定性策略梯度和AC框架。策略梯度理論除了SPG、DPG、AC三個重要的基礎，還有一個就是信賴域系方法，PPO演算法就是屬於策略梯度的這一分支。本文主要梳理前三種方法，信賴域系方法後續會有專文來分析。

bellman方程

價值迭代和策略迭代是動態規劃演算法，迭代的目標是bellman最優方程。價值函式（動作-價值函式）和策略梯度都是從bellman方程衍生而來。而CFR的思路與bellman方程的思路略有差異，前者是從博弈的角度來考慮問題，博弈樹考慮了博弈的各方，它的狀態節點是參與博弈各方當前的共有狀態（加上只有自己能看到的資訊）；後者是從單個智慧體與環境的互動來考慮問題，在計算價值或收益的時候，還做了貼現處理。

1、博弈論初探

記：納什均衡之所以偉大，是因為它的平凡，它之所以平凡是因為它普遍存在於普羅大眾的日常生活中。

1。1、基礎概念

這篇文章對上面那本書的總結比較好，但是在最後他並沒有考慮到多智慧體隨機博弈收斂到不同均衡點的情況，Alphastar的群體博弈可能會出現這種情況，下面會做一個補充。

1.1.1、矩陣博弈

1.1.2、兩個智慧體的矩陣博弈的均衡博弈

1.1.3、線性規劃求解雙智慧體零和博弈

1.1.4、幾個博弈概念

劃重點：第i個智慧體的價值函式是

$V_{i}(s, \pi_{1}^{\ast}, \cdot\cdot\cdot\pi_{i}, \cdot\cdot\cdot, \pi_{n}^{\ast})$

，其中 #FormatImgID_28# 是agent i 在狀態s下的最優策略，也就是Best Response，其處於納什均衡點的最大收益是 #FormatImgID_29# ，博弈雖然可能存在多個納什均衡點，但是在不同均衡點的收益都相等。在多智慧體博弈或多智慧體自博弈或者智慧體與人博弈的場景中，每個智慧體都有屬於自己的價值函式 #FormatImgID_30# ，它們各自獨立選擇一個納什均衡，並不需要選擇相同的平衡點。如果博弈遊戲中有多個納什均衡點，則智慧體可以選擇不同的點；由於每個納什均衡點都具有相同的值，所以這是完全可以接受的。在強化學習中判斷智慧體 i 是否收斂到納什均衡的標準是價值函式 #FormatImgID_31# 是否收斂。

2、反事實後悔最小化（CFR）

2.1、CFR演算法

第一步：用後悔值更新策略機率。

第二步：使用新策略更新平均策略組合。

第三步：使用新策略組合，計算反事實值。

第四步：使用新反事實值計算後悔值。

第一、二、三、四步一直迴圈，直至收斂到納什均衡點。

2.2、符號解釋

這篇文章對CFR的基本概念做了比較好的解釋，為了節省時間，直接拿來用了。

2.2.1、擴充套件式博弈

圖1、德州撲克中的一個狀態-動作序列

2.2.2、策略

圖2、幾種π機率的計算方法

2.2.3、收益值與反事實值

在收益值的計算上，CFR博弈樹非葉子節點收益的計算依賴葉子節點的收益，並且沒有考慮對未來收益的貼現。下面公式中的h表示的是當前階段博弈各方所處的全域性狀態，也就是說它不獨屬於任意一方。

反事實這個概念可以理解為agent p在當前博弈階段面臨的一個客觀事實，也就是說在其他agent的策略的客觀基礎上，從agent p的主觀角度，它應該如何生成應對策略。除了CFR，COMA模型中也借鑑了反事實思想。

對於反事實值

$v_{p}^{\sigma}(h)$

，我們可以這樣來考慮：

$\pi^{\sigma}(h)=\pi_{p}^{\sigma}(h)*\pi_{-p}^{\sigma}(h)$

，這個公式表明，當前的博弈局面h是agent p和除p之外的agent共同作用的結果，

$\pi_{-p}^{\sigma}(h)$

表示除p之外的agent對於局面h的機率貢獻，也就是除p之外的agent到達h的機率。從公式

$u_{p}^{\sigma}(h)=\pi_{p}^{\sigma}(h)*v_{p}^{\sigma}(h)$

可以看到，

$\pi_{p}^{\sigma}(h)$

與

$v_{p}^{\sigma}(h)$

成反比關係，這裡反事實值

$v_{p}^{\sigma}(h)$

表示的是在當前博弈局面h下，除p之外的agent對agent p獲取收益

$u_{p}^{\sigma}(h)$

所施加的影響值，如果

$\pi_{p}^{\sigma}(h)$

越小，那麼就意味著其他智慧體在局面h下對p施加的不利影響越大，也就意味著p獲取到收益

$u_{p}^{\sigma}(h)$

的機率越小；反之，

$\pi_{p}^{\sigma}(h)$

越大，那麼其他智慧體對於p獲取到收益

$u_{p}^{\sigma}(h)$

的影響越小。如果反事實值

$v_{p}^{\sigma}(h)$

越大，那麼agent p就要進行反思，並後悔應該在這裡提高動作機率，並使用後悔值更新策略機率，後悔值越大相應的更新機率應該越大，具體見上文CFR演算法第一步。

這其實也表明了一個重要思想：在零和博弈中，對agent p而言，其他agent想要實現收益最大化，而這就必然要讓p的收益最小化，p面對這種客觀事實局面，在其他agent想要讓它收益最小化的前提下，必然實現自身收益的最大化。每個agent在每階段對其他agent的策略做出最佳響應，以獲得最大收益，那麼最終這場博弈會趨向於納什均衡。

2.2.4、最佳響應BR(Best Response)