AIVAT技术系列中的启发式病态及通过不确定性传播实现进一步的方差缩减

# 启发式病态及其在AIVAT技术家族中的不确定性传播与进一步方差缩减

来源: https://arxiv.org/html/2605.14261
Juho Kim 计算机科学系 卡内基梅隆大学 [email protected]
Tuomas Sandholm 计算机科学系, CMU; Strategic Machine, Inc.; Strategy Robot, Inc.; Optimized Markets, Inc. [email protected]

###### 摘要

当样本量有限或试验成本高昂时，如何评估一个智能体在多智能体环境中的性能？AIVAT 方差缩减技术家族通过引入无偏、低方差的智能体期望收益估计器来应对这一挑战。AIVAT 的一个重要组成部分是启发式价值函数，它能够区分潜在低价值和高价值的反事实历史。文献中的一个显著空白是，关于如何选择启发式价值函数或如何处理其输出中的不确定性，几乎没有约束或指导原则。

在第一个贡献中，我们对启发式价值函数进行参数化，以凸显 AIVAT 的潜在脆弱性：a) 通过直接对样本方差应用梯度下降，可以将样本方差设定为病态的低值；b) 通过对检验统计量进行梯度下降/上升，可以实施 p-hacking 以得出所需的统计结论。主要教训是：启发式价值函数应在观察评估数据之前固定下来！在第二个贡献中，我们展示了如何传播启发式不确定性以量化 AIVAT 估计的不确定性。然后可以使用逆方差加权平均来进一步减少方差，但这可能需要牺牲 AIVAT 的无偏性保证。在我们的实验中，我们使用包含 10,000 手扑克牌局的数据集来展示我们的启发式病态和不确定性结果，其中后者使得出统计结论所需的样本量（扑克手数）减少了 43.0%。

## 1 引言

在多智能体环境中评估智能体的性能通常具有挑战性，例如当每次试验成本高昂或耗时较长时。这在展示 AI 智能体的超人类能力时尤为突出，需要人类专家长时间与智能体竞争。例如，超人类一对一扑克 AI 智能体 Libratus [4] 的评估持续了 20 天，从早到晚，涉及四名人类专家并行竞争，奖金池为 20 万美元。除非使用低方差的输出估计器，否则无法避免生成足够数据以得出统计上显著结论的资源密集型过程。

AIVAT [6] 方差缩减技术家族被提出用于处理扩展形式博弈中常见的高方差特性。AIVAT 主要从两个方面减少由自然和玩家行为引入的方差。首先，利用启发式价值函数，AIVAT 在已知概率的反事实动作应用于观察到的历史时，评估这些反事实历史的潜在价值。其次，AIVAT 利用这样一个事实：无论某个特定玩家的隐藏信息如何，其他玩家都会采取与原始观察中相同的行动。Burch 等人 [6] 表明 AIVAT 估计量是无偏的，并通过实验证明，与不使用该技术相比，所需试验次数减少了“超过一个数量级”才能得出相同的统计结论。此外，AIVAT 的效力随着已知策略的玩家数量增加而增强。然而，当考虑的玩家策略减少时，其效力也会下降，当只知道机会概率时，它退化为 MIVAT [13]。

扑克 AI 智能体 Pluribus [5] 的“5 人人类 + 1 个 AI”实验、另一个扑克 AI 智能体 DeepStack [11] 的评估，以及几届年度计算机扑克竞赛 (ACPC) [1] 代表了 AIVAT 技术家族的重要应用。第一个应用尤其引人注目：尽管 Pluribus 在整个实验中最终收益为负，但 AIVAT 能够证明 Pluribus 实际上是超人类的。

### 1.1 我们的贡献

在本文中，我们对 AIVAT 方差缩减技术家族提供了两种类型的贡献。第一类是警示性的。我们详细阐述了关于启发式价值函数开发约束的一个惊人事实：几乎没有相关论述。在 Zinkevich 等人 [15] 对优势总和无偏性的证明中（该证明构成了 DIVAT [2]、MIVAT [13] 和 AIVAT [6] 的基础），他们指出，“任何”和“所有”启发式价值函数都会产生真实价值的无偏估计量。White 和 Bowling [13] 建议从样本数据中学习一个线性价值函数，其中他们以样本方差作为真实方差的代理进行优化，但没有提供额外的学习过程指导。Burch 等人 [6] 使用其 AI 智能体的自对弈价值作为任意的固定启发式价值函数，该函数也参与生成了同一数据的过程，而该技术正是应用于这些数据。在本文中，我们通过展示可以学习到一个启发式价值函数，该函数 a) 获得病态的低方差，或 b) 进行 p-hacking 以错误地得出关于智能体性能的期望统计结论，从而凸显 AIVAT 的潜在脆弱性。使用 Pluribus 的博弈数据，我们通过参数化启发式输出并对目标目标应用梯度下降/上升来训练这样的函数。主要教训是：启发式价值函数应在观察评估数据之前固定下来！（使用 Pluribus 数据纯粹是为了演示，不应被视为对 Brown 和 Sandholm [5] 的批评；他们的结果是正确的。）

