Bandit Learning in Matching Markets with Indifference
Authors: Fang Kong
Jingqi Tang
Mingzhu Li
Pinyan Lu
John C.S. Lui
Shuai Li
Venue: ICLR 2025 Poster (2025)
Keywords: Bandits
Matching markets
Indifference
Stable regret
Primary area: learning theory

Abstract: A rich line of recent works studies how participants in matching markets learn their unknown preferences through iterative interactions with each other. The two sides of participants in the market can be respectively formulated as players and arms in the bandit problem. To ensure market stability, the objective is to minimize the stable regret of each player. Though existing works provide significant theoretical upper bounds for players' stable regret, the results heavily rely on the assumption that each participant has a strict preference ranking. However, in real applications, multiple candidates (e.g., workers in the labor market and students in school admission) usually demonstrate comparable performance levels, making it challenging for participants (e.g., employers and schools) to differentiate and rank their preferences. To deal with the potential indifferent preferences, we propose an adaptive exploration algorithm based on arm-guided Gale-Shapley (AE-AGS). We show that its stable regret is of order $O(NK \log T / \Delta^2)$, where $N$ is the number of players, $K$ the number of arms, $T$ the total time horizon, and $\Delta$ the minimum non-zero preference gap. Extensive experiments demonstrate the algorithm's effectiveness in handling such complex situations and its consistent superiority over baselines.

Published as a conference paper at ICLR 2025
BANDIT LEARNING IN MATCHING MARKETS WITH IN- DIFFERENCE
Fang Kong* Jingqi Tang
Mingzhu Li*
Pinyan Lu
John C.S. Lui"
Shuai Lill
ABSTRACT
A rich line of recent works studies how participants in matching markets learn their unknown preferences through iterative interactions with each other. The sides of participants in the market can be respectively formulated as players and arms in the bandit problem. To ensure market stability, the objective is mini- mize the stable regret of each player. Though existing works provide significant theoretical upper bounds for players' stable regret, the results heavily rely on the assumption that each participant has strict preference ranking. However, in real applications, multiple candidates (e.g., workers in the labor market and students school admission) usually demonstrate comparable performance levels, making it challenging for participants (c.g., employers and schools) to differentiate and rank their preferences. To deal with the potential indifferent preferences, propose adaptive exploration algorithm based on arm-guided Gale-Shapley (AE-AGS). We show that its stable regret is of order O(NK log T/A?), where N is the number of players, K the number of arms, T the total time horizon, and A the minimum non-zero preference gap. Extensive experiments demonstrate the algorithm's ef- fectiveness in handling such complex situations and its consistent superiority over baselines.
INTRODUCTION
The two-sided matching market is a fundamental concept in economics and operations research (Gale & Shapley, 1962; Roth, 1984; Roth & Sotomayor, 1992; Roth & Peranson, 1999; Fleiner, 2003). It provides a formal framework to model interactions between two distinct sides of agents and has wide range of applications such as labor markets (Kelso Crawford, 1982; Roth, 1984), school admission (Roth, 2008), house allocation (Sönmez & Ünver, 2011), and so forth. Each agent (e.g., employer) has his own preferences over the other side (e.g., workers in labor markets) and seeks form beneficial pairings. To keep the stability of the market and thus avoid dissatisfaction of agents and future inefficiencies, a rich line of works study how to find a stable matching in the market (Gale& & Shapley, 1962; Roth, 1984; Roth & Sotomayor, 1992; Kelso Jr & Crawford, 1982), among which the Gale-Shapley algorithm (Gale & Shapley, 1962) is one of the most classic one. All these works assume that agents' preferences are known prior.
However, prior knowledge of preferences may not always be fully certain in real-world applications. For example, employers typically cannot precisely assess a worker's abilities before they are hired. A stable matching derived from temporal preference estimation may not ensure long-term stability. With the rise of online marketplaces such as the online labor platform Upwork and the crowdsoure- ing platform Amazon Mechanical Turk, employers are increasingly able to learn about uncertain preferences through iterative matching processes driven by their released multiple tasks. The multi- armed bandit (MAB) is a classic model that characterizes the learning process for agents towards
"kongf@susttec.eddu.cc Southern University of Science and Technology "sjjuul2267762248sjju I "justbeme@sjttu.ddu en. Shanghai Jiao Tong University
en. Shanghai Jiao Tong University
cn. $1u. mlu.pinyan@mail.shhi shufe. cn. Shanghai University of Finance and Economics; Key Labora- tory of Interdisciplinary Research of Computation and Economics (SUFE), Ministry of Education
1 deslui@csee cubk. edu. hk. The Chinese University of Hong Kong
ll Alghaal 180s jtu. edu. en. Shanghai Jiao Tong University. Corresponding author

---

