--- title: 04-CFR-反事实后悔值最小化 draft: false tags: - CFR - 反事实后悔值 - 博弈论 - 强化学习 --- 如果说 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)**。 1. **初始化：** 将所有信息集下的所有动作的累积后悔值 $R$ 和累积策略 $S$ 设为 0。 2. **迭代：** 每一个 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)$。 3. **最终输出：** 训练结束后的策略不是最后一次迭代的策略 $\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**。