不完美信息博弈

开源实现

智能体和不完全信息下的序贯决策通常被建模为一个广泛的博弈。反事实后悔最小化（CFR）是计算大型、零和、不完全信息博弈纳什均衡的一种有效方法。在扑克领域，CFR已经被证明是有效的，特别是当使用涉及机会-结果抽样的特定领域的增强时。蒙特卡罗反事实后悔最小化（MCCFR）展示了MCCFR执行与CFR相同的期望后悔更新。然后，MCCFR介绍了两种抽样方案：结果抽样和外部抽样，证明了两种抽样方案都具有高概率的有界总体后悔。因此，他们可以计算一个近似平衡使用自我发挥。最后，我们证明了原CFR算法在遗憾上的一个新的更紧的界，并将这个新的界与MCCFR的界联系起来。虽然基于样本的算法需要更多的迭代，但它们的每次迭代成本较低，可以在各种博弈中显著加快收敛速度。

[1] Lanctot, Marc et al. “Monte Carlo Sampling for Regret Minimization in Extensive Games.” NIPS (2009)

external_sampling_mccfr.zip