On Private and Robust Bandits
Authors: Yulian Wu
Xingyu Zhou
Youming Tao
Di Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Bandits
privacy
robustness

Abstract: We study private and robust multi-armed bandits (MABs), where the agent receives Huber's contaminated heavy-tailed rewards and meanwhile needs to ensure differential privacy. We consider both the finite $k$-th raw moment and the finite $k$-th central moment settings for heavy-tailed rewards distributions with $k\ge 2$. We first present its minimax lower bound, characterizing the information-theoretic limit of regret with respect to privacy budget, contamination level, and heavy-tailedness. Then, we propose a meta-algorithm that builds on a private and robust mean estimation sub-routine \texttt{PRM} that essentially relies on reward truncation and the Laplace mechanism.  For the above two different heavy-tailed settings, we give corresponding schemes of \texttt{PRM}, which enable us to achieve nearly-optimal regrets.  Moreover, our two proposed truncation-based or histogram-based \texttt{PRM} schemes achieve the optimal trade-off between estimation accuracy, privacy and robustness. Finally, we support our theoretical results and show the effectiveness of our algorithms with experimental studies.

On Private and Robust Bandits
Yulian Wu" KAUST yulian. wwwkaust. edu..eeeu....... sa
Xingyu Zhou" Wayne State University xingyu. www.wuhyno.ueeeeooooooo. edu
Youming Tao
Di Wang KAUST
Shandong University
ym. tao99email. sdu. edu,
di wang@kasst eeu.auuuttuuu...e.
Abstract
We study private and robust multi-armed bandits (MABs), where the agent receives Huber's contaminated heavy-tailed rewards and meanwhile needs to ensure dif- ferential privacy. We consider both the finite k-th raw moment and the finite k-th central moment settings for heavy-tailed rewards distributions with A: > 2. We first present its minimax lower bound, characterizing the information-theoretiee limit of regret with respect to privacy budget, contamination level, and heavy- tailedness. Then, we propose a meta-algorithm that builds on private and robust mean estimation sub-routine PRM that essentially relies on reward truncation and the Laplace mechanism. For the above two different heavy-tailed settings, we give corresponding schemes of PRM, which enable us to achieve nearly-optimal histogram-ban PRM
regrets. Moreover, two proposed truncation-brr schemes achieve the optimal trade-off between estimation accuracy, privacy and robustness. Finally, we support theoretical results and show the effectiveness our algorithms with experimental studies.
Introduction
The multi-armed bandit (MAB) [1] problem provides a fundamental framework for sequential decision-makin under uncertainty with bandit feedback, which has drawn wide range of appli- cations in medicine [2], finance [3, 4], recommendation system [5], and online advertising [6], to name few. Consider portfolio selection in finance
example. At each decision round E [T]. the learning agent selects an action a, E [K] (i.e., a choice of assets to user t) and receives a reward r, (c.g., the corresponding payoff) that is i..d. drawn from unknown probability distribution associated with the portfolio choice. The goal is to learn to maximize its cumulative payoff.
In practice, applying the celebrated MAB formulation to real-life applications (e.g., the above finance example) needs to deal with both robustness and privacy issues. On the one hand, it is known that financial data is often heavy-tailed (rather than sub-Gaussian) [7, 8]. Moreover, the received payoff' data in finance often contains outliess [9] due to data contamination. On the other hand, privacy concern in finance is growing [10-12]. For instance, even if the adversary does not have direct access to the dataset, they are still able to reconstruct other customers' personal information by interacting with the pricing platform and observing its decisions [13].
Motivated by this, line of work on MABs has focused on designing robust algorithms with respect to
heavy-tailed rewards [14], adversary contamination [15, 16), both [17]. Another line of recent work has studied privacy protection MABs via different trust models of differential privacy (DP) [18]
such central DP [19, 20], local DP [21, 22] and distributed DP [23, 24]. Moreover, there have also
Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

been recent advances in understanding the close relationship between robustness and privacy for the mean estimation problem (e.g., robustness induces privacy [25, 26] and vice versa [27]). In light of this, fundamental question we are interested in this paper is:
Is there simple algorithm that can tackle privacy and robusiness in MABs simultaneously?
Our contributions. We give an affirmative answer to it by showing that unified truncation- based algorithm could achieve nearly optimal trade-off between regret, privacy, and robustness for MABs under two different heavy-tailed settings. The key intuition is that reward truncation not only helps to reduce outliers (due to both heavy tails and contamination), but also bound its sensitivity (useful for DP guarantees). To make our intuition rigorous, we take the following principled approaches.
(i) We first establish the minimax regret lower bound for private and robust MABs, i.e. heavy-tailed MABs with both privacy constraints and Huber's 's contamination (see section 4) where the reward distribution of each action has finite k-th moment for & 2 2. This characterizes the information- theoretic limit of regret with respect to privacy budget, contamination level and heavy-tailednnss.
(ii) To match the lower bound, we first propose meta-algorithn (see section 5), which builds upon the idea of batched successive elimination and relies on a generic private and robust mean estimation sub-routine denoted by PRM. Then, for two different settings of (heavy-tailed) reward distributions (i.e., finite raw or central moments), we propose corresponding schemes for the sub-routine PRM, both of which require truncation and the Laplace mechanism to guarantee robustness and privacy, simultaneously. Armed with these, our meta-algorithm can enjoy nearly matching regret upper bounds (see section 6). Experimental studies also corroborate our theoretical results.
(iii) Along the way, several results could be of independent interest. In particular, our proposed PRM shows that reward truncation is sufficient to help achieve the optimal high-probability concentration for private and robust mean estimation in the one-dimension case. Moreover, without contamination, our regret upper bounds not only match the optimal one for private heavy-tailed MABs with finite raw moments, but also provide the first results for the case with finite central moments, hence a complete study for private bandits as well.
Due to space limit, experiments (section A in Appendix), technical lemmas, and all proofs are relegated to Appendix.
2 Related Work
Robust MABs. The studies on robust bandits can be largely categorized into two groups. The first group of work mainly focuses on the setting where the total contamination is bounded, i.e., the cumulative difference between observed reward and true reward bounded by some constant [15]. The second group considers Huber's a-contamination model [28] (which is also the focus of our paper) or a similar a-fraction model. In these cases, the reward for each round can be contaminated by an arbitrary distribution with probability E 1/2) [29, 16, 30], or at most a-fraction of the rewards are arbitrarily contaminated [31]. The existing work in this group has mainly focused on the light-tailed setting where the true inlier distribution is Gaussian or sub-Gaussia and uses robust median or trimmed-mean estimator. A very recent work [17] studies the (non-private setting where the inlier distribution only has finite variance and uses Huber's ' estimator establish problem- dependent bounds. In contrast, we take the perspective of minimax regret, i.e., bounds, and also account for privacy protection.
Private MA In addition to the above mentioned results on private MABs with light-tailed rewards, [22] studies private heavy-tailed MABs with finite raw moments under both central and local models of DP. However, how to design private algorithms for heavy-tailed distributions with finite central moments is left as important problem. In this paper, resolve the problem byproduct of our main results.
Robust and private mean estimation. Our work is also related to robust and private mean estimation, especially the one dimensional case. On the robustness side with Huber's model, a concentration bound for the median of Gaussian (hence the mean by symmetry) is first established in [32]. Recently, [30] gives a high probability mean concentration via trimmed-mean estimator for general sub-Gaussian inlier distributions while [33] focuses on the heavy-tailed setting. We refer the reader to the survey paper [34] on high- high-dimensional robust statisties focusing on robust mean estimation. On the robustness side with heavy-tail, we refer the reader to the survey paper
2

