# On Private and Robust Bandits

Yulian Wu Xingyu Zhou 11footnotemark: 1 Youming Tao Di Wang Equal
contribution.King Abdullah University of Science and Technology, Thuwal, Saudi
Arabia. Email<EMAIL_ADDRESS>State University, Detroit, USA.
Email<EMAIL_ADDRESS>University, Qingdao, China. Email:
<EMAIL_ADDRESS>King Abdullah University of Science and Technology,
Thuwal, Saudi Arabia. Email<EMAIL_ADDRESS>
###### 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 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
PRM that essentially relies on reward truncation and the Laplace mechanism
only. For two different heavy-tailed settings, we give specific schemes of
PRM, which enable us to achieve nearly-optimal regret. As by-products of our
main results, we also give the first minimax lower bound for private heavy-
tailed MABs (i.e., without contamination). Moreover, our two proposed
truncation-based PRM achieve the optimal trade-off between estimation
accuracy, privacy and robustness. Finally, we support our theoretical results
with experimental studies.

###### Contents

  1. 1 Introduction
  2. 2 Related Work
  3. 3 Preliminary
    1. 3.1 Private and Robust MABs
    2. 3.2 Regrets for Private and Robust MABs
  4. 4 Lower Bound
  5. 5 Our Approach: A Meta-Algorithm
  6. 6 Upper Bounds
    1. 6.1 Finite Raw Moment Case
    2. 6.2 Finite Central Moment Case
  7. 7 Experiments
    1. 7.1 Experiment Setup
    2. 7.2 Results and Discussions
  8. 8 Conclusion
  9. 9 Acknowledgments
  10. A Useful Lemmas
  11. B Proofs of Section 4
  12. C Proofs of Section 6.1
  13. D Proofs of Section 6.2

##  1 Introduction

The multi-armed bandit (MAB) [BF85] problem provides a fundamental framework
for sequential decision-making under uncertainty with bandit feedback, which
has drawn a wide range of applications in medicine [GPKW17], finance [HBD+11,
SWJZ15], recommendation system [CB13], and online advertising [SBF17], to name
a few. Consider a portfolio selection in finance as an example. At each
decision round $t\in[T]$, the learning agent selects an action $a_{t}\in[K]$
(i.e., a particular choice of assets to user $t$) and receives a reward
$r_{t}$ (e.g., the corresponding payoff) that is i.i.d. drawn from an 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 finical data is often heavy-
tailed (rather than sub-Gaussian) [Rac03, Hul12]. Moreover, the received
payoff data in finance often contains outliers [AHMRV19] due to data
contamination. On the other hand, privacy concern in finance is growing
[LMM20, CSW22, CMW22]. 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 [FLJLPR14].

Motivated by this, a line of work on MABs has focused on designing robust
algorithms with respect to heavy-tailed rewards [BCL13], adversary
contamination [LMP18, KPK19], or both [BMM22]. Another line of recent work has
studied privacy protection in MABs via different trust models of differential
privacy (DP) such as central DP [SS19, AB22], local DP [RZLS20, TWZW21] and
distributed DP [TKMS21, CZ22]. Moreover, there have also been recent advances
in understanding the close relationship between robustness and privacy for the
mean estimation problem (e.g., robustness induces privacy [HKMN22] and vice
versa [GH22]). In light of this, a fundamental question we are interested in
this paper is:

_Is there a simple algorithm that can tackle privacy and robustness in MABs
simultaneously?_

Our contributions. We give an affirmative answer to it by showing that a
simple truncation-based algorithm could achieve a nearly optimal trade-off
between regret, privacy, and robustness for MABs. The key intuition is that
reward truncation not only helps to reduce outliers (due to both heavy tails
and contamination), but bound also its sensitivity, which is necessary for DP.
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
contamination [Hub64] (see section 4). This characterizes the information-
theoretic limit of regret with respect to privacy budget, contamination level
and heavy-tailedness. As a byproduct, our result also implies the first
minimax lower bound for private heavy-tailed MABs (i.e., without
contamination), hence resolving an open problem in [TWZW21].

(ii) To match the lower bound, we first propose a meta-algorithm (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 only 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 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.

Due to space limit, technical lemmas and all proofs are included in 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 is bounded by some constant [LMP18]. The second group
considers Huber’s $\alpha$-contamination model [Hub64] (which is also the
focus of our paper) or a similar $\alpha$-fraction model. In these cases, the
reward for each round can be contaminated by an arbitrary distribution with
probability $\alpha\in[0,1]$ [AGKS20, KPK19, MTCD21], or at most
$\alpha$-fraction of the rewards are arbitrarily contaminated [NT20]. The
existing work in this group has mainly focused on the light-tailed setting
where the true inlier distribution is Gaussian or sub-Gaussian and uses a
robust median or trimmed-mean estimator. A very recent work [BMM22] studies
the setting where the inlier distribution only has finite variance and uses
Huber’s estimator to establish problem-dependent bounds. In contrast, we take
the perspective of minimax regret, i.e., problem-independent bounds, and also
account for privacy.

Private MABs. In addition to the above mentioned results on private MABs with
light-tailed rewards, [TWZW21] study private heavy-tailed MABs with finite raw
moments under both central and local models of DP. However, the optimal
minimax regret for this case is still unknown and how to design private
algorithms for heavy-tailed distributions with finite _central_ moments is
unclear. In this paper, as byproducts of our main results, we resolve both
problems.

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 high-probability concentration bound for
the median of Gaussian (hence the mean by symmetry) is first established in
[LRV16]. Recently, [MTCD21] give a high probability mean concentration via a
trimmed-mean estimator for general sub-Gaussian inlier distributions while
[PBR19] focus on the heavy-tailed setting. On the privacy side, one close work
is [KSU20], which presents the first high-probability mean concentration for
private heavy-tailed distributions with finite central moments (via a medians-
of-means 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 [HKMN22] and vice versa [GH22]). From this aspect,
our results imply that for the one-dimensional mean estimation problem,
truncation alone suffices to help to achieve both.

##  3 Preliminary

In this section, we first formally introduce our private and robust MAB
problem and then present its regret notions.

###  3.1 Private and Robust MABs

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 $\mathbb{R}$ is said to have a finite $k$-th raw moment if
it is within

$\displaystyle\mathcal{P}_{k}=\left\\{P:\mathbb{E}_{X\sim
P}\left[|X|^{k}\right]\leqslant 1\right\\},\quad k\geq 2.$ (1)

######  Definition 3.2 (Finite $k$-th central moment).

A distribution over $\mathbb{R}$ is said to have a finite $k$-th central
moment if it is within

$\displaystyle{\mathcal{P}_{k}^{c}}=\left\\{P:\mathbb{E}_{X\sim
P}\left[|X-\mu|^{k}\right]\leqslant 1\right\\},\quad k\geq 2.$ (2)

where $\mu:=\mathbb{E}_{X\sim P}[X]\in[-D,D]$, i.e., $D$ is the finite range
of its mean but can be arbitrarily large.

We further consider the celebrated Huber contamination model [Hub64] and apply
it to heavy-tailed MABs.

######  Definition 3.3 (Heavy-tailed MABs with Huber contamination).

Given the corruption level $\alpha\in[0,1]$. For each round $t\in[T]$, the
observed reward111Here we use $x_{t}$ in the contaminated case to distinguish
with standard reward $r_{t}$.  $x_{t}$ for action $a_{t}$, is sampled
independently from the true distribution $P_{a_{t}}\in\mathcal{P}_{k}$ (or
$P_{a_{t}}\in\mathcal{P}_{k}^{c}$) with probability $1-\alpha$; otherwise is
sampled from some arbitrary and unknown contamination distribution
$G_{a_{t}}\in\mathcal{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., [MT15]), where the learning agent has access to users’ raw
data (i.e., rewards) and guarantees that its output (i.e., sequence of
actions) are indistinguishable in probability on two neighboring reward
sequences. Due to contamination, the reward data accessed by the learning
agent at round $t$ could have already been contaminated. More precisely, we
let $D_{T}=(x_{1},\ldots,x_{T})\in\mathbb{R}^{T}$ be a reward sequence
generated in the learning process and
$\mathcal{M}(D_{T})=(a_{1},\ldots,a_{T})\in[K]^{T}$ to denote the sequence of
all actions recommended by a learning algorithm $\mathcal{M}$. With this
setup, we have the following formal definition.

######  Definition 3.4 (Differential Privacy for MABs).

For any $\varepsilon>0$, a learning algorithm
$\mathcal{M}:\mathbb{R}^{T}\rightarrow[K]^{T}$ is $\varepsilon$-DP if for all
sequences $D_{T},D_{T}^{\prime}\in\mathbb{R}^{T}$ differing only in a single
element and for all events $E\subset[K]^{T}$, we have

$\displaystyle\mathbb{P}\left[\mathcal{M}{\left(D_{T}\right)\in
E}\right]\leqslant
e^{\varepsilon}\cdot\mathbb{P}\left[\mathcal{M}\left(D_{T}^{\prime}\right)\in
E\right].$

In this paper, we will leverage the well-known Laplace mechanism to guarantee
differential privacy.

######  Definition 3.5 (Laplace Mechanism).

Given a function $f:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$, the Laplacian
mechanism is given by

$\displaystyle\mathcal{M}_{L}(D,f,\varepsilon)=f(D)+(Y_{1},Y_{2},\cdots,Y_{d}),$

where $Y_{i}$ is i.i.d. drawn from a Laplacian Distribution222For a parameter
$\lambda$, the Laplacian distribution has the density function
$\text{Lap}(\lambda)(x)=\frac{1}{2\lambda}\exp(-\frac{|x|}{\lambda})$.
$\text{Lap}(\frac{\Delta_{1}(f)}{\varepsilon})$, where $\Delta_{1}(f)$ is the
$\ell_{1}$-sensitivity of the function $f$, i.e., $\Delta_{1}(f)=\sup_{D\sim
D^{\prime}}||f(D)-f(D^{\prime})||_{1}.$ Then, for any $\varepsilon>0$,
Laplacian mechanism satisfies $\varepsilon$-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 $\\{x_{t}\\}_{t\in[T]}$ is ill-defined [NT20]. 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 [NT20,
BMM22, CKMY22]. Hence, let $\mu_{a}$ be the mean of the inlier distribution of
arm $a\in[K]$ and $\mu^{*}=\max_{a\in[K]}\mu_{a}$. We also let
$\Pi^{\varepsilon}$ be the set of all $\varepsilon$-DP MAB algorithms and
$\mathcal{E}_{\alpha,k}$ be the set of all instances of heavy-tailed MABs with
Huber contamination.

######  Definition 3.6 (Clean Regret).

Fix an algorithm $\pi\in\Pi^{\varepsilon}$ and an instance
$\nu\in\mathcal{E}_{\alpha,k}$. Then, the clean regret of $\pi$ under $\nu$ is
given by

$\mathcal{R}_{T}(\pi,\nu):=\mathbb{E}_{\pi,\nu}[T\mu^{*}-\sum_{t=1}^{T}\mu_{a_{t}}].$

Note that here the expectation is taken over the randomness generated by the
_contaminated_ environment and $\varepsilon$-DP MAB algorithm while the means
are of the true inlier distributions.

To capture the intrinsic difficulty of the private and robust MAB problem, we
are also interested in its minimax regret.

######  Definition 3.7 (Minimax Regret).

The minimax regret of our private and robust MAB problem is defined as

$\mathcal{R}^{\text{minimax}}_{\varepsilon,\alpha,k}:=\inf_{\pi\in\Pi^{\varepsilon}}\sup_{\nu\in\mathcal{E}_{\alpha,k}}\mathbb{E}_{\pi,\nu}[T\mu^{*}-\sum_{t=1}^{T}\mu_{a_{t}}].$
(3)

##  4 Lower Bound

We start with the following lower bound on the minimax regret, which
characterizes the fundamental impact of privacy budget (via $\varepsilon$),
contamination level (via $\alpha$) and heavy-tailedness of rewards (via $k$)
in the regret.

######  Theorem 4.1.

Consider a private and robust MAB problem where inlier distributions have
finite $k$-th raw (or central) moments ($k\geq 2$). Then, its minimax regret
satisifes

$\displaystyle\mathcal{R}^{\text{minimax}}_{\varepsilon,\alpha,k}$
$\displaystyle=\Omega\left(\sqrt{KT}+\left(\frac{K}{\varepsilon}\right)^{1-\frac{1}{k}}T^{\frac{1}{k}}+T\alpha^{1-\frac{1}{k}}\right).$

Let us first present interpretations of the above result, which basically
takes a maximum of three terms. The first term comes from the standard regret
for Gaussian rewards, the second one captures the additional cost in regret
due to privacy and heavy-tailed rewards, and the last term indicates the
additional cost in 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 useful to compare our lower bound with the related ones,
which is the purpose of the following remark.

######  Remark 4.2.

First, when $k=\infty$ and $\alpha=0$, our lower bound recovers the state-of-
the-art lower bound for private MABs with sub-Gaussian rewards [AB22]; Second,
we note that even when $\alpha=0$, there is no existing result on minimax
regret (i.e., problem-independent) lower bound for private heavy-tailed MABs.
In fact, this is left as an open problem in a recent work [TWZW21]. Thus, our
lower bound not only resolves the problem333In [TWZW21], the authors consider
a slightly different setting where the heavy-tailed distribution only has a
finite $(1+v)$-th moment with $v\in(0,1]$. However, our result simply
generalizes to this setting by taking $k=1+v$., but also captures
contamination as well. Finally, when there is no privacy protection, a very
recent work [BMM22] establishes a _problem-dependent_ regret lower bound for
robust MABs while we are interested in problem-independent lower bound. Thus,
its results is incomparable to ours.

Now, it remains to see whether this lower bound can be achieved via certain
algorithms, which is the main focus of the following two sections.

##  5 Our Approach: A Meta-Algorithm

In this section, we first introduce a 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., a private and robust mean estimation sub-routine building on the simple
idea of truncation.

Our meta-algorithm, at a high level, can be viewed as a batched version of the
celebrated successive arm elimination [EMMM06] along with a private and robust
mean estimation sub-routine PRM (see Algorithm 1). 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 via PRM.
More specifically, based on the batch size, it consists of two phases. That
is, when the batch size is less than a threshold $\mathcal{T}$, it simply
recommends actions randomly (line 5-7) (more on this will be explained soon).
Otherwise, for each active arm $a$ in batch $\tau$, it first prescribes $a$ to
a batch of $B_{\tau}=2^{\tau}$ fresh _new_ users and observes possibly
contaminated rewards (line 8). Then, it calls the sub-routine PRM to compute a
private and robust mean estimate for each active arm $a$ (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_{\tau}$.
Finally, it adopts the classic idea of arm elimination with a proper choice of
confidence radius $\beta_{\tau}$ to remove sub-optimal arms with high
confidence (line 18-20).

Algorithm 1 Private and Robust Arm Elimination

1: Input: Number of arms $K$, time horizon $T$, privacy budget $\varepsilon$,
Huber parameter $\alpha\in(0,1]$, error probability $\delta\in(0,1]$, inliner
distribution parameters i.e., $k$ and optional $D$

2: Initialize: $\tau=0$, active set of arms $\mathcal{S}=\\{1,\cdots,K\\}$.

3: for batch $\tau=1,2,\dots$ do

4: Set batch size $B_{\tau}=2^{\tau}$

5: if $B_{\tau}<\mathcal{T}$ then

6: Randomly select an action $a\in[K]$

7: Play action $a$ for $B_{\tau}$ times

8: else

9: for each active arm $a\in\mathcal{S}$ do

10: for $i$ from $1$ to $B_{\tau}$ do

11: Pull arm $a$, observe contaminated reward $x_{i}^{a}$

12: If total number of pulls reaches $T$, exit

13: end for

14: Set truncation threshold $M_{\tau}$

15: Set additional parameters $\Phi$

16: Compute estimate
$\widetilde{\mu}_{a}=\texttt{PRM}(\\{x_{i}^{a}\\}_{i=1}^{B_{\tau}},M_{\tau},\Phi)$

17: end for

18: Set confidence radius $\beta_{\tau}$

19: Let $\widetilde{\mu}_{\rm max}=\max_{a\in\mathcal{S}}\widetilde{\mu}_{a}$

20: Remove all arms $a$ from $\mathcal{S}$ s.t. $\widetilde{\mu}_{\rm
max}-\widetilde{\mu}_{a}>2\beta_{\tau}$

21: end if

22: end for

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_{\tau}\leq\mathcal{T}$) is that the mean estimate by PRM does
not have a high probability concentration when the sample size is small. 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 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.,
[EMMM06]) where each mean estimate is based on all samples so far (as no
batching is used), and hence a single reward change could impact $O(T)$ mean
estimations444One can use tree-based algorithm [CSS11] to reduce it to $O(\log
T)$, but it is still sub-optimal [SS19].. _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, a well-tuned truncation threshold enables us to achieve
a near-optimal trade-off between regret, privacy and robustness. _Finally,_ in
contrast to the first phase, we can now eliminate sub-optimal arms with high
confidence due to the high probability concentration of mean estimate when
batch size is larger than $\mathcal{T}$ (more details will be given later for
specific choices of PRM and hence the choice of $\mathcal{T}$).

