Competing Bandits in Matching Markets via Super Stability
Authors: Soumya Basu
Venue: ICML 2025 poster (2025)
Keywords: Bandits
Matching Markets
Stable Matching
Super Stability
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: Extended Gale-Shapley algorithm with exploration finds stable matchings in bandit learning with two-sided reward uncertainty.

Abstract: We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of `super-stability' from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incomplete information. By employing the Extended GS algorithm, our centralized algorithm attains a logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter.  This algorithm is further adapted to a decentralized setting with a constant regret increase.  Finally, we establish a novel centralized instance-dependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching in characterizing the complexity of stable matching with bandit feedback.

Competing Bandits in Matching Markets via Super Stability
Soumya Basu'
Abstract
However, this preference order is unknown a-priori, and must be elicited from noisy feedback by matching with the other side through repeated interactions. A stable matching is matching among the users and arms, where there is no blocking pair of user i and arm j such that i and j prefer each other compared to their current partner. The objective of the system is to converge one of multiple possible stable matching with low regret.
We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of "super- stability" from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incom- plete information. By employing the Extended GS algorithm, our centralized algorithm attains logarithmic pessimal stable regret dependent instance-dependent admissible gap param- eter. This algorithm is further adapted to a de- centralized setting with a constant regret increase. Finally, we establish a novel centralized instance- dependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching characterizing the com- plexity of stable matching with bandit feedback.
Unlike most prior works, except select few (Pagare & Ghosh, 2024; Zhang & Fang), which are limited to user side uncertainty we consider two-sided uncertainty, where all users and arms need to learn their respective preferences. Our work also considers general matching markets. In an- other direction, the existing literature has been limited to combining bandit learning methods with the standard Gale- Shapley algorithm. One major shortcoming of this approach is the need to learn the top N ranks for general matching market with N users and K arms where N < K. This does not capture the intrinsic complexity of the underlying stable matching problem. We move beyond the standard Gale- Shapley algorithm, and harness a seminal work of Irving (1994) to construct an algorithm with regret that grows with the intrinsic complexity of the problem.
1. Introduction
In order to understand the weakness of Gale-Shapley algo- rithm let us first review the task at hand. Given the history, at each round users and arms can construct their respective par- tially recovered rankings, and require to find a stable match using these partial rankings. However, using Gale-Shapley algorithm over partially recovered ranking, breaking ties in uncertain manner, the system arrives at weakly stable matching. This is a concept of stability defined in Irving (1994) for partial rankings, where matching is weakly sta- ble if there no blocking pair of user and arm j such that and j strictly prefers each other compared to their current partner. The problem with weakly stable matching as ties in preferences are resolved weakly stable matching can turn out have blocking pairs. Therefore, it is not stable under the true full-rankings. The only way to ensure exploration is complete is by resolving the top N ranks for all the agents and ensure that a weakly stable matching is indeed stable under the true full-rankings.
The problem of finding stable matching in two-sided matching market has gained considerable attention in the past few years (Das & Kamenica, 2005; Liu et al., 2020: Sankararaman et al., 2021; Basu et al., 2021; Liu et al., 2021; Jagadcesan et al., 2021; Hosseini et al., 2024; Ghosh et al., 2024). major motivation is the two-sided matching market provides model to study multiple real world sys- tems such as crowd- sourcing markets like UpWork or Task Rabbit (Li et al., 2019; Zhang et al., 2023), ride-sharing systems (Johari et al., 2021) as well as classical markets like matching students in college programs (Gale & Shapley, 1962), matching organ donors with recipients (Reddy et al., 2013). In a two-sided market there are two types of agents, demand side (users) and supply side (arms). Each agent has implicit preference order for the other side agents.
'Google, New York. Correspondence to: Soumya Basu <basu- soumya@ goom...com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Interestingly, Irving (1994) we can also find way to circumvent this issue leveraging the concept of super stable

---

Competing Bandits in Matching Markets via Super Stability
matching. A matching is super stable under partial rankings of the agents if there is no blocking pair of user i and arm j such that i and j strictly prefers or is indifferent to each other compared to their current partner. If at any stage a super stable matching is found it is ensured that this is a stable matching under the true complete full-rankings. The Extended Shapley algorithm in Irving (1994) ensures whenever a super stable matching exists we can recover one, otherwise determine none exists. This provides with way to adaptively exploit when a super slable matching is present under the recovered partial rank, or explore more when it is absent.
to Spieker (1995), we define the set of admissible partial ranks that are compatible with the true full rank, and whose compatible full ranks all share at least one stable matching with the true full rank. If the UCB-LCB- based partial rank falls within this admissible set, a true stable matching is guaranteed. Let AA represent the maxi- mum of the minimum gaps, where the minimum gap for a given partial rank the smallest difference between any two unequally ranked arms for any user (and vice versa). We demonstrate that each user and arm incurs an expected cu- mulative pessimal stable regret of O(K log(T) /42) over T rounds. This improves upon existing results that achieve O K log (T) min), as A 2 Amin- Our experiments confirm the superior performance of our proposed algorithm compared to existing Gale-Shapley-basee approaches. We then demonstrate how, using only two shared boolean flags, users and arms can emulate the centralized algorithm in decentralized setting, incurring only an additional O(N2) cumulative regret, independent of the time window. We also discuss the communication trade-offs involved. This adaptation from centralized to decentralized settings may have broader applicability in two-sided matching markets.
We first show how Extended Shae-lh algorithm can be used with an UCB-LCB based rank recovery in a centralized setting, and prove that we can achieve a logarithmic pes- simal stable regret that depends admissible gup parameter. Notably, our method does not require resolving top N ranks for all agents and adapt to the problem hardness. Next, using a 2-bit shared feedback we show how this centralized algorithm can be modified to a de- centralized algorithm at the cost of constant regret increase. Finally, we present new instance-dependent pessimal sta- ble regret lower bound for general instances in centralized setting. Our lower bound depends on the admissible gap, and shows that admissible gap is indeed an intrinsic hard- ness parameter for bandits in matching markets. It also highlights how the super-stable matching plays a pivotal role in the informational bottlenecks for this problem.
cestance-dependeee
Instance-dependent regret lower bound: We establish the first ristanceddepenent regret lower bound for stable matching in the centralized (and consequently decentralized) setting under two-sided uncertainty. This bound focuses on binary stable regret, quantifying the number of times a sta- ble matching is not achieved. Building upon the framework of Combes et al. (2017) we formulate this lower bound as an optimization problem over possible matching mar- ket instances, introducing a novel constraint set. Crucially, instances sharing a stable matching with the true instance do not contribute to the lower bound. We derive explicit lower bounds for specific market structures, including gen- eral serial dictatorships and markets with redundant arms, demonstrating a scaling of 2 (KKKs log(T)) where Keff. Dess are instance-dependent parameters. Through a dual formulation, we reveal a fundamental connection between our lower bound and specific set covers of the boundary of the admissible partial rank set. While a tight regret bound remains open, we anticipate that the structure of admissible partial rank set will be pivotal in achieving it.
Our main contributions are as follows:
Sall-SSappey-baseee bandit algorithms suffer from a key limitation: under partial prefer- ence information, they can only guarantee convergence to a weakly stable matching, which may not be a true stable matching. However, as shown by Irving (1994), given partial ranking, it is possible to find a super-stable matching if one exists or to determine that none exists. Crucially, if a super-stable matching exists for partial rank that is compat- ible with the true full rank, then that super-stable matching is guaranteed to be a true stable matching. Since a UCB- LCB-based partial rank is compatible with the true full rank with high probability, the resulting super-stable matching (if found) incurs no pessimal stable regret. This insight opens a novel al algorithmic pathway for addressing bandit problems in two-sided matching markets with uncertainty.
A new algorithmic pathway:
2. Problem Formulation
We consider the matching markets with two-sided uncer- tainty. There are N users and K arms. We are interested in setting where the number of users is less or equal to the number of arms N < K.
Algorithms for two sided uncertainty: Building on this insight, we first develop a centralized algorithm that con- structs a UCB-LCB--basd based partial rank and attempts to re- cover a super-stable matching using the Extended-GS al- gorithm (Irving, 1994). If no such super-stable matching exists, the algorithm defaults to round-robin exploration. Exploiting the structure of the super-stable matching set due
Each user i E [N] has a valuation for an arm j E [K] denoted by Pt.j. Similarly, each arm j E [K] has a valuation for a user i E (N] denoted by T3.-- These valuations are a
2

---

Competing Bandits in Matching Markets via Super Stability
priori unknown to the users and arms, and can be learned only by matching with the other side. We denote by Fu,a as
exists a user-pessimal matching M()) E Stable (Fus Fa) such that for each user i E [N] the reward Hipess Mi,Mitu) is the lowest among all possible partner in stable
the preference full-rank of user i E [N] over the arms [K], and Fa.j as the preference full-rank of arm j E [K] over the users [M]. We denote the set of full-ranks by (Fu; Fa)
matching. Similarly, we define the stable arm -em-eessmall match M(a) and the arm-pessimal reward "j.eess = J,,M, '(a) for each arm j E [K]. We define the expected pessimal stable regret for the users [N] and the arms E [K] in rounds as
(fFa,s 1 E [M]] [Fa. j E [K])).
The system evolves in rounds, while in each round user can match with at most one arm, and vice versa. When an arm is matched with multiple users in round, there is a collision, and all the users involved in the collision receive zero reward, and collision signal. Let us call the match for user i E [N]] in round f as m, (t) E [K] U {0}. and the match for an arm j E [K] in round t as m; (t) E [M] Here, mt(t) = 0 implies the user i is unmatched, and m, (t) 0 implies arm j remains unmatched. For each pair (t.j) E m(() for i E [A] and j E [K] the user and arm j receives noisy rewards (t) and (t), respectively. The rewards are given as
T
E RR, (T)) = pesss
Σ
Σ
Pry 5),
1=1
jE[K]
E[R.. = T Tiipp
Σ
E [M[]
Ja. (1) = =i).
We also consider the binary stable regrel where regret of failure to find a stable match is counted as 1, and otherwise 0 each round, i.e.
Yi(1) = (t)m)(() + "K (t) (1) if (t)= # 0, else O, (t) = (,,m"((1) + 1 1//m5'0000 (8) if m7' (t) * 0, else 0,
T
B[Ro/1(T))
= Σ P(m(t) & Stable Fu, Fa)).
1=1
where ne. (t) and (t) are independent 1-subgaussian noise for i E [N] and j E [K].
2.1. Partial Rank and Super Stable Matching
In this section, we present the structure of the super-stable matching due to Spieker (1995). In order to state the results we first define partial rank and super-stable matching.
We consider two versions of the system that differs in how the matching is formed in each round.
Centralized: In this setting, in each round the arms and users reveal their learned preferences to central platform. The central platform arrives to a matching in that round.
Definition 2.2 (Partial Rank). A partial rank (Pu, Pa) over N users and K arms is defined as a set of directed ayclic graphs (DAG) Pu,i for each E [N] and Pag for each E [K]. Each DAG Pu, is defined by a set of directed edges (j.j") C [K] x [K], and satisfies j >P.,, j' if and only if there exists a directed path from j to j". Each DAG Paj is defined analogously. Let define the set of all partial ranks for N users, and K arms as P(N,K)
Decentralized: In this setting, in each round the users can propose to the arms (possibly multiple). Each arm can ac- cept and match with at most one user, while rejecting all the unmatched proposing users. Additionally, users have access to shared flags (binary semaphores)! After receiving the signals from the arms, the users modify the shared bits and finally use the updated shared bits to match with arms.
Definition 2.3 (Compatible Full Rank). A partial rank (P,,P') P.) is compatible with a partial rank (Pa. Pa) ifr any pair of users i, i' E [N]. and any pair of arms j.j' E (K), J = jr x j. and > ==> 1' i. P
In each round, the objective of all the users and the arms are trying to construct stable match defined as below.
Pr. The set of all full ranks compatible with a partial rank (Pu, Pa) is denoted as FullRank( Pu., Pa).
Pe.
Definition 2.1 (Stable Match). A matching M is called stable under a full rank (Fa, if there is no pair user [K] such that simultaneously user
i E [N], and arm prefers to arm j over her match M,, and arm prefers user i over its match M, 1 The set of all super-stable matching of the partial rank (Fu,, Fa) is denoted as (a,ble(F',,A F.).
If a full rank (Fa, Fa) is compatible with a partial rank (Pu, Pa). then there exists a way of breaking ties (by adding more directed edges) in the partial rank (Pu, Pa) to reach (Fu, Fa). The reversal of the process takes us from full rank to compatible partial rank.
In general, there are multiple stable matching given a full rank (Fur F.) which we denote by Stable(F,,, Fa). There
We now define the notion of super-stability for partial rank, and follow it up with a proposition due to Spieker (1995) that shows how relates to the compatible full ranks.
'hhared information is used in the literature to avoid technical difficulties pertaining communication design, e.g. (user, arm) broadcast in (Liu et al., 2021; Kong & Li, 2023; Pagare& & Ghosh, 2024). It is possible make the algorithm fully decentralized with an additional (l)og(T)) regret rounds.
Definition 2.4 (Super-Stare Stable Match). A matching M is called super-stable under a partial rank (Pu, Pa) if there is
3

---

Competing Bandits in Matching Markets via Super Stability
no pair user i E [M], and arm j E [K] such that simultane- ously user i prefers or is indifferent to arm over her match ( and arm prefers or is indifferent to user i over its match M- (j). The set of all stper-stable matching of the partial rank (Pu, Pa) is denoted as SuperStable( Pa, Pa).
Algorithm 1: Centralized Two-Sided Matching Bandit
Exploration Index: Fex f- 0
Initial Ranking: Pa. (1) <- [[K]] for all i e [N],
(1) + [[[]]] for all i E [K]
3 for 2 1 do
Proposition 2.3. [Adaptedrron Spieker [1995]] For par- tial ranking (Pu: Pa), the set of super-stable matching the
The centralized platform receives the partial ranks:
users. (t) = (t). : i [M]] and
5
(possibly empty) intersection of all the stable matching of
arms Pa(() (Pa.. : E [K]].
full ranks (Fas Fa) compatible with (Pus Pa),
7
Obtain Matable <- EXTENDED (PA (P))
if Mstahle = then
CaperStable(Pu..ee Pa)
Play: (t) <- {m) = (i Tew) mod K}
(Fs P.P.B..DEPlllRann......... Stable(Fu: Fa).
10
Increase exploration index: Tex f Tea +
else
From the above proposition, given a full rank we define a set of partial match, namely admissible partial rank, for which super-stable match is always stable under the specific full rank.
12
Trim and play matching:
(t) < {(i, arg max,em, (.uccb,,(t))
(i, E Matabll
for each pair (i, E (t) do
Definition 2.6 (Admissible Partial Rank), For a given full rank (Fa, Fa), we define partial rank (Pa, Pa) to be ad- missible if and only if (Fa, Fa) E FullRank(Pu: Pa) and is SuperStable(Pur- Pa) * 0. We define the set of admissible partial rank instances as A(Fu, Fa).
User i receives reward (t), and arm j
receives reward (,,((t) User and arm j updates the partial rank Pu,(l + 1) and Pa., 1) (Eq. (3))
It follows from Proposition 2.5 that for any partial ranking in the set A(Fa, Fa) super-stable match is stable match for the true Stable matching instance (Fu, Fa).
y-leb,,(t)
(t,a(t) v 6 log(t)) logg(t//mu)(
(2)
Corollary 2.7. For full rank (Fu, Fe), for any admis- sible partial rank P.) E A(Fu,Fa) and each super- stable matching M E SuperStable(P, Pa) we have M E Stable(Fa. Fa).
j' j if y-ucbs, (1) < (1)
Pl.(()-
3 if p-ucbs, (t) < p- (t),
8 = otherwise.
i' > i i y-ucb,, < x-1cbj,;' (t):
3. Centralized Two-Sided Matching Bandit
Pa.(t)
1 i if y-ubb,, x (1) < 7lob),,(1);
(3)
8 = i otherwise.
In this section, we present centralized algorithm that re- covers a stable match with uncertainty of the rewards on both sides of the market. Each agent and arm maintain their own partial rankings based on UCB-LCB (similar to Kong & Li (2023)). Similarly Liu et al. (2020) in each round, users share their 1-8-LLCB-baseed partial rankings with the centralized platform. The centralized platform then uses the partial ranking and finds super-stable match if it ex- ists using the Extended-Gale Shapley algorithm in Irving (1994) (given as Algorithm 2). If such a match does not exist, then using a round-robin schedule, the centralized platform explores.
Here for round for i [N), arm j E [K], for user i the mean reward for arm is Pa,((), for arm j the mean reward for user is (1), and number of matches between user i and arm j is ni (t) as defined in the Appendix C.
3.1. Regret Upper Bound
We obtain logarithmic regret with two-sided uncertainty. Our result relies on few key properties of the system. Firstly, we know from Kong & Li (2023) that with high probability the LCB and UCB-based partial ranking contains the true ranking for each of the user and arm. Next, by the seminal work of Irving (1994), the Extended Gale-Shapley algorithm can retrieve super-stable matching if there exists one under given partial ranking, or declare if there is no such super-stable matching. Finally, the key observation is that a super-stable matching for a partial ranking is always a stable (not necessarily the optr-o)timal) matching for any full ranking contained by the specific partial ranking (c.f.
We update the UCB, LCB, and partial rank estimates follows for all i E [N] and all j e [K]:
p-uebi (t) = (i.s(t) + / (t)
p-lebi, (1) = (1) V 6 (og(t)/nis()
>-uobs,(11) (1) + Glog(t)/n...())
4

---

Competing Bandits in Matching Markets via Super Stability
Spieker (1995)). Our exploration is forced when there is no super-stable matching available.
partial rank instances of the true rankings. This culminates in the following regret bound.
We now define the gaps in our system that will appear in our regret upper bounds. Note that all the gaps we mention is with respect to the underlying rewards (1,7).
Theorem 3.5 (Centralized Regret Bound). The cumulative regret of Algorithm 1 in I rounds for the true stable match- ing instance with no ties (Fu: satisfies the following upper bound.
Definition 3.1 (Minimum Gap). For a system with re- wards (4,,7) and a partial rank (Pu, Pa), the minimum gap Amin (Pu, Pai Y) is defined as the minimum gaps among the users and arms with different ranks, i.e.
max (E(N]JE[K] (iippes -Pimin""
(T)
S (T)),
Mamin
NK
96K log(T))
E| Roo/ (T) S
K
3
A2(
Amin (Pu, (,
= =min ( min |Mi, pigh min JEIK], 171 Po.j
has - (130-1301))
Improved Regret Bound: We first note that for the partial rank where the top user for each arm, and the top arms for each user are separated we always have the user-optimal matching as a super stable-matching. Hence, Amin S A holds for all the instances. For general instances, is not possible improve this relationship, there are instances where they are equal. We now present motivating example that shows stark separation between these two quantities.
iE(N),
jf5 in Pali
Definition 3.2 (Admissible Gap). Consider a system with rewards (p,,7) and corresponding full rank (Fu. Fa). The admissible gap ( is defined as the largest mini- mum gap for the admissible partial rankings of (Fu, F.), max Amia (Pu, , (a. ()
AA(M,7) (P..Pa)EA(PP.FF.)
Consider an example with N users and N arms, for some N 2 3. Fix an E E (0, 1/2). For each user i E [N] let and (i+ 1)mod N be the top 2 arms with the respective rewards Mt.i = (1 (1 and 1m, N = (1-2s). The remaining arms j E [N] \ {i, (i + 1)oodN } all have mean reward
We also need to define the width of the rewards of users or arms that have the same partial order.
Definition 3.3 (Overlap Width). For a system with re- wards (1:77 and partial rank (Pa, Pa), overlap width Wor (Pu, Pai 14, >) as the maximum variation of rewards among overlapping users and arms with an equivalent par-
Ma. = E. For each arm j E [N]. let 75. N E and
Tj.a = (1 e) for all users i * (j - 1)modd N. For this instance we have Amin E. One stable matching for this
tial rank, i.c.,
instance is given as {(i, : E [N]].
Wor (Pur Pai 7,7)
Next, let us consider the partial ranks for each user i,
= max
max
|p4. Wigh jE[K]. 1= in Pu
max
hoss -1,26 l)
iE[N] j=y' Pa.
Pa, = (i > j. (i (i+ 1)mod N > j:
Vjj E [N] \ fú, (i + mmodN]}
We next show that the set A(Fu, Fa) has the following "completeness' property with respect to reward gap.
and the partial ranks for each arm j
Lemma 3.4. Consider the system with rewards (H:7) and the corresponding full rank (Fuy Fa). For a partial rank Pa), if (Fw, Fa) E FullRank(P,, (Pu, Pa) and the overlap width Wor (Pa, Pa) < Ax(H,)) then (Pu. Pa) E A(F,,Fa)
Pa. - -i (j- N Vi E [N]M[-- 1)mod NJ).
For the above partial ranks, we have Amin (Pu, Pas ,1, 7) = (1 2s). Moreover, this partial rank (Pu, Pa) has f {i. E [N]] as a super-stable matching. Therefore, (Pu, Pa) is admissible, and the gap AA 2 (1 2=). The ratio A 1 2 is unbounded as ε + 0. This shows that there can be an arbitrary separation between Amin and A
The regret upper bound proof shows that once we have enough exploration, such that we can resolve a gap of ((Aa(,,7) with high probability in round t, the partial rank (P.(I,, P(()) lies in the admissible set A(Pr: F.). Hence, the Algorithm 1 always lands super-stable matching, as the set SuperStable per Corollary 2.7. Furthermore, due to Corollary 2.7 we know that SuperStableeP..()), (t), C Stable F;; F.). Therefore, the algorithm suffers no stable regret. Finally, once the number of exploration satisfies Neaptore(!) > K + (eKlog((T) we show that (t), P. Pa(t)) E F(F;,F:) A3077)
4. Decentralized Two-Sided Matching Bandit
(t) / 0 as
In this section, we convert the centralized algorithm to a decentralized version where the users two global binary flags restarl and success to coordinate. We present Algo- rithm 3 used by user i, and Algorithm 4 used by an arm j in the Appendix C due to the lack of space.
Our algorithm proceeds in phases (of at most N steps each) and simulates the Algorithm 2 in each phase in a staggered
i.e. the recovered partial rank lies in the set of admissible
5

---

Competing Bandits in Matching Markets via Super Stability
manner. An ongoing phase is terminated by setting the restart flag to True by user, and the flag restart is shared the change of phase is always in sync across arms and users. Each phase Tg, starting at time t + 1, begins with setting the initial partial rank of each user i to (t,:(t) and each arm j to (t) (the UCB-LCB based partial ranks obtained at the end of previous phase). This is similar to the ranks.
Our regret upper bound for the decentralized system fol- lows the centralized system closely. We argue that each phase mimics one round of the centralized system. After O [K (Tg( / 7)) many rounds of exploration, any phase with high probability ends in finding a true stable matching, similar to Lemma E.4. The final regret bound in the decentralized case is given as follows.
centralized algorithm starting a round with updated partial
Theorem 4.1 (Decentralized Regret Bound). For a true stable matching instance (Fa F%) when the users follow Algorithm 3. and the arms follow Algorithu 4, the cumula- rive regret in T rounds satisfies the following upper bound.
Next, a user i reads the flag success which if False indicates the phase Tÿ is used for exploration. Otherwise, the success flag being True indicates the previous phase ended with a super-stable match. This implies at least one arm accepted proposal of user i, and the user chooses as the arm with highest UCB index among accepting arms as it's match (T2) for the phase Tg.
(T)]
BI 1TR,,
I B| (T),,
max (E[N]JE(K] (ii.peas - -Mrminn
"Is Vi.min
B/ & (1+ +
K
NK 2
96K log
3
A (1,
Inside the phase Tÿ in each round, we have the following alternating steps between users and arms.
Balancing Communication, and Regret: We rely on a 2- bit communication protocol per round in order to mimic the centralized system. However, it is possible make the com- munication sparse, by forcing the communication to happen once every phase, and force the phases to have arbitrary lengths. The idea is to perform the Global communication if round t is multiple of a pre-determined period, say L. This will increase the regret constant from (1 + N2) to (1 + L). However, this requires working with older matching (T,) for user i, which can be non-optimal from user i's point of view. Thus it can create some tension between commu- nication and incentives. Exploring this tension is left as an interesing avenue of future work.
(i) A user first propose to the 'source' nodes of the (up- dated) partial rank (Te) (line 14 Alg. 3).
(it) An arm j receives the proposals and computes the 'source' nodes (i.e., the non-dominated nodes) I' (j) among the proposing nodes (t) and (updated) partial rank (Te) (line 10 Alg. 4). If there is a unique 'source' node i" (j),, that node is accepted by arm and all nodes dominated by i" (j) are deleted from P PRa.j(TE) (line 11-14 Alg. 4). Otherwise, with multiple proposals all propos- ing users are rejected, and the 'tail' nodes in partial rank (Te) are deleted (line 15-17 Alg. 4).
(Mii A user receives the accept or reject signals from the proposed arms, and deletes rejecting arms from PR (Te) (line 15-16 16 Alg. 3). Next, it determines whether to explore or exploit based on explore(Tt). If explores then matches with the arm (t) = (ixTex)) mod K, otherwise matches with (t) = M; (Tz) (line 17-20 Alg. 3). We note that Tea also in syne for each user as explore(TT) and phases are in sync. Next, the user and the arms, if matched, observe their respective rewards, and updates the partial ranks (t)) for users i E [N], and Pa.j( (L) for arms j E [K]. (line 22-23 Alg. 3, and line 21-23 Alg. 4)
We numerically study the be- havior of the proposed centralized algorithm. Due to lack of space we defer the details of our experiment in Appendix B. As the decentralized algorithm is guaranteed to have only a regret ( away from the centralized one, we omit the decentralized algorithm. We compare against centralized Explore-then-Gale Shapley (ETGS) algorithm for fair com- parison.* Extended-GS significantly outperforms ETGS by quickly identifying a viable partial ranking during the explo- ration phase. This leads to lower regret than ETGS, which needs a full ranking of the top N items before achieving comparable performance.
Experimental Validation:
In the global communication phase the users play an active role. First, if user i is rejected by all proposed arms then she sets success False.2 Next, the success flag is read by user i. If success is True (each user has prospective match) or if PR,, (Tt) is empty the phase terminates. User i sets restart to True.
Regret Comparison:
We end this section by comparing the regret guarantees of a selected few works in this domain in Table 1. We provide the first regret upper bound that
ner, a user broadcasts a RESTART signal to all arms in a single round. Upon receipt, an arm echoes the RESTART signal to all proposing users. Consequently, within one additional round, all users receive the RESTART signal, achieving decentdeceetr 'restart' flag setting. congruent strategy can be adopted by users for managing the 'success' flag.
Finally, the restart flag is read, by each user and arm. If the flag is True the system enters a new phase. Otherwise, the old phase 3 3
We require users not changing the flags to also update the flags, so that shared flags are ready to be read.
"A decentralized version of this algorithm with shared global flags (aka blackboard) is presented in Algorithm 2 in (Pagare & Ghosh, 2024).
TTo trigger wide 'restart' in fully decentralized man-
6

---

Competing Bandits in Matching Markets via Super Stability
works for two sided general matching markets and depends on the instance dependent intrinsic gap A- Note that our algorithm uses the 2-bit feedback which is more restrictive than the (user, arm) broadcast where all the users and arms can observe the matching that occurs in each round. We also provide the first centralized regret lower bound that depends on gaps (which we call A,aog for simplicity) related to AA. See Section 5 for details.
X such that Stable(X") n Stable(O)= * 0 we can create partial rank (Pi, Pb) (by keeping only the shared pairwise inequalities of 0 and X) which lies in A(0). Hence,
U.)AAE)) FullRank( Pa)
{A Stable(A) n Stable(0) * 0].
It follows that the admissible set is regret free. As there can be no divergence for any matched pairs in true stable matching that narrows the 'bad' set of parameters further. We first define the 'Locked' edges as follows.
5. Regret Lower Bound
Definition 5.1. For any instance E O, we define Locked(O) as the set of all user-arm pairs (i,j), such that (i.j) E M for some match M Stable(0).
We develop an instance- instance-dependent lower bound for binary stable regret for the centralized setting. A pessimal stable regret lower bound general instances is not meaningful for the learning task of finding the stable matching. For example, there may exists set of matchings which are not stable but can be scheduled to achieve negative pessimal stable regret. Hence, binary stable regret which is always positive is the right quantity to lower bound for the bandit learning problem in matching markets.
The set (()) can be equivalently stated
A(0) - (> e e: X Ag U FullRank Po):V((,5)) E Lockod |ij (0) = (z)()) ()x(d)} (4)
(a)AAa))))
Th:
A policy т is uniformly good if for any = (u((), 7()) the algorithm æ has O(T9) regret for any a > We now state our regret lower bound below for any uniformly good policy.
We adapt the framework in Combes et al. (2017) to our multi-agent setup. The detailed formulation is provided in the Appendix F. Our system is parameterized by 0- (H,7) a : [o, 1J2NK_ We focus on Bernoulli rewards with appropriate means for ease of exposition. For any (i,5) E [M] x [K]. the term kl( A; (i.j)) denotes the sum of KL-diiergence between the 0 and instances for the rewards associated with the match (i.j) and satisfies (A)). This can be extended to the kl divergence given matching M (0, >; M) (anee k0, >; (i,j))-
Theorem 5.2 (Centralized Regret Lower Bound). For any instance 0 E O, for any uniformly good pol- icy л the binary stable regret is lower bounded as lim inf [[:G,](T:0]] log(T) 2 c(f), where c(0) minimizes the following optimization problem
kl(0, A: (i, = kl(m,,(0) (4,, +
min m(M)22
Σ ME MaaaMch N.K) (Stablee())
n(M,, s.t.
We need to take extra care while adapting the main results in Combes et al. (2015) as we are dealing with multiple so- lutions. To that end, we note that Graves & Lai (1997), from which Combes et al. (2015) is adapted, allows for switch- ing between optimal stationary policies without any cost. Moreover, while defining 'bad' parameter space Graves & Lai (1997) considers the parameter that does not share optimal solution with the true parameter, 0, and which has no 'divergence' with 0 while playing any one of the optimal policy. Therefore, our 'bad' parameter space for a given 0 becomes
((M) 2 E (K [K] MB(1))
Σ
Σ
E A(0),
where A(0) is defined in Equation (4).
We now present binary stable regret lower bounds derived for some special instances.
Corollary 5.3 (Serial Dictatorship). Consider a general serial dictatorship instance @ with two sided uncertainty, where N < K, (),((0) > (0)(() for all i < it and j. and the unique stable matching is {(i, :1 e [N]]. Then the binary stable regret for 0 is lower bounded as for any uniformly good policy is lower bounded
A(0) = (A E θ (0M)) = 0, VA O E Stablo
for all stable match of divergenco is Stable(A) n Stablc(O) 9).
ELR (T:01]
in 70000
log(T)
max
max (O), max (0) [EENN]
JE[K]
no common solution
where,
We now want to formulate the set A(0) using the admissible sets. If Stable(A) n Stable(O)= = 0, that means any partial rank (Pu, Pa) such that both and are compatible to (Pu, P.)S has no super-stable match. We note that for any
Co (0)
Σ (0))))))))))00
jED.(!)
J>1
derlying (unique) full rank compatible to the partial rank under consideration. More generally, we may replace (Fa, Fa) with 0.
"An instance is compatible to partial rank means the un-
7

---

Competing Bandits in Matching Markets via Super Stability
Algorithm
Two sided
Market Assumptions
Upper Bound per User/Arm
C-UCB (Liu et al., 2020)
NO
Contralized
Pessimal ONK (T)/ mmn)
UCB-D3 (Sankararaman et al., 2021)
NO
Serial Dictatorship
Unique O(NK (T)) min)
CA-UCB (Liu et al., 2021)
NO
(user, arm) broadcast
Pessimal O ((exp( N "NNKK""" K" log (T)
min)
UCB-D4 (Basu et al., 2021)
NO
uniqueness consistency
Unique O[N (Tg( 1/Aminn)
UCB-DMA (Maheshwari et al., 2022)
NO
a-reducible
Unique OCC, N..NNK K log log(T)) (TT///)))
ETGS (Kong& & Li. 2023)
NO
(user, arm) broadcast
Optimal O log (T (T)/ ()/mmnn)
PCA-DAA (Pokharel & Das, 2023)
YES
(user, arm) broadcast
ETGS+BB (Pagare& & Ghosh, 2024)
YES
(user, arm) broadcast
User Optimal O(K (T') (/mmm))))
CA-ETC (Pagare Ghosh, 2024)
YES
no broadcast
User Optimal O (ppoly(T) (T))
Ours
YES
2-bit broadcast
Pessimal & Binary O[K (T) (AA)
Two sided
Market Type
Lower Bound per User/Arm
NO
No Broadcast
Unique N log (T)A min
K log(T)) (min)) (Sankararaman et al., 2021)
YES
Centralized
Binary ( log( A.avy) [Ours]
Table 1: A more comprehensive regret comparison. We consider three type of gaps satisfying Amin S A S A.,vv Ca a parameter specific to a-irreducibility in (Maheshwari et al., 2022). For lower bound, L denotes the average number of (user, arm) pairs not participating in stable matching with (K - .N s L S (K - 1) (see Theorem 5.2). In regret upper bound, 'Unique' means unique stable matching, 'Optimal' means User optimal stable regret, "Pessimal" means User pessimal stable regret, and 'Binary' means binary stable regret.
(0)
Σ (0)
+
[N]. E [K] such that - (i) for each Pa,, E A(0) there is at least one (i, (i.'7)) such that j # j' or
Pu.
(i, (') such that i + f'; (ii) at most one of (i,j) or
Note the above instance holds with out loss of generality up to renaming of arms and user, and thus covers all instances of general serial dictatorship. This lower bound differs from Sankararaman et al. (2021) in several ways. It's for binary stable regret (not per-user regret), applies to general serial matching (not just OSB instances), and accounts for two- sided (not just user-sided) uncertainty. Thus, the bounds are incomparable.
Pu.;
(i,j') lies in Locked(0). same for (i,j) and (j, and (iii)
all the triplets are 'realizable'. See, Def. F.5 in appendix for formal version. Also, two triplets above are overlapping if they share common (user, arm) pair, e.g. (i, (j.j')) and (j, fi, (i,))). We define a collection of 'non-connected' cover-group where no pair of covers share any overlapping triplet. See Def. F.6 in appendix. The set of cover-group for O is CG)
Corollary 5.4 (General Instance with Redundant Arm). Consider general two-sided stable matching instance O with redundant arms N K, where (i) maxy (0), (i.j) E Loc Then the binary sta-
Through dual formulation of optimization problem in Theorem 5.2 we show in Theorem F.7 that the value c(0) therein admits the lower bound
ble regret for 0 is lower bounded as for any uniformly good (T:M)
c(0) Z
max Σ C),,C)-
(5)
policy π is lower bounded as lim +00
log(2")
GECS(O) GEG
where the divergence for a cover C' is given as
max
max (0), max [EE[
(as(0)) where,
Lockke)o)))))
()(0,C)= Σ max
(1(g((0))
(Lo))Eookke)()) (WUS''
NEIN
(o)
kl (1())(0)) 758 (8))
(0
max
j1l-53 Locked(()
jE[K] (2 (.DDEtoocodd0))
(0) = Σ
The quantity CG(O) and kl(0,)) C) depends on the combinato- rial structure of the admissible partial rank set set.A(B) A(0), and any further simplification without large sub-optimality proves to be difficult.
[E[M]
General Instances:
Because of space constraints, detailed definitions and results for the fully general case (where N may equal K) are relegated to Appendix G. We provide a brief and high-level overview here.
Remarks on Lower Bound: Multiple remarks on our regret lower bound is in order.
A cover of the set A(0) is a set of triplets (2nd and 3rd entries are unordered) (i, (i.j')) (i. (1,1)) for i e
o OSSB Applicability: We note that in Combes et al. (2015) the authors provide an algorithm that can attain the
8

---

Competing Bandits in Matching Markets via Super Stability
regret lower bound named OSSB. However, as the size of the set of all matchings is exponential in N) OSSB style algorithm is computationally prohibitive for our problem. More importantly. OSSB algorithm is designed for instances with unique optimal solution, so is unclear if OSSB can be applied in our case directly.
References
Basu, S., Sankararaman, K. A., and Sankararaman, A. Be- yond log² regret for decentralized bandits in match- ing markets. In Meila, M. and Zhang, T. (eds.), Pro- ceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 705-715. PMLR, 18-24 Jul 2021. URL https: http///oooeeengggeeeeeee/ee wwr.pressss....... v139 1559/basu2la. html.
Regret 'Free' Instances: If for each pair (i,5) there ex- ists a stable match M E Stable(0) then regret is (log(())) Playing the stable matching in round robin manner re- solves all the gaps with exp(-S((T") probability without any regret. So statistically ((1) regret is feasible even for uniformly good policies. We present detailed argu- ment, and a sequence of such zero regret instances for all N 2 2 in the appendix G.For N = 2 in the in- stance U1 [1, U2 [2, 1), [2, A2 : [1 both
Combes, R., Talebi Mazraeh Shahi, M. S., Proutiere, A., et al. Combinatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
Combes, R., Magureanu, S., and Proutiere, A. Minimal exploration in structured stochastic bandits. Advances in Neural Information Processing Systems, 30, 2017.
[(1, 1),1), (2, 2)] and [(2, 1), 21] are stable matching, and
these two covers all edges.
6. Conclusion and Future Work
Das, S. and Kamenica, E. Two-sided bandits and the dating market. In IJCAI, volume 5, pp. 19, Citeseer, 2005.
This work investigates two-sided bandit learning in general matching markets, providing both centralized and decentral- ized algorithms with logarithmic regret guarantees (Theo- rems 3.5 and 4.1, respectively). Our algorithms leverage the concept of super-stable matching (Irving, 1994), playing such a match when possible and exploring otherwise. Our centralized regret lower bound (Theorem F.7) highlights the importance of the super-stable set in determining the difficulty of stable matching bandit learning. While our cur- rent work employs sub-optimal round-robin exploration strategy, future work will focus refining exploration tech- niques to achieve tight regret bounds. Furthermore, while we guarantee pessimal stable regret, developing algorithms that optimize for specific objectives (c.g.. user-optimal or social-optimal) represents another important direction. We hypothesize that our initial stable matching algorithm could be combined with the distributive lattice structure of the sta- ble matching set efficiently explore and identify optimal stable matching.
Etesami. S. R. and Srikant, R. Decentralized and uncoor- dinated learning of stable matchings: A game-theoretic approach, 2024. URL https: /tts://arxae /ttp/aaxiivv..///////eee////aa org/ /
Gale, D. and Shapley, L. S. College admissions and the sta- bility of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. ISSN 00029890, 19300972. URL http: jtt.://wwww./..//oo/o/oo/oo/...t http://sstoor..g/staab//bb.s/t http://saalll/eeee 2312222
Ghosh, A., Sankararaman, A., Ramehandran, K., Javidi, T., and Mazumdar, A. Competing bandits in non-stationary matching markets. IEEE Transactions on Information Theory. 70(4):2831-288) 2024. doi: 10.1109/TIT.202. 3352228. Graves, T. L. and Lai, T. L. Asymptotically efficient adap- tive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):715- 743, 1997.
Impact Statement
Hosseini, H., Roy, S., and Zhang, D. Putting gale & shapley to work: Guaranteeing stability through learning. arXiv preprint 13X:v22410.04376, 2024.
This paper presents a theoretical exploration in the field of Bandit learning in Matching markets with two sided uncer- tainty. The ideas presented may have future implications in developing efficient algorithms in various fields, such as e-commerce and crowd-sourcing marketplaces, ride-sharing systems. However, given the pure theoretical nature of this work, and gaps from practice (e.g. lack of contextual re- wards) it is hard to foresee any specific impact at this stage.
Irving, R. W. Stable marriage and indifference. Discrete
Applied Mathematics, 48(3):261-272, 1994.
Jagadeesan, M., Wei, A., Wang, Y., Jordan, M., and Stein- hardt, J. Learning equilibria in matching markets from bandit feedback. Advances in Neural Information Pro- cessing Systems, 34:3323-3335, 2021.
Johari, R., Kamble, V., and Kanoria, Y. Matching while learning. Operations Research, 69(2):655 -611,1,,,,, 2021.

---

Competing Bandits in Matching Markets via Super Stability
Kong, F. and Li, S. Player-optimal stable regret for bandit learning in matching markets. In Proceedings the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), Pp. 1512-1522. SIAM, 2023.
Pokharel, G. and Das, S. Converging stability in two-sided bandits: The case of unknown preferences on both sides of matching market. arXiv preprint arXiv:2302.06176, 2023.
Kong, F. and Li, S. Improved bandits in many-to-one match- ing markets with incentive compatibility. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 38, pp. 13256-13264, 2024.
Reddy, M. S., Varghese, J., Venkataraman, J., and Rela, M. Matching donor recipient in liver transplantation: rele- vance in clinical practice. World journal of hepatology. 5 (11):603, 2013.
Lai, T. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in Applied
Saha, R., Choudhury, S., and Salomaa, K. Altruistic bandit learning for one-to-many matching markets. In Proceedings of the 2024 International Conference on Information Technology for Social Good, pp. 197-203, 2024.
Mathematics, 6(1):4-22, 1985. ISSN 0196-8858.
doi: http:://b.oogg//....000099433339
URL https: httpss//wwwscceeneedreeee. com/ ceiane//ariccee//1/1119666689881
Sankararaman, A., Basu, S., and Abinav Sankararaman, K. Dominate or delete: Decentralized competing bandits in serial dictatorship. In Banerjee, A. and Fukumizu, K. (eds.), Proceedings of The 24th Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 130 of Proceedings of Machine Learn- ing Research, pp. 1252-1260. PMLR, 13-15 Apr 2021. URL http:: http::///oocceeeeeeeeeeee .asss.m.. (all.prrss/ v130/ httto//aakaaarmmm2la..aa.s
Li, B., Cheng, Y., Yuan, Y. Wang, G., and Chen, L. Three- dimensional stable matching problem for spatial crowd- sourcing platforms. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining, pp. 1643-1653, 2019.
Lin, S., Mauras, S., Merlis, N., and Perchet, V. Stable matching with ties: Approximation ratios and learning. arXiv preprint arXiv:2411.03277 2024.
Spieker, B. The set of super-stable marriages forms a dis- tributive lattice Discrete Applied Mathematics, 58(1): 1-11, 1995.
Liu, L. T. Mania, H., and Jordan, M. Competing ban- dits in matching markets. In Chiappa. S. and Calan- dra, R. (eds.), Proceedings of the Twenty Third Interna- tional Conference on Artificial Intelligence and Statis- tics, volume 108 of Proceedings of Machine Learn- ing Research, pp. 1618-1628. PMLR, 26-28 Aug 2020. URL https:/ /ttp:s://prrooee /ttp///ccceeens..ce/ee///// mmlr.press/ v108 0tt.///iu0c.htteee
Zhang, N., Liu, Z., Li, F., Xu, Z., and Chen, Z. Stable matching for crowdsoureing last-mile delivery. IEEE Transactions on Intelligent Transportation Systems, 24 (8):1144-187,, 2023.
Zhang, Y. and Fang, 7. Decentralized two-sided bandit learning in matching market. In The 40th Conference on Uncertainty Artificial Intelligence.
Liu, L. T., Ruan, F, Mania, H., and Jordan, M. I. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1- 34, 2021. URL pectp://jmle www.llrorggpapppss//e/ 20-1429.1 html.
Maheshwari, C., Sastry, S., and Mazumdar, E. Decentral- ized, communication- and coordination-free learning in structured matching markets. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, vol- ume 35, pp. 1508 155922. Curran Associates, Inc., 2022.
Pagare, T. and Ghosh, A. Explore- Explore-then-comee comm- algorithms for decentralized two-sided matching markets. In 2024 IEEE International Symposium on Information Theory (ISIT), pp. 2092-2097, 2024. doi: 10.1109/111777844. 2024.10619416
Parikh, S., Basu, S., Ghosh, A., and Sankararaman, A. Com- peting bandits in decentralized large contextual matching markets. arXiv preprint arXiv:241 1194, 2024.
10

---

Competing Bandits in Matching Markets via Super Stability
A. Related Work
Stable Matching with Partial Preference: Stable matching has been a successful concept for studying equilibria among incentivized agents in two-sided matching markets. In the foundational work Gale & Shapley (1962), participants express preferences through strict rankings. A natural extension allows for more realistic scenarios with partial preferences. Irving (1994) expanded the concept of stability to partial preferences by introducing three distinct stability concepts: weak, strong, and super-stability. Our work draws from Irving (1994), and connects super-stability to the inherent hardness of learning stable matheing under bandit feedback. The Extended Gale-Shapley algorithm there is the central algorithm that we use breaking from the literature that exclusively uses the original Gale-Shapley algorithm. Next, we build on the work of Spieker (1995) which provides structure of the set of super-stable matchings.
Bandit Learning in Matching Markets: The work of (Das & Kamenica, 2005) introduced the problem of learning stable matching for matching markets with one-sided uncertainty, i.c. the users have unknown preferences but the arms have complete knowledge of their prefrences. In (Liu et al., 2020) the authors provided UCB based centralized algorithm with the first theoretical regret guarantee of O(N K log(T)/A An explore-then-commit algorithm with the knowledge of minimum gap Amin was also proposed. Next, the work was extended to the decentralized setup that removes the knowledge of gap but imposes uniqueness of stable matching via structural assumptions on preference rank (Sankararaman et al., 2021; Basu al., 2021; Maheshwari et al., 2022). The algorithms proposed therein achieve a O(NK (oN (T) min) ) user pessimal stable regret. The collision avoidance UCB based algorithm proposed in (Liu et al., 2021) achieves O (exp(NN) log" (T)) (in) regret in general matching markets.
A separate thread of work explored the Explore- sestorr-then-cooe comm-c type algorithms for general markets starting from (Basu et al., 2021), and improved in the ETGS (Kong& & Li, 2023). The ETGS type algorithms are able to achieve a O(K ( user optimal stable regret. A more recent work (Hosseini et al., 2024) provides sample complexity bounds, which translates to (ogl (T)g(T)// (T)/ min) regret bound, using a concept of envy-set where F is the size of average envy set, and may be less than K based on the underlying instances. There has been multiple works with ETGS as the core where a user can match with multiple arms (upto quota) in each round (Kong& & Li, 2024; Saha et al., 2024).
Only select few recent works (Pokharel & Das, 2023; Pagare& & Ghosh, 2024; Zhang & Fang) study matching markets with two-sided uncertainty where both sides need to learn their respective preferences from bandit feedback. In (Pagare & Ghosh, 2024), the authors present a black-board model similar to ours and attain a O(K log (Tg(T)/ ( algorithm similar to centralized ETGS mentioned in this work. Similar guarantees are provided in (Zhang & Fang) without baclkboard, while (Pokharel & Das, 2023) lacks any theoretical guarantee. But all these works focus on user optimal stable match learning. This is incomparable the task in this paper of finding any one stable matching.
Our work provides an entirely new algorithmic idea by applying the Extended Gale Shapley algorithm (Irving, 1994). Furthermore, we provide new instance dependent lower bound for general instances for centralized setting, and hence also for decentralized setting. The long standing regret lower bound before this work comes from (Basu et al., 2021) which is applicable only to decentralized setting, and for the limited special case of serial dictatorship. Our work is based on
On the algorithmic side, apart from Gale Shapley based bandit algorithms, the authors in (Etesami & Srikant, 2024) take a new game-theoreee approach of preference learning with exponential weight learning with one-sided uncertainty and provide a O(N (T) No / A ) regret bounds. Also, there has been work that involved non-stationarity in the mean rewards of the arms (Ghosh et al., 2024; Maheshwari et al., 2022), and mean rewards have a linear contextual structure (Jagadeesan et al., 2021; Parikh et al., 2024). Finally, in (Lin et al., 2024) the authors study approximation ratios and learning to find weak-stable matches which is different from the standard setup.
B. Experiments
In this section, we numerically study the behavior of the proposed centralized algorithm. As the decentralized algorithm is guaranteed to have only regret O(N2) away from the centralized one, omit the decentralized algorithm. We first show the pessimal stable regret dynamics of the centralized algorithm for a system with N users and K arms. We generate a bandit instance by selecting a random preference order for each user and each arm. We generate the mean rewards μú,j and Yg.a, for E [N] and j E [K] such that the permutation is randomized, and the gaps are chosen uniformly at random from [ Amax]. For each reward observation we apply independent Gaussian noise with standard deviation a (the UCB and LCB bonuses are also scaled with r). We plot the evolution of the mean cumulative regret with time for our proposed

---

Competing Bandits in Matching Markets via Super Stability
Algorithm 1, and centralized aeplore-then-Gaeee Shapley (ETGS) algorithm of Kong al. (Kong & Li, 2023) for fair comparison." Centralized ETGS explores until the top N ranks are resolved for each user and arms, and then commits the Gale Shapley solution afterwards.
In Figure 1, we consider one such instance with N = 8 users, M = 8 arms, Amin = 0.2, Amax 0.5, and or = 0.4. We observe the logarithmic pessimal stable regret for both the algorithms. However, clearly the proposed Extended-GS based algorithm outperforms the Centralized ETGS adapted from Kong et al. (Kong Li, 2023). We plot the mean rewards, as well as 25% and 75% regret plots averaged over 20 sample paths. Next, Figrue 2 we study the dependence on a/aav by varying for N K 5 and min 0.2, max 0.5. We observe that there is a clear separation between the Centralized ETGS and proposed Extended-GS GG algorithm showing the superiority of the latter. Both the algorithms initially explore but Extended-GS algorithm finds an admissible partial rank much earlier than the top N rank resolution leading to lower regret than ETGS. Figrue 3 exhibits similar behavior with varying gaps Ain and A Amxx.
Average
Average
25000
20000
Pessimal Regret
Extended-CG GS
Pessimal Regret
Extended-GS
20000
10000
10000
5000
5000
Time
Time
Figure 1: Pessimal Stable Regret for N 8 Users, M 8 Arms, Amin 0.2, A Amxx 0.5, and o 0.5.
ETGS
Extended-C
12500
sgma=0.2
12500
sigma-0.2
Average Regret
sgma-0.3
Average Regret
sigma-0.3
10000
soma=0.4
10000
sigma-0
s.gme=0.5
5igma=0
sigma=0.75
sigma=0 75
$gma-1.0 1.0
sigma-10
2500
2500
10a
10a
10
10
10a
10a
10a
10*
Figure 2: Average pessimal stable regret across all users and arms with different o, with N Users, M = Arms, Amin 0.2, Amax 0.5.
ETGS
Extended
AvamO: 10.2
Aecu 0. -00. 0.25
Average Regret
5000
Dew=0 00.5
10,000mm #1000
Average Regret
5000
= 40 00
1000
4000
4000
2000
2000
1000
1000
107
10a
101
107
30'
10'
Time
Time
Figure 3: Average pessimal stable regret across all users and arms with different Amin- and A with N = 5 Users,
M = 5 Arms, o = 0.4.
'A decentralized version of this algorithm with shared global flags (aka blackboard) is presented Algorithm 2 in (Pagare & Ghosh, 2024).
12

---

Competing Bandits in Matching Markets via Super Stability
C. Algorithms Addendum
round / for E [N] and j [K], the estimated mean rewards (t) and (t,((), and number of samples na (t) for our Algorithms (Algo 1.Algo 4, and Algo 3) are given as
(1,((1) -) 1) ((t)))
(t)(t) May(t - (t Yi(t)
if (i.j) e M(t) else Pt, 1)
Mt - 1)+
(t,(t) ni,(( - 1)8g,((t - 11) ((t))
(i. e M(t) else ft.e 1).
nt - 1)+1
We now state the Extended GS algorithm from Irving (Irving, 1994).
Algorithm 2: Extended Gale Shapley (EXTENDED-GS)
Input: User partial rankings Pa. and arm partial rankings Pa Initialize: m, for all E [N]
while for all i [V] Pa.s # 0AA, 3i [N], 0 do
for each user i [N] do
Propose to all 'source' arms j E [K] under partial rank Pa.j
for arm j E [K] do
Gather the proposing users Prop(j)
Get the 'source' nodes S(j) in the DAG Pa.j O Prop(j)
for each user k Pa.j
s. f.for some E S(j) do
10
Remove arm j from Pa,k: and user ls from Pa.j
11
[[(]]] = then > A user can be accepted by multiple arms
12
For i3 E Sy. append j to may
14
else
15
for each user le in the 'sink' of Pa.j (a DAG) do Remove arm j from Pa,ks and user le from Pa.j
16
17
if for all E [N]. m4 * then Return Mstable ((i,m.) m.) :iE [N]]
18
19
else
29
Return
Next, we state the full decentralized algorithms here. We colorize the communication among the users and the arms, the observations, and the update to global shared flags.
13

---

Competing Bandits in Matching Markets via Super Stability
Algorithm 3: Decentralized Two-Sided Matching Bandit, User
Global Flags: restart False, success +- Folse
Local Indices: Exploration Tex 0, Phase count тą <- 1, Phase exploration indicator explore(1) t False Initial Ranking: (0, f- empty node DAG
p- Let global time & < (convention)
for Tr. 2 do
Update (Te) (t)
Read shared flag success and set erplore(Te) -success if success then
MT(r) + arg (() p-
10
while True do
> Globally: restart + False, success t- True
13
& Increment global time L e 1+1
Propose for all arms j in 'source' of (T.,,(T)). Sy(1) (i) Receive the signals from the proposed arms Sty(t) Delete all [j (t) reject) from (Tu,s(TT)
17
if explore((T)) then
Match with m²(() <- (Ta) mod K, and set Tea f- Tea 1.
else
29
Match with mt(1) < Ms(T))-
Match from previous phase
21
> No collision occurs, and mt) #
22
Observe reward (e) (t) and update UCB and LCB using Eq. (1).
23
Compute (t,:(t) (t) using Eq. (3).
GLOBAL COMMUNICATION
25
if V proposed arm j. (t) = reject then
26
Set success + success A False
27
else
Set success + success A True
Read shared flag success (once all updates are done) if (Te) = V success then
30
31
Set restart + restart V True
32
else
33
Set restart +- restart V False
34
Read shared flag restart (once all updates are done) restart then
35
36
break b Enters new phase
The algorithm for the arm is given as follows.
14

---

Competing Bandits in Matching Markets via Super Stability
Algorithm 4: Decentralized Two-Sided Matching Bandit, Arm j
Global Flags: restart
Counter: Phase counter T +-1 1
Initial Ranking: Pa, (0) t empty N node DAG
> Let global time & <- (convention)
for Tt 2 1 do
Update (T.,(TT) (t)
while True do
Increment global time t Receive proposals from users (t)
Get 'source' nodes (j) from Sz(1) (Ti.((T))
if [+) = then
11
Accept the unique user (") E (j), by setting S ()))(( = accept
For all 5,(t (t) and * (j), set St,(() reject
For all < 8 (j), delete in (
else if [T) > then
For all E (t),, set (t) reject
All 'tail' user i in (Te) are deleted
b Arm j matches with user my (t)
18
pm, (1) {i: P pmm (1) = or (t) if explore(Tr) = False
Tex) mod K j} (possibly 0) if explore((r) True
20
if m, (t) + 0 then
Observe reward y J.m.' (1) (1)()) and update UCB and LCB using Eq. (2)
23
Compute (t) using Eq. (3).
24
> GLOBAL COMMUNICATION
25
Read shared flag restart (once all users finish update)
26
restart then
27
break
Enters new phase
D. Proofs of Preliminary Section
Proof of Lemma 3.4. Given (Fu: F.) Stable(F,, us Fa) * 0 in order prove this lemma. It is sufficient to argue that FullRank(Pu,, Pa) FullRank P' P.) for any (Pr, P.) E A(F,,, F,), because
FullRank Pa), need show that SuperStable( Pus Pa)
Stable(F,, F.) SuperStable(Par. Pa)
Stable Fa, Fa)
n
Stable(F', F()
2 Stable(Fu, Fa)
Stable(F F.)
(F..F.))ePlllaaa((PP....
(i0) Stable(Fu,, F.) SuperStable(P",, P() +
(184)
The equality (i) and (iii) is by the definition of super-stable set. Inequality (ii) follows from the assumption FullRank P.., Pa) S FullRank(P', Pt), and inequality (iv) holds because we chose (Pr, P.)) E A(Fa, Fa).
What is left to complete the proof to show that the assumption FullRank(P,,, Pa) S FullRank(P,, P,,, P!)) is true for some (P',, Pt) E A(Fu, Fa). Let us choose a partial rank (P,, P.) E A(Fa, Fa) with a minimum gap Ax(u, 7) which exists due the finiteness of the A( F,, Fa). For any pair of users i, E [N] and arms j.j' [K], we have by definition of
15

---

Competing Bandits in Matching Markets via Super Stability
overlap width, and because Wor ( Pa: < A1
Ipas - 15.5 AA(,,)) = j * Pa,s
j' and his - "3pel 2 AA(1:7) = =i
Pag
However, by definition of AA(U, 7) and the fact that (Pa: Pd) attains the maximum gap we know
j' = 1pt. - parl 2 A = j
P..
Pa.
+
hyg - 73al 2 7 = + i'.
Pa.
Pa.i
In other words, any pair of users (or arms) that unequal in the partial rank (Pú, Pb) are also unequal in the partial rank Pa). This in turn implies that FullRank((P. Pa) S FullRank(P2, Pa). This completes our proof.
E. Proofs of Regret Upper Bounds
We define the good event Gr for all time t 2 1 as
Vi E [, E [K], max (HES - (L. - -sx((t)) =V (t)
6 llo((t)
Lemma E.1. The probubility of ''ud' event for any 1 2 1, satisfies P(G S 2NK/eP
Proof. We start our bound follows,
P(g))
=P( max max (INSS - (1xx(01) (E(N).E[[K]
6 6log(!)
V
(ig(t)
Σ
P(INLs (a)s >
(1)
PP P(130 - P1a3ss-9s0000 -390
6log(t)
V mis(1)
min(() (1)
[E(M].jE[K]
6 6log(t)
+ P P(hss - -5),,(t)1 > V 6log(t)
Σ
Σ
P
(t) = s, |ass p(i((t)
[E[]]][ ==1
6log(t)
2NK
[mn(()= =
8=1
2NK Σ exp( 1op(-31mg ()) < 2NK/t..
All the rewards come from some --sub-gaussian distribution. Therefore, we can bound inequality (i) using the sub- gaussian concentration bound with m samples for 1-subgaussian zero mean distribution X (c.f. Lattimore et al ()
P(IA x e) < 2 se²p(_se//2),
Lemma E.2. Conditioned on the good event G(t), the recovered set of partial matching (Pa(t),Pa(t) satisfies that (Fr, Fi) E (Pl,)
Proof. We know that given the good event (t), for any two users i, E [N] and any two arm j E [K] we have
p-ucbi,, (t) 2 M4.5 +
6log(T)
lps.j pi.s 2 Mo.j.
(t)
(tlebry(t) $ 14,6
Glog(T] (t)
+ lit.s - HhJl S P1.t
16

---

Competing Bandits in Matching Markets via Super Stability
Therefore, j- (1) (() implies that Ma.j Pt,y" under the good event g()). Similarly, y-ucbe (t) implies "i.j 2 j under the good event (t)).
Therefore, for any fixed user i E [M] any pair of arms j.3' E [K] if we have Hig > Mig's i.e. j > J', then j > j'.
Pu.((()
Similarly, for any fixed arm j E [K] any pair of arms i, 1 [K], > i' imillss i
V. This implies by definition that (v)
F%) E Full (1), (a),
Lemma E.3 (Convergence to Admissible Set). Conditioned on the good event (t)1 for any time 2 1 if number of explorations Nesplore(t) > K + 96K log(T) (2)(7))) we have (Pu(t), E A(F Fū), i.e. the recovered partial rank lies in the set of admissible partial rank instances of the true rankings.
Proof of Lemma E.3. Let N Nexplore (f) be the number of exploration steps taken by the centralized platform up to time t. That implies that for each user and arm pair (i,j) for i E [N] and j E [K], the number of samples (t) 2 (Neaxporrett)- ())K With (1) many samples, under the good event (()) by definition
max (189) - -ots0(0) 1oaa--99,10 -Bsx(01)3 - 1
6 Glog(()
(t)(t)
Therefore, for any fixed user i E [N] and any pair of j,j' E [K].
6K log(T)
(mas pt,s') AV
Neapiore (t) 2 2Vogo Vnig(1)
(nn.y()))
then we have (-Icbs,j(t) > p-ucbs, and j
6K log(() J. Similarly, if (13,4 73,e} > Av Neuptore ()-K we have i > Pa.(t))
(t.)
Therefore, by definition Wor (Pu,(),, (t)); S VV Nuzytore (t) (+)-K*
6K log(T)
From Lemma E.2 ((F2; E FullRank(Puu()) (t)) under the good event G.. Therefore, under good event n from Lemma 3.4 if W.v
< (1,, 7) then (Pa(t).Paatt) E A(Fi, FY). Therefore, for all such that
log(T)
N Nerplore (f) 2 + 96K
A (2, 7)
we have (P(())P((()) E A(F
Lemma E.4. Conditioned on the good event (t219(t),, for some & 2 if and only if (P.())Pa(() & A(F F?) then exploration is triggered in round t.
Proof. For round t 2 1, if Algorithm 2 does not return a stable match then exploration is triggered in Algorithm 1. Therefore, we need to show that under Qt) if (Pu Pa(t)) & A(F;, F?) then Algorithm 2 does not return stable match. Note that from Lemma F.2 we have (F FT) E FullRank(P..()) Pa(()) under the good event G. If there stable match returned by Algorithm 2 in round f, then SuperStable(P..) (t))) # Therefore, by definition (Pa(t), (t)) E A(F;, Ft). This proves the lemma.
Proof of Centralized Upper Bound Theorem 3.5. We now create the regret decomposition. We first define the following for notational simplicity
Th(T) K 96Л log(T)
(u,
where Th(T) corresponds the sufficient amount of exploration necessary to find a super-stable matching for any $ T (we will show this shortly).
E RR.. (T) - Mi,min)
17

---

Competing Bandits in Matching Markets via Super Stability
E
(t & Stable(Fä. P.))
P.))
E
((P,(())Pa(()) & A(Fa: F2))
(18))
T
E
((P.(())Pa()) & A F2)) ni Go
+ Σ P(G;)
(in)
1 ((Pu(),Pa(()) $ A(F.. ( (Nxxpiore S (T(T)) St
+
E
1 (t), & A(F F:)) (Nexptore (T)TTT(T)) 7r Go + + 2NK/1²
t=1
1=1
Th(T) TP
N Nexplore (T) Th(T) n So + N
Th(T)- + TP 31 S T: Nexplore = Th(T) A A (P(P))))(() & ((FFF.) Di Gi + +NK*3/
(v4)) x T - NK
The first inequality (i) simply states that we incur regret (Ji,pesa (4,min) regret if Algorithm does not create stable matching (t) at round f. Incquality (ii), follows as Pa F implies (t) is a stable matching under true preference by definition of A(F F.). In equality (fii) we condition under good event n and it's complement U.Gf. We also use union bound over 4, to upper bound the latter quantity by (Jiipess Mi,min) Et P(gī). In equality (iv) we further break the first term by considering two cases: (a) when (Nexrplore (T) > Th(T") and (b) it's complement. Inequality (v) first bounds the case where Nezpiore(T) (T) S Th(T'). From Lemma E,4 it follows that under good event N,Gr, Nexplore(T)
Et= ((Pu(tt) & A(FF;, gives regret bound of (Hi,pese Mi,min (Th(T). Inequality (v) next bounds the second term with trivial T bound on E ((),(tt) (t) & A(F2, F.)). In (vi), we notice that in order Nemplore(T)) Th(T)) hold there must be time when Nezpiore (T)) = Th(T) and (s)( (s)) & A(F F?)). Finally, due to Lemma E.3 we know that this event not possible which gives our final bound.
Hence, under n,9t, Nesplore (T) S Th(T)
A similar chain of inequalities proves the regret bound for EE R (T))
Proof of Decentralized Upper Bound Theorem 4.1. We now create the regret decomposition. We first define the following for notational simplicity
lTg(T) A 74,
([T)==+++) + = = N++ + K + 96K
where Th'(T), similar to the centralized case, corresponds to the sufficient amount of exploration necessary to find a super-stable matching for any t < T (we will show this shortly). Note that as our exploration may cross the centralized threshold at the beginning of a phase, can occur for N2 extra rounds.
We note that the restart flag ensures synchronization of each phase across the agents and arms. Each phase of the decentralized system follows round of centralized system. Hence, the following results hold due similar line of reasoning as in the centralized system.
1. If and only if (PR., (T)), (T)(T)) A(F;,F) Fū) then the phase Te ends in 'success' and the recovered mapping used in phase (Te 1), M(T 1) E Stable( Fi Ft). This is true by definition of A(F;, F.).
We now present the on the regret decomposition of the user below.
E. (R, (T)) Miiuunn) -1
18

---

Competing Bandits in Matching Markets via Super Stability
T
E
1 (M)t) & Stablo(Fü, F:))
t=1
Σ
Σ
((xplooreTT))
T221 1 te Phase(T))
(18)
T
(erpl Go + [a0]+++uun (()))
21
t=1
(se)
E
(ecplo(ee)))))(Te a n 9o]
r221
T
+
Σ
(er)))((eplorrr( ( (>>(h no Gi + + 2NK//2
1
1=1
(T) + TIP
Nemporee (T) (T((T) n. Go) + //
(v1)
S (T) +TP
phase starting (t. + 1): Neaplore (ts) = Th' A ((epplore(s) ((xplorcc)) +N
(w1)
(T) + NK 3 + TPP phase s starting at (ta/ + 1):
Nexptore (es))ore(ts)) 2 (T) - N2 A (PRn(S); PRa (.C(s))PPR...A & A Fi)] Et ST T Nexplore (t) 2 (T) 1) (PL())))))))) & (FF.F:)
(wiSt) (T(() N 1 TF
x (T) + N3
The inequality (it) follows as for all E Phose(rt) the matching M(t (Te) & Stable(F (Fū, Fū) only if the (Te 1)
phase terminated with a super-stable match and we have success False. But if (Tz 1)-th phase has success = False then explorreTT)) The inequality (tii) and (iv) follows identically to the centralized system. The first term in incquality (v) follows by noting that conditioned on good event Nexplore (T) = =E,, n((T)] (cxplore(Te)) Hence Nexplore (e S Th'(T) (T) bounds the first term by (T). The second term uses the trivial bound T for E,, (vi) we note that Nexptore (7) can cross Th'(T) only if there is phase 8 that has explore(s) = True, and Nexptore (t) is
For the inequality
equal to Th (T) at the beginning of phase s. For inequality (vii) we note that explore(s) = True only if for the (s 1)-th phase (PR,,
1). (s 1)) E A(F; F.). and Nezplore (t) should at least be (Th'(T) N at the beginning of phase (s- - 1). The former holds due to the fact (1), and the latter is true each phase lasts at most N steps. For inequality (vitt) we note that the above is equivalent to an existence of time t (t can be taken the penultimate round in phase (s (s-2)) 2))
such that N Neaplore (t) > (T) N 1) and the recovered UCB-LCB rank (1), (t())) & A(F F7). However, noting (T) - N22 - 1) = Th(t) due to Lemma E.3 we know this is not possible. This gives the final result.
F. Proof of Regret Lower Bounds
In this section, we present proof of the theorems and lemmas related to the lower bound result. Our lower bound follows framework similar to Combes al. (Combes et al., 2017), which in turn relies on Graves et al. (Graves & Lai, 1997). However, Combes et al. (Combes et al., 2017) does not capture our use case as it is tailored to bandit feedback. due to the multiplicity of the stable matching set there is no easy way to encode this problem in the form of linear Semi-bandit like Combes et al. (Combes et al., 2015).
We recall our system definition. Our system is parameterized by 0 = (H,, E θ 10,1 We extend our notations (e.g. Stable (u, Fa), A((,,,))) to replace both (H, and (Fu, F.) with 0, as uniquely specifies our instance. The action space is the space of all matching between bipartite graphs between two sides of size N and K, denoted as Match(N, K). In round by choosing matching (t) Match(N, K) the centralized platform observes random vector ((M,t) = ((V,()) Y (1)) i E [N), E [K]) where for unobserved user-arm pairs, i.e. (i.j) & M, we have deterministically Y:(1) Y5(1) 0, and for any observed user-arm pairs Y:(1) come from an i.i.d. distribution (conditioned
on (i.j) E (t)) with mean pr,5( (0). Similarly, any observed (t) are i.i.d. with mean 35.x (f). For the sake of simplicity,
19

---

Competing Bandits in Matching Markets via Super Stability
for the rest of the paper we work with Bernoulli variables. Extending it general single-parameter distribution can be done similar Lai et al. (Lai & Robbins, 1985).
We recall from the main paper (Equation (4)) that the set of 'bad' parameters is given as
A(0) = E θ: 1I A; M) = 0, VM E (Oable(0); Stable(A) n (1) 0} for all stable match of divergence is
common solution
= = : = (A)( (5)(0))))(0)))) - (A), ((i, E Locked À & Peet. (Pu, Pa)).
Therefore, we can apply the lower bound formulation in Combes et al. (Combes et al., 2015) and arrive at the following lower bound for our system. As mentioned earlier, adapting the results of Combes et al. (Combes et al., 2015) to our multiple-solution setting requires careful consideration because we need to account for the possibiliiyy of switching between optimal stationary policies, which is allowed without cost in the original framework of Graves et al. (Graves & Lai, 1997). Crucially, Graves et al. (Graves & Lai, 1997) defines the "bad" parameter space as those parameters that do not share an optimal solution with the true parameter, f, and exhibit no divergence from 0 when any of its optimal policies are applied. This definition is essential for properly adapting the theoretical framework to our context.
Theorem F.1 (Adapted from Combes et al. (Combes et al., 2015)). For all E θ, for any uniformly good policy π R (0) l 2 c(f), where c(f) minimizes the following optimization problem
lim r
min MMM20
Σ
(M)
MEMasch(NN KY)aaaalle1))
subject to
Σ Σ
M(M)kl00. A: (1,5)) 2
(6)
(i.1) M:(JJ)EM
where A(0) is defined Equation (4).
F.1 Instantiation of Lower Bound for Special Cases
We now construct some regret lower bounds using Theorem F.1.
Regret 'Free" Instances: If for each pair (i.j) there exists a stable match M Stable(O) then regret is o(log(T)). Let
for any ordered list I., let (L) [L|z] ......... [1) denote one anti-clockwise rotation, (L, m) denote applying
rot(-) times, and rew L) [L [r. L)) (.../ L1] denote reversal of the list L. The instance {[U; : [NV] i)
[N]), {A,
([V).
j E [N]}] has the stable matchings [(i, rol[ [T] i E [N]] for 1 = 0. ...... (N
1).
This covers all the pairs (i,j) for i E [N] and j E [M.] For all these instances 0 stable regret is attainable statistically. We do not have a logarithmic regret lower bound for these instances. Any algorithm that alternates between the possible stable matching of for the first 12(1-=)) rounds for some e >> 0, and then commits to a super-stable matching of the discovered partial rank if one exists or plays any sub-linear algorithm (like ours) a uniformly good policy. But for any instance with ((1) reward gaps this learns with O(exp(-T" error rate the true rank for all users and arms. So for 0 it incurs O1) regret. Note this is not constructive argument as we do not know a-priori which matchings stable.
General Serial Dictatorship with Two sided Uncertainty: In serial dictatorship all the arms share the same preference, With out loss of generality (up to renaming users) let us assume user i is preferred than user i' for i < i'. There exists unique stable match which again without loss of generality (up to renaming arms) we can denote as (i, i) for all E [N]. Then we have dominated arm for user i as (0) = {j (0) > (r,((),,j S i} for all i S N. Dominated arms are the armed preferee by user i compared to it's own stable matched arm. We can construct an instance Xx,(61) by picking a j E (0) and then making user i preferable to user j for arm i.c. new 2/,- = Ty.. (0)++.) We have k((O, (y.()))
(0) (0) (0)+)). Because serial dictatorship has unique stable match, we have a blocking (user, arm) pair (i. in Xy. for the matching {(i,)) é E [,V],, and therefore Xy,( A()). We have A1 {(),(t)) : E [N], E D.(0)) C A(0). Next, we consider change on the user side. Let \,,())) be constructed by picking any j > i, and making new /4,55 = (4,; (0) + This way now (i,j) again create blocking pairs and as a consequence we have \m.(i)) E A()). Let A2 = ()p,(1)) : E [N], > i} C A()).
Then the optimization problem (6), relaxed by replacing A(0) with A U Ag has the instantiation
min (M)2
Σ
(M)
20

---

Competing Bandits in Matching Markets via Super Stability
Σ 7(M) 2 way V(,,)) M3(E.)
s.t.
W/ wi (l.gkl(73.. (5), + 2 E [N], Vj D2(0) Wa.kkl (0) (0) + +) 2 Wi Vi [N Vj
Because each user i can match with only one arm j in each matching we have a lower bound for the above optimization problem as
Cu.i
Σ
Σ
(0),
(ED.(0)
JE[+IK]
Similarly, considering the perspective of each arm we obtain lower bound
(0)(
Σ
kl()),(0), (()))))) + Σ (0),
(.))D(()
Thus the final lower bound for the general serial dictatorship for binary stable regret is
c(0) max
max Cu.i max (o.,(())
iE(N]
JE(K]
This lower bound different than the lower bound in (Sankararaman et al., 2021) in multiple ways. Firstly, our bound is for binary stable regret, instead of per user individual regret like the previous one. Further note the lower bound therein does not apply for general serial matching instance, but for further specialized OSB instances. Also the bound in the previous work only uses user sided uncertainty, not both side uncertainty. So these bounds are incomparable.
F.2 Regret Lower Bound for General Instances
In this part, we connect the lower bound in Theorem F.1 with the admissible set gaps in 0.
Definition F.2 (0 (o-ked),)). partial rank (Pay Pa) is d-Locked iff for all i [N] two arms j. j' in ((( have the order in Pu.i identical to (0), and for all j [K] two users i, 1' in (0) have the order in Pa.j identical (
For a given instance 8, the boundary of the admissible set, namely ((0), defined as the set of partial ranks (Pa; Pa) A(O) that is not compatible with any other (Pu, P!) E A(0).
Lemma F.3 (A) Decomposition). Given an instance and the boundary admissible set B(0). for each instance and the corresponding full rank (A,, the following are equivalent: (a) X E N0) and (b) (F,(A), (A)) (i) B-Locked, and (ii) reverses at least one 8-open triplet for each (Pu, Pa) E B(0), as specified below
a triplet (i.j.i') such that j', and either (i.j) or (i.j") or both not in Locked(O).
Pes a triplet (j.ú, i.) such that i > i. and either (i,j) or (i',j or both not in Locked(0).
Pa.
Lemma F.3 provides wider set of instances that have sub-logarithmic regret. Corollary E4. If there exists a (P), (O)) E B() that contains no 0-open triplet then A(0) = =0. Hence, the stable regret the instance is sub-logarithmic
Proof of Lemma F.3 and Corollary F.4 are deferred to SectionG.l.
More importantly, Lemma F.3 gives us a way to construct critical instances by reversing 9-open triplets that form a 'cover' of the set ((0) to construct a full rank (Fu, F.) that is 0-locked, and does not have any stable-match overlapping with the instance O. fact, it is enough to consider the minimal covers of the set B(8), which we denote as Cover(#).
Definition E.5 (Cover of B())). A set of triplets (i.j.'') or (j. i') for i, E [N] and j.j E [K], C' a minimal cover of B(0), ie. C E Cover((), iff all the following statements hold (i) each (Pa, Pa) e B(0) there exists triplet o E C such that o is f-open for (Pu, Pa),
21

---

Competing Bandits in Matching Markets via Super Stability
(ii) any proper subset C' C C, C' is not cover of B(0), (iii) the set Ac defined below is empty
(p. 78) E AC = (Ø .00 satisfies
1 pi, 7/. -},(00), V(i,j) Locked(0),
(7)
p.g 2 Mig tE, V(i.j,') EC,
(8)
F.. 2 7/ te, V(iit)) EC,
As will be clear shortly, in our lower bound group of such covers can be simultaneously used as long as these covers are not overlapping.
Definition F.6 (Non-connected Cover Group). set of 'set of triplets' G= = {C1, C..). is called non-connected cover- group iff for all E G we have C' E Cover(O), and for each distinct pair covers C, C² there no (i,j) & Locked(()) such that
((,,j. ((. 5). (1,i,)), (i, if [N], [K]) #
The set of all non-connected cover-groups is denoted as CG(
The next theorem our main lower bound result. It first formulates the optimization problem in Theorem F.1 using the 8-open triplets using dual formulation. Next, given the dual optimization in itself does not highlight the dependence clearly the theorem provides a closed form lower bound (possibly not tight). For this second part we need to define a combined kl divergence per cover C' as
kI(O, C) A
Σ
max E (Locke))))))) (GJJ) S)EC
kl (()s((0)))))(01))
Σ
max Locked()) (ELockee))) (...",
(5)
(10)
5
which we use in the regret bounds.
Theorem F.7. The value of c(f) in Theorem F.I is lower bounded by the value (0) that optimizes the following, for any
E
0
max ())20
Σ
(()), S.t.
Σ
(A) S 1,VM & Stable(B),
(11)
XEVCEComer(o) Ao
where Ag is as defined in Definition F.5.
Furthermore, c(0) satisfies the following lower bound c(0) 2 maXGeca(0) Ecea kl(B, C) where, kl(0, C.) is defined in Equation (10).
The proof is provided in Section G.
Our lower bound in the main paper, Theorem 5.2, is derived from the main lower bound in Theorem F.7. We now make some remarks various definitions used.
We note in the above definition the condition (i) and (ii) together defines the set of minimal vertex covers of a hyper graph over the triplets as vertices, and the partial ranks (Pu. Pa). containing their respective subset of 0-open triplets as edges. The condition (iii) ensures that there exists an instance corresponding to a cover C. For example, it avoids inclusion of two triplets (i,j.i) and (i, cover where (i. Ji) and (i,j2) both are in (ocked(O). This is not realizable because we can not chose a / that simultaneously bigger than (0) and smaller than Pr.ji (0), where Mt.. (0) J4 (0). Condition (iii) is present because we need respect the O-locked property of any À A(6).
Remark on Definition F.:
G. Proof of Results in Section F
Before proceeding to the proof, we need to define the set (A) = () (I(O & 0} contain the pairs where A changes from 8, and for any set of instances A, (A) = (o
We also require the following two lemmas that help with deriving bounds for optimization problem (12).
22

---

Competing Bandits in Matching Markets via Super Stability
The following lemma shows how A(O) can be broken into non-overlapping support and can be used in bounding the optimization problem (12).
Lemma G.1. Consider a group of subsets At C A(0) for 1 E [T]] for L 2 1, such that for any two distinct pair,
(A, we have non-overlapping support (l))(A)) (A)) Then the optimization problem (12) admits lower bound Σ, (maxxex, max ş. (Sthble(0) kl(0, X; M
Next, we provide a kl divergence bound for instances under the set Ac for cover C, as defined in F.5. Lemma G.2. For minimal cover C' E Cover(O) there exists a d that for all M & Stable(0) satisfies kl M) s kl(o, C)) where kl(O, C)) is as defined in Equation (10).
Proof of Theorem F.7. (Part 1) We first show that ce (0). defined in this theorem statement, provides a lower bound for c(0).
The dual of the above optimization problem in in Theorem F.1 is given as
max 2
Σ (a)), s.t. Σ (AA)k(O, A; M) S 1, & Slable(0).
(12)
(EA
AEA(A)
As we need to construct lower bound, any feasible solution of the above dual optimization problem will give us a valid
lower bound. In partieular, for any set A' A(O) can be used to create valid lower bound by setting s(A) 0 for all À & A'. Therefore, Equation (11) is justified as long A' used is a subset of A()). For that purpose, we need to show that for each triplet C' E Co)er(@), for any Ac= = ( 50) that satisfies Equations (7), (8), and (9) we have Ac E A(0). We call the set of As satisfying these three equations for some C' E Cover(0) as (0) Then A' (0) S A()). If for given C' E Cover(#), À satisfies Equation (8) or (9), then the condition b(iz) in Lemma F.3 holds. Also, if X satisfies Equation (7) then À is Ollocked, and b(i) in Lemma F.3 holds. Therefore, by Lemma F.3 we know X E A(0). Hence, the solution to optimization problem in the current theorem forms lower bound for c(0) in Theorem F.I.
(Part 2) The next part of the proof establishes that for any non-connected group G E CG(() we have valid lower bound as EceG RI[O,TT. where (0, C) is as defined in the theorem statement.
Due to Lemma G.1 we want to create group of subsets A₁ S A(0) which are pairwise non-overlapping (same as in Lemma G.I). We choose G E CG) For each C E G we construct singleton set Xe A that satisfies the equations (7), (8), and (9) that has small kl divergence as specified in Lemma G.2. The constructed λe has the property klyo(Ac) S {(;,j): {(i.j.)), j),, (j, -) (i) n + 0}. But as G is non-connecting cover-group we have for any two distinct C, C" E G as kl (lc) n (l>o()a')) = 0. Therefore, due to Lemma G.1 we obtain the lower bound Eceg R((OCC) Taking a max over G E (f) gives us the final result.
G.1. Additional Proofs required for Proof of Theorem F.7
Proof of Lemma F3. For any À E A()) assume (A)(A), Fa(A)) is not l-locked that implies for some (i,j) E Locked (0) we have either (0) * (A) (0))(0) # (A),(A). Which is contradiction. So (F,(A), FA))) must be O-locked.
We next assume that the full rank (Fa Fa())) reverses no 8-open triplet for some partial rank (P. ) PO)) E B(O). Consider any i, E [N] and any j.3' E [K]. Then j > j' implies j' X j. Siiilarly,, >> o' 'implles i x i.
(a)(
Pa))(0)
(A)
Po)
E Full (P, (0), PO)). But that leads to a contradiction as (A), (A)) E P.) F FullRank(PP Pa, P.). So, (F), (A()) must reverse at least one 8-open triplet for each (Pu, Pa) E B(0). This implies that for all À E A(8) the conditions (i) and (tt) in the lemma statement are satisfied.
Hence, (A), (A)) is compatible with (L)),, and (F)
To prove the other direction, for some À let conditions (i) and (ii) are satisfied. Then due to (t), À satisfies (t)(0) May (A), T3a(0) (A), (i,,)) E (f) Next due to (ii), (Fa(A), Fa())) reverses at least one 9-open triplet for each (Pu., Pa) E B()). But that means (F,,)), (a))) is no longer compatible with any (Pu, Pa) E B(0). This in turn implies, from the definition of B()) that (F,(A), Fa (A)) is not compatible with any (Pu, P.) E A(0). This completes the proof.
Proof of Corollary F.4. From Lemma F.3 it immediately follows that if there is one (O), (.) E B(0) that contains no 8-open triplet then A(0)= = G. To conclude that we can statistically attain a sub-logarithmic lower bound (not a constructive argument) we need to show that by playing stable matching we can reach the partial rank (P, (0). ,, Pa (()).. To recover a
partial rank (Pu, Pa) we need to recover all the inequalities that form the partial rank. For (Pu Pa(O) with no 9-open
23

---

Competing Bandits in Matching Markets via Super Stability
triplet any inequality V'
implies both (i.j) and (i,j") lie in Locked(O). But, by playing the set of stable matchings
Pa (0)
in round-robin manner for the first 5)(T rounds, for some E > O we can recover the rewards of (i, and (i,j") up to any (11) accuracy (ccxp(-TT==) by round t. Similar conclusions follows for any inequality i' x i. Therefore, for
(a)
any instance with O(1) reward gaps we can attain a O(1) regret using a uniformly good policy.
Proof of Lemma G.I. The lower bound is obtained by setting ExEA, (()) (maxxeλ, (Stabet))))( kl X; M))- and (A) 0 for all X & UtA, The above choice gives the stated lower bound is easy to see. We need to show the inequalities hold. We pick an arbitrary M & Stable(f) and calculate the right hand side of the bound as follows:
Σ (A) = Σ
E
(A)AE(O, M)
AEA(0)
SE[L] AEA,
E M) max LEIL XEA
max max M)(
Σ (())
LELL, AEA,
AEA
maxiEa, kl X; M)
max
(E(L M maxMesSthle (0) kl (0, M)
The second equality is due the non-overlapping support property of any pair of sub sets (A, A'). Due to this property for any matching M there exists most one E [L] such that ExEs, (AA)k(( X; M) 0. The rests are standard.
Proof of Lemma G.2. We fix an arbitrary cover C E Cover(0), First, observe that for any C E Cover(() (0) we first note that keeping N = (e,( for all (i. such that (i) & C and (i, & C satisfies the inequalities (8). Similarly, keeping 5,, = (0) for all (j, i) such that (j,,, i) & C and (j, i, :) & C satisfies the inequalities (9). So the changes are isolated in the triplets under C. Therefore, it follows that
kl(0, M)
= =E (l(p),(0). P..) + (0)))
(1.)MM
M1(s) (0), Σ LoCk))E)
Σ max
(0) 49,))
3
Lockee))))
$ Σ max
(1((),-)) E V (i.j.)) e (O),
Lockke)))))
Σ max
(1(6);))) EC V (1,4.)) E (0))
Lockee)))
$ Σ max Lockee))) oe (i.d" Loocked]) (aa3") JaEE
max
max
kl(pe, (0) (0) +
+ Σ max ti (( Lockked())
max (2 Je Locked(0) (1.. (.Y
7u (0) 6
The first inequality is true as all non-zero kl distance values isolated to (i,j) & Locked(0) per (7). The second inequality holds as the changes are further isolated to triplets inside the cover C. We now explain the third inequality. For given cover C, by Definition E.5 there is a valid do that satisfies equations (7), (8), and (9). For such a Acs we claim to have for any (i & Locked(O)
min (Loc)eoo) (e
(0) - Pij
C <
max (Lcc)))o (6. JiEc
(0) +e,
(13)
24

---

Competing Bandits in Matching Markets via Super Stability
min (ock)) (a.a)EC
(0. f/s
max (ock)E)okk))()) ( 3)EC
75.0(0) + E,
(14)
Due to the inequalities (7) and (8) we have
pl (1. e, (1,5,'") e C,(1))) Locked(0),
p 2 (0) + e, vj' (i,f.5) C, (i,5") Locked( (0).
Therefore Equation (13) holds. The inequality (14) follows a similar manner.
easy to see the inequality (13) implies
(0), PEg)
S max d==s (eccke)))))) (.dd"Mi s)EC
max (O), + 6).
Similarly, the inequality (14) implies
kd (0),
S max 8 (i S.C-- Locked(()
max
(0),,(0))H,,,00 6).
(aad" Vaa',a)ee
Finally, taking infimum over we obtain the final value of kl(6, C) in Equation 10.
25


Reviews:
[{"review_id": "tHM3yJk4Cg", "reviewer": "Reviewer_pFWb", "summary": "This paper addresses the problem of bandit learning in two-sided matching markets with two-sided reward uncertainty, where both users and arms must learn their preferences through repeated interactions. The authors propose an innovative approach using super-stability from Irving (1994) to enhance traditional Gale-Shapley (GS) algorithms.\n\nThey adapt the Extended Gale-Shapley (GS) algorithm to find super-stable matchings instead of just weakly stable ones.\nSuper-stable matchings are more robust under uncertainty and ensure true stability under complete preference rankings under two kind of incomplete learning models: (i) central and (ii) local. For the central model:\nThe algorithm integrates the Extended GS algorithm with UCB-LCB-based rank estimation. If a super-stable matching exists under the current estimates, the algorithm selects it; otherwise, it explores via a round-robin method. The decentralized algorithm extends the centralized setting with only a constant regret increase, using 2-bit communication between users and arms.\n\nInstance-Dependent Regret Lower Bound:\nA new instance-dependent lower bound for binary stable regret is derived.\nThis bound characterizes the fundamental hardness of the problem using the admissible gap and highlights the pivotal role of super-stable matchings in overcoming informational bottlenecks.\nDecentralized Approach:\nUsers propose to arms, and arms accept based on their preferences.\nTwo shared binary flags coordinate matching and exploration, ensuring efficient learning without a central authority.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review. \n\n**Re How will you make this fully-decentralised?** \nThe binary flags are used to set *restart* to True and *success* to False by individual user or arm. Note that *restart* is set from the user side, and arm side only passively acts on the *restart*  signal. An user that wants to trigger a *restart* can send a <RESTART> signal to all the arms ($K$ rounds if user can communicate with only one arm, or $1$ round if it can communicate with all arms). Once an arm receives a <RESTART> signal, the arms can respond back the <RESTART> signal to all the proposing users. Within $1$ more round all the users will receive the <RESTART> signal, and this will complete the fully-decentralised setting of restart flag. The users can adopt a similar strategy for the *success* flag as well.", "claims_and_evidence": "Centralized: $O(K \\log(T) / \\Delta_A^2)$\nDecentralized: An additional $O(N^2)$ term over the centralized bound.\nLower Bound: $\\Omega(K_{\\text{eff}} \\log(T) / \\Delta_A^2)$ where $K_{\\text{eff}}$ represents the effective number of competing pairs.\n\nThe proof ideas for these claims are correct. I didn’t go through all details.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "All claims are theoretical and look sound to me.", "experimental_designs_or_analyses": "Experiments are well-done. Probably, the authors can show how the results vary with N and K (in a single setup).", "relation_to_broader_scientific_literature": "This will have a broad impact on the community in general since this is a very nice problem to address. It will potentially open doors for other such problems.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. How will you make this fully-decentralised (i.e., without using binary signal mechanism)? This is remarked as a comment but never clearly outlined.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yTYQQTmiPO", "reviewer": "Reviewer_7WSg", "summary": "This paper studies the bandit learning in matching markets with two-sided unknown preferences. It investigates the structure of super stability to determine the exploration-exploitation process. Existing works mainly consider LCB-UCB methods before identifying the full ranking or using known $\\Delta$ to decide the exploration budget. Exploiting super stability to adaptively determine the exploration-exploitation improves the dependence on the $\\Delta$ in the regret. \n\nThe paper proposes both centralized and decentralized algorithms with stable regret upper bound guarantees. The lower bound correspondings to the newly defined $\\Delta$ is also provided. Experiments validate the convergence.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful comments. \n\n**Relationship between $\\Delta_{\\min}$ and $\\Delta_{\\mathcal{A}}$:** \nWe first note that  for the partial rank where the top $N$ user for each arm, and the top $N$ arms for each user are separated we always have the user-optimal matching as a super stable-matching. Hence, $\\Delta_{\\min} \\leq \\Delta_{\\mathcal{A}}$ holds for all the instances. For general instances, it is not possible to improve this relationship, as there are instances where they are equal. \n\n- *We now present a class of instances where $\\Delta_{\\min} = \\varepsilon$,  and $\\Delta_{\\mathcal{A}} = (1 - 2\\varepsilon)$ for any $\\varepsilon > 0$*. \n\nConsider the situation with $N$ users and $N$ arms. Fix any $\\varepsilon > 0$.  For each user $i$  let $\\mu_{i,i} = (1- \\varepsilon)$ and $\\mu_{i,(i+1) mod\\\\, N} = (1- 2\\varepsilon)$ (top 2 arms), and each of the remaining arms has a mean reward $\\mu_{i,j} = \\varepsilon$ for all $j \\notin \\\\{ i, (i+1) mod\\\\, N \\\\}$.  For each arm $j$ let $\\gamma_{j, (j - 1) mod\\\\, N} = \\varepsilon$ and $\\gamma_{j, i} = (1 - \\varepsilon)$ for all $i \\neq  (j - 1) mod\\\\, N$. We have $\\Delta_{\\min} = \\varepsilon$ for this instance. \n\nConsider the partial ranks $P_{u,i} = \\\\{ i > j,  (i+1) mod\\\\, N > j:  \\forall j \\notin \\\\{ i, (i+1) mod\\\\, N \\\\} \\\\}$ for $i \\in [N]$, and $P_{a,j} = \\\\{ i > (j-1) mod\\\\, N, \\forall i \\neq  (j - 1) mod\\\\, N \\\\}$ for $j \\in [K]$. We have $\\Delta_{\\min}(P_u, P_a, \\mu, \\gamma) = (1 - 2\\varepsilon)$ for this partial rank. But this $(P_u, P_a)$ has $\\\\{ (i,i): \\forall i \\in [N] \\\\}$ as a super-stable matching. Therefore, $\\Delta_{\\mathcal{A}} \\geq (1 - 2\\varepsilon)$. \n\nThis shows that there can be *arbitrary* (ratio is unbounded) separation between $\\Delta_{\\mathcal{A}}$ and $\\Delta_{\\min}$.\n\n**Re Missing references:**  We will expand the Table 1 to include more references pointed out by reviewers, including [1], [2], and [3] mentioned in this review. We cite some prior works (including [3]) in the paper, but leave them from Table 1 due to space constraints. \n\n**Re Corollary 2.7:** Thank you for the careful review. We will simplify the double 'for any followed by for all' logic in the final version. In particular, we will replace `for all matching M` by `each super-stable matching M`.\n\n**Re line 12 Algorithm 1:** Note that the $M_{stable}$ match returned by the Extended-GS algorithm may return multiple arm candidates for an user $i$, namely $m_i$. The largest UCB is taken only over $m_i$, not over the entire set of arms $[K]$ in line 12.  For any two distinct users $i$, and $j $, and  their respective arm candidates $m_i, m_j \\in M_{stable}$, we have $m_i$ and $m_j$ are non-overlapping. Therefore, it is guaranteed that  there will be no conflict. We will provide this explanation in the revised version.", "claims_and_evidence": "Yes. The claims are supported by the theoretical analysis and emprical validations.", "methods_and_evaluation_criteria": "Yes. The stable regret and binary regret (market unstability) is commonly adopted in the literature.", "theoretical_claims": "I do not check every detail of the proof. But the stable regret order is standard in existing exploration-then-commit algorithms.", "experimental_designs_or_analyses": "Yes. \n\nSome baselines are missing. For example, the following works also consider bandit learning in matching markets with player-optimal stable regret. \n\nZhang Y, Wang S, Fang Z. Matching in Multi-arm Bandit with Collision. Advances in Neural Information Processing Systems (NeurIPS), 2022, pp. 9552-9563.\nKong F, Wang Z, Li S. Improved Analysis for Bandit Learning in Matching Markets. Advances in Neural Information Processing Systems (NeurIPS), 2024.", "relation_to_broader_scientific_literature": "Yes. This paper on bandit learning in matching markets is related to the machine learning/learning theory/bandits/multi-player literature.", "essential_references_not_discussed": "Yes. Both the table comparisons and experiments lack some necesary baselines. \n\nIn Table 1, after the UCB-D3 algorithm, the following works [1][2] studying player-optimal stable regret and the two-sided unknown setting [3] are missing. \n\n\n[1]Zhang Y, Wang S, Fang Z. Matching in Multi-arm Bandit with Collision. Advances in Neural Information Processing Systems (NeurIPS), 2022, pp. 9552-9563.\n\n[2]Kong F, Wang Z, Li S. Improved Analysis for Bandit Learning in Matching Markets. Advances in Neural Information Processing Systems (NeurIPS), 2024.\n\n[3]Zhang, Y. and Fang, Z. Decentralized two-sided bandit learning in matching market. In The 40th Conference on Uncertainty in Artificial Intelligence.", "other_strengths_and_weaknesses": "Strength: \n\n1. Investigating the super stability is a novel and interesting idea to adaptively balance exploration and exploitation in matching markets. \n\n2. The introduction of the admissible gap is a theoretically novel contribution that refines prior instance-dependent analyses (e.g., \\Delta_min) by incorporating the structure of super-stable matchings. This parameter elegantly captures the interplay between partial rankings and true stability, advancing the literature on problem-dependent regret in matching markets.\n\nWeaknesses: \n\n1. Though the work improves existing dependence on $\\Delta_{\\min}$ using a newly defined gap. The definition relies on the \"admissible partial rank set\" (A(Fu,Fa)), which is abstract and heavily tied to the lattice structure of super-stable matchings. This makes a less intuitive compared to $\\Delta_{\\min}$ and readers may struggle to grasp its relationship to instance hardness without concrete examples. Can you provide some market example to clearly compare these two gaps?", "other_comments_or_suggestions": "The logic of Corollary 2.7 is a little difficult, you can modify it to make the meaning of the sentence clearer.", "questions_for_authors": "In line 12 of algorithm 1, if each player chooses the arm with the largest UCB estimation value, won't there be a conflict? If not, more explanations are required.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Nxkj3b78Kz", "reviewer": "Reviewer_nH7U", "summary": "This paper studies bandit learning in two-sided matching markets where both users and arms have unknown preferences and must learn them through bandit feedback. It introduces super-stable matching, using Irving’s (1994) concept to overcome the limitations of standard Gale-Shapley (GS) algorithms, which only guarantee weak stability under uncertainty. The proposed Extended-GS algorithm, combined with UCB-LCB-based rank estimation, enables efficient matching in a centralized setting with logarithmic pessimal stable regret. A decentralized version is developed using a 2-bit communication protocol, incurring only a constant regret increase. The paper also establishes a new instance-dependent lower bound, showing that the admissible gap is a key complexity parameter for stable matching with bandit feedback.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback. We first want to clarify the paper's scope.\n\nThis paper advances bandit learning for finding *any* stable matching in matching markets. It demonstrates Extended-Gale Shapley's effectiveness over standard Gale Shapley and uses super-stable matching structure for instance-dependent regret lower bounds. Developing methods for real-world challenges (large-scale, communication constraints, collusion robustness) is outside this paper's scope, consistent with most work in this area, and will be highlighted as future work.\n\nPlease find individual responses below.\n\n**Re Missing References:** Pagare & Ghosh (2024) is cited in the Introduction (page 1, column 2, paragraph 2) and Table 1. We could not locate Dai & Jordan (2021), “Learning Stable Matches with Uncertainties in Preferences” (NeurIPS 2021), and believe the reviewer may refer to \"Learning in Multi-Stage Decentralized Matching Markets.\" This paper addresses preference uncertainty using nonparametric statistics and variational analysis, making it not directly related. We will add it to our citations of loosely connected prior works.\n\n**Re lack of empirical comparison:** Our algorithm is compared against the centralized two-sided version of Kong et al.'s Explore then Gale Shapley, which, as stated, is the centralized variant of Pagare & Ghosh (2024) and Zhang & Fang. Therefore, we respectfully disagree that our empirical results do not compare against the recent two-sided matching bandit algorithms. Furthermore, no non-adaptive exploration baseline exists for bandits in matching market with two-sided uncertainty (to our knowledge).\n\n**Re How tight is the instance-dependent regret lower bound in practice?** We are unclear about what is meant by `practical tightness of the lower bound`. If the reviewer asks about the upper and lower bound gap, we reiterate that a tight bound for bandits in two-sided matching markets is beyond the current state-of-the-art. Our work establishes a lower bound for binary stable regret, leaving optimal algorithm design for future work.\n\n**Re focus on pessimal stable regret:** This work explores the complexity of bandit learning for finding *any* stable matching, contrasting with finding a specific one. Our binary stable regret quantifies the hardness of this objective, for which we provide regret upper and lower bounds.  Note this was the original objective in Liu et al (2020) as well.\n\nOptimizing regret for a specific stable matching (e.g. user-, arm-, or social-optimal) is a related learning objective that can leverage our findings. In particular, using the distributive lattice structure of the stable-matching efficient exploration for this task can be designed (in future) once *any* stable matching is found. \n\n**Re Why was the decentralized algorithm not evaluated empirically?** The centralized and decentralized algorithms are closely linked. We prove the decentralized algorithm's regret is at most $(1+N^2)$ higher (uniformly across instances and time T) than the centralized one. We will include decentralized algorithm simulations in the revised version to demonstrate this empirically. Our synthetic experiments focus on highlighting the effectiveness of Extended Gale-Shapley versus Gale-Shapley variants, for which the $(1+N^2)$ regret addition provides no further insight.\n\n**Re How sensitive is the performance to different exploration strategies?** Our regret upper bounds hold (up to reward gap-independent constants) as long as the exploration strategy ensures all (user, arm) pairs are explored with a constant fraction in the long run. Round robin exploration, adopted in prior work for its simplicity, ensures uniform long-run exploration. Finding an optimal non-adaptive exploration strategy is outside this work's scope. We believe under-exploring \"unlikely\" (user, arm) pairs is promising, but the two-sided uncertainty and numerous stable matchings complicate non-adaptive exploration.\n\n**Re Why were no real-world datasets used, and how would the method generalize?** This work, like most prior work in this area, focuses on establishing theoretical guarantees. Evaluating with real-world datasets is typically outside this line of work's scope. The reviewer's question about generalization is unclear. Scaling to large systems is beyond this paper's scope and is often addressed by contextual reward modeling, as recently considered for one-sided matching markets in Parikh et al. \"Competing Bandits in Decentralized Large Contextual Matching Markets\" arXiv:2411.11794.", "claims_and_evidence": "The efficiency of the round-robin exploration strategy is theoretically justified, but it may not be the most optimal choice in practice. There is a lack of alternative exploration strategies leaves room for stronger empirical support. Additionally, while the decentralized algorithm is claimed to be scalable with a 2-bit communication protocol, no empirical evidence is provided to demonstrate its performance in large-scale settings, where factors like network latency and asynchrony could impact its effectiveness. Finally, the claim that the method is applicable to real-world matching markets (e.g., crowdsourcing, ride-sharing, college admissions) is plausible but remains untested on real-world data—all experiments are conducted on synthetic setups, making it unclear how the approach would handle dynamic, highly imbalanced, or adversarial market conditions.", "methods_and_evaluation_criteria": "The experiments are conducted only on synthetic data, with no real-world datasets or practical case studies to validate the approach’s applicability in markets like crowdsourcing, ride-sharing, or college admissions. While synthetic setups allow for controlled comparisons, real-world dynamics, preference heterogeneity, and strategic behavior could introduce additional challenges not captured in the current evaluation. Furthermore, while the decentralized algorithm’s theoretical regret bound is well-analyzed, its empirical performance is not tested—the experiments focus only on the centralized approach. Given that real-world markets often involve decentralized decision-making with communication constraints, an empirical assessment of the decentralized method’s scalability and robustness would strengthen the paper. Finally, the exploration strategy (round-robin exploration) is simple but potentially suboptimal, and it would be valuable to compare it against adaptive exploration strategies to assess trade-offs in convergence speed. Expanding the evaluation to real-world scenarios, alternative exploration techniques, and decentralized settings would enhance the credibility and impact of the proposed methods.", "theoretical_claims": "I checked the proofs for Proposition 2.5 & Corollary 2.7, Theorems 3.5 & 4.1, and Theorem 5.2.  The regret analysis follows standard UCB-based techniques and introduces the admissible gap, though the reliance on round-robin exploration may be loose compared to adaptive strategies. The instance-dependent lower bound is derived using Combes et al. (2017) and Graves & Lai (1997).  Some assumptions are too strong: e.g.,  the scalability of the decentralized approach assumes perfect phase synchronization, which may not hold in real-world applications, and the impact of preference ties on convergence is not explicitly addressed.", "experimental_designs_or_analyses": "The experimental design has notable limitations. The evaluation is entirely based on synthetic data, with no real-world datasets or application-driven case studies, making it difficult to assess how well the algorithm generalizes to real-world markets with dynamic and imbalanced preference structures. Moreover, while the centralized algorithm is tested, the decentralized version is not empirically evaluated, even though its theoretical regret bound is derived. Given that real-world matching markets often operate in decentralized settings, an empirical study on scalability, robustness, and communication constraints would significantly strengthen the paper. Additionally, the round-robin exploration strategy, while simple, is not compared against more adaptive exploration approaches, leaving open the question of whether a more intelligent exploration mechanism could further improve performance.", "relation_to_broader_scientific_literature": "First, it connects to the bandit learning literature, particularly structured multi-armed bandits in matching markets. The problem of learning stable matchings under uncertainty was first introduced in Das & Kamenica (2005), which considered single-sided uncertainty, where only users needed to learn preferences while arms had full information. Subsequent works, such as Liu et al. (2020) and Sankararaman et al. (2021), focused on decentralized learning algorithms in matching markets but assumed single-sided uncertainty and relied on the standard Gale-Shapley (GS) algorithm, which only guarantees weak stability. The Explore-then-Gale Shapley (ETGS) framework developed in Kong & Li (2023) improved upon these results by allowing for user-optimal stable regret minimization. This paper differs from these works by introducing two-sided uncertainty and leveraging super-stable matching—a concept from Irving (1994)—to guarantee true stability rather than weak stability.\n\nIn terms of matching theory, the paper draws from classical stable matching literature, particularly the Gale-Shapley (1962) deferred acceptance algorithm, but expands upon it by incorporating super stability from Spieker (1995). Prior work in bandit-based stable matching relied on weakly stable matchings under partial information, leading to suboptimal matching assignments when full rankings were revealed. By integrating Irving’s Extended Gale-Shapley algorithm, the paper provides a more robust stability concept that ensures convergence to fully stable matchings under incomplete preferences.\n\nRegarding regret analysis in bandit learning, the paper advances the theoretical understanding of instance-dependent regret bounds in structured matching problems. The instance-dependent regret lower bound derived in Theorem 5.2 builds upon the KL-divergence-based minimization techniques from Combes et al. (2017) and Graves & Lai (1997), but specifically tailors them to two-sided matching problems with bandit feedback. \n\nHowever, while the theoretical contributions are well-situated within the literature, the paper lacks empirical comparisons to recent two-sided matching bandit algorithms (e.g., Pagare & Ghosh (2024), Zhang & Fang), particularly in scalability and real-world performance. A broader experimental evaluation across different matching frameworks could further strengthen the paper’s impact in this domain.", "essential_references_not_discussed": "Missed references: Pagare & Ghosh (2024), “Explore-Then-Commit Algorithms for Decentralized Two-Sided Matching Markets” (ISIT 2024)\nThis paper also provides instance-dependent regret bounds but under different matching assumptions. A comparison between the admissible gap used in the current work and the regret characterizations in Pagare & Ghosh (2024) could strengthen the novelty and justification of the new lower bound in Theorem 5.2.\n\nDai & Jordan (2021), “Learning Stable Matches with Uncertainties in Preferences” (NeurIPS 2021). The omission of Dai & Jordan (2021) NeurIPS is a significant gap in the paper’s literature review. Including it would situate the contributions more precisely within the existing body of research on bandit learning in stable matching, particularly regarding the differences between static and dynamic uncertainty settings.", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. How tight is the instance-dependent regret lower bound in practice?\n\n2. How does the super-stable matching framework compare to user-optimal stable regret frameworks?\n\nThe paper focuses on pessimal stable regret, whereas recent works such as Hosseini et al. (2024) and Kong & Li (2023) optimize for user-optimal stable regret.\n\n3. Why was the decentralized algorithm not evaluated empirically?\n\n4. How sensitive is the performance to different exploration strategies?\n\n5. Why were no real-world datasets used, and how would the method generalize?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l8NLtNvi1t", "reviewer": "Reviewer_MWcb", "summary": "The paper identifies a problem with using the Gale-Shapely algorithm for stable matching with two-sided uncertainty: finding a weakly stable matching based on partial ranking doesn't give guarantees for the full ranking. Instead, they build on a different algorithm: finding a super stable ranking that guarantees consistency between partial and full rankings. Based on that they build an algorithm to minimize the regret and analyze the instance-dependent lower bound and an upper bound. They also propose a decentralized version of the algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable review. Please find the responses below.\n\n**Re  motivation for regret instead of pure-exploration:**  In online learning (including matching markets), guaranteeing good cumulative performance and minimizing losses is crucial. Regret, unlike pure exploration, balances learning (exploration) with earning (exploitation) to maximize total rewards. Pure exploration focuses solely on identifying the best option, disregarding rewards gained during learning. Consequently, the importance of cumulative reward in matching markets (e.g., e-commerce marketplaces) makes regret minimization a natural objective. \n\n**Re motivation of Bandits in Matching Markets:** Bandit learning in matching markets is an active field of research with a long and rich history, starting with Das & Kamenica (2005). This paper is not introducing the problem. This area has seen significant research, with over [100 publications](https://scholar.google.com/scholar?q=%22bandit+learning%22+AND+%22matching+markets%22) since then, and a recent surge in activity beginning with Liu et al. (2020). This paper pushes the frontier of bandit learning for finding any stable matching in matching markets. It proves Extended-Gale Shapley's advantage over the standard version and leverages super-stable matching structure to establish tighter, instance-specific regret lower bounds.\n\n**Re why is $N \\leq K$:** We present the results with $N \\leq K$ for notational convenience, but the results and respective proofs presented in this paper can be easily generalized to $N > K$ (only notational and textual changes required).\n\n**Re motivating example for $N \\leq K$:** Let us consider the two sided e-commerce marketplace, such as UpWork, where clients submit specific tasks (number of task is $N$) and there are multiple vendors that can be matched with the tasks (number of vendor is $K$). In these platforms often the number of tasks is much less compared to the number of vendors (i.e. $N \\leq K$).  As mentioned above, we do not claim that $N \\leq K$ is more interesting than the $N> K$ scenario. The presentation is just for notational convenience. \n\n **Re the source of uncertainty for these two-sided problems in real life?**\nUncertainty in two-sided matching stems from a-priori unknown payoffs between users and arms, and vice versa. In the e-commerce marketplace example, a client's reward (denoted as $\\mu_{i,j}$) depends on the vendor's skillset, but the vendor's execution is randomized, varying due to latent extrinsic factors modeled by reward distributions. Similarly, a vendor's preference for a client depends on factors like payment and trustworthiness, which can also vary due to latent extrinsic factors, leading to the vendor's reward  (denoted as $\\gamma_{j,i}$) being modeled by random variables. We will expand on this in the revised version of the paper.", "claims_and_evidence": "Yes, mostly clear", "methods_and_evaluation_criteria": "My main concern with the paper is the notion of optimizing regret in the case of stable matching. From the user perspective, what matters most is that the algorithm converges quickly and not so much that the intermediate arms that are chosen are low-regret. In this case, I don't see why the authors don't present a bound for a pure-exploration version of the stable matching instead of the low-regret version. This limits the impact of the paper as the main metric of interest is mismatched with the motivating problem.", "theoretical_claims": "Mostly yes but why is N <= K? In how many cases are the number of users smaller than the number of options? For example, on of the motivations for stable matching is matching students to universities. Are the authors saying the interesting case is when there are fewer students than colleges? Fewer users than the number of crowd-sourcing tasks? If their contribution is only interesting in the case of N <= K, then that limits the impact of the paper.", "experimental_designs_or_analyses": "Theoretical paper, does not apply.", "relation_to_broader_scientific_literature": "The users find an interesting problem with the stable matching problem and correctly connect it with the super stable matching from the Irving 1994 paper.", "essential_references_not_discussed": "None, that I see.", "other_strengths_and_weaknesses": "Bandits have been well studied over the past. The bar for introducing a new algorithm is high and both novelty and a good motivation for a real-world problem needs to be met. My main concern here is with the motivation of this problem and the regime in which it is proposed.", "other_comments_or_suggestions": "Line 21: should be learn instead of elarn", "questions_for_authors": "It would be good to talk about the motivation for regret instead of pure-exploration. Also, what are motivating examples where N <= K? The one that I can think about is the organ donor problem potentially. Also: what is the source of uncertainty for these two-sided problems in real life? Again, connect the uncertainty to a real-world problem.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles the challenges of bandit learning within the context of two-sided matching markets, specifically addressing the complexities of two-sided reward uncertainty. In this dynamic environment where both users and arms must refine their preferences through repeated interactions, the research explores approaches to improve learning outcomes.

The regret analysis employs standard Upper Confidence Bound (UCB) techniques while introducing the concept of the admissible gap, a significant contribution to the field. However, while the method offers valuable insights, it's worth noting that its reliance on round-robin exploration may be less effective compared to more adaptive strategies that could potentially enhance learning efficiency and performance.

Despite the promising theoretical framework, the evaluation relies exclusively on synthetic data. This narrow focus raises questions about the algorithm's applicability in real-world scenarios, where markets are often characterized by dynamic and imbalanced preference structures. The lack of real-world datasets or application-driven case studies limits our ability to ascertain how well the proposed algorithm would perform in practical settings.

Nevertheless, it is important to highlight that most reviewers expressed positive feedback about the paper's contributions, reflecting a recognition of its potential value to the field. Given this encouraging response, I find myself inclined to recommend a weak acceptance, hoping that further refinements could bridge the gap between theory and real-world application.
Decision: Accept (poster)