1. 博弈论基础概念
1.1 基本元素
定义 1.1（博弈） 一个博弈由三元组
：玩家集合 ：策略空间，其中 为玩家 的可行策略集 ：收益函数，其中 为玩家 的效用函数
定义 1.2（正常形博弈） 当博弈描述为玩家同时选择策略时，称为正常形博弈（Normal Form Game），其收益矩阵为：
1.2 扩展形博弈
定义 1.3（扩展形博弈） 扩展形博弈（Extensive Form Game）通过博弈树描述时序决策：
其中：
：非终止节点集合（决策节点） ：终止节点集合（终点） ：所有可行行动集合 ：玩家函数，将每个节点分配给某玩家或 chance（随机事件） ：信息分割，其中 为玩家 的信息集 ：玩家 在终点 的收益
完美回忆（Perfect Recall） 若玩家在博弈过程中始终记得其历史决策，则称该博弈满足完美回忆条件。
2. 纳什均衡（Nash Equilibrium）
2.1 纳什均衡的定义
定义 2.1（纯策略纳什均衡） 策略组合
等价表述：
2.2 混合策略纳什均衡
定义 2.2（混合策略） 玩家
定义 2.3（混合策略纳什均衡） 混合策略组合
2.3 纳什均衡的存在性
定理 2.1（纳什存在定理） 任意有限玩家、有限策略的正常形博弈至少存在一个混合策略纳什均衡。
3. 零和博弈（Zero-Sum Game）
3.1 基本定义
定义 3.1（零和博弈） 双人零和博弈满足
3.2 鞍点与 Minimax 定理
定义 3.2（鞍点） 策略对
定理 3.1（Minimax 定理） 有限双人零和博弈满足：
4. CFR（Counterfactual Regret Minimization）
4.1 核心背景：非完美信息博弈
在德州扑克中，你不知道对方的底牌，这被称为非完美信息。
-
信息集 (Information Set,
)： 玩家根据自己看到的信息无法区分的一组游戏状态。 -
策略 (
)： 在信息集 下采取动作 的概率分布 。
4.2 数学基石：反事实后悔值 (Counterfactual Regret)
CFR 的核心在于：“如果我当时做了另一个决定，现在会怎样？” 这种对比产生的差值就是”后悔值”。
反事实价值
瞬时后悔值 (Immediate Regret)：
在时间步
4.3 CFR 算法逻辑：后悔匹配 (Regret Matching)
CFR 的训练过程就是一个不断更新累积后悔值，并根据它调整策略的过程。
在第
其中
4.4 CFR 收敛性
外部后悔值定义： 在
关键定理（后悔值下界）： 若玩家按后悔匹配规则更新策略，则：
定理 4.1（folk theorem 推论）： 在双人零和博弈中，若所有玩家的外部后悔值
5. CFR+ 算法
CFR+ 通过以下改进提升收敛速度：
- 线性加权平均：对历史策略加权平均，近期权重更高
- 替代遗憾值：
6. 蒙特卡洛 CFR（MCCFR）
算法（MCCFR）
- ** outcome sampling**：对每条轨迹只采样一个后继
- ** chance sampling**：对 chance 节点按先验概率采样
- 外部采样：只跟踪单方的信息集更新
7. 均值场博弈（Mean Field Game）
7.1 大量智能体的近似
均值场博弈处理
定义 7.1（均值场近似） 智能体
7.2 均值场博弈定义
定义 7.2（Mean Field Equilibrium） 策略
其中
8. PSRO（Policy Space Response Oracles）
算法 8.1（PSRO）
- 初始化策略基
和相应收益矩阵 - 迭代：
- 对每个
，计算最佳响应 - 扩展策略基
- 重新计算 NE
- 对每个
参考文献
- Osborne, M.J. and Rubinstein, A., 1994. A course in game theory. MIT press.
- Nash, J., 1950. Equilibrium points in n-person games. PNAS, 36(1), pp.48-49.
- Zinkevich, M. et al., 2007. Regret minimization in games with incomplete information. NIPS.
- Lanctot, M. et al., 2017. OpenSpiel: A framework for reinforcement learning in games. arXiv.