Bandit Learning in Matching Markets Robust to Adversarial Corruptions
Authors: Zheshun Wu
Jinhang Zuo
Zenglin Xu
Fang Kong
Venue: ICLR 2026 Poster (2026)
Keywords: Bandits
Matching markets
Robust algorithms
Adversarial corruptions
Primary area: learning theory

Abstract: This paper investigates the problem of bandit learning in two-sided decentralized matching markets with adversarial corruptions. In matching markets, players on one side aim to learn their unknown preferences over arms on the other side through iterative online learning, with the goal of identifying the optimal stable match. However, in real-world applications, stochastic rewards observed by players may be corrupted by malicious adversaries, potentially misleading the learning process and causing convergence to a sub-optimal match.  We study this problem under two settings: one where the corruption level $C$ (defined as the sum of the largest adversarial alterations to the feedback across rounds) is known, and another where it is unknown. For the known corruption setting, we develop a robust variant of the classical Explore-Then-Gale-Shapley (ETGS) algorithm by incorporating widened confidence intervals. For the unknown corruption case, we propose a Multi-layer ETGS race method that adaptively mitigates adversarial effects without prior corruption knowledge.  We provide theoretical guarantees for both algorithms by establishing upper bounds on their optimal stable regret, and further derive the lower bound to demonstrate their optimality.

Published as a conference paper at ICLR 2026
BANDIT LEARNING IN MATCHING MARKETS ROBUST TO ADVERSARIAL CORRUPTIONS
Zheshun Wu
Jinhang Zuo
Zenglin Xu
Fang Kong!*
Southern University of Science and Technology
Harbin Institute of Techholooy,, Shenzhen
3 City University of Hong Kong (wuzhsh23, jinhangzuo, zeng in @gma i i1 com kongf@sustech. edu. on
*Fudan University
*Shanghai Academy of Al for Science
@
ABSTRACT
This paper investigates the problem of bandit learning in two-sided decentralized matching markets with adversarial corruptions. In matching markets, players on one side aim to learn their unknown preferences over arms on the other side through iterative online learning, with the goal of identifying the optimal stable match. However, in real-world applications, stochastic rewards observed by players may be corrupted by malicious adversaries, potentially misleading the learning process and causing convergence to a sub-optimal match. We study this problem under two settings: one where the corruption level C (defined as the sum of the largest adversarial alterations to the feedback across rounds) is known, and another where is unknown. For the known corruption setting, we develop a robust variant of the classical Explore- T'hen-Gale- Shapley (ETGS) algorithm by incorporating widened confidence intervals. For the unknown corruption case, we propose a Multi-layer ETGS race method that adaptively mitigates adversarial effects without prior corruption knowledge. We provide theoretical guarantees for both algorithms by establishing upper bounds on their optimal stable regret, and further derive the lower bound to demonstrate their optimality.
INTRODUCTION
Two-sided matching markets have garnered significant research attention due to their central role in marketplace applications (Gale & Shapley (962), from crowdsourcing markets (matching customers with freelancers) (Sun et al.) 2023) to ridesharing platforms (pairing passengers with riders) (Dick) jerson et al.) 202 l). In these markets, each participant maintains preference ordering over the other side (Liu et al.) 2020), derived from latent utilities such as freelancer's s service quality or a rider's reliability. One of the core evaluation metrics on matching markets is stability (Roth & Sotomayor 1992), which illustrates equilibrium states where no participant pair can mutually benefit from deviating from their current match.
In real-world applications, for example, labor markets with employers and workers, employers not aware of the real working qualities of workers before employment. Hence, their preferences over workers are unclear (Liu et al. 2020 Kong & Li. 2023). A key challenge arises on how to attain an optimal stable matching among competing participants, only through learning from the iterative matchings with the other side (Liu et al. 2021). As well known learning framework under uncertainty, multi-arma anddd bandit (MAB) has been widely used in many sequential decision- makinn applications (Auer et al., 2002 Slivkins, 2020). In recent years, the MAB framework has been studied in many studies of matching markets (Liu et al. 22000) 2021, Basu et al. 2021 Kong et al.) 2024| (025). These works regard players and arms in MAB as two sides of the market participants. Each player has unknown preferences over arms corresponding unknown reward distributions in MAB. Hence, players aim to learn the distribution iteratively via collecting empirical observations to minimize the player-optimal regret defined comparing practical matching with the players' pret-rreferred stable matching. We notice that the common bandit learning model for matching markets significantly depends stochastic rewards. In words, most of the current works assume that
"Corresponding author.

---

