技术摘要：用于上下文匹配市场的自适应多臂老虎机算法

问题表述

本文研究了双边匹配市场中的上下文多臂老虎机问题。该市场由 $N$ 个参与者（players）和 $K$ 个臂（arms）组成（其中 $N \le K$）。核心挑战在于参与者偏好的动态性，这种偏好通过线性上下文效用函数建模：$U_{i,j}(t) = \theta_i^\top x_j(t)$。其中，$\theta_i$ 表示参与者 $i$ 的未知固定偏好向量，$x_j(t)$ 是时间 $t$ 时臂 $j$ 的观测上下文向量。

与具有静态偏好的传统设定不同，上下文 $x_j(t)$ 随时间变化，可能会改变底层稳定匹配基准。目标是设计一种在线算法，将参与者匹配到臂，以最小化参与者最优稳定遗憾（player-optimal stable regret）。该遗憾定义为：在每一轮中，算法匹配下参与者获得的效用与该参与者在给定真实效用下所能获得的参与者最优稳定匹配（即对该参与者而言的最佳稳定匹配）所获得的效用之间的累积差值。

本文针对上下文生成的两种不同设定进行了探讨：

1. 随机上下文（Stochastic Contexts）： 上下文从固定但未知的分布中独立同分布（i.i.d.）抽取。
2. 对抗性上下文（Adversarial Contexts）： 上下文可以是任意的，甚至可能由自适应对手选择，代表了最坏情况下的非平稳环境。

方法论

作者提出了完全自适应的算法，无需预先知道最小偏好间隙或上下文的协方差结构。两种算法均采用批处理自适应阶段转换机制（batched adaptive phase transition scheme），在探索（细化参数估计）和利用（执行稳定匹配）之间交替进行。

1. 随机设定：批处理自适应遗憾平衡（BARB）

针对随机设定，作者引入了BARB，该算法以批处理模式运行。

• 自适应间隙估计： 算法维护一个候选最小偏好间隙 $\Delta_k$，其初始化为输入值，并在随后的每个批次中缩小 $\sqrt{2}$ 倍。这使得算法能够在不知道真实间隙的情况下，自适应地逼近问题的真实难度。
• 探索与利用：
  • 探索： 如果上下文向量的马氏范数 $\|x_j(t)\|_{V_i(t)^{-1}}$ 超过阈值 $\xi_k$，算法进入探索阶段。它构建一个高不确定性对的双部图，并执行最大基数匹配（Maximum Cardinality Matching），以收集用于岭回归更新的信息样本。
  • 利用： 如果不确定性较低，算法基于估计的效用使用Gale-Shapley (GS) 算法。它监控估计效用置信区间的重叠情况。如果重叠过多（表明当前的间隙估计 $\Delta_k$ 过大），则当前批次终止，算法进入下一个批次，并使用更小的间隙估计。
• 理论保证： 在温和假设下，BARB 实现了实例相关的多对数遗憾上界 $\tilde{O}(\log^2 T / \Delta_{\min}^2)$。此外，在上下文协方差矩阵具有严格正最小特征值的条件下，该界限改进为 $O(\log T / \Delta_{\min}^2)$。在渐近区域，本文建立了紧致的实例无关遗憾界限 $\tilde{\Theta}(T^{2/3})$。

2. 对抗性设定：自适应探索 - 选择预言机（AdECO）

针对对抗性设定，标准的遗憾定义变得不可处理，因为对手可以迫使最小效用差 $\delta_{\min}$ 在任意长的时间内任意小。

• 可处理的遗憾定义： 作者提出了一种改进的遗憾概念，在较大间隙和较小间隙之间进行插值。当 $\delta_{\min}(t) > \Delta$ 时，基准为标准的最优稳定份额 $U^*_i(t)$。当 $\delta_{\min}(t) \le \Delta$ 时，基准为 $\epsilon$-最优稳定份额 $U^\epsilon_i(t)$ 的 $\alpha$-近似值，利用离线近似预言机实现。
• 算法设计： AdECO 遵循与 BARB 类似的自适应结构。
  • 在探索阶段，它使用最大基数匹配来减少不确定性。
  • 在利用阶段，如果置信区间分离良好，它使用 Gale-Shapley 算法。如果它们重叠（表明间隙较小），则调用$\alpha$-近似预言机（基于 Lin 等人，2026），生成一种随机匹配，保证获得最优稳定份额的一部分。
• 理论保证： 通过设置算法参数 $\Delta = O(T^{-1/3})$，AdECO 实现了实例无关的次线性遗憾界限 $O(T^{2/3})$。

3. 去中心化扩展

本文简要将 BARB 框架扩展到去中心化市场，其中参与者独立行动，没有中央协调器。通过引入关于环境识别的假设（不同环境具有不同的前 $N$ 名排名），去中心化算法实现了与集中式版本相同的遗憾阶数，并增加了一个依赖于环境数量的常数项。

主要贡献

1. 问题难度的新颖度量：

   • 对于随机上下文，本文引入了最小偏好间隙（$\Delta_{\min}$），该间隙通过概率定义以捕捉小效用差的可能性，提供了比先前工作中使用的确定性下界更现实的度量。
   • 对于对抗性上下文，它定义了一种可处理的遗憾概念，根据间隙大小在精确稳定匹配基准和近似基准之间切换，从而在最坏情况场景下实现有意义的保证。

2. 完全自适应算法：

   • 提出的算法（BARB 和 AdECO）是完全自适应的，无需预先知道最小偏好间隙或上下文分布的协方差结构。它们根据观测数据动态调整探索与利用的权衡。

3. 紧致的理论界限：

   • 随机设定： 本文提供了实例相关的多对数遗憾界限，并在温和的协方差假设下提供了对数界限。关键在于，它建立了匹配的实例无关下界 $\Omega(T^{2/3})$，证明了渐近速率的紧致性。
   • 对抗性设定： 针对提出的可处理遗憾度量，它实现了实例无关的次线性遗憾界限 $O(T^{2/3})$。

4. 去中心化适应： 这项工作展示了这些自适应机制如何在最小化额外假设的情况下适应去中心化环境。

结果与意义

本文声称其主要意义在于解决了匹配市场中上下文变化引入的复杂性。作者指出，微妙的上下文变化可能会轻微改变某个参与者的效用，同时完全重新配置底层稳定匹配基准，从而可能导致其他参与者出现巨大的遗憾峰值。

• 鲁棒性： 所提算法的自适应性质使其能够处理任意的上下文协方差结构（在随机情况下）和任意的上下文序列（在对抗情况下），在上下文分布病态（例如，最小特征值较小）的场景中，其表现优于非自适应基线（如 ETC，即探索 - 然后承诺）。
• 理论紧致性： 在随机设定下，针对实例无关遗憾推导出匹配的上下界（$\tilde{\Theta}(T^{2/3})$），为理解具有未知偏好的上下文匹配的难度提供了基础认识。
• 实际适用性： 通过消除对环境分布或间隙参数的先验知识需求，这些算法更适合实际应用，如在线劳动力市场、拼车服务和住院医师匹配，在这些应用中，偏好动态和上下文分布通常是未知且非平稳的。

作者总结道，虽然当前框架假设线性上下文效用，但所开发的自适应机制为未来在更复杂市场结构中的工作提供了坚实的基础。