# Beyond log2(T) Regret for Decentralized Bandits in Matching Markets

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 12 Mar 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Collaborative Learning of Stochastic Bandits over a Social Network](https://mlsanity.com/paper/1602.08886/) (2016)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Learning Strategies in Decentralized Matching Markets under Uncertain Preferences](https://mlsanity.com/paper/2011.00159/) (2020)
- [Selfish Robustness and Equilibria in Multi-Player Bandits](https://mlsanity.com/paper/2002.01197/) (2020)
- [Game of Thrones: Fully Distributed Learning for Multi-Player Bandits](https://mlsanity.com/paper/1810.11162/) (2018)
- [Multiplayer Bandit Learning, from Competition to Cooperation](https://mlsanity.com/paper/1908.01135/) (2019)
- [Competing Bandits: The Perils of Exploration Under Competition](https://mlsanity.com/paper/2007.10144/) (2020)
- [Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship](https://mlsanity.com/paper/2006.15166/) (2020)

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

- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Deep Learning for Two-Sided Matching](https://mlsanity.com/paper/2107.03427/) (2021)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Decentralized Learning in Online Queuing Systems](https://mlsanity.com/paper/2106.04228/) (2021)
- [Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility](https://mlsanity.com/paper/2401.01528/) (2024)
- [Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning](https://mlsanity.com/paper/2410.04376/) (2024)
- [Competing for Shareable Arms in Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2305.19158/) (2023)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)
- [Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints](https://mlsanity.com/paper/2301.10230/) (2023)
- [Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty](https://mlsanity.com/paper/2501.03018/) (2025)
- [Competing Bandits in Matching Markets via Super Stability](https://mlsanity.com/paper/2506.15926/) (2025)
- [Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach](https://mlsanity.com/paper/2407.21294/) (2024)
- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)
- [Bandit Learning in Matching Markets: Utilitarian and Rawlsian Perspectives](https://mlsanity.com/paper/2412.00301/) (2024)
- [Online Learning and Equilibrium Computation with Ranking Feedback](https://mlsanity.com/paper/2603.19221/) (2026)
- [Probably Correct Optimal Stable Matching under Two-Sided Uncertainty](https://mlsanity.com/paper/2607.04824/) (2026)
- [Competing Bandits in Decentralized Contextual Matching Markets](https://mlsanity.com/paper/2411.11794/) (2024)
- [Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship](https://mlsanity.com/paper/2512.06758/) (2025)
- [Regret Analysis of Sleeping Competing Bandits](https://mlsanity.com/paper/2603.19700/) (2026)
- [Adaptive Bandit Algorithms for Contextual Matching Markets](https://mlsanity.com/paper/2605.28290/) (2026)
- [Double Auctions with Two-sided Bandit Feedback](https://mlsanity.com/paper/2208.06536/) (2022)
- [PPA-Game: Characterizing and Learning Competitive Dynamics Among Online Content Creators](https://mlsanity.com/paper/2403.15524/) (2024)
- [Learning in Matching Games with Bandit Feedback](https://mlsanity.com/paper/2506.03802/) (2025)
- [Stochastic Matching Bandits with Rare Optimization Updates](https://mlsanity.com/paper/2509.04194/) (2025)
- [Learn to Match: Two-Sided Matching with Temporally Extended Feedback](https://mlsanity.com/paper/2606.06744/) (2026)
- [Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning](https://mlsanity.com/paper/2606.19883/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

We design decentralized algorithms for regret minimization in the two-sided matching market with one-sided bandit feedback that significantly improves upon the prior works (Liu et al. 2020a, 2020b, Sankararaman et al. 2020). First, for general markets, for any varepsilon > 0, we design an algorithm that achieves a O(log1+varepsilon(T)) regret to the agent-optimal stable matching, with unknown time horizon T, improving upon the O(log2(T)) regret achieved in (Liu et al. 2020b). Second, we provide the optimal Theta(log(T)) agent-optimal regret for markets satisfying uniqueness consistency -- markets where leaving participants don't alter the original stable matching. Previously, Theta(log(T)) regret was achievable (Sankararaman et al. 2020, Liu et al. 2020b) in the much restricted serial dictatorship setting, when all arms have the same preference over the agents. We propose a phase-based algorithm, wherein each phase, besides deleting the globally communicated dominated arms the agents locally delete arms with which they collide often. This local deletion is pivotal in breaking deadlocks arising from rank heterogeneity of agents across arms. We further demonstrate the superiority of our algorithm over existing works through simulations.