Improved Analysis for Bandit Learning in Matching Markets
Authors: Fang Kong
Zilong Wang
Shuai Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandits
Matching markets
Stable matching
Stable regret
Exploration and exploitation
$\alpha$-condition
Primary area: bandits

Abstract: A rich line of works study the bandit learning problem in two-sided matching markets, where one side of market participants (players) are uncertain about their preferences and hope to find a stable matching during iterative matchings with the other side (arms). The state-of-the-art analysis shows that the player-optimal stable regret is of order $O(K\log T/\Delta^2)$ where $K$ is the number of arms, $T$ is the horizon and $\Delta$ is the players' minimum preference gap. However, this result may be far from the lower bound $\Omega(\max\{N\log T/\Delta^2, K\log T/\Delta\})$ since the number $K$ of arms (workers, publisher slots) may be much larger than that $N$ of players (employers in labor markets, advertisers in online advertising, respectively). In this paper, we propose a new algorithm and show that the regret can be upper bounded by $O(N^2\log T/\Delta^2 + K \log T/\Delta)$. This result removes the dependence on $K$ in the main order term and improves the state-of-the-art guarantee in common cases where $N$ is much smaller than $K$. Such an advantage is also verified in experiments. In addition, we provide a refined analysis for the existing centralized UCB algorithm and show that, under $\alpha$-condition, it achieves an improved $O(N \log T/\Delta^2 + K \log T / \Delta)$ regret.

