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

Problem Formulation
The paper addresses the challenge of online multi-human multi-robot teaming, a scenario where a learner must assign a fixed pool of $K$ robots with unknown capabilities to varying sets of $M$ human agents over $T$ rounds. The objective is to maximize the cumulative reward generated by these human-robot teams. The problem is framed within a linear matching bandit framework. The core difficulty lies in two aspects: the "intractable arm space," where treating every unique matching as a distinct bandit arm leads to exponential growth, and "combinatorial complexity," where matching constraints interconnect rewards and complicate optimization.

The authors assume a linear reward structure where the expected reward of a team formed by human agent $m$ (with known feature vector $X_{m,t} \in \mathbb{R}^d$) and robot $k$ (with unknown feature vector $\theta_k \in \mathbb{R}^d$) is given by the inner product $X_{m,t}^\top \theta_k$. While human features are observable (derived from profiles or task context), robot features are unknown due to the complexity and lack of transparency in advanced AI systems. The learner observes the features of arriving humans, selects a matching (an injection function from humans to robots), and receives noisy rewards.

Methodology: LinMatch Algorithm
To solve this, the authors propose LinMatch, an online learning algorithm based on the "Optimism in the Face of Uncertainty" (OFU) principle. The algorithm operates in rounds and consists of the following steps:

1. Confidence Interval Construction: Using ridge regression, LinMatch estimates the unknown feature vectors $\theta_k$ for each robot. It maintains a covariance matrix $V_{k,t}$ and a weighted sum of rewards $H_{k,t}$ for each robot based on historical assignments. This allows the construction of an ellipsoidal confidence interval $\hat{\Theta}_{k,t}$ for each $\theta_k$, ensuring the true parameter lies within the interval with high probability.
2. Optimistic Matching: In each round, the algorithm computes an "optimistic" matching. Instead of using the point estimates of $\theta_k$, it selects the parameter vectors within the confidence intervals that maximize the expected total reward.
3. Efficient Solving via Linear Programming: A key technical contribution is the reformulation of the optimistic matching problem. The authors demonstrate that the mixed-integer program required to find the matching that maximizes the sum of inner products over the confidence sets can be decoupled. By defining optimistic reward estimates $\tilde{y}_{mk,t}$ for each human-robot pair, the problem reduces to a standard maximum weighted matching problem in a bipartite graph. This can be solved efficiently in $O(K^3)$ time using the Hungarian algorithm.

Key Contributions and Theoretical Results
The paper makes two primary contributions:

1. Algorithmic Reformulation: It recasts the optimistic matching problem in each round as a linear program of maximum weighted matching, making it computationally tractable via the Hungarian algorithm.
2. Tight Regret Bounds: The authors provide rigorous theoretical guarantees for LinMatch.
   • Upper Bound: They establish an instance-independent upper bound on the cumulative regret of $\tilde{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 time horizon.
   • Lower Bound: They prove a minimax lower bound of $\Omega(d\sqrt{MKT})$ for any matching policy in this setting.
   • Optimality: The matching of the upper and lower bounds establishes a tight optimal regret rate of $\tilde{\Theta}(d\sqrt{MKT})$. This demonstrates that LinMatch achieves the strictly optimal achievable regret with respect to all problem parameters ($T, d, M, K$).

Experimental Results
The authors validate LinMatch through numerical simulations with $K=20$ robots and $M=10$ humans.

• Comparison with ETC: LinMatch is compared against an Explore-Then-Commit (ETC) algorithm. While ETC can achieve sublinear regret with an optimal exploration phase length, it suffers linear regret if the exploration is insufficient. LinMatch demonstrates more consistent performance with a narrower confidence interval compared to ETC.
• Regularization Sensitivity: Experiments varying the regularization parameter $\lambda$ show that while the theoretical upper bound requires $\lambda \ge L^2$, in practice, smaller values (e.g., $\lambda=1$) often yield lower regret, suggesting the theoretical condition is conservative.

Significance and Scope
The paper claims that LinMatch is the first work to show that the instance-independent optimal achievable regret rate for matching problems with a linear bandit structure is precisely $\tilde{\Theta}(d\sqrt{MKT})$. The proposed approach is designed to be applicable beyond human-robot teaming to any centralized matching problem with linear features, such as housing allocation and recommendation systems. The work highlights that by leveraging the linear structure and efficient combinatorial optimization, one can overcome the exponential complexity typically associated with multi-agent matching in online learning settings.