Improved Analysis for Bandit Learning in Matching Markets

Authors: fang  kong
zilong  wang
shuai  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 10:47:20

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.

Main paper: 
 introduction: 
 The two-sided matching market problem has been extensively studied in the literature due to its wide range of applications like labor market, school admission, house allocation, and online advertising [25, 9, 1] . There are two sides of participants in the market, such as the employers and workers in the labor market, advertisers and publishers in online advertising. Each participant on the one side has a 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 [25] . Achieving stability is critical for ensuring the long-term viability of the market.A rich line of works [9, 15, 24] study how to find a stable matching in the market. Most of them assume the preference ranking of each market participant is known beforehand, which we refer to as 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 find an exact stable matching. With the emergence of online market platforms such as the online labor market UpWork 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 a classic framework that characterizes the learning process during iterative interactions [3, 18] . 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 exploitation. 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-commit (ETC) [10] are common strategies in MAB to achieve this objective.Liu et al. [19] introduce the bandit learning problem in matching markets and try to provide theoretical 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 ≤ K to ensure each player has a chance to 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 objective is the most desirable. Liu et al. [19] 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 ∆ and the latter can only ensure to reach the playerpessimal stable matching. Motivated by real applications where the central platform may not always exist, a rich line of works then study the decentralized case where no platform coordinates players' behavior [20, 27, 4, 17, 21] . This line of works again only achieve guarantees for player-pessimal stable regret [20, 17, 27, 4, 21] . Table 1 compares settings and regrets among these works. Until recently, Zhang et al. [30] and Kong and Li [16] independently derive algorithms that have polynomial player-optimal stable regret and show the upper bound is O(K log T /∆ 2 ). However, this result may be still far from the lower bound Ω(max{N log T /∆ 2 , K log T /∆}) [27] since K is usually much larger than N such as 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, we try to provide more efficient algorithms and improve the results over existing works. The detailed contribution can be summarized as follows:• We propose an adaptive online Gale-Shapley (AOGS) algorithm for general markets. Stateof-the-art works [30, 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. • We prove that the player-optimal stable regret of AOGS can be upper bounded by O(N 2 log T /∆ 2 + K log T /∆). 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. • We refine the analysis of the centralized UCB algorithm in Liu et al. [19] for markets satisfying the α-condition. By investigating the preference hierarchy structure of the α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.SettingLiu et al. [19] O K log T /∆ 2 * # known ∆, gap 1 O N K log T /∆ 2 # gap 2 Liu et al. [20] O N 5 K 2 log 2 T ε N 4 ∆ 2 gap 2 Sankararaman et al. [27] O N K log T /∆ 2 serial dictatorship, gap 1 Ω max N log T /∆ 2 , K log T /∆ Basu et al. [4] O K log 1+ε T + 2 ( 1 ∆ 2 ) 1 ε * gap 2 O N K log T /∆ 2 α-condition, gap 1 Maheshwari et al. [21] O CN K log T /∆ 2 α-reducible condition, gap 1 Kong et al. [17] O N 5 K 2 log 2 T ε N 4 ∆ 2 gap 2 Zhang et al. [30] O K log T /∆ 2 * gap 2 Kong and Li [16] O K log T /∆ 2 * gap 3 Ours O N 2 log T /∆ 2 + K log T /∆ * gap 4 O N log T /∆ 2 + K log T /∆ # α-condition, gap 3Table 1 : Comparisons of settings and regret bounds with most related works, * represents the playeroptimal stable regret and bounds without labeling * are for player-pessimal stable regret, # represents the centralized setting. N and K are the number of players and arms with N ≤ K, T is the total horizon, ∆ corresponds to some preference gap, ε depends on the hyper-parameter of algorithms, 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 gap 1 , gap 2 , gap 3 , gap 4 represent the minimum preference gap between the (player-optimal) stable arm and the next arm after 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 all 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 1 ≥ gap 4 ≥ gap 3 ≥ gap 2 . So our dependence on ∆ is better than the state-of-the-art works [30, 16] for general markets. 
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 some empirical methods to solve the problem. Liu et al. [19] first theoretically formulate this problem and provide an upper bound for the stable regret of players. They propose a centralized explore-then-commit (ETC) algorithm and upper confidence bound (UCB) algorithm, which obtain an O K log T /∆ 2 player-optimal stable regret and O N K log T /∆ 2 player-pessimal stable regret, respectively. It is worth noting that the former ETC algorithm requires knowledge about ∆ to ensure the algorithmic operation. Due to the generality, the following works focus on the decentralized setting. Liu et al. [20] and Kong et al. [17] propose the UCB and TS-type algorithm for general decentralized markets, respectively. Such a setting is much more challenging and both of them only achieve O exp(N 4 )N 5 K 2 log 2 (T )/∆ 2 upper bound for the player-pessimal stable regret.To improve the stable regret guarantee, a line of research studies some special markets with unique stable matching in which case the player-optimal stable matching is equivalent to the playerpessimal one. Sankararaman et al. [27] propose the UCB-D3 algorithm based on the assumption of serial dictatorship, i.e., all arms share the same preferences, and obtain an O N K log T /∆ 2 regret upper bound. To investigate the problem hardness, they also derive a lower bound Ω max N log T /∆ 2 , K log T /∆ under this assumption. Basu et al. [4] consider more general α-condition setting for unique stable matching. They propose the UCB-D4 algorithm and also achieve the O N K log T /∆ 2 regret bound. Later, Maheshwari et al. [21] study the market satisfying α-reducible condition and proposes a communication-free 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. [30] and Kong and Li [16] propose ETC-type algorithms that achieve O K log T /∆ 2 player-optimal stable regret. Wang and Li [28] studies the matching markets with serial dictatorship and obtains the O N log T /∆ 2 + K log T /∆ regret. Table 1 , compares our 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. [29] study a many-to-one market where an arm can accept multiple players. Jagadeesan et al. [12] consider online matching markets with monetary transfers. Min et al. [22] 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 et al. [23] , Ghosh et al. [11] , who propose robust algorithms to mitigate the impact of reward disturbances. 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. 
setting: 
 This paper considers the problem of bandit learning in two-sided matching markets. Denote N = {p 1 , p 2 , . . . , p N } as the player set and K = {a 1 , a 2 , . . . , a K } as the arm set. Let N and K be the 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 [19, 20, 27, 4, 17, 30, 16] .For each player p i ∈ N , its preference towards arm a j can be portrayed by an absolute utility µ i,j ∈ (0, 1]. For any pair of arms a j and a j ′ , µ i,j > µ i,j ′ indicates that player p i prefers arm a j over a j ′ . Following previous works for matching markets [9, 19, 20, 27, 4, 17, 30, 16] , players are assumed to have distinct preferences over different arms, i.e., µ i,j ̸ = µ i,j ′ for any a j ̸ = a j ′ . 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 a j also has a fixed and distinct preference utility π j,i over each player p i ∈ N , and π j,i > π j,i ′ means that arm a j prefers player p i over p i ′ . 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 [19, 20, 17, 27, 4, 30, 16] .At each round t = 1, 2, . . . , each player p i proposes to an arm A i (t). For each arm a j , denote A -1 j (t) = {p i : A i (t) = a j } as the set of players who selects arm a j at round t. When more than one player selects a j , it accepts its most-preferred one in A -1 j (t), i.e. a j will match with p i ∈ arg max pi∈A -1 j (t) π j,i . If a player p i is successfully matched with arm A i (t), it will receive a random reward X i (t) characterizing its matching experience, which we assume is a 1-subgaussian random variable with expectation µ i,Ai(t) . Otherwise, p i is rejected by its proposed arm and only gets reward X i (t) = 0. Denote Āi (t) as the final matched arm of player p i at round t. Then Āi (t) = A i (t) if p i is accepted by the arm A i (t) and we simply set Āi (t) = ∅ if p i is rejected.Stability is a key property of a matching in two-sided markets [9, 26, 24] . A matching Ā(t) = {(i, Āi (t)) : i ∈ [N ]} is stable if no market participant wants to break up its current matching relationship and find a new partner. Formally speaking, there is no player-arm pair (p i , a j ) such that µ i,j > µ i, Āi(t) and π j,i > π j, Ā-1 j (t) . It is worth noting that there may be multiple stable matchings in the market. Denoted M = {m : m is stable} as the set of all stable matchings. It is shown that there exists a stable matching m * ∈ M such that all players are matched with their most preferred stable arm [9] , i.e., µ i,m * i ≥ µ i,mi for any m ∈ M, i ∈ [N ]. Given a specified horizon T , the learning objective is to minimize the player-optimal stable regret for each player p i which is defined as the difference between the cumulative reward received by being matched with m * i and the cumulative reward received by p i over T rounds:Reg i (T ) = E T t=1 µ i,m * i -X i (t) .Here, the expectation is taken over by the randomness 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 to 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 p i , denote σ i as p i 's preference ranking and let σ i,k as p i 's the k-th preferred arm in its ranking. With a little abuse of notation, let σ i (a j ) represent the rank of arm a j in p i 's preference. For each player p i and arm a j ̸ = a j ′ , let ∆ i,j,j ′ = |µ i,j -µ i,j ′ | be the preference gap of p i between a j and a j ′ . Define ∆ = min i,k∈[σi(m * i )] ∆ i,σ i,k ,σ i,k+1 as the minimum preference gap between the arm ranked the first (σ i (m * i ) + 1)-th among all players. Further, define∆ N = min i,k∈[N ] ∆ i,σ i,k ,σ i,k+1as the minimum preference gap between the arm ranked the first (N + 1)-th among all players. 
