# Competing Bandits in Time Varying Matching Markets

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 21 Oct 2022.

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

- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards](https://mlsanity.com/paper/1405.3316/) (2014)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Learning in Multi-Stage Decentralized Matching Markets](https://mlsanity.com/paper/2102.06988/) (2021)
- [Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets](https://mlsanity.com/paper/2206.02344/) (2022)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)
- [Online Algorithms for Dynamic Matching Markets in Power Distribution Systems](https://mlsanity.com/paper/2003.06971/) (2020)

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

- [Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship](https://mlsanity.com/paper/2512.06758/) (2025)
- [Adaptive Bandit Algorithms for Contextual Matching Markets](https://mlsanity.com/paper/2605.28290/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

We study the problem of online learning in two-sided non-stationary matching markets, where the objective is to converge to a stable match. In particular, we consider the setting where one side of the market, the arms, has fixed known set of preferences over the other side, the players. While this problem has been studied when the players have fixed but unknown preferences, in this work we study the problem of how to learn when the preferences of the players are time varying and unknown. Our contribution is a methodology that can handle any type of preference structure and variation scenario. We show that, with the proposed algorithm, each player receives a uniform sub-linear regret of widetildeO(L1/2TT1/2) up to the number of changes in the underlying preferences of the agents, LT. Therefore, we show that the optimal rates for single-agent learning can be achieved in spite of the competition up to a difference of a constant factor. We also discuss extensions of this algorithm to the case where the number of changes need not be known a priori.