Notes/机器学习/深度学习模型/08-强化学习/1-基础理论与博弈/1-博弈论.md

title, draft, tags

title	draft	tags
00-博弈论	false	博弈论 纳什均衡 数学基础 强化学习

博弈论基础

本笔记面向深度学习与强化学习科研人员，系统阐述博弈论的核心概念、数学基础与算法。 更新日期：2026-05-14

---

1. 博弈论基础概念

1.1 基本元素

定义 1.1（博弈） 一个博弈由三元组 G = (N, A, u) 构成：

• $N = {1, 2, \ldots, n}$：玩家集合
• $A = A_1 \times A_2 \times \cdots \times A_n$：策略空间，其中 A_i 为玩家 i 的可行策略集
• $u = (u_1, u_2, \ldots, u_n)$：收益函数，其中 u_i : A \rightarrow \mathbb{R} 为玩家 i 的效用函数

定义 1.2（正常形博弈） 当博弈描述为玩家同时选择策略时，称为正常形博弈（Normal Form Game），其收益矩阵为：

u_i(a_1, a_2, \ldots, a_n) \quad \forall i \in N, \forall a_i \in A_i

1.2 扩展形博弈

定义 1.3（扩展形博弈） 扩展形博弈（Extensive Form Game）通过博弈树描述时序决策：

\Gamma = (H, Z, A, P, I, u)

其中：

• $H$：非终止节点集合（决策节点）
• $Z$：终止节点集合（终点）
• $A$：所有可行行动集合
• $P: H \rightarrow N \cup {c}$：玩家函数，将每个节点分配给某玩家或 chance（随机事件）
• $I = {I_1, I_2, \ldots, I_n}$：信息分割，其中 I_i 为玩家 i 的信息集
• $u_i: Z \rightarrow \mathbb{R}$：玩家 i 在终点 z \in Z 的收益

完美回忆（Perfect Recall） 若玩家在博弈过程中始终记得其历史决策，则称该博弈满足完美回忆条件：

h, h' \in I_i \implies \text{历史完全一致}

1.3 最优响应与效用

定义 1.4（最优响应） 给定其他玩家的策略 $a_{-i}^*$，玩家 i 的最优响应为：

BR_i(a_{-i}^*) = \arg\max_{a_i \in A_i} u_i(a_i, a_{-i}^*)

定义 1.5（严格优势） 策略 a_i 严格优于策略 $a_i'$，若对 $\forall a_{-i} \in A_{-i}$：

u_i(a_i, a_{-i}) > u_i(a_i', a_{-i})

---

2. 纳什均衡（Nash Equilibrium）

2.1 纳什均衡的定义

定义 2.1（纯策略纳什均衡） 策略组合 a^* = (a_1^*, \ldots, a_n^*) 构成纳什均衡，当且仅当 $\forall i \in N, \forall a_i \in A_i$：

u_i(a_i^*, a_{-i}^*) \geq u_i(a_i, a_{-i}^*)

等价表述：a_i^* 是对 a_{-i}^* 的最优响应，即 $a_i^* \in BR_i(a_{-i}^*)$。

2.2 混合策略纳什均衡

定义 2.2（混合策略） 玩家 i 的混合策略 \sigma_i 是其纯策略空间 A_i 上的概率分布：

\sigma_i(a_i) \geq 0, \quad \sum_{a_i \in A_i} \sigma_i(a_i) = 1

定义 2.3（混合策略纳什均衡） 混合策略组合 \sigma^* = (\sigma_1^*, \ldots, \sigma_n^*) 构成纳什均衡，当且仅当 $\forall i, \forall a_i \in A_i$：

u_i(\sigma_i^*, \sigma_{-i}^*) \geq u_i(a_i, \sigma_{-i}^*)

其中 $u_i(\sigma_i, \sigma_{-i}) = \sum_{a_i, a_{-i}} \sigma_i(a_i) \sigma_{-i}(a_{-i}) u_i(a_i, a_{-i})$。

2.3 纳什均衡的存在性证明

定理 2.1（纳什存在定理） 任意有限玩家、有限策略的正常形博弈至少存在一个混合策略纳什均衡。

证明（Brouwer 不动点定理）：

构造策略组合空间 $\Delta = \Delta_1 \times \cdots \times \Delta_n$，其中 \Delta_i 为玩家 i 的混合策略单纯形。

对每个玩家 i 定义响应函数 $f_i: \Delta_{-i} \rightarrow \Delta_i$：

f_i(\sigma_{-i})(a_i) = \frac{\max(0, u_i(a_i, \sigma_{-i}) - u_i(\sigma_i, \sigma_{-i}))}{\sum_{a_i' \in A_i} \max(0, u_i(a_i', \sigma_{-i}) - u_i(\sigma_i, \sigma_{-i}))}

