Department of Industrial Engineering & Decision Analytics [Joint IEDA/ISOM seminar] - Match Made with Matrix Completion: Efficient Offline and Online Learning in Matching Markets
Online matching markets face increasing needs to accurately learn the matching qualities between demand and supply for effective design of matching policies. However, the growing diversity of participants introduces a \emph{high-dimensional} challenge in practice, as there are a substantial number of \emph{unknown} matching rewards and learning all rewards requires a large amount of data. We leverage a natural low-rank matrix structure of the matching rewards in these two-sided markets, and propose to utilize \emph{matrix completion} (i.e., the nuclear norm regularization approach) to accelerate the reward learning process with only a small amount of offline data. A key challenge in our setting is that the matrix entries are observed with \emph{matching interference}, distinct from the independent sampling assumed in existing matrix completion literature. We propose a new proof technique and prove a near-optimal average accuracy guarantee with improved dependence on the matrix dimensions. Furthermore, to guide matching decisions, we develop a novel ``double-enhancement'' procedure that refines the nuclear norm regularized estimates and further provides a near-optimal entry-wise estimation. Our paper makes the first investigation into adopting matrix completion techniques for matching problems. We also extend our approach to online learning settings for optimal matching and stable matching by incorporating matrix completion in multi-armed bandit algorithms. We present improved regret bounds in matrix dimensions through reduced costs during the exploration phase. Finally, we demonstrate the practical value of our methods using both synthetic data and real data of labor markets.
Kan Xu is currently an Assistant Professor of Information Systems at Arizona State University, W. P. Carey School of Business. Previously, he completed my PhD degree from University of Pennsylvania, Department of Economics under the supervision of Hamsa Bastani. He received a B.S. in Mathematics and a B.A. in Economics from Tsinghua University, and a M.S. in Statistics from University of Chicago.
His research focuses on developing novel machine learning methods for data-driven decision making practices, with applications to healthcare, textual analytics, digital platform, and pricing. In particular, he has designed tools for sequential decision making (e.g., bandits, reinforcement learning), collaborative decision making (e.g., multitask learning, transfer learning), and decision making with unstructured (e.g. natural language processing (NLP)) or matrix form (e.g., matrix completion).