######  Remark 5.1.

The algorithm choice of the first phase can be flexible. For example, instead
of playing a randomly selected action for the whole batch, one can choose to
play a randomly selected action for each round. Moreover, one can also choose
to be greedy or probabilistically greedy with respect to the mean estimate by
PRM, 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.

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 [SS19, CZ22] to achieve optimal
regret. For robust MABs (without privacy), existing works take different
robust mean estimations. For example, both [NT20, MTCD21] use a trimmed mean
estimator for sub-Gaussian inlier distributions while [BMM22] adopts Huber’s
estimator to handle inlier distributions with only bounded variance. We are
the first to study privacy and robustness simultaneously, via a simple
truncation-based estimator, which in turn reveals the close relationship
between privacy and robustness in MABs. This complements the recent advances
in capturing the connection between these two in (high-dimensional) statistics
[HKMN22, GH22].

##  6 Upper Bounds

In this section, we establish the regret upper bounds for two specific
instantiations of our meta-algorithm, i.e., one for the finite raw moment case
and another for the finite central moment case. In particular, the results
could match our lower bound up to a logarithmic factor, demonstrating their
near-optimality.

Algorithm 2 PRM for the finite raw moment case

1: Input: A collection of data $\\{x_{i}\\}_{i=1}^{n}$, truncation parameter
$M$, additional parameters $\Phi=\\{\varepsilon\\}$

2: for $i=1,2,\dots,n$ do

3: Truncate data $\bar{x}_{i}=x_{i}\cdot\mathbbm{1}_{\\{|x_{i}|\leq M\\}}$

4: end for

5: Return private estimate
$\widetilde{\mu}=\frac{\sum_{i=1}^{n}\bar{x}_{i}}{n}+{\rm
Lap}(\frac{2M}{n\varepsilon})$

###  6.1 Finite Raw Moment Case

In this section, we will focus on private and robust MABs where the inlier
distributions have a finite $k$-th raw moment as given by Definition 3.1. In
particular, we first introduce the choice of PRM in this case (see Algorithm
2) and establish its concentration property, which plays a key role in our
implementation of meta-algorithm.

The PRM in Algorithm 2 is simply a 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 to 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-probability concentration result for the mean estimate returned by PRM in
Algorithm 2.

######  Theorem 6.1 (Concentration of Mean Estimate).

Given a collection of Huber-contaminated data $\\{x_{i}\\}_{i=1}^{n}$ where
the inlier distribution satisfies Definition 3.1 with mean $\mu$, let
$\widetilde{\mu}$ be the mean estimate by Algorithm 2. Then, for any privacy
budget $\varepsilon>0$ and $\delta\in(0,1)$, the following results hold:

Uncontaminated case. For $\alpha=0$, we have

$\displaystyle|\widetilde{\mu}-\mu|=O\left(\sqrt{\frac{\log(1/\delta)}{n}}+\frac{M\log(1/\delta)}{n\varepsilon}+\frac{1}{M^{k-1}}\right),$

with probability at least $1-\delta$. Thus, choosing the truncation threshold
$M=\Theta\left(\frac{n\varepsilon}{\log(1/\delta)}\right)^{\frac{1}{k}}$
yields

$\displaystyle|\widetilde{\mu}-\mu|=O\left(\sqrt{\frac{\log(1/\delta)}{n}}+\left(\frac{\log(1/\delta)}{n\varepsilon}\right)^{1-\frac{1}{k}}\right).$

Contaminated case. For $\alpha\in(0,1]$ and
$n=\Omega\left(\frac{\log(1/\delta)}{\alpha}\right)$, we have the following
with probability at least $1-\delta$

$\displaystyle|\widetilde{\mu}-\mu|\\!=\\!O\left(\sqrt{\frac{\log(1/\delta)}{n}}\\!+\\!\frac{M\log(1/\delta)}{n\varepsilon}\\!+\\!\frac{1}{M^{k-1}}\\!+\\!\alpha
M\right).$

Therefore, choosing the truncation threshold
$M=\Theta\left(\min\left\\{\left(\frac{n\varepsilon}{\log(1/\delta)}\right)^{\frac{1}{k}},\alpha^{-\frac{1}{k}}\right\\}\right)$,
yields $|\widetilde{\mu}-\mu|\leq\beta$, where

$\displaystyle\beta=O\left(\sqrt{\frac{\log(1/\delta)}{n}}+\left(\frac{\log(1/\delta)}{n\varepsilon}\right)^{1-\frac{1}{k}}+\alpha^{1-\frac{1}{k}}\right).$

With the above result, several remarks are ready. _First,_ for the
uncontaminated case, our concentration result consists of the standard sub-
Gaussian term and a new one due to privacy and heavy-tailed data. It can be
translated into a sample complexity bound, i.e., to guarantee
$|\widetilde{\mu}-\mu|\leq\eta$ for any $\eta\in(0,1)$, it requires the sample
size to be $n\geq
O(\frac{\log(1/\delta)}{\eta^{2}}+\frac{\log(1/\delta)}{\varepsilon\eta^{\frac{k}{k-1}}})$,
which is optimal since it matches the lower bound for private heavy-tail mean
estimation (cf. Theorem 7.2 in [HKM22]). _Second,_ for the contaminated case,
it has an additional bias term $O(\alpha^{1-1/k})$, which is also known to be
information theoretically optimal [Dia18]. 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-
algorithm.

Now, based on the concentration result, we can set other missing parameters in
our meta-algorithm accordingly. In 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 $\alpha\in(0,1]$. Let Algorithm 1 be instantiated with
Algorithm 2 and $M_{\tau}$, $\beta_{\tau}$ be given by Theorem 6.1 with $n$
replaced by $B_{\tau}$. Set
$\mathcal{T}=\Omega(\frac{\log(1/\delta)}{\alpha})$ and $\delta=1/T$. Then
Algorithm 1 is $\varepsilon$-DP with its regret upper bound

$\displaystyle\\!\\!O\left(\sqrt{KT\log T}\\!+\\!\left(\frac{K\log
T}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}\\!+\\!T\alpha^{1-\frac{1}{k}}\\!+\\!\frac{K\log
T}{\alpha}\right).$

The above theorem presents the first achievable regret guarantee for private
and robust bandits. The first three terms match our lower bound in Theorem 4.1
up to $\log T$ factor. The last additive term is mainly due to the fact that
the mean concentration result only holds when the sample size is larger than
$\mathcal{T}=\Omega(\frac{\log(1/\delta)}{\alpha})$. As a result, each sub-
optimal has to be played at least $\Omega(\frac{\log(1/\delta)}{\alpha})$
times. However, for a sufficiently large $T$ and a constant $\alpha$, the last
term is dominated by other terms.

######  Remark 6.3.

For the case when $\alpha=0$, using the uncontaminated concentration bound in
Theorem 6.1 and the same analysis, we achieve a regret upper bound
$O(\sqrt{KT\log T}\\!+\\!(\frac{K\log
T}{\varepsilon})^{\frac{k-1}{k}}T^{\frac{1}{k}}\\!)$, which also matches the
lower bound up to $\log T$ factor.

###  6.2 Finite Central Moment Case

The setting in the last section for the finite raw moment case may not be
entirely satisfactory as it 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. To this end,
we first need a new PRM, since now simply truncating around zero as in
Algorithm 2 will not work.

Algorithm 3 PRM for the finite central moment case

1: Input: A collection of data $\\{x_{i}\\}_{i=1}^{2n}$, truncation parameter
$M$, additional parameters $\Phi=\\{\varepsilon,D,r\\}$, $r\in\mathbb{R}$.

2: // First step: initial estimate

3: $B_{j}=[j,j+r),j\in\mathcal{J}=\\{-D,-D+r,\dots,D-r\\}$

4: Compute private histogram using the first fold of data:
$\widetilde{p}_{j}=\frac{\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}\in
B_{j}\\}}}{n}+\operatorname{Lap}\left(\frac{2}{n\varepsilon}\right)$

5: Get the initial estimate $J=\arg\max_{j\in\mathcal{J}}\widetilde{p}_{j}$

6: // Second step: final estimate

7: Get final estimator using the second fold of data:
$\widetilde{\mu}=J+\frac{1}{n}\sum_{i=n+1}^{2n}(X_{i}-J)\mathbbm{1}_{\\{|X_{i}-J|\leq
M\\}}+\operatorname{Lap}\left(\frac{2M}{n\varepsilon}\right)$

Our new PRM is presented in Algorithm 3, which consists of two steps. The
intuition is simple: the first step aims to have a 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 to 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, it simply truncates around the
initial estimate and again adds Laplace noise for privacy.

######  Remark 6.4.

It is worth noting that a similar idea of two-step estimation has been used in
previous work on robust mean estimation in the one-dimensional heavy-tailed
case [PBR19, KSU20, LBY22]. However, there are several differences in our
algorithm design and analysis. In particular, while [PBR19] considers mean
estimation under Huber’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 [PBR19], though they
share the same high-level intuition. On the other hand, while [KSU20]
considers mean estimation under differential privacy, there is no
consideration of Huber contamination as in our case. Moreover, our second
estimate is based on truncation while their method is via medians-of-means. In
fact, as will be shown later (see Remark 6.7), when our result reduces to the
uncontaminated case, it achieves improvement over the one in [KSU20]. Finally,
[LBY22]555In particular, we refer to the first arxiv version of [LBY22].
considers both Huber contamination and _local_ differential privacy, and
establishes the corresponding mean square error (MSE). In contrast, we
consider the _central_ differential privacy and aim to establish a high-
probability 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
[LBY22].

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 a collection of Huber-contaminated data $\\{x_{i}\\}_{i=1}^{2n}$ where
the inlier distribution satisfies Definition 3.2 with mean $\mu$, let
$\widetilde{\mu}$ be the mean estimate by Algorithm 3. For any
$\alpha\in(0,\alpha_{\max})$, $\varepsilon\in(0,1]$ and $\delta\in(0,1)$,
there exist some constants $\mathcal{T}(\alpha,\varepsilon,\delta)$, $r$, $M$
and $D\geq 2r$ such that for all
$n\geq\mathcal{T}(\alpha,\varepsilon,\delta)$, with probability at least
$1-\delta$

$\displaystyle\\!|\widetilde{\mu}-\mu|\\!\leq\\!O\left(\sqrt{\frac{\log(1/\delta)}{n}}\\!+\\!\frac{M\log(1/\delta)}{n\varepsilon}+\frac{1}{M^{k-1}}\\!+\\!\alpha
M\right),$

where $\alpha_{\max}<1$ 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 are the threshold value
$\mathcal{T}(\alpha,\varepsilon,\delta)$ and the breakdown point
$\alpha_{\max}$, which are summarized in the following results.

######  Corollary 6.6 (Mean Concentration, $\alpha=0$).

Let the same assumptions in Theorem 6.5 hold. For any $\varepsilon\in(0,1]$,
setting $r=10^{1/k}$ and
$M=\Theta\left(\frac{n\varepsilon}{\log(1/\delta)}\right)^{1/k}$, then for all
$n\geq\Omega\left(\log(D/\delta)/\varepsilon\right)$ and $D\geq 2r$, we have
that for any $\delta\in(0,1)$, with probability at least $1-\delta$,
$|\tilde{\mu}-\mu|\leq\beta$ where

