AV-AIVAT：在不完美信息博弈中成本降低 74 倍、具有认证的任意时间有效停止的智能体评估

AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games

arXiv: 2608.06362v1

论文信息

标题: AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games

作者: Boning Li, Yu Chen, Longbo Huang

发布日期: 2026-08-06

arXiv ID: 2608.06362v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：评估两个智能体谁更强需要打足够多的对局，但每局都有金钱、推理或专家时间成本，且事先无法知道需要多少局；固定预算会浪费或无法得出结论，随意提前停止又会破坏统计保证。论文要解决 “直到证据足够即可停止，同时保持所声称的置信水平” 的问题。
  • 核心方法：将降低博弈结果方差的 AIVAT 技术，与允许连续监测且可随时停止的置信序列（Confidence Sequence，CS）相结合，提出 AV-AIVAT 协议；并通过 “过去信息可测” 的值函数更新，使修正项的条件均值为零，从而保证在线学习值函数时有效性不失效。
  • 关键结果：在 15 个 LLM 扑克智能体的 71,439 手牌评测中，达到 ±1 大盲注精度所需的中位手数，使用渐近置信序列的 AIVAT 修正结果仅为原始结果的约 1/74，即减少 74 倍（表 1）。
  • 主要局限：文中采用的精确有限样本认证（EB-CS）因赌注上限（≤1/2）导致宽度存在确定性的下界（2B⋅2log⁡(2/α)/t2B\cdot2\log(2/\alpha)/t），方差缩减并不总能线性转化为提前停牌；只有在游戏的收益上界是通过结构独立证明时（如 Leduc 的例子），EB-CS 才提供无条件的精确覆盖，而在更大规模的 HUNL 中，修正收益的上界尚无可用的解析证明。
  • 适合读者：对博弈智能体评估、交互式评测的统计效率、序贯决策中的可靠推导、以及可重复审计感兴趣的机器学习、统计和博弈论领域的研究者与工程师。

论文背景和研究动机

交互式智能体的评测，特别是像德州扑克这样的不完全信息博弈，通常极其昂贵。以 LLM 智能体为例，PokerSkill 平台每手牌的推理成本约为 $0.07–$0.30；人类高手对局的投入更是惊人，Libratus 在 20 天内与职业牌手打了 12 万手牌，奖金池约 20 万美元。这些固定的、预先设计好的评测预算缺乏灵活的终止准则：要么在结果已定型后继续支付额外成本，要么在证据不足时就草草收场。

更麻烦的是，评估者如果简单地反复查看一个固定样本量的置信区间，并在第一次看到 “显著” 就停止，会严重破坏所声称的置信水平，造成假阳性膨胀。因此，真正需要的是一套能够在证据足够时立即终止，同时保持所声称统计保证的评测框架。

减少博弈结果方差的工具 AIVAT 已经存在，它利用动作条件核将期望为零的修正项叠加到原始收益上，从而大幅降低噪声。而另一个独立领域——置信序列（CS）——则专门解决连续监控与可选停止下的统计有效性问题。将两者恰当结合，是一个自然的思路。但直接结合会遇到三个实际问题：① 值函数能否随着新数据到来而更新而不破坏修正项的零均值性质？② 方差缩减如何以及何时转化为所需对局数的减少？③ 若要在事后被第三方审计，需要发布哪些数据？这篇论文正是围绕这三个问题展开。

核心方法和技术细节

AV-AIVAT 的核心是一个分层协议：底层利用可预测的 AIVAT 接口对每一局的原始收益进行修正，随后在上层运行两个平行的置信序列——渐近版本的 AsympCS 作为高效的主要区间，和基于有界赌注的 EB-CS 作为有限样本的精确认证。

