Counterfactual Regret

概述

反事实遗憾（Counterfactual Regret，CFR）是博弈论与人工智能领域的重要概念，由 Martin Zinkevich 等人于 2008 年提出，用于解决不完全信息博弈中的策略优化问题。在德州扑克等游戏中，CFR 是虚拟遗憾最小化算法（Regret Minimization）的核心组成部分，被广泛应用于构建高水平 AI，例如 Libratus 和 Pluribus。

原理

反事实遗憾衡量在某个信息集（玩家当前已知的全部信息）下，如果玩家选择其他行动而非实际选择的行动，所能获得的收益差异。具体而言，对于每个信息集和每个可能的行动，算法计算该行动的“反事实遗憾值”：假设玩家在所有其他决策点都按照既定策略行动，仅在该节点改变行动，则遗憾值等于新行动带来的预期收益减去当前策略的预期收益。

每次对局结束后，算法根据实际结果更新每个信息集下各行动的遗憾值。随着迭代次数增加，遗憾值逐步累积并用于调整策略：选择遗憾值较低的（即后悔程度较小的）行动概率更高。最终，当所有信息集下的平均遗憾值趋近于零时，策略收敛到纳什均衡。

在德州扑克中的应用

CFR 特别适合于德州扑克等包含隐藏信息、随机性和多轮决策的博弈。由于完整博弈树过于庞大，实际应用中常采用抽象技术（如状态聚类、行动抽象）降低复杂度。通过数千亿次自对弈模拟，CFR 可生成接近最优的策略，并在单挑无限注德州扑克中击败人类顶尖选手。

与相关术语的关系

• 虚拟遗憾最小化（RM）：CFR 是 RM 在多博弈者、非完全信息场景下的扩展，核心思想相同。
• 纳什均衡：CFR 的目标是找到混合策略纳什均衡，即任何一方无法通过单方面改变策略获益。
• 策略迭代：CFR 通过反复迭代更新策略，不同于传统值迭代或策略梯度方法。