Learning in Matching Games with Bandit Feedback

技术摘要：匹配博弈中的学习问题

问题定义
本文引入了一个位于双边匹配市场与博弈论交汇处的新颖学习问题。该设定涉及一个广义市场，其中包含两组不同的主体（集合 $P$ 和 $A$），他们在时界 $T$ 内由一个中央平台进行匹配。与传统的具有静态已知偏好的匹配问题，或标准多臂老虎机（MAB）设置（其中主体获得直接的随机收益）不同，本框架假设一旦匹配成功，主体将参与一个初始未知的二-人零和博弈（ZSG）。

在这种场景下，主体必须同时学习底层的博弈动态，并从这些交互的结果中推导出其偏好。在每个时间步 $t$：

1. 中央平台根据估计的主体偏好生成一个匹配 $m_t$。
2. 已匹配的主体选择策略（混合动作）并采样特定的动作。
3. 主体接收随机老虎机反馈（奖励）并观察其匹配伙伴的动作。
4. 主体更新对博弈矩阵及偏好的估计，以备下一轮使用。

核心挑战在于学习一个匹配均衡（Matching Equilibrium），这是一个由 [10] 定义的解概念，即匹配是稳定的（不存在阻塞对），且主体与其分配的伙伴进行纳什均衡（NE）博弈。难点在于，主体预先并不知道博弈矩阵，必须通过探索来形成偏好，而匹配机制（通常为 Gale-Shayley 算法）依赖于这些偏好来确保稳定性。

方法论与算法
为了解决这一问题，作者提出了基于“面对不确定性保持乐观”原则的算法 UCB-MG。其方法论如下：

• 乐观估计： 主体为潜在匹配的收益矩阵维护上置信界（UCB）。具体而言，对于一对 $(p, a)$，通过在观测到的奖励经验均值上添加置信奖励，构建乐观的收益矩阵 $\bar{A}_{p,a}$。
• 偏好形成： 基于这些乐观的收益矩阵，主体在假设采取最优策略（极大极小策略）对抗每个潜在伙伴的前提下，计算乐观的博弈价值 ($\bar{V}^*$)。主体根据这些乐观博弈价值对偏好进行排序。
• 匹配： 中央平台收集这些报告的偏好，并执行 Gale-Shapley (GS) 算法以生成当前轮次的稳定匹配。
• 策略执行： 一旦匹配成功，主体根据其乐观收益矩阵推导出的极大极小策略选择动作，采样动作并接收反馈以更新其估计。

遗憾度定义：匹配不稳定性
本文的一个关键贡献是定义了一个合适的遗憾度指标，称为匹配不稳定性（Matching Instability, MI）。标准的 MAB 或博弈论中的遗憾度定义并不适用，因为目标是收敛到匹配与策略的联合均衡。

作者将 MI 定义为在给定当前匹配 $m$ 和策略剖面 $X$ 的情况下，使市场趋于稳定所需的最小总补贴。在数学上，它是求解一个线性规划问题，旨在最小化补贴 $s_a$，并满足以下条件：

1. 无阻塞对： 确保在给定当前策略的情况下，没有任何一对 $(p, a)$ 能通过偏离当前策略来改善其效用。
2. 个体理性： 确保主体偏好其当前的匹配而非处于未匹配状态。
3. 价值保证： 确保主体获得的效用至少等于其博弈的极大极小值（这是对严格纳什条件的放宽，以实现可处理的分析）。

累积遗憾 $R_T$ 被定义为时界 $T$ 内匹配不稳定性之和。

核心贡献

1. 学习问题定义： 本文形式化了第一个学习场景，即双边市场中的主体必须通过学习未知的零和博弈来形成用于匹配的偏好。
2. 遗憾度指标： 引入了匹配不稳定性，将子集不稳定性 [8, 17] 的概念扩展到了匹配主体进行博弈的场景。该指标量化了距离匹配均衡的距离。
3. 算法设计： 作者提出了一个基于 UCB 的算法 (UCB-MG)，它将乐观博弈价值估计与 Gale-Shapley 机制相结合。
4. 理论保证： 文中证明了所提算法实现了与实例无关的亚线性遗憾度界限 $\tilde{O}(\sqrt{Tmkpa})$，其中 $T$ 是时界，$m$ 和 $k$ 是每方主体的动作数，$p$ 和 $a$ 是双方主体的数量。
5. 泛化性： 该理论界限统一了现有结果。当 $m=k=1$ 时，它恢复了经典双边匹配的界限 ($\tilde{O}(\sqrt{Tpa})$)。当 $p=a=1$ 时，它恢复了零和博弈中的自我博弈界限 ($\tilde{O}(\sqrt{Tmk})$)。

结果与实证证据
作者通过使用从正态分布中采样的收益矩阵生成的合成实例进行了实证验证。他们比较了三种场景：

• 自我博弈（Self-Play）： 双方都遵循 UCB-MG 算法。
• 纳什响应（Nash-Response）： 一方已知真实的博弈矩阵并执行纳什均衡策略，而另一方进行学习。
• 最佳响应（Best-Response）： 一方已知真实的矩阵及对手的策略，并进行最佳响应。

结果表明，系统在所有场景下都能学习到稳定结果，表现出亚线性的遗憾度增长。正如预期，纳什响应场景下的遗憾度最低。有趣的是，虽然最佳响应场景最初的表现优于自我博弈，但随着市场规模（主体数量和动作数量）的增加，其性能有所下降，这可能是由于一方利用另一方所带来的复杂性导致的。

意义与未来方向
该论文声称其意义在于作为理解此类环境研究的初步步骤——即在这些环境中，主体只有在通过动作进行博弈交互后才能获得收益，而非直接接收偏好信号。它证明了在如此复杂且耦合的设置中，可以高效地学习到稳定结果。

作者谦逊地将这项工作视为未来研究的基础。他们提出了几个开放的研究方向：

• 将模型从零和博弈扩展到一般和博弈。
• 将无遗憾学习算法（如 Exp3）集成到匹配框架中，以处理非零和动态。
• 放宽主体观察其伙伴动作的假设。
• 探索替代的博弈模型（马尔可夫博弈、斯塔克尔伯格博弈）和匹配结构（多对一市场）。
• 研究无需中央协调器的去中心化设置，即主体自行选择匹配和策略。