adaptive online gale-shapley algorithm for general markets: 
 In this section, we propose an algorithm called adaptive online Gale-Shapley (AOGS). For simplicity, we present the centralized version of the algorithm in Algorithm 1 from view of player p i . The discussion on how to extend it to a decentralized version is deferred to later subsections.In general, AOGS is an online 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-11). And once the player finds this arm is occupied by a more preferred player, it would re-start exploration to find the next preferred arm (Line 12-19). Specifically, each player p i still maintains μi,j (t) and T i,j (t) to represent the empirical mean and the number of observations on each arm a j at the end of round t. To determine whether an arm is more preferred than another, it maintains a confidence interval for each arm a j with upper bound UCB i,j (t) := μi,j (t) + 6 log T /T i,j (t) and lower bound LCB i,j (t) := μi,j -6 log T /T i,j (t). When T i,j = 0, they will be initialized as +∞ and -∞, respectively. And once the confidence intervals of the two arms are disjoint, it can regard the arm with a higher empirical mean to be more preferred (Line 1). To be consistent with the offline GS, each player maintains D i to represent the set of arms that have rejected p i during previous steps. In the beginning, it is initialized as an empty set. And we use A i to represent the available arms with the potential to be the stable arm of p i , which is initialized as K \ D i . For convenience, denote E i as the exploration status of player p i . E i = True means that p i still needs to explore arms in A i to determine its most preferred arm. And E i = False means that p i 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 i and eliminate sub-optimal arms in real-time (Line 6-8). Here to avoid collision during round-robin exploration, we would maintain A i such that it contains no less than N arms if p i still has not determined its most preferred one. Thus the union of the available arm set over all players with E i = True contains more than N arms and the round-robin exploration over A i for each such player p i can be carried out without Algorithm 1 adaptive online Gale-Shapley (from the view of player p i ) Input: N, K, T .1: Initialize: μi,j (0) = 0, T i,j (0) = 0, UCB i,j (0) = ∞, LCB i,j (0) = -∞, ∀j ∈ [K]; 2: Initialize: D i = ∅, A i = K, E i = True; 3: for round t = 1, 2, • • • , T do 4:Select A i (t) ∈ A i in a round-robin manner;5:Update μi,j (t), T i,j (t) as Algorithm 2; compute UCB i,j (t), LCB i,j (t) for any j ∈ [K];6:if |A i | > N and ∃j ∈ A i s.t. UCB i,j (t) < max j ′ ∈Ai LCB i,j ′ (t) then 7: A i = A i \{j}; 8: end if 9:if ∃j ∈ A i s.t. LCB i,j (t) > UCB i,j ′ (t) for any j ′ ∈ A i and j ′ ̸ = j then 10:A i = {j}, E i = False, A i = j; 11: end if 12:for other playerp i ′ with E i ′ = False, A i ′ ∈ A i do 13: if π A i ′ ,i ′ > π A i ′ ,i then 14: D i = D i ∪ {A i ′ }, A i = K\D i ; 15:if E i = False and A i ∈ D i then16:E i = True; 17: end if 18: end if 19:end for 20: end for collisions. For completeness, we defer how to arrange players' explorations in later discussions. And once there exists an arm in A i that can be regarded to be optimal, p i will set the exploration status E i to be False and update the exploration arm set A i to only contain this optimal arm. For convenience, denote A i as this arm (Line 9-11).The update of the available arm set should not only depend on p i 's own observations but also on the other market participants. Specifically, if a player p i ′ determines A i ′ as its most preferred arm, then the final stable player of A i ′ would be the same as or more preferred than p i ′ . So if A i ′ prefers p i ′ than p i , then A i ′ would not be the stable arm of p i and there is no need for p i to explore A i ′ anymore. In this case, p i deletes arm A i ′ from its available set and update A i (Line 12-19). It is worth noting that this operation may incorporate the eliminated arms again in A i . This is reasonable as the previously eliminated arm may be more preferred than the current arms in A i after the deletion operation. And if the deleted arm is p i 's current most preferred arm, it will mark E i as True and restart exploration to find the next most preferred one (Line 15-17).Theorem 4.1. Following Algorithm 1, the player-optimal stable regret for each player p i satisfiesReg i (T ) ≤ O N 2 log T /∆ 2 + K log T /∆ .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 and significance of the result.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 2N rounds, the observation count difference among all available arms is at most 1. Players would perform arm elimination and optimal arm identification (Line 6 and 9) in the end of each 2N rounds. Therefore, compared to the timely eliminating/deleting 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 N 2 times (each of N players can focus on N arms), this scenario leads to an additional O(N 2 K) constant regret and does not influence the final regret order.Extension to the decentralized setting.For simplicity, we present the AOGS 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, 4, 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 a 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 E i = True can have a pre-agreed protocol to explore arms in their available arm set in a 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 a player's exploration status becomes True from False and a player updates E i from False as True only when its most preferred arm is occupied by a higher-priority player (Line 15). As shown by Lemma A.3, each player may occupy N arms, so such event happens at most N 2 times. And when all players find their unique optimal arm which requires O(N 2 log T /∆ 2 ) times, the phase would continue until the end of the interaction. Above all, the total number of phases is of order O N 2 log N 2 log T /∆ 2 . For the detailed communication procedure, as phase 1 in Kong and Li [16] , players can first estimate their unique indices and we assume the matching results are public as [16, 17, 20] . During the communication block of each phase, players sequentially transmit their data based on their indices, received by others through matching outcomes. Specifically, in the corresponding round, player p i selects the focused arm if E i = False and nothing otherwise, incurring an O N 3 log N 2 log T /∆ 2 cost for status communication in all phases. For deletion (eliminating) sets, p i first selects the arm with index k to indicate it will transmit k arms and then sequentially selects these k arms. The communication cost on the arm set size is O N 3 log N 2 log T /∆ 2 . Recall that players delete arms only when a higher-priority player focuses 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 eliminate up to K -N arms during each exploration and would re-start exploration for at most N 2 times. Thus the communication cost on the deletion (eliminating) arms is O(N 3 K) and the total communication cost is O N 3 log N 2 log T /∆ 2 + N 3 K , which is not the main order of the regret.Novelty and significance. Balancing the exploration-exploitation trade-off is the key to achieving low regret. Previous efforts were devoted to addressing pessimal stable regret [19, 20, 17] and uniqueness assumptions [27, 4] using classic UCB and TS strategies. Until recently, Zhang et al. [30] 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-optimal stable matching. However, such a method may over-explore and cause unnecessary regret. The reason is that to learn the first N -ranked arms, each sub-optimal arm a j must be selected O(log T /∆ 2 i,σ i,N ,j ) times to be distinguished from the N -ranked arm. And each time selecting this arm, the player pays ∆ i,m * i ,j regret. The mismatch between the paid regret and the difference to be figured out results in O(K log T /∆ 2 N ) regret. In contrast to the existing approach, we present a more adaptive perspective that integrates the learning 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 identified. And if this arm is occupied by a 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 also design a 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 a j , the reward difference to be figured out is at least ∆ i,m * i ,j , which matches the regret when selecting this arm. So the regret caused by these eliminated arms is O(K log T /∆), avoiding the dependence on K in the main order term. This is a more effective way to balance exploration and exploitation in matching market scenarios. Our result also shows a significant improvement over Zhang et al. [30] and Kong and Li [16] in common applications such as labor markets and online advertising where the number N of players (employers, advertisers) is far smaller than that K of arms (workers, publisher slots).Discussion on the definition of gaps. Recall that our ∆ is defined as the minimum preference difference among arms that ranked in the first (σ i (m * i ) + 1)-th positions (gap 4 ), while the lower bound in Sankararaman et al. [27] for markets with serial dictatorship depends on ∆ that is defined as the minimum preference difference between the arm ranked σ i (m * i ) and the arm rankedσ i (m * i ) + 1 (gap 1 in Table 1, respectively).It is an open problem whether the lower bound should depend on our gap 4 in general markets. Here we would like to discuss that the knowledge of gap 4 is necessary to learn the true stable matching. Consider a market with 4 players and 5 arms. The preference rankings of players are p 1 :a 1 > a 2 > a 3 > a 4 > a 5 ; p 2 : a 2 > a 3 > a 1 > a 4 > a 5 ; p 3 : a 3 > a 1 > a 2 > a 4 > a 5 ; p 4 : a 1 > a 2 > a 3 > a 4 > a 5and the preference rankings of arms are a 1 :p 2 > p 3 > p 4 > p 1 ; a 2 : p 3 > p 4 > p 1 > p 2 ; a 3 : p 4 > p 1 > p 2 > p 3 ; a 4 : p 1 > p 2 > p 3 > p 4 ; a 5 : p 1 > p 2 > p 3 > p 4 .In this market, the player-optimal stable matching is {(p 1 , a 4 ), (p 2 , a 1 ), (p 3 , a 2 ), (p 4 , a 3 )}. However, if player p 1 has collected enough observations to identify gap 1 but not collected enough observations to identify gap 4 and wrongly estimate the first σ i (m * i ) ranked arms, i.e., p 1 wrongly estimate the preference ranking as p 1 : a 1 > a 2 > a 4 > a 3 > a 5 . Then the computed player-optimal stable matching under this preference ranking is {(p 1 , a 4 ), (p 2 , a 3 ), (p 3 , a 1 ), (p 4 , a 2 )}, which is not stable in the original market as player p 1 and arm a 3 form a blocking pair. This example shows that player p 1 must identify the gap among the first σ i (m * i ) ranked arms to find a stable matching in the market, which further illustrates the crucial role of gap 4 in finding the real stable matching. We leave the lower bound in general markets as an important future direction. 