---

[35] for mean estimation and regression under heavy-tailed distributions. Besides median-of-man meamns techniques and trimmed mean we mentioned above to handle heavy-tailed data, Catoni's estimator is very different estimator for heavy tail [36, 37] and also used in bandits [14]. On the privacy side, one close work [38], which presents the first high-probabilityy mean concentration for private heavy-tailed distributions with finite central moments (via a medians-of-medt
approach). It is worth noting that there are recent exciting advances in understanding the close relationship between robustness and privacy (e.g., robustness induces privacy [25, 26] and vice versa [27]). From this aspect, our results imply that for the one-dimensional mean estimation problem, truncation alone suffices to help to achieve both.
Concurrent and independent work. While preparing this submission, we have noticed that [39] also studies private and robust bandits problems under the Huber model. However, there are many differences between our work and theirs. First, for the differential privacy and bandit models, we investigate the multi-armed bandit problem under central differential privacy while they study stochastic linear bandits under the local differential privacy model. For the assumption of rewards, we focus the heavy-tailed cases where the distribution of reward has finite k-th raw moment and central moment for & 2 2 while they essentially assume that the rewards are bounded".
3 Preliminaries
In this section, we first formally introduce our problem of private and robust MABs and subsequently present its corresponding regret notions.
3.1 Private and Robust MABs
In this paper, we consider the multi-armed bandits problem where the agent interacts with the environment for 7 rounds. In each round f, the agent chooses an action E [K] and then standard reward r, is generated independently from inlier distribution. After contamination, the agent observes contaminated reward Iz.
As mentioned before, by robustness, we aim to handle both reward contamination and possible heavy- tailed inlier distributions. To this end, we first introduce the following two classes of heavy-tailed reward distributions.
Definition 3.1 (Finite k-th raw moment). A distribution over TR. is said have finite k-th raw moment if it is within
Pk = (P: Ex-P [|x]]] S1}. k
where k is considered fixed but arbitrary.
Definition 3.2 (Finite k-th central moment [40, 38]). A distribution over TR. is said to have a finite k-th central moment if it is within
Ps = [P: [X- -111 $1}, k: 122
where μ = [X= E I- D] and D21. 1.
The relationship between the finite raw moment and the finite central moment has been discussed in [22]. We further consider the celebrated Huber contamination model [28] in heavy-tailed MABs.
Definition 3.3 (Heavy-tailed MABs with Huber contamination). Given the corruption level a E
[0, 1/2). For each round & [T]. the observed reward Ia for action as is sampled independently from the true distribution Pa, E Pa (or Pa, E PE)) with probability - o; otherwise is sampled from some arbitrary and unknown contamination distribution Ga, E G.
In addition to robustness, we also consider the privacy protection in MABs via the lens of DP. In particular, we consider the standard central model of DP for MABs (e.g.. [41]), where the learning agent has access to users' raw data (i.e., rewards) and guarantees that its output (i.e., sequence
Note that although the general problem formulation [39] considers sub- Gaussian rewards, their privacy guarantce only holds for bounded rewards.
Herr use z; in the contaminated case distinguish with standard reward
3

---