$\displaystyle\beta=O\left(\sqrt{\frac{\log(1/\delta)}{n}}+\left(\frac{\log(1/\delta)}{n\varepsilon}\right)^{1-\frac{1}{k}}\right).$

In other words, taking number of samples $n$ such that

$\displaystyle n\geq
O\left(\frac{\log(1/\delta)}{\eta^{2}}+\frac{\log(1/\delta)}{\varepsilon\eta^{\frac{k}{k-1}}}+\frac{\log(D/\delta)}{\varepsilon}\right),$

we have $|\tilde{\mu}-\mu|\leq\eta$ with probability at least $1-\delta$.

######  Remark 6.7.

The above lemma strictly improves the result in [KSU20, Theorem 3.5]666We also
note that the main focus of [KSU20] is not on achieving the optimal estimate..
In particular, it uses the method of medians-of-means and achieves $\frac{\log
D\cdot\log(1/\delta)}{\varepsilon}$ for the third term. In contrast, our third
term is additive rather than multiplicative. In fact, our concentration is
optimal, which matches the lower bound for the one-dimensional case (see
[HKM22, Theorem 7.2]).

######  Corollary 6.8 (Mean Concentration, $\alpha>0$).

Let the same assumptions in Theorem 6.5 hold. For any $\varepsilon\in(0,1]$
and $\alpha\in(0,0.133)$, we let $r=\iota^{1/k}$ where
$\iota=\frac{1-\alpha}{0.249-\alpha}$ and
$M=\Theta(\min\\{\left(\frac{n\varepsilon}{\log(1/\delta)}\right)^{1/k},(\alpha)^{-1/k}\\})$.
Then, there exists constant $c_{1}$, for all $n$ such that
$n\geq\mathcal{T}=\Omega(\max\\{\frac{\iota\log(1/\delta)}{\varepsilon},\frac{c_{1}\log(D/\delta)}{\varepsilon},\frac{\log(1/\delta)}{\alpha^{2}}\\})$
and $D\geq 2r$, we have that for any $\delta\in(0,1)$, with probability at
least $1-\delta$, $|\widetilde{\mu}-\mu|\leq\beta$ with

$\displaystyle\beta=O\left(\sqrt{\frac{\log(1/\delta)}{n}}+\left(\frac{\log(1/\delta)}{n\varepsilon}\right)^{1-\frac{1}{k}}+\alpha^{1-\frac{1}{k}}\right).$

######  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 $\alpha$). The threshold $\mathcal{T}$ on $n$ depends on both
$\alpha,\varepsilon$ now. We note that even for the sub-Gaussian inlier
distributions without privacy protection, the existing concentration also has
a threshold $\mathcal{T}=\frac{\log(1/\delta)}{\alpha^{2}}$ (see Lemma 4.1 in
[MTCD21]).

Now, we 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., $\alpha=0$.
Therefore, robustness is then only with respect to heavy-tailed rewards while
privacy is still preserved.

######  Theorem 6.10 (Performance Guarantees, $\alpha=0$).

Consider a private and robust MAB with inlier distributions satisfying
Definition 3.1 and $\alpha=0$. Let Algorithm 1 be instantiated with Algorithm
3, and $r$, $M_{\tau}$, $\beta_{\tau}$ be given by Corollary 6.6 with $n$
replaced by $B_{\tau}$. Set
$\mathcal{T}=\Omega(\frac{\log(D/\delta)}{\varepsilon})$ and $\delta=1/T$.
Then, Algorithm 1 is $\varepsilon$-DP with its regret upper bound

$\displaystyle\\!\\!O\left(\sqrt{KT\log T}\\!+\\!\left(\frac{K\log
T}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}\\!+\\!\gamma\right),$

where $\gamma:=O\left(\frac{KD\log(DT)}{\varepsilon}\right)$.

######  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-art
result is only focused on the simpler case, i.e., the finite raw moment
assumption [TWZW21].

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, $\alpha>0$).

Consider a private and robust MAB with inlier distributions satisfying
Definition 3.1 and $\alpha\in(0,0.133)$. Let Algorithm 1 be instantiated with
Algorithm 3, and $r$, $\mathcal{T}$, $M_{\tau}$, $\beta_{\tau}$ be given by
Corollary 6.8 with $n$ replaced by $B_{\tau}$. Set $\delta=1/T$, then
Algorithm 1 is $\varepsilon$-DP with its regret upper bound

$\displaystyle\\!\\!O\left(\sqrt{KT\log T}\\!+\\!\left(\frac{K\log
T}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}\\!+\\!T\alpha^{1-\frac{1}{k}}\\!+\\!\widehat{\gamma}\right),$

where $\widehat{\gamma}:=O\left(\frac{DK\log T}{\alpha^{2}}+\frac{\iota DK\log
T}{\varepsilon}+\frac{DK\log(DT)}{\varepsilon}\right)$ and
$\iota=\frac{1-\alpha}{0.249-\alpha}$.

The above upper bound also matches our lower bound up to
$O(\widehat{\gamma})$, which is dominated by other terms for a sufficiently
large $T$ and constant $\alpha,D$.

##  7 Experiments

(a) Student’s $t$, $\alpha=5\%$, $\varepsilon=0.2$

(b) Student’s $t$, $\alpha=5\%$, $\varepsilon=0.5$

(c) Student’s $t$, $\alpha=5\%$, $\varepsilon=1.0$

(d) Pareto, $\alpha=2\%$, $\varepsilon=0.5$

(e) Pareto, $\alpha=5\%$, $\varepsilon=0.5$

(f) Pareto, $\alpha=10\%$, $\varepsilon=0.5$

Figure 1: Comparison of cumulative regret for PRAE-R, PRAE-C and DPRSE. Top:
Rewards generated from Student’s $t$-distribution with fixed Huber parameter
$\alpha=10\%$ and varying privacy budget $\varepsilon\in\\{0.2,0.5,1.0\\}$.
Bottom: Rewards generated from Pareto distribution with fixed privacy budget
$\varepsilon=1.0$ and varying Huber parameter $\alpha\in\\{2\%,5\%,10\%\\}$.

In this section, we will empirically evaluate the practical performance of our
private and robust arm elimination algorithms, which are abbreviated as PRAE-R
and PRAE-C when the sub-routine PRM is Algorithm 2 for the finite raw moment
case and Algorithm 3 for the finite central moment case, respectively. We
compare them with the DPRSE algorithm in [TWZW21], which achieves the optimal
regret bound for DP heavy-tailed MAB.

###  7.1 Experiment Setup

We consider the case where there are $K=5$ arms, and the mean of each arm is
within the range of $[0,100]$. Specifically, we let the arm means descend
linearly, i.e., for each arm $a\in[k]$, let
$\mu_{a}=100-\frac{100(a-1)}{K-1}$. We consider the following two types of
heavy-tailed distributions for the true inlier reward generation:

- Pareto distribution: For each pull of arm $a$, we generate a reward that is sampled from the distribution $\mu_{a}+\eta-2.5$, where $\eta\sim\frac{sx_{m}^{s}}{x^{s+1}}\mathbbm{1}_{\\{x\geq x_{m}\\}}$ for $x\in\mathbb{R}$ and we set the shape parameter $s=2.5$ and the scale parameter $x_{m}=1.5$.

- Student’s $t$-distribution: For each pull of arm $a$ we generate a reward that is sampled from the distribution $\mu_{a}+\eta$, where $\eta\sim\frac{\Gamma(\frac{\nu+1}{2})}{\sqrt{\nu\pi}\Gamma(\frac{\nu}{2})}\Big{(}1+\frac{x^{2}}{\nu}\Big{)}^{-\frac{\nu+1}{2}}$. Here we set the degree of freedom $\nu=2.5$. For both cases, the stochastic rewards have finite second central moment of $5$. The main difference between the above two types of distribution is that the Student’s $t$-distribution is symmetric while the Pareto distribution is one-sided. To generate contaminated rewards, we consider Gaussian distribution with zero mean and standard deviation of $50$.

For Student’s $t$-distribution case, we will fix the Huber parameter
$\alpha=5\%$ with different privacy budget $\varepsilon\in\\{0.2,0.5,1\\}$,
while for the Parote distribution case we fix $\varepsilon=0.5$ and vary the
corruption level $\alpha=\\{2\%,5\%,10\%\\}$. For each experiment, we repeat
30 times and set the total number of round $T=10^{5}$ (thus we set
$\delta=10^{-5}$). We will report the average of cumulative regrets
$\mathcal{R}_{T}$ with respect to the number of rounds.

###  7.2 Results and Discussions

We present our results in Figure 1. For all cases, PRAE-R and PRAE-C achieve
smaller cumulative regret and thus better expected performance than DPRSE.
More specifically, from Fig. 1(d)-1(f), we can see that, when the Huber
parameter $\alpha$ increases, DPRSE diverges to a larger regret, while PRAE-R
and PRAE-C are only limitedly affected. This is because DPRSE adopts more
aggressive truncation thresholds which incorporate more outliers. In contrast,
the truncation thresholds in PRAE-R and PRAE-C are delicately designed and
thus provide robustness against contaminated rewards. In addition, by
observing the error bars, we find all three methods are stable under both
symmetric and one-sided types of heavy-tailed distribution (see, e.g., Fig,
1(b) and 1(e)). Thus, we can conclude that our approaches PRAE-R and PRAE-C
outperform the baseline method DPRSE.

For both PRAE-R and PRAE-C, we can also observe that when $\varepsilon$ is
smaller or $\alpha$ is larger, the regret will increase for both types of
distributions, which is due to the fact that the regret bound is proportional
to $1/\varepsilon$ and $\alpha$ when $T$ is large enough. Moreover, compared
with PRAE-R, we can see the regret of PRAE-C is lower for all experiments.
This is due to the fact that the PRM subroutine for PRAE-C leverages the prior
information (i.e., range $D$) of mean for each arm, which could provide finer
performance bound for Algorithm 1. In total, all above results corroborate our
theories.

##  8 Conclusion

In this paper, we investigated private and robust multi-armed bandits with
heavy-tailed rewards under Huber’s contamination model as well as differential
privacy constraints. We proposed a meta-algorithm that builds on a private and
robust mean estimation sub-routine PRM. For two different heavy-tailed
settings, we provided specific schemes of PRM, both of which only rely on the
truncation and the Laplace mechanism. Moreover, we also established regret
upper bounds for these algorithms, which nearly match our derived minimax
lower bound. We also conducted experiments to support our theoretical
analysis.

##  9 Acknowledgments

YW and DW are supported in part by BAS/1/1689-01-01, URF/1/4663-01-01,
FCC/1/1976-49-01 of King Abdullah University of Science and Technology. XZ is
supported in part by NSF CNS-2153220. We thank Mengchu Li for the insightful
discussions and for pointing out the first arxiv version of [LBY22].

## References

  * [AB22] Achraf Azize and Debabrota Basu  “When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits”  In _arXiv preprint arXiv:2209.02570_ , 2022
  * [AGKS20] Pranjal Awasthi, Sreenivas Gollapudi, Kostas Kollias and Apaar Sadhwani  “Online learning under adversarial corruptions”, 2020
  * [AHMRV19] John Adams, Darren Hayunga, Sattar Mansi, David Reeb and Vincenzo Verardi  “Identifying and treating outliers in finance”  In _Financial Management_ 48.2 Wiley Online Library, 2019, pp. 345–384
  * [BCL13] Sébastien Bubeck, Nicolo Cesa-Bianchi and Gábor Lugosi  “Bandits with heavy tail”  In _IEEE Transactions on Information Theory_ 59.11 IEEE, 2013, pp. 7711–7717
  * [BF85] Donald A Berry and Bert Fristedt  “Bandit problems: sequential allocation of experiments (Monographs on statistics and applied probability)”  In _London: Chapman and Hall_ 5.71-87 Springer, 1985, pp. 7–7
  * [BMM22] Debabrota Basu, Odalric-Ambrym Maillard and Timothée Mathieu  “Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm”  In _arXiv preprint arXiv:2203.03186_ , 2022
  * [CB13] Stéphane Caron and Smriti Bhagat  “Mixing bandits: A recipe for improved cold-start recommendations in a social network”  In _Proceedings of the 7th Workshop on Social Network Mining and Analysis_ , 2013, pp. 1–9
  * [CGR18] Mengjie Chen, Chao Gao and Zhao Ren  “Robust covariance and scatter matrix estimation under Huber’s contamination model”  In _The Annals of Statistics_ 46.5 JSTOR, 2018, pp. 1932–1960
  * [CKMY22] Sitan Chen, Frederic Koehler, Ankur Moitra and Morris Yau  “Online and distribution-free robustness: Regression and contextual bandits with huber contamination”  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 684–695  IEEE
  * [CMW22] Xi Chen, Sentao Miao and Yining Wang  “Differential privacy in personalized pricing with nonparametric demand models”  In _Operations Research_ INFORMS, 2022
  * [CSS11] T-H Hubert Chan, Elaine Shi and Dawn Song  “Private and continual release of statistics”  In _ACM Transactions on Information and System Security (TISSEC)_ 14.3 ACM New York, NY, USA, 2011, pp. 1–24
  * [CSW22] Xi Chen, David Simchi-Levi and Yining Wang  “Privacy-preserving dynamic personalized pricing with demand learning”  In _Management Science_ 68.7 INFORMS, 2022, pp. 4878–4898
  * [CZ22] Sayak Ray Chowdhury and Xingyu Zhou  “Distributed Differential Privacy in Multi-Armed Bandits”  In _arXiv preprint arXiv:2206.05772_ , 2022
  * [Dia18] Ilias Diakonikolas  “Algorithmic high-dimensional robust statistics”  In _Webpage http://www. iliasdiakonikolas. org/simons-tutorial-robust. html_ , 2018
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith  “Calibrating noise to sensitivity in private data analysis”  In _Theory of cryptography conference_ , 2006, pp. 265–284  Springer
  * [DR+14] Cynthia Dwork and Aaron Roth  “The algorithmic foundations of differential privacy.”  In _Found. Trends Theor. Comput. Sci._ 9.3-4, 2014, pp. 211–407
  * [EMMM06] Eyal Even-Dar, Shie Mannor, Yishay Mansour and Sridhar Mahadevan  “Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems.”  In _Journal of Machine Learning Research_ 7.6, 2006
  * [FLJLPR14] Matthew Fredrikson, Eric Lantz, Somesh Jha, Simon Lin, David Page and Thomas Ristenpart  “Privacy in pharmacogenetics: An $\\{$End-to-End$\\}$ case study of personalized warfarin dosing”  In _23rd USENIX Security Symposium (USENIX Security 14)_ , 2014, pp. 17–32
  * [GH22] Kristian Georgiev and Samuel B Hopkins  “Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation”  In _arXiv preprint arXiv:2211.00724_ , 2022
  * [GPKW17] Benjamı́n Gutiérrez, Loı̈c Peter, Tassilo Klein and Christian Wachinger  “A multi-armed bandit to smartly select a training set from big medical data”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2017, pp. 38–45  Springer
  * [HBD+11] Matthew Hoffman, Eric Brochu and Nando De Freitas  “Portfolio Allocation for Bayesian Optimization.”  In _UAI_ , 2011, pp. 327–336  Citeseer
  * [HKM22] Samuel B Hopkins, Gautam Kamath and Mahbod Majid  “Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 1406–1417
  * [HKMN22] Samuel B Hopkins, Gautam Kamath, Mahbod Majid and Shyam Narayanan  “Robustness Implies Privacy in Statistical Estimation”  In _arXiv preprint arXiv:2212.05015_ , 2022
  * [Hub64] Peter J Huber  “Robust Estimation of a Location Parameter”  In _Ann. Math. Statist._ 35.4, 1964, pp. 73–101
  * [Hul12] John Hull  “Risk management and financial institutions,+ Web Site”  John Wiley & Sons, 2012
  * [KPK19] Sayash Kapoor, Kumar Kshitij Patel and Purushottam Kar  “Corruption-tolerant bandit learning”  In _Machine Learning_ 108.4 Springer, 2019, pp. 687–715
  * [KSU20] Gautam Kamath, Vikrant Singhal and Jonathan Ullman  “Private mean estimation of heavy-tailed distributions”  In _Conference on Learning Theory_ , 2020, pp. 2204–2235  PMLR
  * [KV17] Vishesh Karwa and Salil Vadhan  “Finite sample differentially private confidence intervals”  In _arXiv preprint arXiv:1711.03908_ , 2017
  * [LBY22] Mengchu Li, Thomas B Berrett and Yi Yu  “On robustness and local differential privacy”  In _arXiv preprint arXiv:2201.00751_ , 2022
  * [LMM20] Yanzhe Murray Lei, Sentao Miao and Ruslan Momot  “Privacy-preserving personalized revenue management”  In _HEC Paris Research Paper No. MOSI-2020-1391_ , 2020
  * [LMP18] Thodoris Lykouris, Vahab Mirrokni and Renato Paes Leme  “Stochastic bandits robust to adversarial corruptions”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , 2018, pp. 114–122
  * [LRV16] 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)_ , 2016, pp. 665–674  IEEE
  * [LS20] Tor Lattimore and Csaba Szepesvári  “Bandit algorithms”  Cambridge University Press, 2020
  * [MT15] Nikita Mishra and Abhradeep Thakurta  “(Nearly) optimal differentially private stochastic multi-arm bandits”  In _Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI)_ , 2015, pp. 592–601
  * [MTCD21] Arpan Mukherjee, Ali Tajer, Pin-Yu Chen and Payel Das  “Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 9651–9662
  * [NA21] Joseph P Near and Chiké Abuah  “Programming Differential Privacy”  In _URL: https://uvm_ , 2021
  * [NT20] Laura Niss 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_ , 2020, pp. 450–459  PMLR
  * [PBR19] Adarsh Prasad, Sivaraman Balakrishnan and Pradeep Ravikumar  “A unified approach to robust mean estimation”  In _arXiv preprint arXiv:1907.00927_ , 2019
  * [Rac03] Svetlozar Todorov Rachev  “Handbook of heavy tailed distributions in finance: Handbooks in finance, Book 1”  Elsevier, 2003
  * [RZLS20] Wenbo Ren, Xingyu Zhou, Jia Liu and Ness B Shroff  “Multi-armed bandits with local differential privacy”  In _arXiv preprint arXiv:2007.03121_ , 2020
  * [SBF17] Eric M Schwartz, Eric T Bradlow and Peter S Fader  “Customer acquisition via display advertising using multi-armed bandit experiments”  In _Marketing Science_ 36.4 INFORMS, 2017, pp. 500–522
  * [SS19] 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)_ , 2019, pp. 5579–5588
  * [SWJZ15] 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
  * [TKMS21] Jay Tenenbaum, Haim Kaplan, Yishay Mansour and Uri Stemmer  “Differentially private multi-armed bandits in the shuffle model”  In _Advances in Neural Information Processing Systems_ 34, 2021
  * [TWZW21] Youming Tao, Yulian Wu, Peng Zhao and Di Wang  “Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits”  In _arXiv preprint arXiv:2106.02575_ , 2021
  * [Ver18] Roman Vershynin  “High-dimensional probability: An introduction with applications in data science”  Cambridge university press, 2018

##  Appendix A Useful Lemmas

######  Lemma A.1 (Post-Processing [DR+14]).

Let $\mathcal{M}:\mathcal{X}\rightarrow\mathcal{Y}$ be a randomized algorithm
that is $(\varepsilon,\delta)$-differentially private. Let
$f:\mathcal{Y}\rightarrow\mathcal{Z}$ be an arbitrary randomize mapping. Then
$f\circ\mathcal{M}:\mathcal{X}\rightarrow\mathcal{Z}$ is
$(\varepsilon,\delta)$-differentially private.

######  Lemma A.2 (Composition Theorem [DR+14]).

Let $\mathcal{M}_{1},\mathcal{M}_{2},\dots,\mathcal{M}_{h}$ be a sequence of
randomized algorithms, where
$\mathcal{M}_{1}:\mathcal{X}^{n}\rightarrow\mathcal{Y}_{1}$,
$\mathcal{M}_{2}:\mathcal{Y}_{1}\times\mathcal{X}^{n}\rightarrow\mathcal{Y}_{2},\dots$,
$\mathcal{M}_{h}:\mathcal{Y}_{1}\times\mathcal{Y}_{2}\times\mathcal{Y}_{h-1}\times\mathcal{X}^{n}\rightarrow\mathcal{Y}_{h}$.
Suppose for every $i\in[h]$ and
$y_{1}\in\mathcal{Y}_{1},y_{2}\in\mathcal{Y}_{2},\dots,y_{h}\in\mathcal{Y}_{h}$,
we have
$\mathcal{M}_{i}(y_{1},\dots,y_{i-1},\cdot):\mathcal{X}^{n}\rightarrow\mathcal{Y}_{i}$
is $\varepsilon_{i}$-DP. Then the algorithm
$\mathcal{M}:\mathcal{X}^{n}\rightarrow\mathcal{Y}_{1}\times\mathcal{Y}_{2}\times\dots\mathcal{Y}_{h}$
that runs the algorithm $\mathcal{M}_{i}$ sequentially is $\varepsilon$-DP for
$\varepsilon=\sum_{i=1}^{h}\varepsilon_{i}$.

######  Lemma A.3 (Parallel Composition [NA21]).

Suppose there are $n$ $\varepsilon$-differentially private mechanisms
$\\{\mathcal{M}_{i}\\}_{i=1}^{n}$ and $n$ disjoint datasets denoted by
$\\{D_{i}\\}_{i=1}^{n}$. Then for the algorithm which applies each
$\mathcal{M}_{i}$ on the corresponding $D_{i}$, it is $\varepsilon$-DP.

######  Lemma A.4 (Markov’s inequality).

If $Y\in\mathbb{R}$ is a random variable and $a>0$, we have

$\mathbb{P}\left(|Y|\geqslant
a\right)\leqslant\frac{\mathbb{E}\left(|Y|^{k}\right)}{a^{k}}$

######  Lemma A.5 (Chebyshev’s inequality).

For a real-valued random variable $Y\in\mathbb{R}$, $a>0$ and
$k\in\mathbb{N}$, we have

$\mathbb{P}(|Y-\mathbb{E}Y|\geqslant
a)=\mathbb{P}\left(|Y-\mathbb{E}Y|^{k}\geqslant
a^{k}\right)\leqslant\frac{\mathbb{E}\left(|Y-\mathbb{E}Y|^{k}\right)}{a^{k}}$

######  Lemma A.6 (Tail Bound of Laplacian Vairable [DMNS06]).

If $X\sim{{\rm Lap}(b)}$, then

$\mathbb{P}(|X|\geq t\cdot b)=\exp(-t).$

######  Lemma A.7 (Hoeffding’s inequality).

Let $Z_{1},\dots,Z_{n}$ be independent bounded random variables with
$Z_{i}\in[a,b]$ for all $i$, where $-\infty<a<b<\infty$. Then

$\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(Z_{i}-\mathbb{E}\left[Z_{i}\right]\right)\right|\geqslant
t\right)\leqslant 2\exp\left(-\frac{2nt^{2}}{(b-a)^{2}}\right)$

######  Lemma A.8 (Hölder’s Inequality).

Let $X,Y$ be random variables over $\mathbb{R}$, and let $k>1$. Then,

$\mathbb{E}[|XY|]\leqslant\left(\mathbb{E}\left[|X|^{k}\right]\right)^{\frac{1}{k}}\left(\mathbb{E}\left[|Y|^{\frac{k}{k-1}}\right]\right)^{\frac{k-1}{k}}$

######  Lemma A.9 (Bernstein’s Inequality [Ver18]).

Let $X_{1},\cdots X_{n}$ be $n$ independent zero-mean random variables.
Suppose $|X_{i}|\leqslant M$ and $\mathbb{E}[X_{i}^{2}]\leq s$ for all $i$.
Then for any $t>0$, we have

$\mathbb{P}\left\\{\left|\frac{1}{n}\sum_{i=1}^{n}X_{i}\right|\geqslant
t\right\\}\leqslant
2\exp\left(-\frac{\frac{1}{2}t^{2}n}{s+\frac{1}{3}Mt}\right)$

##  Appendix B Proofs of Section 4

######  Lemma B.1 (Upper Bound on KL-divergence for Bandits with
$\varepsilon$-DP [AB22]).

If $\pi$ is a mechanism satisfying $\varepsilon$-DP, then for two instances
$\nu_{1}=(r_{a}:a\in[K])$ and $\nu_{2}=(r_{a}^{\prime}:a\in[K])$ we have

$\text{KL}\left(\mathbb{P}_{\pi,\nu_{1}}^{T}\|\mathbb{P}_{\pi,\nu_{2}}^{T}\right)\leq
6\varepsilon\mathbb{E}_{\pi,\nu_{1}}\left[\sum_{t=1}^{T}\text{TV}(r_{a_{t}}\|r^{\prime}_{a_{t}})\right]$

where $\text{TV}(r_{a}\|r^{\prime}_{a})$ is the total-variation distance
between $r_{a}$ and $r^{\prime}_{a}$.

######  Lemma B.2 (Theorem 5.1 in [CGR18]).

Let $R_{1}$ and $R_{2}$ be two distributions on $\mathcal{X}$. If for some
$\alpha\in[0,1]$, we have that $TV(R_{1},R_{1})=\frac{\alpha}{1-\alpha}$, then
there exists two distributions on the same probability space $G_{1}$ and
$G_{2}$ such that

$(1-\alpha)R_{1}+\alpha G_{1}=(1-\alpha)R_{2}+\alpha G_{2}.$

###### Proof of Theorem 4.1.

Let $\Pi$ be the set of all polices and $\Pi^{\varepsilon}$ be the set of all
$\varepsilon$-DP policies. We denote the environment corresponding to the set
of $K$-Gaussian reward distributions with means $\mu\in\mathbb{R}^{K}$ the
same variance $\sigma_{k}^{2}$ where the value of $\sigma_{k}$ is determined
by $k$ to make the $k$-th raw moments of the distributions are bounded by $1$
as
$\mathcal{E}_{\mathcal{N}}^{K}(\sigma_{k})\triangleq\left\\{\left(\mathcal{N}\left(\mu_{i},\sigma_{k}^{2}\right)\right)_{i=1}^{K}:\mu=\left(\mu_{1},\ldots,\mu_{K}\right)\in\mathbb{R}^{K}\right\\}$.
Since $\Pi^{\varepsilon}\subset\Pi$, we can have that

$\mathcal{R}_{T}^{\operatorname{minimax}}(\pi,\nu)\geqslant\inf_{\pi\in\Pi}\sup_{\nu\in\mathcal{E}_{\mathcal{N}}^{K}(\sigma_{k})}\operatorname{Reg}_{T}(\pi,\nu)\geqslant\Omega{(\sqrt{KT})}$

where the last inequality is due to Theorem 15.2 in [LS20].

Case 1: Uncontaminated case. By the definition of minimax regret, we know that
$\mathcal{R}^{\text{minimax}}_{\varepsilon,\alpha}\geq\mathcal{R}^{\text{minimax}}_{\varepsilon,0}$.
Therefore, we first derive the lower bound of private bandits without
contamination.

We consider two environments. In the first environment $\nu_{1}$, the optimal
arm (denote by $a_{1}$) follows

$r_{a_{1}}=\begin{cases}1/\gamma&\text{ with probability of
}\frac{1}{2}\gamma^{k}\\\ 0&\text{ with probability of
}1-\frac{1}{2}\gamma^{k}\end{cases}$

where $\gamma\in(0,1]$. We can verify
$\mathbb{E}{[r_{a_{1}}]}=\frac{1}{2}\gamma^{k-1}$ and
$\mathbb{E}{[r_{a_{1}}^{k}]}=\frac{1}{2}\leq 1$. Any other sub-optimal arm
$a\neq a_{1}$ in $\nu_{1}$ follows the same reward distribution

$r_{a}=\begin{cases}1/\gamma&\text{ with probability of
}\frac{3}{10}\gamma^{k}\\\ 0&\text{ with probability of
}1-\frac{3}{10}\gamma^{k}\end{cases}$

We can verify $\mathbb{E}{[r_{a}]}=\frac{3}{10}\gamma^{k-1}$ and
$\mathbb{E}{[r_{a_{1}}^{k}]}=\frac{3}{10}\leq 1$. Then the gap of means
between the optimal arm and sub-optimal arm is
$\Delta=\frac{1}{5}\gamma^{k-1}$.