experiments: 
 In this section, we compare our Algorithm 1 with baselines ETGS [16] , ML-ETC [30] and Phased ETC [4] which also enjoy guarantees for player-optimal stable regret in general decentralized oneto-one markets. To better illustrate the advantages of our algorithm, especially 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 X i,j (t) for player p i on arm a j at time t is drawn independently from the Gaussian distribution with mean µ i,j and variance 1. We report the maximum cumulative playeroptimal 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 as standard deviations divided by √ 50.As shown in the figure, our AOGS algorithm, which only conducts necessary explorations over unknown preferences and promptly eliminates sub-optimal arms, achieves the least cumulative regret and cumulative player-optimal unstability among all baselines. The ML-ETC and ETGS algorithms 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. 6 Centralized UCB Algorithm for α-conditionIn this section, we provide a new analysis for the centralized UCB algorithm in markets satisfying α-condition. The algorithm is first introduced by Liu et al. [19] . For completeness, we present the full algorithm in Algorithm 2. At each round, players submit their UCB rankings to 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: μi,j (0) = 0, T i,j (0) = 0, UCB i,j (1) = ∞, ∀i ∈ [N ], j ∈ [K]. 2: for round t = 1, 2, . . . , T do 3:Receive rankings σ := {σ i } i∈[N ] according to the decreasing order of {UCB i,j (t)} j∈[K] , ∀i ∈ [N ]; A i (t) ←Gale-Shapley (σ, π) for each player p i ; 5:Observe X i (t), and update μi,j (t), T i,j (t), UCB i,j (t + 1) for each p i , a j ; 6: end forIn the following, we introduce the α-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 [27, 4, 21] . Among these conditions, the α-condition is shown to be the weakest sufficient one [13] and incorporate the conditions studied in existing works [27, 4, 21] .[N ] β = {Q (β) 1 , . . . , Q (β) N } and [K] β = {q (β) 1 , . . . , q (β) K } denote permutations of the ordered sets [N ] and [K], respectively. The j-th player in [N ] β is the Q (β) j -th player in [N ], and the k-th arm in [K] β is the q (β) k -th arm in [K].Then we can define the α-condition below. Definition 6.1. The α-condition is satisfied if there is a stable matching (j * , i * ), a left-order of players and arms s.t. ∀i ∈ [N ] l , ∀j > i, j ∈ [K] l : µ i,j * i > µ i,j where j * i is the partner of player p i in stable matching (j * , i * ), and a (possibly different) right-order of players and arms s.t.∀j < i ≤ N, q j ∈ [K] r , Q i ∈ [N ] r : π qj ,Q i * q j> π qj ,Qi . Here similarly, i * qj is the partner of arm a qj in stable matching (j * , i * ).Without loss of generality, we consider the identity of players and arms is just the left order, i.e., [N ] = [N ] l and [K] = [K] l . Thus we only deal with player order Q (r) i = Q i and arm order q (r) j = q j , for i ∈ [N ], j ∈ [K] in the rest of the paper. Under α-condition, it is easy to inductively verify that for any i ∈ [N ], the player p i is matched with arm a i , and the player p Qi is matched with the arm a qi in the unique stable matching [4] .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: The codes are uploaded in supplementary material.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