其中 u_i(\sigma_i, \sigma_{-i}) 为当前策略下的期望收益。

该映射 F: \Delta \rightarrow \Delta 连续（收益函数的线性组合）。由于 \Delta 为紧凸集，Brouwer 不动点定理确保存在 \sigma^* 使得 $F(\sigma^) = \sigma^$。

验证不动点条件：对任何 a_i 若 $u_i(a_i, \sigma_{-i}^) > u_i(\sigma_i^, \sigma_{-i}^)$，则 $f_i(\sigma_{-i}^)(a_i) > 0$；若 $u_i(a_i, \sigma_{-i}^) < u_i(\sigma_i^, \sigma_{-i}^)$，则 $f_i(\sigma_{-i}^)(a_i) = 0$。故不动点即为纳什均衡。\square

2.4 纳什均衡的唯一性与稳定性

定义 2.4（NE 的唯一性） 博弈可能有多个纳什均衡，需通过稳定性分析筛选。

定义 2.5（渐进稳定） 考虑最佳响应动态的离散系统：

\sigma_i^{t+1} = BR_i(\sigma_{-i}^t)

若某 NE 周围的雅可比矩阵特征值模小于 1，则该 NE 局部渐进稳定。

---

3. 零和博弈（Zero-Sum Game）

3.1 基本定义

定义 3.1（零和博弈） 双人零和博弈满足 $u_1 + u_2 = 0$，可记为收益矩阵 $A$（玩家 1 的收益）：

u_1(p, q) = p^\top A q, \quad u_2(p, q) = -p^\top A q

其中 $p \in \Delta(A_1)$，q \in \Delta(A_2) 为双方的混合策略。

3.2 鞍点与 Minimax 定理

定义 3.2（鞍点） 策略对 (p^*, q^*) 为鞍点若满足：

p^{*\top} A q^* \leq p^{*\top} A q, \quad \forall p \in \Delta(A_1), \forall q \in \Delta(A_2)

定理 3.1（Minimax 定理） 有限双人零和博弈满足：

\max_{p \in \Delta(A_1)} \min_{q \in \Delta(A_2)} p^\top A q = \min_{q \in \Delta(A_2)} \max_{p \in \Delta(A_1)} p^\top A q = v^*

证明（线性规划对偶）：

玩家 1 的最小最大化问题：

\max_p \min_q p^\top A q = \max_p v \quad \text{s.t.} \quad [Ap]_j \geq v, \forall j

等价变换（消除常数 $v$）：

\min_{p, v} -v \quad \text{s.t.} \quad Ap \geq v \cdot \mathbf{1}, \quad \sum_i p_i = 1, \quad p \geq 0

其对偶问题为：

\max_{q, \lambda} \lambda \quad \text{s.t.} \quad A^\top q \leq \lambda \cdot \mathbf{1}, \quad \sum_j q_j = 1, \quad q \geq 0

这恰对应玩家 2 的最大化最小化问题 $\min_q \max_p p^\top A q$。由线性规划对偶理论，强对偶性成立。\square

3.3 鞍点不等式推导

引理 3.1（鞍点不等式） 若 (p^*, q^*) 为鞍点，则：

p^\top A q^* \leq p^{*\top} A q^* \leq p^{*\top} A q, \quad \forall p, \forall q

由鞍点性质可直接导出 minimax 等式：

\max_p p^\top A q^* \leq p^{*\top} A q^* \leq \min_q p^{*\top} A q

由于 \max_p \min_q p^\top A q \geq \min_q p^\top A q 对任意 p, q 成立，故等式两边相等。

3.4 策略空间的线性规划

双人零和博弈的求解可转化为线性规划：

玩家 1 的 LP（最大化最小收益）：

\max_{p, v} v \quad \text{s.t.} \quad \sum_i p_i a_{ij} \geq v, \quad \forall j, \quad \sum_i p_i = 1, \quad p_i \geq 0