For algorithm $\pi$ and instance $\nu_{1}$, we denote
$i={\arg\min}_{a\in\\{2,\cdots,K\\}}\mathbb{E}_{\pi,\nu_{1}}[N_{a}(T)].$ Thus,
$\mathbb{E}_{\pi,\nu_{1}}[N_{i}(T)]\leqslant\frac{T}{K-1}$.

Now, consider another instance $\nu_{2}$ where $r_{a_{1}},\cdots,r_{a_{k}}$
are the same as those in $\nu_{1}$ except the $i$-th arm such that

$r_{i}^{\prime}=\begin{cases}1/\gamma&\text{ with probability of
}\frac{7}{10}\gamma^{k}\\\ 0&\text{ with probability of
}1-\frac{7}{10}\gamma^{k}\end{cases}$

We can verify $\mathbb{E}{[r_{i}^{\prime}]}=\frac{7}{10}\gamma^{k-1}$ and
$\mathbb{E}{[(r_{i}^{\prime})^{k}]}=\frac{7}{10}\leq 1$. Then in $\nu_{2}$,
the arm $i$ is optimal.

Now by the classic regret decomposition, we obtain

$\mathcal{R}_{T}(\pi,\nu_{1})=(T-\mathbb{E}_{\pi,\nu_{1}}[N_{1}(T)])\Delta\geq\mathbb{P}_{\pi,\nu_{1}}^{T}\left[N_{1}(T)\leq\frac{T}{2}\right]\frac{T\Delta}{2}.$
$\mathcal{R}_{T}(\pi,\nu_{2})=\Delta\mathbb{E}_{\pi,\nu_{2}}[N_{1}(T)]+\sum_{a\notin\\{1,i\\}}2\Delta\mathbb{E}_{\pi,\nu_{2}}[N_{a}(T)]\geq\mathbb{P}_{\pi,\nu_{2}}^{T}\left[N_{1}(T)\geq\frac{T}{2}\right]\frac{T\Delta}{2}.$

By applying the Bretagnolle–Huber inequality ([LS20], Theorem 14.2), we have

$\displaystyle\mathcal{R}_{T}(\pi,\nu_{1})+\mathcal{R}_{T}(\pi,\nu_{2})$
$\displaystyle\geq\frac{T\Delta}{2}\left(\mathbb{P}_{\pi,\nu_{1}}^{T}\left[N_{1}(T)\leq\frac{T}{2}\right]+\mathbb{P}_{\pi,\nu_{2}}^{T}\left[N_{1}(T)\geq\frac{T}{2}\right]\right).$
$\displaystyle\geq\frac{T\Delta}{4}\exp{\left(-\text{KL}\left(\mathbb{P}_{\pi,\nu_{1}}^{T}\|\mathbb{P}_{\pi,\nu_{2}}^{T}\right)\right)}$

Based on Lemma B.1, we can get the upper bound of the KL-Divergence between
the marginals.

$\displaystyle\text{KL}\left(\mathbb{P}_{\pi,\nu_{1}}^{T}\|\mathbb{P}_{\pi,\nu_{2}}^{T}\right)$
$\displaystyle\leq
6\varepsilon\mathbb{E}_{\pi,\nu_{1}}\left[\sum_{t=1}^{T}\text{TV}(r_{a_{t}}\|r^{\prime}_{a_{t}})\right]$
$\displaystyle\leq
6\varepsilon\mathbb{E}_{\pi,\nu_{1}}[N_{i}(T)]\text{TV}(r_{i}\|r^{\prime}_{i})$

since $\nu_{1}$ and $\nu_{i}$ only differ in the arm $i$.

Thus,

$\displaystyle\mathcal{R}_{T}(\pi,\nu_{1})+\mathcal{R}_{T}(\pi,\nu_{2})$
$\displaystyle\geq\frac{T\Delta}{4}\exp{(-6\varepsilon\mathbb{E}_{\pi,\nu_{1}}[N_{i}(T)]\cdot\frac{2}{5}\gamma^{k})}$
$\displaystyle\geq\frac{T\gamma^{k-1}}{20}\exp{\left(-\frac{12\cdot\varepsilon
T\gamma^{k}}{5(K-1)}\right)}.$

Taking $\gamma=\left(\frac{K-1}{T\varepsilon}\right)^{\frac{1}{k}}$, we get
the result

$\mathcal{R}_{T}(\pi,\nu_{1})\geq\Omega\left(\left(\frac{K}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}\right).$

Case 2: Contaminated case. For $\alpha\neq 0$ and $\alpha\in(0,1]$, we still
consider the true distributions of arms are the same in above $\nu_{1}$ and
$\nu_{2}$. In the first environment $\nu_{1}$, the optimal arm (denote by
$a_{1}$) follows

$r_{a_{1}}=\begin{cases}1/\gamma&\text{ with probability of
}\frac{1}{2}\gamma^{k}\\\ 0&\text{ with probability of
}1-\frac{1}{2}\gamma^{k}\end{cases}$

where $\gamma\in(0,1]$. We can verify
$\mathbb{E}{[r_{a_{1}}]}=\frac{1}{2}\gamma^{k-1}$ and
$\mathbb{E}{[r_{a_{1}}^{k}]}=\frac{1}{2}\leq 1$. Any other sub-optimal arm
$a\neq a_{1}$ in $\nu_{1}$ follows the same reward distribution

$r_{a}=\begin{cases}1/\gamma&\text{ with probability of
}\frac{3}{10}\gamma^{k}\\\ 0&\text{ with probability of
}1-\frac{3}{10}\gamma^{k}\end{cases}$

We can verify $\mathbb{E}{[r_{a}]}=\frac{3}{10}\gamma^{k-1}$ and
$\mathbb{E}{[r_{a_{1}}^{k}]}=\frac{3}{10}\leq 1$. Then the gap of means
between the optimal arm and sub-optimal arm is
$\Delta=\frac{1}{5}\gamma^{k-1}$.

And we denote the contaminated version of $\nu_{1}$ as $\tilde{\nu}_{1}$. For
algorithm $\pi$ and instance $\tilde{\nu}_{1}$, we denote
$i={\arg\min}_{a\in\\{2,\cdots,K\\}}\mathbb{E}_{\pi,\tilde{\nu}_{1}}[N_{a}(T)].$
Thus, $\mathbb{E}_{\pi,\tilde{\nu}_{1}}[N_{i}(T)]\leqslant\frac{T}{K-1}$.

Now, consider another instance $\nu_{2}$ where $r_{a_{1}},\cdots,r_{a_{k}}$
are the same as those in $\nu_{1}$ except the $i$-th arm such that

$r_{i}^{\prime}=\begin{cases}1/\gamma&\text{ with probability of
}\frac{7}{10}\gamma^{k}\\\ 0&\text{ with probability of
}1-\frac{7}{10}\gamma^{k}\end{cases}$

We can verify $\mathbb{E}{[r_{i}^{\prime}]}=\frac{7}{10}\gamma^{k-1}$ and
$\mathbb{E}{[(r_{i}^{\prime})^{k}]}=\frac{7}{10}\leq 1$. Then in $\nu_{2}$,
the arm $i$ is optimal.

Also, we denote the contaminated version of $\nu_{2}$ as $\tilde{\nu}_{2}$.
Take $\gamma=\alpha^{\frac{1}{k}}\in(0,1]$, since for any $a\in[K]$,
$\text{TV}(r_{a}\|r_{a}^{\prime})\leq\frac{2}{5}\gamma^{k}=\frac{2}{5}\alpha\leq\frac{\alpha}{1-\alpha}$,
from Lemma B.2, we have for any arm $a\in[K]$, there exists distribution
$G_{a}$ and $G_{a}^{\prime}$ such that

$(1-\alpha)r_{a}+\alpha G_{a}=(1-\alpha)r_{a}^{\prime}+\alpha G_{a}^{\prime}.$

We consider $\tilde{\nu}_{1}=\\{x_{a}=(1-\alpha)r_{a}+\alpha G_{a}:a\in[K]\\}$
and $\tilde{\nu}_{2}=\\{x_{a}^{\prime}=(1-\alpha)r_{a}^{\prime}+\alpha
G_{a}^{\prime}:a\in[K]\\}$.

Now by the classic regret decomposition, we obtain

$\mathcal{R}_{T}(\pi,\tilde{\nu}_{1})=(T-\mathbb{E}_{\pi,\tilde{\nu}_{1}}[N_{1}(T)])\Delta\geq\mathbb{P}_{\pi,\tilde{\nu}_{1}}^{T}\left[N_{1}(T)\leq\frac{T}{2}\right]\frac{T\Delta}{2}.$
$\mathcal{R}_{T}(\pi,\tilde{\nu}_{2})=\Delta\mathbb{E}_{\pi,\tilde{\nu}_{2}}[N_{1}(T)]+\sum_{a\notin\\{1,i\\}}2\Delta\mathbb{E}_{\pi,\tilde{\nu}_{2}}[N_{a}(T)]\geq\mathbb{P}_{\pi,\tilde{\nu}_{2}}^{T}\left[N_{1}(T)\geq\frac{T}{2}\right]\frac{T\Delta}{2}.$

By applying the Bretagnolle–Huber inequality ([LS20], Theorem 14.2), we have

$\displaystyle\mathcal{R}_{T}(\pi,\tilde{\nu}_{1})+\mathcal{R}_{T}(\pi,\tilde{\nu}_{2})$
$\displaystyle\geq\frac{T\Delta}{2}\left(\mathbb{P}_{\pi,\tilde{\nu}_{1}}^{T}\left[N_{1}(T)\leq\frac{T}{2}\right]+\mathbb{P}_{\pi,\tilde{\nu}_{2}}^{T}\left[N_{1}(T)\geq\frac{T}{2}\right]\right).$
$\displaystyle\geq\frac{T\Delta}{4}\exp{\left(-\text{KL}\left(\mathbb{P}_{\pi,\tilde{\nu}_{1}}^{T}\|\mathbb{P}_{\pi,\tilde{\nu}_{2}}^{T}\right)\right)}$

Based on Lemma B.1, we can get the upper bound of the KL-Divergence between
the marginals.

$\displaystyle\text{KL}\left(\mathbb{P}_{\pi,\tilde{\nu}_{1}}^{T}\|\mathbb{P}_{\pi,\tilde{\nu}_{2}}^{T}\right)$
$\displaystyle\leq
6\varepsilon\mathbb{E}_{\pi,\tilde{\nu}_{1}}\left[\sum_{t=1}^{T}\text{TV}(x_{a_{t}}\|x^{\prime}_{a_{t}})\right]$

Since, $\text{TV}(x_{a}\|x^{\prime}_{a})=0$ for $\forall a\in[K]$,
$\Delta=\frac{1}{5}\gamma^{k-1}$ and $\gamma=\alpha^{\frac{1}{k}}$. We obtain

$\mathcal{R}_{T}(\pi,\tilde{\nu}_{1})\geq\Omega(T\alpha^{1-\frac{1}{k}}).$

Combine Gaussian case, case 1 and case 2, we have

$\mathcal{R}_{T}=\Omega\left(\max\left\\{\sqrt{KT},\left(\frac{K}{\varepsilon}\right)^{1-\frac{1}{k}}T^{\frac{1}{k}},T\alpha^{1-\frac{1}{k}}\right\\}\right).$

∎

##  Appendix C Proofs of Section 6.1

###### Proof of Theorem 6.1.

We denote the finite raw moments distribution for rewards by $P_{k}$, and
denote $P_{k}$ under $\alpha$-Huber contamination by $P_{\alpha,k}$. Let
$\widehat{\mu}=\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}$ and
$\mu=\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}]$.

$\displaystyle|\tilde{\mu}-\mu|\leq$
$\displaystyle\left|\text{Lap}\left(\frac{2M}{n\varepsilon}\right)\right|+|\widehat{\mu}-\mu|$
$\displaystyle\leq$
$\displaystyle\left|\text{Lap}\left(\frac{2M}{n\varepsilon}\right)\right|+\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]\right|+|\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]-\mu|$ $\displaystyle=$
$\displaystyle\left|\text{Lap}\left(\frac{2M}{n\varepsilon}\right)\right|+\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]\right|+|\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|>M)}]|$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\frac{2M\log(2/\delta)}{n\varepsilon}+\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]\right|+\mathbb{E}_{X_{i}\sim
P_{k}}[|X_{i}|\mathbbm{1}_{(|X_{i}|>M)}]\quad\text{w.p.}\quad
1-\frac{\delta}{2}$ $\displaystyle\overset{(b)}{\leq}$
$\displaystyle\frac{2M\log(2/\delta)}{n\varepsilon}+\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]\right|+(\mathbb{E}_{X_{i}\sim
P_{k}}[|X_{i}|^{k}])^{\frac{1}{k}}(\mathbb{P}_{X_{i}\sim
P_{k}}{(|X_{i}|>M)})^{\frac{k-1}{k}}$ $\displaystyle\overset{(c)}{\leq}$
$\displaystyle\frac{2M\log(2/\delta)}{n\varepsilon}+\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]\right|+\frac{1}{M^{k-1}}$

where the inequality $(a)$ follows from Lemma A.6, $(b)$ is from Hölder’s
Inequality in Lemma A.8 and $(c)$ follows from Markov’s inequality in Lemma
A.4.

Now we focus on the upper bound of
$\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|$.
Let $N_{G}$ be the set of indices in $n$ samples distributed according to $G$,
and $N_{P_{k}}$ be the set of indices in $n$ samples distributed according to
$P_{k}$. Then

Case 1: uncontaminated case ($\alpha=0$) Now, the only thing left is to upper
bound

$\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}-\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|.$

For $X_{i}\sim P_{k}$, let $Y_{i}=X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}$, then
$|Y_{i}|\leq M$ and
$\text{Var}(Y_{i})=\mathbb{E}[Y_{i}^{2}]-(\mathbb{E}[Y_{i}])^{2}\leq\mathbb{E}[Y_{i}^{2}]\leq\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}^{2}]\leq 1$. Then, from Bernstein’s inequality in Lemma A.9, we
have with probability $1-\delta/2$

$\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}-\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}]\right|\leq\sqrt{\frac{2\log(4/\delta)}{n}}+\frac{4M\log(4/\delta)}{3n}.$
(4)

Then we get with probability at least $1-\delta$,