theoretical results: 
 We analyze the regret for the centralized UCB algorithm under α-condition. Theorem 6.2. When preferences of participants satisfy α-condition, following Algorithm 2, the stable regret for each player p i satisfiesReg i (T ) ≤ O N log T /∆ 2 N + K log T /∆ .The centralized UCB algorithm is proposed by Liu et al. [19] and shown to have O(N K log T /∆ 2 ) player-pessimal stable regret for general markets. We provide a new analysis for markets satisfying α-condition which removes the dependence of K in the regret. Due to the space limit, the detailed proof is deferred to Appendix C.Key idea of the proof. We investigate the preference structure of α-condition to obtain the improved analysis. For player p i , its regret is due to selecting sub-optimal arm a k with µ i,k < µ i,i . Arm a k will be selected by p i when its UCB value is higher than p i 's stable matched arm a i , which time is bounded by O(log T /∆ 2 i,i,k ), and one ∆ i,i,k on the denominator can be eliminated when multiplying ∆ i,i,k to compute regret. This contributes O (K log T /∆) regret since there are at most K -1 sub-optimal arms. It is worth noting that arm a k will also be selected by p i if p i is rejected by a i in the GS algorithm. Recall that under α-condition, there is a right orderQ i ′ = i ∈ [N ] r for player p i , such that ∀i ′′ > i ′ , Q i ′′ ∈ [N ] r : π q i ′ ,Q i ′ > π q i ′ ,Q i ′′ , which means arm a q i ′ = a i can only prefer players p Q1 , p Q2 , • • • , p Q i ′ -1 than player p Q i ′ = p i .Thus p i is rejected by a i only when these players select a i , and a i is sub-optimal for those players. To bound the regret of p i when being rejected, we just need to bound the exploration times of these players p Q1 , p Q2 , • • • , p Q i ′ -1 on arm a i . However, the exploration time of a single player p Q ℓ with 1 ≤ ℓ ≤ i ′ -1 on a i can not be trivially bounded by O(log T /∆ 2 N ) since p Q ℓ may have to select arm a i after rejected by its stable arm a q ℓ in offline GS, where a q ℓ might be selected by p Q1 , • • • , p Q ℓ-1 . This leads to a recursion form. We control this term using the fact that when a player is rejected by its stable matched arm in the GS, it can date back to a higher right-order player wrongly over-estimate its preference for a sub-optimal arm. This key observation and the definition of ∆ make it possible to derive the final O N log T /∆ 2 N bound.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 to a 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, or as supplemental material. 
