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

In many real-world scenarios, such as warehouse automation or disaster response, a central platform must repeatedly match a pool of robots to a set of human agents. Because robot capabilities are often unknown or complex, the platform must learn these features over time while simultaneously maximizing the total reward of the human-robot teams. The authors investigate how to solve this online matching problem efficiently under a linear reward structure.

To address the combinatorial complexity of this problem, the authors propose LinMatch, an algorithm based on the principle of Optimism in the Face of Uncertainty (OFU). The algorithm maintains confidence intervals for the unknown feature vectors of each robot using ridge regression. In each round, it constructs an optimistic estimate of the reward for every possible human-robot pair. The problem of finding the optimal matching is then recast as a maximum weighted matching problem, which the authors show can be solved efficiently using the Hungarian algorithm in polynomial time.

The authors provide both upper and lower bounds for the algorithm's performance. They prove that LinMatch achieves an instance-independent regret bound of O(d * sqrt(MKT)), where d is the feature dimension, M is the number of humans, K is the number of robots, and T is the total number of rounds. Furthermore, they establish a minimax lower bound of Omega(sqrt(dKT)), demonstrating that the sqrt(T) dependence is optimal. Numerical simulations confirm that LinMatch consistently outperforms explore-then-commit (ETC) strategies, exhibiting lower variance and more stable performance in dynamic environments.

This work provides a rigorous theoretical foundation for online matching in multi-agent systems. By recasting a complex combinatorial bandit problem into a standard linear programming framework, the authors offer a scalable and computationally efficient solution for real-world applications like task allocation, resource management, and recommendation systems where agent features are not known a priori.