of actions) are indistinguishable in probability on two neighboring reward sequences. Due to contamination, the reward data accessed by the learning agent at round could have already been contaminated. More precisely, we let Dr (I1,... ,T)) ) E TR." be a reward sequence generated in the learning process and M(Dr) = (tt....,ar)) E [K] to denote the sequence of actions recommended by learning algorithm MM. With this setup, we have the following formal definition. Definition 3.4 (Differential Privacy for MABs). For any > O, a learning algorithm M R²" + [K]" is DP for all sequences DT D/- E R² differing only in single element and for all events E C [K] we have
PP (IM(Dr) E ((M())) E
In other words, we protect the privacy of any individual user who interacts with the learning agent in the sense that an adversary observing the output of the learning agent (i.e., a sequence of actions) cannot infer too much about whether any particular individual has participated in this process, or the specific reward feedback of this individual. In this paper, we will leverage the well-known Laplace mechanism to guarantee differential privacy.
Definition 3.5 (Laplace Mechanism). Given a function f X" Rd, the Laplacian mechanism is given by
ML (.)= f(D,) + (V1, "2, YYa),
where Y, i.i.d. drawn from a Laplacian Distribution Lap( -ا(ا)) where A (f) the l--enniitivity of the function f. i.e., A A1(f) supD.>Dy llf ((D)))li Then, for any >> 0, Laplacian mechanism satisfies e-DP.
In the following sections, for brevity, we will simply use private and robust MABs to refer to our setting, i.e., heavy-tailed MABs with Huber contamination and privacy constraints.
3.2 Regrets for Private and Robust MABs
In the contamination case, the standard regret using observed (contaminated) rewards (ejr is ill-defined [31]. Instead, the literature focuses on the clean regret, that is, to compete with the best policy in hindsight as measured by the expected true uncontaminated rewards [31, 17, 42]. Hence, let Na be the mean of the inlier distribution of arm a E [K] and μ = max Pa. We also let IIf be the set of all c-DP MAB algorithms and Ea be the of all instances heavy-tailed MABs (with parameter k) with Huber contamination (of level a)).
Definition 3.6 (Clean Regret). Fix an algorithm ग E II and an instance v E Ea Then, the clean regret of π under v is given by Rr(T,v) == (T,"(Tp" - Mar).
Note that here the expectation is taken the randomness generated by the contaminated environ- ment and e- DD MAB algorithm while the means are of the true inlier distributions.
To capture the intrinsic difficulty of the private and robust MAB problem, minimax regret.
also interested in its
Definition 3.7 (Minimax Regret). The minimax regret of our private and robust MAB problem is defined as Riinimax : inf supweE.. E [Tp" El=
4 Lower Bound
We start with the following lower bound on the minimax regret, which characterizes the fundamental impact of privacy budget (via c), contamination level (via a) and heavy-tailedness of rewards (via k) in the regret. Note that this lower bound is mainly established under Definition 3.1, which in turn also serves one valid lower bound for the central moment case in Definition 3.2.
Theorem 4.1. Consider private and robust MAB problem where inlier distributions have finite k-th raw (or central) moments (k 2 2). Then, its minimax regret satisifes
Ruminimar S (VKT + (K/e)* k Ta²
'For parameter X, the Laplacian distribution has the density function Lap(X)(x) 2X exp(-111)

---

Algorithm Private and Robust Arm Elimination
Input: Number of arms K, time horizon T. privacy budget e, Huber parameter (0,
error probability 8 E (0, 1J, inliner distribution parameters i.c., & and optional D.
2: Initialize: 7 active set of arms S [1, K}.
3: for batch r = 1, 2.2.... do
4: Set batch size B, 2
5: if B, < T then
6:
Randomly select an action a E [K]. 7: Play action for B, times.
8: else
9:
for each active arm S do for i from to B, do
10:
11:
Pull arm observe contaminated reward aç. If total number of pulls reaches T, exit. end for
12:
13:
14:
Set truncation threshold M,-
15:
Set additional parameters +
16:
Compute estimate jáa PRM -PM((=;)) Mr, $).
17:
end for
18:
Set confidence radius 3+.
19:
Let jmmax max,gs Ma-
20:
Remove all arms from s.t. Jmax Paa 28,.
21:
end if
end for
This lower bound basically takes maximum of three terms. The first term comes from the standard regret for Gaussian rewards, the second one captures the additional cost regret due to privacy and heavy-tailed rewards, and the last term indicates the additional cost regret due to contamination and heavy-tailed rewards. Note that, for a given k, the impact of privacy and contamination is separable. It would also be helpful to compare our lower bound with the related ones, discussed below.
Remark 4.2. First, when k = and a O, our lower bound recovers the state-of-te ofte-offthe-arl lower bound for private MABs with sub-Gaussian rewards [20]; Second, when there is no privacy protection, very recent work [17] establishes problem-dependee dependent regret lower bound for robust MABs while we are interested the
lower bound with further privacy protection.
Our Approach: A Meta-Algorithm
In this section, first introduce meta-algorithm for private and robust MABs, which not only allows us to tackle inlier distributions with bounded raw or central moments in a unified way, but also highlights the key component, i.e., private and robust mean estimation sub-routine building on the main idea of reward truncation.
Our meta-algorithm, at high level, can be viewed batched version of the celebrated successive arm elimination [43] along with private and robust mean estimation sub-routine PRM (see Algo- rithm l). That is, it divides the time horizon T into batches with exponentially increasing size and eliminates sub-optimal arms successively based on the mean estimate
PRM. More specifically, based on the batch size, it consists of two phases. That is, when the batch size is less than threshold T. simply recommends actions randomly (line 5-7) (more on this will be explained soon). Oth- erwise, for each active arm in batch it first prescribes to a batch of B, = 2 fresh new users (i.e., "doubling") and observes possibly contaminated rewards (line 8). Then, it calls the sub-routine PRM to compute private and robust mean estimate for each active arm (line 12). In particular, it only uses the rewards within the most recent batch (i.e., "forgetting") along with a proper reward truncation threshold M, Finally, it adopts the classic idea of arm elimination with proper choice of confidence radius 8, to remove sub-optimal arms with high confidence (line 18-20).
We now provide more intuitions behind our algorithm design by highlighting how its main components work in concert. First, the reason behind the first phase (i.e., B, S T)), named forced exploration, necessary it ensures that concentration is satisfied that the optimal arm will not be eliminated.
5

---

Algorithm 2 PRM for the finite raw moment case
Input: A collection of data {2i)i=1. truncation parameter M, additional parameters {e).
2: for i= 1,2,.... do
3: Truncate data T. 244 1 (1s:1sM)
4: end for
5: Return private estimate j7 Em= Rt + Lap (2M) Re
This is due to the fact that in the contamination case, a well-behaved concentration only kicks in when the number of samples is larger than a threshold. Thus, one cannot adopt arm elimination in this phase since it might eliminate the optimal arm. Note that, instead of our choice of random selection, one can also use other methods for the first phase (see Remark 5.1 below). Second, for the second phase, the idea of doubling batching and forgetting is the key to achieving privacy with a minimal amount of noise (hence better regret). This is because now any single reward feedback only impacts one computation of estimate. This is in sharp contrast to standard arm elimination (e.g., [43]) where each mean estimate is based on all samples so far (as no batching is used), and hence a single reward change could impact ((T") mean estimations". Third, the simple idea of reward truncation in PRM turns out to be extremely useful for both robustness and privacy. On the one hand, truncation helps to reduce the impact of outliers (due to both heavy tails and contamination); On the other hand, truncation also helps to bound the sensitivity, which is necessary for privacy. In fact, as we will show later, well-tuned truncation threshold enables to achieve a near-optimal trade-off between regret, privacy and robustness. Finally, in contrast to the first phase, we can now climinate sub-optimal arms with high confidence due to the high probability concentration of mean estimate when batch size is larger than T (more details will be given later for specific choices of PRM and hence the choice of T)).
We choose to use the successive elimination (SE) technique here because it suffices to enable us to achieve optimal order-wiss wise regret later. fact, once armed with our novel PRM module, one can also use other exploration strategies like UCB in [20]. One difference is that now instead of first pulling each arm once, it needs to pull each arm T times to ensure that concentration kicks later. This is in fact not surprising since the high-level. the analysis of SE and UCB is very similar, i... doubling (batching) and forgetting. We also note that instead of UCB, one can also adapt it to the Thompson sampling strategy, e.g., [45], with our PRM module. Again, the key idea is batching and forgetting.
The algorithmic choice of the first phase can be flexible. For example, instead of playing randomly selected action for the whole batch, one can choose to play randomly selected action for each round. Moreover, one can also choose to be greedy or probabilistically greedy with respect the mean estimate by PRK, which also only uses the rewards collected within the last batch for each arm. All of these choices have the same theoretical guarantees, though some will help to improve the empirical performance.
Remark 5.1.
We then present the following remark that places our meta-algorithm in the existing literature.
Remark 5.2 (Comparison with existing literature). For private MABs (without contamination), the state-of-the-art also builds upon the idea of batching and forgetting [ [19, 20, 24] to achieve optimal regret. For robust MABs (without privacy), existing works take different robust mean estimations. For example, both [31, 30] use trimmed mean estimator for nub-Gaussian inlier distributions while [17] adopts Huber's 's estimator to handle inlier distributions with only bounded variance. We are the first to study privacy and robustness simultaneously, via simple truncation baaodd estimator, which in turn reveals the close relationship between privacy and robustness in MABs. This complements the recent advances capturing the connection between these two in nhigh-dimensionl) statistics [25, 27].
6 Upper Bounds
In this section, we establish the regret upper bounds for two specific instantiations of our meta- algorithm one for the finite raw moment case and another for the finite central moment case. The results could match our lower bound up to a log factor on T, demonstrating their near-optimality.
One can use the tree-based mechanism [44] to reduce to Ollog I'). but it is still sub sub-optimal [19].

---

6.1 Finite Raw Moment Case
In this section, we will focus on private and robust MABs where the inlier distributions have finite k-th raw moment given by Definition 3.1. In particular, we first introduce the choice of PRM in this case (see Algorithm and establish its concentration property, which plays key role in our implementation of meta-algorithm.
The PRM in Algorithm 2 simply truncation-based Laplace mechanism. That is, it first truncates all the received data with the threshold M (line 3). Then, Laplace noise is added to the empirical mean preserve privacy (line 5). We highlight again that truncation here helps with both robustness (via removing outliers) and privacy (via bounding the sensitivity of empirical mean).
As in the standard algorithm design of MABs, the key is to utilize the concentration of the mean estimator. To this end, we first give the following high-proe probbabbbbblltt concentration result for the mean estimate returned by PRM in Algorithm 2.
Theorem 6.1 (Concentration of Mean Estimate). Given collection of Huberr-contaminated data {xi) where the inlier distribution satisfies Definition 3. I with mean p., let p be the mean estimate
by Algorithm 2. Then, for any privacy budgel > O and 5 E (0, 1), the following results hold:
Uncontaminated case. For a we have 1 14|= 1-
M log(1/6)
with
M
probability at least 1 Thus, choosing the truncation threshold M = θ (og(1/88)
yields
T - ml =0 log(1/8) + (og(1/6)
Contaminated case. For 0 < a S a1 E (0,1/2) and = 52 [og(11/6) we have the following
with probability at least - l7 1l =0
log(1/6)
M log(1/8) + M taMM) Therefore,
+))) vields 1/ -A| S 3. where , 01
-
choosing the truncation threshold M- = θ min
nH [og(1/0)
o (V 1og(1/5) (Vorr
[[g[[188)
ai 1-#
With the above result, several remarks are order. First, for the uncontaminated case, our concentra- tion result consists of the standard sub-Gaussian term and new one due to privacy and heavy-tailed data. It can be translated into a sample complexity bound, i.c., to guarantee I/ μ4| S r7 for any log(1/5)
E (0, 1), it requires the sample size to be 2 O (log(//)) + matches the lower bound for private heavy-tail mean estimation (cf. Theorem 7.2 in [46]). Second, for the contaminated case, has an additional bias term 1-1A-/ which also known to be optimal [47]. Thus, via truncation, the PRM given by Algorithm 2 achieves the optimal trade-off between accuracy, privacy and robustness, which in turn shows its potential to be integrated into our meta-al meta-algorine alorihhmm. Note that aj here is any upper bound (e.g., estimate) on the true contamination level a.
en = ) which is optimal since it
Now, based on the concentration result, we can set other missing parameters in our meta- algorithm accordingly. particular, we have the following theorem that states the specific instantiation along with its performance guarantees.
Theorem 6.2 (Performance Guarantees). Consider a private and robust MAB with inlier distributions satisfying Definition 3.1 and 0 < S E (0, 1/2). Let Algorithm be instantiated with Algorithm 2 and Mr. 3+ be given by Theorem 6. I with n replaced by By. Set 2 log(118) and 1/T. Then Algorithm is c-DP with its regret upper bound
RT 0
( (KKTToooT
(KlogT)
T
1-1
*
K log The Tk 1-t
on
The above theorem presents the first achievable regret guarantee for private and robust bandits. The first three terms match lower bound in Theorem 4.1 up to log factor. The last additive term is
7

---

Algorithm 3 PRM for the finite central moment case
1: Input: A collection of data {2i)i=1, truncation parameter M, additional parameters +
(er)). r R.
2: // First step: initial estimate
3: B, = [i.j + r).j J = ( - r...., r...
Eis [x)E + -Ta (
4: Compute private histogram using the first fold of data: pj
5: Get the initial estimate J = arg maxje5 Pj-
6: // Second step: final estimate
7: Get final estimator using the second fold of data: jt J n Eiintt - +
Lap 2M
mainly due to the fact that the mean concentration result only holds when the sample size is larger than T ( log(1/6)). As result, each sub-optimal has to be played at least 12( (oog(1/0)) times. However, for sufficiently large T and a constant the last term is dominated by other terms. The last term is also exactly the reason that we choose an upper bound a on the actual contamination level and state the upper bound results in terms of on rather than a That is, for very small but non-zero a one can choose a larger 01 to balance the regret. This subtle issue is also mentioned in one nice related work [42], see the remark after Theorem 7.4 and Remark 5.4 in their work.
on
01
Remark 6.3. For the uncontaminated case with a = O, using the uncontaminated concentration bound in Theorem 6.1 and the same analysis, we achieve regret upper bound O(vKT Tog K log T 1-1 Tt), which also matches the lower bound Theorem 4. 1 up to a factor of O T).
6.2 Finite Central Moment Case
The setting in the last section for the finite raw moment case may not be entirely satisfactory as essentially assumes that the mean of arms is bounded within a small range (hence the sub-optimal gaps). Thus, in this section, we turn to private and robust MABs where the inlier distributions have a finite k-th central moment as given by Definition 3.2 for reward distribution with large mean but small variability around the mean. To this end, we first need new PRM, since now simply truncating around zero as in Algorithm 2 will not work well (as discussed in detail in Remark 6.1...
Our new PRM presented in Algorithm which consists of two steps. The intuition is simple: the first step aims to have rough estimate of the mean, which is necessary since now the mean could be far away from zero. Then, in the second step, it truncates around the initial estimate to return the final result. More specifically, in the first step, we first construct bins over the range [-D, D), which is assumed contain the true mean by Definition 3.2. Then, we compute the private histogram via the Laplace mechanism. The initial estimate is given by the left endpoint of the bin that has the largest empirical mass. Next, in the second step. simply truncates around the initial estimate and again adds Laplace noise for privacy.
Remark 6.4. It is worth noting that similar idea of two-step estimation has been used previous work on robust mean estimation in the one- -imeeninnii heavy-tailed case [33, 38, 403. However, there are several differences in our algorithm design and analysis. In particular, while [33] considers mean estimation under Huber's 's model without privacy constraints, we further impose differential privacy requirements. As a result, the estimates for both two steps are in different forms in our case compared to [33], though they share the same high-level intuition. On the other hand, while [38] considers mean estimation under differential privacy, there is no consideration of Huber contamination as our case. Moreover, our second estimate is based on truncation while their method is via medians-of -ofounns----maass. In fact, as will be shown later (see Remark 6.7), when our result reduces to the uncontaminated case, achieves improvement over the one in [38]. Finally, [40] considers both Huber contanination and local differential privacy, and estublishes the corresponding mean square error (MSE). In contrast, we consider the central differential privacy and aim to establish high-probabie tail concentration. To this end, we take a different truncation method (i.e., using an indicator function in Line 7) compared to the one in [40] (Section 3.2 in its first arxiv version).
8

---

As before, we first present the concentration property of our new PRM, which will manifest in the specific instantiation of our meta-algorithm. In particular, we first give the following general theorem and then state two more detailed corollaries.
Theorem 6.5 (Concentration of Mean Estimate). Given collection of Huber-comtaminatter data ) where the inlier distribution satisfies Definition 3.2 with mean let gL be the mean estimate by Algorithm 3. For any a S 01 E (0, O ). e (0, 1] and (0, 1). there exist some constants ((1,,,,)), M and D 2 2r such that for all n 2 T(,,,,,,) with probability at least 1 - 6
(v
M log(1/6)
1 - -0=4s00
+ M taiM
n
ne
where O'max < 1/2 is the breakdown point.
The above theorem follows the same pattern as the one for the raw moment case (Theorem 6.1.. The key differences the threshold value T(a, e, 6) and the breakdown point Omaxx which are summarized in the following results.
Corollary 6.6 (Mean Concentration, 0). Let the same assumptions in Theorem 6.5 hold. For 1/k
The any E E (0, 1}, setting r = 10 and M = log(1/8)
then for all n 2 Q (log(D/0)/e)
and D 2 2r, we have that for any (0, 1), with probability at least 1 8, j pl S where
o
1og(1/82
[1o((1/6] ne
1-b
In other words, taking number of samples n such that
a
O
10g(1/6) 112
+
log(1/8) + log(D/8) we have iā - pl S 1) with probability at least 1 5.
Remark 6.7. The above lemma strictly improves the result in [38, Theorem 3.5 In particular,
uses the method of medians-of of-maans and achieves log D-log(1 for the third term. contrust, our third term is additive rather than multiplicative. fact, our concentration is optimal, which matches the lower bound for the miedimmesional case (see [46, Theorem 7.2]).
Corollary 6.8 (Mean Concentration, a 0). Let the same assumptions in Theorem 6.5 hold. For any e E (0, 1] and 0
01 E 0.133. we let / where 0.249-a and S (a1) -1/k()) Then, there exists constant et, for all n such that n 2 1/k
Th [og T (mmxx (108(1/6)
M- = @(min{
log( (/5) losl1/01 }) and D 2 2r, we have that for any (0, (0, with of
probability at least 8, 1i pl S 3 with 3= - +
(10s(1/6)
1-
1
+ tai
Remark 6.9. The above concentration has the same form as the one in Theorem 6.1. Specifically, for a large sample size n, it has the optimal concentration (for small a).. The threshold T on depends on both a, e now. We note that even for the sub- Gaussian inlier distributions without privacy protection, the existing concentration also has threshold T log[1/8) (see Lemma 4.1 in [30]). The finite central moment assumption will help us get logarithmic results for sample complexity on D of 2 Ω (log( D D/8)/e) which is better than the polynomial results on D from the finite raw moment. Actually, finding a private estimator that achieves an error on the logurithmic of the range of the parameter is significant in the topic of DP estimation (see [48-50] on the importance of the problem).
a
Now, are left to leverage the above two concentration results to design specific instantiations of our meta-algorithm and establish their performance guarantees. Our first instantiation is for the uncontaminated case, i.e., = 0. Therefore, robustness then only with respect to heavy-tailed rewards while privacy is still preserved.
Theorem 6.10 (Performance Guarantees, distributions satisfying Definition 3.2 and a = O. Let Algorithm be instantiated with Algorithm 3, and r, My, 3r be given by Corollary 6.6 with n replaced by B,. Set T 2 Jog(D/8) and = 1/T. Then, Algorithm I e-DP with its regret upper bound
0). Consider private and robust MAB with inlier
R₂ 0 ( KT (K log (c) + Th+4).
where y O (KD log (DT))).)
We also note that the main focus of [38] is not achieving the optimal estimate though.

---

Remark 6.11. To the best of our knowledge, this is the first result on private and heavy-tailed bandits with the finite central moment assumption. The state-of-the-ar art result only focuses on the simpler case, i.e. the finite raw moment assumption [22].
Finally, armed with Corollary 6.8, we have the second instantiation of our meta-algorithm that deals with the contaminated case.
Theorem 6.12 (Performance Guarantees, a > 0). Consider a private and robust MAB with inlier distributions satisfying Definition 3.2 and ar S on E (0,0. 0.13). Let Algorithu I be instantiated with Algorithm 3, and v. T, Mr. Br be given by Corollary 6.8 with n replaced by Br. Set 1/T, then Algorithm 1 is D-DP with its regret upper bound
Rx = 0
(V--VVTTooo Ko T +K T/c) + 1- ((*t
where 9 =
DK log T DKllg 1DK log
DK log(
and 0.249
1-a
af
Remark 6.13. The above upper bound also matches our lower bound up to log factor and O(4), which is dominated by other terms for a sufficiently large T and small D. A comparison between the results in Theorem 6.2 (Remark 6.3) and Theorem 6. 6.12 (Theorem 6. 10) for contaminated case (uncontaminatte case). respectively, allows first transform the central moment condition to the raw moment condition, and then simply apply Algorithms 1 and 2 get regret upper bound? This is because the central moment condition implies | = =OD*). By employing a simple scaling technique, Algorithms I and 2 would yield a regret bound of O(D. Reg), where Reg corresponds the bound stated in Theorem 6.2. Thus, significant contrast arises when comparing this result with Theorem 6. 12, where the dependence on D is only an additive linear term rather than a multiplicatiie factor of (D). Consequently, the bounds presented in Theorem 6. 6.12 and Theorem 6.10 prove to be substantially tighter when D assumes larger values, hence highlighting the contributions of our new PRM module in Algorithm 3.
address fundamental question: why do not
7 Simulations and Conclusion
We refer readers to Appendix A for our simulation results. In this paper, we investigated private and robust multi-armed bandits with heavy-tailed rewards under Huber's contamination model well as differential privacy constraints. We proposed a meta-algorithm that builds on a private and robust mean estimation sub-routine PRM for different heavy-tailed assumptions of rewards, i.e. finite k-th raw moment and finite k-th central moment with & 2 2. Moreover, we also established regret upper bounds for these algorithms, which nearly match our derived minimax lower bound.
There remain many open questions in this direction. First, the problem-dependent lower bound is unclear for private and robust bandits but some work has been done for corrupted heavy-tailed bandits (see Theorem in [17]). One interesting future direction is to study how to leverage both the insights in [17] and the lower bound under privacy to derive problem-dependent lower bound for private and robust bandits. Second, how to design algorithms and analyze the theoretical results for private and robust bandits under other corrupted models such as "bandits with total corruption budget" in [15]. Third, throughout the paper T is known in advance, and it remains to see how to handle the case where T unknown and infinity.
8 Acknowledgments
We thank Mengchu Li for the insightful discussions and for pointing out the first arxiv version of [40]. And we also thank the anonymous NeurIPS reviewers for their feedback. Xingyu Zhou is supported in part by NSF grant CNS-2153220. Di Wang and Yulian Wu were supported in part by the baseline funding from the CRG grand URF/1/4663-01- -0101, FCC/1/1976-49001
funding DASS///119-01--1 from CBRC of King Abdullah University of Science and Technology (KAUST). Di Wang was also supported by the funding of the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUS) AI)
10

---

References
[1] 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.
[2] Benjamín Gutiérrez, Loie Peter, Tassilo Klein, and Christian Wachinger. A mulli--rmed bandit to smartly select a training set from big medical data. In International Conference on Medical Image Computing and Computer-Assise Intervention, pages 38-45. Springer, 2017.
[3] Matthew Hoffman, Eric Brochu, Nando De Freitas, al. Portfolio allocation for bayesian optimization. In UAI, pages 327-336. Citeseer, 2011.
[4] Weiwei Shen, Jun Wang, Yu-Gang Jiang, and Hongyuan Zha. Portfolio choices with orthogonal bandit learning. In Twenty-fourth international joint conference on artificial intelligence, 2015.
[5] Stéphane Caron and Smriti Bhagat. Mixing bandits: A recipe for improved cold-start recom- mendations in a social network. In Proceedings of the 7th Workshop on Social Network Mining and Analysis, pages 1-9,20 2013.
[6] Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 36(4):500-522, 2017.
[7] Svetlozar Todorov Rachev. Handbook of heavy tailed distributions in finance: Handbooks in finance, Book 1. Elsevier, 2003.
[8] John Hull. Risk management financial institutions, + Web Site, volume 733. John Wiley & Sons, 2012.
[9] John Adams, Darren Hayunga, Sattar Mansi, David Reeb, and Vincenzo Verardi. Identifying and treating outliers in finance. Financial Management, 48(2):345 384, 2019.
[10] Yanzhe Murray Lei, Sentao Miao, and Ruslan Momot. Privacy-preserving personalized revenue management. HEC Paris Research Paper No. MOSI-2020-1391, 2020.
[11] Xi Chen, David Simchi-Levi, and Yining Wang. Privacy-preserving dynamic personalized pricing with demand learning. Management Science, 68(7):4878 4898, 2022.
[12] Xi Chen, Sentao Miao, and Yining Wang. Differential privacy in personalized pricing with nonparametric demand models. Operations Research, 2022.
[13] Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page, and Thomas Ristenpart. Privacy in pharmacogeneties: An (End-to-End) case study of personalized warfarin dosing. In 23rd USENIX Security Symposium (USENIX Security 14), pages 17-32, 2014.
[14] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59 397117777117771 2013.
[15] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 114-122, 2018.
[16] Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Cormuption-ollrrant bandit learning. Machine Learning, 108(4))687-715, 2019.
[17] Debabrota Basu, Odalric-Ambryy Maillard, and Timothée Mathieu. Bandits corrupted by na- ture: Lower bounds on regret and robust optimistic algorithm. arXiv preprint arXiv:2203.03/88 2022.
[18] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[19] Touqir Sajed and Or Sheffet. An optimal private stochastic-mab algorithm based on optimal private stopping rule. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 5579-5588, 2019.

---

[20] Achraf Azize and Debabrota Basu. When privacy meets partial information: A refined analysis of differentially private bandits. arXiv preprint arXiv:2209.02550, 2022.
[21] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff. Multi-armed bandits with local differential privacy. arXiv preprint arXiv:2007.03121, 2020.
[22] Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. arXiv preprint arXiv:2106.02575, 2021.
[23] 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.
[24] Sayak Ray Chowdhury and Xingyu Zhou, Distributed differential privacy in multi-armed bandits. arXiv preprint arXiv:2206.0577 2022.
[25] Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. arXiv preprint arXiv:2212.05015, 2022.
[26] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back.
arXiv preprint 2302:0230000 2023.
[27] Kristian Georgiev and Samuel B Hopkins. Privacy induces robustness: Informattion-computaiioon gaps and sparse mean estimation. arXiv preprint arXiv:2211.007744 2022.
[28] Peter Huber. Robust estimation of a location parameter. Ann. Math. Statist., 35(4):73-101, 1964.
[29] Pranjal Awasthi, Sreenivas Gollapudi, Kostas Kollias, and Apaar Sadhwani. Online learning under adversarial corruptions. 2020.
[30] 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 2021.
[31] Laura Niss and Ambuj Tewari. What you may not be what you get: Ucb bandit algorithms robust to s-contamination. In Conference on Uncertainty in Artificial Intelligence, pages 450-459. PMLR, 2020.
[32] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665-674. IEEE, 2016.
[33] Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A unified approach to robust mean estimation. arXiv preprint arXiv:1907.00927. 2019.
[34] Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint 191.001111.05911, 2019.
[35] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: survey, Foundations of Computational Muthematics, 1455)1145-1 2019.
[36] Olivier Catoni and llaria Giulini. Dimension-free pac-bayesian bounds for the estimation of the mean of random vector. arXiv preprint arXiv: 0430004 2018
[37] Sujay Bhatt, Guanhua Fang, Ping Li, and Gennady Samorodnitsky. Nearly optimal catoni's m-estimator for infinite variance. In International Conference on Machine Learning, pages 1925-1944. PMLR, 2022.
[38] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pages 2204-2235. PMLR, 2020.
[39] Vasieeoo Charisopoulos, Hossein Esfandiari, and Vahab Mirrokni. Robust and private stochastic linear bandits. 2023.
12

---

[40] Mengchu Li, Thomas B Berrett, and Yi Yu. On robustness and local differential privacy. arXiv preprint arXiv:2201.00751, 2022.
[41] Nikita Mishra and Abhradeep Thakurta. (Nearly) optimal differentially private stochastic multi- arm bandits. In Proceedings of the 31st Conference on Uncerlainty in Artificial Intelligence (UAI), pages 592-601, 2015.
[42] Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau. Online and distribution- robustmess: Regression and contextual bandits with huber contamination. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 684-695. IEEE, 2022.
[43] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(6), 2006.
[44] T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):1-24, 2011.
[45] Bingshan Hu and Nidhi Hegde. Near-optimal thompson sampling-bass bbsed algorithms for dif- ferentially private stochastic bandits. In Uncertainty in Artificial Intelligence, pages 844-80 -522. PMLR, 2022.
[46] Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via sum-of-squares exponential mechanism. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1406-1417, 2022.
[47] Ilias Diakonikolas. Algorithmic high-dimensional robust statistics. Webpage http://www. iliasdiakonikolas. org/simons-tuue cetpmooonn-uuooirrrooooooe html, 2018.
[48] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
[49] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint 1711v:1711.03900 2017.
[50] Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pages 10633-10660. PMLR, 2022.
[51] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 933-4)2211-07,, 2014.
[52] Joseph P Near and Chiké Abuah. Programming differential privacy. URL: https://uvm, 2021.
[53] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[54] 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-1960, 2018.
[55] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
13


Reviews:
[{"review_id": "NdyydddXyD", "reviewer": "Reviewer_xHN8", "summary": "The paper studies the private and robust multi-armed bandits, where the rewards are heavy-tailed or contaminated. It proposes a meta-algorithm which is based on private and robust mean esitmation sub-routine incorporating reward truncation and Laplace mechanism. ", "questions": "Overall, I think the paper is well organized and easy to follow. See questions in weakness part.", "limitations": "No.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper establish the minimax regret lower bound for private and robust MABs.\n\nIt proposes a meta-algorithm matching the lower bound.\n\nIt takes into account both reward contamination and heavy-tailed cases.\n\nThe analyses are relatively complete.", "weaknesses": "The current setting seems to require the horizon, T, to be known in advance. If T is unknown or infinity, how does it change the differential privacy definition and the technical difficulty. \n\nThe paper needs to include additional literature review about heavy-tailed cases, especially in the line of Catoni's estimator (with application in bandits). For example,\n\n1. Olivier Catoni. Challenging the empirical mean and empirical variance: a deviation study\n2. Gabor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey.\n3. Sujay Bhatt, Guanhua Fang, Ping Li, Gennady Samorodnitsky. Nearly Optimal Catoni’s M-estimator for Infinite Variance\n\nSome detailed explanations of differences between proposed method and DPRSE should be given.\n\nIn supplementary, it seems that Lemma B.2 is never used. According to the current algorithm, the pararell composition should be sufficient?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and comments. We are glad you find our analyses are relatively complete. We will recap your comments and present our detailed response. We hope our answers will resolve your concern.\n\n**Unkown and infinity horizon T**  \n- We first clarify when $T$ is unknown and infinity, the differential privacy definition is the same for differentially private online learning under the event-level privacy framework of [1]. The definition is the same under two cases also has been discussed in Section 2.2 of [2].\n- When $T$ is unknown and infinity, in fact, once armed with our novel PRM modules, one can also use other exploration strategies like UCB in [3] for anytime regret guarantee. One difference is that now instead of first pulling each arm once, it needs to pull each arm $\\mathcal{T}$ times to ensure that concentration kicks in later. This is in fact, not surprising since on the high level, the analysis of SE and UCB is very similar, i.e., doubling and forgetting.\n\n- We also note that instead of UCB, one can also adapt it to the Thompson sampling strategy, e.g., [4], with our PRM module. Again, the key idea is doubling and forgetting.\n\n\nWe will include the above discussion in the next version to highlight the flexibility of our PRM modules.\n\n[1] Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Differential privacy under continual observation. In Proceedings of\nthe forty-second ACM symposium on Theory of computing, pp. 715–724, 2010.\n\n[2] Hu, Bingshan, Zhiming Huang, and Nishant A. Mehta. \"Optimal algorithms for private online learning in a stochastic environment.\" arXiv preprint arXiv:2102.07929 (2021).\n\n[3] Azize, Achraf, and Debabrota Basu. \"When privacy meets partial information: A refined analysis of differentially private bandits.\" *Advances in Neural Information Processing Systems* 35 (2022): 32199-32210.\n\n[4] Hu, Bingshan, and Nidhi Hegde. \"Near-optimal Thompson sampling-based algorithms for differentially private stochastic bandits.\" In Uncertainty in Artificial Intelligence, pp. 844-852. PMLR, 2022.\n\n**Additional literature review about heavy-tailed cases** Thanks for pointing out these important and nice works. We will include them in the next version.\n\n**Difference between our proposed algorithms and DPRSE**\n- First, DPRSE in [5] is only designed for handling privacy and heavy-tailed rewards, i.e., no robustnees with respect to contamination. In contrast, our proposed algorithm can handle privacy, heavy-tailed rewards and Huber contamination altogether.\n- Second, even if one only considers privacy and heavy-tailed rewards, our algorithm can handle the important case where the central moment is bounded while DPRSE cannot. This is because DPRSE is desinged only for the finite raw moment case.  \n\n[5] Youming Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. arXiv preprint arXiv:2106.02575, 2021\n\n**Parallel composition** Yes, we didn't use Lemma B.2 and parallel composition is sufficient. Thanks for pointing out this and we will remove it in the next version.\n"}, {"review_id": "LN9a9HZwYz", "reviewer": "Reviewer_nGB6", "summary": "This work studies the specific setting of heavy-tailed bandits with Huber contamination and differential privacy constraints. They first give a regret lower bound, tightly characterizing the minimax rate in terms of all the parameters involved in this setting. Then, they provide matching (up to log terms) upper bounds. The crucial technical novelty is to use new concentration bounds they developed for private and robust estimation via truncation methods in bandits.", "questions": "See above.", "limitations": "No forseeable negative societal impacts.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "They derive the first minimax rates in this robust+private bandit setting and give matching upper bounds. The paper is also generally well-written and has many useful remarks comparing the results and techniques with previous works. The algorithmic ideas and intuition behind the new estimation scheme were easy to follow. ", "weaknesses": "* I think some discussion on problem-dependent rates in this setting would be interesting. The paper could at least comment on why their analyses don't extend easily to obtain problem-dependent rates or what the minimax problem-dependent rates might look like in terms of $\\epsilon, k,\\alpha$.\n* There are many recent works on \"bandits with total corruption budget\" (e.g., the cited paper Lykouris et al., 2018). It would be good to include some comparison with this setting, even if just in terms of experiments. For instance, the $T\\cdot \\alpha^{1-1/k}$ term in this paper's minimax regret rate seems to be similar to the additive corruption term sometimes seen in this other setting (Theorem 1; Gupta et al., COLT 2019). Can the analyses in this paper extend to this setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive evaluation of our paper! We would like to provide the following clarifications to the reviewer's questions. \n\n**Minimax vs. problem-dependent bound**  Thanks for your sharp comments. Let us approach your question in the following steps.\n\n- Problem-dependent upper bound:  Our current analysis can also yield problem-dependent upper bounds. In particular, by line 586-587, if $\\alpha \\leq c \\Delta_{\\min}$ (where $\\Delta_{\\min}$ is the minimal gap; $c$\n is some constant), then one can determine the number of pulls for each sub-optimal arm, hence a standard problem-dependent bound, which mimics the one established for the case of Gaussian inlier rewards [1].\n\n- Problem-dependent lower bound: it is unclear for private and robust bandits, but some work has been done for corrupted heavy-tailed bandits; see Theorem 1 in [2]. One interesting future direction is to study how to leverage both the insights in [2] and the lower bound under privacy to derive a problem-dependent lower bound for private and robust bandtis.\n\n[1] Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Corruption-tolerant bandit learning, Machine Learning 108.4 (2019): 687-715.\n\n[2] 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.03186,\n405 2022.\n\n**Comparision with \"bandits with total corruption budget\"**\n\n- First, we clarify that the \"bandits with total corruption budget\" and \"Huber contamination model\" is different in nature, as they are models for different contamination scenarios. This is also reflected in Section 3.4 of [1].\n\n-  At a high level, Algorithm 1 in [2] is similar to our meta-algorithm in the spirit of arm elimination, forgetting, and batching since both algorithms proceed in epochs that increase exponentially in length and only use the most recent epoch to calculate statistics. The difference is that Algorithm 1 in [2] chooses the arm with a probability at step 8 and never completely eliminates any arm, but our algorithm removes the arm based on the confidence radius.\n- One possible approach to further provide a privacy guarantee to Algorithm 1 in [2] is as follows: As in our paper,  one can also add some noise on the average of rewards at step 9. Then there should be an additional term related to noise in concentration inequality (1) in [2]. This approach is reasonable because Algorithm 1 in [2] also enjoys doubling and forgetting. We believe that one can use this approach to derive a private version regret guarantee of Algorithm 1 in [2].\n\n[1] Niss, Laura, and Ambuj Tewari. \"What You See May Not Be What You Get: UCB Bandit Algorithms Robust to $\\varepsilon $-Contamination.\" In Conference on Uncertainty in Artificial Intelligence, pp. 450-459. PMLR, 2020.\n\n[2] Gupta, Anupam, Tomer Koren, and Kunal Talwar. \"Better algorithms for stochastic bandits with adversarial corruptions.\" In Conference on Learning Theory, pp. 1562-1578. PMLR, 2019.\n"}, {"review_id": "7RZaWOT1CJ", "reviewer": "Reviewer_Ssa1", "summary": "The paper studies the MAB problem where the agent receives rewards that are both heavy tailed and contaminated according to Huber's process (provides true rewards w.p. $1-\\alpha$ and provides samples from an arbitrary, unknown distribution w.p. $\\alpha$). For the case of heavy-tailed rewards, both settings with finite $k$-th raw moment (the expected reward in a narrow range) and finite $k$-th central moment (expected deviation from the mean is in a relatively narrow range). The paper provides a regret lower bound for any algorithm in this setting, proposes a novel algorithms whose regret is analysed in both the finite $k$-th raw moment setting, as well as the finite central moment setting. Some experiments are provided in the Appendix though an existing algorithm, RUCB, appears to outperform the proposed algorithm.", "questions": "See Weaknesses.\n\nAlso am I reading the experimental results correctly when assessing that the RUCB algorithm outperforms the one proposed here? Can you find a problem instance where your algorithm performs best among the baselines?", "limitations": "I do not see any potential negative societal impact arising from this work.\n", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides both a regret lower bound as well as nearly matching upper bounds for the regret of their proposed algorithm.\n\nIf contamination is removed from the setting, the regret upper bounds provided here match the lower bounds for the bounded central moment setting, filling a gap in the existing study of private bandits.\n\nThe algorithms are accompanied by experiments showcasing their performance against other existing algorithms designed for similar (but not identical) settings.", "weaknesses": "Presentation is lacking in my opinion and I found the paper hard to follow. \n\nI am missing a thorough description of the problem statement describing the interaction between the agent and the environment in a self-contained, concise section. I found the quite hard to read as the setting isn't made explicit in a single place. I suggest this be done instead of the Preliminaries section (the definitions can be made in place as the need appears rather than having to keep track of them until they appear).\n\nI would have liked to see a more explicit description of how privacy ties into this setting: whose privacy are we aiming to defend here and from whom? A more clear description of the setting should also clarify this, in my opinion.\n\n I find it hard to argue for the significance of the results here meeting the conference standards as the setting feels a bit too narrow. I would have liked to see the synergy between the two aspects studied here better articulated: is the combination of privacy and heavy tailed rewards in bandit settings more difficult than the sum of its parts? What does their interplay look like?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the suggestions on the presentation. We will address them as follows.\n\n- **Description of the problem setting** We have stated the MAB protocol in the first paragraph of the introduction section. As suggested by the reviewer,  we will re-emphasize it in the preliminary part (Section 3.1) in the next version.\n\n- **Description of privacy protection** We have explained privacy protection in lines 112-118. We will add a more intuitive explanation in the next version as follows: In other words, we protect the privacy of any individual user who interacts with the learning agent in the sense that an adversary observing the output of the learning agent (i.e., a sequence of actions) cannot infer too much about whether any particular individual has participated in this process, or the specific reward feedback of this individual.\n\n**Interplay of different parts** We first clarify that privacy and heavy-tailed rewards are not just the sum of the two parts. Rather, it introduces several interesting interplays. In particular, due to heavy-tailed rewards, it becomes difficult to guarantee privacy as the sensitivity is not bounded anymore. Thus, one cannot directly apply standard DP mechanisms, which assume a bounded sensitivity. Instead, one needs to first carefully control the sensitivity in some way while not leading to too much increase in regret. To this end, we employ the truncation method with a careful choice of truncation threshold to balance between privacy and regret. In addition to the interplay of privacy and heavy-tailed rewards, we also considered robustness in terms of contamination. Interestingly, we showed that truncation method can handle all three of them in a principled way.\n\nGiven the recent popularity of research on privacy, heavy-tailed feedback, and robustness, we believe that our setting that studies the interplay of all three of them will have a broad audience. Practically speaking, our setting naturally covers many real-world scenarios. Theoretically speaking, our paper not only provides some useful tools for the field (e.g., optimal concentration result), but reflects the recent trends on the interplay of privacy and robustness [1]-[3].\n\n[1] Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. arXiv preprint arXiv:2212.05015, 2022.\n\n[2] Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. arXiv preprint arXiv:2302.01855, 2023.\n\n[3] Kristian Georgiev and Samuel B Hopkins. Privacy induces robustness: Information-computation gaps and sparse mean estimation. arXiv preprint arXiv:2211.00724, 2022.\n\n**Experimental results** We first clarify that we design the experiments by choosing DPRSE as the private bandit benchmark and RUCB as the robust bandit benchmark. RUCB is only a robust but not private algorithm and hence it's better than ours in terms of regret. Our algorithm not only handles robustness but also guarantees differential privacy, which naturally leads to a worse regret guarantee compared to RUCB."}, {"review_id": "SNdl0InuIC", "reviewer": "Reviewer_kQhg", "summary": "In this paper, the authors study private and robust multi-armed bandits (MABs), where the heavy-tailed rewards are contaminated. They first present its minimax lower bound, characterizing the information-theoretic limit of regret with respect to privacy budget, contamination level, and heavy-tailedness. Then, they propose a meta-algorithm that builds on a private and robust mean estimation sub-routine PRM which could achieve nearly-optimal regrets. Finally, the authors run simulations to support their theoretical results.", "questions": "Please refer to the weaknesses above.", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem of private and robust bandits is well-motivated.\n2. The upper bounds nearly match the lower bound, the paper is solid.\n3. The writing is very clear, I enjoy reading the paper.\n4. Connecting privacy with robustness using truncation is quite interesting.", "weaknesses": "My main question is about the last term in both Theorem 6.2 and Theorem 6.12. Intuitively, as the contamination converges to 0, the regret upper bound should be smaller, while the last term will converge to infinity. Could the authors discuss possible methods to get rid of the term or the difficulties?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive evaluation of our paper!\n\nYour observation is really sharp and points to a subtle part of Huber model.\n\nIn fact, your observation is exactly the reason that we choose an upper bound $\\alpha_1$ on the actual contamination level $\\alpha$ and state the upper bound results in terms of $\\alpha_1$ rather than $\\alpha$. That is, for a very small but non-zero $\\alpha$, one can choose a larger $\\alpha_1$ to balance the regret.\n\nThis subtle issue is also mentioned in one nice related work [1], see the remark after Theorem 7.4 and Remark 5.4.\n\n\n[1] Chen, Sitan, et al. \"Online and distribution-free robustness: Regression and contextual bandits with Huber contamination.\" 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022."}]

Author rebuttal:

Meta-review: The reviewers and myself have recognized that the many strong contributions of these papers qualify it to be accepted to Neurips 2023.

The paper is clear and well-written but one of the reviewers suggests that the discussion on the meaning of “privacy” in this paper should be added to the final version.
Decision: Accept (poster)