conclusion: 
 In this paper, we investigate the problem of whether a 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 2 log T /∆ 2 + K log T /∆). This result removes the dependence on K in the main order term of existing works and improves the stateof-the-art result [30, 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 a novel analysis for the centralized UCB algorithm in markets satisfying α-condition and derive an improved O(N log T /∆ 2 N + K log T /∆) regret upper bound. One significant future direction is to investigate the optimality of algorithms. Although the dependence on N, K, T in Theorem 6.2 matches the lower bound, the definition of ∆ differs. It remains unclear how the upper bound changes with the same ∆. Furthermore, since the lower bound provided by [27] applies only to special markets, and the learning problem in general markets is more challenging due to the complex preference structure, determining whether an algorithm can perform better in general markets is still an open problem.A Proof of Theorem 4.1Define F = ∃1 ≤ t ≤ T, i ∈ [N ], j ∈ [K] : |μ i,j (t) -µ i,j | > 6 log T Ti,j (t)as the failure event that 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.Reg i (t) =E T t=1 µ i,m * i -X i (t) ≤E T t=1 µ i,m * i -X i (t) |⌝F + P (F) • T • µ i,m * i ≤E   T t=1 aj 1 Āi (t) = a j • ∆ i,m * i ,j |⌝F   + E T t=1 1 Āi (t) = ∅ • µ i,m * i |⌝F + P (F) • T • µ i,m * i ≤96N 2 log T /∆ 2 + 96K log T /∆ + 192N 2 log T /∆ 2 + 2N K (1) =O N 2 log T /∆ 2 + K log T /∆ .where Eq. ( 1) holds based on Lemma A.1, A.2, and A.4.Lemma A.1.E   T t=1 aj 1 Āi (t) = a j • ∆ i,m * i ,j |⌝F   ≤ 96N 2 log T /∆ 2 + 96K log T /∆ .Proof. Recall that player p i would update the available set A i when other players p i ′ sets E i ′ = False and π A i ′ ,i ′ > π A i ′ ,i as Line 14. Denote t s as the round index when this operation happens for the s-th time. Without loss of generality, let t 0 = 1.Recall that at a high level, each time another player p i ′ sets E i ′ as False, it means that p i ′ 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 AOGS algorithm is an online version of GS and the s ′ -th time player p i ′ sets E i ′ as False is equivalent to that p i ′ proposes its s ′ -th most preferred arm in the offline GS. According to Lemma A.3, at most N -1 arms are proposed by all players before reaching stability. Thus for player p i , the operation in Line 14 would happen for at most N -1 times.Recall that for each s, during time t s to t s+1 , player p i would explore all available arms in a roundrobin manner, eliminate 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 s as the set of the remaining N arms that p i explored in A i in a round-robin manner until condition Line 9 is satisfied, D s as the set of arms that p i eliminated due to condition Line 6, and j s as the arm that p i focuses from the time it sets E i as False to time t s+1 -1. Then it holds thatEQUATIONwhere Eq. ( 2) is due to that, based on Lemma A.6 and the offline GS algorithm, the arm j s before GS stops would be better than m * i , thus the regret caused by selecting these arms is less than 0. For the first term in Eq. ( 2), we haveEQUATION)where Eq. ( 4) is due to Lemma A.5, Eq. ( 5) holds since R s 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 a j and s ∈ {0, ..., N -1}, denote T i,j,s as the value of T i,j at the end of the round t s+1 -1. For s ≥ 1 and arm a j ∈ D s , if T i,j,s-1 ≤ 96 log T /∆ 2 i,js-1,j , it must hold that T i,j,s := s ′ ≤s (T i,j,s ′ -T i,j,s ′ -1 ) ≤ 96 log T /∆ 2 i,js,j to ensure arm a j is eliminated from A i at step s based on Lemma A.5. On the other hand, if T i,j,s-1 > 96 log T /∆ 2 i,js-1,j , based on Lemma A.5, it holds that T i,j,s -T i,j,s-1 ≤ 96 log T /∆ 2 i,js,j -96 log T /∆ 2 i,js-1,j when a j is eliminated. For any arm a j , denote s j,1 := max 0≤s≤N -1 s : T i,j,s ≤ 96 log T /∆ 2 i,js,j as the last step when the number of observation times on a j is less than that threshold. Then the second term in Eq. ( 2) satisfiesE   N -1 s=0 ts+1-1 t=ts aj ∈Ds 1 Āi (t) = a j • ∆ i,m * i ,j |⌝F   =E   aj ∈K s:aj ∈Ds ts+1-1 t=ts 1 Āi (t) = a j • ∆ i,m * i ,j |⌝F   =E   aj ∈K s:aj ∈Ds (T i,j,s -T i,j,s-1 ) • ∆ i,m * i ,j |⌝F   =E   aj ∈K   s:aj ∈Ds,s≤sj,1(T i,j,s -T i,j,s-1 ) + s:aj ∈Ds,s>sj,1(T i,j,s -T i,j,s-1 )   • ∆ i,m * i ,j |⌝F   ≤E   aj ∈K   T i,j,sj,1 + s:aj ∈Ds,s>sj,1 (T i,j,s -T i,j,s-1 )   • ∆ i,m * i ,j |⌝F   ≤ aj ∈K   96 log T ∆ 2 i,js j,1 ,j + s:aj ∈Ds,s>sj,1 96 log T /∆ 2 i,js,j -96 log T /∆ 2 i,js-1,j   • ∆ i,m * i ,j ≤ aj ∈K 96 log T ∆ 2 i,m * i ,j • ∆ i,m * i ,j ≤ 96K log T /∆ ,where the second last line is due to the definition of s j,1 and the above analysis.Above all,E   T t=1 aj 1 Āi (t) = a j • ∆ i,m * i ,j |⌝F   ≤ Eq. (2) ≤ 96N 2 log T /∆ 2 + 96K log T /∆ . Lemma A.2. E T t=1 1 Āi (t) = ∅ • µ i,m * i |⌝F ≤ 192N 2 log T /∆ 2 .Proof. Based on the AOGS algorithm, when E i = True, the central platform would assign arms in A i to player p i in a round-robin manner. Since the number of arms |∪ i:Ei=True A i | to be explored is larger than the number i 1{E i = True} of players with E i = 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 i = False.Denote t s and t s as the round index when p i sets E i as False for the s-th time and as True for the s + 1-th time, respectively. Recall that when E i = False, p i will always select arm A i . Here we use j s to represent the arm that is selected by p i from time t s to t s .Further, recall that in the AOGS algorithm, each time an arm is added into D i (Line 13), the eliminated arms may be contained into A i 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 N times. For any player p i ′ , denote t i ′ ,r as the round index when p i ′ adds arms to D i ′ (Line 13) for r-th time. Then{t i ′ ,r } r∈[N ] further divide [t s , t s ] s∈[N ] into at most2N slices. We use t ′ s , t ′ s to represent the start round and end round index of the s-th slice, where s ∈ [2N ]. Based on Lemma A.5, p i ′ and p i would select the same arm for at most 96 log T /∆ 2 times within each slice.Then the regret satisfiesE T t=1 1 Āi (t) = ∅ • µ i,m * i |⌝F ≤ E   N s=1 ts t=t s 1 Āi (t) = ∅ • µ i,m * i |⌝F   = E   N s=1 ts t=t s 1 Āi (t) = ∅, A i (t) = j s • µ i,m * i |⌝F   ≤ E   i ′ ̸ =i N s=1 ts t=t s 1{A i (t) = A i ′ (t) = j s } • µ i,m * i |⌝F   ≤ E   i ′ ̸ =i 2N s=1 t ′ s t=t ′ s 1{A i (t) = A i ′ (t)} • µ i,m * i |⌝F   ≤ i ′ ̸ =i 2N s=1 96 log T /∆ 2 • µ i,m * i ≤ 192N 2 log T /∆ 2 .Lemma A.3. In the offline GS algorithm, at most N -1 arms have been proposed by players before the algorithm stops.Proof. Based on the offline GS algorithm, once an arm is proposed, it has a temporary player. By contradiction, once N arms have been proposed, it means that N players are occupied. In this case, each player has a partner and the algorithm stops.Lemma A.4.P (F) ≤ 2N K/T .Proof.P (F) = P ∃1 ≤ t ≤ T, i ∈ [N ], j ∈ [K] : |μ i,j (t) -µ i,j | > 6 log T T i,j (t) ≤ T t=1 i∈[N ] j∈[K] P |μ i,j (t) -µ i,j | > 6 log T T i,j (t) ≤ T t=1 i∈[N ] j∈[K] t s=1 P T i,j (t) = s, |μ i,j (t) -µ i,j | > 6 log T s ≤ T t=1 i∈[N ] j∈[K] t • 2 exp(-3 ln T ) ≤ 2N K/T ,where the second last inequality is due to Lemma B.1.Lemma A.5. For any player p i , let Ti = 96 log T /∆ 2 . For any two arms j, j ′ with µ i,j > µ i,j ′ andσ i (a j ) ∈ [1, σ i (m * i )], if T i (t) := min {T i,j (t), T i,j ′ (t)} > Ti , we have UCB i,j ′ (t) < LCB i,j (t) conditioned on ⌝F.Proof. By contradiction, suppose UCB i,j ′ (t) ≥ LCB i,j (t). According to ⌝F and the definition of LCB and UCB, we haveµ i,j -2 6 log T T i (t) ≤ LCB i,j (t) ≤ UCB i,j ′ (t) ≤ µ i,j ′ + 2 6 log T T i (t) .We can then conclude ∆ i,j,j ′ = µ i,j -µ i,j ′ ≤ 4 6 log T Ti(t) , which implies thatT i (t) ≤ 96 log T ∆ 2 i,j,j ′ ≤ 96 log T ∆ 2 .This contradicts the fact that T i (t) > Ti . Lemma A.6. Conditioned on ⌝F, at any time t, UCB i,j (t) < LCB i,j ′ (t) implies µ i,j < µ i,j ′ .Proof. According to the definition of LCB and UCB, we haveLCB i,j (t) = μi,j (t) - 6 log T T i,j (t) ≤ µ i,j ≤ μi,j (t) + 6 log T T i,j (t) = UCB i,j (t) ,where two inequalities comes from ⌝F. Thus if UCB i,j (t) < LCB i,j ′ (t), there would beµ i,j ≤ UCB i,j (t) < LCB i,j ′ (t) ≤ µ i,j ′ .The lemma can thus be proved.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] 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. 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 of compute required for each of the individual experimental runs as well as 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to 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 not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets• According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we 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. 
 
 Appendix: Lemma B.1. (Corollary 5.5 in Lattimore and Szepesvári [18] ) Assume that X 1 , X 2 , . . . , X n are independent, σ-subgaussian random variables centered around µ. Then for any ε > 0,P 1 n n i=1 X i ≥ µ + ε ≤ exp - nε 2 2σ 2 , P 1 n n i=1 X i ≤ µ -ε ≤ exp - nε 2 2σ 2 .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 N 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 at the same round. By contradiction, suppose when player p i assigns its j-th arm, there is no available round to make this assignment due to conflicting constraints. Given that player p i is currently assigning the j-th arm, it implies that there are 2N -j +1 rounds where no arm is assigned to player p i . Since none of these rounds satisfy the conflict constraint, it means that the previous i -1 players assigned arm j in these 2N -j + 1 rounds. This creates a contradiction since the first i -1 players can only occupy i -1 rounds when selecting arm j, where i -1 < 2N -j + 1 with i ≤ N, j ≤ N .C Proof of Theorem 6.2In this section, we analyze the regret of the centralized-UCB algorithm under α-condition. Recall thatF = ∃1 ≤ t ≤ T, i ∈ [N ], j ∈ [K] : |μ i,j (t) -µ i,j | > 6 log T Ti,j (t)is the failure event that the estimated reward is far from the expected reward at some time and some player-arm pair.For any player p i with i ∈ [N ], we know that its stable arm is a i under α-condition. Thus its regret can be decomposed asReg i (T ) ≤ E   k:µ i,k <µi,i ∆ i,i,k T t=1 1 Āi (t) = k, ⌝F   + T • P (F) .The first term is the number of selections for sub-optimal arms. The second term is the regret caused by the bad events.For the arm a k such that it is sub-optimal for player p i , i.e., µ i,k < µ i,i , it will be selected because the preference for arm a k of player p i is estimated higher than its stable matched arm a i , or player p i is rejected by arm a k in the GS algorithm. Note that under α-condition, there is a right orderQ i ′ = i ∈ [N ] r for player p i , such that ∀i ′ < i ′′ ≤ N, Q i ′′ ∈ [N ] r :π q i ′ ,Q i ′ > π q i ′ ,Q i ′′ , which means arm a q i ′ = a i can only prefer players p Q1 , p Q2 , • • • , p Q i ′ -1 than player p Q i ′ = p i . DenoteThe right-order mapping for α-condition for player p i is lr(i) so that Q lr(i) = i with Q i defined in Definition 6.1, and lr(i) ≤ N . For player p i , denote G t,i := {∀1 ≤ i ′ ≤ lr(i) -1, ĀQ i ′ (t) ̸ = i} as the event all players preferred by arm a i do not select p i at time t. Then the number of selections for sub-optimal arm a k can be decomposed asE T t=1 1 Āi (t) = k, ⌝F =E T t=1 1 Āi (t) = k, G t,i , ⌝F + E T t=1 1 Āi (t) = k, ⌝G t,i , ⌝F ≤E T t=1 1 Āi (t) = k, UCB i,k (t) > UCB i,i (t), ⌝F + E T t=1 1 Āi (t) = k, ⌝G t,i , ⌝F ≤ 24 log T ∆ 2 i,i,k + E T t=1 1 Āi (t) = k, ⌝G t,i , ⌝F .The last inequality is from Lemma C.1.For the second term in the RHS of the last inequality, E T t=1 1 Āi (t) = k, ⌝G t,i , ⌝F , we can sum over all sub-optimal arms and it turns out to beE k T t=1 1 Āi (t) = k, ⌝G t,i , ⌝F ≤E T t=1 1{⌝G t,i , ⌝F} ≤E   lr(i)-1 i ′ =1 T t=1 1 ĀQ i ′ (t) = i, ⌝F   ≤ lr(i)-1 u ′ =1 lr(i) u ′′ =u ′ +1 24 log T ∆ 2 Q u ′ ,q u ′ ,q u ′′ ≤ lr(i)-1 u ′ =1 lr(i)-u ′ k=1 24 log T (k∆ N ) 2 ≤ (lr(i) -1)   lr(i)-u ′ k=1 1 k 2   24 log T ∆ 2 N ≤ (lr(i) -1) 5π 2 log T ∆ 2 N ,where the third inequity is from the Lemma C.2. The fourth inequality is from the definition of ∆ N .Above all, the stable regret of player i can be bounded byReg i (T ) ≤E   k:µ i,k <µi,i ∆ i,i,k T t=1 1 Āi (t) = k, ⌝F   + T • P (F) ≤ k:µ i,k <µi,i ∆ i,i,k 24 log T ∆ 2 i,i,k + ∆ i,i,k (lr(i) -1) 5π 2 log T ∆ 2 N + 2N K ≤ 24K log T ∆ + (lr(i) -1) 5π 2 log T ∆ 2 N + 2N K ≤O K log T ∆ + N log T ∆ 2 N ,where the second inequality is based on Lemma A.4.Lemma C.1. Conditioned on ⌝F, under the traditional single-player UCB algorithm with single player p i , the expected number of times at which the UCB index of arm a j ′ exceeds that of the better arm a j , is at most 24 log(T )/∆ 2 i,j,j ′ by round T .Proof. Conditioned on ⌝F, for any i, j, t we have,EQUATION)Recall that the UCB index is:EQUATION)The event that arm a j ′ is successfully selected for player p i rather than the better arm a j at time t implies that UCB i,j ′ (t) > UCB i,j (t) .Hence,µ i,j ′ + 2 6 log(T ) T i,j ′ (t -1) (6a) > μi,j ′ (t -1) + 6 log(T ) T i,j ′ (t -1) (6c)> μi,j (t -1) + 6 log(T ) T i,j (t -1)> µ i,j -6 log(T ) T i,j (t -1) + 6 log(T ) T i,j (t -1)= µ i,j , which leads toT i,j ′ (t -1) < 24 log(T ) ∆ 2 i,j,j ′, where ∆ i,j,j ′ is the reward difference between the µ i,j ′ and µ i,j .Lemma C.2. For any player p i with right order Q lr(i) , the following inequality holds:E   lr(i)-1 i ′ =1 T t=1 1 ĀQ i ′ (t) = i, ⌝F   ≤E   lr(i)-1 u ′ =1 lr(i) u ′′ =u ′ +1 T t=1 1 ĀQ u ′ (t) = q u ′′ , G t,u ′ , ⌝F   ≤ lr(i)-1 u ′ =1 lr(i) u ′′ =u ′ +1 24 log T ∆ 2 Q u ′ ,q u ′ ,q u ′′ .Proof. For player p i with right order Q lr(i) , from α-condition we have that its stable matched arm a i may prefer p Q1 , p Q2 , • • • , p Q lr(i)-1 than player p Q lr(i) . For any i ′ < lr(i), we know that the number of times player p Q i ′ selects arm a i is decomposed as byE T t=1 1 ĀQ i ′ (t) = i, ⌝F =E T t=1 1 ĀQ i ′ (t) = i, G t,i ′ , ⌝F + E T t=1 1 ĀQ i ′ (t) = i, ⌝G t,i ′ , ⌝F .The event ⌝G t,i ′ implies that there exists another player p Q i ′′ with i ′′ < i ′ that selects the stable arm of p Q i ′ . This leads to a recursion form. But it is easy to verify that every event ⌝G t,i ′ happens only when there exists two players pQ u ′ , p Q u ′′ with u ′ < u ′′ ≤ lr(i ′ ), such that player p Q u ′ explores the stable matched arm a q u ′′ of p Q u ′′ , i.e., p Q u ′ selects a q u ′′ conditioned on G t,u ′ . And thus it holds that E   lr(i)-1 i ′ =1 T t=1 1 ĀQ i ′ (t) = i, ⌝F   ≤E   lr(i)-1 u ′ =1 lr(i) u ′′ =u ′ +1 T t=1 1 ĀQ u ′ (t) = q u ′′ , G t,u ′ , ⌝F   ≤ lr(i)-1 u ′ =1 lr(i) u ′′ =u ′ +1 24 log T ∆ 2 Q u ′ ,q u ′ ,q u ′′ . (d)We recognize that reproducibility may be tricky in some cases, in which case authors 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 be possible for other researchers to have some path to reproducing or verifying the results.Justification: The research conducted in the paper complies with NeurIPS 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 a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: There is no societal impact of the work performed.Guidelines:• The answer NA means that there is 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to 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 for 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 is 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 mitigation 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). 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: The contributions are rather incremental. Details are below:
