Online Matching with Bayesian Rewards

We study in this paper an online matching problem where a central platform needs to match a number of limited resources to different groups of users that arrive sequentially over time. The reward of each matching option depends both on the type of resource and the time period the user arrives. The matching rewards are assumed to be unknown, but drawn from probability distributions that are known a priori. The platform then needs to learn the true rewards online based on real-time observations of the matching results. The goal of the central platform is to maximize the total reward from all the matchings without violating the resource capacity constraints. We formulate this matching problem with Bayesian rewards as a Markovian multiarmed bandit problem with budget constraints, where each arm corresponds to a pair of a resource and a time period. We devise our algorithm by first finding policies for each single arm separately via a relaxed linear program, and then assembling these policies together through judicious selection criteria and well-designed pulling orders. We prove that the expected reward of our algorithm is at least $(\sqrt{2}-1)/2$ the expected reward of the optimal algorithm. In particular, in the single-resource case, we prove the ratio is at least $\sqrt{2}-1$. We also design numerical experiments to verify our algorithm's performance guarantee, and compare the algorithm with alternative heuristics to illustrate the algorithm's good and robust performance in various settings