强化学习 Chapter 7 - 强化学习与多智能体系统

首次发布: 2025-06-13

... 次访问

Theory

/

AI Basics

7.1 零和博弈#

零和博弈是博弈论中的一个重要概念，也是多智能体系统中的基础理论。在零和博弈中，参与者的利益完全对立，一方的收益正好等于其他方的损失总和，因此所有参与者的收益与损失的总和为零。

7.1.1 零和博弈的特点#

利益冲突：参与者之间存在完全的利益冲突，无合作可能
总和为零：所有参与者的收益之和必须等于零
保守策略：参与者倾向于采用最小化最大损失的策略
确定性：在完美信息的情况下，理论上可以找到最优策略

零和博弈的典型例子包括棋类游戏（如国际象棋、围棋）、扑克牌游戏等。在这些博弈中，一方的胜利必然意味着另一方的失败，双方的目标是最大化自己的收益，同时最小化对手的收益。

7.1.2 双人零和博弈#

双人零和博弈是指有两个玩家的博弈，其中一方的收益等于另一方的损失，即双方的收益总和为零。

基本概念#

玩家 (Players): 博弈中有两个玩家，通常称为玩家1和玩家2
策略集 (Strategy Sets): 每个玩家有一组可供选择的策略。玩家1的策略集记为 $S_1$ ，玩家2的策略集记为 $S_2$
收益 (Payoffs): 对于每一对策略组合 $(s_1, s_2)$ ，其中 $s_1 \in S_1, s_2 \in S_2$ ，玩家1获得收益 $u_1(s_1, s_2)$ ，玩家2获得收益 $u_2(s_1, s_2)$ 。在零和博弈中， $u_1(s_1, s_2) + u_2(s_1, s_2) = 0$ ，因此只需关注其中一个玩家的收益
收益矩阵 (Payoff Matrix): 假设玩家1有 $m$ 个纯策略，玩家2有 $n$ 个纯策略，则玩家1的收益可以用一个 $m \times n$ 的矩阵 $A$ 表示，其中 $a_{ij}$ 表示当玩家1选择策略 $i$ 而玩家2选择策略 $j$ 时玩家1的收益
混合策略 (Mixed Strategy): 玩家以特定概率分布选择纯策略的方案

策略函数表示#

在博弈论中，我们使用 $\pi(a|s)$ 来表示策略函数，它表示在状态 $s$ 下选择动作 $a$ 的概率。需要注意的是，符号 $\pi$ 在不同上下文中有不同的含义：

作为概率分布函数： $\pi(a|s)$ 表示在给定状态 $s$ 下选择特定动作 $a$ 的概率值
作为策略向量： $\pi$ 本身表示整个动作概率向量或策略，包含了所有可能动作的概率分布

例如，当玩家1采用混合策略 $\pi_1$ （一个 $m$ 维概率向量），玩家2采用混合策略 $\pi_2$ （一个 $n$ 维概率向量）时，玩家1的期望收益为：

u(\pi_1, \pi_2) = \sum_{i=1}^{m}\sum_{j=1}^{n}\pi_1(a_i|s) a_{ij} \pi_2(a_j|s) = \pi_1^T A \pi_2

这里, $\pi_1, \pi_2$ 既可以指动作概率分布本身，也可以指全部可选动作对应的概率值的向量，公式中的含义是后者。

7.1.3 纳什均衡#

纳什均衡是博弈论中的核心概念，由数学家约翰·纳什（John Nash）提出。在纳什均衡状态下，每个参与者都采用了最优策略，且在其他参与者策略不变的情况下，没有任何参与者能够通过单方面改变策略来获得更高的收益。

纳什均衡的特点#

稳定性：一旦达到纳什均衡，任何一方单独改变策略都不会获益
互相制约：每个参与者的策略是对其他参与者当前策略的最佳应对
非唯一性：一个博弈可能存在多个纳什均衡
非最优性：纳什均衡不一定是帕累托最优的

在双人零和博弈中，纳什均衡与最小最大策略紧密相关。当双方都采用最小最大策略时，他们正好处于纳什均衡状态。

纳什均衡的数学表示#

对于双人零和博弈，如果策略对 $(\pi_1^*, \pi_2^*)$ 满足：