在我们的第二个贡献中，我们注意到，虽然 AIVAT 考虑了玩家动作相关的的不确定性，但在使用启发式价值函数时，它引入了另一个不确定性来源，即启发式价值函数对其输出的确定程度。我们可能对启发式价值函数的某些输出更有把握，而对其他输出把握较小。当价值函数输出是非确定性近似的博弈论值（例如，蒙特卡洛展开和/或抽象过程中的随机聚类）或从现有数据 [13] 中学习得到，并且是从训练分布的低密度与高密度区域的输入进行预测时，情况确实如此。我们以方差形式量化不确定性，并演示如何将启发式价值函数的不确定性传播到估计级别，从而获得特定价值估计的不确定性的度量。我们还展示了可以应用逆方差加权，对不确定性较大的估计赋予较小的权重，反之亦然，以实现进一步的方差缩减，尽管这存在将一些偏差引入估计的风险。尽管如此，我们 a) 展示了该偏差为零的必要条件，b) 演示了如何估计该偏差，c) 认为博弈智能体不太可能操纵偏差以显得表现更好。使用 Pluribus 的博弈数据，我们报告说，达到统计结论所需的试验次数（即扑克手数）减少了高达 43.0%。我们的发现使多智能体评估更具可扩展性。

## 2 符号与背景

在本节中，我们定义本文使用的符号，并提供扩展形式博弈和 AIVAT 方差缩减技术家族的背景知识。

### 2.1 扩展形式博弈

在本文中，我们将分析重点放在扩展形式博弈上，但 AIVAT 的思想也可以应用于其他表示形式。扩展形式博弈有一个有限的玩家集合 \(P\)（包括机会玩家 \(p_c\)）和历史集合 \(H\)。每个历史是由每个玩家 \(i \in P\) 采取的一系列动作组成，并与一个玩家 \(p(h)\) 和一组可用动作 \(A(h)\) 相关联。\(h \cdot a = h'\) 表示在 \(h\) 处应用 \(a \in A(h)\) 导致 \(h'\)。如果 \(p(h) = p_c\)，则 \(f_c(h, a)\) 给出每个可用动作 \(a \in A(h)\) 的固定概率分布。每个终止历史 \(z \in Z \subseteq H\) 都有每个玩家 \(i\) 的效用 \(u_i(z)\)。

不完全信息设置由信息集 \(\mathcal{I}_i\) 表示：属于非机会玩家 \(i \in P \setminus \{p_c\}\) 的历史的一个划分。玩家 \(i\) 无法区分 \(h, h' \in I \in \mathcal{I}_i\)。因此，\(A(h) = A(h')\)，并且我们将一个信息集处的可用动作集合记为 \(A(I)\)。每个玩家 \(i\) 使用一个策略 \(\sigma_i(I)\) 来玩，该策略在 \(A(I)\) 上分配一个概率分布。那么一个策略组合 \(\sigma\) 被定义为所有玩家策略的元组。我们使用 \(\pi(h)\) 来表示在玩家按照 \(\sigma\) 进行博弈时达到 \(h\) 的概率。玩家 \(i\) 对该概率的贡献是 \(\pi_i(h)\)。

#### 2.1.1 智能体评估

扩展形式博弈中的智能体评估通常需要估计给定策略组合 \(\sigma\) 下特定玩家 \(i\) 的期望效用：

\[\mathbb{E}_{z \in Z}[u_i(z)|\sigma] = \sum_{z \in Z} \pi(z) u_i(z).\]

在出现用于扩展形式博弈的方差缩减技术之前，独立抽取蒙特卡洛样本 \(z_1, \ldots, z_T\) 来计算平均玩家效用：

\[\bar{u}_i = \frac{1}{T} \sum_{t=1}^T u_i(z_t),\]

