在介紹CFR+算法之前，我們首先介紹一下基礎概念。

在CFR+算法中，counterfactual utility被定義為以下形式：

然后在regret的基礎上，CFR+算法定義了一個regretlike value，注意在這里CFR+算法的regret為一個累加值，而CFR算法定義的regret為平均值，需要乘以1t：

,where

另外，在CFR+算法中，最后輸出的平均策略為以下形式：

然后CFR+算法的bound為：

bound證明

在對Lemma 1的證明過程中，我們可以得出以下結論：

我們得到了

，之后我們可以從Lemma 1可知 ，于是，我們得出以下結論：

然后我們引入Lemma 3， Lemma 3很容易證明，可以直接看出：

然后證明Lemma 4：

Lemma 4的證明就是將原有的序列擴充為1，2，3，。。。，T，這樣的話等于有（T^2+T）/2的過程，然后我們再引入Lemma 3，這樣的就可以求出新的bound：

然后我們由CFR算法的定義可知

于是可以得到新的

結論

從CFR算法和CFR+算法的證明過程中我們可以獲取以下證明過程范式。

首先定義average overall regret：

因為直接優化average overall regret困難，然后我們定義immediate counterfactual regret，并且最優化他，但是優化這個困難，于是我們優化他的擬合項counterfactual regret，使其小于

，就可以得到 。記住這樣的話，counterfactual regret必須除t作為一個平均值，而CFR+算法直接將其作為了累加項。

在CFR+算法中，我們的counterfactual regret沒有除t。但是我們得到了一個結論：

然后我們計算累加的counterfactual regret：

為了求出上面公式的bound，我們一般需要Lemma 3，而在LCFR中，需要在Lemma 3的基礎上進行進一步的擴展。

然后我們證明

，于是得到 。

總結

以上是生活随笔為你收集整理的算法证明_CFR+算法证明过程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。