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

arXiv: https://arxiv.org/abs/2606.29221 · HTML: https://mlsanity.com/paper/2606.29221/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 40 references that are in the map.
- First posted on arXiv 28 Jun 2026.

## Builds on (most cited first, 13 of 13)

- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [DCM Bandits: Learning to Rank with Multiple Clicks](https://mlsanity.com/paper/1602.03146/) (2016)
- [Scalable Operator Allocation for Multi-Robot Assistance: A Restless Bandit Approach](https://mlsanity.com/paper/2111.06437/) (2021)
- [Traversing Supervisor Problem: An Approximately Optimal Approach to Multi-Robot Assistance](https://mlsanity.com/paper/2205.01768/) (2022)
- [Simultaneous Human-robot Matching and Routing for Multi-robot Tour Guiding under Time Uncertainty](https://mlsanity.com/paper/2201.10635/) (2022)
- [Initial Task Allocation for Multi-Human Multi-Robot Teams with Attention-based Deep Reinforcement Learning](https://mlsanity.com/paper/2303.02486/) (2023)
- [Interactive Learning with Pricing for Optimal and Stable Allocations in Markets](https://mlsanity.com/paper/2212.06891/) (2022)

## Abstract (arXiv)

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 Theta(√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.