Matching in Multi-arm Bandit with Collision
Authors: Yirui Zhang
Siwei Wang
Zhixuan Fang
Venue: NeurIPS 2022 Accept (2022)

Abstract: In this paper, we consider the matching of multi-agent multi-armed bandit problem, i.e., while agents prefer arms with higher expected reward, arms also have preferences on agents. In such case, agents pulling the same arm may encounter collisions, which leads to a reward of zero.
For this problem, we design a specific communication protocol which uses deliberate collision to transmit information among agents, and propose a layer-based algorithm that helps establish optimal stable matching between agents and arms. With this subtle communication protocol, our algorithm achieves a state-of-the-art $O(\log T)$ regret in the decentralized matching market, and outperforms existing baselines in experimental results. 

Matching in Multi-arm Bandit with Collision
Yirui Zhang', Siwei Wang", Zhixuan Fang!.3. 1.3
IIS, Tsinghua University Microsoft Research Shanghai Qi Zhi Institute zhangyr220mails tsinghua, edu. cn
si siveivang@mi crosoft. com zf zfang@mail, tsinghua. edu.
Abstract
In this paper, we consider the matching of multi-agent multi-armed bandit prob- lem, i.e., while agents prefer arms with higher expected reward, arms also have preferences on agents. In such case, agents pulling the same arm may encounter collisions, which leads a reward of zero. For this problem, we design specific communication protocol which uses deliberate collision to transmit information among agents, and propose layer-based algorithm that helps establish optimal stable matching between agents and arms. With this subtle communication proto- col, our algorithm achieves a saate-of-the-aae Olog T) regret in the decentralized matching market, and outperforms existing baselines in experimental results.
1 Introduction
Decentralized matching between two sides with preferences (e.g., supply and demand) is the core process in many online marketplaces, such passengers and riders on ridesharing platforms (e.g., Uber), or customers and free-lancers in online labor markets (e.g.. TaskRabbit), etc. Since practical scenarios, participants in the online market obtain information mainly through their experiences, a crucial question arises on how to achieve an optimal stable matching among these competing agents, through learning from the iterative interactions with the other side, and, at what cost?
Learning the uncertainty in two-sided markets has been studied from various angles, e.g., the contextual bandit scenario (88 77, the economic perspective []]. and the stability and faimeess in the centralized matching market [3]. Following a strand of recent literature (e.g., 2),, we model the problem as a multi-agent multi-arm bandit problem. Specifically, in the decentralized matching market with multi-armed bandits, we consider a set M of M agents, and a set A K arms, with M K. Every agent knows M, K, and the time horizon T. Each arm has its fixed preference towards agents, which unknown to all the agents. The notation i > j means that arm prefers agent rather than agent j.
At each time f, every agent) j pulls an arm (t) A. When multiple agents pull the same arm at time t, collision occurs this arm. Only the agent that the prefers most, e.g., will win the competition. The winning agent does not encounter collision, and obtains a stochastic reward (t) from the arm, which is sampled from a unknown fixed distribution Fşx with mean Uzk- In the meantime, the other agents that pull arm will encounter collision and receive zero reward, i.., (t) 0. Same with the previous works, two among all agents A A minme M min,, [mmn Una is positive. We let C₃(() represent the collision indicator for agent j at time f, i.e., Ct({) = denotes that agent j encounters collision time step and (l) = 0 otherwise. In model, each agent j is informed of her own collision signal Cj (t) and reward Ry (t) after her pull. At each time step t, every agent j pulls an arm (t) only according to her observed history (T) (T) (r)))
assume that the minimal gap of utility between
"Conresponding author: Zhixuan Fang (zfang maiin@@mail.ee mai. .si.ggua..du...c.)
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1. Comparison between our work and prior results.
Algorithms
Model
Regret (M 1)K log T/A²)
UCB-D3
globally ranked agent
UCB-D4
uniqueness consistency
O(M [ 1)K log T/
CA-UCB
partially decentralized O(expl [M' M log" 2 T/A²) (pessimal regret)
Phased-ETC
general model
O(M K log 1 T + exp(1/A²))
ML-ETC (our result)
general model
O(MK T/
Now we introduce the optimal stable matching to give a suitable notion of regret (6) While arms have preferences towards agents, an agent j always prefers the arm with higher utility, i.e., the arm with higher újk- stable matching. there does not exists any "agent, arm" pair such that each one prefer each other than the current matched partner.
If there exists at least one stable matching where agent j is matched with arm k; we call arm k an attainable arm to agent j. We denote the set of attainable arms of agent j by Astable (j). The optimal Uzk. i.c., the arm with highest mean to agent j in (stable()). As shown in previous study (e.g.166), there exists a unique stable matching where every agent matches with her optimal stable arm. The optimal regret is defined as the expected reward gap between the ideal reward according to the optimal stable matching and the achieved reward, i.e.,
stable arm for agent; j is az aegmaa
M
T
M
(T) = Σ
E
(1
C,(t))ugz,()
jml
1.1 Our Main Contribution
Following the explore-then-comnil (ETC) framework [T 9 12,, we propose an algorithm called ML-ETC. Specifically, all the agents will first explore arms and then commit to their optimal stable arms in terms of empirical means.
The key point in ML-ETC is that we allow agents to communicate through deliberately designed collisions, so that they can switch from exploration to exploitation timely. Previous works in multi- agent multi-arm bandit (e.g.. 4 [5 14 3) have discussed the use of deliberate collisions among agents for communication, but they fail in the case of matching market with multi- aamei- bandit. This is because when arms have preferences communicate with each other. For example, consider an extreme case where agent j is ranked first on all arms. In this case, agent j will never encounter collision, let alone receiving information from others through deliberate collisions. To solve this problem, we show that under such circumstance, the agent who cannot transmit information to agent will never be able to influence the stable matching of agent j. which means that there is nearly no difference whether they exist from agent j's point of view. Therefore, an agent could end the exploration once all the agents who can communicate with her have high confidence of their preference about arms. After that, we can apply GS (66) to make sure that each agent obtains her optimal stable arm within limited time steps and then commits to that optimal stable arm.
agents, it may be impossible for every agent to
Based on these properties, we show that our subtle multi-layered algorithm ML-ETC achieves state-of tf-tte--rtt regret upper bound of Oloog T) in the decentralized setting, which is better than the existing results, including the O(log L+e T') regret bound for Phased-ETC [2] and the Oloog T) regret bound for CA-UCB in [10]. Please see Table for the summary of comparison with previous results, and Section 1.2 for detailed discussions.
1.2 Related Work
The study of matching in multi-armed bandit is initiated by the recent work 9 In this work, the authors introduce the model and design both centralized ETC policy and a decentralized ETC policy. The centralized ETC has good performance but requires a central organizer to proceed matching, which may not exist in many real-world applications. The decentralized ETC, on the other hand, may cause very high regret when the minimal gap A is unknown to the agents, which is also common case in reality. Thereafter, there are two major strands of literature on this problem.

---

A strand of literature studies the special case where the arms' preferences satisfy some special conditions. For example, the work of [T3] assumes that the agents are globally ranked, which means all arms have the same preference toward agents, and proposes the UCB-D3 algorithm. Also, [ designs the UCB-D4 algorithm based on the assumption of uniqueness consistency on agents and arms. The assumption of uniqueness consistency requires that there exists a unique stable matching for all agents and arms, and the matching remains to be the unique stable matching when arbitrary matched pairs leave the system.
The other strand of literature focuses on the general case of unrestricted arm preferences. In [0]] the authors design the CA-UCB algorithm, based on extra information that all agents can observe the winning agent for each arm at the end of each round. CA-UCB achieves an Ollog T) pessimal regret (a less strict notion of regret). Within this strand of work, the work [2] is the most related to our work, which also analyzes the optimal regret in the general market. Beyond the aforementioned UCB-D4, the authors also design a phased based algorithm Phased-ETC (for general arm preference) and achieves the regret bound of Oloog+**) T), with have no communication at all. Therefore, agents keeps exploring all the arms and have no idea of others' estimations of the arms. In addition to the Ollog!+*7 7) factor, Phased-ETC also has a huge regret term (an exponential term of exp( )) because of the possibility of the exploration failure, and this will be explained in detail in our experimental section. Compared to [2]. we design subtle communication protocol to allow agents to end the exploration timely while they have high confidence of the arms' order according to the empirical means. This allows us to obtain a state-of-the-ar Ollog 7) regret upper bound without any potential exponential terms.
O. However, in their algorithm, agents
2
The ML-ETC Algorithm
In this section, we introduce Multi-Layer Explore Then Commit (ML-ETC) algorithm, which is described in detail in Algorithm I
and achieves Ollog T)) regret.
2.1 Brief Introduction
The algorithm can be briefly divided into 3 phases: the initialization phase, the multi-layered exploration and communication phase, and the exploitation phase.
In the initialization phase, all agents will be assigned an index and receive some information of the arm preferences. After the initialization phase, agents form an underlying hierarchical structure with respect to their communication capability through collision. Then, the algorithm proceeds to the multi-layered exploration and communication phase to match agents of each layer with arms. At each layer, the algorithm keeps iterating between exploration and communication. During exploration, every agent will explore the arms orthogonally (according her index in order avoid collision) and will estimate the expected rewards of all the remaining arms. During communication, every agent checks whether her estimations are accurate enough, and transmit this information all the agents that can hear from her. Only when some of the agents are able to successfully find their empirical optimal stable arms, will they leave the multi-layered exploration and communication phase, and start their exploitation phase. The remaining agents will enter the next layer, until all the agents find out their empirical optimal stable arms. In the exploitation phase, every agent continuously pulls her empirical optimal stable arm.
2.2 Communication Protocol
In this subsection, will introduce the core of ML-ETC, the communication protocol used in both the initialization phase and the multi-layered exploration and communication phase.
Suppose agent (i.e., the transmitter) wants to convey binary sequence to agent j (i.e., the receiver). Let |s] denote the length of the binary sequence, i.e., s E {0. 1}1s), We design a procedure com(i. j, k s) to allow such communication, where agent i and agent j will create deliberate colli- sions on arm k to deliver the bits. The communication procedure will last for |s] time steps, during which other agents are serving as bystanders. We specify the actions of all agents in com(i. k, as follows.
3

---

Transmitter i: During the procedure com k s), at the E-th time step, if s(() (the f-th digit in s) 1. then the transmitter will pull arm k. Otherwise, she pulls an arbitrary arm k' * k at the time step.
j. s), the receiver j deliberately pulls arm & for all |s] time steps receive information, and the resulting collision indicators (2()) during these time steps are the digits of the binary sequence 8.
Receiver j: During com(i.j, k.
During com(i. k. s), all agent m * i.j are bystanders. Each bystander chooses an arbitrary arm k' * l to pull for each time step within all |s| time steps of the procedure, to avoid interfering the bit transmission between agent i and j on arm k:
Bystanders:
In this paper, agents may transmit two types of information: the index of an agent, a binary signal of whether the exploration success or not. It is easy to check that the communication of these two types of information with length [log M] and 1.
However, com(i, j. k, s) does not always succeed. Only if > j. i.e., when agent wins against during the competition on arm k, the collision indicators (t)'s form the sequence s. Otherwise, (l) always equals to 0 and therefore com(i. (i,j, k; is not effective. Based on this observation, we define the communication graph as follows.
Definition 1. A communication graph A), where M is the set of agents and A is the set of arms, is a directed graph with each agent in M one vertex. There is directed edge from vertex i to vertex j in G if and only if there exists at least one arm k E A such that >> j.
Based on Definition 1 if there exists at least one edge from i to j in graph G(M, A), it means that agent i can transmit information to agent j effectively (through the proper arm). The communication graph captures the communication availability among agents. We will further categorize agents with similar communication "capability" as follow.
Definition 2. An outer closed circle is a non-empty subset of vertexes in a directed graph G, i.e. M C V(G), which satisfies that: i) M is connected; ii) there is no entry edge from vertices in V(G) \ M to any vertex in M.
From Definition 2. we can easily see that the agents in an outer closed circle of the communication graph G(M,, A)) can exchange (transmit and receive) information among each other. However, agents in the outer closed circle can only transmit information to agents outside, but are unable to receive information from them. The following proposition further shows that there always exists exactly one outer closed circle in a communication graph G(M,A).
Proposition If there exists at least one edge between any two vertices in directed graph G, there exists a unique outer closed circle in G.
Due to space limit, the details of the proof of Proposition I iss deferred to Appendix in the supplemen- tary material.
Remark: Multi-layer separation of agents. The result of Proposition is critical. With this result, we can uniquely determine a group of agents with bidirectional communication capability within the group, but unidirectional transmission to the outside. Thus, by iteratively extracting outer closed circle from the agent set M, we are naturally constructing a hicrarchical structure within agents. In such structure, agents can transmit information only agents of the same level and below, while receiving information from agents of the same level and higher (see Section 2.4 for detailed discussions).
2.3 Initialization Phase
The initialization phase (lines 1-4 in Algorithm I consists of two procedures: indez_ aasegggmnsttt and in information _access.cc.ssss Through procedure index_ aaddx_assiignentt each agent is assigned an index, and obtains some information about each arm's preferences. Then, the procedure in cermatiionaccess allows agents to share their obtained preference rankings on all arms.
The procedure inder_ assignment (see details in Appendix) consists of K rounds with M time steps each, lasting a total M K time steps. In round 1, every agent starts with pulling arm 1. an agent does not encounter collision at time step index ý1 and starts to pull arm 2. This means that the index of an agent is her ranking on arm 1. Similarly, in round & = 2, 3, ..., K, if an agent does not encounter collision on arm & at time step
ji (i E [1, M). the agent is assigned with

---

Algorithm ML-ETC Algorithm
Require: K, T,
1: a Initialization phase:
2: (j,83) inder_assiigment/// assignment(K, M) #assign index to "this agent"
3: Mp) t foromtiion, sanpa_cces((ss (K,, M,j.8;)
4: #8, is the arm preference known agent J. Mp is the of layer leaders in layer p
5: a Multi-layered exploration and communication phase:
6: B(G) # [ denotes whether agent j enter the exploitation phase
7: while EG) == do
8: Communication:
9: if' j E MM then #Agent j is a layer leader
whether_success _uciess_s + whether [u)
11:
#whether j achieves an accurate estimation for all remaining arms Ap
#Ap is the (opt arm, E()) +
remaining arms layer p. Ry the set of remaining agents in layer p
13:
Sj. Ap. Mp. whether success, whether_success, M) #if the layer leaders succeed, then E(j) -- and j will enter the exploitation phase #opl_arm is the empirical optimal stable arm of agent end
15:
17:
if j & MM then #Agent j is layer follower
18:
Ap. Mp, Rp) + tayer_followe (j. sj. Ap. Rp Mp. M,p)
19:
#if all the layer leaders succeed, then p + + 1 and agent will enter the next layer
20:
end
21:
Exploration:
22:
Let be the order of agent j in remaining agent set Rp. t-
23:
for Apl [log 7 time steps do
24:
<- Ap
25:
i --i+1 mod [Apl
26:
Pull arm æ, update the empirical means ((j) = (t)())))))))..)) and matching
times NG) = (ye()),.)
28:
end for
end while
30:
<1 Exploitation phase:
Pull opt opt_arm arm until
t 1)M + ju. she knows that her ranking on is ja, and starts keep pulling arm k: + 1 mod K, so that the other agents can continue to confirm their rankings on arm k. In this way, after MK time steps, every agent knows her ranking on all the arms.
Then in the procedure of in in formation access (given in Appendix), there will be M rounds of information exchange. In each round, we list all the "agent, agent, arm" tuples, i.e.. {(i. k)), Vi, M, E A, and conduct communication procedure (i, k, 8i) on all these tuples one by one according any publicly designated order, matter whether the communication is effective not. Here 8; represents agent i's updated knowledge about all rankings, e.g., 8; E 1,. M) K x. where the matrix element s.[n][[]] is the index of the agent that has the m-th ranking on arm n. If the index is unknown to agent i, 8; [m] is O. Each matrix element [n [m] is encoded in a binary sequence with length [log M for transmission.
After the initialization phase, every agent will receive an index and get part of the information about agents' rankings. Specifically, agent i receives information of the rankings of all the agents j such that there exists a path from j to in G(M,A), i..., agents of the same level as or higher.
2.4 Multi-layered exploration and communication phase
The multi-layered exploration and communication phase (lines 5-29 in Algorithm [ is driven by the layer categorization of agents. Recall Proposition I we can first identify unique subset of agents from M, called outer closed circle, in which agents can communicate with each other. At this stage, we call the system at "layer 1". Agents in the outer closed circle are called layer leaders of layer 1, the set of which is denoted Mi. Our algorithm will finish this stage by assigning each
5

---

agent in MM her empirical optimal stable matching arm. Thus, agents in Mi will leave this stage and directly jump to the exploitation phase. Those remaining agents and arms will enter the stage of layer 2 and start the identification of a new outer closed circle. The above process will keep repeating until all agents enter the exploitation phase.
In general, for each layer p = 1,, 2, 3... the system is in, we let R2 denote the set of all remaining agents, and Ap denote the set of all remaining arms (we have R, M and A A). Then according to Proposition D there exist a group of agents My. which form the outer closed circle of the communication graph ((Rp.AA)) We call the agents in MM layer leaders in this layer, while the remaining agents in Rp \ MM are called layer followers. Based on the properties of the outer closed circle, all the layer leaders can i) exchange information among each other, and ii) transmit information to all layer followers but not be able to receive information from them (via the remaining arms in Ap). Then, the goal in this layer is to let all the layer leaders find out their empirical optimal stable arm. The reason that we only care about layer leaders is because the communication from layer followers to layer leaders is not effective, and layer followers can not influence layer leaders (including their pull decisions, results and optimal stable arms).
To achieve this goal, at any layer, all remaining agents will conduct communication and exploration. They will first communicate with each other to check whether all the layer leaders have obtained an accurate estimation on the remaining arms. If the layer leaders have obtained accurate estimation on all remaining arms, then they will enter the exploitation phase, otherwise, they will conduct exploration for [pp[log 77 time steps. Specifically, for layer leader i, if for any two remaining arms m, n. either the lower confidence bound of üja is larger than the upper confidence bound of Ujm or the lower confidence bound of Uym is larger than the upper confidence bound of Ujn (i.e., with high probability, the order of empirical means is the same as the order of real means), then she can confidently differentiate these two arms. Thus, the agent has successfully obtained an estimation (or, sort) on all remaining arms that is accurate enough for her to enter the exploitation phase. In the communication, we let layer leaders reach a consensus on a global signal of whether all layer leaders have achieved a successful estimation on every remaining arm, and transmit this signal to all layer followers, while layer followers do not transmit anything. Since all the layer leaders can hear from each other, after the communication, they know the updated status of all layer leaders. If all layer leaders successfully sort the arms with confidence, they start to find out their empirical optimal stable-matchin arms (by conducting the GS GS_and_on ron__ammiie prr__nnfon formation procedure based on the Gale-Shapley algorithm), and then jump to the exploitation phase. Otherwise, all agents will start round of exploration, so that the agents with unsuccessful signal of exploration have the chance to achieve an accurate estimation successfully before the next communication. When all the layer leaders jump the exploitation phase, all the remaining agents (the layer followers in this layer) start to enter the next layer and learn the remaining arm set.
Note that at the beginning of layer p. remaining agent i is able to identify all layer leaders and layer followers by her own, based on the knowledge of Rp. Ap and her available information about the rankings from the initialization phase (See Appendix for detailed proof). Therefore, the above procedure can be done in a distributed manner. For simpler presentation, in the rest of this subsection, will first specify the exploration process, and then the communication process.
2.4.1 Exploration
Within one round of exploration layer p that lasts for [Apl T time steps, every agent in R, will explore every remaining arm in Ap orthogonally according to their index to avoid collision. Specifically, at the 7-th time step in this round of exploration, the j-th agent in R, will pull the (j ++ T mod (A,l)-th arm in Ay. Since [Apl > (Rpl. every agent will pull different arms through the exploration and avoid collision with each other.
The empirical mean of arm & estimated by agent j during exploration after time step t is denoted by (t), the number of time steps that arm m is pulled by agent j in exploration at the end of time step / is denoted by Nym(1) (t). We say agent achieves an accurate estimation for the remaining arms in Ap successfully at time step (i.e., she will transmit a success signal of exploration) only if for any
pair of arms (m,n) in Ap. either (!) -v
2 T (9)
(in +V
2 log (
ügn (1)
2lg T
fym(1) (1) +/
2log T is satisfied.
N Ny

---

2.4.2 Communication
Algorithm 2 @ayer_leaded
Require: Ap. Ry. Mp, whether successs ochether_success, M
Ensure: opt_ arr E(j)
opt arm
apt_arm 1,,, E f all leader success whether_success success
2: for m =1,2, [Mp. i 1, 2, ...., Apl i 1,2, .... M, i2 i1 + 1, 1,... M do
3: if 83 (Appp()]] == j then
4:
If all Lillleader leader_success _uccesss =- 0, agent j pulls arm i; otherwise pulls an arbitrary arm i' +' aaggent is transmitter
5:
6:
else if sy[Ap|i]|( = then
7:
Agent j pulls arm i, and only if (t) == 1, she sets all_leader_succen 0. # agent; is receiver
8:
9: else
10:
Agent j pulls an arbitrary arm i' * # agent j is bystander 11: end
12: end for
13: if all leader_success _succesucssssss == then
14: opt_arm, GS _anaa_ddaa hond_arm_itee arr__iinoormaaioon/ Ap)
15:
end if
17: return opt_arm, E(i)
Layer leaders. For layer leaders at layer p. their communication procedure is described in Algorithm 2 From lines 1-12, they exchange their information about whether all the layer leaders achieve accurate estimation successfully and transmit this information to the layer followers at the mean time.
If all layer leaders achieve accurate estimation successfully, then they continue to execute GS __nd_____ arm__in cerrn_inoorren formation and enter the exploitation phase. Otherwise, they start a round of exploration according ML-ETC. The GS and Larm_ in formmtaio procedure in Algorithm 2 lasts for [Mp) + (Rp [Mp time steps. In the first [Mpll time steps, layer leaders follow the standard Gale Shapley algorithm (6), where each agent's preference towards arms is in the descending order of the empirical means. Thus, each layer leader proposes to the best unrejected arm iteratively (i.e., the empirical best arm which agent hasn't 't encounter collision yet). This makes sure that all the agents obtain their empirical optimal stable arms. In the rest (/Rpl - [MMp] [AApl time steps, they commit to their empirical optimal stable arms so that the layer followers have enough time to receive the information about these "leaving arms" (which is used to construct the remaining arm set in the next layer).
Layer followers. For a layer follower in layer p. her actions in the communication described in Algorithm 3 From lines 2-8, the agent either stands by wait for her turn receive the information whether all layer leaders achieve an accurate estimation successfully (denoted by all all_leader success in line 4).
If there exist some layer leaders sending the unsuccess signal of exploration, all the layer followers switch to a new round of exploration. Otherwise, layer follower continues to execute lines 10-25. Specifically, layer followers first wait for IM, 2 time steps by choosing an arbitrary arm to pull. Note that based on the property of layer followers, their actions will not influence the GS algorithm among layer leaders. Then for each arm in R,, layer followers explore whether the arm is available (i.e., the remaining arm set Ap+1 in the next layer) based the order of the their indices one by one. For an agent i, if it is not her turn to explore an arm, e.g., k. she will always choose the next arm in Ap to pull. Note that in i's exploration of available arms, all the other layer followers o i are pulling another arm in Ap. Therefore, those arms on which the agent gets a collision will leave at the end of this layer. Below, We illustrate the algorithm with example.
Example 1. Ler M (A, B, D) and A 21, 4) and assume the preference below:
1: 1: >
C Cx1 D
A:1>A2743>4
2: A B >2 C
B:1>93>n2>n1
3:B A>3
C:2>c3><4re1
4: 1:AxBBDD>
D:A703>02>01
7

---

Algorithm 3 layer_follwwer
Require: 8, Ap, Ry, Mp, M,
Ensure: p. Ap Ap.MM. Rs
I: A Ap: M f Mp, R t Rp R
2: for m = 112, 2,.....
Mpl.i=1. 1,2,
AAp = 2, N..,,,,, M, 12 i, + 1.... M do
3:
if 89 [1 = j then# agent is receiver
4:
Agent j pulls arm i, and sets all _eeader_succent = - if bplli E MMp
5: else
6:
Agent j pulls an arbitrary arm i' * i. # agent j is bystander
7: end if
8:
end for
9:
if all leader sindderssucesss success
then
Pull an arbitrary arm for M time steps. wait for the layer leaders to look for their optimal stable matching arms 12: for Ap. T = 1, 2.... Rpl Mpl do
10:
if T == I (f the order of agent j in layer follower set Rp M,)) then # it is agent j's turn to explore available arms
14:
Agent j pulls arm æ if (t) == 1 then A
16:
17:
18:
end if
19:
else
20:
Agent j pulls an arbitrary arm x' +
21:
end
22:
end for
23:
R < Rp \ Mp. M t- occ(i, A, R. 85) #M denotes the set of new layer leaders
24:
p p + #agent j will later enter the next layer
25:
end if
return p. M,R
From Definition 7 and we construct the communication graph G(M; and find out that
the subset [A, B3 forms an outer closed circle. Thus, at layer 1, all agents will keep iterating between communication and exploration until the layer leaders M1 = {A, B} achieve accurate
estimations on all remaining arms A₁ = A= {1, 3, 4} and leave with their empirical optimal arms {1, 3} (with high probability). Then, the layer followers {C, D3 will enter layer p with the
arm set A2 = {2, 43. With similar analysis, we conclude the whole process in Table 2
At the end
(layer 4), all agents will exploit their optimal stable arms (with high probability).
Table Example
Layer(p)
A
R2
Mp
Exploitation
(1,2.3.4)
(4. (.
2
(2,4)
(C, D)
(D)
((A, 1), (B,3))
(2)
(C)
[C)
[GA, 1), (B,3), (P.4)
4
((A, 1), (D.
2.5 Regret Analysis
Theorem 1. If every agent rums Algorithm ML-ETC, then the optimal regret after T time steps is upper bounded by:
32 A
Reg(T) MK
Mog T MC1 MC2 + MC3,
(1)
where C MK + M M*K2 M, C2 ( 32 + M)
KM²(M-1)
+ M + KM), and C's
2
2MK
32
A

---

In Theorem the regret term MC2 is the communication cost induced by the initialization phase; the regret term MC2 is the communication cost in the multi-layered exploration and communication phase; and the regret term MC3 is the cost of wrong estimation under a low-probability event.
Asymptotic term of T: The majority term of regret is MK [og T), which is Ollog T') term and is better than all prior works [0].
Dependence of M, K: The regret upper bounds of existing works (i.e., Phased-ETC and CA- UCB) have much higher dependence on M, K. For example, the regret bound of Phased-ETC contains a term of O(cxp( (xxp(()))) 2=)). Note that A < 1/K (since the utility is from [0, 1], this term is ((xp((K3) and much larger than ours. As for the regret bound of CA-UCB, it contains term of O(exp(M*) log" T).
Proof sketch: The regret of our algorithm ML-ETC can be divided into three parts.
The regret caused by the initialization phase is upper bounded by M MC1, since the initialization phase lasts for C₁ time steps.
To bound the regret caused by the other two phases, we let ro = r1 = [ define the following event.
r2 = ro + M,, and A
32
2 loo T
Vj E G,M ro E A, (ugmmmm)) - aym (t) Sv Njm(t) (t)
holds after rounds of exploration
We prove that Pr[E] 2 1- Mr Because of this, we know that the expected regret in the last two phases under - is upper bounded by constant MCC.
Then we consider the expected regret in these two phases under &. In this case, the length of the multi-layer exploration and communication phase can be upper bounded by rı K [log 71 + C2, since the length of one round of exploration [Ap][Tog T S K [log T7, the length of one round of
communication be upper bounded by K (M-((M M KM and every agent will enter the exploitation phase after at most T1 rounds of exploration and r2 rounds of communication conditioning on E.
On the other hand, under E, all the agents will get the right estimation during the GS _____nd____ allaaaddddmm____a aam_armmii perm_informn formmtaion procedure. Therefore, every agent j must match with her optimal stable arm 0 in the exploitation phase. This means that the expected regret in the exploitation phase under E is O.
Summing over the expected regret in three phases, we finally get the regret upper bound in Theorem 1 Due to space limit, the details of the proof are deferred to Appendix.
Simulation
Setup. We choose the time horizon to be T 2.5 x 107, arms' mean utilities within [0.3. 0.6), and the minimal gap A 0.05. We have tested two cases with agents and 5 arms but different preference and utility. To investigate the quality of the converging stable matching under different algorithms, we choose the arm preferences such that there exist multiple stable matches between agents and arms (see Appendix for the implementation detail).
Baseline. Phased-ETl ETC is a phased based decentralized algorithm which theoretically obtains the Ollg + T + exp( )) regret. The duration of each exploration determined by the parameter When e is smaller, the duration of each exploration is shorter. Same as the simulation in 22) we choose 6 0.2 in our simulation.
CA-UCB 10 is a UCB-basee algorithm that aims to avoid collision combined. guarantees an Ollog" T) pessimal regret (a less strict notion of regret). Same as the simulation in 10], we choose the parameter À of delay probability to be X 0.1. Note that CA-UCB requires more information (i.e., all agents know the complete arm preference and can observe the winning agent for each arm at the end of each round), thus the comparison here is not entirely fair for ML-ETC.
Result. Figure shows the average regret and the standard deviation of regret over 50 independent runs. From Figure I ML-ETC outperforms both Phased-ETC and CA-UCB from asymptotic view,

---

which shows that our proposed algorithm has lower regret in general cases, but may encounter cold start. The cold start means that when the time horizon T is small, ML-ETC may cause a relatively high regret. This is because ML-ETC has strict requirement of agents' estimation, only when the agents have very high confidence, will they enter the exploitation. As for Phased-ETC. the duration of the exploration is determined by the parameter c. The agents may start the exploitation only with limited exploration, and in this case they are not able to distinguish the arms, especially when A is small. Though this leads to smaller short-term expected regret (at the beginning, Phased-ETC outperforms our ML-ETC), for large T, this can cause a very high expected regret of O(exp( x )) (in experiments with A 0.05, this is even larger than T, and therefore the regret of Phased-ETC increases linearly as T increases). In CA-UCB, there is possibility that an agent j converges to pulling a sub-optimal arm is # 0j in Astable (i),, which also causes linear optimal regret.
12-
regrut
regrel
04
tmo
time
(i) Case 1
(ii) Case 2
Fig. 1. Comparison between ML-ETC and basclines.
4 Further Discussion on Possible Improvements
In this section, we discuss several possible improvements on ML-ETC, which may largely improve the efficiency of the communication and exploration.
Initialization Phase: In the in informaaion__ _access_csssssss procedure, instead of conducting communication procedure com(i, j, k, s;) on all the "agent,agent,arm" tuples, we only need conduct communication procedure com(i, j. k, s;) on some special tuples which satisfies that j is ranked the next of i on arm k. And this will reduce the regret of this procedure by M times.
Multi-layered exploration and communication Phase:
In the communication part for layer leaders to exchange signal of successful estimation, instead of conducting every effective communication pro- cedure on every remaining arm, we can find circle no longer than 2M that includes all layer leaders in the corresponding communication graph and conduct communication procedure through this circle. Specifically, we begin from an agent in this circle according to a pre-determined order and conduct effective communication along the circle until all agents have gone through the communication twice. This improvement will reduce the regret of this procedure by O(M² K) times.
Dependence on the minimal gap A: In the exploration part, for example, instead of trying to distinguish all remaining arm, all layer leaders in layer p only need to distinguish the [Mpl-best remaining arms (which is the number of the layer leaders). This means that letting the agents only distinguish "meaningful arms" may also improve our algorithm by reducing the dependence on the minimal gap. We can use the minimal utility gap between "meaningful arms" instead of the minimal gap in our regret upper bound.
The frequency of Communication: Instead of exploring every remaining arms [log 7'I times per ex- ploration, we can explore more time steps per exploration and reduce the frequency of communication, which may also help achieve lower regret.
Acknowledgments and Disclosure of Funding
The work of Siwei Wang is supported in part by the National Natural Science Foundation of China Grant 62106122.
10

---

References
[1] Itai Ashlagi, Anilesh K Krishnaswamy, Rahul Makhijani, Daniela Saban, and Kirankumar Shiragur. Assortment planning for two-sided sequential matching markets. Web and Internet Economics: 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings, volume 12495, page 476. Springer Nature, 2020.
[2] Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pages 705-715. PMLR, 2021.
[3] Ilai Bistritz, Tavor Baharav, Amir Leshem, and Nicholas Bambos. My fair bandit: Distributed learning of max-min fairness with multi-player bandits. In International Conference on Machine Learning, pages 930-940. PMLR. 2020.
[4] Etienne Boursier and Vianney Perchet. Sic-mmab: synchronisation involves communication in multiplayer multi-armed bandits. Advances in Neural Information Processing Systems, 32, 2019.
[5] Sarah H. Cen and Devavrat Shah. Regret, stability & faimess in matching markets with bandit learners. In International Conference on Artificial Intelligence and Statistics, pages 8938-80 8968. PMLR, 2022.
[6] David Gale and Lloyd Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962.
[7] Meena Jagadeesan, Alexander Wei. Yixin Wang, Michael Jordan, and Jacob Steinhardt. Learn- ing equilibria in matching markets from bandit feedback. Advances in Neural Information Processing Systems, 34:3323-3333 2021.
[8] Yuantong Li, Chi-hua Wang, Guang Cheng, and Will Wei Sun. Rate-optimal contextual online matching bandit. arXiv preprint arXiv:2205.03699 2022.
[9] Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference Artificial Intelligence and Statistics, pages 1618-1628. PMLR, 2020.
[10) Lydia T Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. Journal of Machine Leurning Reseurch, 22(211):1-34 2021.
[11] Abbas Mehrabian, Etienne Boursier, Emilie Kaufmann, and Vianney Perchet. A practical algorithm for multiplayer bandits when arm means vary among players. International Conference on Artificial Intelligence and Statistics, pages 1211-1221. PMLR, 2020.
[12] Jonathan Rosenski, Ohad Shamir, and Liran Szlak. Multi-player bandits-a musical chairs approach. International Conference on Machine Learning, pages 155-163. PMLR, 2016.
[13] Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate delete: Decentralized competing bandits in serial dictatorship. In International Conference on Artificial Intelligence and Statistics, pages 1252 1260. PMLR, 2021.
[14] Chengshuai Shi and Cong Shen. On no-sensing adversarial multi-player multi-armed ban- dits with collision communications. IEEE Journal on Selected Areas in Information Theory, 252):5 2021.
[15] Chengshuai Shi, Wei Xiong. Cong Shen, and Jing Yang. Decentralized multi player multi-armed bandits with no collision information. In International Conference on Artificial Intelligence and Statistics, pages 1519-1528. PMLR, 2020.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 3
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen- tal material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "sVgE1MLL6pe", "reviewer": "Reviewer_gFbZ", "summary": "The paper is concerned with matching and MAB setting of Liu et al, 2020. The main contribution of this paper is an improvement in the regret to O(log(T)) through a communication protocol between the agents. ", "questions": "In particular, I would the authors to address points 1 and 2 below weaknesses in the above section.\n\nMinor Issue: In Line 24, I_j(t) \\in A (set of arms), not M (set of agents). ", "limitations": "Authors have adequately the limitations ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "$\\textbf{Strengths}:$\n\n-This setting has gained significant attention and I think an improvement to log(T) is significant. Further the algorithm experimentally outperforms the other baselines. \n\n-It does not seem that using communication between agents was explored in this setting.   \n\n$\\textbf{Weaknesses}:$\n\n1-The regret seems to have a higher linear dependence on the number of agents M. Is this a drawback? For example the simulation results actually involve a small number of agents (3 and 5). Would the algorithm still outperform other baselines when the number of agents is increased, it seems that it would be good to demonstrate that.\n\n2-While the agent only needs knowledge of his history and collisions to make decisions, is the setting completely decentralized? Is it obvious that no agent has an incentive to deviate from the protocol?\n\n3-The discussion of the algorithm discussion is rather  verbose. While this is not necessarily a weakness, I think the technical content could be improved representation-wise perhaps through the addition of diagrams. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rnIeRE-ewn", "reviewer": "Reviewer_kPHe", "summary": "The authors study the problem of bipartite matching under one-sided uncertainty with respect to preferences—i.e., where one set of market participants (here, agents) must learn their preferred ordering over the other set of market participants (here, arms) through repeated interactions (pulls). They do not assume that agents are globally ranked, but rather, that each arm has its own privately held preference order over agents, such that if multiple agents propose to the same arm at time $t$, a collision will occur, and only the agent most-preferred by the arm will obtain a non-zero stochastic reward. To address this setting, the authors introduce Multi-Layer Explore Then Commit (ML-ETC). This algorithm achieves asymptotic regret of $O(\\log T)$, which is an improvement upon prior work in this space. Regret in this setting is defined with respect to the optimal stable matching (i.e., under Gale-Shapley with known preferences, rather than preferences derived vis-à-vis empirical means). ", "questions": "1. This algorithm seems to require sustained adherence to the prescribed protocol(s) and trustworthy communication to be effective. Is it vulnerable to strategic behavior? (i.e., misrepresentation during the communication stage?) \n2. Are arms’ preferences over agents required to be strict and complete?\n", "limitations": "- The authors acknowledge that one limitation of their proposed approach is that ML-ETC may outperform alternative approaches asymptotically, but over smaller, finite time horizons, the estimation accuracy requirements of ML-ETC may result in relatively high regret. \n- A possible limitation is that the phase-based approach outlined here may result in uneven distribution of regret over agents. This concern could be mitigated if it’s possible to show that these agents would fare at least as poorly in expectation under existing approaches.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*:\n- The problem considered— i.e., decentralized matching under uncertain preferences—is interesting, and the introduction of communication among (subsets of) agents in this setting seems reasonable/well-motivated. \n- ML-ETC asymptotically outperforms existing SoTA approaches with respect to regret; empirical results support theoretical claims. \n- Reproducibility: the authors provide detailed pseudocode along with source code.\n \n*Weaknesses*:\n- Scalability/ lack of sensitivity analysis: empirical results are reported only for small values of $M$ (number of agents) and $K$ (number of arms) and a single value of the minimal gap, $\\Delta$. \n- Clarity: while the paper is generally well-organized, certain details of the algorithmic exposition were a bit hard to follow (in particular, which communication(s) of what information were occurring simultaneously versus sequentially). A visual representation of the way in which arms and agents progress through the algorithmic pipeline over time/from phase to phase would be helpful. Additionally: \n    - Since much of the algorithm builds upon Proposition 1, it would be helpful to include at least a proof sketch in the main paper (in particular, re: uniqueness). \n    - (really minor) grammar suggestion: “switch from exploration to exploitation timely.” → “switch from exploration to exploitation in a timely fashion.”\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qZIzjffJ0_", "reviewer": "Reviewer_EhYJ", "summary": "This paper studies the matching under the multi-agent MAB setting. Specifically, the arms have preferences over agents; the communication is via a decentralized communication graph instead of via a central server. This paper proposes an ETC-based algorithm. The algorithm provably achieves state-of-the-art $\\log(T)$ regret. Empirical study justifies the theory. ", "questions": "The related work is not thoroughly discussed in this paper. To mention a few:\n\ni. What is the relation between the problem considered in this paper with the classical combinatorial bandit problem (e.g. [1], [2])?\n\nii. Elimination-based algorithms are popular for MAB (e.g. [3]). Is it possible to leverage elimination-based methods in the setting of this paper and why or why not (intuition is fine)? My guess is that elimination probably does not help here due to the setting that arms have preference. But the authors should at least touch on this facet. \n\niii. MAB can be viewed as a special case of contextual linear bandit, and there are many related works studying two-sided matching with linear bandit (e.g. [4], [5], [6]). Should briefly mention how these works are related to this paper (e.g. similarity and difference in the setting and algorithm design; can the problem be reduced to each other)? \n\n[1] Cesa-Bianchi, N. and Lugosi, G. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404– 1422, 2012\n\n[2] Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. Combinatorial pure exploration of multi-armed bandits. In Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N. D., and Weinberger, K. Q. (eds.), Advances in Neural Information Processing Systems 27, pp. 379–387. 2014.\n\n[3] Katariya, S., Kveton, B., Szepesvari, C., Vernade, C., and Wen, Z. Stochastic Rank-1 Bandits. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 392–401, Fort Lauderdale, FL, USA, 20–22 Apr 2017.\n\n[4] Learning Equilibria in Matching Markets from Bandit Feedback, M Jagadeesan, A Wei, Y Wang, M Jordan, J Steinhardt, 2021\n\n[5] Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets, Y Min, T Wang, R Xu, Z Wang, M Jordan, Z Yang, 2022\n\n[6] Rate-Optimal Contextual Online Matching Bandit, Y Li, C Wang, G Cheng, WW Sun ", "limitations": "No extra concerns.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The math is clear and easy for the readers to follow.\n\n2. The paper contributes to a problem that is very important in ML theory and also in real applications.\n\nWeaknesses:\n\n1. The authors fail to discuss many important and probably highly related works. \n\n2. The communication protocol is a bit complicated to understand. Also should justify why this protocol makes sense (by giving a simple example). \n\nOverall, I think this paper makes good contributions to an important area. But the weaknesses make it hard to justify whether there are enough level of originality compared to the related work and thus the significance is not very clear at this moment. More elaboration is needed from the authors. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "qN-lQXqiY0V", "reviewer": "Reviewer_UKRH", "summary": "\nThis papers considers decentralized matching markets with bandit feedback. An algorithm, ML-ETC, is proposed that organises the agents in communicating/hierarchical layers. An upper bound on regret is proven and the algorithm is empirically compared against Phase-ETC and CA-UCB. ", "questions": "\n\n- In line 30 you say that w.l.o.g. you assume that all gaps between the utility for all arms and agents is positive. Can you explain why this can be assumed \"without loss of generality\"?  \n\n- If I am not mistaken, your definition of regret is \"incorrect\" in that a lower bound would be linear. An arm can be attainable for agent $j$ according to your definition, however, under the agent-optimal matching $j$ may not actually be matched to $a^*_j$. Instead, you should probably say that an arm is attainable for agent $j$ if $j$ and this arm are being matched under the agent-optimal matching. (I could be wrong.)  \n\n- Line 98, you write that your algorithm achieves *asymptotic* regret $O(\\log T)$. Please clarify. \n\n- Line 283: You claim that your regret bound is $O(\\log T)$ better than prior work. I don't think that this is true. See [1].\n\n\n\n- As I already said, I have difficulties following the proof. Very weird is the step at line 510. First of all writing $\\sqrt{\\frac{\\log T}{\\log T}}$ makes no sense and is probably a typo(?). Secondly, what is the purpose (even when you add $N_{jn}(t)$) to the statement? Yes, you can control the distance of your estimated utilities to the true utilities in terms of the number of times that you saw these, however, I don't understand how you use this afterwards. The proof looks like the standard explore-first algorithm (which suffers larger regret than $\\log T$). Lines 511 and following are very confusing to me. \n\n\n- The fact that both Phase-ETC and CA-UCB suffer linear regret in your experiments is pretty surprising (even when you set the gap as small as you do). I couldn't find an implementation of these algorithms in the submitted code. Could you make it available? I'm curious about their empirical sensitivity to the gap on your problem instances.  \n\n\n\n- Minor: Line 171: $j_1 \\in [1, M]$ should probably be $[M]$ ($= \\{1, \\dots, M\\}$)\n\n\n\n[1] *Beyond log2 (T) Regret for Decentralized Bandits in Matching Markets*, Basu et al. ", "limitations": ".", "rating": 3, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThe authors claim a regret bound of order $O(MK \\log(T) / \\Delta^2 + M^5 K^2)$, which would, as far as I can tell, be an improvement over prior work (Although $M^5 K^2$ is a fairly large overhead compared to e.g.\\ the dependence on $M$ and $K$ in [1].) \n\nHowever, I have concerns about the soundness of the paper, both on the theoretical as well as the empirical side. \nTo be honest, I cannot really make sense of the proof given in the Appendix and I'd like to hear my fellow reviewers' opinion on the proof of Theorem~1. Moreover, I'd like to ask the authors to elaborate on the empirical results (see below). \n\n\nThe organisation of the paper is fine, although the writing would benefit from a few more iterations. \n\nI am willing to increase my score if the soundness of the paper can be demonstrated by means of a rigorous, easier to follow proof and empirical reproducibility.  \n\n[1] *Beyond log2 (T) Regret for Decentralized Bandits in Matching Markets*, Basu et al. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_TlyTp2Zj1u", "reviewer": "Reviewer_6TUF", "summary": "The paper studies the problem of matching in multi-armed bandits with collisions, where $M$ agents interact with $K$ arms. Agents aim to maximize their (arm-dependent) reward, while arms have an ordinal preference over agents. If two agents play the same arm, the agent with the higher preference will gain the reward, while the second agent will experience a collision. As in some previous works, the authors use collisions to transmit information between agents. As the ‘winning’ agent does not observe a collision, some agents cannot receive messages from other agents, and the communication scheme can be described by a directional graph. \n\nTo solve this setting, the authors suggest a 3-phase algorithm. The first phase is a fixed-length initialization phase, in which all agents explore the graph structure and communicate it with each other. Then, agents are divided into a hierarchy that’s based on the graph structure. Agents on each level of the hierarchy explore all arms until they accurately identify them (‘exploration’), and then commit to a single arm until the end of the game. This is done sequentially at all levels of the agent hierarchy. The authors show that this algorithm (ML-ETC) achieves a logarithmic regret and empirically compare it to other baselines.", "questions": "Minor comments:\n- Lines 37-38: when reading the stability definition for the first time, it seemed like the ‘both are more statisfied’ phrase referred to the two agents, and not the agent-arm. I suggest rephrasing it to be clearer.\n- I would also appreciate it if the authors could say a bit more in the main text about the Gale-Shapely algorithm", "limitations": "The authors should discuss the weaknesses I described in greater detail (the synchronization assumption and implications of the dependence on the minimal gap).", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To my understanding, the main contributions of the paper are:\n1) The characterization of the graph structure in the matching bandit problem,.\n2) The insight that this structure effectively creates a hierarchy between agents that can be leveraged for layered exploration.\n\nOn the other hand, I think that there are a few major issues in this work. The main issue is the assumption that all agents are synchronized (always start the game at the same round). This assumption is not trivial in any multi-agent system, and to my knowledge, creates the `hack’ that allows the communication-through-collisions [4]. With this assumption, the agents can easily identify the graph structure (as done in the initialization stage) and make sure to avoid collisions except in designated communication phases. Therefore, synchronization makes the model much easier – there’s no major difference between a known or unknown preference model (and probably no real gain in knowing the identity of the agents we collide with).\nA second weakness is the requirement to explore all arms for all agents until their ordering is identified with a high probability. This creates a dependence on the minimal gap between any two arms, which might be extremely small. In particular, the algorithm will probably break if any two arms have the same mean, and this also probably implies that the algorithm has no sublinear problem-independent regret.\n\nAnother smaller, related, issue is that the exploration phases must know the time horizon – the game is not only synchronized, but also cannot be anytime.\n\n\n---------------------\n\n### Post Rebuttal\nI thank the reviewers for the response. I still don't think that the contribution (the communication characterization/protocol between agents) is sufficient to pass the acceptance bar, and I decided to leave my score unchanged.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept