A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
Authors: Zicheng Hu
Cheng Chen
Venue: NeurIPS 2025 poster ()
Keywords: multi-armed bandits
adversarial corruption
multi-agent bandits
batched bandits
graph bandits
semi-bandits
Primary area: general_machine_learning

Abstract: We investigate various stochastic bandit problems in the presence of adversarial corruptions. A seminal work for this problem is the BARBAR~\cite{gupta2019better} algorithm, which achieves both robustness and efficiency. However, it suffers from a regret of $O(KC)$, which does not match the lower bound of $\Omega(C)$, where $K$ denotes the number of arms and $C$ denotes the corruption level. In this paper, we first improve the BARBAR algorithm by proposing a novel framework called BARBAT, which eliminates the factor of $K$ to achieve an optimal regret bound up to a logarithmic factor. We also extend BARBAT to various settings, including multi-agent bandits, graph bandits, combinatorial semi-bandits and batched bandits. Compared with the Follow-the-Regularized-Leader framework, our methods are more amenable to parallelization, making them suitable for multi-agent and batched bandit settings, and they incur lower computational costs, particularly in semi-bandit problems. Numerical experiments verify the efficiency of the proposed methods.

A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
Zicheng Hu Cheng Chen'
MoE Engineering Research Center of Hardware/Software Co-design Technology and Application
East China Normal University
512759020090stuu. ecnu. edu.cn chchen@sei. edn..edu. on
Abstract
We investigate various stochastic bandit problems in the presence of adversarial corruptions. A seminal work for this problem is the BARBAR [ algorithm, which achieves both robustness and efficiency. However, it suffers from regret of O(KC), which does not match the lower bound of S?(C", where K denotes the number of arms and C denotes the corruption level. In this paper, we first improve the BARBAR algorithm by proposing a novel framework called BARBAT, which eliminates the factor of K to achieve an optimal regret bound up logarithmic factor. We also extend BARBAT to various settings, including multi-agent bandits, graph bandits, combinatorial semiibandits and batched bandits. Compared with the Righ--egulriized-- parallelization, making them suitable for multi-agent and batched bandit settings, and they incur lower computational costs, particularly in semi-bandi problems. Numerical experiments verify the efficiency of the proposed methods.
framework, our methods are more amenable to
Introduction
The multi-armed bandit (MAB) problem is one of the most fundamental online learning tasks, and Recently, as security concerns have grown, many studies
it has long and rich history 2
3
focus on the so-called adversarially corrupted regime where an adversary allowed to manipulate reward observations in stochastic environment. Existing approaches can be broadly categorized into two classes: the Follow-the-Regulant Dolloo--te-Rggllaizee---dddd (FTRL) family algorithms 4 [S] 6, 7 and elimination-bass stochastic and adversarial settings and also achieve optimal regret the adversarially corrupted setting. However, these methods need to solve optimization problem in each round, which may incur high computational costs in many scenarios such as semi-bandits. Also, the FTRL framework challenging extend to parallel settings such batched bandits and multi-agent bandits. On the other hand, elimination-han based methods such as BARBAR 1 are computationally efficient and easy parallelize. However, the BARBAR algorithm suffers from a suboptimal regret of O ()C), and remains an open question how to achieve optimal regret by elimination-base methods.
algorithms {8 [ [0]. FTRL-based methods perform optimally in both
In this paper, improve upon the BARBAR II method and propose novel framework called BARBAT (Bad Arms get Recourse, Best Arm gets Trust) for stochastic bandits with adversarial corruttions. Unlike BARBAR, which employs dynamic epoch lengths, BARBAT adopts static epoch lengths by increasing the probability of selecting the estimated best arm. In addition, BARBAT utilizes epoch-varying failure probabilities 8m instead of a global failure probability ă used in BARBAR, allowing us to achieve near-optimal regret bounds. We further demonstrate that our
'The corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

BARBAT framework is scalable and parallelizable by extending it to various scenarios, including cooperative aggent multi- armed bandits (CMA2B) [TT 9 12,, graph bandits [3 14. semi- bandits
15
16 17 and batched bandits T8 19 20 The regret bounds of our methods along with
comparisons to recent works are summarized Table
We summarize the contributions of this work as follows:
BARBAT framework We propose the BARBAT framework for stochastic bandits with adver- sarial corruptions that achieves a near-optimal regret bound. This result resolves the open problem raised in [Л] Moreover, BARBAT does not require prior knowledge of the time horizon T.
Extensions of BARBAT We extend our BARBAT framework various corrupted bandit settings including multi-agent bandits, batched bandits, strongly observable graph bandits and d-set semi- bandits. We show that all resulting algorithms achieve near-optimal regret. To the best of our knowledge, our work is the first to study a robust algorithm for batched bandits. We also provide lower bound for batched bandits with adversarial corruptions.
Comparison with FTRL Compared to FTRL-based methods, our framework has advantages in three ways. First, our methods are more efficient. The FTRL framework requires solving constrained convex optimization problem in each round. Such problems generally do not have a closed-form solution (except for FTRL with Shannon-entropy regularization) and can therefore be computationally costly, particularly in semi-bandi scenarios. Second, our BARBAT framework is parallelizable, making it suitable for batched and multi-agent settings, whereas extending FTRL to these scenarios is quite challenging. Lastly, as shown in the last column of Table [] not require the assumption of unique optimal action, which is required by FTRL-based methods in environments other than MAB.
our methods do
Related work In recent years, the study of stochastic bandits with adversarial corruptions has garnered significant attention. Existing approaches can be broadly classified into two main categories:
elimination-baser algorithmss [8. I 9 [10] and FTRL-based algorithms 44 5 6 77. Elimination- based methods, with the Active Arm Elimination (AAE) algorithm [21] being a prominent example,
progressively discard suboptimal arms based on empirical reward estimates. By removing poorly performing arms, these algorithms focus their sampling efforts on a shrinking set of promising candidates. (8] introduced a mulli-layer extension of the AAE algorithm, achieving regret bound of Ō EsC 1/4x). Building on this, 1 proposed the BARBAR algorithm and reduced the 6
regret to +ICC+EArr 1/4x). ) On the other hand, FTRI-bbased methods 22 23 24 25
can achieve optimal regret bounds the stochastic, adversarial and adversarially corrupted settings. However, these methods are more computationally expensive than fiminationn-asee methods since they need to solve an optimization problem in each round.
Stochastic bandits with adversarial corruptions can be extended to graph bandits, semi semi-bandits, and batched bandits, each of which benefits from specialized techniques to handle challenges such as exponential action spaces, partial observability, or limited adaptivity [26 13 14
[8] [9] 12] enable agents to pool information and expedite
15
16
17
20 Finally, multi-agent extensions [9] the learning process but often encounter larger regret bounds under adversarial corruptions or rely on gevel performance guarantees rather than individual regrets.
2 Preliminaries
We consider stochastic multi-armed bandits with adversarial corruptions. In this setting, the agent interacts with the environment over T rounds by selecting an arm from set of K arms, denoted by [K]. In each round I, the environment generates an i.i.d. random reward vector {rr,s ] from an unknown fixed distribution. An adversary, having access the reward vector, subsequently attacks these rewards to produce the corrupted reward vector (Fe,
(x)) The agent then selects an arm I, according to its strategy and observes the corresponding corrupted reward Fe. Let μ4 denote the mean reward of arm & E [K], and let As E arg maxke[K) [K] μ4 be an optimal arm. The corruption level defined as = ='= max Fi, rt.ul- The suboptimality gap for arm & defined as A My 1Ab*, and we denote A = MİnA, >o De the smallest positive suboptimality gap.

---

Setting
Algorithm
Regret
Prup.
Prop. 2
BARBAR
KC Ea,30
(7)
4
Tsallis-FRRL
C+ C+E., ΣBe30
log(T)
x
x
2u
3
Essaliis-FRRL 6
C+ E 2,,20
Ing(T)
x
Multi-arm handits
Au
Shamnon-FTRIL 13
C+ E 2A.30
/
Algorithm
C' Ea,
IT"
/
Au
bound
C + Es
lng(T)
C + (1))(())
CBARAC
A
Multi-agent multi-arm bandits
DRAA 12
c + (Tog((T) VA
Algurithm
1Tg E VA
Lower bound
V
C. + Σsy (Tg(T)
CT T
Algorithm
Batched bandits
Σs LlogiT)
R Klog(T)
Lower bound (Ours)
TILL (K + (1-1//2
lox 102 aC ΣxeD
Hlise
As
C + log
Caamnon-FPRLL 13
3
Strongly ohservable graph bandits
(1 Tog(X) Tsallis FTRI 14]
C+ min (K)( lug(3))
x
x
A
Algorithm
C+ C+EErr kE
lTg
Lower bound
C+ ΣNET.
HYBRID 15
dC + +EE5
log(T)
Ag
LBINF 16
dG Ea.>o
lon(T")
Ak
d-set semi-bandits
LBINF LS, LBINF GD 17
dC + Σs.>0
log(T)
X
Algorithm
dC + Σ Ag
log*
Lower bound
dC Σa,>D log(?)
Table 1: "Prop. 1" denotes that the algorithm can efficiently compute the sampling probabilities of the arms, while "Prop. 2" denotes that the assumption of unique optimal arm is not required. For graph bandits, a denotes the independence number of graph G and I" denotes the set of at most In + 1)) arms with the smallest gaps. For batched bandits, denotes the number of batches. "t": Blise is restricted to undirected graphs, while the remaining studies address directed graphs. "f": These lower bounds be directly achieved by combining the corruption lower bound from
with the lower bound for the stochastic setting.
Our goal to minimize the pseudo-regret:
T
T
T
T
T
R(T))
max R
E
Ti.k
E
A
which a standard definition in stochastic bandits. Notice that FTRL-based methods 26
13
4
15
16
17
18
19
20 typically adopt a different form of pseudo-regret, denoted as R(T) R.), which is more appropriate for adversarial settings. However, argue
max; E
Σ D (T.

---

that comparing against the true means, rather than the corrupted rewards, is more natural. Theorem in [ presents the conversion between the two definitions of pseudo-regret in the adversarially corrupted setting as R(T) = (R((T) + O(C)).
CMA2B In cooperative multi-agent multi-armed bandits, V agents collaborate to play the bandit game. We denote the set of agents by [V]. All agents are allowed to pull any arm from [K]. When multiple agents pull the same arm, each receives independent reward drawn from that arm's n's distribution. The adversary is allowed to attack all agents with a total corruption budget C. We only consider the centralized setting where each agent can broadcast messages to all other agents without any delays. For simplicity, we define the total communication cost for each agent v as:
Cost, (T)
Σ
Σ
Magent broadcasts a message to other agents in round l}.
DE(V Am
We aim to minimize the individual pseudo-regret for each agent v over a horizon of 'I' rounds:
T
R. (T) max E KE[K]
Σ (k)
E
Fo (Frst)
Σ (me Ms
Se,e"
Batched bandits In this case, we suppose the agent can only observe the corrupted rewards from a batch after it has concluded. The time horizon is divided into batches, represented by grid T {4,, ,2, tr,), where S ti < 12 .... < tr. = T. As in most previous works [19, the number batches L interest is at most log(T). Additionally, the grid can be one of two types:
Static Grid: The grid is fixed and predetermined before any arm sampling occurs.
Adaptive Grid: The value of ty is determined dynamically after observing the rewards up to time tj-1, which may incorporate external randomness.
Previous works 18
mainly focus on stochastic batched bandits. To the best of our knowledge, no existing work studies stochastic batched bandits under adversarial corruptions.
19
28 20 29
Strongly observable graph bandits In this setting, when the agent pulls arm k. it may observe the rewards of other arms. This feearakfeedback structure is represented by a directed graph ([K), E), where pulling arm k; reveals the rewards of each arm k; such that (ka, ký) E E. Each arm either has a self-loop or receives incoming edges from all other arms [30]. Let a denote the independence number of G, i.e., the maximum size of an independent set. A vertex set D is called an out-domination set of every vertex in G has an incoming edge from some vertex D.
d-set semi-bandits The d-set semi-bandits problem is special case of semi-bandits. Given E [1, in each round the agent selects a combinatorial action x; (containing d distinct arms) from the set X = {x E 1] Σ x(k) = d). where x(k) = 1 indicates that arm is selected. Then the agent can observe the corrupted rewards for each arm in the action (i.e., for each arm such that (k) = 1). Let μl denote the mean reward of arm & E [K]. Without loss of generality, we assume 14 2 f1 ... 2 fk and denote A pd μ4 for all d. We aim minimize the pseudo-regret over a horizon of T rounds:
T Σ
T
T
R(T) = max E XEX
Σ
Ttak
E
Σ
Pk
[
k:X,
(K)==
3 Stochastic Multi-Armed Bandits Robust to Adversarial Corruptions
Main idea Notice that in the BARBAR [| algorithm, the arm ls is approximately drawn n = ((1/(AM~)))) times in expectation during epoch m, where Am- is the estimated gap computed in the previous epoch. Thus, each epoch has length of approximately N. & O 1/(Am- Consequently, adversary can significantly extend the length of an epoch by utilizing all of the corruption budget in the previous epoch, thereby implicitly increasing the number of pulls for

---

Algorithm BARBAT:
Bad Arms get Recourse, Best Arm gets Trust
1: Initialization: Set the initial round To + A + 1, and r t- for all E [K].
2: for epochs m 1, 2, 2, ... do
3: Set Gm + (m++4)22(m+4)) In(K) and 8m < 1/(K)m)
4: Set Am f- 2 In (4K/ and 8m 6- K.
5:
Set n - >m 1 for all E [K].
6:
Set Nm f Am 22 1)7 and Tm <- Tm-1 + Nm- th and compute n according to
7:
Set Km f- arg e [K] l'k
8:
fort Tm- + Tm,
Choose arm 1, ~ Pm where Pm (k) n /N 10: Observe the corrupted reward Tt. and update the total reward S%. + 5% +
9:
11:
end for
12: Set K min (5 /ug. 1) and r.hh <- maxxe(k) {TT
4lm(4/8m)
13: Set AT max (2-m) mm r rk
14:
end for
suboptimal arms. To address this challenge, BARBAT algorithm chooses data-independent epoch length Nm. RJ O ((22),m-)) which cannot be affected by the adversary. We still allocate "i = 0(10((()))))) 001 pulls to each arm k; but assign all remaining pulls to the estimated optimal arm km resulting in pulling arm km for about Nm, En "i rounds. On the other hand, pulling the estimated optimal arm km too many times may lead to additional regret, as arm km could be suboptimal. To mitigate this additional regret, adopt spoch-varying failure probabilities 8m (1/ (11/mm/) (m))22m) for epoch m rather than using a global failure probability 8. The choice of 5m also eliminates the need to know the time horizon T.
Algorithm We introduce our BARBAT framework for stochastic bandits with adversarial corrup- tions in Algorithm ! In each epoch m. BARBAT sets the fallure probability as 6n = 1/ (m(K(m), where Sm is chosen to make 6m I 1/Nm- The algorithm sets the epoch length to be Nm = [KAm 22(mm2) 2 ΣeE(K) n. We denote km as the arm with the maximum empirical reward in the previous epoch; in case of ties, the arm with the smallest index is chosen. Then the number of pulls for each arm set to
m N
o kims kim
7 12g
- keth 1
During epoch m, the agent pulls arm I, with probability Pm (I+) - /Nm. observes the corrupted reward Fe. and accumulates the total reward ST. At the end of each epoch m, BARBAT updates SalsSS//n/g
the estimated reward r min{ S / 1} and computes the estimated suboptimality gap A/r
An example showing how BARBAT avoids paying an O(KC) term Gupta et al. | provide an example where BARBAR suffers regret Q(KC), in which all corruptions happen in epoch with corruption level C N. (c2 OKK). Then the algorithm will lose all information from the previous epochs so that the length of the next epoch becomes No+1 = K x222 = O(C)) and each arm will be pulled uniformly. In this scenario. BARBAR will pull each arm approximately O(C) times and generate O((K' - 1)C') regret. On the other hand, our BARBAT algorithm fixes the length of the m-th epoch to be N,, = KR 2mm-1) If the adversary intends to corrupt an entire epoch c, the required corruption level is = N. = (x22(e-1)) which K times larger than needed to attack BARBAR. Thus our BARBAT algorithm will only suffer O(C) regret from adversarial corruptions.
Regret Bound BARBAT achieves the following regret bound, with proofs deferred to Appendix B.1
Theorem 1. The expected regret of BARBAT satisfies
R(T) (
log(T) log( KT)
K log(1/A) log( (ogg(1/))log(K/A))
A
A
5

---

Algorithm 2 MA-BARBAT
1: Initialization: Set the initial round To + A - 1, and r - for all [K].
2: for epoch
1,2, 2,... do
3: Set Sm + (m + 4)22(m++4) (VV)) and 8m + 1/(VK(m).
4: Set Am f- 2 In (4K 8m) /V and 8m +- 8m/ (VK).
5:
Set ni - \
for all
[K].
6:
Set Nm f- K Am 22(m-1)] 1)7 and Tm f- m Nm-
7:
Set kim f- arg max ' p m- and compute n according to
8:
fort m-
Tm do
9:
Each agent chooses arm I Pm. where Pm (k) n /N
Each agent observes the corrupted reward Ft.1, and compute ST. S%, + Fide.
11:
end for
Each agent e broadcasts the messages (S ke[K]] to other agents.
13: Set & +- min ( Evel ST, /V/igV }} and r. maxxe[K] { (
4lm(4/Bm) Vig
14:
Set AT <- max (2-
m, rm rk)
15:
end for
Remark 1. The regret bound of BARBAT contains an extra term log (1/A)/ Notice that this Log² Ax
term is independent T, making it generally much smaller than the major term Σs.>o
Remark 2. Notice that a concurrent work [12] also employs static epoch lengths and removes the factor K from the regret bound. However, they adopt global across all epochs, resulting
regret of O + K log" (T)/A), which is worse than our regret of O (C+ Σs
log²(T) (T)
Extensions
In this section, we extend BARBAT various corrupted bandit settings and introduce the necessary modifications to accommodate the specific configurations of these environments.
4.1 Cooperative Multi-Agent Multi-Armed Bandits
We extend BARBAT
the multi-agent setting and propose the MA-BARBAT (Multi-Agent BAR- BAT) algorithm in Algorithm 2 In each epoch m, all agents pull arms according to the same probability distribution and broadcast their total rewards {S K at the end of the epoch. Each agent then updates the estimated suboptimality gaps AT" using the received messages and its observations. We present the regret bound and communication cost of our MA-BARBAT algorithm in the following theorem, with the proof given in Appendix B.2
Theorem 2.
The MA-BARBAT algorithum requires only communication of V log(VT) over T roudss. The individual regret of each agent v satisfies:
C
log(VT) log(KTT)) log (1/A)log (KV/A)
Σ 4+50
VA
VA
Remark 3. The regret bound demonstrates that collaboration reduces each agent's 's individual regret our bound is tighter than those of previous works on
by a factor of V. As summarized in Table 7 CMA2B with adversarial corruptions.
Remark 4, Notice that some recent works (TT) CMA2B achieve communication cost of only o(log(T)). However, these methods rely on the assumption of a unique best arm. In the presence of multiple best arms, it remains unclear whether a communication cost of o(log(T)) is sufficient.
4.2 Batched Bandits
We extend BARBAT to the batched bandit setting and propose the BB-BARBAT (Batched Bandits- BARBAT) algorithm in Algorithm 3 The BB-BARBAT algorithm sets the epoch lengths N,, to

---

Algorithm 3 BB-BARBAT
1: Initialization: Set the initial round To + A + 1, and r < for all [K].
2: for epochs m = 1,,,, ... ... do
3: Set a < T2(1+)), Sm t- (m + 2)a2(m++)) In (n(K) and om t 1m)
4: Set Am - a² In (4K (mm) and Bm K./K.
5: Set gh t () for all k [K].
6:
Set N,, [K a (m and Tm f- T N.. Set Kim arg max k K] mi=l and compute fig according to I.. to Tm do
7:
8:
for 1o mm +
9:
Choose arm It ~ Pm where Pm (k) / /Nm- end for
10:
11:
Observe the all corrupted rewards řı, in this batch and compute ST. t Sy, + +7,,-
12: Set & t ( /ng 1} and t max {1r
4lm(4/8m) "
13: Set AT + max(a (ax m, r. rg)
end for
be approximately O(T ensuring that the number of epochs matches the number of batches. In this way, each epoch serves batch, making the BB-BARBAT algorithm almost identical the BARBAT algorithm. We present the regret upper bound of BB-BARBAT and the lower bound for corrupted batched bandits Theorems respectively. The proofs are deferred Appendix B.3]
Theorem 3. For corrupted batched bandits with a static grid, the regret of BB-BARBAT satisfies
R(T) = o CT (
+ +
Llog(KT) +
K (T)g(T) log(1/ (1/ log K/A)
A
LA
Theorem 4. For any algorithm, there exists an instance of batched bandits with static grid such that
R(T)= 2 2 (TT (K (K+C+++))
Remark 5. There is still a gap between our upper bound and the lower bound. We believe that our lower bound is nearly tight. Achieving optimal regret upper bounds for corrupted batched bandits remains an interesting open question.
4.3 Strongly Observable Graph Bandits
We extend BARBAT to strongly observable graph bandits and propose the SOG-BARBAT (Strongly- Observable Graph (andit--AARBAT) algorithm, presented Algorithm 4 Our method adopts n and 4 to denote the expected pulls and expected observations in epoch
respectively. Gm
denotes the graph used in the m-th epoch. SOG-BARBAT adopts the proposed Algorithm 6 (in Appendix A) to compute the out-domination set Dm of Gm", whose size is at most ax In K/a)).
Moreover, if G is acyclic, we can guarantce that 1 < a. Then SOG-BARBA which is the minimal number of additional pulls per out-dominating arm that ensures some vertex meets its observation requirement. After that, SOG-BARBAT updates T and / and removes all nodes that have now been sufficiently observed from GmL Repeating these steps ensures that by the end of epoch m, all arms have been observed sufficiently. The regret bound for SOG-BARBAT is presented as follows, with the proof given in Appendix B.4
computes H
Theorem 5. For any strongly observable directed graph G ([K), E) with independence number a, the expected regret of SOG-BARBAN satisfies
E [(((T))= (0 Σ
log(T) log(KT)
K log (1/A) log (K/A)
D
A
REZ
where I" is the set of at most [a(1 + (n(K/a))] arms with the smallest gaps. Especially, for directed acyclic graphs and undirected graphs, I" is the set of at most a arms with the smallest gaps.
Remark 6. The regret upper bound of SOG-BARBAT depends [I*| O(a In( K/o + 1)), which matches the lower bound established by [37y. When an acyclic graph or an undirected graph, have I I indicating that BOR-BARBAT performs better under this condition.

---

Algorithm SOG-BARBAT: Strongly Observable Graph-BARBAT
1: Input: A Strongly Observable Directed Graph G.
2: Initialization: Set the initial round To < O, A t 1, and r t- 0 for all E [K].
3: for epochs m 21,2.... do
4: Set Sm + (m + 4)22(m=+1) In K)) and 6m < 1/((Km))
5: Set Am f 2 In ( (4K/6, 6m) and 8m + 6m/K.
6:
Set ng t Am(4 )ー² for all
[K].
7:
Set Nm + Am (2(m-)) 17 and Tm <- Tm-1 + Nm
8:
Set km f- arg max k1
9:
Set 2 + and Hy + 0 for all arms k E [K], Gm 4- G.
10:
while H 2 nigg holds for all arms
[K] do
11:
Compute an out-domination set D of Gm by Algorithm 6
12:
Compute H +- minge K (ng) - )
for each arm K; 1 do
14:
Update Z & Zk. + H and H + H H
Update Hg H H for all arms (ks, k;) E with Ky +
16:
end for
17:
Remove all arms which satisfy H 2 nkkk from G
18:
end while
m
+ km and nig + E Een "l: = km
19:
Set n2
for Tm-1 E km
N
E T do
Z
20:
21:
Choose arm It ~ Pm where Pm (m)))) n /Nm-
22:
Observe the corrupted reward Ft,1, and update the total reward ST.
5%,
Fe,le
23:
end for
Set K <- ( (STT// /ng 1} and r <- maxxe[k] {TT
1ln(4/8m)
24:
25:
Set A +- max 22220 " "r rk
end for
Remark 7. Compared to FTRL-based methods [13 144, whose regret bounds depend on the smallest suboptimality gap 1/2, our bound reveals the relationship between the regret and the suboptimality gap of all arms. In addition, these works require prior knowledge of the independence number which is NP-hard to compute, whereas SOG-BARBAT does not need such prior knowledge.
Remark 8. Compared with []0], which adapts BARBAR to graph bandits with undirected graphs. our SOG-BARBAT method improves the porruption-dependee term from O(aC) to O(C). Also, our method can be applied to bandits with directed graphs.
4.4 d-set Semi-bandits
We extend BARBAT to the d-set semi-bandis setting and propose the DS-BARBAT (d-Set BARBAT)
algorithm in Algorithm 5 In this setting, the optimal action is subset of d distinct arms. Thus, DS BARBAT estimates the best action Kmm as set of d distinct arms with the highest empirical rewards in the previous epoch. When estimating the suboptimality gap, DS-BARBAT considers the with the d-th largest empirical reward, since the set of the first d arms is the optimal action. The regret bound for OS-BARBAY is presented follows, with the proof provided in Appendix B.5
Theorem 6. The regret of DS-BARBAT satisfies
K
log(T) (KT) KT)
dK log (1/A) log (K/A)
R(T) - dc +
Σ k=d+1
A
Remark Notice that our DS-BARBAT algorithm can efficiently compute the sampling probability Pms while FTRL-basee methods 25
[7] need to solve complicated convex optimization problem in each round, which is rather expensive. The time comparison in Table 3 in Appendix C demonstrates that our DS-BARBAT algorithm is significantly faster than these FTRL-based methods.
15
16

---

Algorithm 5 DS-BARBAT: d-Set-BARBAT
1: Initialization: Set the initial round To + 0, - + 1, and r - for all [K].
2: for epochs m 1, ... do
3: Set Sm + (m + 4)2 ln(K), and 6m t (mm
4: Set Am f- 2 In (4K 8m) and 8m f- 6m
5: Set ni <- Am ) for all arms
[K].
6: Set Nm f Am 22(m-2) /d] and Tm < Tm + Nu-
7: Set the arm subsets Km - arg [E(KK] "k with [Kml = d.
E Km
8: Set
Ekek.. nk m /d k E Km Tm do Choose action X2 Pm where Pm (k) = 1ik /Nm- For each arm &o with (k) 1, observe Ti, and update the total reward Sp Sk Te,k-
N
9:
for Tm mm
10:
12:
end for
Set Th <- min ( (ST /ng. 1}.
Set + <- Ta {1r V (...))
kE(K)) where Ta(AA) returns the d-th largest value A.
15:
Set AN +- m 2 m .r rk)
16: end for
PTAI
Jo' TIR
[4) (TA
Indvidual
Individual
N
Individual
Indviduall
Rounds
Rounds
Rounds
Rounds
(a) K 12, C= 2000
(b) == 12, C 5000
(c) K = 16, C 2000
(d) K 16, C 5000
Figure 1: Comparison between MA-BARBAT, DRAA, IND-BARBAR and IND-FTRL in cooperative multi-agent multi-armed bandits.
5 Experiments
In this section, we present numerical results to demonstrate the robustness and effectiveness of our framework. All experiments are implemented in Python 3.11 and conducted Windows laptop equipped with GB of memory and an Intel 17-13700H processor. For all experiments, we run 50 independent trials, report the average results and use shaded regions to represent standard deviations. The detailed experimental settings and time comparisons are deferred to Appendix
5.1 Cooperative Multi-agent Multi-Armed Bandits
We compare our framework with DRAA (12), IND-BAN AD-BARBAR [. and IND-FTRL 4 in multi-agent setting with V/ 10. Here, IND-BARBAR and IND-FTRL serve as non-cooperative baselines, where each agent runs the algorithm locally without any communication. We do not compare with [32] since baseline DRAA an improved version of their method. We present the experimental results in Figure D which shows that BARBAT framework outperforms all baseline methods, reflecting the advantage of collaboration and verifying our theoretical analysis. In addition, when is increased, the increase in individual regret of our framework is the smallest, which shows that the robustness of our framework stronger than that of all baseline methods.
5.2 Strongly Observable Graph Bandits
We compare our SOG-BARBAT algorithm with Shannon-FTRI. 13 and Tsallis-FTRI. 14 using two directed graphs as illustrated Figure in Appendix C.2 do not include the Elise [T0] algorithm in the experiment since it only works for undirected graphs. The experimental results

---

505 Bensel Sarrer-it IT
1.0
500 BATBA SharopurT
50c 50C-A-2AA LA
1.00
Steenen $3P
Respett
$54.5
1.00
(a) 12, C= 2000
(b) K 12, C= =500
(c) 16, C 2000
(d) == 16, C 5000
Figure Comparison between SOG-BARBAT, Shannon-FTRL, and Tsallis-F FTRL in strongly observable graph bandits.
2117
Regret
Regger
(a) 12, C 2000 (b) 12, C= 5000
(c) 16, C 2000
(d) 16. C 5000
Figure 3: Comparison between DS-BARBAT, HYBRID, LBINF, LBINF LS and LBINF GD in d-set semi-bandits.
are presented in Figure 2 showing that our SOG-BARBAT algorithm significantly outperforms all baseline methods and verifying the robustness of our method.
5.3 d-Set Semi-bandits
In d-set semi-bandits, we set d = 3 for K 12, and d = 4 for K = 16. We compare our framework
with HYBRID [15]. LBINF [16], LBBIF_ISS (17 and LBINF GD [77. shown Figure 3 our
DS-BARBAT algorithm significantly outperforms all baseline methods.
6 Conclusion
Building on the BARBAR algorithm M. we propose the BARBAT framework by elaborately design- ing the epoch lengths Nm and the parameters 8m We further extend BARBAT to various corrupted bandit settings, including multi-agent bandits, batched bandits, strongly observable graph bandits and d-set mani-sandits. Our theoretical analysis shows that these algorithms achieve near-optimal regret bounds for adversarially corrupted environments. Compared with FTRL-based approaches, BARBAT and extensions are more computationally efficient and not rely on the assumption a unique optimal action. Moreover, since FTRL-based methods are difficult to parallelize, they are unsuitable for multi-agent and batched settings. These advantages make the BARBAT framework an attrac- tive alternative to FTRL-based algorithms across wide range of corrupted bandit problems. One future direction is to improve the log)(())) dependence in our regret bound to log (T). Investigating extensions in other bandit settings such as linear bandits also an interesting future direction.
Acknowledgement
This work was supported by Natural Science Foundation of China (No. 62306116), and in part by the Key Program of National Natural Science Foundation of China (No. 62432007).
References
[1] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, volume 99, pages 15622-178.. PMLR, 2019.
10

---

[2] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, 6(1):4-22, 1985.
[3] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-20 256, 2002.
[4] Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22((8))1--9,, 2021.
[5] Shinji Ito. Parameter-free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference on Learning Theory, volume 134, pages 2552-2583. PMLR, 2021.
[6] Tiancheng Jin, Junyan Liu, and Haipeng Luo. Improved aumdi bandits: Ftrl with general regularizers and multiple optimal arms. In Advances in Neural Information Processing Systems, volume 36, pages 30918 19918-3021 10118888,7 2023.
www.ooffoohworllde guarantees for
[7] Taira Tsuchiya, Shinji Ito, and Junya Honda. Stability-penally- penalty-adaptive follow-the th-.---a--rrrrzedd leader: Sparsity, dependdeen,,,, and best-of-both-workke In Advances in Neural Information Processing Systems, volume 36, pages 47406-47437, 2023.
[8] 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, pages 14-1222 2018.
[9] Junyan Liu, Shuai Li, and Dapeng Li. Cooperative stochastic multi-agent multi-armed bandits robust to adversarial corruptions. arXiv preprint arXiv:2106.00 04207, 2021.
[10) Shiyin Lu, Guanghui Wang, and Lijun Zhang. Stochastic graphical bandits with adversarial corruptions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8749 8757, 2021.
[11] Xuchuang Wang, Lin Yang, Yu-zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, Don Towsley, and John CS Lui. Achieving optrmoptimal individual regret low communications in multi-agent bandits. In The Eleventh International Conference on Learning Representations, 2023.
[12] Fatemeh Ghaffari, Xuchuang Wang. Jinhang Zuo, and Mohammad Hajiesmaili. Multi-agent stochastic bandits robust to adversarial corruptions. In Proceedings of the 7th Annual Learning for Dynamics & Control Conference, volume 283, pages 12-25, 2025.
[13] Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 35, pages 28631-28644 2022.
algorithms for
[14] Chris Dann, Chen- Yu Wei, and Julian Zimmert. blackbox approach best of both worlds in bandits and beyond. In Conference on Learning Theory, volume 195, pages 5503-5570. PMLR, 2023.
[15) Julian Zimmert, Haipeng Luo, and Chen-Yi Yu Wei. Beating stochastic and adversarial semi- bandits optimally and simultaneously. In International Conference on Machine Learning, volume 97, pages 7683-7692, PMLR, 2019.
[16] Shinji Ito. Hybrid regret bounds for combinatorial semi-bandits and adversarial linear bandits. In Advances in Neural Information Processing Systems, volume 34, pages 2654-2667, 2021.
[17] Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worldd algorithm for combinatorial semi- bandiss In International Conference Artificial Intelligence and Statistics, volume 206, pages 8117-8144, PMLR, 2023.
[18] Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. In Conference on Learning Theory, volume 40, pages 1456-1456, PMLR, 2015.
[19] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. Advances in Neural Information Processing Systems, volume 32, pages 503-513, 2019.

---

[20] Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 1340-7348, 2021.
[21] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi- bandit and reinforcement learning problems. Journal of Machine Learning Research, 1(39):1079-11 1105, 2006.
[22] Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, volume 23, pages 42.1-42.23. PMLR, 2012.
[23] Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning, volume 32, pages 1287-1295. PMLR, 2014.
[24] Peter Auer and Chao- Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory, volume 49, pages 116-120. PMLR, 2016.
[25] Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, volume 75, pages 1263-1291. PMLR, 2018.
[26] Chloé Rouyer, Dirk van der Hoeven, Nicolò Cesa-Bianchi, and Yevgeny Seldin. A near-optimal best-of-both-wee worlds algorithm for online learning with feedback graphs. In Advances in Neural Information Processing Systems, volume 35, pages 35035-35048, 2022.
[27] Ronshee Chawla, Daniel Vial, Sanjay Shakkottai, and R Srikant. Collaborative multi-agent heterogeneous multi-armed bandits. In International Conference on Machine Learning, volume 202, pages 421944217. PMLR, 2023.
[28] Kelly Zhang, Lucas Janson, and Susan Murphy. Inference for batched bandits. In Advances in Neural Information Processing Systems, volume 33, pages 9818-9829, 2020.
[29] Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Quanquan Gu. Double -hmlore-then-comiit. Asymp- totic optimality and beyond. In Conference Learning Theory, volume 134, pages 2584-2633. PMLR, 2021.
[30] Noga Alon, Nicolo Dasa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6): (066)::78855 785-11826 2017.
[31] Houshuang Chen, Yuchen He, and Chihao Zhang. On interpolating experts and multi-armed bandits. International Conference on Machine Learning, volume 235, pages 6776-6802. PMLR, 2024.
[32] Haoyang Liu, Keqin Liu, and Qing Zhao. Learning in changing world: Restless multiarmed bandit with unknown dynamics. IEEE Transactions on Information Theory, 1911 2012.
[33] Devdatt Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009.
[34] Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. International Conference on Artificial Intelligence and Statistics, volume 15, pages 19-26. PMLR, 2011.
[35] Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
[36] Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publication of the Mathemat- ical Institute of the Hungarian Academy of Sciences, 5:17-61, 1960.
12

---

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

---

Justification: see Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: the pseudo code of algorithms, Section 5 and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: see supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuiiu wwwticccguie//eeieeeeeeii CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: see the pseudo code of algorithms, Section 5 and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: see Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: het::://neuisspee http://s...cppuu.tttttcccsuuueee
Answer:
[Yes]
Justification: I confirm the paper in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: this work is theoretical research
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee www.ree.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
17

---

Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
18

---

Justification: the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non- stanssand components.
Please refer to our LLM policy hattps://neurips... / for what should or should not be described.
19

---

Contents
OODS algorithm for strongly observable graph bandits
21
Proof Details
22
B.1
Proof of Theorem
22
I.I
Notations
22
B. B.1.2
Lemmas for Proving Theorem
22
B. 1.3
Proof for Theorem]
26
2
Proof of Theorem
28
B.2.1
Notations
28
B.2.2
Lemmas for Proving Theorem]
28
B.2.3
Proof for Theorem
32
B.
Proof of Theorem
34
B.3.1
Notations
34
B.3.2
Lemmas for Proving Theorem
34
B.3.3
Proof for Theorem
37
B.3.4
Proof for Theorem
39
B. 4
Proof of Theorem
39
B.4.1
Lemmas for Proving Theorem
39
B 3.4.2
Proof for 55
43
B.5
Proof of Theorem
46
B.5.1
Notations
46
B.5.2
Lemmas for Proving Theorem
46
B.5.3
Proof for Theorem
47
Experimental Details
50
Cooperative Multi-Agent Multi-Armed Bandits
50
Strongly Observable Graph Bandits
50
d-Set Semi-bandits
50
20

---

A OODS algorithm for strongly observable graph bandits
In this section, we present the OODS algorithm for strongly observable graph bandits. For any graph G = (V, E), the time complexity of the algorithm is (((V))
Algorithm 6 OODS: Obtain an out-domination Set
1: Input: graph G.
2: Output: an out-domination set D.
3: while the graph G' is not empty do
4: if the graph G is an acyclic graph then
5: Find all no-root vertices and add them the set D.
6: Remove all no-root vertices and their out-degrce neighbors from the graph G.
7: else
8: Select the vertex with the largest out-degree in the graph G and add it to the set D.
9: Remove the vertex and its out-degree neighbors from the graph G.
10: end if
end while
A "no-root vertex" is defined as vertex with incoming edges other than its self-loop. To ensure that the rewards for no-root vertices are observed, OODS pulls these vertices directly. However, in some graphs, there may be such vertices. In such cases, OODS applies a greedy strategy: it selects the vertex with the highest out-degree and adds it to D. The procedure proceeds as follows: cycle is detected in G, the greedy strategy is employed; otherwise, all no-root vertices D. The vertices D and their out-degree neighbors are then removed from the graph G, and the process repeats until G is empty, ensuring that D forms out-domination set covering G.
added to
At high level, the OODS algorithm finds an out-domination set Dm such that pulling the arms k E D allows us to observe the rewards of all arms. The loop iteratively removes arms once they meet the observation requirement. After each removal, the independence number of the remaining graph may decrease, so the required dominating set becomes smaller-therees reducing the number of pulls allocated suboptimal arms.
21

---

B Proof Details
B.1 Proof of Theorem 1
B.1.1 Notations
We define C% as the sum of corruptions arm k in epoch and let Cm & ma Cx"
B.1.2 Lemmas for Proving Theorem
Lemma 1. For the BARBAT algorithm time horizon T, the number of epochs M is at most log2 (T). In the m-th epoch, the selected arm km must satisfy A mm-1 =2 (mmm)
km
Proof.
The length of epoch m is given by Nm [K
2 22(m-11, From the lower bound
of Nm, can complete the first statement. Since Ax- f m (axx221 (m1-1) r - }. there exists at least
that satisfies Am-1 2- (m and all arms satisfy Ar-1 2 (mm-)), Since km 2- (m-m11) 1) must hold.
T -mmm-1 rm the equality A m-m1
Lemma 2. For any epoch m, the length Nm satisfies Nn. 2 EkE[K] n
Proof. Since A = max (2 (2-m -m - rx 1 n, we can get na = Am (1 S Am 22 Therefore, we have Σ EkE[K] ni & KAm 22 I Nm.
Lemma 3. For epoch and m with 1 S S m. the following inequality holds:
Am A
(x+1 (i)4)) (7/6)²
Proof. We first show that the function f(x)
is strictly decreasing for x 2 5.
Notice that the derivative function
('(x) (In(4) + 1/x) - ((x In))))(()))) In (H)
is monotonically decreasing and f'(5) < 0, thus we have f'(x) < 0 for x 2 5, which indicates that
f(x) strictly decreasing. Since K 2 2, we can get
Am
In(4k (m 4)220m+4))
X
1.7 + In (m+++
1.7 1.7- In(4) In(s + 4) (8+4)) (4)
f(m + 4)
(3)
m-s
f(s + 4)
where we use the monotonicity of f(x) and the fact that K 2 2.
Lemma 4. For any epoch m, the following inequality holds:
X 20 mm 3ln))))(()))).
Proof. Given the function f(x) 2x(1 - - Notice that the derivative
function as fz( 2 - 2 ln(2) 0 for all æ 2 which means that f(x) is strictly increasing
22

---

for x 2 1. Since f(x) 2 f(1) 2 0, we can get the inequality as 2x +7 2(x 4) + In(x +4)
for all x 2 then have
2 (s2())))++2)2(+1) 4)22(0+1)))
sm
(2 + 4) + In(s + 4) + In(4K2In(At)
s=1
m
(2s (=(kk()
2 (m² + m ))
S 2d (m² + + mm11++ln(KK))
Lemma 5, For any fixed k, m and Bm. Algorithm 7 satisfies
4 4m(44/Bm
(m)
20m
Pr
Irk
MR
N m S Bm.
Tik
Proof. The proof of Lemma 5 mainly follows the proof of Lemma 4 in []] We only consider the randomness in epoch m and condition on all random variables before epoch m. In epoch m, the agent pulls arm & with probability Pm. (A) - /Nm-
For ease of analysis, we an indicator variable Yg which determines whether the agent updates the corrupted reward Fı, into the total reward S7; at step t. We define the corruption at step on arm k as C T rt. Let Fmm == [7m-1 1,... Tm] represent the Nm time-steps for epoch m. Since
rk min [ mm 1}, we can obtain
Sm
Y Ct).
BEE
We can divide the sum into two components:
Ap
D
Σ Y EE
E.
For the previous component A notice that rf is independently drawn from a [o, 1]-valued dis- tribution with mean Pk. and Y is independently drawn from Bermoulli distribution with mean %% == n /N.. Therefore, have
E| Nm Eiri] = Tok S Tm
By applying the Chernoff-Hoeffding inequality (Theorem 1.1 in 33
we can get
3lm(4/Bm)
3m
Pr
7
2
For analyzing the latter component BT we define martingale difference sequence XI,..., Xr., where X, (Y ggth Ct for all f, with respect to the historical information {F)T Since the corruption C deterministic when conditioned on F and since F[y = % we can get
B[x,FFi-1] = E "f F 0.
Additionally, we have |Xe| < for all I, and the predictable quadratic variation of this martingale be bounded as follows:
E(((x)) <
Σ
ICHIVar(YY) S oh
Σ ICL--
E.
E...
E
23

---

By Freedman concentration inequality (Theorem 1 in 34), with probability at least have
Bm/ we
BE S m Σ
C +
Σ
lm(44mm)) S 241
Σ
cct + lm(4/3m))
BEEm
BE
IEEm
Since 9% n /N DIEE.
C
S Cm and nik 2 Am 2 161n(4/8m)) with probability least
8m/4 4 the following inequality holds:
B
In(4/8m)
20m
167g
Nm
Similarly, with probability least 1 B the following inequality holds:
B
In(4/3m)
2Cm
16m
Nm
Thus we have
In lm(4/3m)
20m Nm
pm
Pr
16ng
2
Combine Eq. (2) and Eq.
13. we complete the proof.
We define event en for epoch m follows:
4
4ln(4/
2Cm
mm
V k: 1
MA S
N m
Then establish lower bound on the probability of the event &m occurring by the following lemma.
Lemma For any epoch m, event &m holds with probability at least 8m. also have 1/0m Nm-
Proof. By Lemma B. we can get
4ln(4/9m) 72
20m
5m
Pr Ir Mkl
S 8m
N
K
union bound over the K arms indicates that the success probability of event &m is at least 8m.- Since m 2 and K 2 2, then we can get
N 1m)(m-1) Am
(22(m+3)) +3)
In((m + 2) K2 In(K))
< k
[In(m + 4) + 2mm + 5) In(2) + ln(K3))
K2
(m 4) In(K] + 2(m 5) ln(K) + 3ln(K)
< k22(m+3) (4m + 16) In()
(2 (m 4) (n((())))))))))) 1/5m.
Now we can define the offset level Dm for each epoch m:
220m
when Em occurs
Dmm
Nm
when &m does not occur
24

---

Since we always have Irx" - Mal - 1, thus the following inequality always holds, regardless of whether event Em happens:
(lmm4/mm)
Dmm
Ir ubl S
+
Nm
By the definition of Dm we have
Pr(Dm = 20m] 2 1 - 8m and Pr(Dm = Nm] 1 6m
Next, we will bound the estimated gap Ag. To start, we define the discounted offset rate as
De
Pm 8m
Then we have the following lemma.
Lemma 7. For all epochs m. and arms k, we can have
4 ke
2 2
3
6pm
S Ar
8
(m-1)
2pm-
2
Proof.
Since Ir
1K S
1 1l(4//3m)
Dm Nm
we have
Dm
4 (m)
Dm
4ln(4/3m)
r
Mk S
+
Nm
7%%6
Nm
Additionally, since
Dm Nm
41m(4/8m)
4 4m(433mm)
Dm
T I max
Mb +
+
S Mk +
71k
Tik
Nm
4 1l(44 (n(4/Bm)
4 (m4333mm
4 4ln(4/3m)
Dm
max
Tk
rk=
pk 2/
n
7
N
we can get
Dm
4ln(4/3m (m)
Dm Nm
2V
I r
Mkk I
N
According Algorithm I and Lemma 2 following inequality for all k E [K]
we have nht
nok for all arms
Then we have the
4ln (m((4/m))
4 4ln(4/3m)
AT
ni
8
now establish the upper bound for A by induction on m.
For the base 1, the statement is trivial as A for all & [K].
Assuming the statement is true for the case of m 1, we have
A b
rk
(r (x-) + (JAZ ma) + (#x - r rkt)
Dm
Dm
+ Ao
+
+ -
Nm
Nm 8
2Dm m
1 88A 22-(m-2) + 2pm-
Nm
8
8Ap
2 (m + 2pm
Where the second inequality follows from the induction hypothesis.
25

---

Next, we provide the lower bound of A.. We can get
m
1k
(T th
pk-) ) + (uu - [x)) + (NL
- -Tk
Dm
Arr +
Dm
1 Am--
Nm
Nm 8
2Dm
3 /8Ax
+ A
+ 2-2-m-22 + 2pm
Nm
8
4
A
6pm-
where the third inequality comes from the upper bound of A mm
B.1.3 Proof for Theorem 1
We first define the regret Rg generated by arm epoch m as
{ S m
+ km
R
A m
mm
k km
Then we analyze the regret in following three cases:
Case 1: 0 Ax S 64pm-1-
If k & kms then we have
R DRNI S 64pmm-1nj
If k = km then we have
RE
< 64pmm N
Case 2: Ae 2- and Pm-1 S
A
l: j km. then we have
16Am
R Tik D Am Am (A S 22
Ab 5
A
If k = km since A m-1_ km = 2 (m- we can get:
16K Am
16K Am
R ni Apm < Nm = 1m 22m-1)A) <
Akm
+ Akm
km
A
1.
Case 3:
m and Pm-1 S A. > 8 8.2 8-
A
64
By Lemma we have
3
m- k
2
A
2
A
2 0.294
64
16
64
In this case, it is impossible that k = km because A m- 2- So we can obtain
(m-1) < 0.29 8 2-22-
< 0.294
Am
16A
R no. A Aa (Ag
5
0.29 A
A
26

---

We define A {k [K] can upper bound the regret as
< As I 64pm-1} for epoch m. By combining all three cases, we
R(T)
Σ
R
Ri
m=1
mm
M
64pm- Nm +
64pm-1
Σ
16Am
A
m=1
REA t kom
hEAm Ac>0
16K Am
+ 1)
+
I100
km 58.2
A
(4)
M
16Am
$
64pm-1 Nn +
Σ
+
A
m=1
Ax30
Ax70
16K Am
+ 11 (m S logz (8/A))
A
<
M
128pm +
16Am
(8/2(
Σ
(66K Am
+1) 1
AB
A
m=1
A,30
m=1
where the last inequality uses the fact that Σs ni S Nm. Notice that we can bound the expectation the offset level
[D = =2(1 6m + 5m S 20m +
and we can bound EM 1 Pm 1m Nm as
M
M
D2
Σ
Pm
Nm S
Nm
Noo
m=1
m=1
M
(4m-1-s 1-s + 1)dm D.
8m-11
m=1
Σ
(7/12) (7/48)m-1-9))
(5)
M-1
Σ
(7/12) -1--8 + m7
#=1
m=s+1
/M-1
M-1
< 4
Σ
Dm
(7/12)/ + (7/48)/ < 11 Σ Dm
m=1
m=1
27

---

still holds for Combining Eq. 4 and Eq. (5), by Lemma
we can get
M-1 R(T)
16Am
loRg(8/A)
16K Am
1440E[Dm
+1
Ax
A
A,20
(log (T) + 3 3log (T) log(30K))
1440E[Dm]
A
A250
2 K(log" 2 (8/A) + 3
log(8/ A) log(()))) + log(8/A)
A
2 log((') log(30KTT)
2880Cm 1440
Ak
24 K log 8 A) log
240K A)
+ log(8/A)
A
log (KT)
K log(1/A) log(//))og((//)) (K/o)((())))))))))
C+
A
A
A420
B.2
Proof of Theorem 2
B.2.1
Notations
We define O as the sum of corruptions to arm & in epoch m for all agents E [V], and let ma C
Cm
B.2.2 Lemmas for Proving Theorem 2
Lemma 8. For BARBAT with time horizon T, the number of epochs M most log(VT) In the m-th epoch, the selected arm kim must satisfy A m-1 (m-1)) for all agents v E [V].
lim
22(m-1)1 > m2 /V. From the lower Proof. The length of epoch m is given by Nm. 2
bound of Nm, we can complete the first statement. Since Am--1 +- max maxx(216 (2-(m-1), mm r there
exists least one arm that satisfies A 2 (mm-1) and all arms satisfy A < 2 (m Since p-
m-1 the equality A m-1 2- (mm-11) must hold.
Since the length Nm still satisfies Nm = K Km 22(mm11)))) EkEjKy n Lemma this setting.
Lemma 9, For epoch s and m with S s S m, the following inequality holds:
Am X <
Proof. We first show that the function f(x)
1.77 Ha(z)
is strictly decreasing for x 2
(7/6)*
Notice that the derivative function
f((x) (In(4) + 1/x) ((x + 1.7) lm(4) + In(x)) In (n)
(t)
is monotonically decreasing and ('(5) < 0, thus we have (x)x < 0 0 2 5, which indicates that
f(x strictly decreasing. Since K > 2 and V 1, we can get
Am In(4V K2 In 4)2 4)22(m+4)) In(4VK2 (V 1n44VK21n(VK)) + + 4) + (m + 4) In())
X
ln + (s (1)4)
28

---

1.7 In(4) + In(m + 4) - (m + Im(4)
1.7 -In(4) + In(s 4) - (8+4) In(44)
[mm + 4)
7
[(s + 4)
6
6
where we use the monotonicity of f(x) and the fact that K 2 and V 2
Lemma 10. For any epoch m, the following inequality holds:
Aa S 2 (m² + m(10 + In(VK)))
Proof. Given the function f(x) = 2z In 4) Im()). Notice that the derivative
function as (z) 2- 2 In(2) x 0 for all x 2 which means that f f(x) is strictly increasing
for x 2 1. Since f(x) f(1) 2 0, we can get the inequality 2x + 2(x+ + 4) In(2) + In(x +
for all x 2 1, then have
(4V (I (VK) + 4)22(s+4)))
(2((s + 4) ln + In(s + 4) + ((VKK)
(2s 7+ In
2mmm + 8m m ml x²))
$ 2 (m2 + mm(1++3mm) K))).
Lemma 11. For any fixed k and any Bm 2 4e Vom Algorithm 2 satisfies
(11(4/mm)
20m
Pr
mkl 2
S Bm.
Vina
VNn
Proof. Since in each epoch m. all agents have the same probability Pro (k:) of pulling each arm indicator variable yt which determines whether the agent
Using the method as Lemma 5 updates the corrupted reward Fu, into the total reward St,,, step f. We define the corruption step / on arm & for agent as C == Pr, Te Let Em = [Tm-I + 1, ...; Ti.] represent the N.. time-steps for epoch m. Since r
min m Eve(v] /TT 7ig ), 1}. we can obtain
S o.k
Σ teEm eE(V)
Σ
Ve C..)).
Tk
Vn
Vn
V
We can divide the sum to two components:
AT Σ Σ
to v.ke
BE
Σ E.
Σ vE[V]
Yr,
Ct
EE vE[V]
For the previous component A notice that rf is dependently drawn from unknown distribution with mean Pk. and yi, dependently drawn from Bernoullvdistribution with mean of = 7i /Ng/N,,.. Therefore, have
E[AT] = VN oe E = Vn μ4 S Vn
By applying the Chernoff- Hrerooff-ooofdding incquality (Theorem I.I [3] I,, we can get
AT Vn
3 3ln(4/3m))
Bm
Pr
2
<
(6)
V Ving
2
29

---

For the latter component B we need to define martingale difference sequence X ..... , X;, where X (Y,, 9%) )C for all t, with respect to the historical information { Since the corruption C becomes deterministic value when conditioned on Fi-1 and E [F-11 o% we can get
- FF = 0. E - = = -
Additionally, we have |X| < for all and all u E [V]. and the predictable quadratic variation of this martingale can be bounded as follows:
Var Σ Σ E(X))
Σ
Σ
(aa( S 9
Σ
Σ
IC
EE DE(V]
DE E.E... sE[V]
tEE. WE(V)
By applying the concentration inequality for martingales (Theorem in 34 ), with probability at
least 1
Bm have
4
B S 4
Σ
Σ
C. + Var + lm(4/3m) S 24
Σ
Σ IC + ln(4/
Fm VE(V]
EEE vE[V]
Since g0th
miK /n ElEE,. E 1C, S Cm and nx 2 Am 2 161n(4/Bon./V, with
probability at least 1 - Am 4
we can get the following inequality:
B
lm(4/Bm)
2C
16V
V Vin
Similarly, Vag
also meets this bound with probability 1 - B/4. Therefore, we have
B
In(4/Bm) 16V
20m
Bm
Pr
V VNm $
Vn
2
Combine Eq. 6 and Eq. 7 we complete the proof.
We also define an event En for epoch m as follows:
4 lmm44/m)
2Cm
Em
vk I
pal
Vnn
V VN
Lemma 12. For any epoch m, event &m holds with probability least 1 6m And after rigorous calculation, we have 1/6m 2 V
Proof. By Lemma
we can get
4lm(4/3m) Vnn
20m
8m VK
Pr |r
p4
< 2,8
VNm
union bound over the V agents and the K arms conclude the proof.
Since m 2 1, V 2 and K 2 2, then we can get
V VN KV2 Am
222(m-3 In((m + 2)2 V In(K))
K22(m-3) (Iu(m + 4) + 2(m + +5) In(2) + In(V
K22(m--4) ((m 4) (VV)))
1/8m-
30

---

As mentioned before. for each epoch m, to unify the varying bounds depending on the occurrence of event m. we also define the offset level
22 VN
when &m occurs
Dm
when Em does not occur
This way we can always guarantee the following inequality:
4ln(4/3m)
Dm VN
mal S
Vin
By the definition of Dm, we have
Pr(Dm 20ml 2 1 8m and Pr(Dm Nm] S 6m-
Next, we will bound the estimated gap Age To start, define the discounted offset rate
m
D2
Pm
NV.
Then we have the following lemma.
Lemma 13. For all epochs and arms k can have
4
2 6pm
8
2 (m- + 2pm
Proof.
Since Irk
MRl
S
lm(4/3m) Vng
we have
VN
D Vnm
441n4/8mm (m)4 Vnn
Dm VNm
4 4ln44/3m)
S Mk S
Vn
Additionally, since
Dm VN
4lm(4/Bm) m Vn
4 4mm(4/3m) Vinz
Dm VNm
p < max
M1 +
+
I Mk- +
4 In(44/ Bm))
41n(4/ (m)4
4ln(4/3m)
Dm
max
rk
Ving
Vina
2 pbk 2/
Vn
VN
we can get
Dm
4lm(4/3m)
Dm VN
VN 2V
STT T pk- I
V
According Algorithm and Lemma
2 we have Th
nik for all arms Then we have the
following inequality for all k E [
4 (m(4//m))
4ln(433m)
Am-1
Ving
Vn
8
We now establish the upper bound for AT m by induction on m.
For the base case 1, the statement is trivial as A = for all 1: E [K].
Assuming the statement is true for the case of 1, have
r r
(r
pk-) + (px. mb) + (μK - Tk
Dm
Dm 1 m-1
+A+
VNm -
VNm
2Dm + +
88A 7
+2 2 + 2pm
VNm
8A 2 (m-1) 2pm
7
31

---

Where the second inequality follows from the induction hypothesis. Next, we provide the lower bound of AE. We get
A
Th
(k-) ) (112 -1k)
(14 rk
k
Dm
Dm
Am:
+ DF
VNm 8 - - 1m-1
VNm
2Dm
18A
+ Ds
+ 2 (m- + +22m--1
Nm
7
3
Ak
2-m
6pm.
2
where the third inequality comes from the upper bound of A m-1
We only introduces a small change into the parameter Am. by simple calculation, Lemma 3 still holds.
B.2.3 Proof for Theorem 2
We first define the regret R% generated by arm & in epoch m for agent v as
k: + ki
R e
A
m
k = km
Then we analyze the regret in following three cases:
Case 1: 0 Ax S 64pm-1-
If k o km then we have
R = A I 64pm-11
If k km, then have
R
I 64pm-1 1
Case 2: As < mm and Pm-1 S
A
64
If ls of km then have
16Am
R U Di = Am (A S Am 12 A 5
AF
If k km since Am-1 2 (m--1), we can get:
16K Am
16K Am
R 1i Akm S Nma = KKA 22(m-1)7A
Apm
km
A
Case 3:
A > 8 m and Pm-1
S
A 64
By Lemma we have
3
6
A Am-1
k
2-m
A
k
2 0.29A
In this case, it is impossible that k = kim because So obtain
m-1 km
2 (m-1)
< 0.29 8 2-
< 0.294r.
X
16\m
RT
nith A (Am-
0.292 A
A
32

---

We define A {k [ < As I 64pm-1} for epoch m. By combining all three cases, we can upper bound the regret for agent v as
R(T)
Σ
R
Ri
m=1
mm
M
64pm- Nm +
64pm-1
Σ
16Am
A
m=1
REA t kom
hEAm Ac>0
16K Am
+ 1)
+
I100
km 58.2
A
(8)
M
16Am
$
64pm-1 Nn +
Σ
+
A
m=1
Ax30
Ax70
16K Am
+ 11 (m S logz (8/A))
A
<
M
128pm +
16Am
(8/2(
Σ
(66K Am
+1) 1
AB
A
m=1
A,30
m=1
where the last inequality uses the fact that Σs ni S Nm. Notice that we can bound the expectation the offset level
[D = =2(1 6m + +.m
S 20m +
and we can bound EM 1 Pm 1mm11 Nm as
M
M
D
Σ
Nm
Nm
8m
-VN
m=1
m=l
4
(4 1)Am D.
V
8m-11
(7/12) (7/48) Do
M
M
D
(7/12) 11 + (7/48) 118
m=s+1
11 M-1
Dm
(7/12)² (7/48)² < V
Σ Dm
m=1
m=1
33

---

Combining Eq. 8 and Eq. (9) by Lemma 10
we can get
M
(8/2(
(T) S
1440E Dm]
+
Σ
16Am
Σ
16K Am
+1)
A
A
mm
A 20
m
M
2 (VT) 3 log VT) 1og(30V
<
1440E Dm] +
VÂ
m==
A,50
2 K 2log2 (8/A) + log((8/A) (30V 30V)))))
+
+ log(8/A)
VA
M 1
Cm
2 (V) log(30V KT)
<
2880
1440 +
V
VDs
m=
A,50
2
K log(8/ 8/ A) (2g(2 K/A)
+
+ log(8/A)
VA
ITg(T) log(VKT)
Klo (1/ /A) (VK(V)
=0 +
VA
VA
A,50
So the cumulative regret for all agents
R(T) 1m--0
(c (
log(VT) log(VKT)
log(1/A) log (VK/A)
Σ
A
A+
And each agent only broadcast messages the end of each epoch, so the communication cost of MA-BARBAT as follows:
Cost(T)
Σ
M OVV log(
NE[V]
B.3
Proof of Theorem 3
B.3.1 Notations
We define C as the sum of corruptions arm & in epoch m, and let C.m e maxke[K] C
B.3.2 Lemmas for Proving Theorem
Lemma 14. For the BB-BARBAT algorithm time horizon T,, the number of epochs M = L. In the m-th epoch, the selected arm km must satisfy A k.. (m--1)
Proof. The length of epoch m is given by Nm K KAm a (m > a 2m From the lower bound of
Nm and a 7 T1,+11, we can complete the first statement. Since A 2 +- max (a (a--(n (m-11) r rk
there exists at least one arm that satisfies A mm a (m-1) and all arms satisfy A mm s (m 1)
Since m km > pm-1, the equality m km 2- (m-1) must hold.
Lemma 15. For any epoch m, the length Nm satisfies Nm 2 ExE(K n
Proof. Since A = max (aaxxa= (a= n - -r Therefore, we have ΣkE[K] mi K KAmaaai 2(m-1) Nm-
a m we can get
Am Am 11) s Am (mm-))
Lemma 16. For epoch s and m with 1 S s S m, the following inequality holds:
Am
X
34

---

Proof. We first show that the function f(x) +nn(a))+n(()) (7/5)=
is strictly decreasing for 2 5, where
a = ==max max (220+)) ,2 2
Notice that the derivative function
f'(x) (In(a²) + 1/0) (xr In(a²) In(a:) In (5)
(3)²
is monotonically decreasing and (5) < 0, thus we have ('(x) < for x 2 5, which indicates that
(ax ) strictly decreasing. Since K 2 2, we can get
Am
In(4k" ( + 4)a2(m+4))
X
In(4K2 In( + 1))
([()))((())) + Im + 4) + (m + 4) In(a²)
In(4K>In(K)) (n + 4) (s 4) In(a²)
In(m + 4) + (m + In(a²) In(s + 4) + (s lm
f(m 4)
m-
7
m-8
f(s + 4)
where we use the monotonicity of ((x) and the fact that K
Lemma 17. For any epoch m, the following inequality holds:
Σ A S 2a In(a)(m + 3m + In(K))).
Proof.
Since a 2 and K 2 2. we can have
a [b(44> (4 4)a2(++1))
a (2((s + 4n(a()) + In(s + 4) + In(4 In(aK)) In(4K)I((K)))
a (2(s + 4) ln(a) + 2(s l) 6ln(K)
a In( 10 6l)())
s=1
2a (m + 3m In())))
We can also guarantee Lemma stiil holds. As mentioned before, given the definition of event En as follows:
4 1l(4//3m)
20m
Em
vl k: 1
14 <
n
N
Then we can establish lower bound on the probability of the event &m occurring by the following lemma.
Lemma 18. For any epoch m, event &m holds with probability least 1 6m, We also have 1/5m 2 Nm-
Proof. By Lemma
5 we can get
4
4
20m
8m
Pr
< 2mm
Nm
K
35

---

A union bound over the K arms conclude the proof.
Since
K 2 2 and 2, then can get
Nm = KAm a 2m-11)
Ka 2m++++3)) In In(4 (m 4)a (m++4) In(aK))
< 2m)(+)3)
(2(m + 4) (n( + In(m 4) In(K In(aK)) In(aa)((KK))) + In(4))
S Ka 2(m+3))
(2(m + 4) () (m ()lk(a + 3ln(a)) + 2ll(aa))
S Ka Ka 2(m+3)
(6)
Ka (m)())4)
4)
1/0m-
As mentioned before, for each epoch m, to unify the varying bounds depending on the occurrence of event Em, we define the offset level
20 N
when &m. occurs
D
when &m, dose not occur
This way we can always guarantee the following inequality:
4 (l144/mm
Dm
Ir - ukl S
N
It is worth noting that Pr[Dm- = m0 2 1 - 6m and Pr(Dm Nm] S 6m.
Next, we will bound Ar. To start, define the discounted offset rate
2m- D. a (mm-))
Pmn
Lemma 19. For all epochs m and arms k, we can have
a²
a² -
2a a
6pm S A
As + (m--1 + 2pm
a
Proof.
Since Im
M1l S
1ln(1/9m)
Dm N.
we have
Dm
4 lmm44/m))
Dm Nm
4mn44/mm
Mk 5
+
N
70%
Additionally, since
Dm
41n(4/ Bm)
4 1mm4/3m)
Dm
T S max
Mb +
+
2 Mk +
Nm.
71%
Tik
Nm
(l(44/m)) 7ik
441(4/33m)
41n(4/3m)
Dm
mm
max
rk
2 mm
2 Mk - 2
nx..
Nm
we can get
Dm
4ln(4/3m)
Dm Nm
S Th
ph- <
N
According Algorithm and Lemma following inequality for all k E [K]
we have Th
no for all arms
Then we have the
1m(44/8m)
4 4ln(4/mm)
2A m
a
36

---

We now establish the upper bound for A by induction on m.
For the base case m = 1, the statement trivial as A = for all & E [K]. Assuming the statement is true for the case of m - 1, we have
m r.
rk
(r pk-)
+ (pI - mb) + (#+ - 1%
D
D
2
+ Ab +
Nm at A mm
Nm
2Dm
2
a A'
+ D
+ (m-2) + 2pm-
Nm
at
a
a² A
(m-1) 2pm
a² 2
Where the second inequality follows from the induction hypothesis. Next, we provide the lower bound of AT. We can get
rk
(r
px-)
+ (#22
- -4h + (f4 rkk
Dm
4
Dm
2 m-1
mm
+ As
Nm a A
Nm
a=
k'
2Dm
m
6
Aa
a
+ (m-2) 2pm
Nm
at
2
8
3
A
a
6pm
2a
where the third inequality comes from the upper bound of A Am-1
B.3.3 Proof for Theorem 3
We first define the regret Ri generated by arm in epoch m as
An T
k + km
R
A
A
k km
Then analyze the regret in following three cases:
Case 1: << As & 64pm-1-
If le + km then have
R Agn S 64pm m
If k = km then we have
R A S 64pm-1 Nm.
Case 2: As 54.00 24-a-(m-1) (mm-1 and Pm-1 <
Ax 64
le o km then we have
Am
R n2t Do Am (A (Am--)-2a} S Am 2(m amm 1 5
A
If k: km since A kmm
2- (m) can get:
16K Am
16K Am
R 72 km Akm I NmA = Km 2(m 2(m
+ Akm
+ 1.
Akm
A
Case 3:
A. > 4. a (m--1) and Pm < d+
64
By Lemma 7 we have
3
6
A m
As
a
m
AB
>
Ao
1
>
0.29
4 2
2a
64
a
2
8a
64
37

---

In this case, it is impossible that K = km because mm-1 km
a (m-1) <
1.299-4a--0 < <0.99A.
So we can obtain
16Am
R nig D Am (4 (1 S 0.29 A
A
We define A {k E [K] < D S 64pm-1} for epoch m. By combining all three cases, we upper bound the regret as
R(T)
Σ
R
Σ
Rm
A
Σ
16Am
64pm-11Nm +
64pm--1%
A
REAT Re
REAm AE
16K Am
+1) 11(0 < Akn $4.a a4.a-(m-1))
+
A
16Am
64pm-1 1N + Σ 64pm 1ng +
Σ
A
m=1
Ax30
Au20
(10)
16K Am
+1 11 (m S logo (4/A)+
+
M
162m
<
64pm-1 Nn + Σ
64pm-
m2
+
A
m=1
A430
A4s0
16K Am
+1) 1) I1 (m S logg (8/A))
+
A
M
16Am
(8/2)
16K
128pm-1 N +
Σ
+1)
DB
m=m
A,30
mal
where the last inequality uses the fact that Σ expectation of the offset level as
Nm.
Notice that bound the
E[Dml 2(1 - 5m + Nm S 20m +
and we can bound Σ Pm 1m
M Σ
M
m
2m am-11- D2
Pm-
Nm 5
Nm
a 4(m No
m=1
M
((2a²) )m 1 1-s + 1)Am D2
a
a4(m-1-s)
m=1
14 m-1-3
a²
D2
5
(11)
M
14
m-1-s
m
1-s
a
D
5a2
a
m=8+1
M
< ?
Σ m
Σ
14
+
1
5a
a
m=1
5
a
M-1
22a² 2 M
< 2
Dm <
Σ
Dm
5a 14
a
m=1
m=1
38

---

Combining Eq.
10
and Eq. 11 by Lemma 17 since T
and M L,
get
R(T)= 2
M
570a 570a"E[Dan E[Dm]
+
M
16Am
(8/2(8/A)
Σ
16KAm
+1
A
A
mim
Ag >0
m=
(8/2(8/A)
161m
16K Am
570a 3T0m2 +
Σ
+1
Ak
A
m=
L 3L(2 + log(K))
1140a Cm 570a² 2 In(a)
Σ
A
m=1
A+20
K (logg (1/4) + 3log(8/4) (og(K))))))))) (K))
+ (0/2
(CTEEE CCTEE+TTR +TIi
loog(KT)
K log(() log log(1/A) log k/A))
4
LA
B.3.4 Proof for Theorem 4
Proof. In batched bandit problem, the static grids be defined as to <4 < ,4 =T According to Lemma 2 in [1), the lower bound for stochastic batched bandits with no corruption are given by:
= 0, =0 K max t2
(12)
jE(L] 1--1
For adversarial corruptions, define adversary who starts attacking at round and continues until the end of a batch, denoted by tg for 0 < 8 < The attack strategy involves setting the rewards of all arms to zero, forcing any algorithm to pull all arms evenly in round 1, which leads to regret of approximately 1, - 11-1. Therefore, under adversarial corruptions, the lower bound can be expressed
13+1 lj
R(C, =
K max +C.
max 3EIL-11
t--1 ]E[L]
tj
l - 1
=
Kh (K C)
(13)
jE(L.-1]
tj
T I
0
K4 + (K C)
4-1 Combine equa-
According the formula, we can get the optimal value of 4 =
[K(--)) K+C
tion 13
we can get
RCC, L) 2 2 (Tt (K (K=CO C (k=C
B.4
Proof of Theorem 5
B.4.1 Lemmas for Proving Theorem
By employing the methods described above, we establish that Lemmas 2 contrast to the standard multi-armed bandit setting, the feedback structure in model implies that, for each arm k. the expected number observable pulls ny does not necessarily equal the expected number of actual pulls n
and remain valid. In
Lemma 20. For any epoch m, all arms k + km must satisfy ny S no and it n
Proof. By Algorithm 4 we can easily guarantee that the inequality 7m S n holds for arms k & Km. Recalling the setting of strongly observable graph, for each arm k either it has self-loop
39

---

or all other arms have an edge pointing to it. According to Algorithm follows for each arm k- E [
we can get the guarantee as
Σ
T0k
So for each arm which has a self-loop, we have the following inequality:
Σ
THE Fh:
Th + Fikk
2 nkk m
B.
For each arm which does not have self-loop, since n 2 m 2 n for all arms o kim 80 we complete the proof.
L
Same as the proof in Appendix B. we only need change oi to ng to obtain the following lemmas.
Lemma 21. For any fixed k, m and Bm. Algorithml satisfies
4
(l444Bm))
2Cm Nm S Bmm
Pr
rk
PR 2
We also define an event Em for epoch m as follows:
Inn (m
20
Em
A
4 k: 1r
MAl S
N
Lemma 22. For any epoch m, event &m holds with probability least 1 6m And after rigorous calculation, we have 1/6m 2 Nm-
We also always guarantee the following inequality:
4 1ln(4 1l(44/m)
Dm
In
pal S V
+
Nm
is worth noting that Pr[Dm = 20m] 2 1 8m and Pr(Dm = Nm] S 6m.
Next, we will bound Ar, which is also the turning point of our proof. To start, we define the discounted offset rate as
D2
Pm
8t
Lemma 23, For all epochs m and arms Ko # k., we can have
3 2 6pm - A A + +2 (m--) + 2pm
A.
for the optimal arm k", we have
1 A + (mm-1) + 2pm
6pm < A
<
7
Proof.
Since In
Mkl
4 41n44/8m)
Nm we have
Dm
4 (mm(4/mm)
Dm
4 1n 1l(44/8m)
N
Srb 1ike S
Nm
+
V
fm
By Lemma 20
we can get nm 2 ni for all arms 1s + ki and kkm E Eiskii
Th for arm km. Then
we have the Following inequalities:
4 4ln(4/Bm)
4ln(4/Bm) Bm))
m-
Vk o km
n2
40

---

and
4l(4/3mm)
41n(4/3m)
A m--1
max Regt
min Reghe
Tkkm
Additionally, given that
Dm
4ln(4/Bm)) %
4 4ln(4/3m) 1
Dm
max
1ik
+
S pk. +
Nm
Nm
and
Inn (l(4/3m))
P
max
Tk
12
4 (m(4/3m)
2 1--
D
2 Pkk-"
max { A m-1
min
A
m-
4
Nm
Dm
2 pk-
A An-11
Nm
It follows that
Dm
Dm
1 m-1 A S 1 pke S
Nm
Nm
We now establish the upper bound for ATT using induction epoch m.
For the base case m 1, the statement is trivial as A = for all l E [K]. Assuming the statement is true for 1, for arm k * k. since there least two arms: one optimal arm and one sub-optimal arm, we can obtain
8 A + 2 (m-1) 2pm-
min Am-1 S max ( A Am-1 1) kepkk
Then we have
rk
(riTh px)) + (/4, m4)) + (14 -/"))
Dm
Dm
+ D₁ +
Nm + 8
max Am
min A m
Nm
2Dm + D + 8
/8 maax Des A}
<
+ (m + 2pm
Nm
8Ak 2 (m- + 2pm
Where the second inequality follows from the induction hypothesis. For arm 1., we have
(r. p.)) + (Mr - px-) (px= r
Tk
Dm
Dm 1
+maxfA m-1 min Am-11
Nm
Nm
k
2Dm
8A
+ 2 (m + 2pm-1
+
Nm
8
1
A + 2 (m--1) + 2pm
41

---

Next, we establish the lower bound for AT Specifically, for arm k o h- we demonstrate that
A
1
(r
u.) + (M+ mxx) + (uL rkk
2
Dm
max
m k- A 8- } + 4 x.
Dm
8 x
Am-
Nm
4
Nm
2Dm
8 max As, A}
A
+ 2-
(m-2) + -2
Nm
3
IV
m
6pm
where the third inequality comes from the upper bound of A mm For arm k., we have
A m
(T
[.)
+
(1,,
px-) (#x-
rk--)
Dm
1
Dm
1
max
A vo- A A
A
Nm
4
Nm
2Dm
8A
+ (m + 21m-1)
Nm
3
3
2-m m
6pm
7
2
This proof is complete.
Lemma 24, For any strongly observable directed graph G with the independence number a, the obtained out-domination set D must satisfy [D] I [a(1 + 22n(2n( (n(K/a))] by Algorithm 0 Especially, when G an acyclic graph and undirected graphs, we have D) S a.
Proof. If the graph G' is undirected, then in each iteration of the Algorithm 6 we select a vertex and remove its neighbors. The selected vertices therefore pairwise non-adjacent and form independent set; hence the resulting out-dominating set D satisfies D S a. The remainder of our analysis focuses on the directed graphs.
Recalling the definition of the no-root vertex, for any strongly observable directed graph G with the independence number o, can get that if we remove a no-root vertex & and its out-degree neighbors, the remaining graph G' whose independence number is at most a 1. That's 's because no vertex in graph G' is connected the vertex k. By the definition of strongly observable directed acyclic graph, we can always get the no-root vertex for the remaining graph, which means that DD S a.
Recalling the pseudo-code in Algorithm 6 we denote the loop index as and initialize other words, G, ([V.), F.) shows the residual graph obtained after s loops of removing vertices. Given any graph G. ([Va], E.) with no no-root vertices, Go41 is obtained by removing from G, the vertex i, with the largest out-degree d. Hence,
0. In
Fss
V.
V
d
2
2
2
Vs
20.
2
2a
2'
by Turan's 's theorem (e.g.. that
35 where o₂ is the independence number of G, and a 2 0s,, This shows
1
V4+1
[V
d V.
/V/le
2a
Iterating, obtain [V, < 1/21/2a We define the graph G.. ((V,,) E.g)) with the independence number Otsp as the the final residual graph has cycles. We can discuss this in two cases:
Case 1: VVal < a.
We can get a graph Gs, = (VV, I. Es,) with 81 I 8p, which satisfies VV, < a and VV,--1 2 a. Since Va,-1 < Ke (=1-1)/(2n), we have $1 - - [2 In < In(/aa] So we get
DD| [V,, + 2a In + +15 [a(1 2l((K/a))].
42

---

Case 2: Veol 22 a
By Ve S Ke Ke=so/(a), we have so I 22 In K/ 1) Σ [2/]][ Because Gop has no eycles and the independence number Ctsg a, can get
D Σ aso + |aaln(K/aa] & [a(1 + 2l((K/)))].
The proof is complete.
B.4.2 Proof for Theorem 5
Recalling Lemma 23 for all arms + k", we have
A 2
6pm S A
7 A +
2-
+ 2pm-
We first define the regret Rg generated by arm epoch m as
A E t
+ km
R T
A
kim
Then we analyze the regret in following three cases:
Case 1: 0 AS & 1-
If ls o km then have
R ARTi 64pmm-1m
k: km then we have
R%
A km S 64pm- Nm-
Case 2: As 2.22 and Pm-1 S 64
If le o km, then have
162m
R n2k D5 Am (A S Xm 22(m-1)
AK 5
AB
If 1: km since A Km 2 2- (m-1) can get:
16K Am
16K Am
R
w Tkm
Dpm Nm [K 2
Akm
+ Akm.
km
1.
Case 3:
4. > 8.2 2 and Pmn-1 I
At 64
By Lemma we have
3
3
k
2
A
> 0.294
64
16
64
In this case, it is impossible that l- ki because A So we can obtain
m-1 km
2 (m--1)
0.29 8 2-
< 0.29Ak
Am
16A
R no. A >am (Ag
5
0.29 A
A
43

---

We define A {k [K] can upper bound the regret as
< As I 64pm-1} for epoch m. By combining all three cases, we
R(T)=
R
Am
M
16Am
64pm-11. +
64pm-1nk m
A
m=1
REAm Re
h@Am Ac>0
+
16K Am
+ 1
I10
km 58.2
A
(14)
M
167m
64pm-1 Nn +
Σ
64pm-
111k
m
+
A
m=1
A=
Ax
16K Am
+1) [m S loga (8/4))
A
M
16Am
18/2(8/2)
16K Am
+1)
128pm
+
AP
A
m=1
A,30
m=1
where the last inequality uses the fact that Ean>o " S Nm- expectation of the offset level
Notice that we can bound the
E[Dml = =2(1 - 5m) + 5m S 20m +
and we can bound EM= Pm N as
M
M
D2
Pm Pm- N I
Nm
8m-1-55 1-NNo
m=1
m=1
(4m-1-s + 1)2m D2
8
m=1
M
m
Σ
(7/12) (7/48)=-1-0)D,
(15)
M
M
4
D (7/12) m-1-s + (7/48)m-1-9
sm1
m=s+1
<
Σ
Dm
(7/12)² + (7/48)² < 11 Σ Dm-
Recalling the pseudo-code of SOG-BARBAT in Algorithm 4 we define the loop (Line 10-16) index as a. For ease of analysis, removing multiple arms from m in one loop, we also consider this case as multi loops where the H is set by zero. According to the above analysis, we have n < 16Am
A?
Defining b K |, by Lemma 24 we can a parameter 7th max,=1,2.-.. | With loss of generality, for each arm & E A we set A; 2 A2 2 2 A.. Recalling the process of Algorithm 4 we only need to pull H" times for all arms in the out-domination set Dmm where observe at least H" times for all arms k [K]. By this way, to maximize the value of Exe R we should try to select the larger part of the suboptimal arm from the arms that have not been removed. In addition,
have the following inequality:
16
16Am
16Am
H S m
H
T
H
S
H
H S
A
A
44

---

By this way, we can get the following equation:
sup
Σ
Rs = sup
Σ
Ha
Σ
A
kE
==1
REAAD,KEDE
b- b-y
16Am
16Am
16Am
167m
Σ
As
+
A
A
A
A
A
--1
k=
s=b-ym42
s=b-
16Am
16Am
16Am
A
A
A
2ry
20Am
16Am
16Am
32
4
S...
A
A
D
k=
mm
k=b-ym
k=b
(16)
In the second inequality, for case write, we set 16 = 0. For the above inequalities, we use the 8n
2
inequality
+
(
+t) Aym+t S A holds for all 2 2 31 3o 2 For example, in
De
4m
the first inequality, we have
16Am
2ry
16Am
16
A
Rmmny +1
24
20Am
= 16Am
+
A pm
A
A2
A
A
mm
k=y
+1
Combining Eq. 14
Eq. 15
and Eq.
(66). by Lemma 4
we can get
(8/2(
16Am
16K Am
R(T)= S
1440E[Dm]
+
2,30
2 2 "log" (T) + 3og (T) log(30K)
1440R(DmL +
A
AESO
22 K(logl (8/A) + 3-3 log(8) (8//8//A) Alg (3g(()
+ log(8/A)
A
24 log (T) log
2880Cm 1440
Σ
Ax
A,30
214 K Klog (8/A) log
(240K/4//))) A))
+ log(8/A)
A
2 log (T) (30KT)
2880Cm. 1440
A
KEI
211 MAKKI logg(8/
(8/ A log (240K/A))
+ +lgg(8/A)
A
=o
c+
log(T) log(KT)
llog(1 log///)oKKK)) (K/A)
C+
A
A
KET
where I" is the set of at most [a(1 + 2 2 (/))))]] arms with the smallest gaps. Especially, for directed acyclic graphs (including undirected graphs), I" is the set of at most a arms with the smallest gaps.
45

---

B.5
Proof of Theorem 6
B.5.1
Notations
Following [13 [4], with loss of generality, we assume #1 2 P2 Px and A₁. pb Md for all arms k > d.
B.5.2 Lemmas for Proving Theorem
By the methods mentioned before, Lemma still holds, For Lemma 2 we need to consider the impact of changing km representing an arm to representing an arm set.
Lemma 25. For any epoch m, the length Nm satisfies dNm 2 Ekek ni The actual expected pulling times noy 2 n%k for all arms k [.].
Proof. Since A max (2- r rk 2 m we can get
14 11-m-11 < 2m(m11))
Tik
Therefore, we have
Σ
= d.N. "k m S K KXm222mm 22(m-1)
kEK
Since Nm = K KmAm2 22 /d, so for arm E Kmm we have
N
Σ n Am 22(m-1)) 2 nkk
AgK....
This proof is complete.
Using the methods mentioned before, all lemmas in Appendix B. still holds. Maybe Lemma will be different because we changed the way rith is assigned. Next we will prove that Lemma holds.
still
Proof.
Since |r Mkl
4lm(4/9m.) "i
we have Nm.
Dun.
Dm Nm
4 4ln(4/Bm)
Dm
4ln(4/Bm) 1ikk
S rr
14k S
+
Nm
Additionally, since
Dm
Inn 4lm(4/3m)
4lm(4/Bm)
Dm Nm
m S Ta
14k +
+
S pa +
Nm
71
kE[K]
14 14ln(4/Bm)
4ln43/mm) 72
44 44nn44Bmm)
Dmn
Ta
rk
2 rdd
2 pd 2
72kk
Nm
KE[K]
we can get
Dm
4 lm(44mm)
Dm Nm
2
< <r.m Pd S
N..
According to Algorithm and Lemma following inequality for all & ee [K]:
2 we have Wi 2 not for all arms Then we have the
4 41n Bm))
4 1ln(4/3m)
AT
n
8
We now establish the upper bound for AT m by induction on m.
For the base 1, the statement is trivial A for all e [K].
46

---

Assuming the statement is true for the case of m - 1, we have
A
rk
(r ua) + (Md ua) + (ui 1 r(e)
Dm
Dm
1 -
+ A +
Nm + 8
Nm
2Dm
18Ak
D +
(m-(m=22 2) + 2pm
Nm
8 7
8Ak
2 2-(m-1) + 2pm
Where the second inequality follows from the induction hypothesis. Next, we provide the lower bound of AE We can get
(r
1a)) + (1a 11)) + (14: r%)
Dm
Dm
1
Am-1 k-
+ A
A m-1
N
Nm 8
2Dm
3
88k
+ Ab
+ 2- 22(mm22) + 2pm
Nm
8
4
3
A
-2 2
6pm
where the third inequality comes from the upper bound of A Am-1
B.5.3 Proof for Theorem 6
Following to the work 15 we can define the regret Ri generated by arm & in epoch m as
Aang ARTT
l: $ Km
R A P
k: E Km
Then we analyze the regret in following three cases:
Case 1: 0 A < 64pm-1-
If k & Km. then we have
R Agni S 64pmm-11)
If l: E Km then we have
R Agngg S 64pm-1dNN
Case 2: Ag $8.22" and Pm-1 S A If ls & Km, then we have
162m
R = n2K A = Am (A (Am-1)-224 S Ann 22(m-1)
A 5
A
If 1: E Km,s since Am-1 22(mm-1) we can get:
16Kd
16Kd>m
Rm 71 km < dN
/d|
dDkk..
km
+ d.
km
Case 3:
A > 8-2 2m and Pm-1 I
By Lemma 7 we have
m
As
> 0.29
64
16
64
In this case, it is impossible that E Kmm because A So obtain
m-1
(m 1)
< 0.29 8 2- < 0.29Ar.
km
Am
16
R = no A = Am (A (Am-1)-22
-2A
<
<
0.292 4
A
47

---

We define A {k [K] can upper bound the regret as
< As I 64pm-1} for epoch m. By combining all three cases, we
R(T)
Σ
Ri
Σ
R
m=
hEAAm
k@Am
M
64pm IdN
64pm- m +
Σ
16Am
A
m==
KEAA Aophilm
kEAM A..0
16Kd>m + d 1(0 Aen. 58.2
+
(17)
M
16Am
14pm--1dNn
+ Σ
64pm-1 +
Σ
4
Ax30
Ax30
16KdAm +d)
1I S logg (8/A))
A
M
16Am
(8/2(8/A)
16K 16KdAAm
128pm 1dN +
+
+
As
A
m=l
A020
m=1
where the last inequality uses the fact that Σs ni S Nm. expectation the offset level
Notice that we can bound the
[Dm]] = =2(1 6m + 5m S 20m +
and we can bound EM 1 Pm 1m Nm as
M
M
m-1
dN <
d.Vm
8m--1- N
m==
m=1
==1
(4m-1-s + 1)2m De
< 4d
8m-1-o
4d
(7/12) (7/48)--1-3))
(18)
4d
(7/12) + (7/48) m-1-
m=s+1
< 4d
Σ
D
(7/12)² + (7/48)² < l1d Σ Dm
m=
m=1
48

---

Combining Eq. 17 and Eq. 18 by Lemma 4
we can get
(8/A)
16
16KdAm d
R(T)= 6
1440EldDml
Σ
A
A
>0
2 (log (T) 2log
(T') + 3 log(T) log(30K))
1440E
A
AL50
2 2 "ddllog' (8/A) + 3 log(8/ A) log (30K)) (log(8//A)
A
M-1
2 (T' log(30K7)
$
2880dCm 1440d
A
Ax30
2 Kdllg(8/A)) log (240K/4 A)
dlog(8/2)
A
=0
(dc+ Σ
log(T) log
dK dK log(1/A) (og()))oog(//////
4
A430
49

---

BARBAT
DRAA
IND-BARBAR
IND-FTRL
K 12
0.13 s
1.53 0.15
0.14
0.12
K = 16
0.13 s
0.14
1.91
Table 2: The cost time of each agent for BARBAT and all baseline methods.
(a) K = 12
(b) K 16
Figure 4: The feedback structure for the strongly observable graph bandits.
C E Experimental Details
C.1 Cooperative Multi-Agent Multi-Armed Bandits
We first consider CMA2B, where the mean rewards {14 }RE(k) is uniformly distributed in the interval [0.02, 0.96]. For each arm k, we generate the stochastic rewards according to a truncated normal distribution with support [0. 1), mean μ4g, and variance 0.1. We use a time horizon T 50000, set the corruption level C = 2000, 5000 and the number of arms K = 12, 16. Following [1O] we set the two worst arms as target arms and corrupt the target arm's reward and the other arms' rewards to zero until the corruption level is exhausted.
As in Table 2 the time cost by BARBAT is much shorter than that of the FTRL, which confirms that the computational efficiency of the BARBAT framework is much higher than that of the FTRL. framework.
C.2 Strongly Observable Graph Bandits
Following 10],
we adopt the Erdos-Renyi model 36 generate feedback graph in Figure
4 with
the independence number a 4. Specifically, for each pair of arms vu [K] x [K] with u = we connect them with fixed probability 0.5. Blue circles represent vertices without self-loops, while white circles represent vertices with self-loops.
C.3 d-Set Semi-bandits
In d-set semi-bandits, we set d = 3 for K 12, and d 4 for K = 16. Following the recent works [5 177, we generate the stochastic rewards according to Bernoulli distribution, other settings the same cooperative standard MAB.
50

---

BARBAT
HYBRID
LBINF
LBINE_LS
LBINF_OO
K = 12
0.36
14.63 S
10.16
10.21
9.84 S
= 16
0.37
18.62 s
12.37
12.67
12.69
Table 3: The cost time of each agent for BARBAT and all baseline methods.
As seen in Table the time cost by BARBAT is much shorter than that of the FTRL, which confirms that the computational efficiency of the BARBAT framework is much higher than that of the FTRL framework.
51


Reviews:
[{"review_id": "HkrsGCxApp", "reviewer": "Reviewer_FSFH", "summary": "This study investigates the problem of stochastic bandits with adversarial corruptions. The authors refine the BARBAR algorithm and resolve an open issue presented in Gupta et al. Under the refined algorithm, the regret bounds are improved across various settings. The advantage of this algorithm, compared with other algorithms such as Tsallis-INF, lies in its computational efficiency.", "questions": "See above.", "limitations": "N/A.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The authors provide a general framework for stochastic bandits with adversarial corruptions. Although several algorithms have been proposed, many of them are computationally costly, which is undesirable for settings such as graph or batched bandits. For example, $(1/2)$-Tsallis-INF requires solving an optimization problem at every step, which makes parallelization difficult.\n\nBARBAR was proposed by Gupta et al. and is known to be computationally efficient. However, its regret does not match the lower bound with respect to the number of arms $K$ and the corruption level $C$. The authors refine the BARBAR algorithm and extend it to the settings mentioned above. They show that the new algorithm achieves favorable performance while retaining computational efficiency.\n\nI believe the authors’ contribution is worth accepting to the conference; however, I still have some concerns. The main issue is that the regret bound is not tight in $T$. For example, if the algorithm incurs $\\log(T)^2$ regret in the stochastic bandit setting, one could instead use Shannon-FTRL, which also achieves $\\log(T)^2$ regret and is computationally efficient.\n\nMinor comment: In the abstract, the authors use $K$ and $C$ without definition. Although the meaning can be inferred, it may be confusing.", "was_revised": true, "final_justification": "As I replied to the authors, they have fully addressed my concerns. I believe that this study makes solid contributions. However, I personally find them not particularly surprising. I will maintain my original score, weak accept.", "rebuttal": "Thanks for your detailed review of our work. Here are our response to your comments.\n>The main issue is that the regret bound is not tight in $T$. For example, if the algorithm incurs $\\log(T)^2$ regret in the stochastic bandit setting, one could instead use Shannon-FTRL, which also achieves $\\log(T)^2$ regret and is computationally efficient.\n\nWe acknowledge that $\\log(T)^2$ regret is not tight, and we believe that finding a way to achieve optimal regret for adversarial corruptions using elimination-based methods is an interesting open problem. We think our work has made significant strides toward addressing this issue.\n\nThough Shannon-FTRL also achieves $\\log(T)^2$ regret and is computationally efficient in the stochastic MAB setting,  our method outperforms Shannon-FTRL in many extended scenarios. In the strong observation graph bandit setting, Shannon-FTRL achieves only $\\log(T)^3$ regret, which is worse than the regret bound attained by our method. In the $d$-sets bandit problem, to the best of our knowledge, there is no computationally efficient FTRL-type robust algorithm. As pointed by Tsuchiya et al. (2023), the computational cost is the main limitation of FTRL framework, especially when the optimization problem does not have a closed form. Additionally, for the batched bandit setting, our work provides the first algorithm that is robust to adversarial corruption.\n\n> In the abstract, the authors use $K$ and $C$ without definition. Although the meaning can be inferred, it may be confusing.\n\nThank you for the comment. We will include the definitions of $K$ and $C$ in the abstract.\n\nReferences:\n* Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worlds algorithms for online learning with feedback graphs. NeurIPS, 2022.\n* Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits. In ICML, 2023."}, {"review_id": "HP2TC0nHn8", "reviewer": "Reviewer_dQYX", "summary": "This paper proposes BARBAT, a novel algorithmic framework for stochastic multi-armed bandits (MABs) under adversarial corruptions. BARBAT improves upon the BARBAR algorithm [1]  by eliminating the suboptimal corruption-dependent term $\\mathcal{O}(KC)$  in favor of a near-optimal $\\mathcal{O}(C)$ regret bound up to logarithmic factors, where $K$ is the number of arms and $C$ is the corruption budget. The authors further demonstrate the versatility of the framework by extending it to multi-agent, batched, strongly observable graph, and d-set semi-bandit settings, providing tailored algorithms and regret analyses for each. The theoretical results are complemented by empirical validations, showing that BARBAT and its extensions outperform prior methods in several regimes.\n\n[1] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562–1578. PMLR, 2019.", "questions": "Please see the Weaknesses section for related questions and concerns.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Below is a summary of the paper’s main strengths and weaknesses.\n\n**Strengths**:\n\n1) The paper successfully generalizes BARBAT to four complex and practically relevant settings. The algorithmic adjustments for each extension are thoughtfully designed and maintain the core advantages of the framework. For each setting, the paper provides tight regret upper bounds.\n\n2)  BARBAT avoids the need to solve per-round convex optimization problems (as required by FTRL-based methods), making it computationally efficient.\n\n3) The introduction of BB-BARBAT constitutes the first theoretical analysis of batched bandits under adversarial corruptions, along with a corresponding lower bound. This fills a meaningful gap in the literature.\n\n4)  The experimental results across multiple settings consistently demonstrate that BARBAT-based methods outperform baseline algorithms. The results also show robustness to increasing corruption budgets, further supporting the theoretical claims.\n\n**Weaknesses**:\n\n1) The core BARBAT algorithm is closely related to DRAA [2], with the primary distinction being the use of epoch-varying failure probabilities. While this yields slightly improved regret bounds, this improvement is quite incremental.\n\n\n2) The multi-agent setting assumes instantaneous, reliable, and cost-free broadcasts. This assumption, while common in theory, limits the practical relevance of the results, especially since the authors claim their method to be highly parallelizable. There is no discussion of asynchronous or faulty communication scenarios, which are common in real-world systems.  Could the framework be extended to handle asynchronous message passing?\n\n3) While a lower bound is provided for batched bandits, no new lower bounds are given for other extensions (e.g., multi-agent or semi-bandits), making it unclear how tight the regret is in these settings.  Is it possible to derive lower bounds for these setting?\n\n[2] Fatemeh Ghaffari, Xuchuang Wang, Jinhang Zuo, and Mohammad Hajiesmaili. Multi-agent stochastic bandits robust to adversarial corruptions. arXiv preprint arXiv:2411.08167, 2024", "was_revised": true, "final_justification": "The authors responded appropriately to my questions and provided the requested lower bounds for the various settings.", "rebuttal": "Thank you for taking the time to review our paper. We hope that our response below addresses your concerns.\n\n>The core BARBAT algorithm is closely related to DRAA [2], with the primary distinction being the use of epoch-varying failure probabilities. While this yields slightly improved regret bounds, this improvement is quite incremental.\n\nWe do not agree that our regret improvement is quite incremental. Notice that in the MAB setting, the regret bound of DRAA is $O(C + K\\log^2(T)/\\Delta)$ while the regret bound of BARBAT is $O(C + \\sum_{\\Delta_k>0}\\log^2(T)/\\Delta_k)$. When the minimal gap $\\Delta$ is significantly smaller than other suboptimal gaps $\\Delta_k\\neq \\Delta$, our bound may substantially improves upon DRAA. For instance, consider the senario where mean rewards is $1, 1-\\Delta,0,\\dots,0$. Then DRAA incurs regret $C+K\\log^2(T)/\\Delta$, while our regret is only $C+(1/\\Delta + K)\\log^2(T)$. In particular, when $\\Delta \\leq 1/K$, the corruption-independent term in the regret bound of DRAA is effectively $K$ times that of BARBAT.\n\n>The multi-agent setting assumes instantaneous, reliable, and cost-free broadcasts. This assumption, while common in theory, limits the practical relevance of the results, especially since the authors claim their method to be highly parallelizable. There is no discussion of asynchronous or faulty communication scenarios, which are common in real-world systems. Could the framework be extended to handle asynchronous message passing?\n\nWe believe it is possible to extend our framework to an asynchronous setting, though it may encounter some challenges. Here is a rough outline of our approach: each agent independently executes the single-agent BARBAT algorithm, while incorporating an early-stopping mechanism. Specifically, an agent will enter the next epoch as soon as it has observed sufficient reward samples—either through its own pulls or those received from other agents—to reliably estimate the reward gaps. A key challenge in this approach is determining the optimal timing for broadcasting the agents' local information. Broadcasting too early may result in insufficient data collection, necessitating additional rounds of communication. Conversely, delaying broadcasts might lead to redundant pulls, preventing the agents from fully leveraging the benefits of collaboration. \n\n>While a lower bound is provided for batched bandits, no new lower bounds are given for other extensions (e.g., multi-agent or semi-bandits), making it unclear how tight the regret is in these settings. Is it possible to derive lower bounds for these setting?\n\nThank you for the valuable suggestions. The following table shows the lower bounds of all extensions. The lower bound for multi-armed bandits comes from Gupta et al. (2019), and their results can be directly extended to d-semi bandits, multi-agent bandits, and strongly observable graph bandits by incorporating the lower bounds for stochastic settings (without corruption). However, the lower bound for batch bandits cannot be directly derived from the results of Gupta et al. (2019), so we provide a proof in our paper. We will include all lower bounds in the revision.\n\n| Setting | Lower bounds | Our upper bound |\n|:-------:|:-------:|:-------:|\n| Multi-arm bandits | $C + \\sum_{\\Delta_k>0}\\frac{\\log(T)}{\\Delta_k}$ | $C + \\sum_{\\Delta_k>0}\\frac{\\log(T)^2}{\\Delta_k}$ |\n| Multi-agent multi-arm bandits bandits | $\\frac{C}{V} + \\sum_{\\Delta_k>0}\\frac{\\log(T)}{V\\Delta_k}$ | $\\frac{C}{V} + \\sum_{\\Delta_k>0}\\frac{\\log^2(T)}{V\\Delta_k}$ |\n| Batched bandits | $T^{\\frac{1}{\\mathcal{M}}}(K + C^{1 - \\frac{1}{\\mathcal{M}}})$ (this paper) | $C T^{\\frac{1}{M+3}} + T^{\\frac{4}{M+3}} ( \\sum_{\\Delta_k > 0} \\frac{M \\log(T)}{\\Delta_k})$ |\n| Strongly observable graph bandits | $C + \\sum_{k \\in \\mathcal{I}^*}\\frac{\\log(T)}{\\Delta_{k}}$ | $C + \\sum_{k \\in \\mathcal{I}^*}\\frac{\\log^2(T)}{\\Delta_{k}}$ |\n| $d$-set semi bandits | $dC + \\sum_{\\Delta_k > 0}\\frac{\\log(T)}{\\Delta_{k}}$ | $dC + \\sum_{\\Delta_k > 0}\\frac{\\log(T)}{\\Delta_{k}}$ |\n\n\nReferences:\n* Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562–1578. PMLR, 2019."}, {"review_id": "5R94qNxJgJ", "reviewer": "Reviewer_o47x", "summary": "This paper proposes BARBAT, an improved algorithmic framework for stochastic bandits robust to adversarial corruptions. Based on the BARBAR algorithm, BARBAT achieves a near-optimal regret bound of $O(C+ \\sum_{\\Delta_k>0} \\log T^2/\\Delta_k)$, removing the suboptimal $O(KC)$ term. The paper also extends BARBAT to settings including multi-agent, graph-structured, semi-bandits, and batched bandits, which is a naturally generalization for successive elimination algorithms.", "questions": "See weaknesses", "limitations": "See weaknesses", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\nThis paper is well-written and easy to follow, with clear and precise technical discussions. It extends the core framework to a wide range of bandit settings and is supported by extensive numerical experiments. The breadth of the work reflects a commendable level of effort and thoroughness by the authors.\n\nWeaknesses:\nThe proposed BARBAT algorithm appears structurally similar to BARBAR, with the main change being in the change of epoch lengths. If achieving the improved regret bounds requires nontrivial technical innovations beyond modifying this aspect, I encourage the authors to highlight and clarify them. One of the primary advantages claimed is BARBAT's scalability and parallelizability, which are indeed important. However, these properties are common to many elimination-based methods, and it is unclear whether they stem from novel design choices in BARBAT. If direct generalization is not sufficient for the multiple settings considered, it would be helpful for the authors to elaborate on the challenges involved and the innovations introduced. Overall, while the work is executed with care, its contributions feel somewhat incremental.", "was_revised": true, "final_justification": "The authors have provided detailed response to my concerns. While the paper is well-presented and the problem is interesting, their theoretical contribution is not very exciting. Therefore, after consideration, I am maintaining my score of 4.", "rebuttal": "Thanks for your detailed review of our work. Here are our response to your comments.\n\n>The proposed BARBAT algorithm appears structurally similar to BARBAR, with the main change being in the change of epoch lengths. If achieving the improved regret bounds requires nontrivial technical innovations beyond modifying this aspect, I encourage the authors to highlight and clarify them.\n\nUnlike BARBAR, which sets the epoch length to $ N_m = \\sum_{k} n_k^m $, our BARBAT algorithm defines the epoch length as $ N_m \\approx O(K 2^{2(m-1)}) $, making it unaffected by the adversary. However, this change introduces challenges in algorithm design and regret analysis since we have $ N_m > \\sum_{k} n_k^m $ and require addtional pulling of arms. To address this issue, we increase the probability of selecting the estimated best arm $k_m$. However, pulling the estimated optimal arm $k_m$ too many times may lead to additional regret, as $k_m$ could be suboptimal. To mitigate this potential regret, we adopt epoch-varying failure probabilities $ \\delta_m \\approx O(1/(mK2^{2m})) $ and demonstrate that such additional regret will only manifest in the first $ O(\\log(1/\\Delta))$ epochs, thus remaining bounded by a term independent of $T$. Overall, the additional pulls of the estimated best arm in our algorithm, along with the corresponding regret analysis, represent a novel and nontrivial contribution.\n\n>One of the primary advantages claimed is BARBAT's scalability and parallelizability, which are indeed important. However, these properties are common to many elimination-based methods, and it is unclear whether they stem from novel design choices in BARBAT. If direct generalization is not sufficient for the multiple settings considered, it would be helpful for the authors to elaborate on the challenges involved and the innovations introduced.\n\nDirect generalization of existing approaches is not sufficient for the extensions. Our algorithmic adjustments for each extension are thoughtfully designed to address the specific challenges while maintaining the core advantages of the framework:\n* In strongly observable graph bandits, the main challenge is how to leverage the graph-structured feed-back to reduce the regret suffered from exploration. We introduce the novel OODS algorithm (in Appendix A) for action-probability allocation. Specifically, we iteratively compute a minimum dominating set on the communication graph $G$, assigning pulling probabilities accordingly. Once an arm accumulates sufficient observations, we remove it from the graph and recalculate the dominating set. This process repeats until the graph is empty.\n* In batched bandits, the main challenge here is that the agent can only observe rewards after each batch is completed (instead of after each pull) and the number of batches is limited. To address this, we introduce a batch-related parameter $a = \\max\\\\{T^{\\frac{1}{2(\\mathcal{M} + 1)}}, 2\\\\}$, where $\\mathcal{M}$ is the number of batches. This parameter $a$ is used to design the exploration parameter $\\lambda_m$, the epoch length $N_m$, and the estimated gap $\\Delta_k^m$ in our algorithm for batched bandits.\n* In the $d$-set semi-bandit setting, the primary challenge lies in identifying an optimal action composed of $d$ arms, rather than merely a single optimal arm. To address this, we introduce a novel approach: when computing the epoch threshold $r_*^m$, we specifically consider the $d$-th largest empirical reward among arms. This innovation intuitively captures that each arm within the optimal action set can be regarded as an \"optimal arm,\" ensuring effective identification of the optimal $d$-arm combination.\n* For the multi-agent setting, we agree that many elimination-based methods also have parallelizability, but our method achieves state-of-the-art regret bounds."}, {"review_id": "8mSwc8Tnff", "reviewer": "Reviewer_qGGC", "summary": "The paper focused on the stochastic bandits under the adversarial corruption problem. Based on the limitations of the previous BARBAR algorithm, the authors proposed a new framework called BARBAT based on the elimination idea. Based on the framework, they can get a better regret bound. They also showed the framework on different specific bandit settings, such as multi-agent bandits, graph bandits,\ncombinatorial semi-bandits and batched bandits, and provided both theoretical and experimental results for these settings.", "questions": "1. You provided a lower bound in section 4.2 but how about other settings? Is it possible to provide a lower bound for other settings? \n2. From Table 1, the results seem to be a little outperforming previous work. For example, for d-set semmi-bandits, your result is worse than others on the order of $\\log T$. Please discuss it.\n3. You mentioned the different definition of regret: $R(T)$ and $\\tilde{R}(T)$. In the whole paper, you work on $R(T)$, not $\\tilde{R}(T)$. Please discuss the motivation for choosing the definition.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\nThe paper improved the previous regret bound for the problem and provided both solid theoretical results and interesting experimental results.\n\nWeaknesses:\nThe main concern is the novelty of the algorithm since it is based on BARBAR.", "was_revised": true, "final_justification": "I appreciate that the authors provided detailed answers in their response. Especially the lower-bound summary for different settings. My concerns are solved.  Their algorithm is based on the previous method, but they still have solid theoretical results and interesting experimental results. Thus, I would like to keep my score.", "rebuttal": "Thank you for your time and helpful suggestions. We address the reviewer’s concerns as follows.\n\n>The main concern is the novelty of the algorithm since it is based on BARBAR.\n\nThough our method is based on BARBAR, we want to emphsize the novelty of our BARBAT algorithm.\nUnlike BARBAR, which sets the epoch length to $N_m = \\sum_{k} n_k^m$, our BARBAT algorithm defines the epoch length as $ N_m \\approx O(K 2^{2(m-1)}) $, making it unaffected by the adversary. However, this change introduces challenges in algorithm design and regret analysis since we have $ N_m > \\sum_{k} n_k^m $  and require addtional pulling of arms. To address this issue, we increase the probability of selecting the estimated best arm $k_m$. However, pulling the estimated optimal arm $k_m$ too many times may lead to additional regret, as $k_m$ could be suboptimal. To mitigate this potential regret, we adopt epoch-varying failure probabilities $ \\delta_m \\approx O(1/(mK2^{2m})) $ and demonstrate that such additional regret will only manifest in the first $ O(\\log(1/\\Delta))$ epochs, thus remaining bounded by a term independent of $T$. Overall, the additional pulls of the estimated best arm in our algorithm, along with the corresponding regret analysis, is  novel and nontrivial. By utilizing these techniques, our algorithms achieve better regret bounds than that of BARBAR.\n\n>You provided a lower bound in section 4.2 but how about other settings? Is it possible to provide a lower bound for other settings?\n\nThank you for the valuable suggestions. The following table shows the lower bounds of all extensions. The lower bound for multi-armed bandits comes from Gupta et al. (2019), and their results can be directly extended to d-semi bandits, multi-agent bandits, and strongly observable graph bandits by incorporating the lower bounds for stochastic settings (without corruption). However, the lower bound for batch bandits cannot be directly derived from the results of Gupta et al. (2019), so we provide a proof in our paper. We will include all lower bounds in the revision.\n\n| Setting | Lower bounds | Our upper bound |\n|:-------:|:-------:|:-------:|\n| Multi-arm bandits | $C + \\sum_{\\Delta_k>0}\\frac{\\log(T)}{\\Delta_k}$ | $C + \\sum_{\\Delta_k>0}\\frac{\\log(T)^2}{\\Delta_k}$ |\n| Multi-agent multi-arm bandits bandits | $\\frac{C}{V} + \\sum_{\\Delta_k>0}\\frac{\\log(T)}{V\\Delta_k}$ | $\\frac{C}{V} + \\sum_{\\Delta_k>0}\\frac{\\log^2(T)}{V\\Delta_k}$ |\n| Batched bandits | $T^{\\frac{1}{\\mathcal{M}}}(K + C^{1 - \\frac{1}{\\mathcal{M}}})$ (this paper) | $C T^{\\frac{1}{M+3}} + T^{\\frac{4}{M+3}} ( \\sum_{\\Delta_k > 0} \\frac{M \\log(T)}{\\Delta_k})$ |\n| Strongly observable graph bandits | $C + \\sum_{k \\in \\mathcal{I}^*}\\frac{\\log(T)}{\\Delta_{k}}$ | $C + \\sum_{k \\in \\mathcal{I}^*}\\frac{\\log^2(T)}{\\Delta_{k}}$ |\n| $d$-set semi bandits | $dC + \\sum_{\\Delta_k > 0}\\frac{\\log(T)}{\\Delta_{k}}$ | $dC + \\sum_{\\Delta_k > 0}\\frac{\\log(T)}{\\Delta_{k}}$ |\n\n\n\n>From Table 1, the results seem to be a little outperforming previous work. For example, for $d$-set semmi-bandits, your result is worse than others on the order of  $\\log(T)$. Please discuss it.\n\n* The optimal regret bound for semi-bandits is achieved using the FTRL framework (Tsuchiya et al., 2023). In Section 7 of their paper, Tsuchiya et al. note that one limitation of their algorithm is its computational complexity, as the sampling probabilities cannot be efficiently computed. In contrast, our approach is computationally efficient, although the regret is slightly worse than state-of-the-art results.\n\n* For the multi-agent setting, our regret improvement is also non-incremental. Notice that the regret bound of DRAA is $O(C/V + K\\log^2(T)/(V\\Delta))$ while the regret bound of BARBAT is $O(C/V + (1/V)\\sum_{\\Delta_k>0}\\log^2(T)/\\Delta_k)$. When the minimal gap $\\Delta$ is significantly smaller than other suboptimal gaps $\\Delta_k\\neq \\Delta$, our bound may substantially improves upon DRAA. For instance, consider the senario where mean rewards is $1, 1-\\Delta,0,\\dots,0$. Then DRAA incurs regret $C/V+K\\log^2(T)/(V\\Delta)$, while our regret is only $C/V+(1/V)(1/\\Delta + K)\\log^2(T)$. In particular, when $\\Delta \\leq 1/K$, the corruporion-independent term in the regret bound of DRAA is effectively $K$ times that of BARBAT.\n\n* For the batched bandits, our work is the first to study batched bandits with adversarial corruptions and achieve near-optimal regret bounds.\n\n>You mentioned the different definition of regret: $R(T)$ and $\\tilde R(T)$. In the whole paper, you work on $R(T)$, not $\\tilde R(T)$. Please discuss the motivation for choosing the definition.\n\n$R(T) = T\\mu_{k^*} - \\mathbf{E}[\\sum_{t=1}^T \\mu_{k_t}]$ is a standard regret defnition in stochastic bandits, while the regret definition $\\tilde R(T) = \\max_{k \\in [K]}\\mathbf{E}[\\sum_{t=1}^T \\tilde r_{t,k} - \\sum_{t=1}^T \\tilde r_{t,I_t}]$ is typically used in adversarial bandits, where $\\tilde r_{k}$ represents the corrupted rewards. We think that comparing against the true means, rather than the corrupted rewards, is more natural. Also, $R(T)$ has been employed in all previous works on adversarial corruptions.\n\nReferences:\n* Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562–1578. PMLR, 2019.\n* Taira Tsuchiya, Shinji Ito, and Junya Honda. Further adaptive best-of-both-worlds algorithm for combinatorial semi-bandits. In International Conference on Artificial Intelligence and Statistics, pages 8117–8144. PMLR, 2023."}]

Author rebuttal:

Meta-review: (a) Summary: This work proposed BARBAT, an improved algorithmic framework for stochastic bandits robust to adversarial corruptions. Based on the BARBAR algorithm, BARBAT achieves a near-optimal regret bound of $O(C+\sum_{\Delta_k>0}\log T^2/\Delta_k )$, which removes the suboptimal $O(KC)$ term. The work also extended BARBAT to settings including multi-agent, graph-structured, semi-bandits, and batched bandits, which is a naturally generalization for successive elimination algorithms.

(b) Main reasons for decision/Pros: The work proposed BARBAT, which improved the popular BARBAR algorithm and clarified its contribution.

(c) Change during rebuttal: A comparison among theoretical lower bounds and upper bounds is provided in the reply to reviewer dQYX.

(d) Decision: I vote for accept at the moment but I am not certain about that.
- Two reviewers suggested that the technical challenge is a bit incremental and voted for 4, while the remaining reviewer (reviewer dQYX) voted for 5 but pointed out that he/she is not an expert in the topic of bandits with corruption.
Decision: Accept (poster)