Improved Analysis for Bandit Learning in Matching Markets
Fang Kong Southern University of Science and Technology congf@sustech edu. en
Zilong Wang
Shanghai Jiao Tong University wangzilongos juu. edu. cn
Shuai Li"
Shanghai Jiao Tong University shuaili8@sj tu. edu. cn
Abstract
A rich line of works study the bandit learning problem two-sided matching markets, where side of market participants (players) uncertain about their preferences and hope to find a stable matching during iterative matchings with the other side (arms). The sate-of-theean analysis shows that the player-optimal stable regret is of order O(K log T/ where K is the number of arms, T is the horizon and A is the players' minimum preference gap. However, this result may be far from the lower bound (2(max N log T A2 K log T/A) since the number K of arms (workers, publisher slots) may be much larger than that N of players (employers in labor markets, advertisers in online advertising, respectively), In this paper, we propose a new algorithm and show that the regret can be upper bounded by O(N log 22 + K log A)) This result removes the dependence on K in the main order term and improves the state-of-the-an art guarantee in com- mon cases where N is much smaller than K. Such an advantage is also verified in experiments. In addition, we provide refined analysis for the existing central- ized UCB algorithm and show that, under a-condition, it achieves an improved ONN log A/ 2 + log T/A) regret.
Introduction
The two-sided matching market problem has been extensively studied in the literature due its wide range of applications like labor market, school admission, house allocation, and online advertising [26, 9, 1]. There are two sides of participants in the market, such the employers and workers in the labor market, advertisers and publishers in online advertising. Each participant on the one side has preference ranking over the other side. The concept of stability, which characterizes the equilibrium state of the market where no participant wants to break up the current matching relationship and find another partner, has attracted great interest from researchers [26]. Achieving stability is critical for ensuring the long-term viability of the market.
A rich line of works [9, 15, 25) study how find stable matching in the market. Most of them assume the preference ranking each market participant known beforehand, which we refer the offline setting. However, in real applications, the knowledge of the preferences may be uncertain. For example, in the labor market, employers usually do not know the working abilities of workers before being matched, and advertisers also do not know the exact conversion rate of placing the advertisement in a publisher slot. This makes the traditional algorithms unavailable to
"Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

find an exact stable matching. With the emergence of online market platforms such as the online labor market Up and TaskRabbit as well as online advertising platforms where employers or advertisers have many similar tasks, market participants are able to learn their unknown preferences during iterative matchings with the other side of agents.
Multi-armed bandit (MAB) is classic framework that characterizes the learning process during it- erative interactions [3, 19J. It considers the setting with single player on one side and multiple arms on the other side. At each round, the player selects an arm and receives a reward. The player has unknown preferences over arms and would learn this knowledge based on the collected rewards. To accumulate as many rewards as possible, the player faces the dilemma of exploration and exploita- tion. The former selects arms with less observations while the latter focuses on arms with better historical performances. How to balance the exploration and exploitation trade-off is the key of bandit algorithm design. The upper confidence bound (UCB) [3], Thompson sampling (TS) [14, 2], and explore- then--mmmee---omi (ETC) [10] are common strategies in MAB to achieve this objective.
Liu et al. [20] introduce the bandit learning problem in matching markets and try to provide theo- retical guarantees. Two sides of agents in the market can be modeled as players and arms. Without loss of generality, denote N and K as the number of players and arms, respectively. It is worth noting that this work and all of the following works assume N S K to ensure each player has a chance be matched. In this problem, the objective is to find a stable matching and minimize the stable regret for each player, which is defined as the difference between the reward of the stable arm and that the player receives during the horizon. Since there may be more than one stable matching, they mainly focus on the players' most preferred one corresponding to the player-optimal stable matching and the least preferred one corresponding to the player-pessimal stable matching. Note that players receive more rewards in the player-optimal stable matching and thus the former objec- tive is the most desirable. Liu et al. [20] first study a centralized setting where a central platform would compute allocations for players to avoid conflicts. Both ETC and UCB-type algorithms are proposed for this setting. The former achieves a player-optimal stable regret guarantee with prior knowledge of players' minimum preference gap A and the latter can only ensure to reach the player- pessimal stable matching. Motivated by real applications where the central platform may not always exist, rich line of works then study the decentralized case where no platform coordinates players' behavior [21, 28, 4, 18, 22]. This line of works again only achieve guarantees for player player-pessimal stable regret [21, 18, 28, 4, 22]. Table compares settings and regrets among these works. Until recently, Zhang et al. [31] and Kong and Li [16] independently derive algorithms that have polyno- mial player-optimal stable regret and show the upper bound is O(K log T/ ).). However, this result may be still far from the lower bound Mmmxx[ (N log T/ 22, K log T/A}) [28] since K is usually much larger than N such that the number of workers (publisher slots) is usually much larger than that of employers in labor markets (advertisers in online advertising, respectively).
In this paper, try provide more efficient algorithms and improve the results over existing works. The detailed contribution can be summarized as follows: (1) We propose an algorithm named adap- tively explore- sxplore-then-eee Chenn-GlleSSii ShaelSS (AETGS) with elimination. State-of-the-an works [31, 16] ex- plicitly separate the exploration and exploitation processes, which can lead to unnecessary regret, as exploring certain preference rankings may not contribute to the exploitation process. To avoid excessive exploration, our AETGS with elimination algorithm integrates the players' learning pro- cess into the GS steps. Players adaptively switch between exploration and exploitation and promptly eliminate sub-optimal arms. (2) We prove that the player-optimal stable regret of AETGS with elim- ination can be upper bounded by O log T/A² K log T/A). This is the first result that removes the dependence on K in the main regret order term and improves existing works in common cases where N is much smaller than K. We also conduct experiments to show the advantages of the al- gorithm. (3) We refine the analysis of the centralized UCB algorithm in Liu et al. [20] for markets satisfying the a-condition. By investigating the preference hierarchy structure of the a-condition, we demonstrate that the stable matching converges sequentially from player 1 to player N. Through inductive analysis over players, we establish an O(N log T/ 2 K log T/ regret upper bound, which improves the original result for this algorithm in this specific market.
2
Related Work
The problem of bandit learning in matching markets is first introduced by Das and Kamenica [8]. They study the special case where both sides of agents have the same preferences and propose
2

---

Regret bound
Setting
0 K lo T/2
#
known A, gap1
Liu et al. [20]
(NK log T/ A?) 0
#
gap2
N K2 log" T
Liu et al. [21]
o
e A
gap2
0
((NK log T/ T
Sankararaman et al. [28]
serial dictatorship, gap1
Ω
max log T/ A², K log T/A))
Klog -= T 20
Basu et al. [4]
0
gap2
0
INKlog log T/
a-condition, gap1
Maheshwari et al. [22]
0
(CNK log T/
a-reducible condition, gap1
No K2 log" T
Kong et al. [18]
0
g A
gap₂
Zhang et al. [31]
0 (K (/2))
gap2
Kong and Li [16]
0 (K (Klog log T/
gap3
0 N log T/ + K log T/A)
Ours
gap4
0 N log T/A² Klog T/A)
a-condition, gap3
Table I: Comparisons of settings and regret bounds with most related works, represents the player- optimal stable regret and bounds without labeling sents the centralized setting. N and K are the number of players and arms with N S. K, T is the total horizon, A corresponds rithms, and C' is related to the unique stable matching condition which can grow exponentially in N. The definition of in different works requires particular care. We use gap1 gap2; gapy, gap, represent the minimum preference gap between the (player-optimal) stable arm and the next arm af- ter the stable arm in the preference ranking among all players, the minimum preference gap between any different arms among all players, the minimum preference gap between the first N + 1 ranked arms among players, and the minimum preference gap between arms that are more preferred than the next of the player-optimal stable arm among all players, respectively. Based on the property that the player-optimal stable arm of each player must be its first N-ranked (shown in Appendix), there would be gap, > gap4 gap; gapz. So our dependence on A is better than the state-of-the-ar works [31, 16] for general markets.
for player-pessimal stable regret, repre-
some preference gap. ε depends on the hyper-parameter of algo-
some empirical methods solve the problem. Liu al. [20] first theoretically formulate this problem and provide an upper bound for the stable regret of players. They propose centralized explore-then-comme (ETC) algorithm and upper confidence bound (UCB) algorithm, which obtain an O (K log T/)²) player-optimal stable regret and O (N K log T A/) player-pessimal stable gret, respectively. is worth noting that the former ETC algorithm requires knowledge about to ensure the algorithmic operation. Due the generality, the following works focus the decentral- ized setting. Liu et al. [21] and Kong et al. [18] propose the UCB and TS-type algorithm for general decentralized markets, respectively. Such setting is much more challenging and both of them only achieve O (exp(NV*) N K² log" log²((T)/ (T)/A?) upper bound for the player-pessimal pessimal stable regret.
To improve the stable regret guarantee, line of research studies some special markets with unique stable matching in which case the player-optimal stable matching is equivalent to the player- pessimal one. Sankararaman et al. [28] propose the UCB-D3 algorithm based on the assumption of serial dictatorship. i.e., all arms share the same preferences, and obtain an O (NK' log TogT/ 2)) regret upper bound. To investigate the problem hardness, they also derive a lower bound Ω [max NN log T/22, K log ) under this assumption. Basu et al. [4] consider more gen- eral a-condition setting for unique stable matching. They propose the UCB-D4 algorithm and also achieve the O (NK K log 22 regret bound. Later, Maheshwari et al. [22] study the marker satisfy-

---

ing a-reducible condition and proposes a communication-fres algorithm. Their regret bound has an exponential dependence on the number of market participants. Recently, researchers have developed algorithms that can achieve player-optimal stable regret guarantees without assuming unique stable matching. Both Zhang et al. [31] and Kong and Li [16] propose ETC-type algorithms that achieve O (K log T player-optimal stable regret. Wang and Li [29] studies the matching markets with serial dictatorship and obtains the O (N log 2 + K log T/A) regret. Table 1, compares
proposed algorithm with these related works in terms of their corresponding settings and theoretical guarantees.
There are also other works considering unknown preferences in matching markets. Wang et al. [30] study a many-to-on market where an arm accept multiple players. Jagadeesan et al. [12] con- sider online matching markets with monetary transfers. Min et al. [23] investigate Markov matching markets where state transitions occur during the matching process and players' rewards depend on the current state. Other studies have focused on non-stationary rewards, such as Muthirayan er al. [24], Ghosh al. [11], who propose robust algorithms to mitigate the impact of reward distur- bances. Additionally, several studies have explored the problem of offline matching market learning.
Dai and Jordan [6, 7] propose approaches that leverage historical data to design optimal matching or recommend participants on both sides.
3 Setting
This paper considers the problem of bandit learning in two-sided matching markets. Denote N axx } as the arm set. Let N and K be the
Pon.Pp.....PP. as the player set and K. = { 02,,..,, number of players and arms, respectively. To ensure that each player can be matched with an arm, we follow previous works and assume N < K [20, 21, 28, 4, 18, 31, 16].
For each player pa E N, its preference towards arm aj can be portrayed by an absolute utility Ha.j E (0, 1]. For any pair of arms aj and ay, P4.j > Pi.3' indicates that player ps prefers arm aj over ag. Following previous works for matching markets [9, 20, 21, 28, 4, 18, 31, 16), players are assumed to have distinct preferences over different arms, i.e., Hi.j * Pi.j'' for any Oj * ay. In practice, players' preferences which correspond to workers' abilities and the publisher's conversion rates are typically unknown and can be learned through the interactive matching process. On the other side, each arm aj also has fixed and distinet preference utility иJ.ı over each player pt M, and ,5,i > Tz means that arm 0j prefers player over pv. As in labor markets where workers usually know their preferences over employers based on the payments and task types, the preferences of arms are assumed to be known beforehand [20, 21, 18, 28, 4, 31, 16].
At each round t .... each player P: proposes to arm A:(t). For each arm aj, denote (t) {p: (,) a,} as the set of players who selects arm aj at round t. When more (t),
than one player selects aj. it accepts its most-preferred one in 't), i.e. aj will match with P: E arg max p.E, TJ.-- If a player pt is successfully matched with arm At()), it will receive a random reward (1) characterizing its matching experience, which we assume is I-subgaussian random variable with expectation (t)- Otherwise, pt is rejected by its proposed arm and only gets reward (t) = O. Denote (t) as the final matched arm of player P; round t. Then (, = (t) if p; is accepted by the arm (t) and we simply set (t) = 0 if p; is rejected.
Stability is key property of a matching in two-sided markets [9, 27, 25]. A matching A(t) {(i, (!) i E [N]} is stable if no market participant wants to break up its current matching relationship and find new partner. Formally speaking, there is no player-arm pair (p:, such that (c, > (t)AA(t)) and Tj.1 > 't)" is worth noting that there may be multiple stable matchings in the market. Denoted M = {m is stable) as the set of all stable matchings. It is shown that there exists a stable matching m² E M such that all players are matched with their most preferred stable arm [9]. i.e., Pi,m; 2 Hi,, for any m E M, [NV] Given specified horizon T. the learning objective is to minimize the player-optimal stable regret for each player p. which is
defined as the difference between the cumulative reward received by being matched with m and the cumulative reward received by P: over T rounds:
Σ (Mimg - xx(1))
Reg (T) = E
4

---

Here, the expectation is taken over by the randommess of the reward generation and the randomness inherent in the player's strategy.
For completeness, we introduce the procedure of the offline Gale-Shapley (GS) algorithm, which would be useful when describing the algorithmic details. The offline GS algorithm is a classic algorithm to find the player-optimal stable matching when both sides of the market participants know their exact preference rankings. Following offline GS, each player proposes the arm one by one based on its preference ranking, Until no rejection happens, the final matching is exactly the player-optimal stable matching [9]. Specifically, at the first step, all players propose to their most preferred arm. Arms would accept their most preferred player among those who propose to it and reject others. Then players who are rejected at previous steps would then propose to their next preferred arm. And arms still reject the players who propose to it except for their most preferred one. Such a process continues until no rejection happens.
For convenience, we also define some useful notations that quantify the hardness of the learning problem in matching markets and are used in the later analysis.
Definition 3.1.
For each player pi. denote d; as p preference ranking and let di, as pa's the k-th preferred arm in its ranking. With a little abuse of notation, let o; represent the rank of arm o, in p. 's preference. For each player p, and arm a + az', let Ai,js' = |P:. Mey'l be the preference gap of p. between a, and ag. Define A = (eer Ai,,,,.-.,,.1 as the minimum preference gap between the arm ranked the first (m,)m) + 1)-th among all players. Further, define AN = ke Ai,,,.00.44 as the minimum preference gap between the arm ranked the first (N + 1)-th among all players.
4 Algorithm for General Markets
In this section, we propose an algorithm called adaptively explore-then then-Gale-hhapley (AETGS) with climination. For simplicity, we present the centralized version of the algorithm in Algorithm from view of player p;. The discussion on how extend it to a decentralized version is deferred later subsections.
In general, AETGS with elimination is adaptive version of the GS algorithm. Since players do not know their preference rankings, they need to learn this knowledge by exploring arms (Line 4). To reduce the regret during exploration, players would adaptively eliminate sub-optimal arms (Line 6-8). Until they find their most preferred arm among available arms, they will stop exploration and focus on this arm (Line 9-1 And once the player finds this arm is occupied by more preferred player, it would re-start exploration to find the next preferred arm (Line 12-19).
Specifically, each player p; still maintains (f, and (t) to represent the empirical mean and the number of observations on each arm aj at the end of round t. To determine whether an arm is more preferred than another, it maintains a confidence interval for each arm aj with upper bound (C) == (t) + / 6 log (/T,, and lower bound LCB,,, := P..j - / 6 T T/T;, (t). When T. = O, they will be initialized as too and -o0, respectively. And once the confidence intervals of the two arms are disjoint, it can regard the arm with higher empirical mean to more preferred (Line 1). To be consistent with the offline GS, each player maintains DD to represent the set of arms that have rejected p. during previous steps. In the beginning, it initialized as an empty set. And we use A; to represent the available arms with the potential to be the stable arm of pi, which initialized as
D; For convenience, denote E, as the exploration status of player pi- E, = True means that p; still needs to explore arms in A; to determine its most preferred arm. And E, = False means that p. already finds its most preferred arm and now focuses on this arm (Line 2).
To reduce the regret suffered during exploration, players would update A, and climinate sub-optimal arms in real-time (Line 6-8). Here avoid collision during round-robin exploration, we would maintain A such that it contains no less than N arms if p; still has not determined its most preferred one. Thus the union of the available arm set over all players with E, True contains more than N arms and the round-robin exploration over A, for each such player Pt can be carried out without collisions. For completeness, we defer how to arrange players' explorations in later discussions. And once there exists an arm in A, that can be regarded to be optimal, pt will set the exploration status F. to be False and update the exploration arm set A, to only contain this optimal arm. For convenience, denote A, as this arm (Line 9-11).
5

---

Algorithm adaptively explore-then-CCal-Saappp with elimination (from the view of player p.)
Input: N, K.K.T.
1: Initialize: [i.y - 0, = 0, UCB = 00, LCB,, = 00, vjj E [K];
2: Initialize:
True;
3: for round f 1,,,,....
4: Select A.(!) E A. in round-robin manner;
5: Update (t) (1) as Algorithm 2; compute (C) (C,,,,,,)CCBB...lll...
( for any E [K];
6: if [r| N and Rj E A, s.t. (C) maxjee,, (I) then
7:
A, = A\fi);
8:
end if'
9:
ir Jj E A, s.t. (t) > UCB (t) for any j' E A, and j' + then False, A, = j:
A 4--Uh A-U,E
11:
end if
for other player Py with E, False, Ap As do
13:
if . TAy. then
14:
D; D (Av) A; K,,D;;
15:
if F False and A; E D; then
F. True;
17:
end if
18:
end if
19:
end for
20:
end for
The update of the available arm set should not only depend on p.'s own observations but also on the other market participants. Specifically, if a player py determines Ay its most preferred arm, then the final stable player of Ar would be the same as more preferred than pr. So if A₂ prefers Pr than Pt. then Aş would not be the stable arm of p; and there is no need for p. to explore Ay anymore. In this case, P: deletes arm Ag from its available set and update A, (Line 12-19). It is worth noting that this operation may incorporate the eliminated arms again in AA. This is reasonable as the previously eliminated arm may be more preferred than the current arms in A, after the deletion operation. And if the deleted arm is p 's current most preferred arm, it will mark E, as True and restart exploration to find the next most preferred one (Line 15-17).
4.1 Theoretical Results.
Theorem 4.1. Following Algorithm 1, the player-optimal stable regret for each player ps satisfies
Reg. (T) S (N2 log T/A² Klog A/A)
Due to the space limit, the proof of Theorem 4.1 is deferred to Appendix A. The following are discussions on the detailed implementation as well as the novelty the result.
Arrangement of the round-robin exploration process. Recall that the number of available arms of each player is always larger than N based on Line 6 and we assume players can explore their available arms in a round-robin manner without conflict. We now propose an arrangement by letting players explore the available arms in units of N to guarantee this property. Specifically, in every 2N rounds, each player selects the N available arms with the fewest observations (randomly breaks ties) and explores them in a round-robin way. It can be shown by contradiction that there exists an assignment such that each player can successfully match with their respective N arms once during these 2N rounds (Lemma B.2 in Appendix), which only doubles the original regret without influencing the regret order. This guarantees that after every 2.V rounds, the observation count difference among all available arms is at most 1. Players would perform arm elimination and optimal arm identification (Line and 9) in the end of each 2N rounds. Therefore, compared to the timely eliminating/deletin of arms, this approach ensures that each player will select each arm at most one additional time during each exploration cycle before the player finds the optimal one. Since each player may restart exploration (Line 12-13) up to N2 times (each of N players can focus constant regret and does not influence the
on N arms), this scenario leads to an additional final regret order.

---

Extension to the decentralized setting, For simplicity, we present the algorithm in a centralized manner. It can also be extended to the decentralized version where no central platform coordinates players' selections. Specifically, we divide the total horizon into several phases and the length of each grows exponentially; i.e., the lengths of phases are 2, 2,4,8 8, ...... At the end round of each phase, players would decide whether to eliminate sub-optimal arms as Line 6-8, whether to determine one arm as the most preferred one and update the exploration status as Line 9-11. After the end of each phase, players would communicate their current exploration status, update their deletion set and available arm set, re-update the exploration status as Line 12-19, and then communicate their updated available arm set to determine the round-robin exploration process in the next phase. If there exists player whose exploration status becomes True from False during communication, the phase length would re-start from 2 and grows exponentially since new arms may be required for exploration. If the final exploration status of all players is False and their optimal arms are different, the next phase would continues until the end of the interaction. The detailed implementation of communication is deferred to the next paragraph. Based on the communication, players with F; = True can have pre-agreed protocol to explore arms in their available arm set in round-robin manner without collision as discussed in the last paragraph. Within each phase, they just round- robin explore arms and collect observations but do not make any decision on arms' optimality. If L observations on a sub-optimal arm are enough to decide its sub-optimality in the centralized version, then this arm would be eliminated at the end of the corresponding phase with the selected time to be at most 2L due to the exponentially increasing phase length. So the regret in this decentralized version is at most two times as that suffered in the centralized version.
This paragraph describes the implementation of the communication procedure. Recall that players need to communicate their exploration status and available arm set (calculated by subtracting the deletion and eliminating set from K.) at the end of each phase. For the phase length, recall that it grows exponentially until player's exploration status becomes True from False and player up- dates E, from False as True only when its most preferred arm is occupied by higher-priority player (Line 15). As shown by Lemma A.3, each player may occupy N arms, so such event happens at most N2 times. And when all players find their unique optimal arm which requires O(N log )) times, the phase would continue until the end of the interaction. Above all, the total number of phases is of order O (N² log (N² log T/ ))). For the detailed communication procedure, as phase in Kong and Li [16]. players can first estimate their unique indices and we assume the matching results are public as [16, 18, 21]. During the communication block of each phase, players sequen- tially transmit their data based on their indices, received by others through matching outcomes. Specifically, in the corresponding round, player p; selects the focused arm if E, = Falsc and noth- ing otherwise, incurring an O (N' log (N² log T )²) cost for status communication in all phases. For deletion (eliminating) sets, p; first selects the arm with index & to indicate it will transmit k arms and then sequentially selects these arms The communication cost on the arm set size is O (NV log (N2 log //))). Recall that players delete arms only when
cetbbrrrrrortty player fo- cuses on this arm, so N players focus on at most N arms before reaching stability and each player deletes up to N arms. Also, each player can climinate up to K - N arms during each exploration and would re-start exploration for at most N2 times. Thus the communication cost on the deletion (elim- inating) arms is O ((N3 K) and the total communication cost is O (N3 log log A/) + N3K), which is not the main order of the regret.
trade-off is the key to achieving low regret. Previous efforts were devoted to addressing pessimal stable regret [20, 21, 18] and uniqueness assumptions [28, 4] using classic UCB and TS strategies. Until recently, Zhang et al. [31] and Kong and Li [16] show that ETC-type strategies better fit this problem. Specifically, players first uniformly explore arms to learn the complete preference ranking of the top N arms, and then use the GS procedure for exploitation to find the player-opting stable matching. However, such a method may over-explore and cause unnecessary regret. The reason that to learn the first N-ranked arms, each sub-optimal arm aj must be selected Ollo T/A x.)) times to be distinguished from the N-ranked arm. And each time selecting this arm, the player pays Aim, regret. The mismatch between the paid regret and the difference to be figured out results in OKK log T ) regret.
Key idea of removing the dependence on K. Balancing the
In contrast to the existing approach, we present a more adaptive perspective that integrates the learn- ing process into each GS step. To avoid additional regret, players do not need to estimate their complete preference. Instead, they would start exploitation once the optimal available arm is identi-
7

---

fied. And if this arm is occupied by higher priority player, this player would restart exploration to find the next preferred one. To avoid the additional cost while exploring the optimal arm, we design more efficient way to let players promptly eliminate K - N sub-optimal arms and only maintain the remaining N arms to guarantee no collision. For the eliminated arm dj. the reward difference to be figured out is at least J. which matches the regret when selecting this arm. So the regret caused by these eliminated arms is O(K log T/ avoiding dependence on K in the main order.
(AETDA) algo- rithm for more general many-to-one markets with responsiveness. Compared with their realization in the one-to-one setting, our algorithm shares the same idea of balancing exploration and exploita- tion but further introduces the climination operation to avoid unnecessary selections. Compared with their O(N2 K log T/ A²) result in the reduced one-to-one setting, our Theorem 4.1 removes the dependence on K in the main order.
Recall Kong and Li [17] propose an
Discussion on the definition of gaps. Recall that our A is defined as the minimum preference difference among arms that ranked the first (m)( + 1)-th positions (gap4), while the lower bound in Sankararaman el al. [28] for markets with serial dictatorship depends on A that is defined as the minimum preference difference between the arm ranked o;(m;) and the arm ranked o, o,(m)) + (gap; in Table 1, respectively). It is an open problem whether the lower bound should depend on our gap, in general markets. Here we would like to discuss that the knowledge of gap, is important to learn the true stable matching. Consider market with 4 players and 5 arms. The preference rankings of players are P1 a1 > 02 > a3 d4 > asi P2 02 > ag > 01 > 04 > Os: Ps :
a3 > 01 > 02 04 > ag: P4 01 > 02 N 03 V 04 a5 and the preference rankings of arms
are 01 P2 > Ps > P4 > 01:02 : Ps > Pa > Pi > P2; ag Pa > P1 > P2 > P2; 04 P1 >
P2 Ps > Ps; P1 D2 > Ps > P1- In this market, the player-optimal stable matching is {(PI, a4), ()2,a)). (Ps, 02), da)). However, if player pi has collected enough observations to identify gap, but not collected enough observations identify gap, and wrongly estimate the first (.(m)) ranked arms, i.e., P1 wrongly estimate the preference ranking as pl a1 > 02 > a1 > 0g > 05. Then the computed player-optimal stable matching under this preference ranking is {PI, a4), (p2, 43), (P3, a1), (P4, }2)}. which is not stable in the original market as player p1 and arm a3 form blocking pair. This example shows that player pl must identify the gap among the first of (m²) ranked arms to find a stable matching in the market, which further illustrates the crucial role of gap4 in learning the true stable matching. We leave the lower bound in general markets as an important future direction.
5 Experiments
In this section, we compare our Algorithm 1 (abbreviated as AETGS-F) with baselines ETGS [16), MI-ETC [31] and Phased ETC [4] which also enjoy guarantees for player-optimal stable regret in general decentralized one-to-one markets. To better illustrate the advantages of our algorithm, es- pecially when N is much smaller than K, we set N = 3 and K 10. The preference rankings for both players and arms are generated as random permutations. The preference gap between any adjacent ranked arms is set as 0.1. The feedback (t) for player pæ on arm a, at time i is drawn independently from the Gaussian distribution with mean M4. and variance 1. We report the maxi- mum cumulative player-optimal stable regret among all players and the cumulative player-optimal instability in Figure 1 (a) and (b), respectively. Here the cumulative player-optimal unstability is defined as the number of matchings that are not the player-optimal stable one. All algorithms run for T 100k rounds and all results are averaged over 50 independent runs. The error bars represent standard errors, which are computed standard deviations divided by /50.
As shown in the figure, our AETGS-E algorithm, which only conducts necessary explorations over unknown preferences and promptly eliminates sub-optimal arms, achieves the least cumulative re- gret and cumulative player-optimal unstability among all baselines. The ML-ETC and ETGS algo- rithms need to sufficiently explore K arms to estimate the full preference ranking, requiring more exploration time to find the player-optimal stable matching. The PhasedETC algorithm has not yet converged within the displayed rounds due to the cold start problem.
8

---

Cumulative optimal stable regret
Cumulative player-optimal unstability
Maximum Cumulative Regret
23k
30k
AETOS-E
AETGS
FTiCs
Player-optimal Unstability
FTiC
PhasedFTC
PhasedtTE
NLETC
NLETC
19k
30k
5k-
10k
20k
100k
100k
Round
Round t
Figure 1: Experimental comparisons of our AETGS-E with ETGS, ML-ETC and Phased ETC in one-to-one decentralized markets with N players and K 10 arms.
Centralized UCB Algorithm for Markets with a-condition
In this section, we provide new analysis for the centralized UCB algorithm in markets satisfying a-condition. The algorithm is first introduced by Liu al. [20]. For completeness, we present the full algorithm in Algorithm 2. At each round, players submit their UCB rankings the centralized platform (Line 3). The platform runs the GS algorithm (based on players' submitted rankings) and returns the partner to each player (Line 4).
Algorithm 2 centralized UCB
Input: N, K.
1: Initialize: Pi. (0) = 0, (0) = 0, (1),, oo, Vi [N], E [K].
2: for round 1, 1,2 ...,..., do
3: Receive rankings ā =
fōilieNN
to the decreasing order of according
V [N];
4: (t) + Sale-Shapley (6, π) for each player p::
5: Observe (f),, and update (ig (t), (t 1) for each pi, Oy;
6:
end for
In the following, we introduce the a-condition. Conditions guaranteeing the unique stable matching have been widely studied in the offline setting [5, 13] and also the online setting to improve the learning efficiency [28, 4, 22]. Among these conditions, the a-condition is shown to be the weakest sufficient one [13] and incorporate the conditions studied in existing works [28, 4, 22).
Let 3 denote a pair of permutations of [N] and [K]. Then [N]s = (Q)
( and [K]s =
(1()), 4K ( denote permutations of the ordered sets [N] and [K]. respectively. The j-th player in [N] is the (f²))th player in [N], and the k-th arm in [K]s is the (9) -th arm in [K]. Then we can define the a-condition below.
Definition 6.1. The a-condition is satisfied if there is stable matching (i" i"), left-order of players and arms s.t. Vi E [N], Vj > i,j E [K] : μeož > fs, where jr is the partner of player ps in stable matching (i*,i"), and a (possibly different) right-order of players and arms s.t. Vj < i N.9, [K],, Qi [N], Tay Qiz, > Tg Here similarly, iy is the partner of arm Og,
in stable matching (²),
Without loss of generality, we consider the identity of players and arms is just the left order, i.e.. [N] = [N] and [K] [K]- Thus we only deal with player order ②,(²) = Q: and arm order 0 9n for E [N]. E [K] in the rest of the paper. Under a-condition, is easy to inductively verify that for any [N], the player pt matched with arm a, and the player po, is matched with the arm ag in the unique stable matching [4].

---

6.1 Theoretical Results
We analyze the regret for the centralized UCB algorithm under a-condition.
Theorem 6.2. When preferences of participants satisfy a-condition, following Algorithm 2, the stable regret for each player ps satisfies
(T) S SO (N log T/43 + log T/A)
The centralized UCB algorithm is proposed by Liu al. [20] and shown have O(N log T/A²) player-pessimal stable regret for general markets. We provide new analysis for markets satisfying a-condition which removes the dependence of K in the regret. Due to the space limit, we discuss the key idea of the proof below and defer the detailed proof to Appendix C.
We investigate the preference structure of a-condition to obtain the improved analysis. For player Ps. its regret is due to selecting sub-optimal arm dg with Pi,k < j4,s. Arm O will be selected by pr when its UCB value is higher than pt's stable matched arm a,, which time is bounded by Ollo / / ,.,,), and one Ai,i, on the denominator can be eliminated when multiplying A.,.. to compute regret. This contributes O (K log T/ regret since there are at most K 1 sub-optimal arms, worth noting that arm as will also be selected by p. if p: is rejected by a, in the GS algorithm. Recall that under a-condition, there is right order Q2 = E [N], for player pt. such that Vi" > >i' Qi" [N Tq, > Qu.. which means arm ag, = ag can only prefer players PQ,,PQ=. , -q than player PQ² Ps. Thus pi is rejected by a; only when these players select 0g and a, is sub-optimal for those players. To bound the regret of p; when being rejected, we just need to bound the exploration times of these players PQ2. :PQ,_ on arm ag However, the exploration time of single player PQ, with S l 1'
on a, can not be trivially bounded by Olog T/ T since PQ: may have to select arm a; after rejected by its stable arm age in offline GS, where age might be selected by PQ,," ... PQQ. 1. This leads to a recursion form. We control this term using the fact that when player rejected by its stable matched arm in the GS, it can date back to higher right-order player wrongly over- verresstmaate its preference for a sub-optimal arm. This key observation and the definition of A make it possible to derive the final O (N log T/ T bound.
7 Conclusion
In this paper, we investigate the problem of whether tighter bound can be derived for the bandit learning problem in two-sided matching markets. For the general one-to-one matching markets, we try to improve the learning efficiency of the existing algorithms. By integrating the offline GS procedure into the online learning process and carefully designing the elimination strategy, we show that the player-optimal stable regret can be upper bounded by O(N log T A² + K log T' A). This result removes the dependence on in the main order term of existing works and improves the state- of-the-art result [31, 16] in common cases where the number of players is much smaller than that of arms. An experiment is conducted to verify its advantage over other baselines in such markets. We also present novel analysis for the centralized UCB algorithm in markets satisfying a-condition and derive an improved O(N log A3 + K log T/A) regret upper bound.
One significant future direction is to investigate the optimality of algorithms. Although the depen- dence on N, K, in Theorem 6.2 matches the lower bound, the definition of A differs. remains unclear how the upper bound changes with the same A. Furthermore, since the lower bound pro- vided by [28] applies only to special markets, and the learning problem in general markets is more challenging due to the complex preference structure, determining whether algorithm can perform better in general markets is still an open problem.
Acknowledgments and Disclosure of Funding
The corresponding author Shuai Li is supported by National Key Research and Development Pro- gram of China (2022ZD01 14804) and National Natural Science Foundation of China (62376154). Fang Kong is supported by the Baidu Scholarship.
We thank Yuhao Zhang and Wenqian Wang for valuable discussions and suggestions on the proof of Lemma B.2.
10

---

References
[1] Atila Abdulkadiroğlu and Tayfun Sönmez. House allocation with existing tenants. Journal of Economic Theory, 88(2):233-26) 1999.
[2] Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pages 19-107,22 2013.
[3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2))235-255 2002.
[4] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log (1) regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pages 705-715, 2021.
[5] Simon Clark. The uniqueness of stable matchings. Contributions in Theoretical Economics, 6(1), 2006.
[6] Xiaowu Dai and Michael Jordan. Learning in multi-stage decentralized matching markets. In Advances in Neural Information Processing Systems, volume 34, pages 12798-12809, 2021.
[7] Xiaowu Dai and Michael Jordan. Learning strategies decentralized matching markets under uncertain preferences. Journal of Machine Leurning Reseurch, 22(1): 101111800611555 2021.
[8] Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In International Joint Conference on Artificial Intelligence, pages 947-952, 2005.
[9] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The Ameri- can Mathematical Monthly, 69.1),111,, 1962.
[10] Aurélien Garivier, Tor Lattimore, and Emilie Kaufmann. On explore-then-comii strategies. Advances in Neural Information Processing Systems, volume 29, pages 784-792, 2016.
[11] Avishek Ghosh, Abishek Sankararaman, Kannan Ramchandran, Tara Javidi, and Arya Mazum- dar. Decentralized competing bandits in non-stationary matching markets. arXiv preprint XXiv:2206.001200 2022.
[12] Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. Learn- ing equílibria in matching markets from bandit feedback. In Advances in Neural Information Processing Systems, volume 34, 2021.
[13] Alexander Karpov. A necessary and sufficient condition for uniqueness consistency in the stable marriage matching problem. Economics Letters, 178:63-65, 2019.
[14] Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptoti- cally optimal finite-time analysis. In International Conference on Algorithmic Learning Theory, pages 199-213. Springer, 2012.
[15] Alexander S Kelso Jr and Vincent P Crawford. Job matching, coalition formation, and gross substitutes. Econometrica: Journal of the Econometric Society, pages 1483-1504, 1982.
[16] Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching mar- kets. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA). SIAM, 2023.
[17] Fang Kong and Shuai Li. Improved bandits in many-to-one matching markets with incentive compatibility, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13256-13264, 2024.
[18] Fang Kong, Junming Yin, and Shuai Li. Thompson sampling for bandit learning in matching markets. In International Joint Conference on Artificial Intelligence, 2022.
[19] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

---

[20] Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. International Conference on Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[21] Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. Journal of Machine Learning Research, 22(211):1-34, 2021.
[22] Chinmay Maheshwari, Eric Mazumdar, and Shankar Sastry. Decentralized, communication- and coordination-ffee free learning in structured matching markets. In Advances in Neural Informa- tion Processing Systems, 2022.
[23] Yifei Min, Tianhao Wang. Ruitu Xu, Zhaoran Wang, Michael Jordan, and Zhuoran Yang. Learn match with no regret: Reinforcement learning in markov matching markets. In Advances in Neural Information Processing Systems, volume 35, pages 19956-1999999 2022.
[24] Deepan Muthirayan, Chinmay Maheshwari, Pramod Khargonekar, and Shankar Sastry. Com- peting bandits in time varying matching markets. Learning for Dynamics and Control Confer- ence, pages 1020-1031. PMLR, 2023.
[25] Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485-541, 1992.
[26] Alvin Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of political Economy, 92(6)991111016, 1984.
[27] Alvin Roth. Stability and polarization of interests in job matching. Econometrica: Journal of the Econometric Society, pages 47-57, 1984.
[28] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pages 1252-1260. PMLR, 2021.
[29] Zilong Wang and Shuai Li. Optimal analysis for bandit learning in matching markets with serial dictatorship. Theoretical Computer Science, 1010:1 14703, 2024.
[30] Zilong Wang, Liya Guo, Junming Yin, and Shuai Li. Bandit learning in many-to-one matching markets. In Proceedings of the 1 ACM International Conference Information & Knowledge Management, pages 2088-2097, 2022.
[31] Yirui Zhang, Siwei Wang, and Zhixuan Fang. Matching in multi-arm bandit with collision. In Advances Neural Information Processing Systems, 2022.
12

---

A Proof of Theorem 4.1
pa.l the estimated reward is far from the expected reward at some time and some player-arm pair. The regret can be upper bounded as follows.
Define F= (E) st [M] [K] [ta,(t)
Glog T (t)
the failure event that
r
Regi (t) =E
(pim - x((1))
<B
(pamm - X.((t) |7F
+ +F(F) T pt.
T
T
<B
((A(tt) =a} Ammis 1
+E Σ
((A,tt) = =0} pa.m;
F
+ P (FF T ps,m;
% 2 log 7/A2 2 + 96K log T/A + 192N2 log T/A² + 2NK
(1)
0 (N₂ log T/4² 2 K log T/A).
where Eq. (1) holds based on Lemma A.1, A.2, and A.4. Lemma A.1.
E
M
(A((t) =,} Asmg 7F
96N2 log T/A" 2 96K log T/A.
Proof. Recall that player p: would update the available A, when other players pv sets By False and AA,. > TAp. as Line 14. Denote la as the round index when this operation happens for the s-th time. Without loss of generality, let to 1.
Recall that at a high level, each time another player py sets Eg as False, it means that pa learns its most preferred arm in current available set. Combined with F and Lemma A.6, the determined arm of players during each exploration would be truly their most preferred one. Thus the AETGS algorithm is online version of GS and the s'-th time player py sets Eş False is equivalent to that Pr proposes its s'-th most preferred arm in the offline GS. According to Lemma A.3, at most N 1-1 arms are proposed by all players before reaching stability. Thus for player pi, the operation in Line 14 would happen for at most N - times.
Recall that for each during time f., to 4 player pt would explore all available arms in round- robin manner, climinate sub-optimal arms until N arms are in the set, and focuses on the best one among these N when it is identified. For convenience. denote R, the set of the remaining N arms that ps explored in Ag in a round-robin manner until condition Line is satisfied, D2 as the set of arms that pa eliminated due condition Line 6, and j. the arm that p; focuses from the time it sets E, as False to time fs+1- - 1. Then it holds that
E
((A(()) a;} Aim, F
aj
N-16
<B
Σ
Σ
Σ
I(A((t) a,} Dimoz 1F
1=| 4j
N-16U-1
<B
Σ
Σ
Σ 1{A:(1) = az} Aimit + Σ 1(A:(()) =,z} -A Aimmi
0= t=b,
a,ER.
eyED.
+1(A((t) J Aim,; 5.) [FF]
13

---

N-16-111
<B
Σ 1(A(1)) az} Aimps Σ I(A((1) =a3} As,my a,ER,
17
o,ED.
where Eq. (2) due to that, based on Lemma A.6 and the offline GS algorithm, the arm ja before GS stops would be better than m. thus the regret caused by selecting these arms is less than 0.
For the first term in Eq. (2), we have
1 fx+1-1
Σ {(A(11) = = Aimms 1
(3)
RyER,
{(,((t) a,} Aimm 17
Ry
96 96 T
<
A immi 7F
(4)
A
==0 R,ER,
96N22 log
(5)
A
where Eq. (4) is due to Lemma A.5, Eq. (5) holds since R, contains no more than N arms according to the elimination condition (Line 6).
We now analyze the second term in Eq. (2). For any arm aj and E {0,..., N - 1}. denote T Tag. the value of Ti, the end of the round 1.+1 if T Tijas- I 96 96log P/AA...-. it must hold that Tıj.
For s 2 1 and arm aj D., Exco(Tijs'
-i) S
(.... to ensure arm a, is eliminated from A, at step based on Lemma A.5. On the other hand, if T 1.j,8-1 > 96 log T/A based on Lemma A.5, it holds that Tı.j. - Tijaa- S
96 log T/
96 96log T/4 J.J 96 96log T T/ R..... 1- when a, is eliminated. For any arm aj. denote $j11
maxog.5N-1 {8: Tig., S 96 log T/ f.. as the last step when the number of observation times
aj is less than that threshold. Then the second term in Eq. (2) satisfies
N-15.111
E
Σ
Σ
Σ 1{A((!) a,} Aimis 1
ayED,
411-1
=B
[(A((t) az} A Aimm; 1
BjEK eD
t=
=B
Σ
(Tis. - Teg.o-)) Aimps I7F
R, EK ED,
=B
Σ
Σ
(Tij. - 1og
Σ
(Tigo Testo-1) Dimgs 17
REcK
siaj Su.
sin EDy
<B
Thihe +
Σ
(Tij, Tisie-1)
Dimis 1
ayEK
(96log T/Ab, - 96 T/A? //.3..11)))) :2) Aimis
96 log T
< Σ
Σ
?
a3EK
14

---

S Σ
96 log T
Am, S 96K log T/A,
A Emmis
ayek
where the second last line is due to the definition of 8,,1 and the above analysis.
Above all.
((A(t)) - -a}} Ammtd DF
Eq. (2) S 96N log + 96K log T/A.
Lemma A.2.
T (A.(1) = =0} pi.m |7 I 192N log 7/4².
Proof. Based the AETGS algorithm, when E; True, the central platform would assign arms in A; to player in round-robin manner. Since the number of arms = to be explored larger than the number E: IEE,- Truc} of players with E; True based on the elimination condition in Line 6, we can assume that there is no collision in the exploration phase as discussed in Section 4. So the regret caused by collision only occurs during time with E, False.
Denote Lg and is as the round index when p; sets E4 as False for the 8-th time and as True for the + 1-th time, respectively. Recall that when F2 False, p; will always select arm A, Here js to represent the arm that is selected by from time f, to 7,.
Further, recall that in the AETGS algorithm, each time arm is added into D. (Line 13), the eliminated arms may be contained into A, again. And only when other players focus on their currently most preferred arm, such operation of adding arms to D happens. Based on Lemma A.3, such an operation happens for at most times. For any player pv, denote tyrr as the round index when Pr adds arms to Dr (Line 13) for r-th time. Then (ty.r)e(Nt further divide {[t,, &a]] SE[M]
into at most 2N slices. We use t to represent the start round and end round index of the s-th slice, where E [2.].. Based on Lemma A.5, py and pt would select the same arm for at most 96 log 7/A2 times within each slice.
Then the regret satisfies
L {(A,(t)
E
1 (t)
03 pi,,
7F
E
0) Mi,m; 7F
E
((A(() A. =ja] pimm 7F
1=
4
E
Σ
1{A,(0) Ar(t) =js} Hi,m PF
2N
F.
E
Σ
Σ
1(((t) = As(t)) H6.m² 1F
2N
96 log T/A2, Mim
$ 192N2 log 2/22.
Lemma A.3. In the offline GS algorithm, most N arms have been proposed by players before the algorithm stops.
15

---

Proof. Based on the offline GS algorithm, once an arm is proposed, it has temporary player. By contradiction, once N arms have been proposed, means that N players are occupied. In this case, each player has partner and the algorithm stops.
Lemma A.4.
P(F) 2NK/T.
Proof.
6log T (t)
( = P
31 S [M] E [K] (Ri,(t) - pa. >
6log
E
P [piS(t) (pas(t)-noss>>>>
(1)
t=1 EE(N JE[K]
T
33
6 fog
Ti,s(t) =s (,) Ma.l
1=1 NEN JE[K] s=1
T
1. 1-2exp( -33nm
1ml JE(K]
$ 2NK//T,
where the second last incquality is due to Lemma B.I.
Lemma A.5. For any player pa, ler T; 96 A. For any two arms j.3' with pi.j > Pay and (:(a)) E (1,a)(m)) if T.))) = min (t),(t), Tes (4) > Tü we have UCB (1) < (CB,,(() conditioned on "F.
Proof. By contradiction, suppose (C 2 (t) According to FF and the definition of LCB and UCB, we have
6 6log T Maj -V (t)
6log T?
I (CB 1 UCB Mag +2/
We can then conclude Aijy' Psg Mtg < vv
Glog T((0)
which implies that Ti(t) < 96 log
96 log T This contradicts the fact that Tt(t) > T,
A
Lemma A.6. Conditioned on FF, at any time t, (C) < LCB,, (t) implies pis < Migs
Proof. According the definition of LCB and UCB, have
6 log T V (t)
6 6log T (t,
= (t)
$ Pij S (t) + V
(t),,,t),
where two inequalities comes from FF. Thus if UCB:,(() < LCBr (l), there would be Pig S (t) < LCB,,)()) p...
The lemma can thus be proved.
B Technical Lemmas
Lemma B.1. (Corollary 5.5 in Lattimore and Szepesvári (19]) Assume that X1, X2...... independent, o-subgaussian random variables centered around p. Then for any > 0.
Xn
are
n
ns²
PP
x 2u
exxp
F
X
S p 8
S
Sexp
72
20
m
2
1=1
i=1
16

---

Lemma B.2. (Arrangement of players' round-robin exploration) Suppose there are N players who need to explore their respective N arms. There exists an assignment such that during 2N rounds, each player can match with each of its arm for once.
Proof. Without loss of generality. let's assume that players assign their respective arms in 2N rounds one by one, based on the players' and arms' indices, aiming to ensure that no arm is assigned to more than one player the same round. By contradiction, suppose when player p; assigns its j-th arm, there is no available round to make this assignment due to conflicting constraints. Given that player pt currently assigning the j-th arm, implies that there are 2N -j+1 1 rounds where no arm is assigned to player p:- Since none of these rounds satisfy the conflict constraint, it means that the previous players assigned arm j in these 2 - + rounds. This creates a contradiction since the first - players can only occupy i rounds when selecting arm where i - 1 < 2N j with - N.j S N.
C Proof of Theorem 6.2
In this section, we analyze the regret of the centralized- UCB algorithm under a-condition. Recall that = 1EI st T i E [M], E [K] (t. - Ma,l > V (r)
is the failure event that the estimated reward is far from the expected reward some time and some player-arm pair.
/6 T
For any player ps with E [N], we know that its stable arm is ag under a-condition. Thus its regret can be decomposed as
Rega (T) SE
Σ
ALLA Σ 1A(00)-
+ +T-
1=1
The first term the number of selections for sub-optimal arms. The second term is the regret caused by the bad events.
For the arm ax such that it is sub-optimal for player p., i.e., Mig < Piii will be selected because the preference for arm ag of player p; is estimated higher than its stable matched arm dg or player p: is rejected by arm aş in the GS algorithm. Note that under a-condition, there is right order Qr = iie E [|] for player pt, such that Vi' < < S N, Qe" E [N]r Qu, >> Qur which means arm ag a, can only prefer players PQ2>" .PQ.- than player PQ, Pt. Denote The right-order mapping for a-condition for player pa is Ir(i) so that Qii(i) i with Q, defined in Definition 6. 1, and (r(i) < N. For player pt. denote Gi := {VI < < (r(1) 1, Aq. (t) * i} as the event all players preferred by arm a; do not select pa at time Then the number of selections for sub-optimal arm ag can be decomposed as
T
((t(()) = [F}
=F
((A(()) k, K, JF}
+E Σ (A.(1) = Gi.., VF}
<E
((A,(t) k. UCB (t).,:(), 2F}
+E Σ 11 ((A((t) k. Tr,s, FF]
24 log T
Σ (AA(t)) -000)=k = Te,, 1イ}
+ E
A
The last inequality is from Lemma C.I.
For the second term the RHS of the last inequality, E Dr of ((A((() = k. Tr.s, V7}. sum over all sub-optimal arms and turns out to be
we can
T
E
Σ
((A(tt)
Gr.. 7F}
t=1
17

---

T
1 Ge,s VF}
In(() T
<E
1 (t) [F}
1-00-1 (r())
24 log
A vf Au.
w==1 w² ="=a'+1
(r(() 1003--0(())---
24 2o T
Σ
(kAN)²
(I(())
(1r(()) 1)
Σ
1
24 1og T
k2
A
$ (1r(1)) 1) 5T log
A
where the third inequity is from the Lemma C.2. The fourth inequality is from the definition of AN- Above all, the stable regret of player can be bounded by
Reg. (T) SE
Σ
A
Σ ((A(1))= = [F
+T +T-P(F)
2
5T log T
Σ
Disn (Ir(1) 11
222
A L1
A
k:ps, Spe.
24K log T
5TT2 log T
+ (Ir(1) - 1)
+ 2NK
A
K Klog
N Nlog T
<0
A
where the second inequality is based on Lemma A.4.
Lemma C.I. Conditioned on IF under the traditional single-player UCB algorithm with single player Ps, the expected number of times at which the UCB index of arm ay exceeds that of the better arm aj is most 24 log(T)) 2 by round T.
Proof. Conditioned on IF, for any i, we have,
(log(T)
6log(T) Tt 11) 1)
(t Ar. - 1) < pas +
(6a)
Recall that the UCB index is:
Glog(T) UCB = (b. Tt - 1)
(6b)
The event that arm ay is successfully selected for player pa rather than the better arm aj time implies that
UCB UCB.,(() (t).
(6c)
Hence,
18

---

(log(T)
(Ba)
Glog(T)
P4.5' + V
Pss 1) +
(1 -1
Tigi - 1)
(6c)
6 Glog(T)
Pt - 1) +
Ti,
6 (lgg(T)
6 (T) Tig(1 -1)
> Pig
(1,s1 (11 +
which leads to
Tey (t 1) 24 24 (T)
where Aijid' is the reward difference between the pigj and pij.
Lemma C.2. For any player ps with right order Qir(i). the following inequality holds:
In(i)-1
E
Σ
Σ
1(
(1) - (1) iF
Tr())1
Ir())
<B
Σ
Σ
Σ
1 1fA (f) qu", Ge,u's [F}
u'=l
="=w'+
Ir(i)
1 Ir(()
24 T
<
Proof. For player P: with right order Qirū), from a-condition we have that its stable matched arm a, may prefer PQ, PQa."". .PQur(n- than player PQrrce" For any i' Ir(i), we know that the number of times player PQ, selects arm a, is decomposed as by
T
(1)
i,)
=E
Σ 1 (Aq (t) = -, 3F} + IAA (t) -,, i, 7F}
The event "Gr, implies that there exists another player PQ,, with 1" < i' that selects the stable arm of PQ.. This leads to a recursion form. But it easy to verify that every event "G,, happens only when there exists two players PQ.,; with u' < n" s Ir(i'), such that player pQ., explores the stable matched arm ag of PQ... i.e., PQ., selects Og," conditioned on Gewu. And thus it holds that
Ir(i)=1
T
E
Σ
Σ
(1) = [F}
E=1
Ir(i)
<B
Σ
1 (Aew (1) = qar, Grme, FF}
w=l
1/= +1 1=1
Ir(1)
In(3)
24 T
<
Σ
==
""=w
19

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Our abstract and introduction clearly describe the scope and outline our main contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 7 discusses the limitation of this paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
20

---

Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide techniques clearly in the paper, and their detailed proofs are in
Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: Section provides the settings and results of our experiments carefully,
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. novel architecture, deseribing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
For example, if the contribution
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
21

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The codes uploaded in supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips. http:ccccppcccccciiieeeeeeccccee /Coeee/m/deeubiimec wetomisssiooo asionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer:
[Yes]
Justification:
Section 5 provides the settings and results of our experiments carefully.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
22

---

Justification:
We provide the error bar in the results of experiments in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: We do not provide specific information on the computer resources used, as most experiments on multi-armed bandits are lightweight.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https / http://nuurrp.peee httpp///p..p.ittccccccice....aa.
Answer: [Yes]
Justification:
The research conducted in the paper complies with NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
23

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
24

---

Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode cww/coo//////// datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out the asset's 's creators.
13. New Assets
Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
25

---

According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "UzfLH0Mn1k", "reviewer": "Reviewer_unKj", "summary": "This work studies the problem of bandit learning in two-sided matching markets, where the number of players $N$ is smaller than the number of arms $K$. The players' preferences $\\mu\\_{i,j}$ are unknown but the arms' utility preferences $\\pi\\_{i,j}$ are known. Two algorithms with improved regret bounds are proposed. The first one is adaptive online Gale-Shapley (AOGS) for general markets, where multiple stable matchings exist. In AOGS, each player follows an adaptive explore-then-commit strategy to identify the best available arm based on the confidence bounds of each arm reward estimates and whether an arm is better matched to other players. The regret bound of AOGS is stated in terms of a new notion of gap. The second algorithm is centralized UCB combined with offline Gale-Shapely for markets with $\\alpha$-condition, where a unique stable matching exists.", "questions": "Please see the questions in the Weakness section above. One more question below:\n- The assumption that $\\pi\\_{i,j}$ are known seem strong and has been exploited thoroughly in previous works. How are the results impacted if this assumption does not  hold?", "limitations": "- The paper relies on a strong assumption that $\\pi\\_{i,j}$ must be fully known and does not discuss how the approach and results change if this assumption is violated. In particular, it is not clear whether a weaker assumption would work, such as only the top $k$ $\\pi\\_{i,j}$ are known for $k < \\min(N, K)$.\n- The theory in this paper concerns a practical setting that might have some potential societal impacts, none of which is significant.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Novelty: The following contributions of the work seem novel: the new definition of the gap, the exploration strategy in Algorithm 1, and the improved analysis of Algorithm 2.\n- Significance: All algorithms appear to be rigorously analyzed. No proofs are missing. The bound in Theorem 6.2 have optimal dependency on $K, N$ and $log(T)$ compared to a known lower bound.\n- Writing quality: The paper is generally well-written.", "weaknesses": "The contributions are rather incremental. Details are below:\n- The new bound in Theorem 4.1 depends on a new notion of gap. Given that the existing literature in Table 1 already have at least three different notions of gaps, it is not clear in what sense another type of gap is better than the existing ones. Does the new gap capture the difficulty of practical scenarios better? This was not sufficiently discussed in the paper. \n- A lower bound result for the new gap is missing. As the paper acknowledged, comparing with the lower bound in Sankararaman et al is not entirely meaningful because the lower bound there uses a different kind of gap.\n- In general, a comprehensive comparison with existing results is missing. For example, do any of the existing results in Table 1 imply anything about the new results in the current paper? Another thing is Algorithm 2 was proposed by Liu et al for $\\mathrm{gap}\\_2$, while the paper uses the same algorithm for $\\mathrm{gap}\\_3$ under $\\alpha$-condition, so it is not clear why the analysis in this paper is considered an improved version of the one in Liu et al (the goal is different). Maybe if the proposed analysis implies that Algorithm 2 obtain optimal bounds on multiple types of gaps *simultaneously*, then it would be a significant result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer unKj for the valuable comments. Please find our response below. \n\n- New gap definition in Theorem 4.1, lower bound for the gap\n\nRecall that the regret dependence on the gap is $1/\\Delta^2$, which means the larger the gap, the better the regret. Though we define a new gap in Theorem 4.1, this gap is larger than all of the existing works for the general one-to-one markets (only the result of [19] depends on a larger gap than ours but they have a strong assumption of known $\\Delta$), implying that our result not only exhibits better dependence on market sizes but also improves dependence on \\( \\Delta \\). \n\nWhen players know their exact preferences, they can follow the offline Gale-Shapley algorithm, selecting arms based on its preference ranking one by one until reaching the player-optimal stable matching. So in this sense, each player $p_i$ only uses the ranking of the top $\\sigma_i(m_i^*)$. Correspondingly, our new gap definition $\\mathrm{gap}_4$ characterizes the difficulty of learning this ranking information in the online setting. Regarding the lower bound, in the problem instance used to derive the lower bound [27], the stable arm of each player is simply their most preferred arm. In this case, our defined $\\mathrm{gap}_4$ in Theorem 4.1 is equivalent to the original $\\mathrm{gap}_1$. It is unclear whether the lower bound depends on either of these gaps in general markets. We leave this as an interesting future direction. \n\n\n\n- Comparison with existing works\n\nWhile the lower bound under different gaps remains unclear, we emphasize that our derived regret bounds strictly improve existing works regarding both market sizes and the gap. Specifically, for general markets, the $\\mathrm{gap}_4$ in Theorem 4.1 is larger than that in all existing works (except for [19] which assumes known $\\Delta$), and the dependence on market size also improves existing works in common cases where $N$ is much smaller than $K$. When markets satisfy $\\alpha$-condition, our $\\mathrm{gap}_3$ in Theorem 6.2 is larger than the original $\\mathrm{gap}_2$ for the centralized UCB algorithm [19], simultaneously removing the dependence on $K$. \n\n\n\n\n\n- Assumption of known arms' preferences\n\nWe first want to clarify that ``known arms preferences\" means that the arms know their preference rankings, but the players still do not have this information. \nWe consider the scenario with one-sided unknown preferences and aim to improve the learning efficiency towards the player-optimal stable matching. In existing works of this line, arms' preference rankings are used to determine whether an arm is a player's possible stable arm (by letting multiple players select the arm and observe who is accepted). If the arms' preferences are also uncertain, players cannot directly ascertain this information in a single round, and the convergence results of existing works do not hold.\nWe agree that exploring the two-sided uncertainty is an important direction and some studies have begun to delve into these domains (listed below). Nevertheless, for the currently considered fundamental framework, the optimality problem remains open. We hope to first develop a deep understanding of this fundamental setting and perform a tighter analysis before expanding our focus to encompass generalizations of the setting.\n\n\nPagare, Tejas, and Avishek Ghosh. \"Two-Sided Bandit Learning in Fully-Decentralized Matching Markets.\" ICML 2023 Workshop The Many Facets of Preference-Based Learning. 2023.\n\nPokharel, Gaurab, and Sanmay Das. \"Converging to Stability in Two-Sided Bandits: The Case of Unknown Preferences on Both Sides of a Matching Market.\" arXiv preprint arXiv:2302.06176 (2023).", "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": "6WtNzkUqjG", "reviewer": "Reviewer_SWbh", "summary": "The paper proposed a new algorithm for bandit learning in matching markets and showed new results on regret bounds. However, the combination of bandits with matching markets is wired. Is there any evidence that practitioners would like to use bandits for learning in markets? The novelty of the theory is also unclear.", "questions": "1. The key novelty in the paper is unclear. What are the new techniques developed in the paper for proving the upper bound? \n\n2. Do you have any empirical markets that could use the proposed algorithms?\n\n3. How to generalize the techniques to decentralized markets?", "limitations": "The combination of bandits with matching markets is wired. Is there any evidence that practitioners would like to use bandits for learning in markets?", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper proposed a new algorithm for bandit learning in matching markets and showed new results on regret bounds.", "weaknesses": "The combination of bandits with matching markets is wired. Is there any evidence that practitioners would like to use bandits for learning in markets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer SWbh for the valuable comments. Please find our response below. \n\n- Technical novelty\n\nDealing with individual players' exploration-exploitation trade-offs has been extensively studied in the literature. However, in matching markets, researchers have not swiftly comprehended how to integrate this trade-off with interactions among players. Previous efforts were devoted to addressing pessimal stable regret and uniqueness assumptions using classic UCB and TS strategies [4, 17, 19, 20, 21, 27]. Until recently, Zhang et al. (2022) [29] and Kong and Li (2023) [16] have found that ETC-type strategies better fit this problem. Nonetheless, their strategies distinctly separate individual exploration from multi-player interactions, requiring players to first estimate their full preferences and then perform exploitation. This may lead to over-exploration as some estimated preferences are not used in finding the stable matching.\n\nWe propose a new perspective that integrates the players' learning process into GS steps. The algorithm promptly eliminates $K-N$ sub-optimal arms in each exploration cycle and adaptively switches between exploration and exploitation. Such design avoids unnecessary exploration of sub-optimal arms and successfully eliminates the dependence on $K$ in the regret, presenting a more suitable EE trade-off strategy in the matching market scenario. \n\n\n- Bandit in matching markets\n\nThe application of bandit algorithms in matching markets addresses practical scenarios where learning and optimization under uncertainty are critical. For example, many online platforms, such as job portals, dating apps, and online marketplaces, require iterative matching between users (e.g., job seekers and employers, buyers and sellers). These platforms often operate in environments with incomplete information and evolving preferences. Bandit algorithms can help these platforms learn and adapt to user preferences over time, improving the efficiency and quality of matches. \n\nWe acknowledge that our current setting may not perfectly cover real applications such as those involving asynchronous agents, contextual information, and switching costs. However, as a foundational framework, it represents a crucial aspect of learning through interaction with both players and arms. The corresponding algorithm in this basic setting also provides solutions for more general markets. \n\n\n\n- Extension to decentralized markets\n\nOur Algorithm 1 (AOGS) is designed for the decentralized setting and Algorithm 2 is for the centralized setting. For reader-friendly, the algorithm chart of AOGS only summarizes its centralized version. To extend to the decentralized setting, we can modify Algorithm 1 as a phased version like Kong and Li (2023) [17]. Specifically, the total horizon can be separated into several phases with the length of each growing exponentially.\nAt the beginning of each phase, players would decide whether to eliminate sub-optimal arms (Line 6-8), and whether to determine one arm as the most preferred one (Line 9-11, respectively). Each player then communicates with others about their current exploration status based on the available observation and then updates their deletion set, available arm\nset, as well as the exploration status (Line 12-19). All players can have a pre-agreed selection ordering for the next phase's exploration (based on the first paragraph of Section 4.1). Within the next phase, players only need to explore arms based on this pre-agreed ordering. In this way, the AOGS algorithm can be generalized to the decentralized setting without influencing the regret order. More details can also be found in the first two paragraphs of Section 4.1.", "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": "8Be90d8DQ2", "reviewer": "Reviewer_Y8Bw", "summary": "The paper studies the bandit learning problem in two-sided matching markets and provide improved regret analysis that nearly match the lower bound (although with slightly different definition of instance-dependent gaps). The bound is particularly useful when the number of players is much smaller than the number of arms. Numerical experiments show significant improvement under some special cases. The paper also improve the regret analysis for an existing UCB algorithm under an additional $\\alpha$-condition.", "questions": "I would suggest the authors add a paragraph in the introduction to explcitly point out the contributions in this paper. In particular, I would like to see the main algorithmic design insight be emphasized from this work. For example, why previous algorithms fail to obtain low regret (due to over exploration)?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The paper is very well-written. The flow is clear and easy-to-follow.\n2. Strong technical novelty as well as solid theoretical results. The paper gives new insights on how to balance between exploration and exploitation in matching markets.\n3. Numerical experiments show significant improvement compared to existing policies.", "weaknesses": "Although the dependence on $N$, $K$, $T$ is optimal, the main weakness lies in the difference of defining the instance-dependent gap $\\Delta$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer Y8Bw for the valuable comments. Please find our response below. \n\n\n- Gap definition\n\nWe agree that investigating the optimal dependence on the preference gap is an interesting future direction. Among all of the existing works, there are three types of gap definitions due to different learning processes to reach stability. Though it is still unclear whether the optimal result should be under different gap definitions, our provided Theorem 4.1 improves existing works for general markets in terms of both market sizes and gap definitions (without knowing $\\Delta$). This result has further advanced our understanding of the EE trade-off problem in the matching market scenario. \n\n- Contribution of this work\n\nThanks for your suggestion. We will add a paragraph summarizing our contribution in the introduction and the following is a draft: \n\n1. We propose an adaptive online Gale-Shapley (AOGS) algorithm for general markets. State-of-the-art works [29, 16] explicitly separate the exploration and exploitation processes, which can lead to unnecessary regret, as exploring certain preference rankings may not contribute to the exploitation process. To avoid excessive exploration, our AOGS algorithm integrates the players’ learning process into the GS steps. Players explore only the necessary number of candidate arms and adaptively switch between exploration and exploitation.\n\n\n2. We prove that the player-optimal stable regret of AOGS can be upper bounded by $O(N^2\\log T/\\Delta^2 + K\\log T/\\Delta)$. This is the first result that removes the dependence on $K$ in the main regret order term and improves existing works in common cases where $N$ is much smaller than $K$. We also conduct experiments to show the advantages of the algorithm. \n\n\n3. We refine the analysis of the centralized UCB algorithm in [19] for markets satisfying the $\\alpha$-condition. By investigating the preference hierarchy structure of the $\\alpha$-condition, we demonstrate that the stable matching converges sequentially from player $1$ to player $N$. Through inductive analysis over $N$ players, we establish an $O(N \\log T/\\Delta^2 + K \\log T/\\Delta)$ regret upper bound, which enhances the original result for this algorithm in this specific market.", "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": "5YwdneSFpt", "reviewer": "Reviewer_Pjvv", "summary": "This paper considers two-sided matching bandit problems, where the goal is to minimize regret against a player's optimal stable matching. The state-of-the-art algorithms achieve a regret bound of  $KlogT/\\Delta^2$.  The authors suggest an algorithm using an adaptive online Gale-Shapley to achieve a regret bound of $N^2\\log T/\\Delta^2$ under $N<K$. Under $\\alpha$-condition, they provide a new analysis for the previous algorithm to achieve a regret bound of $N\\log T/\\Delta^2$.", "questions": "Without $\\alpha$-condition, is the lower bound linear with respect to $N$?", "limitations": "The authors have discussed the limitations in the conclusion.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors suggest an adaptive online Gale-Shapley algorithm.\n2. The suggested algorithms outperform the previous algorithms when $N$ is much smaller than $K$.\n3. They demonstrate this result using synthetic experiments.", "weaknesses": "1. Without $\\alpha$-condition, the upper bound has $N^2$ instead of $N$, which may not be tight with respect to $N$.\n2. Even though they provide a new algorithm, it may be hard to see the technical novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer Pjvv for the valuable comments. Please find our response below. \n\n- $N^2$ regret for the general market\n\nIn the matching market problem, each player needs to navigate both his individual explorations and game interactions with others. Considerable work has been done to investigate the optimal regret upper bound for this problem, starting from pessimal stable regret and unique stable regret to, only recently, results on player-optimal stable regret. \n\nAlthough the tightest regret bound remains unclear, our regret upper bound of \\(O(N^2\\log T/\\Delta^2)\\) eliminates the dependence on \\(K\\) in the main regret order term for the first time. This observation has enhanced our understanding of the role of the arm set size \\(K\\) in this learning problem and advances our comprehension of the core difficulty arising from the game interactions among $N$ players.\n\n\n- Technical novelty\n\nDealing with individual players' exploration-exploitation trade-offs has been extensively studied in the literature. However, in matching markets, researchers have not swiftly comprehended how to integrate this trade-off with interactions among players. Previous efforts were devoted to addressing pessimal stable regret and uniqueness assumptions using classic UCB and TS strategies [4, 17, 19, 20, 21, 27]. Until recently, Zhang et al. (2022) [29] and Kong and Li (2023) [16] have found that ETC-type strategies better fit this problem. Nonetheless, their strategies distinctly separate individual exploration from multi-player interactions, requiring players to first estimate their full preferences and then perform exploitation. This may lead to over-exploration as some estimated preferences are not used in finding the stable matching.\n\nWe propose a new perspective that integrates the players' learning process into GS steps. The algorithm promptly eliminates $K-N$ sub-optimal arms in each exploration cycle and adaptively switches between exploration and exploitation. Such design avoids unnecessary exploration of sub-optimal arms and successfully eliminates the dependence on $K$ in the regret, presenting a more suitable EE trade-off strategy in the matching market scenario. \n\n\n- Lower bound in the general market\n\nThe state-of-the-art lower bound for this problem is $\\Omega\\left(\\frac{N\\log T}{\\Delta^2}\\right)$ under the serial dictatorship condition [27] where all arms have the same preferences.\nThe general market may be more challenging since the game interactions among players become more complicated. In this setting, the specific dependence of the lower bound on $N$ and $K$ is still unclear. But as demonstrated by the result in [27], there must be at least a linear dependence on $N$. Investigating the optimality in general markets has been extensively studied and we leave this problem as an important future direction.", "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:

Meta-review: The paper proposed a new algorithm for bandit learning in matching markets with regret analysis. It offers new insights into balancing exploration and exploitation in matching markets. The numerical experiments demonstrate significant improvements over existing policies. Please include the discussion on the lower bound and emphasize the precise list of contributions in the final version.
Decision: Accept (poster)