对所有的 $\pi_1$ ， $(\pi_1^*)^\top A \pi_2^* \geq \pi_1^T A \pi_2^*$
对所有的 $\pi_2$ ， $(\pi_1^*)^\top A \pi_2^* \leq (\pi_1^*)^T A \pi_2$

则 $(\pi_1^*, \pi_2^*)$ 是一个纳什均衡。

这里 $\pi_1$ 和 $\pi_2$ 分别是玩家1和玩家2的混合策略向量， $A$ 是玩家1的收益矩阵。

最小最大定理 (Minimax Theorem)#

对于有限的双人零和博弈，有

\max_{\pi_1} \min_{\pi_2} \pi_1^\top A \pi_2 = \min_{\pi_2} \max_{\pi_1} \pi_1^\top A \pi_2 = v

其中 $v$ 称为博弈的值 (value)。存在最优混合策略向量 $\pi_1^*$ 和 $\pi_2^*$ ，使得：

对于玩家1：选择 $\pi_1^*$ 可以保证收益至少为 $v$ ，无论玩家2如何选择
对于玩家2：选择 $\pi_2^*$ 可以保证玩家1的收益不超过 $v$ ，即自己的损失不超过 $v$

这样的策略对 $(\pi_1^*, \pi_2^*)$ 构成博弈的纳什均衡 (Nash Equilibrium)，是双方的最佳应对策略。

7.2 Markov 博弈#

Markov博弈，也称为随机博弈（Stochastic Games），是对零和博弈的一个重要扩展，它将马尔可夫决策过程（MDP）的思想引入到多智能体博弈环境中。与静态的零和博弈不同，Markov博弈考虑了时间序列和状态转移的动态特性。

7.2.1 Markov 博弈的一般定义#

一般的多人Markov博弈可以用一个元组 $(N, S, \{A_i\}_{i \in N}, P, \{R_i\}_{i \in N})$ 来描述：

