Optimal Rates for Feasible Payoff Set Estimation in Games

技术摘要：博弈中可行收益集估计的最优速率

问题表述
本文探讨逆博弈理论问题，具体聚焦于可行收益集的估计，而非单一的点估计。该设定涉及一个学习器观察两名玩家在未知的双矩阵博弈（无论是常和博弈还是零和博弈）中的行动，其中玩家正在执行纳什均衡（可能是近似的）。学习器接收来自玩家混合策略 $(x, y)$ 的乘积分布中抽取的行动对 $(X_t, Y_t)$ 的独立同分布样本。

核心挑战在于，从行为推断效用函数本质上是欠定的（不可识别的）；多个收益矩阵可以为相同的观测均衡行为提供合理化解释。因此，本文旨在恢复所有使得观测策略 $(x, y)$ 构成 $\alpha$-纳什均衡的收益矩阵 $(A', B')$ 集合。目标是以高概率 ($1-\delta$) 和由豪斯多夫距离 ($\mathcal{H}$) 度量的精度 $\epsilon$ 来估计该集合。

方法论
作者提出了一种简单、非迭代的学习算法（过程 1），并对其样本复杂度进行了严格的理论分析，建立了上下界以证明极小极大最优性。

1. 算法：学习器收集 $m$ 个样本以计算经验平均策略 $\hat{x}$ 和 $\hat{y}$。随后，该算法输出所有使得 $(\hat{x}, \hat{y})$ 成为 $\alpha$-纳什均衡的收益矩阵集合。该集合由线性不等式定义，可表示为线性可行性问题。
2. 精确均衡 ($\alpha = 0$) 分析：
   • 下界：作者证明，在一般情况下，由于策略与收益集之间对应关系的强不连续性，从精确均衡学习可行集是不可学习的。具体而言，如果真实策略分布中包含概率趋于零的行动（支撑集发生变化），即使策略在统计上不可区分，可行集之间的豪斯多夫距离仍可能保持很大。为了使问题可学习，他们施加了最小概率假设 ($\pi_{\min}$)，确保支撑集中的每个行动以远离零的概率被执行。
   • 上界：在 $\pi_{\min}$ 假设下，作者构建了真实可行集 $G(x, y)$ 与估计集 $G(\hat{x}, \hat{y})$ 之间的映射。他们表明，豪斯多夫误差与真实策略和经验策略之间的 $\ell_1$ 距离 ($\|x - \hat{x}\|_1 + \|y - \hat{y}\|_1$) 呈线性缩放。
3. 近似均衡 ($\alpha > 0$) 分析：
   • 下界：近似参数 $\alpha$ 的存在缓解了精确情形中发现的不连续性问题，使得该问题无需 $\pi_{\min}$ 假设即可学习。然而，作者证明样本复杂度与 $\alpha$ 成反比（具体为 $\alpha^{-1}$）。$\alpha$ 的小值会显著降低学习速率，因为当概率围绕 $\alpha$ 时，策略的微小扰动可能导致可行集几何形状的巨大变化。
   • 上界：分析涉及对豪斯多夫距离误差的新颖分解。作者将误差控制问题归约为一个分数背包问题。通过利用可行集 $G_\alpha(x, y)$ 的几何结构，他们表明误差项 $(\hat{x} - x)^\top Ay$ 的方差很小，从而允许比标准界限所暗示的更快的收敛速率。他们还利用缺失质量的集中不等式处理了“缺失质量”问题（即在经验分布中观测为零但在现实中非零的行动）。

主要贡献与结果
本文提供了零和博弈与常和博弈中可行收益集估计的首个极小极大最优样本复杂度速率，涵盖了精确均衡与近似均衡。

• 精确均衡 ($\alpha = 0$)：
  • 条件：要求 $\pi_{\min} > 0$（执行支撑集中任何行动的最小概率）。
  • 样本复杂度：$m = \tilde{O}\left( \frac{\log(1/\delta)}{\log(1/(1-\pi_{\min}))} + \frac{n + \log(1/\delta)}{\epsilon^2} \right)$。
  • 第一项与学习策略的支撑集有关；第二项与足够准确地估计策略以界定豪斯多夫距离有关。
• 近似均衡 ($\alpha > 0$)：
  • 条件：无需最小概率假设。
  • 样本复杂度：$m = O\left( \frac{n + \log(1/\delta)}{\epsilon^2 \alpha} + \frac{\sqrt{n}\log(1/\delta)}{\epsilon \alpha} \right)$。
  • 结果揭示了与 $\alpha^{-1}$ 不可避免的依赖关系。对于小 $\epsilon$，项 $\frac{n}{\epsilon^2 \alpha}$ 占主导地位，而对于较大的 $\epsilon$，项 $\frac{\sqrt{n}}{\epsilon \alpha}$ 变得相关。
• 零和博弈与常和博弈：作者将这些问题作为独立问题处理。虽然零和博弈是常和博弈的子集，但作者指出，简单地切片常和估计以满足零和约束 ($A = -B$) 并不能平凡地产生零和集的最优估计，这是由于豪斯多夫距离的方向性问题。他们为这两种设定提供了具体的构造。

意义与主张
本文声称提供了多智能体环境中集合值收益推断的学习理论基础。通过避免施加额外的建模假设（如参数族）或先验选择原则（如最大熵），所提出的方法：

1. 捕捉固有歧义：它明确表示了所有兼容收益的集合，将特定收益的选择推迟到下游应用（如机制设计、反事实分析），在这些应用中可以应用特定的结构约束或选择标准。
2. 确立基本界限：匹配的上下界刻画了问题的统计难度，突出了近似参数 $\alpha$ 和策略支撑结构的关键作用。
3. 模块化：集合值的视角在结构计量经济学中是标准的，但在博弈学习中理论理解不足；这项工作弥合了这一差距。

作者明确指出，他们的分析是与实例无关的，未来的工作可以探索与实例相关的界限，或扩展到无限行动空间及演变的策略分布（例如，遗憾最小化）。他们并未提出具体的实验验证或超出所建立理论框架的新应用。