Published as a conference paper at ICLR 2025
uncertain information (Auer et al., 2002; Lattimore & Szepesvári, 2020), also offering solutions for agents in matching markets to learn their unknown preferences.
The classic MAB model contains one player and K arms. Each arm aj is associated with un- known reward pj. The player would learn this knowledge through iterative selections. The objective of the player is maximize the cumulative rewards, equivalent to minimizing the cumulative regret defined as the cumulative distance between the optimal reward and received rewards. To achieve this oong-horizon objective, the player faces the dilemma of exploration and exploitation. The former hopes to select the arm with fewer observed times to know the arm better, and the latter hopes to se- lect the better-pertte pertor-perf arms to accumulate as many rewards as possible. The sxplore-teen-coe (ETC) (Garivier et al., 2016), upper confidence bound (UCB) (Auer et al., 2002) and Thompson sampling (TS) (Thompson, 1933) are common strategies to deal with the problem.
The bandit learning problem in matching markets recently attracted great interest in the literature, where two sides of participants can be modeled as players and arms. Players can learn their unknown preferences through interactions with arms. Das & Kamenica (2005) first introduces the framework and proposes empirical solutions. Liu et al. (2020) further gives a formal theoretical formulation and derives algorithms with theoretical guarantees on the stable regret, which is defined as the cumulative distance between the reward in a stable matching and the reward received during the interactions. In the matching market scenario, due to the interference among multiple agents, the selections of an individual player can be easily blocked, making the trade-off between exploration and exploitation more challenging. To avoid conflicts among players, Liu et al. (2020) consider the centralized setting where a central platform collects information from participants and assigns partners for players. A rich line of the following works try to improve their stable regret bound and generalize the model by considering the decentralized setting (Liu et al., 2021; Sankararaman et al., 2021; Basu et al., 2021; Maheshwari et al., 2022; Kong et al., 2022; Zhang et al., 2022; Kong & Li, 2023).
Despite the significance of the results, all existing works assume each market participant has strict preference ranking, i.e., the preference values towards different candidates are different. However, this assumption may not be realistic. In many applications such as labor market and school admis- sion, multiple candidates usually demonstrate similar performances, leading to ties of preference rankings. Especially in large markets, maintaining a strict preference ranking over all candidates can be extremely time-consuming and effort-intensive,, while the marginal benefit of distinguishing between closely ranked candidates may be minimal. To improve the practicality and robustness of algorithms, it is crucial to deal with participants' indifferent preferences (Erdil & Ergin. 2008; A Abdulkadiroglu et al., 2009; Chen, 2012; Erdil & Frgin, 2017; Erdil & Kumano, 2019).
The tate--o--theaat approaches in matching markets employ an explore-then- SaaethhhnnGGe-SSiiee Shapley strategy to address the iittooration-xploittaii 2024). In these methods, exploration continues until players have identified all preference gaps, after which the algorithm transits exploitation, applying the Gale-Shapley algorithm (Gale & Shapley, 1962) to achieve stable matching. However, once two arms exhibit identical preferences. the exploration process would never stop, leading the algorithm to incur an OT)) regret, where T represents the total time horizon. With indifferent preferences, the algorithm faces new difficulties in balancing exploration and exploitation. Prolonged exploration could incur additional regret, while prematurely halting exploration may result in incorrect ranking estimates, leading to ntn-stable matching.
trade-off (Zhang al., 2022; Kong & Li, 2023; Kong al.,
In this work, we try to overcome the above challenge for the bandit learning problem in matching markets with indifference. Though existing results all assume market participants have strict prefer- ence rankings, we examine whether they can be extended to the indifference setting. As summarized in Table 1, only Liu et al. (2020) and Basu et al. (2021) can apply to indifference. However, their approaches either require knowledge of A or suffer exponential regret. We propose more suitable policy to balance exploration and exploitation an arm-guided adaptive exploration algorithm where players only explore arms that propose them and adaptively eliminate sub-optimal arms, for both the centralized and decentralized setting, This design allows players to explore freely without the need explicitly distinguish between exploration and exploitation processes. We show that such an algorithm achieves the stable regret of order O(N log T where N is the number of players,
2

---

Published as a conference paper at ICLR 2025
K' is the number of arms, T is the total horizon and A is the minimum non-zero gap'. Extensive periments are conducted to show our algorithm's 's effectiveness and consistent advantage compared with available baselines.
Table 1: Comparisons related results. is the number of players, K is the number arms, A the minimum preference gap among all players for different arms in existing works, and is the minimum zon-zero preference gap among all players for different arms the result holds under indifference. P, e are hyper-parameters. C and D represent centralized and decentralized settings, respectively. We use tiny font to annotate the parts of the original proof where it fails to hold under indifference and provide more details Appendix A.
References
Stable regret bound
Setting
Holds under indifference?
Liu et al. (2020)
O
N. Iog
C
X (orollary
A²
Liu et al. (2021)
N' log p
D
X (Lmmma
Kong et al. (2022)
NO K2 log"
X (L
p
Zhang et al. (2022)
K log
X (2dd paragragh 16)
A²
Kong & Li (2023)
K log
X Lemmaa 4)
A²
Kong et (2024)
N²
C&D
X (Lmmma A.5)
A
Liu al. (2020)
K log T
(Known A)
A²
Basu al. (2021)
O
K log
+c 24-2/1 -2/-
Ours
O
NK log
C&D
V
A²
RELATED WORK
The model two-sided matching markets has been studied for many years (Gale & Shapley, 1962; Roth, 1984; Roth & Sotomayor, 1992). The seminal work (Gale & Shapley, 1962) proposes the Gale-Shapley algorithm to compute stable matching in the one-to-one markets. Some research has extended the algorithm to address more complex markets with different preference structures (Kelso Jr & Crawford, 1982; Roth Sotomayor, 1992). Most these works analyze the algorithm based the assumption that all participants have strict preference ranking. When participants have indifferent preferences, Irving (1994) define different levels of stability and propose algorithms to achieve them. Erdil & Ergin (2008) propose method to improve satisfaction from given stable matching. Abdulkadiroglu et al. (2009) consider the strategy-proofing of the mechanism that whether participants have incentive deviate from the algorithm.
When market participants have uncertain preferences, Das & Kamenica (2005) first introduce the bandit model into matching markets. They propose an e-greedy type algorithm and demonstrate its empirical performances. Liu et al. (2020) theoretically formulate this problem. They mainly study the centralized setting with central platform computing the matching in each time slot. Both an ETC and UCB-type algorithm are proposed for this setting. The former achieves O(K log ) regret with the knowledge of A and the latter achieves O(N log T2) Liu al. (2021) and Kong et al. (2022) generalize the problem to the decentralized setting, where players need to coor- dinate their selections to avoid invalid explorations due to conflicts. However, due to the interfer- ence of multiple agents in the decentralized markets, their algorithm suffers an exponential order of regret. improve the learning efficiency, Sankararaman et (2021); Basu et al. (2021); Mahesh- wari et al. (2022); Wang & Li (2024) consider the setting where participants' preferences satisfy special assumptions thus the interference becomes easier. For these special markets, they provide an O(N K log T ?) or O(N log Tog /²) regret guarantee. Until recently, Zhang et al. (2022) and Kong & Li (2023) independently propose an Saaborr-thhn-Gal-SShhaaa
procedure and show an
If all preference gaps zero, show our stable regret is 0 in the centralized setting and is O T) in the decentralized setting.

---

Published as a conference paper at ICLR 2025
logT) stable regret upper bound for general markets. In all of the above works, both players and arms are assumed to have strict preference rankings and A is defined as the minimum preference gap among all players over different arms, which may be 0 under indifference. Our work follows this line and considers the more general indifference setting.
A contemporary work (Lin et al., 2024) also investigates the indifference setting. They first consider the offline setting where players have known preferences and propose an a-approximate oracle that returns matching in which each player's utility is at least an a fraction of their optimal utility across all stable matchings. They further extend this oracle to the bandit setting, obtaining results on a- a-approximate player-optimal stable regret. Their analysis also yields a problem- -idlllednedeeeeeentt regret of order (TT2/)). Different from this work, we focus on stable regret, which is defined on the least reward among all stable matchings, and do not consider approximate guarantees.
There are also other works studying the uncertain preferences in matching markets. The variants include the market where both sides of agents have unknown preferences (Pagare & Ghosh, 2023), the contextual markets where the player's preferences can be represented by the inner product be- tween the preference vector and the arm feature (Li et al., 2022), the many-to-on -o-onet-oneeeeeoo markets where one side of agents can match more than one partners (Wang et al., 2022; Kong & Li, 2024; Li al., 2024; Zhang & Fang, 2024), as well as the non-stationary markets where the preference of agents vary over time (Ghosh et al., 2022; Muthirayan et al., 2023).
PROBLEM SETTING
This section introduces the problem setting of bandit learning in matching markets with indifference. Denote N = (p1. ....... Pvvl }or as the player set and IC = {aI, a2 ax } as the arm set, where N and K represent the number of players and arms, respectively. To ensure each player has chance to be matched, we assume N < K as existing works (Liu et al., 2020; 2021; Sankararaman et al., 2021; Basu et al., 2021; Zhang et al., 2022; Kong& & Li, 2023; Wang & Li, 2024).
Each market participant has a preference ranking over the other side. Specifically, the preference value of player Pa over arm aj can be portrayed by a real value P4j E (0, 1]. A higher value represents more preferences, i.e., Hij > H4.j'' implies pt prefers aj to ay. These preference values are unknown and need to be learned through interactive interactions with arms. It worth noting that all existing works (Liu et al., 2020; 2021; Kong et al., 2022; Sankararaman et al., 2021; Basu et al., 2021; Zhang et al., 2022; Kong & Li, 2023; Wang & Li, 2024; Kong et al., 2024) assume the preference values over different arms are different, i.e., Majj + Máij'' for any player pE and arms ay. However, this assumption is often unrealistic in practical applications, as multiple arms (e.g., workers in labor markets students in school admission scenarios) usually exhibit similar performances, making it difficult for players to explicitly differentiate their preferences. We relax this assumption by allowing indifferent preferences, i.e., the player can have the same preference values over different arms. On the other side, each arm aj also has preferences over players. Denote TJ. the position of p; in aj's 's preference rankings. Arms can also have indifferent preferences over players. We use jjz - Tj to denote that p; has a higher ranking so is more preferred than Py by aj- And .y. = J represents aj can not distinguish the performances between p; and py. Similar to the labor market scenario where workers (arms) usually have an evaluation system based on the known characteristics of the employers (players) such as the salary, location, and so forth, we assume each arm knows their own preference ranking as existing works (Liu et al., 2020; 2021; Kong et al., 2022; Sankararaman et al., 2021; Basu et al., 2021; Zhang et al., 2022; Kong & Li, 2023; Wang& & Li, 2024; Kong et al., 2024).
The players would iteratively interact with the arms. At each time slot / = 1,2, 3, ..... each player p;
selects an arm (!) E KU[-1), where we use -1 to represent that y; does not select any arm in this
time slot. For the arm side, each arm aj receives the proposals from A (t) = {p: : A.(t) = a))- Due to the capacity constraint, it only accepts the most preferred one, i.e.. the player * e
arg min min AEA"' (t) Ty.; with the highest preference ranking. When there are multiple choices, the arm would randomly break the tie. For the player side, any player p; whose proposal is accepted would successfully match with (t).. It would receive reward (t)) (t) characterizing its satisfaction over this matching experience, where we assume the reward is a 1-subgaussian random variable with expectation (0) existing bandit works (Lattimore& & Szepesvári, 2020). And if p proposal is
4

---

Published as a conference paper at ICLR 2025
rejected, it only receives (t) (t) O. For convenience, A(t) (A,(t))eE[M) represent the final matching outcome in time slot i, where A,(t) (t) if p; is successfully matched and (,) = -1 otherwise.
To ensure long-term equilibrium in the market, the players aim to find stable matching. Given matching : (A:)sE(N). if there exists a pair (pi, az) such that pi prefers 0j to its current partner A, and aj also prefers pa to its current partner AJ', i... Pis M4,A, and ī X ",,4,' then p; and aj has the incentive to deviate from their partners. In this case, the matching A is unstable, and such a pair is called blocking pair. stable matching is matching without any blocking pair. It is worth noting that there may be more than stable matching in the market. Denote M : = [m == (m)) m is stable) as the set of all stable matchings. Existing works study the player-optimal stable matching (Liu et al., 2020; Zhang al., 2022; Kong Li, 2023; Kong al., 2024) which is defined as the stable matching in which all players are matched with their most preferred arm among all stable matchings and the player-pessimal stable matching (Liu al.. 2020; 2021: Kong et al., 2022) which is defined as the stable matching in which all players are matched with their least preferred arm among all stable matchings. However, when the market participants have indifferent preferences, such two stable matchings may not exist. Example 3.1 illustrates one possible case.
Example 3.1. The market contains players and arms with the preference rankings listed below:
P1 : 01 = 02 > a3
a1 a1:P1 X P2 = Р3
P2 d2 03
P2:P1 P2 p3 0g : P2 - P3
Ps 01 > 02 > 03
where a2 > a2.forp p1 implies Pı prefers a2 over ag. In this market, both {(11, a2), (p2, a1), (ps, a3)} and ((),,2), (P2, a3), (p3,01)) are stable matchings. But players p2 and p3 do not match with the most preferred arm common stable matching.
In this work, we focus the stable regret of each player which is defined the difference between the least reward (i,m, = minm'EM (4sm; that can be obtained in any stable matching and the reward accumulated during the interaction process, i.e.,
T
Reg. (T) = E
(pi.m. - (1))
(1)
where the expectation taken from the randomness of the reward and players' policies?.
4 ALGORITHM IN THE CENTRALIZED SETTING
In this section, we introduce our proposed adaptive exploration with arm-guided GS (AE-AGS) algorithm. To better convey the algorithm idea, we first present the centralized version (Algorithm 1) where central platform collects information from market participants and computes the matching.
Algorithm 1 adaptive exploration with uum-guided GS (AE-AGS, centralized version, from the view of the central platform)
1: for time slot 1, 2,.. do
2: Collect the arms' preference rankings (TTA))SENN from each arm aj E
3: Collect the matched times (Ti,))e(K) and the comparison matrix (Better((,,..")))aee from each player p; EV
4: Compute A(t) = Sf (T Tai Better(t...
5: Assign the arm (t) each player p: e N
6: end for
It worth noting that the worst partner for all players may not appear in a single stable matching. As demonstrated in the proof, we bound the stable regret by constraining the number of unstable matchings. So stable regret upper bound also applies to the cumulative market instability (the cumulative number of unstable matchings).
5

---

Published as a conference paper at ICLR 2025
Specifically, in each time slot f, each arm a, would submit its preference ranking (TT)))ie[N] to the central platform (Line 2). If multiple players share the same preferences. the arm can randomly break the tie. And each player p, maintains counter Tı representing the number of times that P; is matched with arm az- It also maintains a comparison matrix Better among each arm pair. Better(i, j') means Pr estimate that it prefers a, over ag. And Better(i, J. 0 means ps still cannot distinguish the performances between aj and ay', or estimates that it prefers ajr over aj. The player would submit the counter and comparison matrix the central platform (Line 3).
Then, the central platform would compute a matching A(t) based on the collected information (Line 4) and assign the target arm (t) to player pt (Line 5). The detailed procedure to compute A(t) is summarized in the subroutine-of- of-AE-AGS algorithm (Algorithm 2). In general, Algorithm 2 can be regarded as an adaptive exploration algorithm based on GS with the arm side as the proposing side. Arms would propose to their most preferred players hased on their submitted preference rank- ing (Line 3). Among the received proposals, players would first compute the estimated sub-optimal arms, i.c., arm új can be regarded as sub-optimal if there exists a player ay such that p; deter- mines it prefers ay over a, (Line 5). Each player P; would accept the proposal from the potential optimal arm with the least matched times (Line 6). If the arm is not accepted by its proposed player, it proposes to the next preferred player (Line 8). Until all arms are matched or have proposed all of the N players (Line 2), the algorithm stops and outputs the final matching. It is worth noting that Algorithm ensures that all players are assigned different arms when stopping since N I K.
Algorithm Subroutine-of-AE-AAG
Input: Arms' preference rankings ( (T)x)))((K) player-arm matched times (Ti.) ( comparison matrix (Better(i, j.)
1: Initialize: Vp; E .N, its available arm set A, = 0, temporarily matched arm m; = 11; Vaj E K. its current proposing ranking 8j = 1, temporarily matched player my -1
2: while Bay m = -1 and 8j S N do
3: Denote p; as the player who ranked at the position sj, i.e., pi = Tj.s;
4: Update the available arm set: A, = AA U {ay)
5: Compute the estimated sub-optimal arm set in A.:
D. = {az E A. : 3j' E A, s.t. Better(i, ji, 1
6: Update the temporarily matched arm of p; as m, E arg minzeAAD Tij
Suppose is the temporarily matched arm of ps, i.e., ag = m,, update m
7: for ay' E A, and a3 * m; do
8: 8y = sy + 1, my 5 =-1
9: end for
10: end while
Output: Matching outcome m = (m,))e(N)
The operation of players is summarized in Algorithm 3. Each player maintains f and Tig to record the estimated preference value and the matched time with arm a, (Line 1). In each time slot t, the player first computes the upper confidence bound UCB,,, and lower confidence bound LCB,,, as Line 3. can be shown in the analysis that the real preference value fi, can be upper bounded by UCBL, and lower bounded by I.CB,,, with high probability. So once an arm az's lower bound is better than the other arm a 's upper bound, Pt can regard it prefers aj over ay and update Better(i.j, = 1 (Line 4). Each player would then submit the information of matched times and comparison matrix to the central platform (Line 5) and receive the assigned target arm At( (Line 6). It then selects this arm and updates the estimated preference values and matched times based on the received rewards (Line 7-9).
4.1 THEORETICAL RESULTS
This section provides the theoretical results for the centralized AE-AGS algorithm. To characterize the hardness of the learning process, we first define the preference gap A as follows.
Definition 4.1. For any player and arm aj. ay', define AijJ' | Mi. as the preference gap of pa between aj and ag. Further, define A "iina,,'",AA,.. 7o0 Aigis as the minimum non- zero gap if min A A A.j. + O. Otherwise, define A = 0.

---

Published as a conference paper at ICLR 2025
Algorithm 3 AE-AGS (centralized version, from the view of player p.)
1: Initialize: Vj [K], P = 0, , = 0
Jj. E [K]. Better(i,,j)) j.J)" 0 Better(i,,..')) implies that p; considers that aj is better than ay', j') 0 otherwise
2: for time slot = 1.2.... do
3: Compute the upper and lower confidence bounds for each arm E K as
T/T LCB:,, = Pi.j VologT/2, // Vf = 0, then UCB,, oc, LCB,,
J R +
4:
Update Better for any j.J J E [K]] Better(i....") - 1 > gt) ( 6: Receive (t) from the central platform and select this arm, receive reward X;,4,
5: Submit (Ti,))5(K
to the central platform
7: if pj successfully accepted by (t) then
8: (s,A.(1) = (X),).()))) + Ai.Ad) TiA()) + +1 (LAT0 = TrA(0)) +
9: end if
10:
end for
The stable regret by following the centralized AE-AGS algorithm can be bounded as follows.
Theorem 4.1. Following Algorithu and 3, if A > O, the stable regret of each player ps satisfies
(T), & O log If A 0, the stable regret of each player p; is Reg; 0.
Due to the space limit, the detailed proof is deferred to Appendix B. The algorithm can also be extended the decentralized setting. We provide more discussions regarding its implementation, problem challenge, and the corresponding theoretical results in the next section.
The experiments are deferred Appendix E.
DECENTRALIZED SETTING
In real applications, the central platform may not be always available. For generality, we also extend the AE-AGS algorithm to the decentralized setting. this case, we follow existing decentralized works (Liu et al., 2021; Kong et al., 2022; Kong & Li, 2023) and assume that each player can observe the successfully matched pairs each time slot. This is also common real applications such as the workers usually updating their online profile in the market and the schools usually publishing the admission list. The decentralized version of the algorithm is presented in Algorithm Due to that the algorithm proceeds in several phases, we
the local time slot index during each phase.
To avoid conflicts among players when selecting arms, Algorithm 4 starts from an index estimation phase where each player learns unique index that guides the following selections. The players can simultaneously learn arms' preference rankings during this phase (Line 3-10). Specifically, the phase contains NK rounds and each arm corresponds to N-round block. At the first round in arm aj's N-round block, all players would first select arm aj. The successfully accepted player can be regarded as ranked in the first position in aj's ranking and receives an index of 1. In each of the following time т, the previously accepted players would not select arms and only the previously rejected players select arm aj- The accepted one regarded as ranked in the 7-th position and receives an index r. Then after NK rounds, each player knows all arms' preference rankings and gets a unique index.
The algorithm then enters the main exploration part. The total horizon can be further divided into several phases (Line 12) with the phase length growing exponentially no player breaks the process (Line 13). Within the phase, each player locally runs the Lubroutine-o--AE-ACA with its local knowledge of all arms' preferences, player-arm matched times, and the comparison matrix (Line 15). The player then selects the computed target arm (Line 16), receives the reward, and updates its estimated preference value (Line 17). The player also updates its local counter T for the observed matched player-arm pair (pa. (p).
(Algorithm 2)
When the phase ends, players will update their comparison information based on the previous reward observations (Line 20-24). Specifically, p; uses Update Flag, (s) indicate whether it has updated

