# Decentralized Competing Bandits in Non-Stationary Matching Markets

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 34 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem](https://mlsanity.com/paper/1711.03539/) (2017)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems](https://mlsanity.com/paper/1802.08380/) (2018)
- [Learning Strategies in Decentralized Matching Markets under Uncertain Preferences](https://mlsanity.com/paper/2011.00159/) (2020)
- [On Slowly-varying Non-stationary Bandits](https://mlsanity.com/paper/2110.12916/) (2021)

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

- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets](https://mlsanity.com/paper/2408.08690/) (2024)
- [Competing Bandits in Time Varying Matching Markets](https://mlsanity.com/paper/2210.11692/) (2022)
- [Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship](https://mlsanity.com/paper/2512.06758/) (2025)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

Understanding complex dynamics of two-sided online matching markets, where the demand-side agents compete to match with the supply-side (arms), has recently received substantial interest. To that end, in this paper, we introduce the framework of decentralized two-sided matching market under non stationary (dynamic) environments. We adhere to the serial dictatorship setting, where the demand-side agents have unknown and different preferences over the supply-side (arms), but the arms have fixed and known preference over the agents. We propose and analyze a decentralized and asynchronous learning algorithm, namely Decentralized Non-stationary Competing Bandits (textttDNCB), where the agents play (restrictive) successive elimination type learning algorithms to learn their preference over the arms. The complexity in understanding such a system stems from the fact that the competing bandits choose their actions in an asynchronous fashion, and the lower ranked agents only get to learn from a set of arms, not dominated by the higher ranked agents, which leads to forced exploration. With carefully defined complexity parameters, we characterize this forced exploration and obtain sub-linear (logarithmic) regret of textttDNCB. Furthermore, we validate our theoretical findings via experiments.