Adaptive Bandit Algorithms for Contextual Matching Markets

We study bandit learning in matching markets, where players and arms constitute the two market sides, and the players' utilities are linear in the arm contexts. In each round, new arms arrive with observable contexts. Then, the algorithm matches them to players, aiming to minimize each player's regret against a stable matching benchmark. This contextual structure creates significant complexity: subtle context shifts can slightly alter one player's utility while completely reconfiguring the underlying benchmark, causing large regret spikes for others. We address this in two settings: stochastic contexts, drawn from a latent distribution, and adversarial contexts, which may be arbitrary. For the stochastic case, we introduce a novel minimum preference gap to capture learning difficulty and provide a fully adaptive algorithm with an instance-dependent poly-logarithmic regret upper bound. We also establish matching instance-independent regret upper and lower bounds under a mild distributional assumption. For the adversarial setting, we propose a tractable regret notion that remains valid under arbitrary contexts and achieves an instance-independent sublinear regret bound via an adaptive algorithm.

Online platforms like freelance marketplaces or ride-sharing apps face a challenge: they need to match workers with jobs, but a worker’s preference for a job (e.g., based on pay or difficulty) is unknown and must be learned over time. Worse, small changes in a job’s description can completely scramble which worker should get which job, causing unfairness and inefficiency. We created two smart, self-adjusting algorithms. One handles predictable, random job postings (like routine tasks). The other handles worst-case scenarios where job details might change arbitrarily or even be manipulated. Both algorithms learn workers’ hidden preferences on the fly, balancing exploration (trying new matches) with exploitation (using what they know) to keep things fair. Our work provides the first fully adaptive, “no‑prior‑knowledge‑required” solutions for online matching. This means platforms can automatically maintain fair and stable matches even in unpredictable environments, from gig economy apps to college admissions, without needing to know how tricky the situation is beforehand.