---

Published as a conference paper at ICLR 2025
Algorithm 4 AE-AGS (decentralized version, from the view of player pt)
1: Initialize: Better(i..j.j") = 0, T. = 0, Vi E [N]. E [K]; fu, 0, vj E [K]
Update Flag(0) = False // Update_Fles
False means no player updates the Better matrix,
Update_ "lpgtt_Flag = True otherwise
2: Initialize: TT. -1, Index, -11 [K] [N]
3: for j E [K] do
4: Arm 0j
5: for round 7 1,2, ........ do
6: (x( Arm
7: Set Arm = -1 and Index; = if accepted by (T(
8: Update π ",,A, ((r) =7
9: end for
10: end for
11: to = 2/ The length of the phase
12: for phase s 1, 2, do
13:
=2,26,11 if Sodate.FFaagl 1) False and la otherwise 14: for round т = 2, ... -l, do
Subroutine-of-AE-AGSS
16: Select arm (T) m,
17:
Update the empirical mean (fs.)) as Line 7-9 in Algorithm
18:
For each arm 0j. observe its matched player (r) and update (T))
19:
end for
20:
Update_Flay (6) False, Update_Pairs, (8) = 0
21:
for j. E [K] and (itter(i,...'') = and UCB,,' LCB,,, do
22:
Update Flag, (s) True
23:
Update (sdd((())))))
24:
end for
25:
Fllgge_)lag(s)) Better Communications Utdateeallaaeeeeeeeeeeeeeelaaaee Update_Pairs, Better)
end for
the comparison information in the phase and uses (oddate_Parrs($} to restore the updated pairs, where pair (j-j") included in Update (sirs,)) if p; identifies that LCB,, > UCB,,, at the end of phase Then players communicate the updated information with each other through the Communi cation procedure (Line 25). After communicating with others, players get the Upddtt_Flag( that represents whether a player has updated his comparison information and the updated Better matrix. Update Flag(s) (s) is true, the players may need to explore some new arms, so the phase length must be restarted to avoid additional exploration cost (Line 13).
The detailed Communi cation description is presented in Algorithm 5. Generally speaking, players by based their unique index. In the first round, each
would transmit their information player would select the arm with its own index if its Update Spdate_Flagg is true and select nothing oth- erwise (Line 2-4). So for other players, they observe that arm aj matched in this round, they can infer that the player with index has updated its comparison information in this phase and would transmit the updated pairs in the following. The following rounds can then be divided into N blocks where the p-th block is used for player with index to transmit information and others to receive the information from this player (Line 6). the player has no information to update, then the block can be regarded as having 0 round (Line 7-8). Otherwise, the player would select the arm its Update_Pais Pairs, one by one (Line 9-15) with a round selecting nothing indicating the end of the transmission (Line 16). And other players would receive the updated pairs by observing the successfully matched arms in the corresponding block (Line 19-26). After the communication, the player gets Flag that represents whether player updates its comparison information in this phase as well as the updated Better matrix. The communication procedure ensures that all players locally maintain the up-to-date comparison information of all players.
8

---

Published as a conference paper at ICLR 2025
Algorithm 5 Communication
Input: Update_Fiie Flag,, Sipdte_Pairs, Better
I: Initialize: Flag False, 7
2: if Upddac__Flae
True then
3: Select arm (;(T) Oindex
4: end if
5: p p=1 // the player index who transmit information currently
6: while p do
7:
if' ap is not matched at time slot then
8:
p -=p+1
9:
else if ap is matched time slot and p Index; then
10:
Flag True
for (j.j') E Update Pairs; do
12:
T T 1, (T Oj.
- A, 0g
14:
Update Better(i.j.." end for
16:
T= + A.(T) =-1
p p=p+1
18:
else
19:
Flag = True
20:
Denote py as the player with index p
21:
T = T +1
22:
while (x # do
23:
j: = A AT)
24:
;':= (r)
25:
Update Better(i'.j.j))) =1
end while
27:
p=p+1
end if
29:
end while
Output: Flag, Belter
5.1 THEORETICAL RESULTS AND DISCUSSIONS
Algorithm 4 is decentralized version of Algorithm 1. Compared with that in the centralized version, the algorithm only pays additional regret for index estimation and communication, which only costs a constant number of time slots and does not influence the regret order.
Theorem 5.1. Following Algoirthu 4, if A > O, the stable regret of each player satisfies Reg. (T) S O(N log T2)
A 0, the stable regret of each player pı satisfies Reg, (T) Ologg T).
Due to the space limit, the proof of Theorem 5.1 is deferred to Appendix C. How to balance ex- ploration and exploitation is important to achieving lower stable regret. The state-of-the-ar works (Zhang et al., 2022; Kong & Li, 2023; Kong et al., 2024) in matching markets distinctly separate exploration from exploitation, where players only shift exploitation once the preferences for arms have been clearly differentiated. Assuming all preference values are distinct, players can keep ex- ploring until all gaps are identified. However, under indifference, when a player cannot differentiate between two arms, it becomes challenging to discern whether further exploration is necessary. Con- tinuous exploration may bring higher regret when preferences are the same; while discontinuing exploration may result in insufficient observations to identify preference differences and further ex- ploiting a non-stable matching. The key to learning under indifference, therefore, is to allow players to explore without the burden of suffering additional regret. Though Liu et al. (2020) and Basu et al. (2021) can be extended to handle indifference, they either use the value of to control the exploration budget (Liu et al., 2020), or adopt exponential time the trial-and --------rrro cost to avoid prematurely exploiting a non-stable matching (Basu et al., 2021). This results their algorithms requiring strong assumptions and suffering from exponential regret.

---

Published as a conference paper at ICLR 2025
Our approach provides more adaptive perspective to balance exploration and exploitation under indifference. Players only need to explore arms that propose to them. If these arms share the same preferences, all become potential partners in stable matching, making exploration cost-free and preserving the opportunity to exploit the stable outcome. If the arms have different preferences, the player will eventually eliminate suboptimal options after collecting sufficient observations. Such design prevents players from deciding when to stop exploring and naturally addresses the learning challenge under indifference.
Although the ODA algorithm in Kong & Li (2024) and AE arm-DA algorithm in Hosseini et al. (2024) are also inspired by the arm-guided GS, they differ fundamentally from our approach in
design principles. These two algorithms still adopt an "explore-thers exploit" strategy, explicitly dividing each step of the GS process. Only when the player completes an exploration step and identifies the optimal arm does the process move to the next step. Such an approach is still unable handle indifferent preferences, which could lead to the algorithm getting stuck in one of the steps. Our key idea to address indifferences is to prevent players from facing the dilemma of determining when to stop exploration. In our approach, the available arms for players in each round are determined dynamically as the outcome of a multi-step GS process, allowing players to freely explore. Our convergence results also differ from Kong & Li (2024); Hosseini et al. (2024). These two algorithms converge to fixed stable matching when players have strict preferences but may fail to converge under indifference. In contrast, our algorithm can guarantee stability under indifferences, with outcomes potentially switching between different stable matchings.
CONCLUSION
In this work, we study the bandit learning problem in more general matching markets with indif- ference. Under this setting, the xxploration-exploiaatiio strategies employed by existing algorithms become ineffective. To enable players to explore unknown arms without incurring significant costs, propose a novel adaptive exploration strategy based on the arm-guided GS algorithm. This ap- proach allows players to freely explore arms with indistinguishable preferences while ensuring ef- ficient exploitation of stable matchings. We prove that the algorithm achieves a stable regret bound of O(N K log T)) We also analyze existing algorithms and demonstrate their limitations when extended to handle indifference. Compared with the two existing algorithms that can be extended to indifference, our method shows significant improvement with respect to not only the assumptions but also the regret order. The convergence and effectiveness of our algorithm are further validated through a series of experiments.
by
One future direction to explore stronger objectives. There are various levels of stability under in- difference, including stronger stability, super stability, and weak stability (Irving, 1994). This work focuses on weak stability, which aligns with existing research on strict preference settings. Inves- tigating stronger objectives is interesting avenue for further study. Under weak stability, while a player-optimal stable matching may not always exist, it may be possible to establish guarantees for Pareto-efficient stable parison to another stable matching while all other players are matched with an arm that is no worse (Erdil & Ergin, 2008).
that player is matched with better arm in com-
ACKNOWLEDGEMENTS
Fang Kong is supported by Guangdong Basic and Applied Basic Research Foundation. The cor- responding author Shuai Li is supported by National Key Research and Development Program of China (2022ZD01 14804) and National Natural Science Foundation of China (62376154). The work of John C.S. Lui is supported in part by the RGC GRF- 1420292.. Pinyan Lu is supported by Na- tional Key R&D Program of China (2023 YFA09550),))0))..
REFERENCES
Atila Abdulkadiroğlu, Parag A Pathak, and Alvin E Roth. in matching with indifferences: Redesigning the nyc high school match. American Economic Review, 9955 1978, 2009.
versus efficiency
10

---

Published as a conference paper at ICLR 2025
Peter Auer, Nicolo Cesa-Bianchi. and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235 256, 2002.
Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pp. 705-715, 2021.
Ning Chen. On computing pareto stable assignments. In International Symposium on Theoretical Aspects of Computer Science, 2012.
Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In International Joint Conference on Artificial Intelligence, pp. 947-952, 2005.
Aytek Erdil and Haluk Ergin. What's the matter with tiebrrakigg? improving efficiency in school choice. American Economic Review, 98(3):669-66 6889, 2008.
Aytek Erdil and Haluk Ergin. Two-sided matching with indifferences. Journal of Economic Theory, 171:268-22 2017.
Aytek Erdil and Taro Kumano. Efficiency and stability under substitutable priorities with ties. Jour- nal of Economic Theory, 184:104950, 2019.
Tamás Fleiner. A fixed-point approach to stable matchings and some applications. Mathematics of Operations Research, 28(1):103-126 2003.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69119-11,, 1962.
Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-commii strategies. In Advances in Neural Information Processing Systems, volume 29, pp. 784-792, 2016.
Avishek Ghosh, Abishek Sankararaman, Kannan Ramchandran, Tara Javidi, and Arya Mazum- dar. Decentralized competing bandits in non-stationary matching markets. arXiv preprint 1rXiv:2206.001220 2022.
Hadi Hosseini, Sanjukta Roy, and Duohan Zhang. Putting gale & shapley to work: Guaranteeing stability through learning. Advances in Neural Information Processing Systems, 37:69043-69068. 2024.
Robert W Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):611222,, 1994.
Alexander Kelso and Vincent Crawford. Job matching, coalition formation, and gross substi- tutes. Econometrica: Journal of the Econometric Society, pp. 1483-1504, 1982.
Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2023.
Fang Kong and Shuai Li. Improved bandits in many-to-one matching markets with incentive com- patibility. In AAAI Conference on Artificial Intelligence, pp. 13256-13264, 2024.
Fang Kong, Junming Yin, and Shuai Li. Thompson sampling for bandit learning in matching mar- kets. In International Joint Conference on Artificial Intelligence, 2022.
Fang Kong, Zilong Wang, and Shuai Li. Improved analysis for bandit learning in matching markets. In The Thihty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yuantong Li, Chi-hua Wang, Guang Cheng, and Will Wei Sun. Rate-optimal contextual online
matching bandit. arXiv preprint 22Xiv:2005.06690 2022.
Yuantong Li, Guang Cheng, and Xiaowu Dai. Two-sided competing matching recommendation markets with quota and complementary preferences constraints. In International Conference on Machine Learning, 2024.
11