可预测的 AIVAT 传统 AIVAT 的值函数在整个评估开始前就冻结。论文证明了一个更灵活的条件：只要在每一局开始前，用于当前局修正的值函数 vtv_t 是过去所有局（及该局之前的信息）的可测函数，修正项 CtC_t 的条件期望在给定过去信息时仍然为零（命题 1）。具体而言，修正节点处的动作分布 pt,hp_{t,h} 必须是已知的，且 “是否启用修正” 的标志 St,hS_{t,h} 必须在观察到该动作之前确定。此时，对每一局，Yt=Xt+CtY_t = X_t + C_t 的条件期望仍为 μ\mu，而 ∣Yt∣|Y_t| 的界由原始收益界与值函数范数决定。这一 “过去信息可测” 条件允许评估者在评测进行中持续精炼值模型，而不会破坏统计有效性的基础。

两个置信序列的分工

  • AsympCS：基于时间一致的中心极限定理推导而来，其宽度正比于样本标准差 σ^t\hat{\sigma}_t 与一个只依赖 tt、参数 ρ\rho 和置信水平 α\alpha 的因子。该序列适用于渐近有效，实际使用中遵循预设的校准（如一个独立的调优拆分），以避免事后的参数选择偏差。
  • EB‑CS：利用可预测的赌注和正则化的历史均值，将 [0,1][0,1] 区间上的过程转换为精确的时间一致置信序列。为保证有限样本覆盖，必须事先声明一个几乎必然的修正收益上界 BYB_Y。由于赌注被限制在不超过 1/21/2，其宽度存在确定性的下界 4Blog⁡(2/α)/t4B\log(2/\alpha)/t（引理 1）。这意味着当目标精度 ε\varepsilon 较小时，EB‑CS 的停牌次数可能不会随着方差缩减而改善，除非声明边界 BYB_Y 足够紧。这一现象在定理 1 中得到系统刻画：停牌行为可划分成由边界主导的 1/ε1/\varepsilon 区域和由方差主导的 1/ε21/\varepsilon^2 区域。

在线值函数的效率 对于 AsympCS 这类宽度追踪条件方差的序列，论文证明：如果在线值函数的方差后悔（即与某个理想值函数相比，条件方差的累积偏差）是次线性的，那么在渐进意义上不会造成停牌延迟（定理 2）。由于值函数的 ℓ∞\ell_\infty 逼近误差通过 4Kσ⋆Δ+4K2Δ24K\sigma_\star\Delta + 4K^2\Delta^2 与方差后悔建立联系（引理 2），只要值函数的误差随局数以多项式速度衰减，例如 ∥vt−v⋆∥∞≤ct−β\|v_t - v^\star\|_\infty \le ct^{-\beta}，就能满足该条件。不过，在实际博弈中，信息集的最小访问次数往往远小于总局数，因此有限样本下仍可能存在可观察的差距。

创新点和贡献

  1. 首次在统一框架下将 AIVAT 与 CS 结合：提出了可预测的 AIVAT 接口，明确指出了 “启用修正” 和 “动作核” 必须前置于当前局观测的约束，提供了同时运行渐近与精确两类 CS 的完整协议。
  2. 给出了方差缩减转化为提前停止的精确刻画：针对 EB‑CS 的赌注上限，推导出确定性的宽度下限，建立了一个三区域的设计代理（公式 7），阐明了为什么某些方差增益不会转化为等比例的停牌收益，并指出一个绑紧的声明边界是必要前提。
  3. 设计了可审计的发布协议：只需发布修正收益前缀、停牌元数据、边界出处和置信序列设定，第三方即可在报告停牌时刻重建区间，而无需原始收益流。这为昂贵、大规模的无完美信息博弈评测提供了可重现性的最低标准。
  4. 提供了在线值学习不会延迟停牌的渐进保证：将方差后悔的概念引入，并给出一个上界，表明可预测的在线值函数在精度足够时能逼近甲骨文值函数的效率，而无需预先冻结模型。

实验结果分析

实验使用三个数据源：来自 PokerSkill 的 15 种 LLM 扑克配置的 HUNL 对局（共 71,439 手），以及 Leduc 扑克的受控仿真。