玩家集 $N$ ：博弈中的所有玩家， $|N| = n$
状态集 $S$ ：博弈可能处于的所有状态的集合
动作集 $\{A_i\}_{i \in N}$ ：每个玩家 $i$ 在每个状态下的可选动作集合
转移概率 $P$ ： $P(s'|s, \mathbf{a})$ 表示在状态 $s$ 下，当所有玩家选择联合动作 $\mathbf{a} = (a_1, ..., a_n)$ 时，转移到状态 $s'$ 的概率
奖励函数 $\{R_i\}_{i \in N}$ ： $R_i(s, \mathbf{a})$ 表示在状态 $s$ 下执行联合动作 $\mathbf{a}$ 时玩家 $i$ 获得的即时奖励

7.2.2 双人Markov博弈#

双人Markov博弈是Markov博弈的一个重要特例，其中只有两个玩家参与。它可以用一个五元组 $(S, A_1, A_2, P, R_1, R_2)$ 来描述：

状态集 $S$ ：博弈可能处于的所有状态的集合
动作集 $A_1, A_2$ ：玩家1和玩家2在每个状态下的可选动作集合
转移概率 $P$ ： $P(s'|s, a_1, a_2)$ 表示在状态 $s$ 下，当玩家1选择动作 $a_1$ 、玩家2选择动作 $a_2$ 时，转移到状态 $s'$ 的概率
奖励函数 $R_1, R_2$ ： $R_i(s, a_1, a_2)$ 表示在状态 $s$ 下执行联合动作 $(a_1, a_2)$ 时玩家 $i$ 获得的即时奖励

双人零和Markov博弈#

当双人Markov博弈满足零和条件，即 $R_1(s, a_1, a_2) + R_2(s, a_1, a_2) = 0$ 对所有状态和动作组合都成立时，就形成了双人零和Markov博弈。在这种情况下，只需要考虑一个玩家的奖励函数即可。

7.2.3 Markov博弈的特点#

动态性：博弈在时间序列上展开，每个时刻的决策都会影响未来的状态
状态依赖：玩家的策略不仅依赖于当前的博弈情况，还要考虑历史状态和未来可能的状态转移
马尔可夫性：下一状态只依赖于当前状态和当前动作，与历史无关
长期收益：玩家需要考虑折扣累积奖励，而非仅仅关注即时收益

在Markov博弈中，每个玩家的策略是一个映射 $\pi_i: S \times A_i \rightarrow [0,1]$ ，其中 $\pi_i(a_i|s)$ 表示在状态 $s$ 下选择动作 $a_i$ 的概率。玩家 $i$ 的目标是最大化期望累积折扣奖励

V_i^{\pi}(s) = \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^t R_i(s_t, \mathbf{a}_t) \mid s_0 = s\right]

其中 $\gamma \in [0,1)$ 是折扣因子， $\mathbf{a}_t$ 是第 $t$ 时刻的联合动作。

7.2.4 与经典博弈论的联系#

Markov博弈是经典博弈论在动态环境下的自然扩展。当状态集只包含一个状态时，Markov博弈就退化为经典的静态博弈。同时，纳什均衡的概念也可以扩展到Markov博弈中，形成马尔可夫完美纳什均衡的概念，要求在每个状态下，玩家的策略都构成该状态子博弈的纳什均衡。

7.3 Minimax Q-Learning#

Minimax Q-Learning是专门为双人零和Markov博弈设计的强化学习算法，它将经典的Q-Learning扩展到多智能体对抗环境中。

7.3.1 算法作用与目标#

求解问题#

Minimax Q-Learning主要用于求解双人零和Markov博弈问题，即

两个智能体在动态环境中进行对抗
一方的收益等于另一方的损失（零和性质）
环境状态按马尔可夫性质转移
智能体需要在不完全信息下学习最优策略

算法目标#

学习最优Q函数：通过与环境交互，学习状态-动作对的价值
无模型学习：无需预先知道环境的转移概率和奖励函数

可以证明，算法得到的最优策略最终会收敛到Markov完美纳什均衡策略

7.3.2 算法核心思想#

Minimax Q-Learning的基本思想基于以下几个关键原理

状态分解：将整个Markov博弈分解为各个状态上的独立子博弈
最小最大原则：在每个状态下应用最小最大定理求解局部最优策略
时序差分学习：结合当前奖励和未来状态价值来更新Q函数
策略提取：从学习到的Q函数中通过线性规划提取最优混合策略

7.3.3 数学公式#

Q函数更新规则#

Q(s, a_1, a_2) \leftarrow Q(s, a_1, a_2) + \alpha [\mathcal{R}(s, a_1, a_2) + \gamma V(s') - Q(s, a_1, a_2)]

其中：

$\alpha \in (0,1]$ 是学习率
$\gamma \in [0,1)$ 是折扣因子
$s'$ 是执行动作 $(a_1, a_2)$ 后的下一状态
$\mathcal{R}(s, a_1, a_2)$ 是奖励函数

状态值函数计算及其推导#

状态值函数的计算是Minimax Q-Learning的核心，它基于最小最大定理在每个状态上求解局部最优解。

推导过程#

在双人零和Markov博弈中，玩家1希望最大化自己的收益，而玩家2希望最小化玩家1的收益。根据博弈论中的最小最大定理，玩家1的最优策略应该是：

玩家1的目标：选择策略 $\pi_1(a_1|s)$ 使得在最坏情况下（即玩家2采用最优反制策略）仍能获得最大收益
玩家2的目标：针对玩家1的任何策略，选择能最小化玩家1收益的动作

这可以表示为一个嵌套的优化问题

V(s) = \max_{\pi_1} \min_{a_2 \in A_2} \sum_{a_1 \in A_1} \pi_1(a_1|s) Q(s, a_1, a_2)

计算公式#

状态值通过求解最小最大问题得到

V(s) = \max_{\pi_1} \min_{a_2} \sum_{a_1} \pi_1(a_1|s) Q(s, a_1, a_2)

等价的线性规划形式

\begin{align} \max \quad & v \\ \text{s.t.} \quad & \sum_{a_1} \pi_1(a_1|s) Q(s, a_1, a_2) \geq v, \quad \forall a_2 \\ & \sum_{a_1} \pi_1(a_1|s) = 1 \\ & \pi_1(a_1|s) \geq 0, \quad \forall a_1 \end{align}

公式含义：

第一个约束确保无论玩家2选择什么动作 $a_2$ ，玩家1的期望收益都至少为 $v$
第二个约束确保 $\pi_1$ 是有效的概率分布
第三个约束确保概率非负

理论保证：收敛到纳什均衡#

收敛性定理：在适当条件下（如所有状态-动作对被无限次访问），Minimax Q-Learning收敛到唯一的最优Q函数 $Q^*$ ，对应的策略对 $(\pi_1^*, \pi_2^*)$ 构成该双人零和Markov博弈的马尔可夫完美纳什均衡。

这意味着：

玩家1采用 $\pi_1^*$ 可以保证在最坏情况下获得博弈值 $V^*(s)$
玩家2采用 $\pi_2^*$ 可以确保玩家1的收益不超过 $V^*(s)$
任何一方单方面偏离均衡策略都不会获益

策略提取#

从最优Q函数提取纳什均衡策略：

玩家1的策略：上述线性规划的最优解 $\pi_1^*(a_1|s)$
玩家2的策略： $\pi_2^*(a_2|s) = \arg\min_{a_2} \max_{a_1} Q^*(s, a_1, a_2)$

迭代收敛后，得到的 $Q^*$ 对应的策略对正是该零和博弈的马尔可夫完美纳什均衡（Nash Equilibrium），需要注意的是

对于零和博弈，最小最大值 $V^*(s)$ 唯一，因此价值函数唯一，策略对可能有多个等价解。
如果博弈不是零和，对抗结构被打破，Minimax Q-学习不再保证收敛到纳什均衡；这时可改用如 Nash Q-learning、Correlated Q-learning 等方法，或考虑其他解概念（如相关均衡）。

7.3.4 算法伪代码#

Minimax Q-Learning


Input:	环境 $env$ ，最大回合数 $M$ ，学习率 $\alpha$ ，折扣因子 $\gamma$ ，探索率 $\varepsilon$
Output:	学习到的 Q-table $Q(s,a,b)$
1:	初始化 $Q(s,a,b)=0$ 对于所有状态 $s$ 和动作对 $(a,b)$
2:	For $\text{episode} = 1, \dots, M$
3:	$s \leftarrow env.reset(),\ \text{done}\leftarrow\text{False}$
4:	while $\lnot\text{done}$
5:	以概率 $\varepsilon$ 随机选取 $a$ ，否则 $a \leftarrow \arg\max_{a}\min_{b}Q(s,a,b)$
6:	对手策略获得 $b$
7:	执行 $(a,b)$ ，得到 $(s',r,\text{done})\leftarrow env.step(a,b)$
8:	计算 $V = \begin{cases} 0, & \text{if done}\\ \max_{a'}\min_{b'}Q(s',a',b'), & \text{otherwise} \end{cases}$
9:	更新 $Q(s,a,b)\leftarrow Q(s,a,b) + \alpha\bigl[r + \gamma V - Q(s,a,b)\bigr]$
10:	$s \leftarrow s'$
11:	返回学习到的 Q-table $Q(s,a,b)$

7.4 Nash Q-Learning#

Nash Q-Learning是Minimax Q-Learning在一般和博弈（非零和博弈）中的推广，专门用于求解多智能体博弈中的纳什均衡策略。与Minimax Q-Learning不同，Nash Q-Learning不假设博弈是零和的，因此需要考虑所有参与者的收益函数。

7.4.1 算法背景与动机#

从零和到一般和博弈#

在现实世界的多智能体系统中，智能体之间的关系往往不是完全对抗的零和关系，而是存在合作、竞争或混合的复杂关系。例如：

交通控制：不同路口的信号灯控制系统需要协调，既要考虑自身路口的效率，也要考虑整体交通流量
资源分配：多个用户共享网络带宽时，既存在竞争也可能通过协调获得更好的整体性能
经济市场：企业间既有竞争关系，也可能通过某种合作实现共赢

一般和博弈的特点#

一般和博弈具有以下特征：

非零和性：所有参与者的收益总和不必为零，存在共赢或共输的可能
策略耦合：每个参与者的最优策略依赖于其他所有参与者的策略选择
多重均衡：通常存在多个纳什均衡，需要选择合适的均衡概念
协调问题：参与者需要在多个均衡中进行协调选择

基本设定#

考虑 $n$ 个智能体的一般和Markov博弈，用元组 $(S, \{A_i\}_{i=1}^n, P, \{R_i\}_{i=1}^n)$ 描述：

$S$ ：状态空间
$A_i$ ：智能体 $i$ 的动作空间
$P(s'|s,\mathbf{a})$ ：状态转移概率
$R_i(s,\mathbf{a})$ ：智能体 $i$ 的奖励函数

其中 $\mathbf{a} = (a_1, a_2, ..., a_n)$ 是联合动作。

7.4.2 Nash Q-Learning算法框架#

Q函数定义#

每个智能体 $i$ 维护自己的Q函数：

Q_i(s, \mathbf{a}) = \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^t R_i(s_t, \mathbf{a}_t) \mid s_0 = s, \mathbf{a}_0 = \mathbf{a}\right]

表示在状态 $s$ 下执行联合动作 $\mathbf{a}$ ，然后所有智能体都遵循纳什均衡策略时，智能体 $i$ 的期望累积折扣奖励。

纳什均衡计算#

在每个状态 $s$ 下，通过求解以下纳什均衡问题来计算状态值：

对于每个智能体 $i$ ，其策略 $\pi_i^*(a_i|s)$ 应满足：

\sum_{a_i} \pi_i^*(a_i|s) Q_i(s, a_i, \mathbf{a}_{-i}) \geq \sum_{a_i} \pi_i(a_i|s) Q_i(s, a_i, \mathbf{a}_{-i})

对于所有可能的策略 $\pi_i$ 和其他智能体的均衡策略组合 $\mathbf{a}_{-i}$ 。

状态值函数#

智能体 $i$ 在状态 $s$ 的纳什均衡值为：

V_i(s) = \sum_{\mathbf{a}} \left(\prod_{j=1}^n \pi_j^*(a_j|s)\right) Q_i(s, \mathbf{a})

其中 $\pi_j^*(a_j|s)$ 是纳什均衡策略。

7.4.3 Q函数更新规则#

Nash Q-Learning的更新规则为：

Q_i(s, \mathbf{a}) \leftarrow Q_i(s, \mathbf{a}) + \alpha \left[R_i(s, \mathbf{a}) + \gamma V_i(s') - Q_i(s, \mathbf{a})\right]

其中：

$\alpha$ 是学习率
$\gamma$ 是折扣因子
$s'$ 是执行动作 $\mathbf{a}$ 后的下一状态
$V_i(s')$ 通过求解 $s'$ 状态下的纳什均衡获得

7.4.4 算法挑战与限制#

计算复杂性#

纳什均衡求解：在每次更新中都需要求解纳什均衡，这在一般情况下是NP-hard问题
维度诅咒：联合动作空间随智能体数量指数增长，使得Q函数维度过高
多重均衡：可能存在多个纳什均衡，算法需要选择其中一个

收敛性问题#

收敛保证有限：与Minimax Q-Learning不同，Nash Q-Learning的收敛性保证较弱
均衡选择：当存在多个纳什均衡时，算法可能收敛到不同的均衡或在均衡间振荡
探索-利用平衡：需要更复杂的探索策略来确保充分学习

实际应用限制#

可扩展性差：难以扩展到大量智能体的场景
计算资源需求高：每步都需要求解优化问题，计算开销大
实时性要求：在需要快速决策的环境中可能不适用

7.4.5 改进方法与变种#

为了解决Nash Q-Learning的局限性，研究者提出了多种改进方法：

近似求解方法#

函数逼近：使用神经网络等方法近似Q函数，降低维度
采样方法：通过采样减少纳什均衡计算的复杂度
启发式算法：使用遗传算法、粒子群优化等元启发式方法近似求解

替代均衡概念#

Correlated Q-Learning：使用相关均衡代替纳什均衡，计算更简单
Mean Field Games：在大量智能体场景中使用平均场理论
Stackelberg均衡：考虑智能体间的层次关系

Nash Q-Learning为理解多智能体强化学习中的策略交互提供了重要的理论基础，尽管在实际应用中面临诸多挑战，但它为后续更实用的多智能体学习算法发展奠定了基础。