{"ID":5937190,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T08:57:31.292890551Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04824","arxiv_id":"2607.04824","title":"Probably Correct Optimal Stable Matching under Two-Sided Uncertainty","abstract":"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 \\emph{two-sided uncertainty} and by exploiting \\emph{partial preference} information. A central ingredient is the notion of \\textbf{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 \\emph{optimal} stable matching that avoid dependence on the minimum reward gap $Δ_{\\min}$.","short_abstract":"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-ba...","url_abs":"https://arxiv.org/abs/2607.04824","url_pdf":"https://arxiv.org/pdf/2607.04824v1","authors":"[\"Andreas Athanasopoulos\",\"Anne-Marie George\",\"Christos Dimitrakakis\"]","published":"2026-07-06T08:57:30Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"stat.ML\"]","methods":"[\"LoRA\"]","has_code":false}