反事实遗憾

概述

反事实遗憾（Counterfactual Regret）是博弈论中用于求解纳什均衡的一种核心概念，尤其在德州扑克等不完美信息博弈中应用广泛。它由 Hart 和 Mas-Colell 提出，后经 Zinkevich 等人发展为反事实遗憾最小化（CFR）算法，成为 AI 攻克德州扑克的关键技术。

定义与计算

在博弈树中，每个信息集（即玩家无法区分的历史节点集合）上，反事实遗憾衡量的是：若玩家在该信息集上选择某个特定行动，相比于当前策略，其收益的期望差值。具体而言，对于信息集 I 和行动 a，反事实遗憾定义为：

R(I, a) = ∑{h ∈ I} π{-i}(h) * (u_i(h·a) - u_i(h))

其中 π_{-i}(h) 是除当前玩家外其他玩家到达节点 h 的概率（即反事实概率），u_i(h) 是当前策略下玩家 i 在节点 h 的期望收益，u_i(h·a) 是采取行动 a 后的期望收益。

在德州扑克中的应用

CFR 算法通过迭代计算每个信息集上每个行动的反事实遗憾，并据此更新策略：遗憾值越大的行动，在下一轮策略中被赋予更高的概率。经过足够多次迭代，平均策略收敛到纳什均衡。

• 典型示例：在翻牌圈，玩家可能对“下注”和“过牌”两个行动计算反事实遗憾。若“下注”的遗憾为正，说明当前策略下注不足，后续应增加下注频率。

意义与局限

反事实遗憾为不完美信息博弈提供了可计算的均衡求解方法，使 AI 能在德州扑克中达到超人类水平。但其计算复杂度高，需要大量采样或抽象来降低博弈树规模。此外，反事实遗憾本身是策略优化的工具，而非直接可观察的玩家行为。