Contextual Linear Bandits for Matching Markets

An extensive line of work studies bandit learning in two-sided matching markets, where the goal is to learn unknown preferences and converge to a stable matching through repeated interactions. Existing approaches predominantly focus on the tabular setting, where regret guarantees scale with the number of arms $K$. This dependence severely limits scalability in large markets commonly encountered in real-world applications. In this paper, we study contextual matching markets and leverage arm features to accelerate preference learning. For the strict preference setting, we propose a decentralized G-optimal design-based algorithm that achieves a player-optimal regret of $O\left(\max \{d\log T/{\Delta }^2,Nd{\max }_j{\pi }_i(j)\log T/{\Delta }^2\}\right)$, where $N$ denotes the number of players, $d$ denotes the feature dimension, $T$ is the time horizon, ${\pi }_i(j)$ denotes the sampling probability of arm $j$ and $\Delta$ is the preference gap. This result significantly improves scalability when $d\ll K$. We further extend our framework to matching markets with indifference and develop an arm-proposing exploration algorithm that achieves a regret of $O\left(N{d}^2{\log }^{2}T/{\Delta }^2\right)$. To the best of our knowledge, this is the first work that simultaneously addresses both contextual information and tied preferences. In addition, to characterize the hardness of our problem, we establish an instance-dependent regret lower bound of $\Omega \left(\max \{N\log T/{\Delta }^2,d\log T/\Delta \}\right)$. Our framework also recovers existing guarantees in the tabular setting as a special case. Experiments demonstrate that our methods substantially outperform existing approaches in large-scale markets.