# Adaptive Bandit Algorithms for Contextual Matching Markets

arXiv: https://arxiv.org/abs/2605.28290 · HTML: https://mlsanity.com/paper/2605.28290/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 17 of 17)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [The Elliptical Potential Lemma Revisited](https://mlsanity.com/paper/2010.10182/) (2020)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [Adaptive Exploration-Exploitation Tradeoff for Opportunistic Bandits](https://mlsanity.com/paper/1709.04004/) (2017)
- [Dynamic Matching Bandit For Two-Sided Online Markets](https://mlsanity.com/paper/2205.03699/) (2022)
- [Competing Bandits in Time Varying Matching Markets](https://mlsanity.com/paper/2210.11692/) (2022)
- [A Contextual Combinatorial Bandit Approach to Negotiation](https://mlsanity.com/paper/2407.00567/) (2024)
- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)
- [Bandit Learning in Housing Markets](https://mlsanity.com/paper/2511.12629/) (2025)

## Built on by (most cited first, 1 of 1)

- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)

## Abstract (arXiv)

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.