---

Published as a conference paper at ICLR 2025
Shiyun Lin, Simon Mauras, Nadav Merlis, and Vianney Perchet. Stable matching with ties: Ap- proximation ratios and learning. arXiv preprint arXiv:2411.0327,, 2024.
Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In Inter-
national Conference on Artificial Intelligence and Statistics, pp. 1618-1628. PMLR, 2020.
Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan, Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1-33 2021.
Chinmay Maheshwari, Eric Mazumdar, and Shankar Sastry. Decentralized, communication-an coordination- free learning in structured matching markets. Advances in Neural Information Processing Systems, 2022.
Deepan Muthirayan, Chinmay Maheshwari, Pramod Khargonekar, and Shankar Sastry. Competing bandits in time varying matching markets. In Learning for Dynamics and Control Conference, pp. 1020-1031. PMLR, 2023.
Tejas Pagare and Avishek Ghosh. Two-sided bandit learning in fully-decentralized matching mar- kets. In ICML 2023 Workshop The Many Facets of Preference-Based Learning, 2023.
Alvin E Roth. The evolution of the labor market for medical interns and residents: case study in game theory. Journal of political Economy, 92(6)991-10166, 1984.
Alvin E Roth. What have we learned from market design? The economic journal, 11 118(527):285- 310, 2008.
Alvin E Roth and Elliott Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American economic review, 89(4):748-780, 1999.
Alvin E Roth and Marilda Sotomayor. Two-sided matching, Handbook of game theory with nomic applications, 1:485-541, 1992.
Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference Artificial Intelligence and Statistics, pp. 1252-1260. PMLR, 2021.
Tayfun Sönmez and M Utku Ünver. Matching, allocation, and exchange of discrete resources. In Handbook of social Economics, volume 1, pp. 781-852. Elsevier, 2011.
William R Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285 294, 1933.
Zilong Wang and Shuai Li. Optimal analysis for bandit learning in matching markets with serial dictatorship. Theoretical Computer Science, pp. 114703, 2024.
Zilong Wang, Liya Guo, Junming Yin, and Shuai Li. Bandit learning in many-to-on matching markets. ACM International Conference on Information Knowledge Management, pp. 2088- 2022.
Yirui Zhang and Zhixuan Fang. Decentralized competing bandits in many-to-one matching mar- kets. In International Conference on Autonomous Agents and Multiagent Systems, pp. 2603-2605, 2024.
Yirui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. In Advances in Neural Information Processing Systems, 2022.
12

