7.4 KiB
title, draft, tags
| title | draft | tags | ||||
|---|---|---|---|---|---|---|
| 04-CFR-反事实后悔值最小化 | false |
|
如果说 DQN 和 PPO 是处理单智能体或协同环境（如游戏、机器人控制）的利器，那么 CFR (Counterfactual Regret Minimization，反事实后悔值最小化) 则是处理非完美信息博弈（Imperfect Information Games），如德州扑克、博弈论决策的顶级方法。
CFR 并不直接使用深度学习的梯度上升，而是基于博弈论中的后悔值（Regret）概念进行迭代。
1. 核心背景：非完美信息博弈
在德州扑克中，你不知道对方的底牌，这被称为非完美信息。
-
信息集 (Information Set,
I)： 玩家根据自己看到的信息无法区分的一组游戏状态。例如，在你的视角下，对手所有可能的底牌组合构成一个信息集。 -
策略 (
\sigma)： 在信息集I下采取动作a的概率分布 $\sigma(I, a)$。
2. 数学基石：反事实后悔值 (Counterfactual Regret)
CFR 的核心在于：“如果我当时做了另一个决定，现在会怎样？” 这种对比产生的差值就是“后悔值”。
2.1 定义反事实价值 (Counterfactual Value)
定义 v_i(\sigma, h) 为玩家 i 在达到节点 h 后的期望收益。
反事实价值 $v_i(\sigma, I)$ 定义为：在玩家 i 努力达到信息集 $I$，而其他玩家遵循策略 \sigma 的前提下，达到 I 后的期望收益。
v_i(\sigma, I) = \sum_{h \in I} \pi_{-i}^\sigma(h) v_i(\sigma, h)
其中 \pi_{-i}^\sigma(h) 表示除了玩家 i 以外的所有玩家（包括自然随机因素）达到节点 h 的概率。
2.2 瞬时后悔值 (Immediate Regret)
在时间步 $t$，玩家 i 在信息集 I 下，由于没有采取动作 a 而产生的瞬时后悔值为：
r_t(I, a) = v_i(\sigma_t|_{I \to a}, I) - v_i(\sigma_t, I)
其中：
- $\sigma_t|_{I \to a}$：在信息集
I强制选择动作 $a$（其余决策不变）后，遍历博弈树计算出的反事实价值 - $v_i(\sigma_t, I)$：遵循当前策略
\sigma_t到达I后的期望收益
物理意义： 想象你在德州扑克中看到对手下注，此时如果你选择”跟注”能获得 5 分期望收益，而你的当前策略（跟注概率 30%）只给你带来 3 分期望收益，那么选择跟注的瞬时后悔值就是 $5 - 3 = 2$。正值表示”早知道选 a 就好了”。
2.3 累积后悔值 (Cumulative Regret)
这是 CFR 训练的核心指标：
R_T^i(I, a) = \sum_{t=1}^T r_t(I, a)
3. CFR 算法逻辑：后悔匹配 (Regret Matching)
CFR 的训练过程就是一个不断更新累积后悔值，并根据它调整策略的过程。
3.1 策略更新公式
在第 T+1 次迭代中，信息集 I 采取动作 a 的概率与该动作的正累积后悔值成正比：
\sigma_{T+1}(I, a) = \begin{cases} \frac{R_T^i(I, a)^+}{\sum_{a' \in A(I)} R_T^i(I, a')^+} & \text{if denominator} > 0 \\ \frac{1}{|A(I)|} & \text{otherwise} \end{cases}
其中 $x^+ = \max(0, x)$。
直觉： 哪种动作过去让你越后悔没选，下一次选它的概率就越大。
4. 训练全过程 (Training Flow)
CFR 是一个迭代算法，通过数万次甚至数亿次的自我博弈（Self-play）来逼近 纳什均衡 (Nash Equilibrium)。
-
初始化： 将所有信息集下的所有动作的累积后悔值
R和累积策略S设为 0。 -
迭代： 每一个 Epoch 进行以下操作：
-
深度优先搜索 (DFS)： 遍历博弈树。
-
计算收益： 到达叶子节点时返回实际收益。
-
回溯计算：
-
计算每个节点的反事实价值 $v_i(\sigma, I)$。
-
计算每个动作的瞬时后悔值 $r_t(I, a)$。
-
更新累积后悔值：$R_T^i(I, a) \leftarrow R_{T-1}^i(I, a) + r_t(I, a)$。
-
更新累积策略：$S_T(I, a) \leftarrow S_{T-1}(I, a) + \pi_i^\sigma(I) \cdot \sigma_t(I, a)$。
-
-
-
最终输出： 训练结束后的策略不是最后一次迭代的策略 $\sigma_T$，而是平均策略：
\bar{\sigma}_T(I, a) = \frac{S_T(I, a)}{\sum_{a'} S_T(I, a')}
5. 为什么 CFR 能成功？(数学保证)
5.1 后悔值下限保证
CFR 最著名的特性是：外部后悔值（External Regret）以 O(\sqrt{T}) 速度趋于零。
外部后悔值定义： 在 T 次迭代中，玩家选择策略 \sigma^t 而非最优固定策略 \sigma^* 的累积后悔：
R_T^{ext} = \frac{1}{T} \max_{\sigma^*} \sum_{t=1}^T \left[ u_i(\sigma^*, \sigma_{-i}^t) - u_i(\sigma^t, \sigma_{-i}^t) \right]
关键定理（后悔值下界）： 若玩家按后悔匹配规则更新策略，则：
R_T^{ext} \leq \frac{2 |A_{\max}|}{\sqrt{T}}
其中 |A_{\max}| 为最大信息集的动作数。这由黑利（Hoeffding）不等式推导出。
5.2 从外部后悔到纳什均衡
定理 5.1（folk theorem 推论）： 在双人零和博弈中，若所有玩家的外部后悔值 $R_T^{ext} \to 0$，则平均策略 \bar{\sigma}_T 收敛至 $\epsilon$-纳什均衡，其中 $\epsilon = \max_i R_T^{ext}$。
直觉解释： 外部后悔值衡量的是"如果我始终坚持最佳单一策略，能比现在多好多少"。当这个值趋近于零时，意味着没有任何单一策略能显著改善我的表现——这正是纳什均衡的定义：没有玩家能通过单方面改变策略而获益。
5.3 收敛速度分析
CFR 的收敛是次线性的（$O(1/\sqrt{T})$），这意味着：
- 前 100 次迭代：后悔值下降快
- 后 10000 次迭代：后悔值仍在缓慢下降，但收益改善微弱
- 工程实践中，德州扑克通常需要数百万次迭代才能达到人类高手水平
实际例子： 在双人无限注德州扑克中，使用 CFR+ 结合蒙特卡洛采样，Pluribus 在 8 天内训练完成，并在六人桌击败了人类顶尖选手。
6. 可能出现的问题与进阶方案
6.1 状态爆炸
对于像无限额德州扑克这样的游戏，状态空间是 $10^{161}$，无法遍历整个博弈树。
- 解决方案：Deep CFR。 用神经网络来拟合后悔值
R和策略 $\sigma$。这就是 Libratus 和 Pluribus 等击败人类顶尖高手的 AI 核心。
6.2 遍历效率低
标准的 CFR 每次迭代要走遍整棵树。
- 改进：MCCFR (Monte Carlo CFR)。 每次迭代只采样博弈树的一条或几条分支，极大地提高了处理大型博弈的速度。
6.3 负后悔值的处理
有些动作可能长期处于极度负后悔状态。
- 改进：CFR+。 将负后悔值直接截断为 0，并使用线性加权平均，收敛速度比原版 CFR 快得多。
7. 总结：DQN/PPO vs CFR
-
DQN/PPO： 适合动作与状态明确、非对抗或对抗性不强的环境。在非完美信息博弈（如德扑）中容易被对手针对，因为它不具备“博弈稳定性”。
-
CFR： 专为博弈设计。它追求的是“不可被击败性”（纳什均衡），无论对手怎么打，它都能保持最优。
下章预告：
既然已经聊到了博弈和策略优化，如果你对如何将深度学习与 CFR 结合感兴趣，我们可以深入探讨 Deep CFR 或者是将 PPO 用于多智能体竞争环境的 MAPPO。