Published as a conference paper at ICLR 2026
the rewards generated by successful matchings between players and arms are drawn from unknown but fixed distributions.
More specifically, existing bandit algorithms in matching markets commonly assume that the feedback players receive from arms follows the true preference model (Liu et al. 2020 Kong & Li 2023 Zhang & Fang 2024). However, this assumption is often difficult to satisfy in real-world scenarios. External noise or deliberate manipulation may compromise the authenticity of the feedback. For example, in the server resource allocation problem (Hussain al., 2013), certain computing nodes may exhibit performance far exceeding their actual capabilities during the testing phase to induce the system to allocate more resources (Pamarthi Narmadha 2022). Click fraud in advertising scenarios is another typical example of feedback contamination Zhang & Guan [008 Oentaryo jet al. 2014), where competitors or malicious third parties may use automated scripts or click farms to generate a large number of clicks, creating false click-through rates. These interferences can severely distort feedback signals, preventing players from accurately learning the true preferences. Yet, existing algorithms lack defense mechanisms against contaminated feedback, rendering them unable to converge to the true stable matching once the feedback is polluted.
We observe that these challenges can be naturally modeled as stochastic multi-armed bandit (MAB) problem with adversarial corruptions (Lykouris et al. 2018: Gupta et al., 2019), where each arm pull produces stochastic reward that may be perturbed by adversary before being revealed to the player. We further show that standard bandit algorithms for matching markets with stochastic feedback, such as the vulnerable: even limited adversarial corruption can mislead players into consistently matching with suboptimal arms, resulting in linear regret. These insights motivate us design new algorithms for matching markets that remain robust under adversarial corruptions.
(ETGS) algorithm (Kong & Li 2023), , highly
In this paper. we take the first step study bandit learning problem of decentralized matching markets with adversarial corruptions. We first provide a robust variant of ETGS with widened confidence intervals for tackling the known corruption setting as a warm-up. For the unknown corruption setting, we devise a Multi-layer ETGS race method that can handle any level of corruption, and its performance degrades gracefully as more corruption is added. We highlight that this method can both tolerate corrupted feedback and utilize the stochastic component of feedback to enhance bandit learning. However, incorporating existing randomized algorithms (Lykouris et al. 2018) into ETGS leads to frequent matching conflicts, resulting in inefficient feedback collection. To address this challenge, we introduce a sub-phase level synchronization mechanism to avoid conflicts, and develop novel martingale concentration inequality design principled confidence intervals. We also uncover an intrinsic trade-off between communication cost and learning efficiency in the unknown corruption setting, and further propose a joint optimization strategy to identify the optimal synchronization interval for balancing this trade-off. Eventually, we establish the regret lower bound of this problem to demonstrate the tightness of our algorithms' regret upper bounds.
Our contributions can be summarized as follows:
Our work investigates a new bandit learning problem of decentralized matching markets with adversarial corruptions, capturing more practical adversarial scenarios.
We observe that directly extending existing randomized algorithms for matching markets with unknown corruption leads to frequent conflicts in the vanilla ETGS algorithm. To overcome this challenge, we develop novel Multi-layer ETGS race method with a synchronization mechanism that coordinates effective exploration among the players.
We derive novel martingale concentration inequality tailored for the synchronization mechanism to bound the total corruption suffered by Multi-layer ETGS race with high probability. This inequality allows set a principled confidence radius. Finally, we reveal fundamental trade-off between communication overhead and learning efficiency in the unknown corruption setting, and further identify the optimal synchronization interval that balances this trade-off.
We prove player-optimal stable regret upper bounds for proposed algorithms, and further provide the lower bound to show their optimality.
Due to the space limit, more related works can be found in Appendix A
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
In this section, we provide the problem formulation of bandit learning in matching markets robust to adversarial corruptions.
Two-sided matching markets. We consider N players and K arms, and assume N S K. Define = {Pi, P2..... PN } be the player set and K = {a1, ................................ .KK be the arm set. We describe the preference rank of player p4 over arm aj by real value Hu. (0, 1]. We can notice that the greater value of J demonstrates more preference on arm dz. Without loss of generality, we consider that all preference lists are heterogeneous, i.e., [4. o H4,,"' for distinct arms aj # aj', keeping consistent to previous works (Sankararaman et al. 2021 Kong & Li] (003). Besides, each arm is equipped with a preference ranking over players. Denote (Tj,) as the distinct preference values of arm dz over players. Then Tz.i > TJ. implies 0j prefers p; to pi. Motivated by real applications such as online labor market Upwork with employers and workers, the preferences of players are usually uncertain and can be learnt through iterative matching processes. While arms usually know their preferences based on some known utilities such as the payment of employers. matching markets, stability is a key concept (Abdulkadiroglu & Sönmez, 2013). Formally, the matching (t) is stable if no player and arm has incentive to abandon their current partner, i.e., there exists no player-arm pair (pt, aj) such that pij > (t) and J > J.A, '()) where we simply define TT -o and μ4,6 -00 for each j E [K] i E [N]. Notice that there may be more than one stable matching in the market.
Bandit learning in matching markets. In each round E [T], each player p: proposes to an arm A²(1) E K. Correspondingly, each arm oj receives requests from players in ())
{p: : (t) = aa}. Analogous the labor market where a worker can only work for one task, arms would only accept one request from the player that it prefers most. If a player Pe is successfully accepted by the proposed arm (t), will receive a random reward (t) r A.,.. (t) F. corresponding to the expectation characterizing its matching experience in this round, which we assume is 1-subgaussian with expectation ( And if p; is rejected, it only receives X2(t) 0.
For convenience, denote A(I) = {(i, A. (0) i E [N]} as the selections of all players and A(I) = {(i, (t))) : [N]] as the final matching at round
Matching markets with corrupted feedback. In this paper, we consider that there exists an adaptive adversary who can corrupt certain stochastic rewards acquired by players based on historical information. In the following, we take the player p; as an example to illustrate the interaction process between the player and adversary. The interaction protocol is formally provided as follows,
1. For player P;, a stochastic reward (l) is drawn for each arm j E [K] according to the reward distribution Fi,j with mean ji.j.
2. For any arm J E [K] the adversary observes the realizations of ri, (t), along with rewards and matches of player pa in previous rounds. Then the adversary returns a corrupted reward ri.s E 10.
3. If p; is matched successfully with its proposed arm A,(t), Ps will observe the corresponding corrupted feedback X²(1) = (t) (1).
Similar to Lykouris et al. 2018 define maxjejи (t).(t) - (t) as the amount of corruption injected in round 7 for player pj. The level of total corruption incurred by ps is defined as
Σ max (t) - (t) LE|T
JE[K
We emphasize that the adversary is allowed to be adaptive, i.e., the corruptions on round can be chosen function of the past matches and stochastic rewards of player p;-
In this paper, we consider one standard metric in stochastic MAB termed pseudo regret. Fur- thermore, the player-optimal stable pseudo regret is considered for the matching market set- ting. In specific, let M := {m : m is a stable matching) be the set of all stable matchings and m"* = {(i, mf) i E [N]] E M be the players' most preferred one. That say, Mi,m; 2 pi,m, for any m M, [N]. Our objective is to learn the player-optimal stable matching m" and minimize
3

---

Published as a conference paper at ICLR 2026
the player-optimal stable pseudo regret for each p; N, which is defined the cumulative reward difference between being matched with m and that p. receives over rounds:
Reg, (T)
Σ Mi,m
E
Σ (t)
(2)
where the expectation is taken over the randomness in the received rewards, the players' algorithmic decisions, and the adversary's 's strategy.
For convenience, we also introduce several notations to measure the hardness of the bandit learning problem in matching markets, which will be used in the later analysis.
Definition 2.1. For each player ps and arm 03 & aj', let Anjoy' |pa, H4.5" be the preference gap of Pt between aj and a'z- Let P: be player p; 's preference ranking and Pi,k be the k-th preferred arm in pi 's ranking for k E [K] Define A [i
&.PM as the minimum preference gap among all players and their first N + 1-ranked arms, which is non-negative since all preferences are distinct. Further, for each player Ps. let Aimux Pi,m; be the maximum player-optine stable regret that may be suffered by p; all rounds.
3 ALGORITHM
In this section, we first analyze the inherent vulnerability of the ETGS algorithm (Kong & Li 2023) under adversarial corruptions. We then demonstrate a fundamental limitation of ETGS: introducing randomness into ETGS for mitigating corruption will inevitably lead to frequent matching conflicts. To address these challenges, we propose the main algorithm in this paper termed Multi-layer ETGS race method, which maintains multiple ETGS instances at different learning rates to achieve robustness against any level of unknown corruptions. To eliminate matching conflicts arising from the proposed algorithm's 's randomness, coordinates all players to stay in a same ETGS instance by an elected leader. Besides, we provide robust variant of ETGS with widened confidence intervals, which is used for tackling the known corruption setting, as a warm-up for the Multi-layer ETGS race method.
develop sub-phase level synchronization mechanism that
Vulnerability of ETGS. The core idea of ETGS is to collect sufficient observations in Round-Robin manner to accurately estimate preference rankings and then attain the optimal stable matching via the offline Gale-Shapley algorithm. However, ETGS exhibits significant vulnerability under adversarial corruptions. Specifically, an adaptive adversary can observe the information of all the past matches (t) and the corresponding stochastic feedback S (e) of p; to execute corruption injection in the current round. Consequently, since the arm proposing follows deterministic Round-Robln pattern, the adversary match with a suboptimal arm, misleading its learning process. Such manipulation requires only Olog T/ 2) rounds to take effect, ultimately inflicting (TT) cumulative regret p;-
systematically corrupt the optimal arm for player p.. This forces p; to persistently
Frequent confficts in original ETGS caused by algorithmic randomness. Introducing randomness well-established technique for combating adversarial corruptions in bandit algorithms (Lykouris) jet al., 2018)) Gupta et al.) 2019). Randomized algorithms commonly provide inherent to lraancce compared to deterministic approaches like UCB or arm elimination (Lattimore & Szepesvári, 2020). However, in decentralized matching markets, when players independently employ randomized strate- gies, the probability of matching confficts increases substantially, leading inefficient exploration and degraded learning performance eventually.
Based on the above observations, we develop robust bandit learning algorithms for decentralized matching markets under adversarial corruptions. Our proposed algorithm proceeds through three sequential phases: (1) each player first identifies unique self-identifier; (2) through strategic exploration, players estimate their preference rankings over the top N arms; and (3) leveraging these estimates, they identify and permanently match with their optimal stable arm in all subsequent rounds. The key distinction between our algorithm and ETGS emerges in the second phase. Specifically, we introduce a Multi-layer ETGS race method to achieve robustness under agnostic corruption. In the following sections, workflows of Phase I and Phase 3 in Appendix B Here we provide some insights about Phase and Phase 3. Phase is N-round iterative process that assigns distinct index to each player based on
detail these bandit learning innovations for Phase 2, while deferring the
4

---

