# Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 16 Aug 2024.

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

- [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)
- [Matching while Learning](https://mlsanity.com/paper/1603.04549/) (2016)
- [Player-optimal Stable Regret for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2307.10890/) (2023)
- [Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets](https://mlsanity.com/paper/2206.02344/) (2022)
- [Adaptive Matching for Expert Systems with Uncertain Task Types](https://mlsanity.com/paper/1703.00674/) (2017)
- [Decentralized Competing Bandits in Non-Stationary Matching Markets](https://mlsanity.com/paper/2206.00120/) (2022)
- [Converging to Stability in Two-Sided Bandits: The Case of Unknown Preferences on Both Sides of a Matching Market](https://mlsanity.com/paper/2302.06176/) (2023)

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

- [Competing Bandits in Matching Markets via Super Stability](https://mlsanity.com/paper/2506.15926/) (2025)
- [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)
- [Learning in Matching Games with Bandit Feedback](https://mlsanity.com/paper/2506.03802/) (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)

## Abstract (arXiv)

Online learning in a decentralized two-sided matching markets, where the demand-side (players) compete to match with the supply-side (arms), has received substantial interest because it abstracts out the complex interactions in matching platforms (e.g. UpWork, TaskRabbit). However, past works assume that each arm knows their preference ranking over the players (one-sided learning), and each player aim to learn the preference over arms through successive interactions. Moreover, several (impractical) assumptions on the problem are usually made for theoretical tractability such as broadcast player-arm match Liu et al. (2020; 2021); Kong & Li (2023) or serial dictatorship Sankararaman et al. (2021); Basu et al. (2021); Ghosh et al. (2022). In this paper, we study a decentralized two-sided matching market, where we do not assume that the preference ranking over players are known to the arms apriori. Furthermore, we do not have any structural assumptions on the problem. We propose a multi-phase explore-then-commit type algorithm namely epoch-based CA-ETC (collision avoidance explore then commit) (textttCA-ETC in short) for this problem that does not require any communication across agents (players and arms) and hence decentralized. We show that for the initial epoch length of Tcirc and subsequent epoch-lengths of 2l/γ Tcirc (for the l-th epoch with γ ∈ (0,1) as an input parameter to the algorithm), textttCA-ETC yields a player optimal expected regret of Oleft(Tcirc (fracK log TTcirc Delta2)1/γ + Tcirc (fracTTcirc)γright) for the i-th player, where T is the learning horizon, K is the number of arms and Delta is an appropriately defined problem gap. Furthermore, we propose a blackboard communication based baseline achieving logarithmic regret in T.