- 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. 
- 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.
- 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.
questions: questions: Please see the questions in the Weakness section above. One more question below:
- 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: 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)$.
- The theory in this paper concerns a practical setting that might have some potential societal impacts, none of which is significant.
paper_summary: paper_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.
strength_weakness: strength_weakness: The combination of bandits with matching markets is wired. Is there any evidence that practitioners would like to use bandits for learning in markets?
questions: questions: 1. The key novelty in the paper is unclear. What are the new techniques developed in the paper for proving the upper bound? 

2. Do you have any empirical markets that could use the proposed algorithms?

3. How to generalize the techniques to decentralized markets?
limitations: 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?
paper_summary: paper_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.
strength_weakness: strength_weakness: Although the dependence on $N$, $K$, $T$ is optimal, the main weakness lies in the difference of defining the instance-dependent gap $\Delta$.
questions: 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: limitations: N/A
paper_summary: paper_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$.
strength_weakness: strength_weakness: 1. Without $\alpha$-condition, the upper bound has $N^2$ instead of $N$, which may not be tight with respect to $N$.
2. Even though they provide a new algorithm, it may be hard to see the technical novelty.
questions: questions: Without $\alpha$-condition, is the lower bound linear with respect to $N$?
limitations: limitations: The authors have discussed the limitations in the conclusion.