这是一个无偏估计量，即：

\[\mathbb{E}[\bar{u}_i|\sigma] = \mathbb{E}_{z \in Z}[u_i(z)|\sigma],\]

并且具有以下方差：

\[\operatorname{Var}[\bar{u}_i|\sigma] = \frac{1}{T} \operatorname{Var}[u_i(z)|\sigma].\]

多智能体环境的随机性和所需的统计显著性水平影响 \(T\) 的选择。因此，人们受到每次试验成本的限制，使用蒙特卡洛方法可能成本太高而无法得出统计上显著的结论。

### 2.2 方差缩减技术

AIVAT 方差缩减技术家族将控制变量法专门应用于扩展形式博弈中的智能体评估，以对任何函数 \(v(z)\)（例如玩家效用）给出低方差的估计。当前最先进的方差缩减技术是 AIVAT [6]，它可以被视为其两个前身的组合：想象观察 [3] 和优势总和 [15]。AIVAT 技术家族产生价值函数的无偏估计量。

#### 2.2.1 控制变量法

控制变量法 [7, Ch. 4] 是减少蒙特卡洛方法方差的标准方法。我们首先用智能体评估的语言给出简要描述。在该设置中，我们寻求估计 \(\mathbb{E}_{z \in Z}[v(z)|\sigma]\)。假设存在另一个价值函数 \(w(\cdot)\)，其中 \(\omega = \mathbb{E}_{z \in Z}[w(z)|\sigma]\) 是已知的。那么，以下是对 \(\mathbb{E}_{z \in Z}[v(z)|\sigma]\) 的无偏估计量：

\[\hat{v}(z) = v(z) - c(w(z) - \omega)\]

对于任何常数 \(c\) 的选择。其方差如下：

\[\operatorname{Var}(\hat{v}(z)) = \operatorname{Var}(v(z)) + c^2 \operatorname{Var}(w(z)) - 2c \operatorname{Cov}(v(z), w(z)).\]

当 \(c^2 \operatorname{Var}(w(z)) - 2c \operatorname{Cov}(v(z), w(z)) \leq 0\) 时，实现方差缩减。\(c\) 的最优选择可以通过对 (1) 关于 \(c\) 求导得到：

\[c^* = \frac{\operatorname{Cov}(v(z), w(z))}{\operatorname{Var}(w(z))},\]

这导致：

\[\operatorname{Var}(\hat{v}(z)) = (1 - \operatorname{Corr}(v(z), w(z))^2) \operatorname{Var}(v(z)).\]

#### 2.2.2 优势总和

优势总和技术使用带有启发式价值函数的控制变量法来减少估计的方差，形式如下：

\[\hat{v}(z) = v(z) - \hat{v}_c(z),\]

其中 \(\hat{v}(\cdot)\)、\(v(\cdot)\) 和 \(\hat{v}_c(\cdot)\) 分别表示估计、价值函数和修正项。修正项（可以被视为控制变量）定义如下：

\[\hat{v}_c(z) = \sum_{h \cdot a \in K(z)} \left( v'(h \cdot a) - \sum_{a' \in A(h)} f_c(h, a') v'(h \cdot a') \right),\]

其中 \(v'(\cdot)\) 是启发式价值函数，\(K(z)\) 是 \(z\) 之前的历史集合，这些历史在直接父历史处的可用动作的概率分布是已知的。MIVAT [13] 代表了优势总和的一个特例，其中除了自然之外，没有其他玩家的动作概率是已知的。在这种特定情况下，减去修正项可以被视为抵消运气（或缺乏运气）的影响。无论启发式价值函数 \(v'(\cdot)\) 的选择如何，Zinkevich 等人 [15] 表明优势总和（以及因此 MIVAT）是期望值的无偏估计量，即 \(\mathbb{E}_{z \in Z}[\hat{v}(z)|\sigma] = \mathbb{E}_{z \in Z}[v(z)|\sigma]\)。

White 和 Bowling [13] 提出使用线性函数作为启发式价值函数，该函数在现有样本数据上进行训练。在此过程中，他们提议最小化样本方差作为真实方差的代理，因此以下优化问题旨在最小化均方误差：

最小化： \(\hat{v}: Z \mapsto \mathbb{R}\) 使得 \(\sum_{t=1}^T \left( \hat{v}(z_t) - \frac{1}{T} \sum_{t'=1}^T \hat{v}(z_{t'}) \right)^2\)。