Locally Private and Robust Multi-Armed Bandits
Authors: Xingyu Zhou
WEI ZHANG
Venue: NeurIPS 2024 poster (2024)
Keywords: Local Differential Privacy
Robustness
Huber Corruption
Multi-Armed Bandits
Primary area: bandits
TL;DR: We show an interesting interplay between local differential privacy and Huber contamination in MABs.

Abstract: We study the interplay between local differential privacy (LDP) and robustness to Huber corruption and possibly heavy-tailed rewards in the context of multi-armed bandits (MABs). We consider two different practical settings: LDP-then-Corruption (LTC) where each user's locally private response might be further corrupted during the data collection process, and Corruption-then-LDP (CTL) where each user's raw data may be corrupted such that the LDP mechanism will only be applied to the corrupted data. To start with, we present the first tight characterization of the mean estimation error in high probability under both LTC and CTL settings. Leveraging this new result, we then present an almost tight characterization (up to log factor) of the minimax regret in online MABs and sub-optimality in offline MABs under both LTC and CTL settings, respectively. Our theoretical results in both settings are also corroborated by a set of systematic simulations. One key message in this paper is that LTC is a more difficult setting that leads to a worse performance guarantee compared to the CTL setting (in the minimax sense). Our sharp understanding of LTC and CTL also naturally allows us to give the first tight performance bounds for the most practical setting where corruption could happen both before and after the LDP mechanism. 
As an important by-product, we also give the first correct and tight regret bound for locally private and heavy-tailed online MABs, i.e., without Huber corruption, by identifying a fundamental flaw in the state-of-the-art.

Locally Private and Robust Multi-Armed Bandits
Xingyu Zhou Wayne State University Langyu.zhou@war edu
Wei Zhang Texas A&M University komo@tamu edu
Abstract
We study the interplay between local differential privacy (LDP) and robustness Huber corruption and possibly heavy-tailed rewards the context of multi- armed bandits (MABs). We consider two different practical settings: LDP-then- Corruption (LTC) where each user's locally private response might be further corrupted during the data collection process, and Corruption-then-LDD where each user's raw data may be corrupted such that the LDP mechanism will only be applied to the corrupted data. To start with, we present the first tight characterization of the mean estimation error in high probability under both LTC and CTL settings. Leveraging this new result, characterization (up to log factor) of the minimax regret in online MABs and sub-optimality in offline MABs under both LTC and CTL settings, respectively. Our theoretical results both settings are also corroborated by a set of systematic simulations. One key message in this paper is that LTC is more difficult setting that leads to worse performance guarantee compared to the CTL setting (in the minimax sense). Our sharp understanding of LTC and CTL also naturally allows us to give the first tight performance bounds for the most practical setting where corruption could happen both before and after the LDP mechanism. As an important by by-product, we also give the first correct and tight regret bound for locally private and heavy-tailed online MABs, i.c., without Huber corruption, by identifying fundamental flaw in the tate-offtthe-art
(CTL)
then present almost tight
Introduction
The Multi-Armer Bandit (MAB) problem (Berry & Fristedt, 1985) offers fundamental approach for sequential -aaiiinnnmmainnggg under uncertainty based on only bandit feedback. Take online advertising as illustrative example, where the advertising platform (i.e., the central learner) sequentially and adaptively displays ads (i.e., arm) based on users' reward feedback (e.g., engagement score) so as to maximize the cumulative rewards. In practice, several important factors have to be considered when designing world MAB algorithms, as illustrated below using online advertising.
Privacy. The raw engagement score (which is calculated based on clicks, purchases, and time spent viewing the ad, etc.) from user's device may lead to privacy leakage. For instance, when the ad is about medicine on some rare or uncommon disease, a high engagement score might imply interest or association with the uncommon disease. Such privacy leakage may lead to unintended personal and social consequences as well as trust issues the platform. One principled way to mitigate it is via local differential privacy (LDP) (Kasiviswanathan al., 2011; I; Duchi et al., 2018), i.e., each user's device locally adds suitable amount of noise (depending on the privacy mechanism and budget) to obfuscate the raw feedback before sending it out from the device (see the yellow region in Fig. 1).
Robustness. Another important factor in real-world scenarios is the robustness of MAB algorithms under both possibly heavy-tailed feedback and adversary corruption.
Work done during research intern Wayne State University
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Possibly heavy-talled data
Possibly heavy-tailed data
Possibly heavy-tailed data
- Y-- 11 Z
- Y- -
+
Y
-Z
(1) LDDP-then-Corrupion (LTC) (2) Coruption-then-LDDPP -eae--tteee----CITI-I (CTL)
C-LD-C
Figure The interplay between privacy and robustness (heavy-tailed data and corruption).
Heavy-tailed feedback. The engagement score in our example could often be heavy-tailed, i.e., non-negligible probabilities of observing extremely high values. This might happen due to some special events and seasons (e.g.. Black Friday) or influencer interaction.
Adversary corruption. There could be malicious attacks on the engagement scores during the collection of users' feedback, e.g., with some probability, each score could be replaced by any arbitrary value, i.e., Huber corruption (Huber, 1964). On the other hand, corruption can also happen on each user's side before transmission, e-g.. one could manipulate or spoof interactions to skew scores. Most practically, corruption can also happen both before and after the data transmission.
To tackle the above privacy and robustness issues in MABs, there has been a large related literature, which, however, mainly investigates the two issues in an isolated way (see Appendix B for details). Motivated by this, in this work, we are particularly interested in the following question:
Is there any interesting interplay between privacy and robustmess in MABs?
Our contributions. We give affirmative answer to the above question by unveiling a fundamental interplay between privacy protection (in particular, local differential privacy (LDP)) and robustness under Huber corruption and heavy-tailedness. Our main message is a separation result between two MAB settings that differ in the order of privacy protection and corruption, i.e., LDP-then- corruption (LTC) vs. corruption-then-LDee (CTL). That is, under LTC, corruption happens after LDP mechanism while under CTL,, corruption happens before the LDP mechanism (see Fig. 1). To obtain our separation result for the two settings, we take the following principled approach:
We first study the mean estimation problem - a cornerstone step in the analysis of stochastic MABs under both LTC and CTL settings. We give the first tight characterization of the estimation error Specifically,
in high probability, in terms of privacy budget, corruption level. and heavy-tailednest we first establish lower bounds on the minimax error rate in high probability and then propose unified optimal algorithm that achieves matching worst-case upper bounds for both settings. The key observation here is that the mean estimation error under LTC is larger than that under CTL and moreover the gap becomes larger as the privacy requirement becomes stronger. Further, our sharp results LTC and CTL also naturally enable to give tight performance bounds for the most practical setting, C-LDP-C, where corruption happens both before and after LDP, see (3) in Fig. 1.
2. Leveraging the above tight mean estimation results, we then study both online MABs and offline MABs under both LTC and CTL. We present an almost tight characterization (up to log factor) of the corresponding minimax performances (i.c., regret in online MABs and sub-optimality in offline MABs) by deriving lower bounds and proposing almost optimal algorithms. As in mean estimation, there is a separation between LTC and CTL, i.e., LTC is more difficult setting that leads to worse performance in the minimax sense, highlighting the interesting interplay between privacy and robustness in MABs. All of these results also allow to easily handle the C-LDP-C C setting.
3. Along the way, several results could be of independent interest. First, our optimal locally private and robust mean estimators can be applied to many other applications beyond MABs. Moreover, as an important by-product, we identify a fundamental flaw the regret upper bound of state-of-the-art locally private online MABs with heavy tails (i.e., without corruption), and give the first correct one.
Related Work. We discuss the most relevant related work in the main body and relegate a detailed discussion to Appendix B. LDP with Gounded/sub-Gaausiee reward is first introduced to MABs in Ren et al. (2020) and later was generalized the heavy-tailed rewards (Tao et al., 2022). Robust MABs under Huber corruption have been recently studied in Kapoor et al. (2019); Mukherjee et al. (2021); Basu et al. (2022); Agrawal et al. (2023) while robust MABs concerning heavy-tailed reward date back to Bubeck et al. (2013). However, these work only study privacy and robustness separately. To the best of our knowledge, there are only two very recent work that consider privacy and robustness in MABs simultaneously. In Wu et al. (2023), the authors consider the central DP model where the raw non-private feedback received by the central learner can be first corrupted under Huber model. This is in sharp contrast to our local DP model, which is not only stronger but allows to study

---

the order of corruption and privacy. In Charisopoulos et al. (2023), the authors study linear bandits (which includes MAB special case) under LDP and then Huber corruption (i.e., LTC setting). As will be discussed in Section 4, their regret bound is sub-optimal and worse than ours when reduced to the MAB case. Note that we also study the CTL setting, which in turn allows us to study the most practical setting C-LDP-C. Finally, our work is inspired by recent advances in (locally) private and robust mean estimation (Li et al., 2022b; Cheu et al., 2021; Chhor Sentenac, 2023). Our key contributions are the first high-probaability concentration bounds for both CTL and LTC settings.
2 Problem Setup
In this section, we formally introduce the three problems considered in this paper: mean estimation, online and offline MABs, under the constraints of both LDP and robustness (including heavy tails and Huber corruption). To start with, we introduce the privacy and corruption models.
Definition 1 (s-LDP, Duchi al. (2018)). For a privacy parameter [0. 1]. the random variable X an E-locally differentially private view of via privacy channel/mechanismm Q
O(EESJ X S Q(X E E X x-x <
sup
where (λ²) denotes an appropriate o-field on X. In this case, we also say that the conditional distribution (privacy channel) Q is an e-LDP privacy mechanism. We write 2g the set of all s-LDP mechanisms (channels).
Definition (a-Huber corruption, Huber (1964)). Given parameter [0, 1/2) and distribution D on inliers, the output distribution under a-Huber model is O = (1 - a) + a. That is, a sample from O returns sample from with probability 1 a and otherwise returns a sample from some (unconstrained and unknown) corruption distribution F. We write C, (D) as the set of all possible a-Huber corruptions (channels) of inlier distribution D.
With the two definitions in hand, we can introduce the two main settings in this paper: (i) LDP-then- Corruption (LTC) vs. (ii) Corruption- then-LDP (CTL), as also illustrated in Fig.
Definition 3 (LTC vs. CTL).. We consider the following interplay between privacy and corruption.
(i) LDD--thenCoorrpttio (LTC): Each user E [n]] first generates an s-LDP view of raw data X;- Then, the private data Y, from each device is independently corrupted by an a-Huber channel that outputs Z; to the central analyzer/agent.
(ii) Corruption-then-LDD
(CTL): Each user's 's raw data X; is first independently corrupted by an o-Huber model. Then, the corrupted data Y, passes through an e-LDP mechanism at each device that outputs Zi to the central analyzer/agent.
Under both settings, we aim to design e-LDP mechanisms for user devices and central analyzers that ensure local privacy and robustness against o-Huber corruption and heavy-tailed data distributions. The two settings also naturally enable us to study the most practical setting C-L.DP-C.
Mean estimation. As in Duchi et al. (2018), given real number k > 1, we consider the following class of possibly heavy-tailed distributions
Pk (distributions P such that Ex-P [-1, 1] and Ex-pl[X|*] < 1).
(I)
That is, & controls the tail behavior of the distribution with smaller k meaning heavier of the tails. Given any distribution P E Ps, our goal is estimate its mean ((P) as accurately as possible. In contrast to the standard case where the analyzer has access to i.i.d samples (X,) from P. the analyzer in this paper now only observes samples {Z, )= that are both private and corrupted view of {X.) Specifically, we are interested in the high probability error under our two different settings (LTC vs. CTL), as formally defined below.
Definition& 4 (Minimax mean estimation error rate). Given 8 > 0 and sample size 0. the minimax mean estimation error rate of the class Pa under s-LDP and a-Huber corruption is defined as follows
$3 o5 &, n): n):==ii(fe inf 0 inf inf sup sup
P [ x(P) o) s 5)
(2)
QEQ, P. PEP. (P)
3

---

