Search papers, labs, and topics across Lattice.
This paper studies bandit learning in contextual matching markets, where the goal is to minimize player regret against a stable matching benchmark when arms arrive with observable contexts. They address both stochastic and adversarial context settings, developing adaptive algorithms that account for the complexity arising from subtle context shifts that can reconfigure the benchmark. For stochastic contexts, they introduce a minimum preference gap and achieve instance-dependent poly-logarithmic regret, while for adversarial contexts, they propose a tractable regret notion with an instance-independent sublinear regret bound.
Even slight context changes in matching markets can drastically alter optimal matchings and tank player utility, but this new algorithm dynamically adapts to minimize regret in both stochastic and adversarial environments.
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.
