算法证明_CFR+算法证明过程

在介绍CFR&＃43;算法之前&＃xff0c;我们首先介绍一下基础概念。

在CFR&＃43;算法中&＃xff0c;counterfactual utility被定义为以下形式&＃xff1a;

然后在regret的基础上&＃xff0c;CFR&＃43;算法定义了一个regretlike value&＃xff0c;注意在这里CFR&＃43;算法的regret为一个累加值&＃xff0c;而CFR算法定义的regret为平均值&＃xff0c;需要乘以1t&＃xff1a;

,where

另外&＃xff0c;在CFR&＃43;算法中&＃xff0c;最后输出的平均策略为以下形式&＃xff1a;

然后CFR&＃43;算法的bound为&＃xff1a;

bound证明

在对Lemma 1的证明过程中&＃xff0c;我们可以得出以下结论&＃xff1a;

我们得到了

&＃xff0c;之后我们可以从Lemma 1可知

&＃xff0c;于是&＃xff0c;我们得出以下结论&＃xff1a;

然后我们引入Lemma 3&＃xff0c; Lemma 3很容易证明&＃xff0c;可以直接看出&＃xff1a;

然后证明Lemma 4&＃xff1a;

Lemma 4的证明就是将原有的序列扩充为1&＃xff0c;2&＃xff0c;3&＃xff0c;。。。&＃xff0c;T&＃xff0c;这样的话等于有&＃xff08;T^2&＃43;T&＃xff09;/2的过程&＃xff0c;然后我们再引入Lemma 3&＃xff0c;这样的就可以求出新的bound&＃xff1a;

然后我们由CFR算法的定义可知

于是可以得到新的

结论

从CFR算法和CFR&＃43;算法的证明过程中我们可以获取以下证明过程范式。

首先定义average overall regret&＃xff1a;

因为直接优化average overall regret困难&＃xff0c;然后我们定义immediate counterfactual regret&＃xff0c;并且最优化他&＃xff0c;但是优化这个困难&＃xff0c;于是我们优化他的拟合项counterfactual regret&＃xff0c;使其小于

&＃xff0c;就可以得到

。记住这样的话&＃xff0c;counterfactual regret必须除t作为一个平均值&＃xff0c;而CFR&＃43;算法直接将其作为了累加项。

在CFR&＃43;算法中&＃xff0c;我们的counterfactual regret没有除t。但是我们得到了一个结论&＃xff1a;

然后我们计算累加的counterfactual regret&＃xff1a;

为了求出上面公式的bound&＃xff0c;我们一般需要Lemma 3&＃xff0c;而在LCFR中&＃xff0c;需要在Lemma 3的基础上进行进一步的扩展。

然后我们证明

&＃xff0c;于是得到

。