Published as a conference paper at ICLR 2026
their acceptance by single preference d1- Phase 3 can be regarded as decentralized Gale-Shapley algorithm (Gale & Shapley 1962), where the objective for players to find their respective arm in the optimal stable matching based estimated ranking.
Prior to formally introducing our main algorithm. termed the Multi-layer ETGS race method, we first present robust ETGS variant designed for known corruption settings warm-up. This preliminary algorithm enlarges confidence intervals in proportion to the corruption level C, establishing the foundation for our subsequent developments.
3.1 ALGORITHM WITH KNOWN CORRUPTION LEVEL
As introduced earlier, all players enter in the second phase after identifying their distinct indices during the first phase. Similar to ETGS, we consider that the second phase is further divided into several sub-phases
....... with the corresponding lengths denoted by d1, d2.... respectively. For the known corruption setting, we adopt the same sub-phase structure as ETGS, where each sub-phase & consists of 2* rounds. Specifically, sub-phase & begins with exploration stage of length 2 rounds and concludes with a single monitoring round. This monitoring round is used for checking whether the preferences of players are estimated well, and introduced in Appendix [ in detail. During this exploration phase, players aim to collect sufficient feedback on arms and detect whether the preference ranks of all players have been estimated well the monitoring round.
During each sub-phase of the second phase, players propose to arms in round-robin fashion. Leveraging the unique indices obtained in Phase 1, distinct players are guaranteed to pick different arms, ensuring conflict-free matching with their proposed arms. After p: obtains the feedback on the matched arm A,(!), it would update the estimated preference value (L,),()) and the observed time T(,,()) for this selected arm (t) as
())),(() = (Ps,A,C0) TrA,00 + (LA,()) ((AA) + 1), TeA,,0)) = Ti,A,00 +1.
At the end this second phase, players would construct a confidence interval for each estimated preference value based its previously collected feedback. Given the prior information of cor- ruption level C, one intuitive idea is to directly enlarge the confidence intervals to handle the worst-case corruption. Recall that the corrupted rewards (t) (t) can be decomposed into two terms ( (1) + (L)) where the second term (, (1) denotes the corruption injected by the adversary in this round. Thus, if the total corruption introduced by the adversary at most C, the confidence interval of p; for the preference value over a, can be established with the upper bound UCB and lower bound LCB defined as
6 blog T UCB = Puu + V Tús
C. Ti,5"
Glog T
C
LCB:J = Pu.
Tıj
Ti.5
where we simply let UCBL, be and LCBi, be -c when Tij = 0. When the confidence sets for two arms (j; (y' are disjoint, i.e., LCB:,, UCB or LCB > UCB Pt can determine its preference over these arms.
Then we present the upper bound for the player-optimal stable pseudo regret of each player by our algorithm. The corresponding proof is provided in Appendix C
Theorem 3.1. Following the Algorithm P: E N satisfies
7
the player-optimal stable pseudo regret of each player
48 log T
C
48 log T
C A )) N2 + +N²+2NK)
Reg, (T) N N 8K
log [KK
mmmxx
2
=O(K log T/A2 KC/A).
(4)
The regret upper bound of our proposed algorithm for known corruption setting is similar to that of Kong & Li (2023). The first term in Eq. (4) is the upper bound for regret incurred in phase 1, the second term is the regret upper bound for the total exploration rounds and the third term is the upper bound for the total monitoring rounds in phase 2, the fourth term the regret upper bound for phase 3 and the last constant term corresponds the bad concentration events.
Remark 3.2.
5

---

Published as a conference paper at ICLR 2026
Algorithm 1 Robust ETGS with Widened Confidence Intervals (from view of player p.)
1: Input: total corruption C, player set N,, arm set IC, horizon T
2: Initialize: fio 0, Ti, = 0, Vij E [K]
3: Phase I: the index estimation phase in ETGS
4: //Phase 2, learn the preferences
5: for k 1.2..... do
6: F = False //whether the preference has been estimated well
7: for tort- = N E (2 +1
I,....,N. N - (2% + +1) + 2 do
8:
(t) a(Index++- +1-))
9:
Observe (t)) (t) and update ()))) ((,A.(1) (, (t)
10:
to N +E k-1
- (2 + +2
11:
Compute UC and ,CB,,, for each j E [K] defined in Eq. 3
12:
Ti O2 Monitoring (UC), J.C.,,
13:
10x = N then
14:
Enter in the next phase with o; Phase 3: the phase of identifying optimal stable match via decentralized GS algorithm in ETGS.
15:
To find the optimal stable arm with o; = (0i,1, 0i,,,...,,..K.
3.2 ALGORITHM WITH UNKNOWN CORRUPTION LEVEL
In the previous subsection, we aim to make the algorithm robust to corruption by directly enlarging confidence intervals. However, this method is inapplicable to unknown corruption settings, as confidence intervals cannot be properly calibrated without knowledge of the corruption level C. In this section, we devise a Multi-layer ETGS race method for achieving robustness under the unknown corruption setting. We highlight that the core innovation of this method includes: (I) handling all possible amounts of corruption via maintaining multiple ETGS instances with different levels of robustness; (2) establishing a sub-phase level synchronization mechanism for avoiding frequent matching conflicts caused by algorithmic randomness, and further identifying the optimal synchronization interval to balance the trade-off between communication cost and learning efficiency.
Similar to Lykouris et al. (2018), we introduce log T instances of ETGS to address the agnostic corruption. Specifically, we assign each instance distinct sampling probability, and probabilisti- cally select ETGS instances during the bandit learning. Intuitively. instances with lower sampling probabilities are statistically exposed to fewer corruptions, thereby achieving stronger robustness. However, critical challenge arises when players independently sample ETGS instances: frequent matching conflicts occur because players may select different algorithm instances in a given round, rendering the Round-Robin mechanism in the original ETGS ineffective. To resolve this, we intro- duce a synchronization mechanism wherein a unique leader is elected before bandit learning. This leader exclusively performs random sampling of ETGS instances at the end of each sub-phase and broadcasts the selected instance index to other players through arm pulls, ensuring all players operate on the same ETGS instance. This mechanism effectively eliminates potential matching conflicts. The details of leader selection and the synchronization mechanism are deferred to Appendix B Below, we outline the core idea of our mechanism. The leader selection can be implemented by designating player 1, who first obtains an index, as the leader at the end of Phase 1. To achieve synchronization across players, the leader can propose specific arm in predetermined future round the end of each sub- sub-phase, which is used to convey its selected layer index to the other players.
Trade-off' between communication overhead and learning efficiency. For the unknown corruption setting, we also divide the exploration phase into several sub- sub-phases. The difference is that the length of each sub-phase is set to a constant d. At the end of each sub-phase, the leader selects the f-th ETGS instance with the probability proportional to 2-( and broadcasts the index of the selected layer to other players by pulling arms. Then in the next sub-phase, players would propose arms based on the corresponding Round-Robin pattern of the selected ETGS instance, thereby avoiding conflicts. Intuitively, when the constant is set to 1, the proposed sampling strategy recovers per-round sampling used in Lykouris et al. 2018). It means the leader should communicate with other players in each round to achieve synchronization, resulting in a severe communication cost. While increasing d reduces communication overhead, it may amplify the corruptions experienced

---

Published as a conference paper at ICLR 2026
by the selected ETGS instance within each sub-phase (as formally analyzed in Lemma 3.4). This reveals a fundamental trade-off between the communication overhead and learning efficiency in sefting hyper-paramete d. Below, we minimize the regret bound w.r.t. d to select the optimal hyper-parameted Notice that observations collected in each sub-phase are solely used to update the statistics of the corresponding ETGS instance. Below we show that if the corruption level is at most C, then instances with & 2 log C will observe at most (Od log I") corruption with high probability.
Multi-layer ETGS race. The proposed algorithm is called race since we regard it as multiple ETGS instances racing to estimate the accurate preference ranks. If the E-th layer ETGS has estimated preferences well for all players based on its own statistics, players will rum the offline GS algorithm to identify the optimal stable match for this layer. In the remaining rounds. if one layer, whose optimal stable match has been identified, selected in sub- uuh--phaee, players would propose to arms following this optimal stable match in this sub-phase. Besides, if the ε-th layer has finished identifying its optimal stable match of, then optimal stable matches of of all layers l' < l would be modified to be the same as of. This is because the ETGS instance with lower sampling probability is slower but more precise. Intuitively, instances with lower sampling probabilities In the following, we provide a rigorous analysis of the fact that instances behave as without any corruption if they selected with the sampling probability lower than 1/C.
affected by less corruption.
Technical challenge. As previously introduced, our synchronization mechanism resolves matching confficts by delegating layer sampling to unique leader at the end of each sub-phase. However, this algorithm design renders the martingale concentration inequality from Lykouris et al. (2018), which developed for per-round bandit instance sampling, inapplicable our algorithm. To address this challenge, we derive a sub-phase level martingale concentration inequality that establishes the high- probability bound on the total corruption observed by the ETGS instance with sampling probability 1/C. Based on this inequality. we can design reasonable confidence intervals below. Below we provide a lemma to show that the amount of corruption that actually affects the layer with sampling probability 1 1/C is at most O log T).
Lemma 3.3. In Algorithm 2 the ETGS instance with sampling probability less than 1/C experiences, w.p. at least 1/T, cumulative corruption bounded by d log(T)) + 2 during the exploration phase.
We provide the detailed proof of this lemma in Appendix D
Algorithm 2 Multi-layer ETGS race (from view of player p.)
1: Input: player set N,, arm set K. horizon T. the fixed length d for any sub-phases k in Phase 2
2: Initialize: 2E, = 0, TV = 0, vij e [K], Vê E [logT]
3: Phase 1: the index estimation phase in ETGS
4: //Phase 2, learn the preferences
5: for k- 1.2...... do
6: F = False //whether the preference of instance E has been estimated well 1 (d + 1 1+ ++.) + 1, 1...., N Ex= (d + + cw.) + d do
7: for N + Ek=1
8: Select (!) based on the corresponding Round-Robin pattern of layer
9:
Observe (e,A,(e)((
(1) and update Ai(,,,117 Tt. if (( Ai(()
(1))(1)
10:
to + N + E
Ckr)
11:
Compute UCB and LCB,, for each j E [K] defined in Eq. ()
12:
of of
LCB,
13:
if 1 N then
14:
Find the optimal stable arm with of = (a of ff................... of xx via the decentralized offline
GS algorithm, and set the optimal stable matches of of all the layers ll < the same as of if p; is the leader then
15:
Sample layer & [log]] with probability 2- With remaining prob, sample é = 1 Communicate f to other players via pulling arms in [e] rounds
17:
We then formally introduce the proposed Multi-layer ETGS race algorithm for the unknown corruption setting. This algorithm maintains & = 1 log T different instances of ETGS. Each instance E []ogT] keeps its own empirical mean pf,, corresponding to the average empirical reward of the match between pt and aj. and also keeps track of how many times ay was matched with p; in this
7

---

Published as a conference paper at ICLR 2026
instance T- At the end of each sub-phase, the elected leader samples E 2- and broadcasts to other players by pulling arms. Based on Lemma 3.3
[log T"] with probability
we can define the same
width of the confidence interval for p: and 0j in the ε-th layer as V TV,
log
T+2
By properly
Th
selecting d we can ensure that d log T + < 2d log T, and the corresponding UCB and LCB for each layer can be thus defined as
Glog T
2d T
6logT
2dlog T
UCB = -p..j +
+
LCB = ph.s
T (5)
T
Then we provide the regret guarantee for Algorithm 2 and defer its proof to Appendix
Theorem 3.4. When configured with confidence intervals of width
6logT The TV ETGS race algorithm achieves the player-optimal stable pseudo regret of each player Pt E EN Reg,(1) s (N + 2 log T + 22 K log T + N log T') Ai,ax
+
2d the Multi-layer
Term (a)
14l T
d dlogg T
24logT
dlogr)
+ 16K log T
+ +6KC
+
A Ai,ax
2
A
A
Term (b)
22llo'
T
log"r T
24Clog' T
C'log T
+ 16K 16K log T
+
+
A i,max
dA
A
dA
A
(c)
KdlooT((log) C)) +
K log T T(oo T C)
K log" ToooTooogT +C)
dA
A
(6)
Remark 3.5. We first explain each term this upper bound. Term (a) captures the regret incurred well from bad concentration events. Term (b) reflects the regret due
in phases I and to exploration within each sub-phase. Term (c) accounts for the regret arising from the total communication cost between sub-phases. As previously introduced, we select the optimal hyper- parameter d to minimize this regret upper bound. In specific, we set to be O(yoogT) and the upper bound becomes O(K log 1.5 T know that all ETGS instances finish their respective exploration phase with true optimal stable matches. For this scenario, the regret is at most O log2.5 T/A² K log T/A). The additional multiplicative log² T term is from the required rounds of finishing the exploration of log T ETGS instances and O(log T) communication cost to acheive synchronization. When N = 1, there is no need use the synchronization mechanism for avoiding matching conflicts. Thus we know that the regret is at most O K log T(log T + C)/A) at this time.
A + K log" T(log' + ()) When C O,
Proof sketch. For the layer r E [log 7'] whose sampling probability satisfies 2- S 1/C, the corruption it experiences
most O log 2') with high probability. We can thus regard these layers as robust with purely stochastic feedback. The remaining problem is to bound the regret contributed by layers that are not robust to the corruption. We know that there exists some layer E satisfying e = arg ming(2 >> C). According to our algorithm, when its stable match of is identified, the stable matches of of layers l' l would be replaced with of and thus there is regret for these faster layers in the remaining rounds. In expectation the sub-optimal arm is played as most C times more in faster layers f' compared with that of the layer t", and we can bound the regret contributed by layers l' < l" by this analysis.
We then provide a table to summarize the regret and communication cost of two proposed methods under different setting, respectively. [holessshowss that for the regret upper bound of our proposed algorithm dealing with the known corruption setting, the corruption level C serves as an additive factor in O(K log A/A² KC/A), which is independent of T. Besides, the communication cost of this algorithm is (log log T/A + KC/A)) level. which aligns with that of the original ETGS. As for the proposed Multi-layer ETGS race method handling unknown corruption, its regret upper
8

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of regret and communication cost for known C/ and unknown C' settings
Regret Bound
Communication Cost
Known C'
O
K K KC O (log A
K Klog Kō
A
Unknown C
K(log T + C3) log!.5 T
32 + ylogT
bound is around OKK log" logo T/A2 + ('ooog//A2)) Compared with the known C' setting, the additional multiplicative log" factor in the regret bound stems from running log T ETGS instances simultaneously and using at most TT rounds to communicate for achieving synchronization. Notably, in Multi-layer ETGS race for unknown corruptions, both communication cost and regret share the same order (due constant sub-phase length d) while exhibiting sublinear scaling with respect to T, resulting in practically feasible communication overhead.
LOWER BOUND
In this section, provide regret lower bound for the bandit learning in decentralized matching markets with adversarial corruption. We mainly use the techniques in Sankararaman et al. (2021)
Gupta et al. (2019) to prove this lower bound. The proof details are included in Appendix
Let (2, T) denote the cumulative regret of policy on the instance with arm distributions {Ui
[N].j E [K]} for a horizon of length T. Here, P denotes the set of all probability distributions with bounded support [0. 1]. This paper focuses on class of policies termed uniformly consistent policies, defined as follows: A policy π is called uniformly consistent if satisfies for
all / P. all a E (0, 1), the regret lim supt T
(r( = O. This definition is used to eliminate tuning a policy to the current instance while admitting large regret in other instances. Before providing the lower bound, we first introduce a sub-class of bandits, where the stable matching is optimal. Specificallyy consider bandit instances where dominated arms bad, i.e. for any instance
in this class, for all players E [N], Pbj < (sy( for all arms E [K] \ (o()). We call this class of instances Optimally Stable Bandits (OSB), as each agent is matched with its optimal arm in the stable matching. For OSB, another metric Á == min (e[] Ms Pa.j is commonly used to characterize the problem's hardness.
Theorem 4.1. For any player i E [N], under any decentralized universally consistent policy n. there exists OSB bandit instance with Bernoulli rewards, where the regret of agent i is lower bounded as -GG) K
log (T) 2 22 max ((i (1- 1 R
Klog
Á + +c]).
(7)
Remark 4.2. From Table 7 we know that the proposed robust variant of ETGS for the known corruption setting near-optimal since the regret upper bound matches the lower bound, except for slight difference in the definitions of the preference gaps A and Â. We claim that the mismatch between A and Â is actually a fundamental open problem in the study of matching markets (even without corruption). ) It reflects the intrinsic difficulty and cost of achieving stable matchings through agent exploration and interaction. The best known lower bounds in the literature are established for the OSB setting and depend on the gap å (Sankararaman al. 2021). For the unknown-ccrrruptoon setting, we first note that gap, steming from the different definitions of A and P, still remains between the regret upper bound of the multi-layer ETGS race method and the lower bound. Moreover, our algorithm's upper bound incurs an additional multiplicative log T factor compared to the lower bound. The multiplicative log" factor arises because our method maintains log T ETGS instances to estimate the unknown C, and uses at most log rounds for communication at the end of each sub-phase to achieve synchronization. These deteriorations in regret stem from the hardness of coordinating players in decentralized matching markets.
5 EXPERIMENTS
In this section, we conduct simulation experiments to validate our theoretical findings. For the simulation setup, we set N 5 and K and consider that the preference rankings are generated

---

Published as a conference paper at ICLR 2026
random permutations. The preference gap between any adjacent ranked arms is set as 0.2. The feedback (t) for p; on aj at is drawn independently from the Gaussian distribution with mean Mi,j and variance 1. We adopt the corruption strategy proposed in Wang et al. al. (2024). We report the maximum cumulative player-optimal stable regret across all players. The results are averaged over independent runs with standard errors. We first compare our ETGS with widened confidence intervals and Multi-layer ETGS race with below baselines; Vanilla ETGS (Kong & Li 2023), Phased ETC (Basu al. 2021), and AETGS-E (Kong al. 2024), all achieving player-optimal stable regret in decentralized matching markets. We evaluate all baselines under the corruption budget C' 4000 over 500000 rounds. As shown in Figure [(a]] two proposed algorithms incur the lowest cumulative regret among all baselines. We then investigate how varying corruption levels affect our algorithms, and set three corruption levels (C E {1000, 2000, 4000)) to explore their effect on our algorithms. For this experiment, we set the sub-phase length d = 1 for Multi-layer ETGS race. Figure [ shows that the regret of our algorithms increases with higher C. Besides, the algorithm with prior knowledge of C' outperforms the one without, under the same budget. Next, fixing C = 1000, we explore the influence d on Multi-layer ETGS race. The sub-phase length d is set over 10, 10, 50} to investigate its influence on Multi-layer ETGS race. Figure [[cc depicts that large d (d = 10 and d = 50) worsens the performance of Multi-layer ETGS race, consistent with our theoretical findings on the trade-off between communication overhead and learning efficiency. Finally, we present a thorough empirical analysis of the optimal choice of the hyperparameter d. We evaluate our method over d E {1, 4, 6, 8). Recall that our theory suggests the optimal sub-phase length should satisfy d = O Voo I xe 4.3. In Figure ((d) we observe that settings with d = 4 outperform the other choices, which aligns with our theoretical findings.
Base mathods under 4000
Different comuuptinn
algorithms dee
CTGC with wildered Radius Palli laye
45K
atviiiinn enf:
1000
Wesmumm
135
S3C
300
22.00
12.00
<boc
Round e
Round
(a) Regret comparisons.
(b) Effect of corruption levels.
Mulli byer ETGS 1200 under C-1000
Nuti layor ETCS race under C=1050
Mesimmm Laam-datiie (eggee
30%
Mextmmm Cammila commuattive Teggett
500
subunees argin di
B3K-
E3C
b00
39C-
110
enght And
23.6
3300
2008
500K
Round
Round
(c) Effect of sub-phase length.
(d) Exploration of the optimal d.
Figure I: Experimental comparisons of baselines, and the effect of C andnd on proposed methods.
6 CONCLUSION AND LIMITATIONS
This paper studies a novel bandit learning problem in decentralized matching markets under adver- sarial corruptions. We propose robust ETGS variant to tackle known corruptions, and develop a Multi-layer ETGS race method to handle unknown corruptions. We derive regret upper bounds for both algorithms and also provide lower bound to demonstrate their tightness. An important future direction is to design robust algorithms that achieve much higher communication efficiency in unknown corruption settings.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
The corresponding author Fang Kong is supported by National Natural Science Foundation of China (62506150) and Guangdong Basic and Applied Basic Research Foundation (2025A151501141)),
ETHICS STATEMENT
This work is entirely theoretical and does not involve human subjects, personal data, or sensitive information. The research focuses on developing mathematical foundations and providing rigorous proofs for theoretical results in bandit learning. We do not foresee any direct ethical concerns, including issues of privacy, faimeess, security, or legal compliance, arising from this work.
REPRODUCIBILITY STATEMENT
All mathematical statements in our paper fully specified: clearly state all definitions, assump- tions, lemmas and theorems, and provide complete proofs in the main text and appendix. addition, for the simulations included in this paper, provide detailed descriptions of the simulation setups. While our work does not depend on external datasets, the combination of theory and simulation documentation ensures that readers can fully reproduce and validate our results.
REFERENCES
Atila Abdulkadiroğlu and Tayfun Sönmez. Matching markets: Theory and practice, Advances in economics and econometrics, 1:3-47, 2013.
Peter Auer and Chao- Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory, pp. 116-120. PMLR, 2016.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235-2566 2002.
Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. Beyond log) regret for decentralized bandits in matching markets. In International Conference on Machine Learning, pp- 705-715. PMLR, 2021.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandit algorithms with supervised learning guarantees. In AISTATS, volume 15 of JMLR Proceedings, pp. 19-26. JoLR. 201
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial ban- dits. In Conference on Learning Theory, pp. 42-1. JMLR Workshop and Conference Proceedings, 2012.
Sanmay Das and Emir Kamenica. Two-sided bandits and the dating market. In IJCAL, pp. 947-952. Professional Book Center, 2005.
John Dickerson, Karthik Sankararaman, Aravind Srinivasan, and Pan Xu. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Transactions on Economics and Computation (TEAC), 9(3):1117, 2021.
David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American mathematical monthly, 69(1):9-15, 1962.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In COLT, volume 99 of Proceedings of Machine Learning Research, pp. 1562-1578. PMLR, 2019.
Hameed Hussain, Saif Ur Rehman Malik, Abdul Hameed, Samee Ullah Khan, Gage Bickler, Nasro Min-Allah, Muhammad Bilal Qureshi, Limin Zhang, Wang Yongji, Nasir Ghani, al. A survey on resource allocation high performance distributed computing systems. Parallel Computing, 39111):79--736 2013.
11

---

Published as a conference paper at ICLR 2026
Fang Kong and Shuai Li. Player-optimal stable regret for bandit learning in matching markets. In SODA, pp. 1512-1522. SIAM, 2023.
Fang Kong, Yueran Yang, Wei Chen, and Shuai Li. The hardness analysis of thompson sampling for combinatorial semi-bandits with greedy oracle. In NeurIPS. pp. 26701-26713, 2021.
Fang Kong, Zilong Wang, and Shuai Li. Improved analysis for bandit learning in matching markets. Advances in Neural Information Processing Systems, 37:91904 91929, 2024.
Fang Kong, Jingqi Tang, Mingzhu Li, Pinyan Lu, John C.S. Lui, and Shuai Li. Bandit learning in matching markets with indifference. In The Thirteenth International Conference on Learning Representations, 2025. /
net/ wwwp:/eneeee/eeeeeeeee www.ummmdddNNaassmmmmm
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Shuai Li, Zilong Wang, and Fang Kong. A survey on bandit learning in matching markets. In IJCAI, pp. 10546-10554, ijcai.org, 2025.
Shiyun Lin, Simon Mauras, Nadav Merlis, and Vianney Perchet. Stable matching with ties: Ap- proximation ratios and learning. In The Thirty-minth Anmual Conference on Neural Information Processing Systems, 2025. URL https: /ttp:////ppeeeeeeeeeemmee http:wiwwwweeeeeeeeeeeeeeeeeeeee
net/ forum heeerrummidd-pmmmemme HDmDHg
Lydia T Liu, Horia Mania, and Michael Jordan. Competing bandits in matching markets. In International Conference on Artificial Intelligence and Statistics, pp. 1618-1628. PMLR, 2020.
Lydia T. Liu, Feng Ruan, Horia Mania, and Michael Jordan. Bandit learning in decentralized matching markets. Mach. Learn. Res., 22:211:1-211:3 2021.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. pp. 114-122, 2018.
Richard Oentaryo, Fe-Peng Lim, Michael Finegold, David Lo, Feida Zhu, Clifton Phua, Eng- Yeow Cheu, Ghim-Eng Yap, Kelvin Sim, Minh Nhut Nguyen, et al. Detecting click fraud in online advertising: data mining approach. The Journal of Machine Learning Research, 15(1)999-140, 2014.
Satyanarayana Pamarthi and R Narmadha. Literature review on network security in wireless mobile ad-hoc network for iot applications: network attacks and detection mechanisms, International Journal of Intelligent Unmanned Systems, 10(4):482-506, 2022.
Alvin E Roth and Marilda Sotomayor. Two-sided matching. Handbook of game theory with economic applications, 1:485-541, 1992.
Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. Dominate or delete: Decentralized competing bandits in serial dictatorship. In International Conference Artificial Intelligence and Statistics, pp. 1252-1260. PMLR, 2021.
Aleksandrs Slivkins. Book announcement: Introduction to multi-armed bandits. SIGecom Exch., 18 (1):28-30) 2020.
He Sun, Mingjun Xiao, Yin Xu, Guoju Gao, and Shu Zhang. Privacy-preserving stable crowdsensing data trading for unknown market. In IEEE INFOCOM 2023-IEEE Conference Computer Communications, pp. 1-10. IEEE, 2023.
Xuchuang Wang, Jinhang Zuo, Xutong Liu, John Lui, and Mohammad Hajiesmaili. Stochastic bandits robust to adversarial attacks. arXiv preprint arXiv:2408. 2.X::2408.08859, 2024.
Zilong Wang and Shuai Li. Optimal analysis for bandit learning in matching markets with serial dictatorship. Theor. Comput. Sci., 1010:114700 2024.
Linfeng Zhang and Yong Guan. Detecting click fraud in pay-per-elick streams of online advertising networks. In 2008 The 28th International Conference on Distributed Computing Systems, pp. 77-84. IEFF, 2008
12

---

Published as a conference paper at ICLR 2026
YiRui Zhang and Zhixuan Fang. Decentralized two-sided bandit learning in matching market. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference Artificial Intelligence and Statistics, pp- 467-475. PMLR, 2019.
13

---

Published as a conference paper at ICLR 2026
APPENDIX
In the appendices, we provide more details and results omitted in the main paper. The appendices are structured as follows:
Appendix provides the related work part of this paper.
Appendix provides the missing details of the algorithmic procedures.
Appendix provides the proof of Theorem 3.1
Appendix
D
provides the proof of Lemma 3.3
Appendix provides the proof of Theorem 3.4
Appendix provides the proof of Theorem
Appendix provides the LLM usage disclosure of this paper.
A RELATED WORK
Multi-armes bandits (MAB) have been extensively studied due to their broad applicability in sequen- tial prcision-making tasks (Slivkins) 2020, Lattimore & Szepesvári 2020). Learning optimal stable matches for matching markets Gale & Shapley (1622): Li et al. (2025) with unknown preferences has become one of the important applications of MAB. Early work by Das Kamenica (2005) introduced the bandit problem in matching markets, where multiple players and arms occupy opposing sides. Liu et al. 2020) later examined variant with unknown one-sided preferences in general markets, deriving key theoretical guarantees. Further advancing this line of research, [iu et al. (202T): Kong ct al. (2021) investigated decentralized matching markets where players act independently without central coordination. Saankaaraman et al.) (222)): Wang & Li (024) consider scenarios in which participants' preferences adhere to specific assumptions to enhance learning efficiency. Kong & Li (2023) analyzed player-optimal stable regret in decentralized settings critical metric for practical applications. More recently, Kong et al. (2024) propose novel algorithm and refined analysis to achieve an improved regret bound for this problem, and Kong et (2025): Lin et al. (2025) study the potential indifferent preferences in matching markets.
Another line of MAB research explores stochastic bandits with adversarial corruptions. For instance, Lykouris et al. (2018) proposes randomized bandit algorithm robust to adversarial corruptions of stochastic rewards. Specifically, they consider setting where the reward generated by each arm pull is stochastic but may be perturbed by adversary before being revealed to the player. The result was subsequently improved by Guupt al. (2019). Besides bandits robust to adversarial corruption, there is another line of works on best-of-bothe wowooofooohwooffteeoo (BoBW) and best-of-three three-worlds (BoTW) algorithms that aim to achieve near-optimal regret automatically adapting to stochastic, adversarial, and corrupted regimes. Early BoBW approaches design algorithms that perform competitively in both stochastic and adversarial settings by carefully combining exploration and exploitation mechanisms (Bubeck & Slivkins 2012). Follow-up work further refines these ideas to obtain nearly optimal pseudo-regrer guarantees across these regimes (Auer & Chiang 2016) Zimmert Seldin 2019). In particular, ZZimmert& & Seldin (2019) propose essentially optimal FTRL--based method with Tsallis-entropy regularization, which attains tight pseudo-regret bounds simultancously in the stochastic and adversarial cases.
However, most existing work on stochastic bandits with adversarial corruptions focuses on the single- player scenario, with few studies addressing bandit learning in matching markets under corrupted feedback.
B DETAILS OF ALGORITHMIC PROCEDURES
In this section, we present the complete workflow of the vanilla ETGS algorithm Kong & Li (2023 and the monitoring subroutine used in our proposed algorithms. We then present the details of the leader selection and synchronization mechanism used in the Multi-layer ETGS race method.
14

---

Published as a conference paper at ICLR 2026
B.1 WORKFLOW OF VANILLA ETGS
First, provided the algorithm procedure of the vanilla ETGS in Algorithm to clarify the missing details of Phase and Phase used in our proposed Algorithm
We emphasize that for our presented Multi-layer ETGS race method, designed to address unknown corruptions, its Phase implementation is identical to that of the vanilla ETGS. Additionally, Phase 3 of the vanilla ETGS operates decentralized Gale-Shapley algorithm (Gale & Shapley (962)). Consequently, the procedure of identifying the optimal stable matching in Algorithm follows the same Phase 3 protocol the vanilla ETGS.
Then we formally introduce the workflow of the vanilla ETGS. The first phase of ETGS proceeds in N rounds (Line B At the first round 1, all players would propose arm 0₁ (Line 6 and only the player who is successfully accepted gets the index 1 (Line S). In the second round, all of the other players (except for the player who gets index 1) still propose 01 (Line 6 and the only accepted player gets the index 2 (Line 8). Similar actions would be taken in the following rounds 3, ......V. .N. Intuitively, the index of each player P: is just the order of p: the preference ranking a1. At the end of this phase, each player can obtain distinct index. For the third phase (Line 24 28). it can be regarded as a decentralized Gale-Shapley algorithm (Gale Shapley 1962). During this phase, players aim to find and focus the arm in the optimal stable matching with the estimated ranking o, Specifically, p; would propose to arms one by one according to o, until no rejection happens. When each player estimated ranking o; for the first N arms is accurate, this procedure is expected to find the real optimal stable arm for each player.
Algorithm 3 explore- Gaae--GGle------a- (ETGS, from view player p.)
Input: player set N, arm set K., horizon
2: Initialize: رi,j 0, T 0, Vj E [K]
3: //Phase 1, index estimation
4: Arm d1
5: for round = . do
.......,,.
6: A:(() AAm
7: if (1) = (1(() = an then
8:
Index L; Arm 02
9: //Phase 2, Iearn the preferences
for 1. do
11:
F. False //whether the preference has been estimated well
12:
for N Eh_1 (2 + +) 1,...,., .
E/-1 (2" +1) 2 do
13:
(t) = +t
14:
Observe (1.A,(1) and update (i,A,(1), T2,A,(9 if At()) A:(()
15:
Compute UCB,,, and LCB,,5 for each j E [K]
16:
if 3o such that LCB;, UCB for any k [N] and LCB, UCB for any
A = N + + 2.... K then
17:
F True and 0;
18:
Initialize Oz =0
19:
1= N - (2 + + 2 +1
A,(t) Oidexx Ff True and A₁ otherwise
21:
Update Or UrE[N] (1)
22:
if [O = N then
23:
Enter Phase with σ; 12 = t l/t, is the round when phase 2 ends //Phase 3, find the optimal stable arm with 0i,. o.
24:
25:
Initialize s
26: for
1, la 2........ do
27:
(!) = aa..
28: = s + if (t) =
15

---

Published as a conference paper at ICLR 2026
B.2 THE PROCEDURE OF MONITORING SUBROUTINE
In this subsection, we provide the procedure of the monitoring subroutine used in our algorithms in Subroutine
Subroutine 4 Monitoring
1: Input: {UCB.J. LCB.,jjeKKK
2: if 3o such that LCBi,,, > UCB for any n [N] and LCB3,oN > UCBi,a, for any
n N + 1, N + 2,... . then
3: FA = True and
4: Initialize O
5: tkk
6: (t) = OIneex if F == Truc and A;(t) otherwise
7: Return o; and O2 = UveN (A)(
Then we provide the motivation behind this monitoring subroutine. The core idea of this monitoring sub-routine that, for each player E [NV] they use the feedback observed during the current sub- sub-phase to compute UCB,, a. and LCB,. for all arms à E [K]. The player then determines whether her preference ranking has been successfully estimated by checking whether the confidence intervals of all arms are mutually non-overlapping. After that, the player checks whether all other players have already estimated their respective preference ranks determine whether to proceed to the next phase.
B.3 THE PROCEDURE OF LEADER SELECTION AND SYNCIRONIZZTTIE MECHANISSM
In the following, we introduce the details of leader selection and the synchronization mechanism, which are used our proposed Multi-layer ETGS race method.
B.3.1 LEADER SELECTION.
The procedure of leader selection is as follows: leader is designated before the exploration phase begins, once each player has identified their own index. Specifically, at the end of Phase I-when players obtain their respective indices-the protocol can simply assign Player (i.e., the first player to acquire an index) as the leader.
Reliability of leader selection. As mentioned above, this protocol designates the player who first successfully acquires index as the leader. All other players can observe the successful match between this player and arm and they then recognize player as the leader in the subsequent exploration phase. Based on the above procedure, there will always be a first player who successfully matches with arm 1, and thus there will always be player selected as the leader. Therefore, it is difficult to disrupt this leader selection mechanism.
B.3.2 SYNCIRONIZATION MECHANISM.
We observe that in decentralized matching market, communication among players is realized through arm-proposing, where each player infers information by observing the arms pulled by others, the direct communication among players (Kong & Li 2023 Basu et al. 2021). Consequently, to implement the synchronization mechanism at the end of each sub-phase, the leader may spend up to log T additional rounds proposing specific arm based on the result of layer sampling. By observing which arm the leader pulls, all other players can infer which layer (ETGS instance) they should enter in the next sub-phase.
C PROOF OF THEOREM 3.1
In the following, for convenience, let (t), Tt)(t)), UC),, LCB,, be the value of Tes, UCB and LCB,, at the end of round t, respectively. Define F
{3t E [T] E [N]. E [K] (t, payl Glog + T.
G as the bad event that some pref-
T.
16

---

Published as a conference paper at ICLR 2026
erence is not estimated well during the horizon. Besides, the notation Pt,j to denote the oracle empirical mean calculated by stochastic reward ri. (t) without any suffering comruption.
To provide the regret upper bound of the proposed Algorithm I for the known corruption setting, we first upper-bound the probability of the bad event J defined above.
Lemma C.1. The upper bound for the probability of inaccurately estimating preferences is
P(F) 22NK/T.
(8)
Proof.
6logT
C
P(F) & P
Br,i (Pa -Masl
(t)(t)
(ty(t)
6 6log
< P
3,, i,j : (1) Payl + (1=,)(1) - -iassl >
(!)(1) + (i)(1)
6loo T
P P
3t, i (p4((t) paol V (i,(1)
+P
3t,igj (Pac(t) Misl
Ti,
(a) P
6log T V (t)
31, i. (1s Men1
6 T
ΣΣΣΣ
Tiy(1) s, (T,(()) piol
8
ΣΣΣ t- 2x2e
JE[K
< 2NK/T,
where (a) holds due to the definition of C, and (b) holds since the Hoeffding's inequality.
In the below Lemma we show that given "F, once player ps observes that the UCB of an arm oj smaller than the LCB of another ag,, we able to conclude that ps truly prefers az to aj- Lemma C.2. Conditional on F, JCB,,(t) (t) LCB., (t) implies paj < pig'
Proof. Given FF, know that 14 [T), E [N], [K], (() Mell S
6log T (t))
Then we have
6log T (t,
C (t)(t)
(CB (t,)(t)
V
(0)
GlogT (t,)
(i.s
$ Mi.
(10)
6log T (t)
pis
(6)
GlogT
C (t,(t)
Pi.j +
(t,
UC),,,
where (a) and (b) hold since the definition of C.
Thus, given FF, we have Pig (C) < (C) < m.g.
17

---

Published as a conference paper at ICLR 2026
The following Lemma C.3 provides upper bound for the number of observations required to estimate the preference ranking for any player p, well.
Lemma C.3. In round i, ler T.()) minze[k] (i,(!) and T; 381 + SC Conditional on FF, if > Tú have LCB, LCB (t) > UCB pLat1 (t) for any k [N], and po (t) > UCBr,ppd (1) for any k- = N 1, + K.
Proof. By contradiction, suppose there exists k [N] such that pC (1) UCBi,p (1) or there exists N 1, NN + 2, ..... K such that LCB (t) S UCB, p... (t), Without loss of generality, denote j as the arm in the RHS and j' the arm in the LHS in above cases.
According to I and definition of LCB and UCB, we have
6 log Ti(1)
2C T(())
6 log
2C
Pa. - 2
S LCB (t) & UCB S Mij + 22
+ T.(I)
(11)
Ti(()
We can conclude that Aija pi.
Mis S 4
6log T T:(1)
+
4C TT())
(t)
384 log
SC
have
6 log T Ti(t)
4C Ti(t)
A LJs
96 log T
4C
384
384 log T A
(12)
A
A
+
2
This implies that Ti(1)=
384 log A
SC and thus contradicts the fact that T:(1) Tz.
According to the protocol of Algorithm I all players have the same observations, we conclude that all of them would enter the third phase simultaneously. Denote Lmax as the largest sub-phase number Phase 2. That is to say, players enter Phase the end of sub-phase Lmax-
Based on this observation and the lemmas provided above, we then provide the formal proof of Theorem 3.1 as follows.
Proof of Theorem 3.7 As introduced earlier, we denote Liaa as the largest sub-phase number of Phase 2, i.c., the preference ranks are estimated well after this sub-phase.
The optimal stable regret for player can be bounded as follows,
Regi (T)
(Mim) xx(())
I (A((t) # m²} Ai.max
NA, + E
Σ I(A(t) # m²H
Ai,ax + +P(F) T A Ai,ax
(13)
N=
Traax
N A max +
(de 1)+++)+M0 + +N
Aimax + -P(F)--. Ai,max
Lmaxe
NA i,max +
Σ
(dx + + N2
Ai,ax +NN A,max:
18

---

Published as a conference paper at ICLR 2026
where (a) comes from Lemma C.I
Based on Lemma C,3
we know that Phase 2 proceeds in at most Lmax sub-phases where
48 log T
)
Timax min k: dx 2 8K
(14)
A
==1
Recall that we select dR = 2 and set the confidence radius as on the definition of Lmax, have
6log T
Tii
+
Ti.3
C in Algorithm
based
Lemox
48 log T
C
2
S
16K
A
(15)
Hence have Lmax log
16K
48 1
2)) and the regret can be bounded follows
(Tg S [6K
48 48 T
+ log (I6K'
48 log T
2))) A max
+
A
A
(16)
+ NA, + N2 Dimax + 2N max.
D PROOF OF LEMMA 3.3
In this section, we provide the proof Lemma 3.3 We bound with high probability the total corruption suffered by the ETGS instance with sampling probability 1/C. Similar to Lykouris et al. (2018), we also use a Bernstein-style martingale concentration inequality.
Lemma D.1 (Lemma in Beygelzimer al. (201I)). Let XI...., .x be sequence of real-valued random numbers. Assume, for all t, that X₂ S R and that X . = O. Also let
V
X.-l-
Then, for any 8 > O:
6-2 R
IP
X, > Rln(1/8)
V 5
Let (t) be the corruption that is observed in the t-th round of the ETGS instance with sampling probability P = 1/C for the match between the player Pt and arm az. For every round f, Cz,ú(t) is the corruption selected by the adversary for the match of p; and aj- Tr denotes the k-th sub-phase. We define (k) as the total corruption observed the k-th sub- phase of the ETGS instance with sampling probability P 1/C for player i. In words, (k) is defined as Z, (k) = EiET, (o,A,(0)()) (t). According to our algorithm, 2, (k) is Bernoulli random variable: (k) = C((k) with the probability P and (k) = 0 with the probability -- P, where C,(k) Eien, (t).
Proof of Lemmaa 3.3
Then we define the martingale sequence as
(k)k) = (k) - T.. ((k k k-1)
(17)
where H(1 k 1) corresponds the history up to sub-phase k.
Note that
(x,()))) H(1 k- 1)]
- PC(())) -1-
P(1 - (( (k)
(18)
=P(1 - (P-
P(1 - (A))
19

---

Published as a conference paper at ICLR 2026
Since set the length of each sub- hub-ppase constant d, we can bound the term (C)(
following
Σ ci(t) 1)
(C;(k))}
(C,((t)
(c,(t))
S d Σ Ct(t), (19)
MET
SET
tET,
tET: inequality and the last inequality holds due to
LET
where the first inequality holds since C,(t) E [0, 1].
Therefore, summing over all the sub- sub-phases, the variance V becomes
V
E
(x,())))))((1
: 1)
(c((k))
P
Pd
Σ Ci(1)
(20)
1ET.
Pd Σ Ci(t)
SE[T]
< d,
where the last step holds due to the definition of C and P J. Then we turn upper-bound (k) as follows,
(k) (k: E (k)
Σ (tt
(21)
TЕT
d,
where the last inequality holds since the rewards are in [0, 1] (thus the instant corruption for each match in one round should be in [0, 1)).
Applying Lemma D.I we show that, w.p. 1 - +:
Σ x((k)) S dloog(T) + (e-20 2
d
k
(22)
< dlog(T)) +
= dlog(T) +1
We also know that
(1)) k -1
E. ((:)))((1=
P
Σ Ci(k)
(23)
T
Σ (IA.(o())
1
To sum up. w.p. 1 I the total corruption incurred by the ETGS instance with P= 4 for player i is
7.
Σ Z..A.(0(())
Σ Xi(k) x((k)+ + Σ Z((k) -
(24)
< dlogg()) +
20

---

Published as a conference paper at ICLR 2026
E PROOF OF THEOREM 3.4
For each layer l E [log T), we denote (t) (t), (t), K T UCB and I,C,, the end of round t, respectively. In the following, define F 3 31 [T] [N],e e [K] |,,000) mal V
LCB (t),
as the value of
/o + ldg T as the event that some
(T) TV, T(,(0)
preference is not estimated well during the horizon for the L-th layer. Besides, denote Fo the event that there exists one ETGS instance of those layers E" E [log 7] whose sampling probability satisfying 2- < 1/C, the actual experienced total corruption of some player in this instance is larger than dloo T 2. And we define the bad event (Ure (iee)log7FFF3 F3) Fc.
In the following, we also give an upper bound for the probability of the bad event F.
Lemma E.1. The upper bound for the probability of the bad event F is
2N K log
Nlgg
P(F) - T
(25)
Proof. We first define the notation Cf as the actual total corruption experienced by the f-th ETGS instance of player i. Recall that we select the constant satisfying log I + 2 S 2d log T,, we can thus upper-bound the probability of the bad event F follows
P(F) v
Σ RE[log T]
GlogT
2d log T (1
P i, (1),(() - Ma.i >
V Th
+
EE(log?! 21
Σ
P(3:: : o (T) 2dlo)(())
(26)
82 'g//c
Σ
Σ
Σ
t. t-2exp(-31n1) + Σ log T
T
(E(log T] KE[T] [E[N] jE[K]
iE[N]
2NK log T N log
T
T
where (a) holds due to selection of enlarged radius for the unknown C' setting, and (b) holds based on the similar analysis the proof Lemma C.I and Lemma 3.3
Based on the results of Lemma 3.3 we know that the actual corruption suffered by the layers satisfies that 2 > C, E [log 7| is most d l'log T + 2. Since select the constant d satisfying dog + 2 < 2d 7 and set the confidence interval as log have the following results.
+ 2d T Ti,
we can immediately
Tí
Lemma E.2. round t, let (t) minje(K] (t)(t) and T
384 log T A
+
2d Tog
Conditional
on FF, ()) > Té. we have ICB ,p,, (1) > UCB! UCB
pp (1) any &o E [N], and LCB, p. (1)
UCB a. (t) for any le = N N + 2...., K.
Below, we present the proof of Theorem 3.4
21

---

Published as a conference paper at ICLR 2026
Proof of Theorem 3.4
The optimal stable regret for player can be bounded as follows,
Regi (T) E
(umm - Xx(1)]
- E
H{t(t) & m"}
mi,xax
(27)
N A max + E
Σ
T((())
Ai + P(F) T Aimax
I=N+1
& (N + 2N log T + log T) + E
Σ N++1
[(A(t) * #m"}| A.max:
where the last inequality comes from Lemma
In the following, we focus on the regret contributed by those layers whose suffered actual corruption smaller than C, and the regret contributed by the layers that are not tolerant to the corruption C,
respectively. We first define the minimum layer that is robust to corruption: 8" arg ming [2 C7.
Hence, for the robust layers L' > e" according to Lemma 3.3 and Lemma E.2 we can establish
regret upper bound 16K( log T log T i,,aa. Since there are at most log T layers, the total
A
A
A regret coming from these robust layers is 16K log ( 24 dlog T) Aimax.
For the layers e that matches of these faster layers will be modified to keep the same as that of l" when f has estimated its own preference rank well. Hence, in expectation, this is at most C T times as every move in the layer L occurs with probability 1/C of these moves are matches of arm j while it is the optimal stable matching for the faster algorithms. Formally, we define the number of times that the optimal layer is selected T In expectation, know the layers l l have finished the estimation of their preference ranks before l" Thus, we have
tolerant to the corruption, i.e., 2 < C, we know the optimal stable
BTA.
Pt. T - T = CT TT; S CT
(28)
where Ti, denotes the number of times that layers l <<E E" are chosen.
Based on the above analysis, the total regret contributed by the faster layers is 16KC( 24 log dlog T
imax
According to the protocol of our algorithm, the number of sub-phases in Phase 2 is at log T
most [16K
d2a +
log? T
+ 24G T
ds + x T and thus the total communication cost is
[16K log T 24 log T
log 21 C C
d
dA
To sum up, the regret upper bound of Multi-layer ETGS is
(T)
24log 2
dlog T
(N + N2 log
2N KNKllg T
N log A 16K log T
Aimax
A
24g T
dlog T'
16KC
2
A
i.ax
24
log 2 T
24Clog
Cloog
+ 16K T
+
Aj,aa
2
A
dA2
A
=0 ((
(Kidlog
[Kdlog T(log T C)
K
Klog²
T(lo
T + C)
K log T(log T + +())
A jmmx
A
2
A
(29)
22

---

Published as a conference paper at ICLR 2026
F PROOF OF THEOREM 4.1
In this section, we provide the proof of Theorem 4.1 by utilizing the main results from Sankararaman et al. 2021); Gupta al. 2019).
Before providing the formal proof, we provide a vital lemma proposed in Sankararaman et al. (021). Lemma F.1. Under any decentralized universally consistent algorithm n, there exist OSB ban- dit instance with Bernoulli rewards, where the regret of player E [N] is lower bounded as [og
K log T }). where Á == min (E(N,,s5 Pey5 - -Ms...
max
A²
Proof Theorem 4.7 Recall that we define ,! == arg max (ly recursively and we denote } := M Pt.j and A == arg [in Hi.g!" Pt,j in the following.
For any player E [N), we know its pseudo regret under policy and any bandit instance
(V T) = Σ A + (B
(30)
SE[K]
where (t) denotes the number of time the agent is blocked up to time t.
We claim that this is true as for each matching conflict the player p; obtains Migt regret (0 reward) in expectation, and for each successful match of arm j it obtains AJ regret.
Based on it, trivial regret lower bound
(V, TT)
N
Σ JE[K]
(31)
To illustrate the effect of corruption on the problem hardness, below we follow the basic idea of Gupta et al. (2019) to conduct a finer- merrggrained analysis for Eq. (3T). In specific, for any player i E [N], we consider another bandit instance v: the deterministic reward of the optimal arm is Å and the reward of each sub-optimal arm is zero without any noise. Given that the regret defined in this paper is based adaptive adversary who inject corruptions based on the historical information, can thus consider weaker adversary here to provide a valid lower bound of regret. In specific, this weaker adversary swaps the rewards of matched arms with probability 1/2 each round. Thus, in expectation, there most total amount of LC/ A rounds where the rewards swapped during the first [2C/å] rounds. This makes the arms appear indistinguishable to the algorithm during these rounds.
Besides, know that in expectation the total amount of rounds where the reward of arm j [K] is corrupted is roughly - Then we have E' [N[Nj] 2 - where E' denotes the expectation operator taken over the randomness from the attacking strategy of the considered adversary.
Based on the above analysis, we have
Rt(
Σ
A
]E[K]
Σ ÅE [N)(T)]
(32)
C
(K - 1)
(CC),
where the second inequality holds since we consider a weaker adversary here instead of the adaptive adversary using the historical information to maximize the pseudo regret.
Applying Lemma
E.
we know that
lim inf (1)(v)
K
2
(33)
T log T
2
23

---

Published as a conference paper at ICLR 2026
Based on the analysis of these two instances, we have
(v) 2 max
K
log T
c] 2 2
K Klgg T
A +CJ.
(34)
Â
Referring to similar proof proposed in Sankararaman et al. (202I). we know that for an OSB instance, the number of times the players to 1) matches arm 1 successfully, the player p; should either move to sub-optimal arm or it is blocked. In the best possible scenario, P: successfully matches its second best arm, in each of these instances. This holds as Aini I Maj for non-negative rewards. Therefore, the regret from the events when players p1 to P matches arm jr successfully, is lower bounded following
( x)) 2 M Mags (B)
A min E By [
A [N
(35)
KÂ
Ω K
Σ
Similarly, applying Lemma F.1 and then we have
(v)
i-1
lim T+000 logT
>
(36)
A
To sum up, we have
(v) 2 2 ( 1)(
log T
A + G)
}
(37)
K
Combining the results in Eq. (33) and Eq. 37 we can roughly lower-bound the pseudo regret by
Reg. (T) Ω max (i - 1)(
log T
C
K KlogT
+c])
(38)
K
G THE USE OF LARGE LANGUAGE MODELS (LLMs)
We used large language model (LLM) only for editing correcting grammar, spelling, word choice, and overall phrasing to improve readability. The LLM did not contribute to research ideation, methodology, experiments, data analysis, results, proofs, or theoretical claims. All such components were conceived, developed, and validated solely by the authors. We assume full responsibility for the final manuscript, including parts influenced by the LLM, and declare that no content generated via the LLM constitutes plagiarism or scientific misconduct.
24


Reviews:
[{"review_id": "mjMCnJWrHK", "reviewer": "Reviewer_qjPx", "summary": "This tackles the problems of one-to-one decentralised matching with bandit feedback  under adversarial corruption, for the case where one side's (arms) preferences are known.\n\nThe decentralised matching works by players proposing to arms, and each arm accepting their most prefered player. The feedback here is corrupted, with stochastic rewards $r^S$ being modified to $r$ up to a total corruption budget $C$ over the horizon $T$.\n\nThe basic algorithmic idea is to take the corruption level into account when creating confidence intervals. This is first analysed for known corruption in 3.1, which results in $KC/\\Delta$ additional regret and in 3.2 for the case of unknown corruption.\n\nThe paper refers to an index estimation phase in some algorithms, to take care of conflicts. I personally find the decentralised setting to just add unnecessary complexity, without making the problem more interesting. If you have to force everybody to do a round-robin according to some indices, why not just force them to play according to some centrally defiend schedule? This would also avoid the complications with sampling in the unknown corruption case.", "questions": "? The paper refers to an index estimation phase in some algorithms, to take care of conflicts. I personally find the decentralised setting to just add unnecessary complexity, without making the problem more interesting. If you have to force everybody to do a round-robin according to some indices, why not just force them to play according to some centrally defiend schedule? This would also avoid the complications with sampling in the unknown corruption case. But maybe then the proofs would be too straightforward from Lykouris.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ It is a natural extension of the stochastic case.\n+ The proof is not a completely straightforward adaptation of Lykouris to matching.", "weaknesses": "- Maybe the decentralised setting is too complicated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dPFCXrRlWl", "reviewer": "Reviewer_UUKf", "summary": "The paper proposes a multilayer preference learning bandit algorithm that can adapt to an unknown level of corruption. Numerical experiment corroborated the theoretical findings and shows an advantage over existing approaches.", "questions": "See the previous section", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I find the paper to be well written, with a clear storyline, strong motivation, and sufficient explanation of the technical challenges. In particular, the authors effectively use concrete examples to illustrate why a two-sided market with corrupted feedback is an interesting and relevant setting. The discussion of the technical difficulties and the insights provided is also sufficiently detailed and informative.", "weaknesses": "- From the paper itself, it is not entirely clear how the algorithm's overall computation complexity scales as $K$ and $T$ grow. In particular, it is unclear how well the monitoring subroutine scales compared to existing approaches for online learning in a two-sided market.\n- The authors commented on adversarial feedback. Would an FTRL/FTPL-type algorithm achieve a best-of-three-worlds guarantee in the sense that it achieves the same regret in all stochastic, corrupted, and adversarial environments? Can the authors comment on the related works in this direction and outline the technical difficulties in unknown corruption level, and why this is not a suitable algorithmic framework to consider for this setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lXDwkNPyEu", "reviewer": "Reviewer_dRww", "summary": "This paper investigates an online learning problem in two-sidd decentralized matching markets where stochastic rewards are subject to malicious adversarial corruptions. The goal is for N players and K arms to identify the player optimal stable match whilst minimizing the pseudo-regret. The problem is first studied when the corruption level C is known, where the proposed algorithm achieves a regret upper bound that is shown to be near optimal with corresponding lower bounds. The authors extend to the setting of unknown C by coordinating exploration among $O(\\log T)$ parallel running instances of their original algorithm. They validate their results with some empirical results as well.", "questions": "1. Is the multiplicative redundancy $\\log^2 T$ on the regret bound of unknown C fundamentally unavoidable given the layer based approach? Is there a possibility of reducing the overhead to tighten the optimality gap, mye by using alternative communication strategies or nonuniform synchronization intervals?\n\n2. In Remark 3.5, the optimal choice ofor hyper-parameter $d$ is theoretically derived as $O(\\sqrt{\\log T})$ to minimize the regret bound. Figure 1(c) shows that larger $d$ values worsen the empirical regret compared to $d=1$. Can you provide a deeper empirical discussion on the optimal $d$ value?\n3. The upper bounds utilize the minimum preferene gap $\\Delta$, while the lower bound utilizes $\\tilde{\\Delta}$ specific to Optimally Stable Bandits. Can you clarify the relationship between these two metrics? Does the near-optimality established in Remark 4.2 hold because $\\Delta$ and $\\tilde{\\Delta}$ are equivalent under OSB? Is the derived lower bound also applicable to the general setting characterized by $\\Delta$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The introduction of adversarial robustness into decentralized matching market bandits is a nice direction. The paper addresses realistic adversarial corruptions beyond the common stochastic feedback.\n\n2. The multi-layer extension is elegant to solve the unknown C. The need to introduce a synchronization mechanism to overcome conflicts inherent in randomized strategies is a crucial observation.\n\n3. The optimality analysis for the known C setting is a strong point.\n\n4. The emprical validations are nice.", "weaknesses": "1. For the case of unknown C, there exists a suboptimality gap. The authors acknowledge this multiplicative logarithmic gap and attribute it to the overhead caused from running $\\log T$ paralllel instances.\n\n2. Some important details regarding the algorithmic procedures are deferred to the Appendix, specifically Appendix B; such as Phase 1 index estimation, Phase 3 decentralized GS, leader selection and synchronization specifics. I believe the papers novelty rests heavily on adapting decentralized mechanics to robustness. Therefore, even if the pseudo code remains supplemental, more insights should be provided in the main body of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NEiUKpTZSa", "reviewer": "Reviewer_wBB7", "summary": "This paper studies bandit learning for two-sided decentralized matching markets with corrupted feedback, i.e., the feedback revealed to the learner could be corrupted from the ground truth within some certain corruption level $C$. Algorithms are presented for both known $C$ and unknown $C$ setting.\n\nIn the known $C$ setting, one can simply enlarge the confidence interval so that the ground truth still lies in it (w.h.p). However, it is not applicable to unknown $C$ case. Therefore, in the later setting, in the algorithm design, multiple algorithm instances are created, each of which are tailored to a specific corruption level and are sample with different probability. Eventually, one can show theoretical guarantee when coordinating all these instances together.", "questions": "1. In terms of how to address unknown corruption level, how would the design in this paper different from Lykouris et al. (2018)?\n2. Since each instance is sampled with a fixed probability, how can one adapt to the best/correct one on the fly? (or do we need to?)\n3. In Table 1, why are the regret bound and comm. cost exactly the same in the unknown $C$ setting?\n4. From the lower bounds in Thm. 4.1, how can we claim Remark 4.2? The suboptimality gap has a different definition, and the unknown $C$ upper bound looks quite complicated, can the authors please give a breakdown?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. A new setup that has not been addressed.\n2. Theoretical upper and lower bounds.", "weaknesses": "n/a. please see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)