175 lines
7.4 KiB
Markdown
175 lines
7.4 KiB
Markdown
---
|
||
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**。 |