$|\tilde{\mu}-\mu|\leq\sqrt{\frac{2\log(4/\delta)}{n}}+\frac{4M\log(4/\delta)}{3n}+\frac{2M\log(2/\delta)}{n\varepsilon}+\frac{1}{M^{k-1}}.$

For $\varepsilon>0$ and $\delta\in(0,1)$, we have with probability at least
$1-\delta$,

$|\tilde{\mu}-\mu|\leq\sqrt{\frac{2\log(4/\delta)}{n}}+\frac{4M\log(4/\delta)}{n\varepsilon}+\frac{1}{M^{k-1}}.$

Taking the truncation threshold
$M=\left(\frac{n\varepsilon}{4\log(4/\delta)}\right)^{\frac{1}{k}}$, we have

$|\tilde{\mu}-\mu|\leq\sqrt{\frac{2\log(4/\delta)}{n}}+2\left(\frac{4\log(4/\delta)}{n\varepsilon}\right)^{1-\frac{1}{k}}.$

Case 2: contaminated case ($\alpha\in(0,\frac{1}{2}]$ )

$\displaystyle\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{\alpha,k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|$
$\displaystyle=$ $\displaystyle\left|\frac{1}{n}\sum\limits_{i\in
N_{G}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}+\frac{1}{n}\sum\limits_{i\in
N_{P_{k}}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}-\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|$ $\displaystyle\leq$
$\displaystyle\underbrace{\left|\frac{1}{n}\sum\limits_{i\in
N_{G}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}\right|}_{T_{1}}+\underbrace{\left|\frac{1}{n}\sum\limits_{i\in
N_{P_{k}}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}-\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|}_{T_{2}}.$

To control $T_{1}$, we can write it as

$\displaystyle T_{1}$ $\displaystyle=\left|\frac{1}{n}\sum\limits_{i\in
N_{G}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}\right|$
$\displaystyle\leq\frac{1}{n}\sum\limits_{i\in
N_{G}}\left|X_{i}\right|\mathbbm{1}_{(|X_{i}|\leq M)}$
$\displaystyle\leq\frac{|N_{G}|}{n}M.$

Then $\frac{|N_{G}|}{n}$ can be treat as a mean estimation of Bernoulli
distribution $Ber(\alpha)$. Then based on Bernstein’s inequality in Lemma A.9,
we get with probability $1-\delta/4$,

$\left|\frac{|N_{G}|}{n}-\alpha\right|\leq\sqrt{\frac{2\alpha(1-\alpha)\log(8/\delta)}{n}}+\frac{2\log(8/\delta)}{3n}.$

Thus,

$T_{1}\leq\left(\alpha+\sqrt{\frac{2\alpha\log(8/\delta)}{n}}+\frac{2\log(8/\delta)}{3n}\right)M.\quad\text{with
probability}1-\delta/4$

When $n\geq\frac{\log(8/\delta)}{\alpha}$, we have

$T_{1}\leq 4\alpha M.$

To bound $T_{2}$, we have

$\displaystyle\left|\frac{1}{n}\sum\limits_{i\in
N_{P_{k}}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}-\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|$ $\displaystyle=$
$\displaystyle\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in N_{G}\cup
N_{P_{k}}\\\ X_{i}\sim P_{k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in N_{G}\\\ X_{i}\sim
P_{k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}-\mathbb{E}_{X_{i}\sim
P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|$ $\displaystyle\leq$
$\displaystyle\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in N_{G}\\\
X_{i}\sim P_{k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}\right|+\left|\frac{1}{n}\sum\limits_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{k}\end{subarray}}X_{i}\mathbbm{1}_{(|X_{i}|\leq
M)}-\mathbb{E}_{X_{i}\sim P_{k}}[X_{i}\mathbbm{1}_{(|X_{i}|\leq M)}]\right|$
$\displaystyle\leq$ $\displaystyle 4\alpha
M+\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4M\log(16/\delta)}{3n}\quad\text{w.p.}\quad
1-\delta/4$

where the last inequality is based on the similar analysis of $T_{1}$ and the
inequality of (4).

Put everything together, we have with probability at least $1-\delta$,

$|\tilde{\mu}-\mu|\leq\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4M\log(16/\delta)}{3n}+8\alpha
M+\frac{2M\log(2/\delta)}{n\varepsilon}+\frac{1}{M^{k-1}}.$

Thus, for $\varepsilon>0$, we have

$|\tilde{\mu}-\mu|\leq\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4M\log(16/\delta)}{n\varepsilon}+\frac{1}{M^{k-1}}+8\alpha
M.$

Taking
$M=\min\left\\{\left(\frac{n\varepsilon}{4\log(16/\delta)}\right)^{\frac{1}{k}},(8\alpha)^{-\frac{1}{k}}\right\\}$,
we have

$|\tilde{\mu}-\mu|\leq\sqrt{\frac{2\log(16/\delta)}{n}}+2\left(\frac{4\log(16/\delta)}{n\varepsilon}\right)^{1-\frac{1}{k}}+2(8\alpha)^{1-\frac{1}{k}}.$

∎

###### Proof of Theorem 6.2.

Let $\tau_{0}$ be the maximal epoch such that
$B_{\tau}<\frac{\log(16|\mathcal{S}|\tau^{2}/\delta)}{\alpha}$.

For all epoch $\tau\leq\tau_{0}$, the batch size is less than $2^{\tau_{0}}$.
Since batch size doubles, until epoch $\tau_{0}$, we have the number of pulls
for each arm $a\in[K]$ is less than $2\cdot 2^{\tau_{0}}\leq
2\frac{\log(16|\mathcal{S}|\tau_{0}^{2}/\delta)}{\alpha}$. Then the regret has
to suffer $\frac{2\log(16|\mathcal{S}|\tau_{0}^{2}/\delta)}{\alpha}\Delta_{a}$
for each $a\in[K]$.

For $\tau>\tau_{0}$,
$B_{\tau}\geq\frac{\log(16|\mathcal{S}|\tau^{2}/\delta)}{\alpha}$. For each
$a\in\mathcal{S}$, from Theorem 6.1, we have with probability at least
$1-\frac{\delta}{2|\mathcal{S}|\tau^{2}}$,

$|\tilde{\mu}_{a}-\mu_{a}|\leq\beta_{\tau}.$

Given an epoch $\tau>\tau_{0}$, we denote by $\mathcal{E}_{\tau}$ the event
where for all $a\in\mathcal{S}$ it holds that
$|\tilde{\mu}_{a}-\mu_{a}|\leq\beta_{\tau}.$ and denote
$\mathcal{E}=\cup_{\tau>\tau_{0}}\mathcal{E}_{\tau}$.By taking union bound, we
have

$\mathbb{P}(\mathcal{E}_{\tau})\geq 1-\frac{\delta}{2\tau^{2}},$

and

$\mathbb{P}(\mathcal{E})\geq
1-\frac{\delta}{2}\left(\sum_{\tau>\tau_{0}}\tau^{-2}\right)\geq 1-\delta.$

In the following, we condition on the good event $\mathcal{E}$. We first show
that the optimal arm $a^{*}$ is never eliminated. For any epoch
$\tau>\tau_{0}$, let
$a_{\tau}=\arg\max_{a\in\mathcal{S}}{\widetilde{\mu}_{a}}$. Since

$(\widetilde{\mu}_{a_{\tau}}-\widetilde{\mu}_{a^{*}})+\Delta_{a_{\tau}}=|(\widetilde{\mu}_{a_{\tau}}-\widetilde{\mu}_{a^{*}})+\Delta_{a_{\tau}}|\leq\left|\widetilde{\mu}_{a_{\tau}}-\mu_{a_{\tau}}\right|+\left|\widetilde{\mu}_{a^{*}}-\mu_{a^{*}}\right|\leq
2\beta_{\tau},$

it is easy to see that the algorithm doesn’t eliminate $a^{*}$.

Then, we show that at the end of epoch $\tau>\tau_{0}$, all arms such that
$\Delta_{a}\geq 4\beta_{\tau}$ will be eliminated. To show this, we have that
under good event $\mathcal{E}$,

$\tilde{\mu}_{a}+\beta_{\tau}\leq\mu_{a}+2\beta_{\tau}<\mu_{a^{*}}-4\beta_{\tau}+2\beta_{\tau}\leq\tilde{\mu}_{a^{*}}-\beta_{\tau}\leq\tilde{\mu}_{a_{\tau}}-\beta_{\tau}$

which implies that arm $a$ will be eliminated by the rule. Thus, for each sub-
optimal arm $a$, let $\tau(a)$ be the last epoch that arm $a$ is not
eliminated. By the above result, we have

$\Delta_{a}\leq
4\beta_{\tau(a)}=4\sqrt{\frac{2\log(16|\mathcal{S}|\tau(a)^{2}/\delta)}{B_{\tau(a)}}}+8\left(\frac{4\log(16|\mathcal{S}|\tau(a)^{2}/\delta)}{B_{\tau(a)}\varepsilon}\right)^{1-\frac{1}{k}}+8(8\alpha)^{1-\frac{1}{k}}.$

We divide the arms $a\in[K]$ into two groups:
$\mathcal{G}_{1}=\\{a\in[K]:16(8\alpha)^{1-\frac{1}{k}}\leq\Delta_{a}\\}$ and
$\mathcal{G}_{2}=\\{a\in[K]:16(8\alpha)^{1-\frac{1}{k}}\geq\Delta_{a}\\}$.

Group 1: Now, for all arm $a\in\mathcal{G}_{1}$, we have

$\Delta_{a}\leq
8\sqrt{\frac{2\log(16|\mathcal{S}|\tau(a)^{2}/\delta)}{B_{\tau(a)}}}+16\left(\frac{4\log(16|\mathcal{S}|\tau(a)^{2}/\delta)}{B_{\tau(a)}\varepsilon}\right)^{1-\frac{1}{k}}.$

Hence, we have

$B_{\tau(a)}\leq\max\left\\{\frac{128\log(16|\mathcal{S}|\tau(a)^{2}/\delta)}{\Delta_{a}^{2}},\frac{4\log(16|\mathcal{S}|\tau(a)^{2}/\delta)}{\varepsilon}\left(\frac{16}{\Delta_{a}}\right)^{\frac{k}{k-1}},\frac{\log(16|\mathcal{S}|\tau_{0}^{2}/\delta)}{\alpha}\right\\}.$

Since $|\mathcal{S}|\leq K$ and $2^{\tau}\leq T$ for any $\tau$. Thus,

$B_{\tau(a)}\leq\max\left\\{\frac{128\log(16K\log^{2}T/\delta)}{\Delta_{a}^{2}},\frac{4\log(16K\log^{2}T/\delta)}{\varepsilon}\left(\frac{16}{\Delta_{a}}\right)^{\frac{k}{k-1}},\frac{\log(16K\log^{2}T/\delta)}{\alpha}\right\\},$

Since the batch size doubles, we have $N_{a}(T)\leq 2B_{\tau(a)}$ for each
sub-optimal arm $a$. Therefore, for all arm $a\in\mathcal{G}_{1}$,

$\mathcal{R}_{T}=\sum_{a\in\mathcal{G}_{1}}N_{a}(T)\Delta_{a}\leq
2B_{\tau(a)}\Delta_{a}.$

Let $\eta$ be a number in $(0,1)$. For all arms $a\in\mathcal{G}_{1}$ with
$\Delta_{a}\leq\eta$, the regret incurred by pulling these arms is upper
bounded by $T\eta$. For any arm $a\in\mathcal{G}_{1}$ with $\Delta_{a}>\eta$,
choose $\delta=\frac{1}{T}$ and assume $T\geq K$, then the expected regret
incurred by pulling arm $a$ is upper bounded by

$\displaystyle\mathbb{E}\left[\sum_{a\in\mathcal{G}_{1},\Delta_{a}>\eta}\Delta_{a}N_{a}(T)\right]$
$\displaystyle\leq\mathbb{P}(\bar{\mathcal{E}})\cdot
T+O\left(\sum_{{a\in\mathcal{G}_{1},\Delta_{a}>\eta}}\left\\{\frac{\log
T}{\Delta_{a}}+\frac{\log
T}{\varepsilon}\left(\frac{1}{\Delta_{a}}\right)^{\frac{1}{k-1}}+\frac{\log
T}{\alpha}\Delta_{a}\right\\}\right)$ $\displaystyle\leq O\left(\frac{K\log
T}{\eta}+\frac{K\log T}{\varepsilon\eta^{\frac{1}{k-1}}}+\frac{K\log
T}{\alpha}\right)$

where the last term in the last inequality is based on following result: from
the heavy-tailed assumption for rewards distributions in (1), we have for any
$a\in[K]$, $|\mu_{a}|\leq\mathbb{E}_{r_{a}\sim
P_{k}}|r_{a}|\leq\mathbb{E}_{r_{a}\sim P_{k}}|r_{a}|^{k}\leq 1$, so
$\Delta_{a}=\mu^{*}-\mu_{a}\leq 2$.

Thus the regret from group 1 is at most

$T\eta+O\left(\frac{K\log T}{\eta}+\frac{K\log
T}{\varepsilon\eta^{\frac{1}{k-1}}}+\frac{K\log T}{\alpha}\right).$

Taking $\eta=\max\left\\{\sqrt{\frac{K\log T}{T}},\left(\frac{K\log
T}{T\varepsilon}\right)^{\frac{k-1}{k}}\right\\}$, the regret from group 1 is
at most

$O\left(\sqrt{KT\log T}+\left(\frac{K\log
T}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}+\frac{K\log
T}{\alpha}\right)$

Group 2: For all other arms $a\in\mathcal{G}_{2}$, we have the total regret is
at most $O(T\Delta_{a})=O(T\alpha^{1-\frac{1}{k}})$.

Combine the two groups, choose $\delta=\frac{1}{T}$ and assume $T\geq K$, we
have the that the expected regret satisfies,

$\mathcal{R}_{T}\leq O\left(\sqrt{KT\log T}+\left(\frac{K\log
T}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}+\frac{K\log
T}{\alpha}+T\alpha^{1-\frac{1}{k}}\right)$

We also give privacy guarantee for the algorithm. Based on Laplacian mechanism
in Definition 3.5 and Post-processing in Lemma A.1, we can get that Algorithm
1 is $\varepsilon$-DP. ∎

##  Appendix D Proofs of Section 6.2

