用线性匹配强化学习，让多机器人自动匹配人类团队。
A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming
- 将匹配问题转为线性规划，每轮用匈牙利算法做乐观分配。
- 理论证明最优后悔值为Θ(√T)，随轮数增长缓慢上升。
- 适合需动态匹配的场景，如资源分配、推荐系统。
本文从线性匹配强化学习视角解决在线多人多机器人匹配问题，即在多轮中将具有未知特征的机器人从固定池分配给不同人类群体。提出算法LinMatch，通过更新未知特征的置信区间，并在不确定性下进行乐观匹配。首先，将每轮的乐观匹配问题转化为最大权匹配的线性规划，可高效使用匈牙利算法求解；其次，给出匹配线性特征问题的新理论边界，证明总轮数为T时，最优可实现的后悔值为Θ(√T)。该算法与理论适用于广泛匹配场景，包括住房分配、推荐系统等。
原文摘要 · Abstract (English)
We address the problem of online multi-human multi-robot matching through the lens of a linear matching bandit framework, where a learner assigns robots with unknown features from a fixed pool to distinct sets of human agents over multiple rounds. To solve this problem, we propose LinMatch, an online learning algorithm that updates the confidence intervals of the unknown features and makes the optimistic matching under uncertainty. The contributions and novelty of this work are twofold. First, we recast the optimistic matching problem in each round as a linear program of maximum weighted matching, efficiently solvable by the celebrated Hungarian algorithm. Second, we provide novel bounds for matching with linear feature problems, showing that $Θ(\sqrt{T})$ is the optimal achievable regret with respect to the total number of rounds $T$. The proposed algorithm and bounds apply to a wide range of matching problems with applications beyond human-robot matching, such as housing allocation, recommendation systems, and more.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。