---

Published as a conference paper at ICLR 2025
A DISCUSSION ON THE SUCCESS OR FAILURE OF EXISTING ALGORITHMS WHEN DEALING WITH INDIFFERENCE
In this section, we try to extend existing algorithms for general one-to-one markets (Liu et al., 2020; 2021; Basu et al., 2021: Zhang et al., 2022; Kong & Li, 2023; Kong et al., 2024) to the indifference setting. We specify the failure parts of the original proof if it cannot work under indifference and sketched reason for Liu et al. (2020) and Basu et al. (2021) to deal with indifference.
For the centralized UCB algorithm in Liu et al. (2020), Corollary 9 does not hold as when players have indifferent preferences, Ljrpess S SE 1/((>²) does not hold.
For the CA-UCB algorithm Liu et al. (2021), Lemma does not hold. We can provide a coun- terexample that m, is stable and E holds, but m4+1 & M*. For example, there are 3 players and 3 arms with preference rankings list below:
P1 : 01 > 02 = 03
d1 : p2 > Pa > Pl: 02 : pı p2 P3
P2 02 01 03
ps 01 = 03 > 02
03 Pp:p1 > P2 > P3
At t, the matching m, = (pi. a2), (p2. 02), (ps. a1)} is stable. And at time t + 1, the matching can be {(11, 02), (p2, a1), (P3. 1)}, which is unstable. The same example can illustrate the failure of Lemma 1 in Kong et al. (2022).
For the ML-ETC algorithm in Zhang et al. (2022), the second paragraph in page 16 does not hold as when players have indifferent preferences, there always exists a pair of arms such that the stopping condition is never satisfied (the last paragraph in page 6). Similarly, for the ETGS algorithm in Kong & Li (2023), Lemma 4 does not hold as may never happen that pair of arms with the LCBB of one better than the UCB of the other when their preference values are the same. The same analysis applics to Lemma A.5 in Kong et al. (2024).
The proof the centralized ETC algorithm in Liu al. (2020) and Basu al. (2021) goes through under indifference with A defined as the minimum non-zero preference gap among all players. The reason is that when the matched time of players over arms is enough to identify the minimum non- zero gap A, the matching process in these two algorithms can be regarded as running the offline GS algorithm by randomly breaking the tie, resulting in the stable matching.
B PROOF OF THEOREM 4.1
For convenience, for any time slot t, define (t,, (t,, LCB,, (t), UCB,,, as the value of fs..j LCB,,, UCB1, in the AE-AGS algorithm at the start of Define the failure event
6 log Tt)
F= Ei E [N], e [K],4 E (7] (1)
(2)
to represent that some estimated preference value is far from the real preference value at some round When A 0. the stable regret of Algorithm I and Algorithm 3 can be decomposed as
Regi(T)
Σ (ps.ms - XLA(0(())
Σ (A(t)= & M)
$
E
Σ (A(L) & M)
(3)
Σ (A(1) & MM
E Σ 177
96NV log T
+ 2NK,
(4)
A
13

---

Published as a conference paper at ICLR 2025
where equation 3 holds since all players select different arms in the centralized setting and thus rejection happens, equation is because of Lemma B.1 and Lemma B.2.
When A 0, all players have the same preferences over all arms. So any matching that each player matched with an arm is stable matching since no blocking pair exists. Since Algorithm assigns different arms to different players, the matching Att) in each time slot is stable matching. So the stable regret of all players as equation 3 is 0.
Lemma B.I.
T Σ
1 1[F}
<
2NK.
(5)
Proof. Recall that FF is defined as equation 2. Then,
T
6 T Ti,
(
E
E
[M (K),
[T) ((s Miyl
V
1=1
Glog T (mes(1) m4,1 V (t, [
ST.
Σ
E
[[N]JE[A
=T. Σ ΣEΣΣ
18
Tis(t) w. (Pi,((t) Menl
6 logg T (1,(1)
V
[ (=w==l
=7. Σ ΣΣΣ
P
APS Masl >
Glog w
NE[N] JE[K]
ST. Σ ΣΣΣΣ
iE[N] JE[K] cexp(-3log
(6)
< 2NK.
Here equation is due Lemma D.I.
Lemma B.2. Following Algorithm I and Algorithm 3, when A > 0, it holds that
96N log T
E
Σ ((A(t) & M) 1 <
(7)
2
Proof. For convenience, denote (t) as the set available arms of player at the end of Algorithm 2 when running it at round f. According the definition of stable matching, can first decompose
14

---

Published as a conference paper at ICLR 2025
the above regret
((A(t) & M3 1F
T
SE
Σ
1 Ei [N].j E [K] Pa. > ML,A,(0) and JHS - T,,77000 17F
m=l
<B
E mLA()))) IT
(8)
t=1
<B
Σ 1Ej.h' A.))) :()):Ps) PLg > Pig. A,()) |F
[= (E[N]
Σ Σ Σ 1(A(()) = J' is not the best arm in A,(t)) |
<B
1=1 (E(N) ('EA(())
T <E ΣEΣ
113 3' is not the best arm in A.(t)), = a 1F
(9)
J'[K]]
96N log T
2
where equation holds since arm a, prefers a, to its matched arm (t) then a, must first propose ps in Algorithm 2 and thus aj A.(t). And equation 9 can be proved by contradiction. Suppose the matched time of p; and ay is larger than 96 log 22, i.e., (t) then p3 would not select ay to match at time This is because for other better arms aj E (t(t) with Ji,j > Hi,' if the matched time (t) smaller than log T/A², then pt would select those with fewer match times (Line 6 of Algorithm 2). And otherwise, due to Lemma B.3, pt would estimate ay as sub-optimal arms and does not select it (Line 5 of Algorithm 2).
96 To
Lemma B.3. As any time slot for any player Pe and arm az with Mi. Pajs, if min (t) 96 T/A?, then g LCB,,(t) conditional on "F
Proof. By contradiction, suppose UC) 2 (t.,, Based on the definition of "F (equa- tion and LCB, UCB (Line 3 of Algorithm 3), it holds that
6 loog T (1)
6log T
Pi.j - 2
< (CB,,()) < UCB,, S uir + +2
(10)
(1)
can conclude
6log T
Aij. == Pi.j Pig S VV min (T.,((),TT,(()))
This implies min (T,((), (.) 96 log T/A log < 96 log 7/42, which contradicts the fact that min (e) (f) > 96 log T/Ax A The lemma can thus proved.
C PROOF OF THEOREM 5.1
Denote Smax as the total number of phases of Algorithm 4 when the interaction ends. For each phase 8, denote l,, (Commmmicaation) as the number of time slots when running the Communication
15

---

Published as a conference paper at ICLR 2025
algorithm (Algorithm 5). Then when A O, the regret of Algorithm 4 can be decomposed
T
Reg. (T) = E
Σ (pim. - (e))
1 (A(t) & MB
< E
Smax
$ NK +
Σ (((TT) M) + t, (Coommunicationn)
Smax
Bmaa
T
S NK +
[[A(T) & &M1
E
1 (Communicationn
+ R.
Σ
T=1
NKK- 672NK I
+ NK log + 3NK? 2NK
A
where the second last inequality is due to Lemma C.I, the last inequality is due to Lemma C.2, Lemma C.3, and Lemma B.I.
= 0. recall that any matching without conflicts is a stable matching as no blocking pair exists. So Algorithm 4 would only suffer regret in the index estimation phase and the Communi cat cation ioon phase as running Subroutine-f-AE--GG does not suffer stable regret (Lemma C.1). The regret can thus be decomposed
Regi(T) = E
(ui... - (L))
Σ (A(t) & $
E
((((T) $ M) (CCommunicatiion ]
NK +
Sana
$ NK E
(Comunicction))
NK T,
where the last inequality is due Lemma C.2.
Lemma C.1. In Algorithm 4, no collision happens, ie., A.(t) = A,(t) when players select arms based on the AAS- (Line 15).
Proof. We first prove that all players maintain the values of Ty.i, Ti,j, and Better(i.j.'" for each j.j' E [K]. In Algorithm 4, ग == (TT))))((K) is determined based on which player is matched with observation, different players have the same knowledge over л. Similarly, all players have the since they update this knowledge only when they observe that aj is
ay in the corresponding time slot (Line 3-10). Since all players have the same
same value of (e matched with p; within the phase (Line 18). The comparison matrix Better is only updated during the Communi cation based on the selection of players in the corresponding slot (Line 14, 25 in Algorithm 5), so the value of Better among different players is also the same.
Above all, the computed matching m in each time slot (Line of Algorithm 15) is the same for all players. Further based on the procedure of Subroutine-of-AF-ACC (Algorithm 2), all players are assigned with different arms. So no collision happens, i.e., (,) A₁(t) for each player pi, when players select arms based Subroutine-o--AE-AGs in Algorithm 4 (Line 15).
Lemma C.2. When
0,
E
t. (communication)
< NK log T + 32
16

---

communication cation procedure Published as a conference paper at ICLR 2025
When A 0,
E
ta (communication)
S log T
Proof. We first prove the first inequality. Recall that the phase length grows exponentially until a player p; finds that an arm a; is better than aj' and updates its comparison flag Update_Flas as True. Based on Line 21 in Algorithm 4, the comparison information each arm pair can only be updated once. Above all, N players can update the comparison information in at most NK² phases. We can divide the total phases into several super phases where only the start phase of the super phase has length and the length of all of the following phases grows. Then each super phase contains at most log I' phases and there are at most N K super phases. So the Communi runs in at most 2 log T times.
When running Communicationn one time slot would be first used for all players to transmit the Update_Flag information (Line 2-4). So the total time complexity transmit the update flag is NK² log T' Then players would transmit their updated pairs, with each pair costing 2 time slots and an ending slot to select nothing. Since at most N 2 pairs are updated, the total time complexity to transmit the updated pairs is 3NK2 Thus the lemma can be proved.
When A 0, all players have the same preference values over all arms. Based on the definition of UCB and LCB in Line 3 of Algorithm 3, it would never happen that LCBk, < UCB for some player p3 and arms (j, ajr So the comparison information in all phases. The phase length would never restart and there is only super phase. So the total number of phases is log T. And during each Communication procedure, all players only spend time slot transmit the Update Flag and have update pair to transmit. Above all, the total communication time complexity is log T.
any player would not updated
Lemma C.3. In Algorithm 4,
Smax Σ
672N K log
E
H(A(T) M) 17 6=1 r=1
A
Proof. Recall that the phase length grows exponentially if Update Flag = False and restart Update Flag- = True at the last phase. Divide the total Smax phases into several super-phases based on whether Update Flag = True. And denote 8, as the number of phases contained in the super-phase Use Tmax to represent the number of super-phases. For convenience, denote (t) as the set of available arms of player i at the end of Algorithm 2 when running it at round t. The above regret can be decomposed as
E
((A(T) & M} IF
1=1
Tinax
<E
1(A(T) & M} IF
Tmax dy
1 1( [M], E [K] : PLj PL.A,(7) and JJ, ( 17F
<E
Tmax
<E
1 E E A((T): > (RAAG) 1
Fmxx
<B
(BIENN) E A.()) :AG) ='y.j' is not the best arm in A: 1
Fiax fr
ΣΣE
ΣΣΣ 1=1
1(A(T)) J' is not the best arm in A,(7)) 1
(E J'E[K]
17

---

Published as a conference paper at ICLR 2025
With little abuse of notation, denote s' the first phase the end of which Tiy > 96 log T/ Denote 1' as the first round in s' at the end of which Ti 96 log T/ Further, denote r' as the super-phase that contains phase s' and s(r') as the global phase index of the first phase in r'.
Then at any round 7 that after phase s', if exists better arm dj such that Ti, > 96 log T/A . ps would update Better
(Algorithm 2) would thus not assign ay to player p;. And if all of the other better arms a, have Ti, < 96 log TogT/ P; may still select arm ay' in the next phase. But recall that Lubroutine-of-AE--Me select the arm with the fewest selection times for p; (Line 6 of Algorithm 2), at time t', the difference between T and Ty should be no more than So pj would not select arm or after the phase s' + 1. Above all, the formula be bounded
= based on "F and Lemma B.3. Subroutine--f-AA--AGG
would always
Vinas Sy
E Σ
(A((T)) = =ay a of not the best arm in A.(T)) 1
iE[M] J'E[K]
E
96 log T
Σ
E
Σ
(AA(T) ay, j' is not the best arm in A,(r)) 1
2
ME(M) J'E(K]
E444
Σ 1(A(T)) ag' j' is not the best arm in A(T)) 17 1)
+B
ag', j' is not the best arm in Ar(7)) 17 )
96 log T
E
(2 + 4)
Σ Σ
I(A((T)
A
kE[M]
sma(n() rm
(11)
ΣΣ
log
96 log T
+6 6
A
2
NE[N] ['E[]] K log T
2
where equation 11 is due to the exponentially increasing phase length.
D TECHNICAL LEMMAS
Lemma D.1. (Corollary 5.5 in Lattimore & Szepesvári (2020)) Assume that X1, X2, ........, Xn independent, o-subgaussian random variables centered around p. Then for any > 0,
ne²
ng²
P
Σ X1 x2 1=1
S exp
P
X -
S cxxp
20
2
1=1
E EXPERIMENTS
In this section, we conduct series of experiments to validate the convergence of our AE-AGS in markets with indifference and compare its performance with that of centralized ETC (abbreviated as C-ETC) (Liu et al., 2020) and phased ETC (abbreviated P-ETC) (Basu et al., 2021), both of which can also extended to handle indifference. In each experiment, we run all algorithms for T 100k rounds and report the averaged results over 20 independent runs. The standard errors calculated the standard deviation divided by /20 are plotted.
To present the stable regret of each player, we first test the algorithms' performances small market with 5 players and 5 arms. The position of each arm in player's preference ranking is random number in 21,2,... K), similar to how the arms rank the players. Arms sharing the same position in ranking have the same preference values, and the preference gap between two arms ranked in adjacent positions is set to A 0.1. The feedback X, (t) for player p; on arm a, at time t is drawn independently from the Gaussian distribution with mean Pi.j and variance 1. We report
18

---

Published as a conference paper at ICLR 2025
[a] Player Pr
Player Po
(c) Player P::
Camulative Statle Regret
Camulattive Statle Regret
AEAGS,, Player
AE-ASS, Payer
AE AGS, Hayer Player
C-FTC, Mayer
Player P P-ETC. Hayerrs Py
Camulettee
IETC, Player Ps
Player Ra
10:60
(d) Player P4
Player Ps
Curuliative matket unstability
AE AGS
C-ETC
P-TT
AF-AG5, Player Playr P-ETC. Player
AF-AG5, Payer Plaer Ps p-rTC, Player Ps
cast
Cumuettree
300
1208
Round 2
Round
Round
Figure I: Experimental comparison of AE-AGS and baselines a market with 5 players and 5 arms.
the stable regret of each player in Figure I (d))) and the cumulative market unstability (the cumulative number of unstable matchings) Figure (f).
For generality, we also vary the value of A E {0.1, 0.15, 0.2, 0.25} and market size N = K e (3. 6, 9, 12} to show the performances of algorithms. We report both the market unstability and the maximum cumulative stable regret among all players in Figure 2 (a)(c) and (b)(d), respectively.
randor preforences, Ne5, Ked
random preferences No5, Ki5
canbom preferences, 6=0.
car domm preferences, 6w0.1
Nasmmn Siate
$27
1- (8x08
Gart 2.15
2.9
8377 kx3
830 52
MAG 2112
Figure 2: Experimental comparison of AE-AGS and baselines in markets with different preference gaps and market sizes.
In all tested markets, our AE-AGS consistently demonstrates good performances. This observation aligns with the theoretical results, where the performance of C-ETC is sensitive to the value of A, performing well in markets where A is appropriate but worse in others. The baseline P-ETC suf- fers from exponential regret and has not converged within the reported horizon. The dependency of the algorithm's 's performance on the parameters A and N, K is also consistent with the theoret- ical results. Specifically, as A decreases and N or K increases, the algorithm needs to pay more exploration costs, leading higher regret.
19


Reviews:
[{"review_id": "xCN3gGW6IJ", "reviewer": "Reviewer_SXo9", "summary": "The paper is a contribution that falls under the line of works where the goal is to match participants in a market when the preferences of these participants is not known apriori. While previous works, which the paper lists, have proposed algorithms to solve this problem for the setting where each participant in the market has a strict preference order, this work proposes an approach called AE-AGS that also accounts for the case of indifferent preferences. Indifferent preference is the case when a market participant (player or bandit arm) has an equal preference among one or more options from its complementing partner. \n\nThe indifferent preference scenario is critical for real-world applications since often it is not practical or even reasonable for a market player to create a strict preference ranking order over its complementary market participant. For example, a company might be indifferent towards hiring one among a collection of equally qualified employees. \n\nThe work proposes the AE-AGS algorithm for the centralized and de-centralized with communication settings. They analyze the algorithm and provide an upper bound on stable regret for both these settings. Finally experiments are conducted to compare the approach to baselines from the literature, and establish superior performance especially in the case of preference indifference.", "questions": "1. There appears to be some inconsistency between the message of Table 1 classifying prior work, and section 2 on related work. While the table suggests that there have been prior works (Liu et al. 2020 and Basu et al. 2021) that address the preference indifference setting however there is a line towards the end of para 2 in Section 2 that reads: \"In all the above works, both players and arms are assumed to have a strict preference ranking ... \".\n\nPlease clarify whether Liu et al. 2020 and Basu et al. 2021 can indeed handle preference indifference, and if so, how your approach differs from or improves upon these prior works. This would help resolve the apparent contradiction between Table 1 and the statement in Section 2.\n\n2. Seems to me that the definition of Stable Regret in Eqn 1 needs to be motivated better. In particular, why is stable regret bench marked against the least reward that could be obtained from a stable matching and not the maximum stable matching reward? Please provide a justification for why you chose the least reward from a stable matching as the benchmark, rather than the maximum. Additionally, please discuss the implications of this choice on your results and how the results would compare with those under alternative definitions of stable regret.\n\n3. Please increase the font size of the legend text in Figure 1 to improve readability for printed versions.\n\n4. Please provide a clear definition of \"Cumulative Market Instability\" and explain how it relates to stable regret.\n\n5. Please clarify why enumerating all stable matchings is problematic, even for small toy problems. Also consider including results using stable regret for these smaller examples if feasible.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The work addresses an important gap in the matching markets with unknown preferences literature where previously the approaches were not able to handle the preference indifference setting but this work can. The work proposes a UCB-style algorithm (AE-AGS) for both settings when centralized decision making is feasible and provides an separate algorithm and analysis for the decentralized setting as well.\n\nThe theoretical analysis of their algorithm backed by empirical validation of their approach makes for a strong contribution overall.", "weaknesses": "With my level of understanding of this area, I am unable to identify any big picture weaknesses. Instead, I have presented my concerns in the form of questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "fDnHTUOMNZ", "reviewer": "Reviewer_fp6v", "summary": "The authors study the problem of bandit learning in matching markets when there are ties in the users' preference over arms.  They study the stable regret, i.e. regret with respect to the least reward achieved in any stable matching. They adopt arm side proposal which leverages the fact that the arm side knows about their respective preferences. This way the user don't suffer from the dilemma of whether to declare two arms tied or continuing the exploration. Instead, the user requires only segregate non-tied arm through pairwise computations. This ensures even if ties are present a stable match is discovered with logarithmic regret.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The authors try to study the effect of ties in the well studied field of bandit learning in matching markets.  \n- They design algorithms in both centralized and decentralized setting that achieves logarithmic stable regret. \n- They identify that the existing algorithms with User side proposals cease to work when there is ties on the User side (the side where information is absent). The issue is identifying ties against lack of appropriate exploration.", "weaknesses": "- The paper lacks discussions on the user optimal regret. The arm side proposal makes it hard to obtain user optimal regret even if ties are not present. \n- The motivation to move to arm side (the side that knows the preference) proposal is not clear. Is it a fundamental shift necessary for handling ties while maintaining logarithmic regret?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "HKMAxxqZVl", "reviewer": "Reviewer_Ragn", "summary": "The authors study market stability in a two-sided market with agents whose preferences are unknown. This work allows for indifferent preferences, which have not been considered previously. They propose AE-AGS algorithm, which achieves $NK\\log(T)/\\Delta^2$ for each agent. Additionally, they provide numerical experiments to demonstrate their superiority over baseline methods", "questions": "1. Could you offer further justification for defining regret using the oracle's minimum value? Why minimum value is more proper than maximum reward?\n2. Could you explain the key idea in your algorithm that enables it to handle preference indifference?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Their algorithm can achieve tight regret bound under preference indifference. \n2. They also provide decentralized algorithm maintaining the tight regret bounds.", "weaknesses": "1. For the regret definition, they use the minimum reward value for the oracle, which may lack sufficient justification, under the absence of an optimal or pessimal stable matching.\n\n2. In the experiments, another benchmark (C-ETC), which is much simpler, also appears to perform well in this setting.\n\n3. The algorithm's presentation is difficult to follow. Especially, the main idea of dealing with preference indifference does not seem to be well described.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "zH5T0UecHZ", "reviewer": "Reviewer_2KcX", "summary": "The paper studies the problem of bandit learning in matching markets with ties, while previous literature usually assumed that preferences were strict. The authors propose an Adaptive Exploration Arm-guided Gale-Shapley algorithm, both in a centralized setting and a decentralized setting. The authors provide the corresponding stable regrets and conduct simulated experiments to validate the results.", "questions": "I suggest the authors to formalize the problem in a more convincing way, e.g. the notion of stability, player-optimal stable matching, stable regrets (see the last part). \n\nQuestions:\n(1) Can the AE-AGS algorithm be generalized to many-to-one matching markets? I'm asking this question since the ODA algorithm is designed for many-to-one matching markets.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper studies an important unexplored question of learning matching markets with indifference and indifference is common in real life applications. The authors provided both a centralized and decentralized variant of the AE-AGS algorithm, and showed the stable regrets. The authors also provide a discussion on whether other algorithms can deal with ties (Appendix A).", "weaknesses": "The formulation of the problem setting is not convincing enough. For matching markets with ties, there are notions of weak stability, strong stability, and super stability [1], while the authors focus on weak stability without sufficient discussions. In the example 3.1, both (weakly) stable matchings (line 221, 222) are pareto efficient matchings in the sense that no other (weakly) stable matching can pareto dominate the matching for players. Therefore, it is not accurate to state that no player-optimal stable matching exists in this sense. Finally, the definition of regret compares the difference with $m_i$, which is defined as the worst partner among all weakly stable matchings. By the definition,  {i, m_i} is not a stable matching since the worst partner might be in different matchings. I feel it might be better to define the collective stable regrets instead of individual stable regrets.\n\nI am also concerned with the algorithmic novelty in the paper. The AE-AGS algorithm looks like a simple (not necessarily trivial) generalization of ODA algorithm [2] and the AE arm-DA algorithm [3]. These algorithms utilize arm-guided Gale-Shapley to find stable matchings and utilize UCB structure to eliminate sub-optimal arms. From my understanding, the algorithmic difference in AE-AGS is that players do not need to eliminate an arm if there are ties while still proceeding with the arm-guided Gale-Shapley. Also, the analysis and proof also look similar to [2].\n\n[1] Robert W Irving. Stable marriage and indifference. Discrete Applied Mathematics.\n[2] Fang Kong and Shuai Li. Improved bandits in many-to-one matching markets with incentive compatibility. AAAI \n[3] Hadi Hosseini et. al. Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning. arXiv:2410.04376", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)