# Probably Correct Optimal Stable Matching under Two-Sided Uncertainty

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 6 Jul 2026.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [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)
- [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)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [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)
- [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)
- [Stable Fractional Matchings](https://mlsanity.com/paper/1902.06698/) (2019)

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

- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling two-sided uncertainty and by exploiting partial preference information. A central ingredient is the notion of pervasive stable matching, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the optimal stable matching that avoid dependence on the minimum reward gap Deltamin.