###### Proof of Theorem 6.5.

Step 1: we will show that with high probability $1-\delta/2$, $|J-\mu|\leq
2r$.

To this end, we first study the private histogram. Note
$\mathbb{E}[\mathbbm{1}(X_{i}\in B_{j})]=P_{\alpha,k}(B_{j})$, then

$\displaystyle\mathbb{P}\left(|\tilde{p}_{j}-P_{\alpha,k}(B_{j})|>t\right)$
$\displaystyle=\mathbb{P}\left(\left|\frac{\sum_{i=1}^{n}\mathbbm{1}(X_{i}\in
B_{j})}{n}+\operatorname{Lap}\left(\frac{2}{n\varepsilon}\right)-P_{\alpha,k}(B_{j})\right|>t\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{\sum_{i=1}^{n}\mathbbm{1}(X_{i}\in
B_{j})}{n}-P_{\alpha,k}(B_{j})\right|>t/2\right)+\mathbb{P}\left(\left|\operatorname{Lap}\left(\frac{2}{n\varepsilon}\right)\right|>t/2\right)$
$\displaystyle\leq
2\exp\left(-\frac{nt^{2}}{2}\right)+\exp\left(-\frac{n\varepsilon
t}{4}\right),$

where the last inequality is from Lemma A.7 and Lemma A.6. By a union bound
over $j$, we further have

$\displaystyle\mathbb{P}\left(\max_{j\in\mathcal{J}}|\tilde{p}_{j}-P_{\alpha,k}(B_{j})|>t\right)$
$\displaystyle\leq\frac{2D}{r}\left(2\exp\left(-\frac{nt^{2}}{2}\right)+\exp\left(-\frac{n\varepsilon
t}{4}\right)\right)$ $\displaystyle\leq
2D\left(2\exp\left(-\frac{nt^{2}}{2}\right)+\exp\left(-\frac{n\varepsilon
t}{4}\right)\right)$

Thus, we have with probability $1-\delta/2$,

$\displaystyle\max_{j\in\mathcal{J}}|\tilde{p}_{j}-P_{\alpha,k}(B_{j})|\leq\max\left\\{\sqrt{\frac{2\ln\frac{16D}{\delta}}{n}},\frac{4\ln\frac{16D}{\delta}}{n\varepsilon}\right\\}:=C_{1}.$

In the following, we condition on the above event. Next, by Chebyshev’s
inequality in Lemma A.5 and the assumption of $\mathcal{P}_{k}$ that $k$-th
central moment is less than 1, we have

$\displaystyle\mathbb{P}_{X\sim\mathcal{P}_{\alpha,k}}\left(|X-\mu|\geq
r\right)$ $\displaystyle\leq\alpha\mathbb{P}_{X\sim\mathcal{G}}(|X-\mu|\geq
r)+(1-\alpha)\mathbb{P}_{X\sim\mathcal{P}_{k}}(|X-\mu|\geq r)$
$\displaystyle\leq\alpha+(1-\alpha)(1/r)^{k}:=C_{2}$ (5)

Let $j^{*}$ is the index of the bin containing the true mean $\mu$ and we
consider three consecutive intervals $A_{j^{*}}=B_{j^{*}-1}\cup B_{j^{*}}\cup
B_{j^{*}+1}$

$\displaystyle P_{\alpha,k}(A_{j^{*}})$
$\displaystyle=P_{\alpha,k}(B_{j^{*}-1})+P_{\alpha,k}(B_{j^{*}})+P_{\alpha,k}(B_{j^{*}+1})$
$\displaystyle\geq P_{\alpha,k}\left((\mu-r,\mu+r)\right)$ $\displaystyle\geq
1-C_{2}.$

where the first inequality is from inequality (D). Now, for any
$j\notin\\{j^{*}-1,j^{*},j^{*}+1\\}$, we have when $D\geq 2r$

$\displaystyle\tilde{p}_{j}$ $\displaystyle\leq P_{\alpha,k}(B_{j})+C_{1}\leq
1-P_{\alpha,k}(A_{j^{*}})+C_{1}\leq C_{2}+C_{1}.$

On the other hand, since $P_{\alpha,k}(A_{j^{*}})\geq 1-C_{2}$, there must
exist some $j\in\\{j^{*}-1,j^{*},j^{*}+1\\}$ such that
$P_{\alpha,k}(B_{j})\geq\frac{1-C_{2}}{3}$. Therefore, for this $j$, we have

$\displaystyle\tilde{p}_{j}$ $\displaystyle\geq
P_{\alpha,k}(B_{j})-C_{1}\geq\frac{1-C_{2}}{3}-C_{1}.$

Therefore, if $n$ (depending on $\alpha$, $\varepsilon,r$) such that
$\frac{1-C_{2}}{3}-C_{1}>C_{2}+C_{1}$, the true mean $\mu$ is in the bin
chosen by line 3 in Algorithm 3 or it’s neighboring bin, which implies that
with probability at least $1-\delta/2$, $|J-\mu|\leq 2r$.

Step 2: Utilizing the above result, we aim to show that truncation can handle
heavy-tail, privacy and robustness in the concentration.

$\displaystyle|\tilde{\mu}-\mu|$
$\displaystyle=|J+\frac{1}{n}\sum_{i=n+1}^{2n}(X_{i}-J)\mathbbm{1}(|X_{i}-J|\leq
M)+\operatorname{Lap}\left(\frac{2M}{n\varepsilon}\right)-\mu|$
$\displaystyle=\left|\frac{1}{n}\sum_{i=n+1}^{2n}(X_{i}-J)\mathbbm{1}(|X_{i}-J|\leq
M)+\operatorname{Lap}\left(\frac{2M}{n\varepsilon}\right)\right.$
$\displaystyle\left.+\frac{1}{n}\sum_{i=n+1}^{2n}(J-\mu)\left\\{\mathbbm{1}(|X_{i}-J|\leq
M)+\mathbbm{1}(|X_{i}-J|>M)\right\\}\right|$
$\displaystyle=\left|\frac{1}{n}\sum_{i=n+1}^{2n}(X_{i}-J+J-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)+\operatorname{Lap}\left(\frac{2M}{n\varepsilon}\right)+\frac{1}{n}\sum_{i=n+1}^{2n}(J-\mu)\mathbbm{1}(|X_{i}-J|>M)\right|$
$\displaystyle\leq\left|\frac{1}{n}\sum_{i=n+1}^{2n}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)\right|+\left|\operatorname{Lap}\left(\frac{2M}{n\varepsilon}\right)\right|+\left|\frac{1}{n}\sum_{i=n+1}^{2n}(J-\mu)\mathbbm{1}(|X_{i}-J|>M)\right|$

We first focus on the first term in the right hand of the last inequality. Let
$N_{G}$ be the set of indices in $n$ samples distributed according to
$G\in\mathcal{G}$, and $N_{P_{k}}$ be the set of indices in $n$ samples
distributed according to $P_{k}\in\mathcal{P}_{k}^{c}$. Then, we have

$\displaystyle\left|\frac{1}{n}\sum_{i=n+1}^{2n}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)\right|$ $\displaystyle\leq\underbrace{\left|\frac{1}{n}\sum_{i\in
N_{G}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)\right|}_{T_{1}}+\underbrace{\left|\frac{1}{n}\sum_{i\in
N_{P_{k}}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M)\right|}_{T_{2}}.$

To control $T_{1}$, we can write it as

$\displaystyle T_{1}$ $\displaystyle=\left|\frac{1}{n}\sum_{i\in
N_{G}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M)\right|$
$\displaystyle\leq\frac{1}{n}\sum_{i\in
N_{G}}|(X_{i}-\mu)|\mathbbm{1}(|X_{i}-J|\leq M)$
$\displaystyle\leq\frac{1}{n}\sum_{i\in
N_{G}}|(X_{i}-\mu)|\mathbbm{1}(|X_{i}-\mu|\leq M+2r)$
$\displaystyle\leq\frac{|N_{G}|}{n}(M+2r).$

Then $\frac{|N_{G}|}{n}$ can be treat as a mean estimation of Bernoulli
distribution $Ber(\alpha)$. Then based on Bernstein’s inequality in Lemma A.9,
we get with probability $1-\delta/8$,

$\left|\frac{|N_{G}|}{n}-\alpha\right|\leq\sqrt{\frac{2\alpha(1-\alpha)\log(16/\delta)}{n}}+\frac{2\log(16/\delta)}{3n}.$

Thus,

$T_{1}\leq\left(\alpha+\sqrt{\frac{2\alpha\log(16/\delta)}{n}}+\frac{2\log(16/\delta)}{3n}\right)(M+2r),\quad\text{with
probability}1-\delta/8$

.

Thus, if $n$ satisfies
$\sqrt{\frac{2\alpha\log(16/\delta)}{n}}+\frac{2\log(16/\delta)}{3n}=O(\alpha)$,
then we have $T_{1}=O(\alpha(M+2r))$ Now, we bound $T_{2}$,

$\displaystyle T_{2}$
$\displaystyle=\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in N_{G}\cup
N_{P_{k}}\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)-\frac{1}{n}\sum_{\begin{subarray}{c}i\in N_{G}\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M)\right|$
$\displaystyle\leq\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in N_{G}\cup
N_{P_{k}}\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)\right|+\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in N_{G}\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M)\right|$
$\displaystyle\leq\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in[n]\\\
X_{i}\sim P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)\right|+T_{1}.$

Now we focus on the upper bound of
$\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M)\right|$. With
probability $1-\delta/8$,

$\displaystyle\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M)\right|$
$\displaystyle\leq$
$\displaystyle\left|\frac{1}{n}\sum_{\begin{subarray}{c}i\in[n]\\\ X_{i}\sim
P_{k}\end{subarray}}(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq
M)-\mathbb{E}[(X_{1}-\mu)\mathbbm{1}(|X_{1}-J|\leq M)]\right|$
$\displaystyle+|\mathbb{E}[(X_{1}-\mu)\mathbbm{1}(|X_{1}-J|\leq
M)]-\mathbb{E}[(X_{1}-\mu)]|$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4(M+2r)\log(16/\delta)}{3n}+|\mathbb{E}[(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\geq
M)]|$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4(M+2r)\log(16/\delta)}{3n}+\left(\mathbb{E}[|X_{i}-\mu|^{k}]\right)^{\frac{1}{k}}\left(\mathbb{P}(|X_{i}-\mu|\geq
M-2r)\right)^{\frac{k-1}{k}}]$ $\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4(M+2r)\log(16/\delta)}{3n}+\frac{1}{(M-2r)^{k-1}}$
$\displaystyle\leq$
$\displaystyle\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4(M+2r)\log(16/\delta)}{3n}+\left(\frac{2}{M}\right)^{k-1}$

where the last inequality follows from $M\geq 4r$ ,the third inequality
follows from Hölder’s Inequality in Lemma A.8 and the second inequality
follows from Bernstein inequality in Lemma A.9. That is, let

$Y_{i}=(X_{i}-\mu)\mathbbm{1}(|X_{i}-J|\leq M),$

then

$\displaystyle|Y_{i}-\mathbb{E}[Y_{i}]|$
$\displaystyle\leq|Y_{i}|+|\mathbb{E}[Y_{i}]|$
$\displaystyle\leq|X_{i}-\mu|\mathbbm{1}(|X_{i}-\mu|\leq
M+2r)+\mathbb{E}[|X_{i}-\mu|\mathbbm{1}(|X_{i}-\mu|\leq M+2r)]$
$\displaystyle\leq 2(M+2r)$

and

$\displaystyle\operatorname{Var}(Y_{i}-\mathbb{E}[Y_{i}])$
$\displaystyle=\mathbb{E}(Y_{i}-\mathbb{E}[Y_{i}])^{2}\leq\mathbb{E}[Y_{i}^{2}]$
$\displaystyle\leq\mathbb{E}_{X_{i}\sim
P_{k}}[(X_{i}-\mu)^{2}\mathbbm{1}(|X_{i}-\mu|\leq M+2r)]$
$\displaystyle\leq\mathbb{E}_{X_{i}\sim P_{k}}[(X_{i}-\mu)^{2}]\leq 1.$

Therefore, with probability $1-3\delta/8$,

$T_{2}\leq\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4(M+2r)\log(16/\delta)}{3n}+\left(\frac{2}{M}\right)^{k-1}+T_{1}.$

Now, we focus on the upper bound of
$T_{3}:=\left|\frac{1}{n}\sum_{i=n+1}^{2n}(J-\mu)\mathbbm{1}(|X_{i}-J|>M)\right|$.

$\displaystyle\left|\frac{1}{n}\sum_{i=n+1}^{2n}(J-\mu)\mathbbm{1}(|X_{i}-J|>M)\right|$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i=n+1}^{2n}\left|J-\mu\right|\mathbbm{1}(|X_{i}-J|>M)$
$\displaystyle\leq$ $\displaystyle
2r\frac{\sum_{i=n+1}^{2n}\mathbbm{1}(|X_{i}-J|>M)}{n}$ $\displaystyle\leq$
$\displaystyle 2r\frac{\sum_{i=n+1}^{2n}\mathbbm{1}(|X_{i}-\mu|>M-2r)}{n}$

where

$\displaystyle\mathbb{E}_{X_{i}\sim
P_{k,\alpha}}[\mathbbm{1}(|X_{i}-\mu|>M-2r)]$
$\displaystyle=\mathbb{P}_{X_{i}\sim P_{k,\alpha}}(|X_{i}-\mu|>M-2r)$
$\displaystyle\leq\alpha+(1-\alpha)\mathbb{P}_{X_{i}\sim
P_{k}}(|X_{i}-\mu|>M-2r)$
$\displaystyle\leq\alpha+\frac{1}{(M-2r)^{k}}\leq\alpha+\left(\frac{2}{M}\right)^{k}$

By Hoeffding’s inequality, we have with probability $1-\delta/8$,

$\frac{\sum_{i=n+1}^{2n}\mathbbm{1}(|X_{i}-\mu|>M-2r)}{n}\leq\mathbb{P}_{X_{i}\sim
P_{k,\alpha}}(|X_{i}-\mu|>M-2r)+\sqrt{\frac{\log(16/\delta)}{2n}}.$

Thus, we have

