A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming

问题定义
本文探讨了在线多人类-多机器人组队（multi-human multi-robot teaming）的挑战，即学习者需要在 $T$ 轮中，将固定数量 $K$ 个具有未知能力的机器人分配给变化的 $M$ 个人类智能体集合。目标是最大化这些人机团队产生的累积回报。该问题被框架化为线性匹配强棒（linear matching bandit）问题。其核心难点在于两个方面：“不可处理的臂空间（intractable arm space）”，即将每种唯一的匹配视为一个独立的强棒臂会导致指数级增长；以及“组合复杂性（combinatorial complexity）”，即匹配约束相互关联了回报并使优化过程复杂化。

作者假设了一个线性回报结构，其中由人类智能体 $m$（具有已知特征向量 $X_{m,t} \in \mathbb{R}^d$）和机器人 $k$（具有未知特征向量 $\theta_k \in \mathbb{R}^d$）组成的团队所产生的期望回报由内积 $X_{m,t}^\top \theta_k$ 给出。虽然人类特征是可观测的（源自个人资料或任务上下文），但由于先进 AI 系统的复杂性和缺乏透明度，机器人的特征是未知的。学习者观察到达的人类特征，选择一种匹配（一个从人类到机器人的单射函数），并接收带有噪声的回报。

方法论：LinMatch 算法
为了解决这一问题，作者提出了基于“面对不确定性时的乐观主义（Optimism in the Face of Uncertainty, OFU）”原则的在线学习算法 LinMatch。该算法按轮次运行，包含以下步骤：

1. 置信区间构建： 利用岭回归（ridge regression），LinMatch 估计每个机器人的未知特征向量 $\theta_k$。它为每个机器人维护一个协方差矩阵 $V_{k,t}$ 和一个基于历史分配的奖励加权和 $H_{k,t}$。这使得能够为每个 $\theta_k$ 构建一个椭球置信区间 $\hat{\Theta}_{k,t}$，确保真实参数以高概率落在该区间内。
2. 乐观匹配： 在每一轮中，算法计算一个“乐观”匹配。它不是使用 $\theta_k$ 的点估计，而是选择置信区间内能使期望总回报最大化的参数向量。
3. 通过线性规划高效求解： 一个关键的技术贡献是对乐观匹配问题的重新表述。作者证明了寻找在置信集上使内积之和最大化的匹配所需的混合整数规划可以被解耦。通过为每个人类-机器人对定义乐观回报估计值 $\tilde{y}_{mk,t}$，该问题简化为二分图中的标准最大权重匹配问题。这可以使用 匈牙利算法（Hungarian algorithm） 在 $O(K^3)$ 时间内高效求解。

主要贡献与理论结果
本文有两个主要贡献：

1. 算法重构： 它将每一轮中的乐观匹配问题重新表述为最大权重匹配的线性规划问题，使其可以通过匈牙利算法进行计算。
2. 紧致遗憾界限（Tight Regret Bounds）： 作者为 LinMatch 提供了严谨的理论保证。
   • 上界： 他们建立了一个与实例无关的累积遗憾上界 $\tilde{O}(d\sqrt{MKT})$，其中 $d$ 是特征维度，$M$ 是人类数量，$K$ 是机器人数量，$T$ 是时间跨度。
   • 下界： 他们证明了该设定下任何匹配策略的极小极大（minimax）下界为 $\Omega(d\sqrt{MKT})$。
   • 最优性： 上界与下界的匹配确立了紧致的最优遗憾率 $\tilde{\Theta}(d\sqrt{MKT})$。这表明 LinMatch 相对于所有问题参数（$T, d, M, K$）实现了严格最优的可实现遗憾率。

实验结果
作者通过 $K=20$ 个机器人和 $M=10$ 个人类的数值模拟验证了 LinMatch。

• 与 ETC 的比较： 将 LinMatch 与探索后提交（Explore-Then-Commit, ETC）算法进行了比较。虽然 ETC 可以通过最优的探索阶段长度实现亚线性遗憾，但如果探索不足，则会遭受线性遗憾。相比之下，LinMatch 展示了更一致的表现，且具有比 ETC 更窄的置信区间。
• 正则化敏感性： 改变正则化参数 $\lambda$ 的实验表明，虽然理论上要求 $\lambda \ge L^2$，但在实践中，较小的值（例如 $\lambda=1$）通常能产生更低的回报遗憾，这表明理论条件是保守的。

意义与范围
本文声称，LinMatch 是首个证明具有线性强棒结构的匹配问题中，与实例无关的最优可实现遗憾率精确为 $\tilde{\Theta}(d\sqrt{MKT})$ 的研究。所提出的方法旨在适用于超越人类-机器人组队的任何具有线性特征的集中式匹配问题，例如住房分配和推荐系统。这项工作强调，通过利用线性结构和高效的组合优化，可以克服在线学习设定中通常与多智能体匹配相关的指数级复杂度。