# Player-optimal Stable Regret for Bandit Learning in Matching Markets

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 20 Jul 2023.

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

- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [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)
- [Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets](https://mlsanity.com/paper/2203.03684/) (2022)
- [Learning Strategies in Decentralized Matching Markets under Uncertain Preferences](https://mlsanity.com/paper/2011.00159/) (2020)
- [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)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)

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

- [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)
- [Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets](https://mlsanity.com/paper/2408.08690/) (2024)
- [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)
- [Probably Correct Optimal Stable Matching under Two-Sided Uncertainty](https://mlsanity.com/paper/2607.04824/) (2026)
- [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)
- [Learning with Limited Shared Information in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2502.15338/) (2025)
- [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)
- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)

## Abstract (arXiv)

The problem of matching markets has been studied for a long time in the literature due to its wide range of applications. Finding a stable matching is a common equilibrium objective in this problem. Since market participants are usually uncertain of their preferences, a rich line of recent works study the online setting where one-side participants (players) learn their unknown preferences from iterative interactions with the other side (arms). Most previous works in this line are only able to derive theoretical guarantees for player-pessimal stable regret, which is defined compared with the players' least-preferred stable matching. However, under the pessimal stable matching, players only obtain the least reward among all stable matchings. To maximize players' profits, player-optimal stable matching would be the most desirable. Though citetbasu21beyond successfully bring an upper bound for player-optimal stable regret, their result can be exponentially large if players' preference gap is small. Whether a polynomial guarantee for this regret exists is a significant but still open problem. In this work, we provide a new algorithm named explore-then-Gale-Shapley (ETGS) and show that the optimal stable regret of each player can be upper bounded by O(Klog T/Delta2) where K is the number of arms, T is the horizon and Delta is the players' minimum preference gap among the first N+1-ranked arms. This result significantly improves previous works which either have a weaker player-pessimal stable matching objective or apply only to markets with special assumptions. When the preferences of participants satisfy some special conditions, our regret upper bound also matches the previously derived lower bound.