Comments: title: Thank you for your response.
comment: We thank the reviewer’s consideration in raising the score. We will include the discussion in the next version of the paper.
Overall, the novel approach is interesting because it achieves an $N^2$ dependency rather than $K$ in the setting without the alpha condition. However, the achieved regret bound may not be optimal, or the regret lower bound may not be tight enough. Also, I believe the technical novelty may not be significant enough. Therefore, I have decided to maintain my score.
This is good! I will raise my score. I encourage the authors to add this lower bound response to the paper.
We thank the reviewer for taking the time to read our response. 

Regarding the lower bound, we want to discuss the instance construction intuition from the view of the total number of rounds required to reach the player-optimal stable matching. In the instance of Sankararaman et al. [27], the player-optimal stable arm of each player is exactly their first ranked arm. So it cannot distinguish between their $\mathrm{gap}_1$ and our $\mathrm{gap}_4$. To derive a lower bound depending on $\mathrm{gap}_4$, we hope to find an example such that $\sigma_i(m_i^*)\neq 1$ and any change in the rankings within the first $\sigma_i(m_i^*)+1$ positions would result in a different player-optimal stable matching. 
For example, in the following market, the player optimal stable matching is $\{ (p_1,a_4), (p_2,a_1), (p_3,a_2), (p_4,a_3) \}$. However, if we adjust the $p_1$'s preference ranking as $a_1>a_2>a_4>a_3>a_5$, the player-optimal stable matching under the changed preferences is $\{(p_1, a_4), (p_2, a_3), (p_3, a_1), (p_4,a_2)\}$, which is not stable in the original environment as $p_1$ and $a_3$ form a blocking pair. Although $\mathrm{gap}_1$ (the difference between $a_4$ and $a_5$) of $p_1$ may have already been identified in this scenario, it is insufficient to achieve the optimal stable matching. That's to say, the player $p_i$ must identify the first $\sigma_i(m_i^*)+1$ gaps to find the true optimal stable matching. And the hardness would depend on our newly defined $\mathrm{gap}_4$. To identify these gaps, each player $p_i$ must select the first $\sigma_i(m_i^*)+1$ arms for sufficient times. We hope to find an instance in which these arms prefer other players than this player, such as arm $a_1$ preferring others over $p_1$, forcing $p_1$ to wait for $\Omega(N\log T/\Delta^2)$ rounds for the opportunity to select $a_1$. 



$p_1: a_1>a_2>a_3>a_4>a_5,$

$p_2: a_2>a_3>a_1>a_4>a_5,$

$p_3: a_3>a_1>a_2>a_4>a_5,$

$p_4: a_1>a_2>a_3>a_4>a_5;$

$a_1: p_2>p_3>p_4>p_1,$

$a_2: p_3>p_4>p_1>p_2,$

$a_3: p_4>p_1>p_2>p_3,$

$a_4: p_1>p_2>p_3>p_4,$

$a_5: p_1>p_2>p_3>p_4.$
Thanks! I've read your response and I've decided to maintain my scores.
Thanks for the clarification, especially on the double-sided uncertainty part. However, while the paper and the rebuttal repeatedly claim that proving a lower bound should require a separate paper, no clear explanation has been given so far. Can the authors clarify exactly what are the difficulties in adapting the lower bound construction in Sankararaman et al. to your new gap? I am not asking for a formal proof, just high-level ideas on why a lower bound for your gap would require a fundamentally new construction, and what a difficult instance looks like in your setting.