$T_{3}=\left|\frac{1}{n}\sum_{i=n+1}^{2n}(J-\mu)\mathbbm{1}(|X_{i}-J|>M)\right|\leq
2r\left(\alpha+\left(\frac{2}{M}\right)^{k}+\sqrt{\frac{\log(16/\delta)}{2n}}\right).$

Putting everything together, we have

$\displaystyle|\tilde{\mu}-\mu|=$ $\displaystyle
O\left(\left(\alpha+\sqrt{\frac{2\alpha\log(16/\delta)}{n}}+\frac{2\log(16/\delta)}{3n}\right)(M+2r)\right)$
$\displaystyle+$ $\displaystyle
O\left(\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{4(M+2r)\log(16/\delta)}{3n}+\left(\frac{2}{M}\right)^{k-1}\right)$
$\displaystyle+$ $\displaystyle
O\left(2r\left(\alpha+\left(\frac{2}{M}\right)^{k}+\sqrt{\frac{\log(16/\delta)}{2n}}\right)\right)$
$\displaystyle+$ $\displaystyle
O\left(\frac{M\log(1/\delta)}{n\varepsilon}\right)$

Case I: $\alpha=0$, Uncontaminated concentration. We want to show that our
concentration is better than medians-of-mean in [KSU20] (Theorem 3.5). That
is, we are additive for their third term therein (i.e.,
$\log(D)+\log(1/\delta)$), while they are multiplicative.

In this case, our $C_{2}=(1/r)^{k}$, and by our first condition on $n$, it
need to satisfy $6C_{1}+4C_{2}<1$. This implies that $C_{2}<1/4$. Thus,
setting $r=10^{1/k}$ is sufficient. Hence, we have $C_{1}<0.1$, which requires
$n$ to satisfy $n\geq 200\log(16D/\delta)$ and $n\geq
20\log(16D/\delta)/\varepsilon$. We can safely set $n\geq
200\log(16D/\delta)/\varepsilon$.

In the case of $\alpha=0$, $T_{1}$ is not a problem, which only introduces
another $O(M\log(1/\delta)/n)$. $T_{3}$ is also not a problem which is
dominated by $O((2/M)^{k-1}+\sqrt{\log(1/\delta)}/\sqrt{n})$

Let’s summarize all the values: when $\alpha=0$, $r=10^{1/k}$ and $n\geq
200\log(16D/\delta)/\varepsilon$, we have

$\displaystyle|\tilde{\mu}-\mu|=$ $\displaystyle
O\left(\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{M\log(16/\delta)}{3n}+\left(\frac{2}{M}\right)^{k-1}\right)$
$\displaystyle+$ $\displaystyle
O\left(\frac{M\log(1/\delta)}{n\varepsilon}\right)$ $\displaystyle=$
$\displaystyle
O\left(\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{M\log(16/\delta)}{\varepsilon
n}+\left(\frac{2}{M}\right)^{k-1}\right)$

Now, we need to choose $M$ to minimize the above while satisfying $M\geq 4r$.
By standard choice, we set
$M=4\left(\frac{n\varepsilon}{\log(1/\delta)}\right)^{1/k}$, which satisfies
$M\geq 4r$ when $n\geq\frac{10\log(1/\delta)}{\varepsilon}$.

Case II: $\alpha>0$. Contaminated concentration. We want to minimize the term
$\mathcal{T}(\alpha,\varepsilon)$ while maximizing the possible range of
$\alpha$.

In this case, $C_{2}=\alpha+(1-\alpha)(1/r)^{k}$ and again we need to satisfy
that $6C_{1}+4C_{2}<1$, which first implies that $\alpha$ needs to be
$\alpha<1/4$. Setting $r=\iota^{1/k}$, we have
$C_{2}=\alpha+\frac{1}{\iota}(1-\alpha)$, which needs to be less than $1/4$.
Let’s set $\iota=\frac{1-\alpha}{0.249-\alpha}$ (hence $\alpha<0.249$), we
have there exists an absolute constant $c_{1}$ such that when $n\geq
c_{1}\log(16D/\delta)/\varepsilon$, we guarantee $6C_{1}+4C_{2}<1$.

Now, we turn to $T_{1}$. If $n\geq\frac{\log(16/\delta)}{\alpha}$ and $M\geq
4r$, we have $T_{1}=O(\alpha M)$.

For $T_{3}$, we have

$\displaystyle
T_{3}=2r\left(\alpha+\left(\frac{2}{M}\right)^{k}+\sqrt{\frac{\log(16/\delta)}{2n}}\right)$

One simple way is to set $n\geq\log(16/\delta)/\alpha^{2}$. Then, we have
$T_{3}=O(\alpha M+(1/M)^{k-1})$.

Let’s summarize it. For any $\alpha\in(0,0.249)$, setting
$r=\left(\frac{1-\alpha}{0.249-\alpha}\right)^{1/k}$. Then, for all
$n\geq\max\\{c_{1}\log(16D/\delta)/\varepsilon,\log(16/\delta)/\alpha^{2}\\}$,
we have

$\displaystyle|\tilde{\mu}-\mu|=O\left(\sqrt{\frac{2\log(16/\delta)}{n}}+\frac{M\log(16/\delta)}{\varepsilon
n}+\left(\frac{2}{M}\right)^{k-1}+\alpha M\right)$

Now, we need to choose $M$ to minimize the above while satisfying $M\geq 4r$.
By standard choice, we set
$M=\min\\{4\left(\frac{n\varepsilon}{\log(1/\delta)}\right)^{1/k},4\alpha^{-1/k}\\}$,
which satisfies $M\geq 4r$ when $n$ and $\alpha$ satisfy

$\displaystyle
n\geq\frac{\iota\log(1/\delta)}{\varepsilon}\quad\text{and}\quad\frac{1}{\alpha}\geq\iota,$

where recall that $\iota=\frac{1-\alpha}{0.249-\alpha}$. Hence, we only have a
valid concentration for $\alpha\in(0,0.133)$.

∎

###### Proof of Theorem 6.10.

Let $\tau_{0}$ be the maximal epoch such that
$B_{\tau}<\frac{200\log(16D|\mathcal{S}|\tau^{2}/\delta)}{\varepsilon}$.

For all epoch $\tau\leq\tau_{0}$, the batch size is less than $2^{\tau_{0}}$.
Since batch size doubles, until epoch $\tau_{0}$, we have the number of pulls
for each arm $a\in[K]$ is less than $2\cdot 2^{\tau_{0}}\leq
2\frac{200\log(16D|\mathcal{S}|\tau_{0}^{2}/\delta)}{\varepsilon}$. Then the
regret has to suffer
$\frac{400\log(16D|\mathcal{S}|\tau_{0}^{2}/\delta)}{\varepsilon}\Delta_{a}$
for each $a\in[K]$.

For $\tau>\tau_{0}$,
$B_{\tau}\geq\frac{200\log(16D|\mathcal{S}|\tau^{2}/\delta)}{\varepsilon}$.
For each $a\in\mathcal{S}$, from Corollary 6.6, we have with probability at
least $1-\frac{\delta}{2|\mathcal{S}|\tau^{2}}$,

$|\tilde{\mu}_{a}-\mu_{a}|\leq\beta_{\tau}.$

Given an epoch $\tau>\tau_{0}$, we denote by $\mathcal{E}_{\tau}$ the event
where for all $a\in\mathcal{S}$ it holds that
$|\tilde{\mu}_{a}-\mu_{a}|\leq\beta_{\tau}.$ and denote
$\mathcal{E}=\cup_{\tau>\tau_{0}}\mathcal{E}_{\tau}$.By taking union bound, we
have

$\mathbb{P}(\mathcal{E}_{\tau})\geq 1-\frac{\delta}{2\tau^{2}},$

and

$\mathbb{P}(\mathcal{E})\geq
1-\frac{\delta}{2}\left(\sum_{\tau>\tau_{0}}\tau^{-2}\right)\geq 1-\delta.$

In the following, we condition on the good event $\mathcal{E}$. We first show
that the optimal arm $a^{*}$ is never eliminated. For any epoch
$\tau>\tau_{0}$, let
$a_{\tau}=\arg\max_{a\in\mathcal{S}}{\widetilde{\mu}_{a}}$. Since

$(\widetilde{\mu}_{a_{\tau}}-\widetilde{\mu}_{a^{*}})+\Delta_{a_{\tau}}=|(\widetilde{\mu}_{a_{\tau}}-\widetilde{\mu}_{a^{*}})+\Delta_{a_{\tau}}|\leq\left|\widetilde{\mu}_{a_{\tau}}-\mu_{a_{\tau}}\right|+\left|\widetilde{\mu}_{a^{*}}-\mu_{a^{*}}\right|\leq
2\beta_{\tau},$

it is easy to see that the algorithm doesn’t eliminate $a^{*}$.

Then, we show that at the end of epoch $\tau>\tau_{0}$, all arms such that
$\Delta_{a}\geq 4\beta_{\tau}$ will be eliminated. To show this, we have that
under good event $\mathcal{E}$,

$\tilde{\mu}_{a}+\beta_{\tau}\leq\mu_{a}+2\beta_{\tau}<\mu_{a^{*}}-4\beta_{\tau}+2\beta_{\tau}\leq\tilde{\mu}_{a^{*}}-\beta_{\tau}\leq\tilde{\mu}_{a_{\tau}}-\beta_{\tau}$

which implies that arm $a$ will be eliminated by the rule. Thus, for each sub-
optimal arm $a$, let $\tau(a)$ be the last epoch that arm $a$ is not
eliminated. By the above result, we have

$\Delta_{a}\leq
4\beta_{\tau(a)}=O\left(\sqrt{\frac{\log(|\mathcal{S}|\tau(a)^{2}/\delta)}{B_{\tau(a)}}}+\left(\frac{\log(|\mathcal{S}|\tau(a)^{2}/\delta)}{B_{\tau(a)}\varepsilon}\right)^{1-\frac{1}{k}}\right).$

Hence, we have

$B_{\tau(a)}\leq
O\left(\frac{\log(|\mathcal{S}|\tau(a)^{2}/\delta)}{\Delta_{a}^{2}}+\frac{\log(|\mathcal{S}|\tau(a)^{2}/\delta)}{\varepsilon}\left(\frac{1}{\Delta_{a}}\right)^{\frac{k}{k-1}}+\frac{\log(D|\mathcal{S}|\tau_{0}^{2}/\delta)}{\varepsilon}\right).$

Since $|\mathcal{S}|\leq K$ and $2^{\tau}\leq T$ for any $\tau$. Thus,

$B_{\tau(a)}\leq
O\left(\frac{\log(K\log^{2}T/\delta)}{\Delta_{a}^{2}},\frac{\log(K\log^{2}T/\delta)}{\varepsilon}\left(\frac{1}{\Delta_{a}}\right)^{\frac{k}{k-1}},\frac{\log(DK\log^{2}T/\delta)}{\varepsilon}\right),$

Since the batch size doubles, we have $N_{a}(T)\leq 2B_{\tau(a)}$ for each
sub-optimal arm $a$. Therefore, for all arm $a\in[K]$,

$\mathcal{R}_{T}=\sum_{a\in[K]}N_{a}(T)\Delta_{a}\leq 2B_{\tau(a)}\Delta_{a}.$

Let $\eta$ be a number in $(0,1)$. For all arms $a\in[K]$ with
$\Delta_{a}\leq\eta$, the regret incurred by pulling these arms is upper
bounded by $T\eta$. For any arm $a\in[K]$ with $\Delta_{a}>\eta$, choose
$\delta=\frac{1}{T}$ and assume $T\geq K$, then the expected regret incurred
by pulling arm $a$ is upper bounded by

$\displaystyle\mathbb{E}\left[\sum_{a\in[K],\Delta_{a}>\eta}\Delta_{a}N_{a}(T)\right]$
$\displaystyle\leq\mathbb{P}(\bar{\mathcal{E}})\cdot
T+O\left(\sum_{{a\in[K],\Delta_{a}>\eta}}\left\\{\frac{\log
T}{\Delta_{a}}+\frac{\log
T}{\varepsilon}\left(\frac{1}{\Delta_{a}}\right)^{\frac{1}{k-1}}+\frac{\log
DT}{\varepsilon}\Delta_{a}\right\\}\right)$ $\displaystyle\leq
O\left(\frac{K\log T}{\eta}+\frac{K\log
T}{\varepsilon\eta^{\frac{1}{k-1}}}+\frac{KD\log(DT)}{\varepsilon}\right)$

where the last term in the last inequality is based on following result: from
the heavy-tailed assumption for rewards distributions in Definition 3.2, we
have for any $a\in[K]$, $\mu_{a}\in[-D,D]$, so $\Delta_{a}=\mu^{*}-\mu_{a}\leq
2D$.

Thus the regret is at most

$T\eta+O\left(\frac{K\log T}{\eta}+\frac{K\log
T}{\varepsilon\eta^{\frac{1}{k-1}}}+\frac{KD\log(DT)}{\varepsilon}\right).$

Taking $\eta=\max\left\\{\sqrt{\frac{K\log T}{T}},\left(\frac{K\log
T}{T\varepsilon}\right)^{\frac{k-1}{k}}\right\\}$, the regret is at most

$O\left(\sqrt{KT\log T}+\left(\frac{K\log
T}{\varepsilon}\right)^{\frac{k-1}{k}}T^{\frac{1}{k}}+\frac{DK\log(DT)}{\varepsilon}\right).$

For privacy guarantee, based on Laplacian mechanism in Definition 3.5, privacy
guarantee for histogram learner in [KV17, Lemma 2.3], parallel composition
theorem in Lemma A.3 and Post-processing in Lemma A.1, we can get the result.

∎

###### Proof of Theorem 6.12.

The proof of the theorem is similar to the proof of Theorem 6.2, now the
requirement for batch size to start to arm elimination becomes
$\max\\{\frac{\iota\log(16/\delta)}{\varepsilon},\frac{c_{1}\log(16D/\delta)}{\varepsilon},\frac{\log(16/\delta)}{\alpha^{2}}\\}$
and the upper bound of $\Delta_{a}$ for each $a\in[K]$ is $2D$. Then we can
get the result of upper bound for regret.

For privacy guarantee, based on Laplacian mechanism in Definition 3.5, privacy
guarantee for histogram learner in [KV17, Lemma 2.3], parallel composition
theorem in Lemma A.3 and Post-processing in Lemma A.1, we can get the result.
∎