where Tn is measurable function of {2 i.c., private and corrupted view of n i.i.d samples {Xi] from P E Pk that pass through E-LDP channel Q and a-Huber corruption channel C. We e, az n) and $2, e a,n) n) for the settings of LTC and CTL. write (k,
Intuitively speaking, og represents the minimal error rate that any s-LDP estimator can achieve with high probability - o for all distributions P E Pa and all o-Huber corruption models, hence taking inf over Q and fr, and sup over distribution and corruption. Thus, the goal in our mean estimation problem is to design an optimal E-LDP mechanism Q' at each user's side and an optimal analyzer Ar at the central analyzer in order to attain the minimax mean estimate error rate in (2).
Online MABs. At each round & E [7]. the central learner/analyzer chooses an action/arm de E [K] according a policy я and receives reward sample X, that is drawn from some distribution Pa. with unknown mean r(az) == p(Pa.). Here, the policy is т { J and T++1 is a measurable
function of the data received by the end of round t, i.e. for each f E [T]. D. = {(a, (() (t))
where X ( (4) == (x(m) "x.""...,""""" _()) (.) and Eeek Na(() = L. That is, for each round 4, (1)
groups together all (t) rewards from each arm E [K] where (t) is the total number of times that arm a has been pulled by time t. The goal in online MABs is to characterize the minimax clean regret under our LTC and CTL settings defined below.
Definition 5 (Minimax clean regret), Let MAB(k) == {[Pa)aek Pa E Pk] be the class of K Kaarmed MAB instances with inlier distributions for each arm in Pk. Then, the minimax clean regret defined as
T sup E T r(a") - - Er(a)) QEQ. JEMAB(R)
RC (k, = inf inf sup
(3)
[
where d is measurable function (via T) of private and corrupted dataset {(u, (())
[[[[]]-
is the private and corrupted view of Na (f) samples of Pa that pass through s-LDP channel Q and a-Huber corruption channel C. We write (k, S, at ?") and Ren e, a, T)) for the settings of LTC and CTL, respectively.
Here, for any arm E [K] and t E [7], 2( (t) = (Z(-)) " (o)
The goal in online MABs is to design an optimal E-LDP mechanism Q* and optimal learning policy nt so as to attain the minimax clean regret in (3). Remark 1. As standard in the literature (Wu al., 2023; Chen al., 2022: Niss & Tewari, 2020), r(.) in (3) is the mean of inlier distributions while the randomness in the expectation is generated by both privacy and corruption.
Offline MABs. In the offline case, the analyzer cannot interact with users and instead, it is given batch pre-collected dataset D = {(a, X,) sampled from some joint distribution of behavior policy and reward distributions {Pa ]aE[K] As in Rashidinejad et al. (2021), we assume a finite concentrability coefficient 8 such that 1/x(a*) S B*, where a* is the optimal arm that has the largest mean and 3 captures deviation between the behavior distribution ı and the distribution induced by the optimal policy. The goal here is to characterize the minimax sub-optimality under our LTC and CTL settings defined below.
Definition 6 (Minimax sub- sub-optimality). Let
MAB(3*, k-) == {(T,, (Pa)aek) E Pae and and 1/m(a') S 533
be the class of K-armed MAB instances with distributions in Pa and concentrability coefficient B*. Then, the minimax sub-optimality is defined as SubOpt* (8",,,,,,, k,,,,, N) = inf inf sup sup E [Ir((a)) - rr()]]. rEMAB(S CEC.(1)
(4)
qEQ. à
where à is a measurable function of private and corrupted dataset {(a, z())) and Z(() {Z(0) ..... N.. is the private and corrupted view of N, samples of P. that pass through s- LDP channel Q and HuHuber corruption channel C. We write (,,,tirree",,,,,,,,,,, and SubOptCn. (5* k e, a, N) for LTC and CTL, respectively.
We remark that we assume the batch data is collected by an e-LDP mechanism that can be specified by the learner. Note that as in the standard case, we do not control the behavior policy other than finite S* The goal here is to design an optimal E-LDP mechanism Q' (which protects local privacy for any users offering batch data) and optimal offline learning algorithm ă".

---

3
Mean Estimation
We start with our first problem mean estimation under privacy and robustness constraints. Our main result in this section is the following theorem that characterizes the minimax error rate (cf. Def. 4) Theorem (Mean Estimation). Given any fixed E (0, (0,1/2),, = E [0, 4), a e 1/2) and ls > 1,
have that for all large enough n,
1-1/k
1 1-1/k
(16(1/6)
+
n
1-1/8
1 (1/5) a a/-1/k +
ICTTLL (M,,,,)
Remark 2. To the best of our knowledge, this is the first high- high-probability concentration bound for mean estimation under both LTC and CTL, which tightly captures the dependence on the corruption level a, privacy budget and heavy-tail parameter k, simultaneously. It can be seen that for LTC setting, there is an additional (1/e)1-1/k factor, which implies that introducing LDP guarantee first would make it more vulnerable to corruption/data manipulation attacks. Interestingly, for a fixed e, this additional vulnerability due to LDP decreases the tail becomes heavier, which offers additional insight into the interplay of privacy, heavy-tailedness, and robustness. Our LTC result also complements the result in Cheu et al. (2021), which considers the bounded case (i.e., k = oc) under constant probability only rather than our high probability guarantee. On the other hand, for CTL, we note that the impact of corruption and privacy is separable. Our high probability bound for CTL complements the error bound in terms of mean mean-square square error (MSE) only in Li et al. (2022b).
To establish Theorem I, we first establish the following lower bounds, with full proof in Appendix E.
Proposition 1 (Lower Bounds). Given any fixed ō 1/21, & [0, E [0, 1/2), k > 1 and large enough, for all e-LDP mechanism Q and all estimator P.e there exists distribution P E Pk and a-Huber corruption channel C (P) such that with probability least
(i) For LTC: Pin (M(P)
(g) 1-1k +
log(1/5) 1-10 )1
(ii) For CTL: [Am M(P)) 2 Ω
a 1/1k +
(22 log(1/6)
1-16
where recall that Tha is a measurable function of {Z i.e,, private and corrupted view of i.i.d samples {X4 ) from P E Pv obtained from E-LDP channel Q and o-Huber corruption channel C.
Proof sketch. We provide summary of the key steps in the proof. Essentially, we divide the proof into two parts. First, we consider the case without corruption and aim to establish the second term in the bound. To this end, we will leverage tools from information theory in an novel way, e.g., maximal coupling, strong data processing inequality of LDP, and Bretagnolle-FHube inequality between TV and KL distance. Then, we turn give the first term related to corruption. To this end, we will leverage a folklore but important fact about Huber model. Roughly speaking, this fact says that given two inlier distributions D2 and D2 that satisfy TV (D1, D2) < O(a). then after a-Huber channel, one cannot distinguish between Dj and D2- Another important fact is that E-LDP channel is "contraction" channel in terms of TV distance, i.c., TV (M1, M2) s O())TV (P1, P2) where M1. M2 are induced marginals of Pı, Pa after any c-LDP channel.
Key intuition behind the separation between LTC and CTL. Building upon the above proof, one can immediately see that under the LTC setting, due to the "contraction" of LDP, one can choose two distributions that have larger mean difference by factor of 1/s, while still guaranteeing that after a a-Huber corruption, they are indistinguishable, hence explaining the key difference of 1/s between LTC and CTI. We also provide another understanding of the separation from the attack perspective (see more details in Appendix A). The key idea here is that each single data attack in the LTC setting will lead to an additional 1/e factor compared to CTL setting. This is mainly because any c-LDP mechanism binary data can be simulated by random response mechanism (Kairouz et al., 2015).
We assume ô does depends n2; otherwise, E (8min, 1/2) where òmin - for some 0.
5

---

We now turn to upper bounds, centering around the following key question: Can we design simple al- gorithm that can achieve optimal errors for all LTC, CTL, and even C-LDP-C in a unified way? We give an affirmative answer via Algorithm 1. It consists of a local randomizer at each user's side and an analyzer at the central side. The task of Q is to guarantee that its output is an S-LDP view of its input. To this end, for each input Us it first truncates it into U, using a properly chosen threshold M. Then, it converts the real number to binary data via random rounding. Next, it applies random response technique to gen- crate the final output Ü, i.c., with probability Tf outputs a number of the same sign (with additional scaling for unbiasedness); otherwise flips the sign. Upon receiving the final input {Z:);=1- the analyzer A first simply filters out the data if out of the bounded range and then returns the sample mean.
Algorithm 1 A Unified Algorithm
1: Procedure: E-LDP mechanism Q
//Input: Us, parameters: M, E
3: / //Output: private view U;
4: Truncate: U, = (;I(IU:] - M)
5: Random rounding:
- M w-p. 1+0./M
-M w.p. 1- C
2
6: Random response:
UK!
w.p. e²
U
UK
W.P. ot
7: Return Ug Procedure: Analyzer A 9: / //Input: (7. H=11
parameters: M,
For LTC and CTL, the only difference in Algorithm I would be the truncation value M. The performance bounds for both settings under Algorithm are given below. See Appendix F for proof.
10: / //Output: estimator Jh,
11: Return An = 2 ( s M
e'+1)
Propusition 2 (Upper Bounds). Given any fixed ö E (0, 1). = [0, 1], a E 10, and k > 1, for any distribution P E Px and any o-Huber channel C E Ca. Algorithm 1 satisfies that the mechanism Q is e-LDP and each returned estimate Tn guarantees that with probability at least 1 5
(i) For LTC: 1in - -p()) 0
(0)
(
+ (1
log(1/5)
1- 1/8
1- 1/8
(ii) For CTL: 1mn p(P) S 0
aa-1//k
log(1/8) n
1/K
where (i) holds for ==min
($)
1/k
Ev
and all n 3log(1/8)/a, if
0:
(1gg(1/8)
1/k ((ii) holds for M min (t)
1//
1/k
otherwise for all and M
evn (vig(1188)
eVT
Vlog(1/8)
1/k
and n 2 3ogg(1/8)// if > 0; otherwise for 2 1og(1/8) and M
cvvn
(lo((1/6)
Corraptio-LDP--orrptii (C-LDP-C), Our tight characterization of LTC and CTL immediately helps us understand the C-LDP-C setting, where corruption happens both before and after LDP. In particular, it is easy to see that the minimax lower bound for LTC would be a valid lower bound for the more difficult C-LDP-C setting. It turns out that this lower bound is also tight since it is matched by Algorithm with the same parameter choice M as in the LTC setting, see Appendix G.
How choose parameter M in practice. First, we note that for the bounded case (k = oo). M = 1 across all three settings, independent of other parameters. This implies that Algorithm I can adaptively guarantee optimal minimax rates for LTC, CTL, and C-LDP-C without prior knowledge of the specific setting and other parameter like a. Second, for certain applications, one may have prior knowledge of the underlying setting (see Appendix C.3). In this case, one can have a performance gain if it is under the CTL setting. Also, as mentioned above, we see that choosing the M as in LTC can automatically help to handle the C-LDP-C setting. Finally, the dependence on é in M fine since it is known privacy parameter while the dependence on the unknown parameter is a little bit annoying. A quick practical fix to use an estimated upper bound on a. theory, the story of whether one can remove in our case is complicated, see the discussion in Appendix C.2.

---

Remark 3 (Burn-in period). Under Algorithm 1, when a > 0, the concentration kicks in when the sample size n is larger than threshold. This type of burn-in period also exists in previous concentration results under the Huber model, though in different contexts (e.g., non-private case in Chen et al. (2022) or central model of DP in Wu et al. (2023)) or with different estimators (e.g.. trimmed mean in Mukherjee et al. (2021)).
Remark 4 (Random response vs. Laplace mechanism). One may wonder if the standard Laplace mechanism can be applied in replace of the random response for e-LDP Q. The answer depends on the setting and the analyzer A. For CTL, one can still derive a similar optimal concentration bound as in Proposition 2 by the concentration of Laplace noise. On the other hand, for LTC, simply replacing random response with Laplace mechanism in Q will lead to an additional log(1 /L)) factor. This aligns with the fact that truncation- based estimators even cannot achieve optimal mean estimation for Gaussians under corruption (Diakonikolas & Kane, 2023). The above discussion indicates another difference between LTC and CTL., i.e., the choice of E-LDP mechanisms.
As two interesting applications of our mean estimation results, we will study both online MABs and offline MABs in the next two sections, highlighting again the sharp differences between LTC and CTL settings, in terms of regret and sub-optimality performance, respectively.
Online MABs
For online MABs, our main result is the following theorem that gives an almost tight characterization (up to log factor) of its minimax clean regret (cf. Def. 5) for both LTC and CTL settings.
Theorem 2 (Online MABs). Given any e E [0, a [0, 1/2) and &. > 1, we have for all large enough? T,
8, o,, T. a
1-1/k
k+ T
K
26
+
26
E²
Ra, a, s,,
T T.
1-1k
T
k+1 2
K
Remark 5. For both settings, due to corruption, the minimax clean regret (i.e., gooblem-independen regret) has linear dependence on T, as in previous works under Huber corruption (Wu et al., 2023; Chen et al., 2022). The key here is to capture the tight factor in front of T, where the additional 1/E factor in LTC again demonstrates the sharp difference between the two settings as in the mean estimation problem. As before, one can obtain the same rate for C-LDP-C from the LTC setting.
To prove the above theorem, we start with the corresponding lower bounds (see App. H for proof). Proposition 3 (Regret Lower bounds). Let [0, 1], E [o, 1/2), k > 1 and T be large enough. Then, the minimax clean regrets satisfy the following results.
(i) LTC: Rino(k,e,,, 20
T (2)
2-2/
T
K
(ii) CTL: (k Ω T T. 1-/h +
E+1 24
24
Comparisons related work. We first remark that Tao al. (2022) studied a similar case but without corruption (i.e., = 0) and established a lower bound on the order of Ω ((5) 1-1/k T1/k)) (for k E (1,2) when adapted to our setting), which is weaker concerning T compared to our lower bound. In Tao al. (2022), the authors also claimed achieve their lower bound via some arm- elimination algorithm, which now becomes ungrounded given our tighter lower bound. That is, since for a large enough T. our lower bound even larger than their upper bound for fixed e, h and K (e.g., 3/4 vs. VT for k = 2, see further discussion in Appendix C.3). Another recent work Wu et al. (2023) also studies online MABs with both privacy and Huber corruption but under the weaker central model of DP. In particular, the true reward from each user may be first corrupted before being observed by the central learner, who is then responsible for taking care of privacy guarantees. That is, the central learner has access to users' raw (corrupted) data rather than only a private view of data as in our LDP case. Under this strictly weaker privacy model, Wu et al. (2023) establish the following
7

---

[VKTT + (K/E)' +Tal-k) Compared to our CTL setting, one can see that our stronger LDP privacy incurs larger privacy cost.
lower bound on the minimax clean regret: 92
Now, let turn to our proposed algorithm (i.e., Algorithm 2) for achieving matching regret up- per bounds (up to log factor). Algorithm 2 is variant of upper confidence bound (UCB)-based algorithm (cf. Auer et al. (2002)), which com- putes the UCB index for each arm at each round t [T] and then selects the one with the highest UCB, i.e., optimism in the face of uncertainty. To construct valid UCB, we resort to our mean estimation results in the last section. In par- compute
Algorithm 2 Online MABs under LTC and CTL
1: Input: private and robust mean estimator Th (k, 8, a; 5) in Algorithm 1, constant c 2: Initialize: For each E [K], Pa,a is the
estimate (k, at, (4 based on the first observed values of Zu......, Za of the re- wards for amm a;
3:
for E [T] do
4:
if 3a E [K], Na(() - 6log(()/a then
ticular, we will need Algorithm
5:
0t a
the private and robust sample mean (t)) (t) for each arm E [ at each round t, where (t) be the number of pulls of arm by the beginning of time I. Then, the bonus term (i.e.. radius of the confidence bound) (1) comes from the high probability mean estimation er- ror established in Proposition 2. Note that due to burn-in period of the concentration results,
6:
else
1-1/k
log(t") Let %a() = < Ne(t)
8:
{ c((g 1-1// + e%all)
(1))
8a(1)= { ca 1/h
LTC
11/h (1a
CTL
9:
Let (1) Pa. (1) (1) ( (1)+
Algorithm 2 has an additional exploration pe- riod to guarantee that the number of arm pulls 11:
10:
= argmax (C).
end if
larger than a threshold (line 4). The following 12: end for
proposition formally states the regret guarantees of Algorithm 2 with the proof given in Appendix I.
Proposition 4 (Regret Upper Bounds), Let E [0, E (0. k> and T be large enough. Then, for any 1/2 > ā 2 a, the expected clean regret of Algorithm 2 satisfies the following guarantees.
(i) LTC: RITo(K,E,, S T (T))) 1-1/k
+
K log
T 26
+
K log T
h-1
(ii) CTL: (k,,,kee T) 0 Tat-1/k
K log
T
k+1
K log a
Comparisons to related work. First, for a = O, our result with a direct modification of the burn-in
(( (KlogT) ((Ilogr)
period gives regret bound that only has the term O
2x
This is the first correct
regret bound for locally private heavy-tailed MABs, i.e., without corruption, fixing the aforementioned issue in the state-of-the-arr in Tao et al. (2022) (see more discussions in Appendix C.3). Second, it is worth comparing our result to recent similar result in Charisopoulos et al. (2023), where the authors present regret for linear bandits under LTC setting. Their result is worse than ours when reduced to MAB with bounded rewards, as the scaling with respect to a is /a in the first linear term rather than our a. Another minor difference is that our algorithm is anytime while their algorithm is not.
Other extensions. Although we mainly focus minimax regret (i.e., mooblem-indepence in this paper, under some conditions of corruption level and the minimum mean gap, Algorithm is also able to offer some problem-depended parameter a is very small but not equal to zero, one can tune the choice of ā (hence truncation threshold M) to balance the first and third terms in the bound. Similar comments and observations have been made in related work as in Chen et al. (2022); Wu et al. (2023).
bound)
bounds (see Appendix I). In the case that the corruption
5 Offline MABs
In this section, we study offline MABs as another application of our high probability mean estimation results developed in Section 3. We establish both lower bounds and almost matching upper bounds for locally private offline MABs with corruptions. To the best of our knowledge, this is the first result on offline MABs with heavy-tailed rewards, even without privacy and corruption.
8

---

Proposition 5 (Sub-optimality Lower Bounds). Let E 10, E [0. k: > 1 and N be large enough. Then, for 8 2 2, the minimax expected sub-optimality satisfies the following results.
1-1/k
LI),TC: SubOptiro ,,,,,,
(2)
1-1
+
9-
N
1- 1/k
(ii) CTL: ( o, N) 2 1-11/ +
);
N
Now, let us turn to our proposed algorithm, which able achieve matching expected sub-optimality (up to log factor) for both LTC and CTL settings. Our algorithm a simple variant of the classic Lower Confidence Bound (LCB)-based algorithm as in Rashidinejad et al. (2021), i.e. pessimism in the offline setting. The key difference compared to Rashidinejad et al. (2021) is our private and robust estima- tor (line 8) and penalty term (line 10), which come from high probability mean estima- tion error. Another modification due to our burn-in period of concentration result (line 4). Putting all of these together, Algorithm is able achieve the following guarantees on the ex- pected sub-optimality, which almost matches the lower bound in Proposition See the App. K and for proofs of the upper and lower bounds. Proposition 6 (Sub-optimality Upper Bounds). Let & E 10, a E (0. 1/2).
Algorithm 3 Offline MABs under L.C and CTL
1: Input: Offline data D {(a, Z (()) [aE[K] mean estimator P.n E, a, 6) in Algorithm 1, positive constant c
a,
2: Initialize: N₂ =
|Z(0]| for all a E [K], i.e.
number of pulls for arm in D
3:
for a E [K] do
4:
if Na < 3 log(1/6)/o then
5:
Set the empirical mean reward F(a) = 0
6:
Set the penalty b(a) =
7:
else
8:
F(a) puN. (ki, e, a,,))
1-1/k
9: Define
1 E N.
loK(2K/8)
c (c) 1-1/h my
for LTC
10:
b(a) =
ca /k + cy
for CTL
end if
> 1 and 5 = 1/N. Then, for all finite 8" 2 1 and large enough N and Na. 2 3 (ggg(/)//// the expected sub-optimality of Algorithm satisfies
12: end for
13: Return argmax F(a) b(a)
1-1/k) 2r (og(K(N)
(i) LTC:SubOptt wtwpaa/ppppppot....aaa.aaaae
(9) 10/1
1-1/K
(it) CTL: SubOpt (8", k,,,,,,,,
a--1/k
3+ JoR(KN)
For the case of a 0, as before one can simply choose to use the mean estimate result for a = 0 as shown in Proposition 2 and adjust the burn-in period accordingly. This will lead to a bound that only has the second term in the above upper bounds. For 3* 2 2. one can observe that the upper bound of Algorithm almost matches the lower bounds in Proposition for both LTC and CTL settings. However, when 8* E [1, (i.e., good coverage case), it is known that the performance of LCB is worse than imitation learning, i.e., simply returning the most frequently selected arm in the offline dataset (when there is privacy and corruption) (Rashidinejad et al., 2021).. We leave it to future work to give a tight characterization of the sub-optimality when 3 E (1,2). Moreover, the proof of Proposition 6 also naturally gives us high high-probability bounds without specifying d 1/N in the end.
6 Simulations
Beyond our theoretical results, we have also conducted a set of simulations for our three problems. Our theoretical results capture the worst-case performance (i.e., minimax rates). Thus, for simulations, we are particularly interested in the following two questions: (i) Can we simulate the worst-case scenario and test the performance of our proposed algorithmss? and (ii) How about their performance in non-worst-case scenarios? We give detailed answers to both questions for all three problems in Appendix A, which offers additional insights into the interplay between privacy and robustness.
7 Concluding Remarks
To conclude, we have demonstrated an interesting interplay between privacy and robustness in three problems: mean estimation, online and offline MABs. The punchline across three problems is that

---

corruption after any LDP mechanism becomes easier, i.e., the same amount of corruption leads to worse performance when compared to the case where Huber corruption happens before LDP mechanisms. We also give the first set of results for the most practical C-L.P-C setting.
Some interesting future directions include (i) improving the sub-optimal result for linear bandit in Charisopoulos et al. (2023) by following existing private linear bandits (Li et al., 2022a, 2024) along with the assumption of bounded reward: (ii) generalizing it to other privacy models such as shuffle DP (Chowdhury & Zhou, 2022c); (iii) studying the case where the heavy-tailedness is characterized by the central moment rather than the raw moment currently considered in our paper; (iv) extending the results to locally private and robust reinforcement learning by building upon existing results such as Chowdhury & Zhou (2022a); Liao al. (2023); Zhou (2022).
Acknowledgements
XZ is supported in part by NSF CNS-2153220 and CNS2312835. XZ would like thank Daniel Kane for the helpful discussions.
References
Shubhada Agrawal, Sandeep K Juneja, and Wouter M Koolen. Regret minimization in heavy-tailed bandits. In Conference on Learning Theory, pp. 26-62. PMLR, 2021.
Shubhada Agrawal, Timothée Mathieu, Debabrota Basu, and Odalric-Ambrym Maillard. Crimed: Lower and upper bounds on regret for bandits with unbounded stochastic corruption. arXiv preprint arXiv:2309.1656 2023.
Shubhada Agrawal, Timothée Mathieu, Debabrota Basu, and Odalric-Ambrym Maillard. Crimed: Lower and upper bounds on regret for bandits with unbounded stochastic corruption. In Interna- tional Conference on Algorithmic Learning Theory, pp. 74-124. PMLR, 2024.
Jason M Altschuler, Victor-Emmanuel Brunel, and Alan Malek. Best arm identification for contami- nated bandits. Mach. Learn. Res., 20(91):1-39, 2019.
Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. arXiv preprint arX10:2302.01855, 2023.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-256, 2002.
Debabrota Basu, Odalric-Ambrym Maillard, and Timothée Mathieu. Bandits corrupted by nature: Lower bounds on regret and robust optimistic algorithm. arXiv preprint arXiv:2203.031888 2022.
Donald Berry and Bert Fristedt. Bandit problems: sequential allocation of experiments (monographs statistics and applied probability). London: Chapman and Hall, 5(71-87):7-7, 1985.
Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky. Minimax m-estimation under adversarial contamination. In International Conference Machine Learning, pp. 1906-1924. PMLR, 2022.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transac- tions on Information Theory, (791111777117711 2013.
Vasileios Charisopoulos, Hossein Esfandiari, and Vahab Mirrokni. Robust and differentially private stochastic linear bandits. arXiv preprint arXiv:2304.1174 2023.
Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under huber's contamination model. The Annals of Statistics, 46(5):1932-1966, 2018.
Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Online and distribution- robust-
ness: Regression and contextual bandits with huber contamination. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 684-695. IEEE, 2022.
10

---

Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, and Liwei Wang. (locally) differ- entially private combinatorial semi-bandits. In International Conference on Machine Learning, pp. 1757-1767. PMLR, 2020.
Albert Cheu, Adam Smith, and Jonathan Ullman. Manipulation attacks in local differential privacy. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 883-900. IEEE, 2021.
Julien Chhor and Flore Sentenac. Robust estimation of discrete distributions under local differential privacy. In International Conference on Algorithmic Learning Theory, pp. pp.p111144011.... 411-446. PMLR, 2023.
Sayak Ray Chowdhury and Xingyu Zhou. Differentially private regret minimization in episodic markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp.
2022a.
Sayak Ray Chowdhury and Xingyu Zhou. Distributed differential privacy in multi-armed bandits. arXiv preprint ar arXiv:2206.0577 2022b.
Sayak Ray Chowdhury and Xingyu Zhou, Shuffle private linear contextual bandits. arXiv preprint arXiv:2202.05557. 2022c.
Ilias Diakonikolas and Daniel M Kane, Algorithmic high-dimensional robust statistics. Cambridge University Press, 2023.
John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-200 101-201, 2018.
Kristian Georgiev and Samuel Hopkins. Privacy induces robustness: Information--oompuatiioo gaps and sparse mean estimation. Advances in Neural Information Processing Systems, 35:6829-6842. 2022.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 1562-1578. PMLR, 2019.
Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies
privacy in statistical estimation. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pp. 497-506, 2023.
Peter Huber. Robust estimation of a location parameter. Ann. Math. Starist., 35(4):73- 1964.
Ayush Jain, Alon Orlitsky, and Vaishakh Ravindrakumar. Robust estimation algorithms don't need to know the corruption level. arXiv preprint arXiv:2202.054553 2022.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference machine learning, pp. 1385. PMLR, 2015.
Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pp. 2204-2235. PMLR, 2020.
Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Corruption tolerrat bandit learning. Machine Learning, 108(4))687-715, 2019.
Shiva Prasad Kasiviswanathan. Homin K Lee. Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011.
Fengjiao Li, Xingyu Zhou, and Bo Ji. Differentially private linear bandits with partial distributed feedback. In 2022 20th International Symposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks (WiOpt). pp. 41-48. IEEE, 2022a.
Fengjiao Li, Xingyu Zhou, and Bo Ji. Distributed linear bandits with differential privacy. IFFE Transactions Network Science and Engineering, 2024.

---

Mengchu Li, Thomas B Berrett, and Yi Yu. On robustness and local differential privacy. arXiv preprint arXiv:2001.00751, 2022b.
Chonghua Liao, Jiafan He, and Quanquan Gu, Locally differentially private reinforcement learning for linear mixture markov decision processes. In Asian Conference on Machine Learning, pp. 627-642. PMLR, 2023.
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distribu- tions: A survey. Foundations of Computational Mathematics,
2019.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 114-122, 2018.
Nikita Mishra and Abhradeep Thakurta. (nearly) optimal differentially private stochastic multi-arm bandits. In Proceedings of the Thirtt-FFrst Conference on Uncertainty in Artificial Intelligence, pp- 691-601,220 2015.
Arpan Mukherjee, Ali Tajer, Pin- Yu Chen, and Payel Das. Mean-based best arm identification in stochastic bandits under reward contamination. Advances in Neural Information Processing Systems, 34:9651-9662 2021.
Laura Niss and Ambuj Tewari. What you see may not be what you get: Ucb bandit algorithms robust to 8-contamination. In Conference Uncertainty in Artificial Intelligence, pp. 450-459. PMLR,
2020.
Dan Qiao and Yu-Xi Yu-Xiang Wang. Offline reinforcement learning with differential privacy. arXiv preprint arXiv:2206. 00010, 2022.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702-11716, 2021.
Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.03121, 2020.
Touqir Sajed and Or Sheffet. An optimal private stochastic-mab algorithm based optimal private stopping rule. In International Conference on Machine Learning, pp. 5579-5588. PMLR, 2019.
Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp. 1546-1574. PMIR, 2022.
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Differentially private multi-armed bandits in the shuffle model. Advances in Neural Information Processing Systems, 34, 2021.
Aristide CY Tossou and Christos Dimitrakakis. Algorithms for differentially private multi-armed bandits. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. On private and robust bandits. arXiv preprint arXiv:2302.02526, 2023.
Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang. Locally differentially private (contextual) bandits learning. Advances Neural Information Processing Systems, 33:12300- 12310, 2020.
Xingyu Zhou. Differentially private reinforcement learning with linear function approximation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(1):1-27, 2022.
Xingyu Zhou and Jian Tan. Local differential privacy for bayesian optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12)11152-11155) 2021.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: All claims (i.e., there exists a fundamental interplay between LDP and ro- bustness under Huber corruption and heavy-tailedness) in abstract and introduction reflect the contributions and scope of our paper. We also provide list of our core contributions directly in our introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: One limitation is the algorithm's 's dependence on the unknown parameter A practical fix suggested is to use an estimated upper bound on a, but the theoretical aspect of completely removing this dependence is complex, the discussion in Appendix C.2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section 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 on 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 on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to 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, worse outcome might be that reviewers discover limitations that aren't acknowledged
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.
13

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We state all assumptions of our theoretical results under three problems: mean estimation, online MABs, and offline MABs. For mean estimation, we offer a tight characterization of high-probability mean estimation eroos under both L.TC and CTL settings, with detailed proofs provided in Appendix E and Appendix F. Building on this, the paper presents an almost tight (up log factor) characterization of the minimax regret in online MABs (Appendix I, Appendix H) and the sub-optimality in offline MABs (Appendix Appendix K).
Guidelines:
The answer NA means that the paper does not include theoretical results. 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 supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide a comprehensive discussion of the experiment details for each problem and various types of corruption settings at the beginning of our simulation section (Appendix A).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, 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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
14

---

(c) If the contribution is a 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 or 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 reproducibility. 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 the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the code with detailed instructions for the experiments discussed in Appendix A.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: wwwp//eeeeaisiiiioooooooooooo
//nips.co... cttpsssicc/ppcc//cccccccecccclcc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: We thoroughly list all training details and demonstrate the results in Ap- pendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core 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, 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?
15

---

Answer: [Yes]
Justification: We present different metrics to assess the performance of our algorithms with error bars. Mean estimation
shown under different corruption scenario (Fig. Fig. 3). Similarly. the online algorithm's 's performance under various corruption scenarios is displayed (Fig. 4, Fig. 6). Comparisons between our specific algorithm and other algorithms under Online MABs are also provided (Fig. 5). Lastly, in offline MABs, the suboptimality of our algorithm is illustrated (Fig. 7). For full information, please check Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of 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 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: [No]
Justification: Our experiments designed primarily to support the theoretical results and are relatively simple in their settings. They do not require high-performance hardware and can be most standard computers.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 Fthics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp:://nee.....eeee wwtppcccccc/ceeececcceccccceccee ctticcsuuiellnnss
Answer: [Yes]
Justification: Our experiments are relatively simple their settings, and no privacy informa- tion is leaked through our code.
Guidelines:
16

---

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 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: [Yes]
Justification:
We discuss the broad implications in Appendix D.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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., dep.oymeet 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 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 generate deepfakes for disinformation. On other hand, it is not needed to point out that 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.
If there are negative societal 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 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 no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
17

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset 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 (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
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 anonymize your assets (if applicable). You can either create an 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 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 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
18

---

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 crowdsoureing 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 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 the institution conducting the review.
19

---

A Simulations
In this section, we conduct numerical simulations assess the performance of our algorithms in three problems (i.e., mean estimation, online MABs and offline MABs), under both LTC and CTL settings. Recall that our performance metries for all three problems are minimax ones, which capture the worst-case performance. As a result, we are particularly interested in the following two questions in our simulations:
①i Can we simulate the worst-case scenario and test the performance of our proposed algorithms? (ii) How about their performance in non- wonts-oss--eeeeeee scenarios?
Note that (i) essentially sheds further light on how to design the most powerful adversary Huber corruption model, which in turn could explain the separation result between LTC and CTL from the perspective of attacking. On the other hand, (ii) would help to illustrate our algorithms' performance in some mild/real-world non-adversary Huber corruption. For example, although the minimax regret for online MABs has linear term in the worst case, the actual performance under the non-adversary corruption model can be sub-linear as we will show later.
A.1 Mean estimation
We start with the worst-case scenario for the mean estimation under a large sample size regime where the minimax error rate is dominated by the corruption part, i.e., the separation result (a/e) under LTC vs. a 1-1/ under CTL. To this end, we need to design the most powerful adversary corruption for both LTC and CTL. Here, allow the (white-box) adversary choose inlier distribution over X and can adaptively choose Huber corruption distribution based on inlier distribution and the knowledge of our algorithm, e.g., LDP mechanism Q in the LTC setting.
In particular, the adversary chooses the following inlier distribution:
-(X-1/1) = 2
- -1x==1/-)=
P)
(5)
where y = (a/s)2/k under LTC and y = (a) under CTL. One can clearly see that E for all & > 1, hence P E Px for any
[
<
and a S E. Moreover, we have E [X] =
Now, we first consider the following strong Huber corruption model.
Definition 7 (Strong Huber corruption for mean estimation). Let the inlier distribution over X be given by (5). Under LTC: for each input Y,, with probability a, replace with e'+l. Under CTL: for each input X,, with probability a, replace it with M;
Note that, the white-box adversary knows our algorithm and hence M. We are going to show that no matter how large the sample size is, the mean error has to be large for both LTC and CTL under the above strong Huber corruption.
Let us start with CTL and consider the sample size n to be large. Then, according to Algorithm 1, M (1/a)//k 1/7, which leads to the fact that the mean of Y is now aM a 1-14 (note [[x]= = 0). Then, our estimator will essentially at best return the mean of Y, hence leading to the error of ((at-1/k) For LTC, with the choice y and M, we also have M = 1/7. By our design of LDP mechanism Q in Algorithm 1, the mean of Y is still zero and hence after the corruption, the mean of Z becomes a M M which is the best outcome of our estimator, hence the error e--1"
of ((///)))-1/k)) Note that in both cases, the choice of corruption distribution needs care (i.c., adaptation to algorithm), since otherwise. our estimator may still have accurate estimate, as some other outlier values can be simply filtered out by our algorithm. More importantly, an alternative explanation of our separation result becomes evident: under LTC, the error is larger because the adversary has the capability to select a corruption value that is magnified by a factor of 1/e.
In our experiments, we choose k = 2 and consider various corruption level E {0, 0.02, 0.05} and privacy budget ε (0.3, 0.5, 1). For each set of parameters, we conduct 300 runs and plot the average of the estimation error and corresponding confidence region. Fig. 2 illustrates our simulation results under strong Huber corruption in Definition Fig. 2 is that due to strong corruption, the estimation error will only converge to plateau and almost
common pattern behind all the plots in
20

---

match the lower bounds. Specifically, from the two plots in column (a), we see that when a 0 or 1, the performance under LTC and CTL close (i.e., no-separation), which aligns with our theoretical results. In the two plots of column (b), we see that L,TC has larger error than CTL. and as & decreases (i.e., stronger privacy), the difference becomes larger, which matches our theoretical separation results. Finally, comparing the plots in column (c) with those in (b), we see that as the corruption level increases, the performance becomes worse.
We also consider the following weak corruption model, which simply flips the sign of the data.
Definition 8 (Weak Huber corruption for mean estimation). Let the inlier distribution over X be given by (5), Under LTC: for each input Y, with probability a, replace it with -Y;; Under CTL: for each input X,, with probability a, replace it with X,;
0%, 0.5
2%, 0.3
5%,
0.3
UTC
CTL-ooweroound
0:33
6.0
1800
20:00
3006
2000
1200
02 1%, 1.0
0 2%, é 0.5
0 5%, 0.5
140
LTC
LTC
LTC
CTL
CTL
6.7
Lowcrooodd
LTC Lowas Bound
LTC Lowe Bound
CTL-LowerBound
CTL-LowwrBoue Bound
CTL-LowerBourss
(3) = 0
(b) 2%, vary E
(c) = 5%, vary
Figure 2: Mean estimation error with strong Huber corruption in Definition 7 under LTC and CTL settines.
5%,
UC
UC
LTC
CT.
380
3000
Figure 3: Mean estimation error with weak Huber corruption in Definition 8 under LTC and CTL settings
In Fig.3, see that under weak Huber corruption, the estimation error under our estimators can indeed decrease as the sample size increases. This demonstrates that in some real-world mild corruption scenarios, our estimators can yield promising performance.
A.2 Online MABs
A.2.1
Non-adversary Corruption
In this section, we first consider some classic heavy-tailed distributions under non-adversary corrup- tion. The main purpose is to show that our proposed algorithm (i.e., Algorithm 2) can indeed achieve sublinear regret under certain scenarios. Moreover, our simulations will also provide some insights into our proof.
21

---

2-22%
2=22
2-01
C40.
3.0
0.2
0.8
10
90
922
2.3
0.8
10500
0.2
0.5
400
437
276
2-2%
2-0.L. LTC
5%%
20.0%
dm 7%
7%
3.0
0.5
(+) LTC
(b) CTL
(c) Comparison of regret
Figure 4: Regret performance with weak Huber corruption in Definition 9 under LTC and CTL settings.
Settings. As in previous works Tao al. (2022); Wu (2023), we consider Pareto distribution, whose probability distribution is given by
ex a+t1.
if 2 Zm otherwise
f(1; (m, 8)
0.
where 8 >> the shape parameter um
the scale parameter. In our experiments, we consider there are K = 10 arms, and for each arm i [K]. the distribution is Pareto with i and = 11. To ensure that each arm's reward distribution is in Px: (i.e., [x-P[[X|T] S 1), we normalize *- Consequently, the mean of each arm is 5 (s-1" We consider k which along with our choices of and Tym yields that arm 1 the best arm with
the reward by the k-th moment, which is
satm --
mean of 0.9 while arm 10 is the worst arm with a mean of 0.09. For the corruption, we consider the following Huber model.
Definition 9 (Huber corruption for online/offtine MABs). Let each arm's inlier distribution be Pareto with the parameters described above. Under LTC, for each private view of reward from each E [K]. with probability replace with M g++1 Under CTL, for each raw reward from each arm E [K], with probability a, replace with M.
Remark 6. It worth noting that even though the above corruption values are the same as in Definition 7, it is not necessarily the worst-case as the inliers are now Pareto. That is, even after corruption, the agent can possibly still distinguish between different arms. We also consider strong corruption cases where after corruption, the agent cannot distinguish the distributions of two arms, hence linear regret, see Fig. 6 for details.
Fig. illustrates the regret performance of our proposed algorithm (i.e., Algorithm 2) for online MABs under LTC and CTL settings, with the specific corruption given by Definition 9. The two plots column (a) capture the LTC setting while the two plots in column (b) denote CTL. setting. In both settings, we can see that for small corruption level our algorithm can achieve sublinear regret, even though the worst-case our minimax bounds are linear. In column (c), we also directly compare the regret performance under LTC and CTL with different sets of parameters of a and As expected, the regret performance under LTC is worse than that under CTL, and as a increases or e decreases, the gap becomes larger. This demonstrates separation results in terms of actual performance rather than only in terms of theoretical upper bounds. As a baseline, we also compare with one classic robust MAB algorithm under heavy-tailed rewards proposed in Bubeck et al. (2013).
Fig. compares our specific algorithms with algorithm proposed in Tao et al. (2022), namely LDPRSE, which is proposed for the setting of LDP and heavy-tailed rewards in online MABs. Hence, our comparisons were made in the online MAB setting under weak corruption. The findings organized into two columns, demonstrating the impact of varying (corruption) values
22

---

12
13
08
130
232
X127
UPR 0%
Figure 5: Comparison of Our Algorithms vs. LDPRSE in the online MAB setting under weak corruption.
performance as (privacy) increases. These results highlight the advantages of our algorithms over LDPRSE situations where there exist additional corruptions.
Note that our purpose in this section is not to demonstrate the superior performance of our proposed algorithm over all existing robust or/and private algorithms (given large number of different existing ones). Rather, one of the goals is to use simulations to highlight the separation between LTC and CTL. Another important goal to provide more insights into our proof of the regret upper bounds. Specifically, in our proof of the LTC setting (similar in CTL setting), we will divide the set of all
sub-optimal arms G into two groups 91 and G2 where 92 = {a E [K] a" : e ( 1 2 [AA.) for some constant Then, argue that if G2 is empty. then problem-dependent regret bound. This can also be somehow validated partially by our simulation results. In particular, under problem instances described above, when e = 0.3, we have [G2 under LTC (i.c., no sub-optimal arms G2). In this case, as illustrated in the top plot of column (a) in Fig.
still derive the standard logarithmic
0.02, 0.1, and
observe logarithmic order regret. This naturally extends to the larger case, as illustrated the bottom plot in column (a).
A.2.2 Strong Huber Corruption
As mentioned above, we also create a strong Huber corruption for online MABs, in this case, the regret becomes linear which matches our minimax lower bound. In this scenario, our goal is to create an adversary strong Huber corruption for online MABs, where the agent cannot distinguish the distributions of two arms by utilizing the following probability distribution:
= P(X = 1/7) = * P(X=0)= =1-))=122
P'(X 1/7) = 12, 0)
where y adopts the form (a/e)1/k under LTC and C₁ (a)1/k under CTL. with eı configured as 0.1 to ensure ² < 1 for an expansive As before, P. P' E Pe for any > and μ(P) = *=1 ju( (u(P) = - Let P and P' represent the distributions for arms and respectively. We define the corruption distribution under CTL settings
Definition 10 (Strong Huber corruption under CTL. Settings.
C(X = 1/>) -2
C(X = 0) = /
C' 1/>) = >
C' - x
23

---

c1 - According to 2, it is apparent that the agent cannot differentiate between P and P' upon executing the operation:
(1 (1-a)P+aC = (1 o) oaC
This outcome emerges from the CTL's inherent nature of initially introducing contamination, which perseveres in maintaining indistinguishability. even post-transmission through the LDP channel and the Huber model.
In the context of LTC settings, the distinctiveness arises from the fact that the distributions of P and P' undergo alterations after passing through LDP, necessitating corresponding corruptions. Let R and R' be the post-LDP transformation distributions over variable Y, defined as:
1
k
e
g c -
R(Y = S) -)==)--
R(Y = S) =
2
2
e
+1
2
2
e
+1
1
k
-1
- 7
e
-1
2
4
E +11
4
e
+
where S = M
Additionally, we define the corruption distribution as:
Definition 11 (Strong Huber corruption under LTC Settings).
ex
2 -1- e -1
N(Y = 5) =
N(Y = -S =1
4
e
+1'
4 e +
c -
1
N' S) = 1 )
e - 1
N' 8)
+1 a'
e +1
Now we also have (1 - aa) + aN = (1 (1- a) + aN', indicating our continued inability to distinguish between P and P' in the LTC setting.
Fig. 6 illustrates the regret performance of our proposed algorithm (i.e., Algorithm 2) for online MABs under LTC and CTL settings, with the strong Huber corruption in Definition 10 and Definition 11. common pattern behind all the plots in Fig. is that due to strong huber corruption, the agent cannot distinguish the distributions of two arms, hence linear regret. Based on the analysis above, we anticipate that the regret will scale linearly by a factor of é₁ with respect to our minimax clean regret and Fig. 6 aligned with our discussion. The two plots in column (a) capture the LTC setting while the two plots in column (b) denote the CTL setting. As expected, the regret performance under LTC is worse than that under CTL, highlighting separation results in terms of actual performance rather than only in terms of theoretical upper bounds.
A.3 Offline MABs
In the offline case, the analyzer/agent is given batch of pre-collected data with private and corrupted view. In our experiments, we again consider the case that there are K = 10 arms and each arm's 's raw reward distribution is Pareto with the same parameters in the online case. For corruption, we again consider the one given by Definition 9.
One difference here is that need to specify the behavior policy that is used to collect the data. To this end, we consider the following policy π in our simulation results: for each sample size N, pulled the best arm (i.e., arm 1) times and each other arm i + uinformly, i.e., 3 -(K- times. That is, roughly speaking. we approximately have 1/T 1/T(a*) = 3, which aligns with our theoretical assumption (i.c., the finite concentrability coefficient 8 > 2 when our upper bounds are tight in minimax sense).
2N
Fig. 7 illustrates the suboptimality of our algorithm (i.e., Algorithm 3) under both LTC and CTL settings. We can see that in both settings, the sub-optimality could approach zero under several values of privacy parameters. This again highlights that under malld/oon-adeersee algorithm could yield reasonably good performance, rather than the pessimistic worst-case one, Also, we observe that even in this non-adversary corruption case, suboptimality under LTC in general is still worse than that under CTL. Finally, is not surprising that for both LTC and CTL, as a increases or decreases, sub-optimality will increase.
corruption, the
24

---

-=0.3
1%
1%
3%
3%
5%
7%
regret
1
0.0
0.2
0.5
0.8
1.0
0.0
0.2
0.5
0.8
1.0
x20
e- 1.0
x107
c --10
1%
3%
0 5%
5%
7%
7%
regret
0.0
210"
130
LTC, vary a
(b) CTL, vary a
Figure 6: Regret performance with strong Huber corruption in Definition 10 unde CTL settings and Definition 11 under LTC settings.
0 1%
a= 1%
0.1.1
0.1
8.75
0.3
5.75
0.3
s.b-oztimality
sub optimallayy
2 0.4
625
625
75085
50000
100009
33000
X000
15830
108530
3.00
1.00
0.1
0.1
=
= 0.2
0.3
0.3
sub optimaltyy
6:0-
6.00
LTC, vary
CTL, vary
Figure 7: Suboptimality performance with Huber corruption in Definition 9 under LTC and CTL settings.
25

---

B Additional Related Work
Private Ms To offer mathematically rigorous privacy protection, LDP is first introduced to MABs in Ren et al. (2020) where the authors establish private lower bounds on both problem-dependent and groblem-independen (minimax) regrets as well as several LDP mechanisms and learning algorithms that achieve nearly-optimal performance. Later, it is generalized to the heavy-tailed setting in Tao et al. (2022). LDP has also been considered in various other bandit settings (Chen et al., 2020; Zheng et al., 2020; Zhou & Tan, 2021). In addition to LDP, other strictly weaker privacy models have also been considered in MABs to achieve a better regret, such as central DP where users need to trust the central learner (Mishra & Thakurta, 2015; Tossou & Dimitrakakis, 2016; Sajed & Sheffet, 2019) and distributed DP where users need to trust the intermediate third-party party (Tenenbaum et al., 2021; Chowdhury & Zhou, 2022b). In addition to the above online MABs, recent work (Qiao & Wang, 2022) also considers offline RI. (hence MABs) under central DP with bounded rewards.
Robust MABs. Robust MABs under Huber corruption have been recently studied in Kapoor et al. (2019); Mukherjee et al. (2021); Basu al. (2022); Agrawal et al. (2024). Several other corruption models have also been considered in MABs, such budgeted-corruption model where the cumulative difference between observed reward and true reward is bounded by some constant budget (Lykouris et al., 2018: Gupta et al., 2019) and strong contamination model (Niss & Tewari, 2020; Altschuler et al., 2019). Robust regret minimization in MABs under heavy-tailes rewards have also been studied, e.g., Bubeck al. (2013); Agrawal et al. (2021). Private and Robust MABs. As mentioned above, the existing literature largely investigate privacy and robustness in MABs separately. To the best of our knowledge, there are only two very recent works that consider privacy and robustness in MABs simultaneously. In Wu et al. (2023), the authors consider the central DP model where the raw non-private feedback received by the central learner can be first corrupted under Huber model. This is in sharp contrast to our local DP model, which is not only stronger but allows us to study the order of corruption and privacy. In Charisopoulos et al. (2023), the authors study linear bandits (which includes MAB as a special case) under LDP and then Huber corruption (i.e., LTC setting). As discussed in Section 4, their regret bound is sub-optimal and worse than ours when reduced to the MAB case. Note that we also study the CTL setting, which in turn highlights the interplay between privacy and corruption. Moreover, the results for both LTC and CTL allow us to give the first results for the C-LDP-C setting.
Private and Robust Mean Estimation. Our work is inspired by recent advances in (locally) private and robust mean estimation. In particular, for the CTL setting, the authors of Li et al. (2022b) give the tight characterization in terms of wwean-squareerrro (MSE). In contrast, we derive the high probability concentration. For LTC, both Cheu et al. (2021); Chhor & Sentenac (2023) give constant-probabille concentration when the inlier distribution is bounded. Instead, we present the high-probability version even for heavy-tailed inlier distribution, which requires new analysis and design of the estimators. We would also like to point out some other related private and/or robust mean estimation results. For instance, under central DP, Kamath et al. (2020) gives the first high probability mean concentration for heavy-tailed distributions. For standard non-private mean estimation under heavy tails, we refer readers to the nice survey by Lugosi& & Mendelson (2019). For non- non-private mean estimation under corruption in general high-dimension space, we refer readers to the nice book by Diakonikolas & Kane (2023). We finally remark that there are recent exciting advances in understanding the connection between robustness and privacy in mean estimation (e.g., robustness induces privacy Hopkins et al. (2023); Asi et al. (2023) and vice versa Georgiev & Hopkins (2022)), which, however, mainly focus on the central DP model.
C Discussions
C.1 Discussions on Practical Scenarios for LTC and CTL
In the introduction, we have motivated our paper using the example of online recommenda- tion/advertising via MABs. Here we give two more concrete examples. The key difference between LTC and CTL in practice is that LTC mainly models the situation where the data transmission is vulnerable to manipulation while CTL models the situation where the data source is more vulnerable to manipulation.
26

---

CTL: Consider a healthcare recommendation system that suggests personalized health interventions based on patient data. In this case, the data might first be corrupted (intentionally or unintentionally) before being subjected to LDP mechanisms, such as when data is collected from various sources with different levels of reliability or when users self-report their health information with errors or falsifications. However, the data transmission is often well-controlled in this case and is not likely vulnerable to manipulation due to strong federal regulations.
Siirmett-f-Things smart-home application where sensors are de- ployed to monitor/control the temperature or other metries in homes. These sensors often have built-in checks to ensure that the data is collected correctly. However, after the LDP mechanism at each sensor from each home, the data transmission process through wireless networks (channels) is often more vulnerable to manipulation attacks, e.g., man-in cen--ii-the-mmeee the-middle attacks, packet sniffing, or spoofing.
LTC: Consider a wireless IoT
In addition to the above two examples, we do believe that there are many other practical scenarios that motivate our study of the interplay between LDP and Huber corruption.
Key implication of "LTC is harder": If our recommendation system requires LDP protection, then the adversary can tailor its manipulation attack (corruption) based the LDP mechanism (hence E) to amplify the error by the order of 1/e. In other words, LDP protocols are highly vulnerable to manipulation poisoning the private messages itself. As a result, is important to keep our private protocol "secret" as the adversary needs to tailor its attack according the LDP protocol to create the worst-case scenario (strongest attack).
be far more destructive than poisoning the data
C.2 Robust Estimators without Knowing Corruption Parameter
Currently, whether it is possible to derive tight error bound without knowing a is still unclear to us. In particular, on the one hand, there are some positive results (Jain et al., 2022; Bhatt et al., 2022) for some estimators. On the other hand, some work suggests some negative results regarding MAB problems (Agrawal et al., 2024). Note that all Jain al. (2022); Bhatt et al. (2022); Agrawal et al. (2024) only consider corruption, i.e., privacy protection. Thus, one interesting future work is to settle down this problem, which beyond the scope of our current paper.
C.3 Ungrounded Regret Upper Bound in State-of-the-Art
In Tao al. (2022), the authors consider simpler setting - locally private heavy-tailed online MABs, i.e., without corruption. They claimed to achieve regret upper bound on the order of
o ((x)=11/+T11)) T1/k). However, given our tighter lower bound f T
h-1 in Proposition 3,
their upper bound becomes ungrounded as it contradicts our lower bound for large T. In particular, considering & = 2 (with only a bounded second moment), our lower bound gives a regret on the order of Q(T3/4) while their upper bound is O(VT).
Remark 7. In fact, our lower bound also gives another interesting interplay between privacy and robustness (in particular, heavy-tailed rewards). Specifically, the non-private case, as shown in the Bubeck et al. (2013), one can still achieve O ((VT) regret when the reward distributions have only bounded second moments. However, in the locally private case, our lower bound indicates that the regret is at least ((73/1).
D Broader Impact Statement
This research presents novel insights into the interplay between local differential privacy and ro- bustness in the context of Multi-Armed Bandits (MABs), with focus on two distinct settings: Local Differential Privacy then Corruption (LTC) and Corruption then Local Differential Privacy (CTL). The findings have broad implications in various domains, particularly in online advertising and recommendation systems, where privacy preservation and data integrity are paramount, By enhancing the robustness of MAB algorithms against corruption and heavy-tailed feedback while ensuring local privacy, our work can significantly contribute to the development of more secure and reliable decision-making systems. We show that the mean estimation error under LTC is larger than under CTL, emphasizing that LTC is more challenging setting. This separation is critical for
27

---

practical upplications like healthcare recommendation systems (CTL) and wireless IoT smart-home applications (LTC). Additionally, our algorithms can adaptively guarantee optimal minimax rates across different settings without prior knowledge, which is crucial for real-world scenarios where the specific setting may not he known in advance. However, the complexity and computational demands of these advanced algorithms might limit their accessibility to smaller organizations, potentially widening the gap between large and small entities. Moreover, while our approach reduces privacy leakage and data manipulation risks, it does not completely eliminate them. This is particularly important because adversaries can tailor their attacks based on the LDP mechanism to amplify errors. Thus, ongoing efforts should focus on further improving these algorithms to address potential ethical issues, including data bias and privacy concern,, and enhancing their accessibility and faimess. Furthermore, deriving tight error bounds without knowing the corruption parameter remains an open challenge, suggesting the need for future research this area.
E Proof of Proposition 1
Proof. We first focus on the LTC setting and divide the proof into two steps.
Step 1:
Without corruption. By definition, it suffices to establish a lower bound on the concentration
even without corruption. That is, under LTC, Zr = Y, for all E [n]. This will give us the second term in the bound.
Consider the following two distributions P and p'. Let y > 0, specified later and
P(X = 1/7)= P(X = 0) = 7 P'(X 1/7) = 1/2 P'(X 0)=0) - 1/22
(6)
It is easy to see that for both P" E [X < 1 for all k > 1, hence P' E Pa for any k > 1. Moreover, we have } (pP) = 1/2. f and TV (P, P") -1/2.7². For any e-LDP channel Q, let M and M' be the induced marginal distribution from and P', respectively. That is, for i E [m]. Y M and Y M'. Let MM] (Y))_. and 7/ (Y,) ie.. Mnn M and (m) ~ M
The high-level idea behind our proof is as follows: Given any sample size n, if there exists at least probability 26 such that [i]] %/.- then one has to incur 1()*=1) estimation error with probability 5. This naturally reminds to think about maximal coupling, since it maximizes the probability that Yin = V%, and is also closely related to TV distance. In particular, we have the following textbook facts.
Lemma 1. Let P1 and P3 be two distributions on X that share the same o-algebra. There exists a coupling w" (P1, P2), which is distribution over X² such that
P(x,,X))_w (X1 * X2) TVP), VS measurable, ((x..)))ww (X1 E ES) PI ES) SS measurable, (x. measurrable.Pxxx....vvvvv Ba)
X2 E S) = Pa(22 ES..
This coupling is called maximal coupling.
Based on this fact, fix some n. if (Ynn) Yiy)) is sampled from the maximal coupling w (M S)). then we know that there exists a probability p 1 1-TV(M/*" (M'"", M such that YM,] Yin. To lower bound p. we need to upper bound the TV distance. To this end, we will leverage Bretagnolle- inequality and strong data processing inequality (i.e., Corollary 3 in Duchi et al. (2018)). In particular,
28

---

we have
(a)
1
TV(M M
S
exp (-KT. (Me*l M)en)
2
(6)
1
(-4(e - 1)2 n (TV (P, PT)))
exp
2
1
= 1
exp
(-4(e- - -1)² -n 7
2
(
1
X 1
2 cxp (-16e² ,22))
where (a) holds by Bretagnolle Huber inequality; (b) holds by Corollary 3 in Duchi et al. (2018); (c) Vlog(1/5) for some constant c. Then,
1/k
true since e 1 for E [0, 1]. Thus, let o =
cv
for large enough n, 7 k- < and TV (VM@n, 8
< 1
26, which implies that with probability
1/k
(log(1/6) Ev'
least the error is (0()~11) =
Step 2: Corruption part. Recall that under a- o--Huber, for each private view Y, it is independently comrupeed with probability a, and when it happens, Z₁ is sampled from arbitrary noise distribution N; otherwise, Z, = Y,. To proceed, we will utilize the following useful fact.
Lemma 2 (Theorem 5.1 in Chen al. (2018)). Let Rı and R be distributions on X; ffr some E [0, 1/2), we have that TV (R1, R2) I I-a' then there exist two distributions N₃ and N2 on the same probability space such that
a
(1- a) + aN (1-a)Rg + aN
This result says that the Huber model with parameter can corrupt two distributions that close in TV distance so that the outputs are essentially sampled from the same distribution, hence indistinguishable.
Another fact we will leverage is that LDP mechanism a "contraction" in that it will make the TV distance closer.
Lemma (Corollary 2.9 in Kairouz et al. (2014)). For any & > 0, let Q be any s-LDP mechanism. Then, for any pair of distributions P1 and Pz, the induced marginals M1 and M2 satisfy
TV (M1, M2) S e e1
TV (PI,
The above fact indicates that for E [0, 1]. TV (M, M2) facts, it suffices for us to find two distributions P and l" for X, with "large" mean difference, such that the induced marginal distributions for Y, (a)). To this end, again consider the two distributions in (6) with different choice of Since TV (P,
< (c))TV(PP)) (PI.P)) With the above two
1/2-a*, by Lemma 3, choosing y c' (a/e) 1/k for some small constant d' O yields that TV (M) < aa(1 at). Hence, by Lemma 2, there exists Huber contamination such that it is impossible to distinguish the final outputs. Hence, with a probability of at least 1/2, the error is 2t (-*-1) = f2 ((a/e)1-1/A) We finally conclude that for any 8 E (0, 1/2). with probability at least for all large enough n, estimation error is 52 (11= = ((a/s)1-11)
This finishes the proof for the LTC setting.
As for the CTL setting, the second term in the lower bound follows the same proof as Step 1. The key difference lies in Step i.e., the first term in the bound. In particular, since the contamination is before LDP, result, the estimation error is Ω (1)= Ω (a 1-1k//
only choose 7 c'a 1/k: i..., no "contraction" from LDP anymore. As
F Proof of Proposition 2
Proof. Let us start with the LTC setting. As for privacy, it builds on the privacy guarantee of random response.
29

---

Privacy. By definition, we need to show that for any two inputs z, E X and y E
{M ce-11 1-
-
P y = y = x] P y/ x'] Se.
Consider the case = + and similar analysis applies to the other case. Let M be the probability that x is translated to M in our mechanism Q and P--- be the probability that x is translated to M in mechanism Q. Similarly defines - and P
c--1
Thus, according to our Q in Algorithm 1) and let Pe = e we have
TP Y y/ X 2] = P Pe P (1- Ps)
IP Y y|xx x') P Ps P (1-P3)
As result,
P = y|x PA-MY + P Pa-M (1- Pa)
Ps
Se.
P - y|X= PR-MM+ Pe + P Ps)
1 Ps
Utility. For the utility part, we will divide the proof into four steps. We draw the following informal diagram for an illustration of Algorithm 1.
Trunc. (.nncc(MC of
X; [Md)
X; Random Rounding
X
Random Response
Y,
Cormuttion Z;
2;
Sample Mean
Pa
Step 1: Bound the number of corrupted points.
By Chernoff bound for the binomial distribution, we have that for 2 3 3log(1/8)/a
|B| S 2an, w.p. 1- 8,
where [B] denotes the total number of corrupted ("bad") points. Let this event be E, and in the following steps, we will condition on this event.
Step 2: Bound the distance |E [X]]] E [X:] J.
E [X
E [X]] <
|E [X+] - E [X. + EE - - [X]]
(9)
E [X.] - E X. +0
<
E
[[ [[Xx 2 M)]
M
where (a) holds by the property of random rounding. Recall that, for any X, [-M, M]. X M
w.p. 1+X./M and X - MM w.p. 1-X./M Thus, one can see EE [X]]X.] = X,, hence E. [X.] E [X]]: (b) holds by Hölder's ' inequality and the fact k-th moment of X; is upper bounded by one.
Step 3: Bound the distance [E pul.
P.m - E [X]]
1
Σ
2, E [
=
1
Σ
2, Σ
Y2
+
1 Σ Yı - [
n
n
(0)
< 2a M.
E +1
+
1
Σ Yi E [xII
c -1 1
++1
E +1
log(1/8)
2a M
+0
M
w.P. 1 - 8
6
-
30

---

where (a) holds by triangle inequality, the event & in step 1, and the fact that Z,, Y are both bounded; (b) holds by Hoeffding inequality. Note that Y ='+1 X w.p.
ee e and Y; --+1 X w.p. कन
That is, I [Y:]
[X;] and {M - M
Step 4: Put the above parts together.
For any E [0, 1), any (0, 1) and any E Pk. we have with probability at least
Pnn x(P) So (
a.
M
log(1/0)
M
1/k
Thus, choosing M = min
( (5)
v
yields that
Vlog(1/5)
1-1/8
Fh m(P) 5O
a
1-1/1
+
(1/)
which finishes the proof for the LTC setting.
Now, let us move the CTL setting. For privacy, it follows from the same idea as the LTC setting.
For utility, we will divide the proof into five steps and leverage the following informal diagram for an illustration of Algorithm 1.
Comuutton
Trunc.(M) (M), Y;
Random Rounding Y! Random Response
Sample Mean
X
Y
Zi
Fn
Step Bound number of corrupted points.
By Chernoff bound for the binomial distribution, we have that for n 2 3 3log(1/8)
B < 2am, w.p.
1- 8,
where [B] denotes the total number of corrupted ("bad") points. Let this event be E, and in the following steps, will condition this event.
Step Bound the distance P
E
pinn
Σ
E
Σ
2i E
[Y;]
e +1
log(1/6)
M
w.p. 1 1-6 8,
where (a) holds by property of random rounding, i.e., E [Y.] E [XT]: (b) holds by property of random response, i.e., E [Z,] = E [Y?]] and Hoeffding inequality.
Step 3: Bound the distance 1 Σ Y + E
[.]
-
log log(1/0)
Y 5 M
w.p. 1
n
72
where it simply follows from Hoeffding's 's inequality.
31

---

Step 4: Bound the distance
1 Y, B [X,] |-
-
Σ
E [
Σ Yi
RE
Y - [X + 20r
169
X - M) - - - 1 Σ
XXXXX & M)I + 2a
8E
X M) - 4a.
Σ KE
X & M) - [X & MII+ [[ S M)] [X]]
+4a.
71
where in (a), 9 represents all "good" indexes that are not corrupted and B represents all "bad" indexes that are corrupted: (b) follows from the boundedness Y, and the event & in step
For T2, by Hölder's 's inequality and the fact k-th moment of X; is upper bounded by one, we have
T2 S O
M
For T1, consider two cases: (i) k (1, and (ii) k when applying Bernstein's 's inequality.
For case (i), we note that E [X] - M)] = E [[X | - MM] S E [IX (
M2-k where (a) follows from à < 2. Thus, by Bernstein's 's inequality, have
Ti T (
M log(1/6)
M log(11) 100(
For case (ii), we note that E [X?1 S M)) have
< E X3 < Thus, by Bernstein's 's inequality, we
50 (V log(1/0)
M log(1/6)
Step 5: Put everything together. Case (i): for any & (1,2), e [0, 1]. any (0, and any
P E Pk, we have with probability at least 1 5,
(V
M log(1/8)
M log(1/5)
+0 log(1/0)
M
Prn - x(P)
+0
+0
+(aM))+
MK-1
n
n
n1
Thus, choosing M min
{ (mmaiiir))
1/4
(2)
1/k
EVT V1oR(1/55
1/k
yields that
( (log(1/8) 1-1/k
1-1/K
Vlog(1/0) Evn
P.n - ((P))
+
1-11/
n
Hence, when 2 loog(18)), have
(
(Vlog(188) evn
1-1/k
pnn m(P)) 50
+ a 1-1/
32

---

Case (ii): for any k 2, E [0, 1], any & E (0, and any P E Pks we have with probability at least 1- 8,
log(1/6)
M (log(116)
M
log(1/5)
Iin - (PP) 50
+
+0
O(aM) +0
M
n
n
Thus, choosing M min
Tog(ioo]
1/k
.(2)
1/R
1/k
yields that
log(1/0)
1-1/k
VVog(1/0)
1-1/
iin M(P) S0
+ +a 1a1-1/k +
eV
Hence, when n 2 log(1/00 we have
((Viee)
1-1/k
Pnn - (P) =0
+ 2-11/h
EvT
Finally, combining the above two cases, that when log(1/8), for any 1, it suffices to
choose M = min (1) 1/k
(Vioeti/o)
evm
and obtain that
(oog(1/0)
1-1/k
(llo(L/8)
Pin - m(P)
+ 1-1k 1/k
which finishes the proof for the CTL setting.
G Proof of the Upper Bound for the C-LDP-C Setting
After the proofs for the previous two settings, setting. For completeness, we also provide detailed proof. To elucidate the utility of our approach, will structure the proof into four distinct steps, building upon the derivation outlined previously.
easily establish the upper bound for the C-LDP-
X,
Corruption
Y
Trunc M) Y,
Random Rounding Y!
Random Response
Z
Corruption
Z
Trunc. (M of+11
Zi
Sample Mean
pin.
Step 1: Bound the distance E [Y,]] Rinl- According to the analysis in the LTC setting, we can directly derive
17
EY| =
7, E[Y]]
M e +1
M e +1 c -
log (1/5)
S 2a
6 - +0
w.p.
5
Step 2: Bound the distance 1 Y, Σ, E Yi]
ト Σ Y 0
log log(110) 1/8)
M v
w.p. 1-6
71
T1
n
where it simply follows from Hoeffding's s inequality.
Step 3: Bound the distance 1/4 Σ Y, - E [X,]] J.
From the analysis the CTL setting, we once again derive
1 Σ 72. [E(M]
Σ Y -
(1 s M) JX, (IX S M)
[[X
M)
+40M
n iE[n]
Ti
33

---

Step 4: Put everything together.
Case (i): for any k (1,2), & [0, 1), any d (0, and any P E Pk. have with probability
least 1 6,
M log(1/0)
M log(110) 0
Iin M(P) 50 O(aM) 0 aM
+ +0
MK-I
n
log( ())( M
++0
n
Thus, choosing M min
(
1/k
(+)
1/k
Ev
1/4
yields that
Vlog(1/5)
(10g(1100)
1-1/k
Vlog(1/8)
1-1/1
Pnn - M(P)
1-111/+ +
72
E
EV
Hence, when 2 log((/8), we have
1-1/k
iin ((P) SO
EVT
+ (
Case (ii): for any & 2 2, E E [0, 1). any 6 E (0, and any P E Pk. we have with probability at least 1 8,
log(1/6)
M log(1/))
1
inn [(P) S0
+0
+0
M
aM
.
log (1/()
+ +(aM)) + 0
+
Thus, choosing M min {
(mail)))) ) 1/2 (a) (2)
1/k
cvn
yields that
(lo(11/5)
log(1/0)
log(1 (1/()
1-1/k
(Vlo((1/8)
1-1/K
Phn ((()) 50
+
- 1-1k/ +
Evn
Hence, when n 2 log(1/8), we have
1-1/k
Pin m(P)
+
a 10)1-1/6
evn.
Finally, combining the above two cases, we see that when n 2 log(1/6), for any 1, it suffices to choose M min
1/k
(2)
eva
and obtain that
Voogl1/0)
((Veegt/6)
1-1/k
Pn, x(P)
+ + (-)1-1/6
eVT
34

---

H Proof of Proposition
Proof. As in the section for mean estimation, first focus on the LTC setting and divide the lower bound proof into two steps.
Step I: Without corruption. In this case, we aim to establish the second term in the lower bound. We consider the first MAB instance I as follows. Let y > be determined later and
Pi 1/7) = n Pi(X = 0) = - 1/2
Pa(x 1/7) 1/4-7", Pa(x Pa
114--144-9 1/4-7". Va 1.
Thus, one can see that 7 MAB(k) for a proper choice y and arm the optimal arm for instance J. We let M, be the induced marginal distribution of Pa via any E-LDP channel and E, [-] denote the expectation over Pı, which is over the randomness in the marginal distributions {Ma Jaejk] and policy
Then, construct "coupled" instance I' of follows. Let argmin E, (T)), i.e. the arm between 02 and ag that has the minimum number of pulls under instance J. Define the second instance I' that only differs in the distribution for arm compared to instance
P.(X 1/7) 3/4. P2 0) = 1
(8)
Thus, I' E (A and arm i the optimal arm for instance I'. By definition, we also have E, (T)( S TT(K 1).
For any instance I and policy n, we let Rr (x,, I) be its corresponding expected regret. Then, by standard argument and noting that the mean gap is A 1/4 /-11, have
R1 (x, I) + Rr(x,
2
(Pr N1 (T) - 7/2| + By (T) 2 T/2))
2
(a) TA
cxp(- KL (Pyl Pr.)
4
(0) TA
exp( B, [N:(T) KL. (M M))
(c) TA
exp(- [N:(T) 4(c- -12 (TV (P,, P())
(4) TA
T
4(c-- - -TV P!))3
exp
4
--1
(c) TA
T
A(e- 1)2 222
exp
K-1
where (a) holds by Bretagnolle-Huun Huber inequality; (b) follows from chain rule of KL divergence; (c) holds by Theorem I in Duchi al. (2018); (d) is true since E, [N.(T) < T/(K 1); (c) holds by
definition of TV distance.
Thus, putting everything together and noting that for E
E - - 2s, yields that [0, 11,
TA
T2222 2
Rr( [T, 1') 2
exp
-4
4
K-1
Thus, suppose T > K/E² and choosing 7 (K/(s one can check that all the required conditions on y are satisfied and we finally have that max max(Rr I), (T(,,I'))) 2 Ω (Th
Ω
T
26
Step Corruption part. this case, we aim to establish the first term in the lower bound.
This part basically shares the same argument as before for mean estimation. Note that the only difference between I and I' is the distribution for arm i. Then, apply the same argument as in the proof of Proposition to P; and P/. Hence, we have that there exists Huber corruptions so that one cannot distinguish between P; and P/, and hence I and I'. As result, the total expected regret is Ω (T1 ((T(a//)1-114)
Finally, for the CTI. setting, the first step is the same and second step only differs in that there no "contraction" effect in the proof of Proposition I.
35

---

I Proof of Proposition 4
Proof. Let us start with the LTC case. We divide the set of all sub-optimal arms G into two groups 91 and G2 = \ 91, where 91 {a E [K] \ : d (g) 1-1/k
< [ for some universal constant
chosen later. Hence, 9 {a [K] a² d' (2) 1/k z 2/ A... which implies that the total
expected regret from suboptimal arms in 9 is upper bounded by (+) 1-1/k). Thus, remains
bound the total expected regret of pulling suboptimal arms 91. To this end, for each G1, aim to show that
log (A,))
log
([N(TT)
SO
Let us first assume (9) holds and see how we can arrive at our claimed upper bound. By the definition of expected regret, we have
R(K, Σ (N)
+ Σ A. (M.)
E
IEG2
AE(NT)) T (T))) 1-1/K
Σ IEG1
where inequality holds by the definition of G2. It remains to translate the first term into a problem- independent one. To this end, we further divide the arms in G1 into two groups: one group consists of all arms that satisfy A, < for some constant 17 > 0 and another one contains all arms that satisfy A; 2 1). Thus, by (9), we have
log T
log T
Σ (T) S 1TT +0 E
E2n
8-1
I+1
k-1 24
Choosing =
K log 7
yields that the total expected regret satisfies
R(k,E,a,T) 5o
((K) log T
T + + T 1 1-1/K
K Klog T
(2)
10)1-1/
E2
Finally, for very small a, one can replace it with its upper bound optimize the regret.
remains to establish (9). First note that Oloo T //) basically follows from the burn-in period. Thus, only need to bound the total number of pulls after the burn-in period. We denote by (t) the total number of by time after the burn-in period, i.e., is equal to N&(t) minus the total number of burn-in plays of arm i. In the following, we will show that
log T
E [[) S Ci
+ +
(10)
c²(A,)
=
for some constants C₁ and Cz.
To this end, for that is after the burn-in period of arm i E G1, if az then one of the following must be true:
(11)
1-1/k
(
1-1/k
1
log(14)
P..N,0) > ((P.) +
+
(12)
N₂(t)
log
NE() C
(13)
82 (A, F.
36

---

This is because if all three are not true, then we have
UCB (t) > (Pao.)
= (P.)) +A;
(
(P)) + +
1
+c
a
1-1/k
1-1/k
( (M) +
1
log(t=)
1-1/k
+ c
<
(t(
1-1/k
(9) 2 (M())) 2c
log(14)
1-1/k
( Ni(t)
+ ee
1-1/k
(4)
llg((!)
1-1/k
2 (L.N.))) +c
+c
E Nc(t)
(C)
where (a) holds by the fact that E G1; (b) holds by choosing large constant (13); (c) true
since N.(1)= > N)(1): (d) holds by the inverse direction of (12) and choosing c' d 2c.
Let be the time just after the burn-in period, then we have
SC log
[[((T)) =E
1 1)
+
Σ
[1 = i and (13) is false)]
8²(A,)
T
12
120
(a)
log T
C
Σ 12!
((((()) true or (12) is true)]
3 (A:)
where (a) holds by the above claim, i.e., if a and (13) is false, then one of (11) and (12) must be true. Then, by our mean concentration result and union bounds, we can upper bound the second term above as
1 8
2 f
E ((I1) is true or (12) is true)] <
8=1
Putting them together, we have established (10), hence the result. The proof for CTL setting is essentially the same with the only difference in the definition of Gi and G2.
J Proof of Proposition 5
Proof. Without corruption. We consider two instances in MAB(8*,R, k)). In particular, we consider two-arm MABs and 7':
For I of : 1/2 11 := (ppp 1/4. = 1/2 7/- k-1 11 = (Pp)) = 3/4 7
For 1' 14 == :
(14)
These distributions can be constructed in the same way as in the proof of Proposition 3 (cf. (7)). Moreover, for the behavior policy т, we have (22) 1/5* and (1) - 1/33. We now verify that both (TT, µ²) and (T, μu²) are in MA k)). By construction, each distribution is belonging to Pk. It remains to verify that 1/m(a*) < 3* For I'. we have 1/x(2) 3 And for 1, we have 11m(1)= = 1/(1 - 1/3*) S f when 3 2 2.
Now, we proceed to apply classic Le Cam's 's method. Let loss/sub- losiisub-ottimalltyy of any final chosen arm a E {1, 2} under I and I' be E(O; I), {(ā; I'). Then, by our construction, we have
{(o; I) + ((a; I') 2 1/4. x-
37

---

Thus, by Le Cam's 's method and Bretagnolle- Huber inequality, we have
k-1 exp - KT. Mill My
SubOpt" (8", ,,,,,,,,,,,, N)
16
where KL MMll A= is the private KL divergence between two MAB instances, By chain rule of KL divergence and Theorem I in Duchi et al. (2018), we have
KL [ M f 3
N 4(ee 1)² (TV (Pt, (P). Ps
Thus, noting that for E [0, 1), of - -15 22 and (TV
P3 Ps )
_
have that
SubOpt" (8", e, N) 2 xkー1
N2
exp
16
4
Finally, for a large enough N, choosing 7 = (8" /0:p/(=2)))))) (2))))
yields that
1-1/
3+
SubOpt" (,",,,,,,,,) 20
E N
Corruption part. By our construction (ef. (14) (7), (8) we have that TV (P., = -/2 Then, similar idea as in the proof of Proposition 1 applies here. That is, for the LTC setting, by the contraction of LDP, we can set 7f ) so that TV (M4. My S a. Thus, one cannot distinguish / and I' under HuHueer model. Thus, one has to incur sub-optimality gap 9(7*)
(g) 1=11 In contrast, due to no contraction by LDP first, one can only set 7 O(a), which leads to the final result.
K Proof of Proposition 6
Proof. We will focus on the LTC case, since the CTL case nearly the same with a minor change in the confidence bound. Let & = E n &g where
Σ = (Va E [K], (((a) r(a)l b(a))
& = (aa(') 2 2 NT(a')}
Let us first assume that P [ 2 1 28 and see how we can prove the final result. Then, we will establish this high-probon begh-probbbility event in the end. Hence, condition the event & and define LCB(a) = F(a) b(a). we have
r(a") r(ā) r(a") LCB(a") LCB(a") LCB(a) +CCB(a) r()) S 2b(a")
1-1/k
a
1-1/b
log(2K/5) Na.
< 20
+ +2c
E
N Then, by the bounded Then, by the definition of 8 and E, we can further lower bound N by 23 mean of each arm, and choosing 8 = 1/N, we have the claimed expected sub-optimality result.
remains to bound the probability of E. For &2, by standard Chernoff bound, we have P [[2] when N 2 8, log(1/5). For ε₁, we have the following argument. For any arm a such that N,, is larger than the burn-in threshold, the concentration in & follows from our hioh-rrobyyilityy mean estimation result. For all other arms, by construction and the condition that all arms have mean
6
between [-,, 1], have
F(a) - b(a) = -1 S r(a)) S F(aa) + b(a) = 1,
which enables us to establish our claim [
2 1 1 26.
38


Reviews:
[{"review_id": "6fKsMTFLOj", "reviewer": "Reviewer_1jNj", "summary": "This paper considers the heavy-tailed online and offline MAB problem with local differential privacy and Huber corruption, where the CTL, LTC, and C-LDP-C models are considered. By first providing tight high-probability concentration bounds for the mean-estimation problem under the CTL and LTC settings, the authors offer new upper bound results for online and offline MAB. Lower bound results are also established to demonstrate the tightness of the upper bound results.", "questions": "1.For the questions regarding the claim of the theorems, see Weakness 1 and 2.\n\n2.As discussed in C.3, authors states that the previous SOTA in the heavy-tailed LDP MAB paper [1] has a technical flaw. The authors have demonstrated this claim by showing that the upper bound result in [1] can even break the lower bound result proved in this paper. I am wondering, besides this evidence, can the authors explicitly point out any technical flaw in the proof of the result in [1]?\n\n[1] Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference on Artificial Intelligence and Statistics, pp. 1546–1574. PMLR, 2022.", "limitations": "N.A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The presentation of results in this paper is clear, and the comments are detailed. Related works are well discussed. Several novel results are established and well generalize the previous LDP heavy-tailed estimation results, including:\n\n1. New high-probability bounds for LDP heavy-tailed and corrupted mean estimation problems.\n\n2. An interesting separation result between the CTL and LTC settings, with detailed explanations.\n\n3. New results for offline and online MAB.", "weaknesses": "Several claims are not so clear to me and may need further explanation and clarification, including:\n\n1. In the regret bound for online MAB, it seems that the upper bound result in Proposition 4 cannot directly imply the result claimed in Theorem 2. I take the CTL result as an example, and the LTC result has the same problem:\nIn Theorem 2, the upper bound reads as $O(T({\\alpha}/\\varepsilon)^{1-1/k})$.\nIn Proposition 4, there is a factor $\\tilde{\\alpha} \\in [\\alpha, 1/2]$ that balances the trade-off $\\tilde{O}( T(\\tilde{\\alpha}/\\varepsilon)^{1-1/k} + 1/\\tilde{\\alpha})$. In particular, when $1/\\alpha > T({\\alpha}/\\varepsilon)^{1-1/k}$, it seems that Proposition 4 can no longer recover Theorem 2?\n\n2. In the offline MAB result, while authors claimed that the upper bound result almost matches the proposed lower bound, it seems that the dependency on $N$ is not optimal when comparing the lower bound term $\\sqrt{1/N}$ with the upper bound result $(1/N)^{1/2 - 1/2k}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your time and review. We will provide our response below. \n\n**Online MAB.** In this paper, as in previous work (e.g., Wu et al 2023), we treat $\\alpha$ as a constant (i.e., it does not scale with $T$). Thus, the third term in big-O of Proposition 4 is a lower order term as $T \\to \\infty$, which gives us Theorem 2.\n\n**Offline MAB.** There is a **typo** in Proposition 5, i.e., the exponent term of $1-1/k$ is missing. Our proof in Appendix J indeed has the right one, which matches the upper bound in Proposition 6. The updated lower bounds in Proposition 5 are shown below:\n\n(i) LTC: $\\mathrm{SubOpt}^{\\ast}_{\\mathrm{LTC}}(\\beta^{\\ast}, k, \\epsilon, \\alpha, N) \\geq \\Omega\\left(\\left(\\frac{\\alpha}{\\epsilon}\\right)^{1-1/k} + \\left(\\frac{1}{\\epsilon} \\sqrt{\\frac{\\beta^{\\ast}}{N}}\\right)^{1-1/k}\\right)$\n\n(ii) CTL: $\\mathrm{SubOpt}^{\\ast}_{\\mathrm{CTL}}(\\beta^{\\ast}, k, \\epsilon, \\alpha, N) \\geq \\Omega\\left(\\alpha^{1-1/k} + \\left(\\frac{1}{\\epsilon} \\sqrt{\\frac{\\beta^{\\ast}}{N}}\\right)^{1-1/k}\\right)$\n\n\n\n\n**Technical flaw in Tao et al. 2022.** Please see our general response above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iuN7ZfxCZ7", "reviewer": "Reviewer_5Gx9", "summary": "This paper studies multi-armed bandits where the feedback is a locally differentially private and corrupted version of the true rewards. The main message is that the order in which the rewards are (1) corrupted and (2) made private (i.e., (1) and then (2) or (2) and then (1)) changes the achievable regret rates, which they sharply characterize with new matching lower and upper bounds.", "questions": "Please see weaknesses above.", "limitations": "No broader impact concern.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* New and sharp regret upper and lower regret bounds for this locally private and corrupt bandit setting.\n* Tight characterization of private and corrupt mean estimation error.\n* There is expansive coverage of prior works on DP bandits, which helps place this contribution in context of the literature.", "weaknesses": "* I do think the writing is repetitive at times, and the paper could be better served by simplifying exposition and moving focus to key intuitions (for instance, Propositions 1 and 2 seem redundant given Theorem 1). Additionally, there are many settings and problems (LTC, CTL, C-LDP-C), online and offline MABs, so a summary table or glossary could be helpful to get the high level sense of the results.\n* It is a bit difficult to get the sense of novelties over prior works (Tao et al., 2022; Wu et al., 2023)). For instance, the local DP model is stronger than central DP, but what is the new technical difficulty handled in this setting? Also, there is not really much discussion of what the mistake of the previous state-of-art Tao et al., 2022 is other than that it contradicts the results of this submission. It would be easier for a quick reader to get a sense of confidence if the exact mistake in analysis could be elaborated. Because of the elaborate setting of this paper (i.e., local privacy, corruption, heavy-tail reward, ordering of corruption vs. privacy) and it seems various slices or weaker versions of this specifically arranged setting have been studied in other works, it's difficult to get a sense if the paper is not just a combinatorial composition of prior approaches for this setting or if some important technical obstacle was truly overcome to obtain the results.\n* Although I understand this is mostly a theory paper, I think it would also be good to have some practical discussion of when LTC or CTL might appear in application and what kind of implications the \"LTC is harder\" message has. Likewise, what are application scenarios for LTC or CTL?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for your time and review. Below is our response to the comments. \n\n**Presentation.** Thanks for the suggestion on the presentation. We will try to incoprate them in the final version, e.g., a summary table.\n\n**Practical scenarios of LTC and CTL** Yes, we have already briefly discussed them in Appendix C.1.\n\n**Important contributions compared to previous works.** Our result cannot be obtained by directly following previous works.\n\n1. Even without corruption, the state-of-the-art result is ungrounded. We discuss it further above (see the general response), which highlights the incorrect step in the upper bound proof of Tao et al. 2022. This complements the points we have made from the lower bound perspective.\n\n2. In contrast to Wu et al. 2023's setting of corruption plus central DP, where the standard Laplace mechanism will work, we have shown that the Laplace mechanism will only give a sub-optimal rate in the setting of local DP plus corruption. See Remark 4.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1oy6S0MtWS", "reviewer": "Reviewer_fKk6", "summary": "The study examines the interaction between local differential privacy (LDP) and robustness to Huber corruption and heavy-tailed rewards in multi-armed bandits (MABs). It focuses on two scenarios: LDP-then-Corruption (LTC) and Corruption-then-LDP (CTL). They provide a tight characterization of mean estimation error and minimax regret in both scenarios, supported by simulations. The findings indicate LTC results in worse performance than CTL. Additionally, the study offers the first performance bounds for scenarios with corruption both before and after LDP, and corrects previous errors in regret bounds for locally private, heavy-tailed online MABs", "questions": "Q1: You mention that the upper bound in Tao's paper is incorrect, can you further point out which step in their proof is wrong?\n\nQ2: What is the novelty of your mean estimation in Algorithm 1?", "limitations": "For online MAB, the paper just considers the UCB structure, maybe also consider the extension for Thompson Sampling will make the story more complete.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This model considering both local differential privacy (LDP) and robustness to Huber corruption is new and they provide a unified algorithm for online MAB with better minimax upper bound than previous works. They also propose the minimax lower bound for the first time.", "weaknesses": "The MAB algorithms still involve the hyper-parameter tuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Technical flaw in Tao et al. 2022.** Sure, we have provided a detailed discussion on it, which points out the incorrect step in their upper bound proof (see the above general response).\n\n**Novelty of Algorithm 1.** We remark on the novelty (or insight) of Algorithm 1 from the perspectives of algorithmic design and analysis, respectively.\n\n1. Algorithmic design: We use random response for privacy rather than the Laplace mechanism. This is due to the key observation that under corruption and LDP, the Laplace mechanism no longer gives the optimal rate, highlighting the interesting interplay of corruption and LDP.\n\n2. Analysis: One key novelty in our analysis is that Algorithm 1 can adaptively give optimal rates for all three different scenarios (LTC, CTL, and C-LDP-C) for bounded data.\n\n**Hyper-parameter tuning.** Yes, our MAB algorithms need to determine the optimistic or pessimistic radius, which requires us to know $\\epsilon$, $\\alpha$, $k$, and some constant $c$. We first note that even in non-private, non-corrupted cases, the radius also requires tuning with respect to $c$ in practical implementations. Regarding other parameters (in particular $\\alpha$), we tend to believe that it is necessary to be known in advance to guarantee optimal rates. Finally, to achieve the optimal rate in CTL, one has to carefully choose the right radius, while C-LDP-C (corruption-LDP-corruption) can be the same as LTC. \n\n\n**Other exploration strategies.** In this paper, we use UCB as an example. Since the key step in other variants (like Thompson sampling) also relies on a tight mean estimation, we believe one can generalize our results to other exploration strategies.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Technical flaw in Tao et al. 2022

We thank all the reviewers for their time and insightful comments. Since all reviewers would like to see more discussion of Tao et al. 2022's technical flaw from the perspective of upper bound proof, we will provide a general global response below.

The key flaw in their upper bound proof is **the incorrect bound on the number of pulls for each sub-optimal arm** (in the proof of their Lemma 13).

This step happens on Page 24 of their paper (see "Lastly, for any fixed sub-optimal arm a..."). It should be $\Delta_a \ge D_{\tau(a)}$, rather than $\Delta_a \ge D_{\tau(a)}^2$. After fixing this, one gets the correct bound on the number of pulls for each sub-optimal arm $a$ as (focus on key terms of $\epsilon$ and $\Delta_a$ only)
$${O}\left(\frac{1}{\epsilon^2 \Delta_a^{\frac{2(1+v)}{v}}}\right)$$, rather than the wrong one in their proof, which has $\Delta_a^{\frac{1+v}{v}}$ (i.e., missing the square).

In fact, translating this using our notation (i.e., $k = 1+v$), the correct bound above becomes $${O}\left(\frac{1}{\epsilon^2 \Delta_a^{\frac{2k}{k-1}}}\right)$$, which is exactly the first term in Eq. (9) of our paper.

Thus, following the same proof step in our paper (ignore all corruption terms), one can fix their proof and obtain the correct upper bound.

**Remark.** We remark that in Tao et al.  2022: (i) the authors did not provide detailed proof for the problem-independent (minimax) bound. They only provided the proof for the problem-dependent one (which is also ungrounded, as discussed above). Then, based on this, the authors claimed to obtain the problem-independent one (with standard techniques); (ii) Tao et al. 2022 follow an arm-elimination approach while our analysis is based on UCB. Nevertheless, it is well-known that in both approaches, the key step is to upper bound the number of pulls for each sub-optimal arm.

Meta-review: The paper provides novel characterization for local differential private and robust multi-armed bandits against Huber corruption. It also fixes a technical flaw in previous works.  All reviewers agree that the paper is interesting and makes descent contribution to the field.
Decision: Accept (poster)