玩家 2 的 LP（最小化最大收益）：

\min_{q, u} u \quad \text{s.t.} \quad \sum_j a_{ij} q_j \leq u, \quad \forall i, \quad \sum_j q_j = 1, \quad q_j \geq 0

---

4. 纳什均衡的计算

4.1 优势消去（IESDS）

定义 4.1（严格劣势策略） 策略 a_i 对玩家 i 严格劣于 $a_i'$，若 $\forall a_{-i}$：

u_i(a_i, a_{-i}) < u_i(a_i', a_{-i})

算法：迭代优势消去（IESDS）

while 存在劣势策略 do
    消去所有严格劣势策略
end while

性质：若博弈存在唯一纳什均衡，IESDS 必收敛至该均衡；但若有多个均衡，IESDS 可能消去部分均衡。

4.2 虚拟对弈（Fictitious Play）

定义 4.2（虚拟对弈） 经典虚拟对弈中，玩家假设对手以历史平均频率选择策略：

\sigma_{-i}^t = \frac{1}{t} \sum_{\tau=1}^t a_{-i}^{\tau}

玩家 i 以最优响应更新策略：

a_i^{t+1} \in BR_i(\sigma_{-i}^t)

收敛性：针对特定博弈类（如零和博弈）可证伪，但一般博弈不一定收敛。

4.3 Lemke-Howson 算法

算法 4.1（Lemke-Howson） 适用于双人有限博弈的均衡求解：

1. 选择初始失衡玩家 k 和扰动参数 \lambda
2. 构造辅助线性规划问题
3. 沿着可行方向 pivot 直到满足均衡条件

该算法在最坏情况下指数复杂度，但在实践中对结构化博弈效率较高。

4.4 梯度下降法（Gradient Play）

定义 4.3（梯度Play） 将纳什均衡视为不动点，用梯度下降求解：

\sigma^{t+1} = \Pi_{\Delta}\left(\sigma^t - \eta \cdot \nabla u(\sigma^t)\right)

其中 \Pi_{\Delta} 为欧几里得投影到策略单纯形。

收敛性：对于单阶梯度动态，一般博弈无收敛保证；但对零和博弈可证某些条件下收敛。

---

5. 扩展形博弈与子博弈完美均衡

5.1 扩展形博弈的表示

扩展形博弈通过博弈树 T = (V, E) 描述，其中：

• $V = V_h \cup V_z$（决策节点与终点节点）
• 每个决策节点 v \in V_h 关联玩家 P(v) \in N
• 边 (v, v', a) 表示行动 a

5.2 信息集与完美回忆

定义 5.1（信息集） 同一玩家不可区分的节点集合：

I_i = \{h \in H : P(h) = i\}

完美回忆要求：玩家在信息集中各节点的可达历史完全相同。

5.3 子博弈完美均衡（SP E）

定义 5.2（子博弈） 从节点 h 开始的子博弈包含所有以 h 为根的可达终止节点。

定义 5.3（子博弈完美均衡） 策略组合 \sigma^* 在每个子博弈上均构成纳什均衡。

定理 5.1（SPE 存在性） 任意有限扩展形博弈（完美回忆）存在至少一个子博弈完美均衡。

5.4 逆向归纳法（Backward Induction）

算法 5.1（逆向归纳）

从终止节点逆向计算：
for 节点 h 从深到浅 do
    若 h 为终点：计算效用
    若 h 为玩家节点：
        选择使该玩家收益最大的行动
end for

性质：有限完美信息博弈中，逆向归纳产生唯一 SPE。

---

6. CFR（Counterfactual Regret Minimization）

6.1 虚拟对局后悔值

定义 6.1（Counterfactual Regret） 在时刻 t 玩家 i 选择行动 a 的虚拟后悔值：

R_i^t(a) = \frac{1}{N} \sum_{k=1}^N I(h \in I_i) [u_i(\sigma^k) - u_i(\sigma^k_{-I_i}, a)]

其中：

• $N$：总采样序列数
• $I(h \in I_i)$：指示函数，判断历史 h 是否在玩家 i 的信息集 I_i 中
• $\sigma^k_{-I_i}, a$：在第 k 次序列中，在 I_i 处替换为行动 a 的策略

6.2 CFR 算法

算法 6.1（CFR 迭代）

对每次迭代 $t$：

1. 基于当前策略 \sigma^t 生成采样序列
2. 对每个信息集 I_i 和行动 $a$，计算后悔值 R_i^t(a)
3. 更新策略：

\sigma^{t+1}_i(a) = \frac{\max(0, R_i^{+,t}(a))}{\sum_{a' \in A(I_i)} \max(0, R_i^{+,t}(a'))}

其中 R_i^{+,t}(a) = \max(R_i^t(a), 0) 为正部分。

6.3 CFR+ 算法

CFR+ 通过以下改进提升收敛速度：

1. 线性加权平均：对历史策略加权平均，近期权重更高

\bar{\sigma}^T = \frac{\sum_{t=1}^T (2t-1) \sigma^t}{\sum_{t=1}^T (2t-1)}

2. 替代遗憾值：R_i^{T}(a) = \max(R_i^{T-1}(a) + R_i^{t}(a), 0)

6.4 外部后悔值与收敛性

定义 6.2（外部后悔值）：

R_T(\sigma) = \frac{1}{T} \max_{\sigma^*} \sum_{t=1}^T [u(\sigma^*, \sigma_{-i}^t) - u(\sigma^t, \sigma_{-i}^t)]

定理 6.1（CFR 收敛性） 若每个玩家的外部后悔值 $R_T \rightarrow 0$，则平均策略序列收倥至纳什均衡。

6.5 蒙特卡洛 CFR（MCCFR）

算法 6.2（MCCFR）

• ** outcome sampling**：对每条轨迹只采样一个后继
• ** chance sampling**：对 chance 节点按先验概率采样
• 外部采样：只跟踪单方的信息集更新

---

7. 均值场博弈（Mean Field Game）

7.1 大量智能体的近似

均值场博弈处理 N \rightarrow \infty 的多智能体系统，其中单个智能体的影响可忽略。

定义 7.1（均值场近似） 智能体 i 视其他智能体为统计分布 $\mu \in \mathcal{P}(\Theta)$：

\mu(\theta) = \lim_{N \to \infty} \frac{1}{N-1} \sum_{j \neq i} \delta_{\theta_j}

7.2 配对均值场近似

智能体间相互作用通过配对势能 V(x, x') 建模：

U_i(x, \mu) = \int V(x, y) d\mu(y)

7.3 连续统中的博弈均衡

定义 7.2（Mean Field Equilibrium） 策略 \pi^* 与分布 \mu^* 满足自洽条件：

\mu^* = \Phi(\pi^*, \mu^*)

其中 \Phi 为策略诱导的分布映射。

---

8. 多人博弈中的深度学习

8.1 神经网络在博弈论中的应用

神经网络用于近似：

• 价值函数：V_{\theta}(s, \mu) \approx \mathbb{E}_{a \sim \pi(\cdot|s, \mu)}[Q(s, a)]
• 策略函数：\pi_{\theta}(a|s, \mu)

8.2 PSRO（Policy Space Response Oracles）

算法 8.1（PSRO）

1. 初始化策略基 \Pi = \{\pi_0\} 和相应收益矩阵
2. 迭代：
   • 对每个 $\pi_i \in \Pi$，计算最佳响应 BR(\pi_{-i})
   • 扩展策略基 \Pi \leftarrow \Pi \cup \{BR\}
   • 重新计算 NE

8.3 博弈论的深度学习应用

对抗训练：GAN 中的二人零和博弈，收敛至纳什均衡

多智能体强化学习：

• 独立 Q-learning 的不稳定性源于非平稳环境
• 解决方法：均值场近似、注意力机制、中心化训练去中心化执行

---

参考文献

1. Osborne, M.J. and Rubinstein, A., 1994. A course in game theory. MIT press.
2. Nash, J., 1950. Equilibrium points in n-person games. PNAS, 36(1), pp.48-49.
3. Von Neumann, J. and Morgenstern, O., 1944. Theory of games and economic behavior.
4. Zinkevich, M. et al., 2007. Regret minimization in games with incomplete information. NIPS.
5. Lasry, J.M. and Lions, P.L., 2007. Mean field games. Japanese Journal of Mathematics.
6. Lanctot, M. et al., 2017. OpenSpiel: A framework for reinforcement learning in games. arXiv.