HUNL 上的方差缩减与停牌 AIVAT 将结果的方差中位数降低了 54.4 倍（范围 24.2–86.0 倍）。对于 ±1 BB 的精度目标，AsympCS 的中位停牌手数比为 74.17 倍（即原始收益需要的手数约为 AIVAT 修正收益的 74 倍，表 1）。但在 EB‑CS 中，由于声明的修正收益上界为 200 BB（基于堆叠限制，但不是对修正项的结构证明），方差缩减转化为停牌收益极为有限：中位比仅为 1.365 倍。这一鲜明对比与宽度下限的理论预测一致。

Leduc 上的精确认证 在标准 Leduc 中，通过对游戏树进行枚举，可以结构性地证明修正收益绝对值的上界为 117 筹码（附录 D）。在此严格边界下，400 次重复的 EB‑CS 覆盖完美（0 次排除真实均值），且实际宽度几乎等于其确定性下限，比率为 1.0019–1.0074（在 t=1000t=1000 与 40004000 处）。这证实了当拥有独立解析边界时，EB‑CS 可作为真正的有限样本认证手段。

连续监控的审计能力 一个零效应重抽样池的仿真显示：若评估者反复查看普通的固定样本置信区间，并在第一次排除零时停止，61.35% 的条目会错误地报告显著。但在该选定前缀上重新计算 EB‑CS 和 AsympCS 时，零均被包含在内（EB-CS 100% 包含，AsympCS 99.9185% 包含），即时间一致序列能够正确筛选掉所有因选择性停止而产生的虚假宣称。

在线值函数的实证表现 在 Leduc 中，一个通过历史对手动作频率进行拉普拉斯平滑的值模型，能在两个策略不匹配的测试场景中恢复约 78.6% 和 77.1% 的冻结-甲骨文方差差距。尽管甲骨文值函数仍然最快，但可预测学习的引入已经显著缩小了差距，且理论上的渐进无延迟得到印证。

实践建议

对于希望在昂贵的不完全信息博弈评测中部署 AV-AIVAT 的研究者和工程师，以下几点值得纳入实践：

  1. 双层报告机制 将 AsympCS 作为经常查看的高效区间，用于日常监控与早期发现；当具备从游戏规则中推导出的结构上界时，才使用 EB‑CS 发布精确的有限样本认证。E1 的 Leduc 示例（附录 D）展示了如何构造策略无关的解析边界，是一种可推广的方法。

  2. 确保可预测性的工程约束 所有用于当前局修正的值函数在局开始前就必须冻结；任何模型更新只能在局结束后应用。记录每一步更新的时间戳和训练数据范围，使审计者能够验证 “过去信息可测” 这一条件。

  3. 发布完整的审计材料 无论最终结论如何，都建议发布：

    • 修正收益前缀 Y1:t^Y_{1:\hat{t}} 及可选的原始收益；
    • 停牌时间 t^\hat{t}、目标精度 ε\varepsilon、置信水平 α\alpha；
    • 声明的修正收益边界 BYB_Y 及其推导来源（游戏结构 vs. 样本观察值）；
    • 置信序列的完整参数（ρ\rho、赌注上限、燃烧期等）。 这样，任何第三方都能重建区间，而无需重新对局。

  4. 在线值模型应保守 虽然渐进理论允许在线学习，但在样本量较小的区域，值函数误差可能因信息集访问不均衡而较大。实践中建议使用一个可靠的预热模型作为初始值函数，或采用较为缓慢的学习率，并在早期阶段加入额外的安全边际。

  5. 提前规划边界声明 如果期望得到无条件的精确覆盖声明，应像 Leduc 案例那样，在设计评测时就通过游戏理论分析（例如枚举所有可能的收益路径和修正累加）事先建立一个策略无关的修正收益绝对上界。对于 HUNL 这类复杂游戏，明确的解析边界仍然是开放问题；在此之前，任何 EB‑CS 结果都应明确标记为 “描述性的”，并附上所使用的观测边界。

通过以上实践，AV-AIVAT 不仅能显著节约对手局成本，而且使停止时机的选择成为严格可审计的过程，从而为交互式智能体评测提供一条既经济又可靠的路径。