# When Privacy Meets Partial Information:
A Refined Analysis of Differentially Private Bandits

Achraf Azize and Debabrota Basu
Équipe Scool, Univ. Lille, Inria,
CNRS, Centrale Lille, UMR 9189- CRIStAL
F-59000 Lille, France
<EMAIL_ADDRESS>

###### Abstract

We study the problem of multi-armed bandits with $\epsilon$-global
Differential Privacy (DP). First, we prove the minimax and problem-dependent
regret lower bounds for stochastic and linear bandits that quantify the
hardness of bandits with $\epsilon$-global DP. These bounds suggest the
existence of two hardness regimes depending on the privacy budget $\epsilon$.
In the high-privacy regime (small $\epsilon$), the hardness depends on a
coupled effect of privacy and partial information about the reward
distributions. In the low-privacy regime (large $\epsilon$), bandits with
$\epsilon$-global DP are not harder than the bandits without privacy. For
stochastic bandits, we further propose a generic framework to design a near-
optimal $\epsilon$-global DP extension of an index-based optimistic bandit
algorithm. The framework consists of three ingredients: the Laplace mechanism,
arm-dependent adaptive episodes, and usage of only the rewards collected in
the last episode for computing private statistics. Specifically, we
instantiate $\epsilon$-global DP extensions of UCB and KL-UCB algorithms,
namely $\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$.
$\mathsf{AdaP\text{-}KLUCB}$ is the first algorithm that both satisfies
$\epsilon$-global DP and yields a regret upper bound that matches the problem-
dependent lower bound up to multiplicative constants.

###  1 Introduction

Multi-armed bandit problems, in short bandits, are a model for sequential
decision-making with partial information (Lattimore and Szepesvári,, 2018). In
bandits, a learner sequentially interacts with an environment, which is a set
of unknown distributions (or arms or actions), over $T\in\mathbb{N}$ steps.
$T$ is referred to as the horizon. At each step
$t\in\left\\{1,\ldots,T\right\\}$, the learner chooses an arm $A_{t}$ from
$\left\\{1,\ldots,K\right\\}$ and the environment reveals a reward $r_{t}$
from the distribution $\nu_{A_{t}}$. The learner’s objective is to maximise
its cumulative reward $\sum_{t=1}^{T}r_{t}$. An equivalent performance metric
for a bandit algorithm $\pi$ is regret. Regret is the difference between the
expected cumulative reward collected by pulling the optimal arm $a^{*}$ for
$T$ times and the expected cumulative reward obtained by using $\pi$. Regret
is the price paid by the bandit algorithm due to partial information about the
reward distributions. The goal of a bandit algorithm is to minimise its
regret. Bandits, introduced in (Thompson,, 1933) for medical trials, are
widely studied and deployed in real-life applications, such as online
advertising (Schwartz et al.,, 2017), recommendation systems (Silva et al.,,
2022) and investment portfolio design (Silva et al.,, 2022). Sensitive data of
individuals, such as health conditions, personal preferences, financial status
etc., are utilised in these applications, which raises the concern about
privacy.

######  Example 1.

In bandit-based recommendation systems, the learning algorithm selects an item
for each user. The user decides whether or not to click the recommendation.
Based on the click feedback, the bandit algorithm improves its subsequent
recommendations. Here, an action corresponds to an item and a reward
corresponds to whether a user clicks on the item ($1$) or not ($0$). A change
in a user’s preference prompts changes in the algorithm’s output. As a result,
even if the click feedback is kept private, the user’s private information,
i.e. their preference over items, is revealed. Privacy protection aims to
prevent the algorithm’s output from revealing the preferences of any specific
user.

This example demonstrates the need for privacy in bandits. In this paper, we
use Differential Privacy (DP) (Dwork and Roth,, 2014) as the framework for
privacy. DP ensures that an algorithm’s output is unaffected by changes in
input at a single data point. By limiting the amount of sensitive information
that an adversary can deduce from the output, DP renders an individual
corresponding to a data point ‘indistinguishable’. A calibrated amount of
noise is injected into an algorithm to ensure DP. The noise scale is set to be
proportional to the algorithm’s sensitivity and inversely proportional to the
privacy budget $\epsilon$.

To address the privacy issues in bandit applications, the problem of
Differentially Private Bandits is coined and studied under different settings,
such as stochastic bandits (Mishra and Thakurta,, 2015; Tossou and
Dimitrakakis,, 2016; Sajed and Sheffet,, 2019; Hu et al.,, 2021), adversarial
bandits (Tossou and Dimitrakakis,, 2017), and linear contextual bandits
(Shariff and Sheffet,, 2018; Neel and Roth,, 2018). Also, multiple adaptations
of DP, namely local and global, are proposed for bandits (Basu et al.,, 2019).
Local DP aims to preserve the privacy of the sequence of rewards obtained by
sending noisy rewards to the algorithm (Duchi et al.,, 2013). Global DP allows
the algorithm to access rewards without noise and aims to keep the sequence of
rewards private while only the sequence of actions taken by the algorithm is
produced to the public (Basu et al.,, 2019). Though local DP provides stronger
privacy as the data curator has no access to the original reward stream, it
injects too much noise that leads to higher regret. Also, the fundamental
hardness of local DP in bandits in terms of regret lower bound and also
corresponding optimal algorithms are well-understood (Zheng et al.,, 2020).
Thus, in this paper, we focus on the bandit problems with $\epsilon$-global
DP. We aim to address two questions:

  1. 1.

What is the fundamental hardness of differentially private bandits with global
DP expressed in terms of the regret lower bound?

  2. 2.

How to design an algorithmic framework that converts an optimistic and near-
optimal bandit algorithm into a near-optimal bandit algorithm satisfying
global DP?

Our Contributions. These questions have led to the following contributions:

1\. Hardness as Lower Bounds: We derive both the minimax (worst-case) and
problem-dependent lower bounds on the regret of bandits with $\epsilon$-global
DP for stochastic bandits (Thm. 2 and 3, Sec. 3). Both the bounds show that
the hardness depends on a trade-off between the privacy budget $\epsilon$ and
the distinguishability gap of a bandit environment. If the $\epsilon$ is
bigger than the distinguishability gap, a bandit with global DP is not harder
than a non-private bandit problem. Additionally, our problem-dependent regret
lower bound (Thm. 3) provides a novel observation that the difficulty of a
bandit problem with global DP depends on the TV-indistinguishability gap
($t_{inf}$, Thm. 3). This was not known in the regret lower bound in (Shariff
and Sheffet,, 2018), where the privacy dependent term in regret, i.e.
$\frac{K\log(T)}{\epsilon}$ is independent of the hardness of the bandit
instance. Our lower bounds explicates this missing link between the
interaction of privacy and partial information. We also extend our techniques
to derive the lower bounds for linear bandits with a finite number of arms
(Thm. 4 and 5). These lower bounds also reflect the same transition of
hardness depending on $\epsilon$ and distinguishability gaps.

2\. Algorithm Design: Optimistic bandit algorithms used the empirical mean and
variance of observed rewards to compute indexes and use them to select an
action. We propose three fundamental strategies to design a private bandit
algorithm from an optimistic algorithm (Sec. 4)– a) add Laplacian noise to the
empirical mean of each arm calibrated by the corresponding sensitivity, b) use
adaptive episodes to compute the private empirical mean less number of times,
and c) use only the observed rewards of the arm’s last active episode111The
last active episode of an arm is the last episode in which that arm was
played. and forget everything before to keep the sensitivity of the empirical
mean low. We deploy these techniques with $\mathsf{UCB}$ (Auer et al.,, 2002)
and $\mathsf{KL\text{-}UCB}$ (Garivier and Cappé,, 2011) algorithms for non-
private bandits to propose two near-optimal and $\epsilon$-global DP bandit
algorithms, $\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$ (Sec.
4). Both of these algorithms achieve near-optimal problem-dependent regret and
also reflect a transition in hardness from a low to a high privacy regime
(Thm. 7 and 8). Both theoretical (Table 1) and experimental (Sec. 5) results
demonstrate optimality of $\mathsf{AdaP\text{-}KLUCB}$ than existing
algorithms.

3\. Technical Tools: (a) To derive the lower bound, we extend the Karwa-Vadhan
lemma (Lemma 6.1, (Karwa and Vadhan,, 2017)) to the sequential setting (Lemma
2). (b) We present a novel sequential information processing lemma under
$\epsilon$-global DP (Thm. 10) that controls the difference between the
outcome streams of a differentially private policy when interacting with two
different bandit instances. (c) This leads to a generic proof structure,
utilised to generate refined regret lower bounds under $\epsilon$-global DP
for different settings. (d) To derive the regret upper bound, we develop a
novel and general analysis of optimistic algorithms with adaptive episodes.

Our regret lower and upper bounds close the open question posed in (Tenenbaum
et al.,, 2021), i.e. the problem-dependent regret bounds of differentially
private bandits should depend on the KL-divergence between the reward
distributions.

Related Works: Lower Bound. (Shariff and Sheffet,, 2018) first proposed a
problem-dependent lower bound on regret, $\Omega(\max\\{\sum_{a\neq
a^{*}}\frac{\log T}{\Delta_{a}},\frac{K\log(T)}{\epsilon}\\})$222Here, $a^{*}$
is the optimal arm with mean reward $\mu^{*}$ and
$\Delta_{a}\mathrel{\triangleq}\mu^{*}-\mu_{a}$ is the suboptimality gap of
arm $a$., for stochastic bandits with $\epsilon$-global DP. But this bound is
restricted to Bernoulli distributions of reward. In this paper, we provide the
first problem-dependent regret lower bound that is valid for any reward
distribution. This lower bound shows that the effect of privacy does not only
depend on $\epsilon$ but also on the total variation distance corresponding to
the environment. Thus, it explicates the coupled effect of privacy and partial
information in a high-privacy regime, which was not observed before. To derive
this tighter lower bound, we extend the Karwa-Vadhan lemma (Lemma 6.1, (Karwa
and Vadhan,, 2017)) to a sequential setting and also propose a generic proof
structure leading to problem-dependent and minimax lower bounds for stochastic
and linear bandits. To our knowledge, these are the first regret lower bounds
for linear bandits with $\epsilon$-global DP. Basu et al., (2019) also
proposed a minimax regret lower bound for stochastic bandits with
$\epsilon$-global DP. However, our minimax lower bound (Thm. 2) is tighter and
does not need to assume that the reward distributions are Lipschitz
continuous.

Related Works: Bandit Algorithms with $\epsilon$-global DP.
$\mathsf{DP\text{-}UCB}$ (Mishra and Thakurta,, 2015; Tossou and
Dimitrakakis,, 2016) was the first global DP version of UCB.
$\mathsf{DP\text{-}UCB}$ uses the tree-based mechanism (Dwork et al., 2010a, ;
Chan et al.,, 2011) to compute the sum of rewards. The tree mechanism
maintains a binary tree of depth $\log(T)$ over the $T$ streaming
observations, where each node in this tree holds an i.i.d sample from a
Laplace distribution with zero mean and scale $\left(\log(T)/\epsilon\right)$.
At each step $t$, the mechanism yields the sum of the first $t$ observations
and the $\log(T)$ nodes on the root-to-the-leaf path in the binary tree as the
private empirical mean. As a result, the noise added to the UCB index per
time-step is $\text{O}\left({\log(T)^{2.5}}/{\epsilon}\right)$, which is
responsible for the extra multiplicative factor $\log(T)^{1.5}$ in regret
compared to the lower bound. $\mathsf{DP\text{-}SE}$ (Sajed and Sheffet,,
2019) was the first $\epsilon$-global DP algorithm to eliminate the additional
multiplicative factor $\log(T)^{1.5}$. $\mathsf{DP\text{-}SE}$ is an
$\epsilon$-global DP version of the Successive Elimination algorithm (Even-Dar
et al.,, 2002). However, the drawbacks were that the algorithm was not
anytime, and was optimal only asymptotically, i.e. the horizon should be big
enough. On the other hand, a careful analysis of the algorithm suggests that
what made the algorithm optimal was the fact that the algorithm was run in
doubling episodes, where the private means computed at the end of the episode
to decide which arms to eliminate, were only computed using the samples
collected from that episode. We detect these ingredients and generalise them
to propose a general framework to make any optimist index-based policy optimal
followed by upper bounds matching the lower bounds (Table 1). Similar
techniques have been deployed to design a global DP extension of UCB in (Hu et
al.,, 2021) but they have an additive factor $\log(T)$ extra in regret than
$\mathsf{AdaP\text{-}UCB}$ and do not match our proposed regret lower bound.
Also, DP-TS (Hu and Hegde,, 2022) aims to achieve $\epsilon$-global DP with a
Thompson sampling based approach. The “lazy" version of DP-TS achieves a
similar regret as $\mathsf{AdaP\text{-}UCB}$, but does not achieve the refined
lower bound of Thm. 3 with the indistinguishability gaps. Even in non-private
bandits, Thompson Sampling (Agrawal and Goyal,, 2013) is not known to achieve
the Kullback-Leibler (KL) indistinguishability gap while KL-UCB (Garivier and
Cappé,, 2011) is known to achieve it. Our work leads to the first near-optimal
bandit algorithm with $\epsilon$-global DP, namely
$\mathsf{AdaP\text{-}KLUCB}$.

Table 1: A comparison of $\epsilon$-global DP algorithms for bandits.

Algorithm | Regret |  # Private Means 333The number of private empirical mean reward statistics computed by the algorithm. | Anytime |  Forgetfulness 444Not using the full history of rewards to compute the private empirical mean reward statistics.
---|---|---|---|---
$\mathsf{DP\text{-}UCB}$ (Mishra and Thakurta, (2015); | $\text{O}\left(\frac{\log(T)^{2.5}}{\epsilon}+\sum_{a\neq a^{*}}\frac{\log(T)}{\Delta_{a}}\right)$ | $KT$ | Yes | No
Tossou and Dimitrakakis, (2016)) |  |  |  |
$\mathsf{DP\text{-}SE}$ | $\text{O}\left(\frac{K\log(T)}{\epsilon}+\sum_{a\neq a^{*}}\frac{\log(T)}{\Delta_{a}}\right)$ | $\text{O}(\log(T))$ | No | Yes
(Sajed and Sheffet,, 2019) |  |  |  |
$\mathsf{AdaP\text{-}UCB}$ | $\text{O}\left(\sum_{a\neq a^{*}}\frac{\Delta_{a}\log(T)}{\min(\Delta_{a}^{2},\epsilon\Delta_{a})}\right)$ | $\text{O}(\log(T))$ | Yes | Yes
$\mathsf{AdaP\text{-}KLUCB}$ | $\text{O}\left(\sum_{a\neq a^{*}}\frac{\Delta_{a}\log(T)}{\min(d(\mu_{a},\mu^{*}),\epsilon\Delta_{a})}\right)$ | $\text{O}(\log(T))$ | Yes | Yes

###  2 Background: Differential Privacy and Bandits

Differential Privacy (DP). DP renders an individual corresponding to a datum
indistinguishable by constraining the output of an algorithm to be almost the
same under a change in one input datum.

######  Definition 1 ($(\epsilon,\delta)$-DP (Dwork and Roth,, 2014)).

A randomised algorithm $\mathcal{A}$ satisfies
$(\epsilon,\delta)$-Differential Privacy (DP) if for any two neighbouring
datasets555Neighbouring datasets differ only in one entry, i.e
$\|\mathcal{D}-\mathcal{D^{\prime}}\|_{\mathrm{Hamming}}=1$. $\mathcal{D}$ and
$\mathcal{D}^{\prime}$, and for all sets of output
$\mathcal{O}\subseteq\mathrm{Range}(\mathcal{A})$

$\operatorname{Pr}[\mathcal{A}(\mathcal{D})\in\mathcal{O}]\leq
e^{\epsilon}\operatorname{Pr}\left[\mathcal{A}\left(\mathcal{D}^{\prime}\right)\in\mathcal{O}\right]+\delta,$
(1)

where the probability space is over the coin flips of the mechanism
$\mathcal{A}$ and for some $(\epsilon,\delta)\in^{\geq 0}\times^{\geq 0}$. If
$\delta=0$, we say that $\mathcal{A}$ satisfies _$\epsilon$ -differential
privacy_.

The Laplace mechanism (Dwork et al., 2010b, ; Dwork and Roth,, 2014) ensures
$\epsilon$-DP by injecting a random noise to the output of the algorithm that
is sampled from a calibrated Laplace distribution (as specified in Theorem 1).
We use $Lap(b)$ to denote the Laplace distribution with mean 0 and variance
$2b^{2}$.

######  Theorem 1 ($\epsilon$-DP of Laplace Mechanism (Theorem 3.6, Dwork and
Roth, (2014))).

Let us consider an algorithm $f:\mathcal{X}\rightarrow^{d}$ with sensitivity
$s(f)\mathrel{\triangleq}\underset{\begin{subarray}{c}\mathcal{D},\mathcal{D^{\prime}}\text{
s.t
}\|\mathcal{D}-\mathcal{D^{\prime}}\|_{\mathrm{Hamming}}=1\end{subarray}}{\max}\|f(\mathcal{D})-f(\mathcal{D^{\prime}})\|_{1}$.
Here, $\left\|\cdot\right\|_{1}$ is the $L_{1}$ norm on d. If $d$ noise
samples $\left\\{N_{i}\right\\}_{i=1}^{d}$ are generated independently from
$Lap(\frac{s(f)}{\epsilon})$, the output injected with the noise, i.e.
$f(\mathcal{D})+[N_{1},\ldots,N_{d}]$ satisfies $\epsilon$-DP.

The Laplace mechanism is originally proposed to ensure DP when the input
database is static. In a sequential setting like bandits, a mechanism must
update the published statistics as new data items arrive, and thus DP
definitions are extended accordingly (Basu et al.,, 2019).

Stochastic Bandits with Global DP. Now, we describe the general canonical
bandit model (Section 4.6, (Lattimore and Szepesvári,, 2018)) and define
global Differential Privacy (global DP) in this setting. A bandit algorithm
(or policy) interacts with an environment $\nu$ consisting of $K$ arms with
reward distributions $\left\\{\nu_{a}\right\\}_{a=1}^{K}$ for a given horizon
$T$ and produces a history
$\mathcal{H}_{T}\mathrel{\triangleq}\\{(A_{t},R_{t})\\}_{t=1}^{T}$. At each
step $t$, the choice of the arm depends on the previous history
$\mathcal{H}_{t-1}$. The reward $R_{t}$ is sampled from the reward
distribution $\nu_{A_{t}}$ and is conditionally independent of the previous
history $\mathcal{H}_{t-1}$. Thus, a bandit algorithm (or policy) $\pi$ can be
represented by a sequence $(\pi_{t})_{t=1}^{T}$ , where
$\pi_{t}:\mathcal{H}_{t-1}\rightarrow[K]$ is a probability kernel. Thus, we
denote the probability of occurrence of a sequence of actions
$a^{T}\mathrel{\triangleq}[a_{1},\ldots,a_{T}]$ given a sequence of rewards
$r^{T}\triangleq[r_{1},\ldots,r_{T}]$ as $\pi(a^{T}\mid
r^{T})\mathrel{\triangleq}\prod_{t=1}^{T}\pi_{t}(a_{t}\mid
a_{1},r_{1},\dots,a_{t-1},r_{t-1})$. If we consider $a^{T}$ as the output of a
bandit algorithm and $r^{T}$ as the input, $\pi(a^{T}\mid r^{T})$ defines the
corresponding probability distribution on the output space required for
defining DP (Eq. (1)). In order to define DP in the sequential setup of
bandits, the event-level privacy under continuous observations (Dwork et al.,
2010b, ) framework is adopted. In this framework, if two data sequences differ
on a single entry at a single time-step $t$ and are identical on all other
time-steps, they are called neighbouring data sequences. A sequential
algorithm is differentially private if its output sequence is not
distinguishable from two neighbouring input sequences. This framework leads to
the global DP definition for bandits (Mishra and Thakurta,, 2015; Basu et
al.,, 2019).

######  Definition 2 (Global DP for Bandits).

A bandit algorithm $\pi\in\Pi^{\epsilon}$ satisfies $\epsilon$-global DP, if
$\pi(a^{T}\mid r^{T})\leq e^{\epsilon}\pi(a^{T}\mid r^{\prime T})$ for every
action sequence $a^{T}\in[K]^{T}$ and every two neighbouring reward sequences
$r^{T},r^{\prime T}\in^{T}$, which means that $\exists j\in[1,T]$ such that
$r_{j}\neq r^{\prime}_{j}$ and $\forall$ $t\neq j$ $r_{t}=r^{\prime}_{t}$. The
set of all bandit algorithms satisfying $\epsilon$-global DP, i.e.
$\Pi^{\epsilon}$, is called the $\epsilon$-global DP policy class.

Now, we formally define the regret of a bandit algorithm with
$\epsilon$-global DP, namely $\pi^{\epsilon}$, as

$\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)\mathrel{\triangleq}T\mu^{*}(\nu)-\mathop{\mbox{$\mathbb{E}$}}\nolimits_{\nu\pi}\left[\sum_{t=1}^{T}R_{t}\right]\mathrel{\triangleq}\sum_{a=1}^{K}\Delta_{a}\mathbb{E}_{\nu\pi}\left[N_{a}(T)\right].$
(2)

$N_{a}(T)\mathrel{\triangleq}\sum_{t=1}^{T}\mathds{1}\left\\{A_{t}=a\right\\}$
is the number of times the arm $a$ is played till $T$.
$\Delta_{a}\mathrel{\triangleq}\mu^{*}(\nu)-\mu_{a}$ is the suboptimality gap
of the arm $a$. The expectation is taken with respect to the probability
measure on action-reward sequences induced by the interaction of
$\pi^{\epsilon}$ and $\nu$. The objective of the bandit algorithm
$\pi^{\epsilon}$ is to satisfy $\epsilon$-global DP while minimising the
regret over horizon $T$. A regret lower bound of any $\epsilon$-global DP
bandit algorithm in $\Pi^{\epsilon}$ quantifies the fundamental hardness of
this problem.

Table 2: Regret lower bounds for bandits with $\epsilon$-global DP

| Minimax | Problem Dependent
---|---|---
Stochastic Multi-armed bandit | $\max\biggl{(}\frac{1}{27}\sqrt{T(K-1)},\frac{1}{131}\frac{K-1}{\epsilon}\biggr{)}$ | $\sum_{a:\Delta_{a}>0}\frac{\Delta_{a}\log(T)}{\min(d_{a},6\epsilon t_{a})}$
Stoachastic Linear bandit | $\max\biggl{(}\exp(-2),\exp(-6\epsilon d\sqrt{T})\biggr{)}\frac{d}{8}\sqrt{T}$ |  $\inf_{\alpha\in[0,\infty)^{\mathcal{A}}}\sum_{a\in\mathcal{A}}\alpha(a)\Delta_{a}\log(T)$ $\text{ s.t. }\|a\|_{H_{\alpha}^{-1}}^{2}\leq\Delta_{a}\min\left(\frac{\Delta_{a}}{2},3\epsilon\rho(\mathcal{A})\right)$

###  3 Regret Lower Bounds for Bandits with $\epsilon$-global DP

The first question is how much additional regret we have to endure in bandits
with $\epsilon$-global DP than the bandits without privacy. The lower bound on
regret provides insight into the intrinsic hardness of the problem and serves
as a target for the optimal algorithm design. In this section, we prove
minimax and problem-dependent lower bounds for stochastic and linear bandits
under $\epsilon$-global DP. The proposed lower bounds are summarised in Table
2. We defer the proof details to the supplementary.

##### Stochastic Bandits.

First, we consider the stochastic bandit problem with $K$-arms (as in Section
2).

Minimax Regret. We derive the minimax regret lower bound in this bandit
setting with $\epsilon$-global DP. Minimax regret is the lowest achievable
regret by any bandit algorithm under the worst environment among a family of
environments $\mathcal{E}^{K}$ with $K$ arms under consideration.

$\mathrm{Reg}_{T,\epsilon}^{\text{minimax}}=\inf_{\pi^{\epsilon}\in\Pi^{\epsilon}}\sup_{\nu\in\mathcal{E}^{K}}\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)$

######  Theorem 2 (Minimax lower bound).

For any $K>1$ and $T\geq K-1$, and $\epsilon>0$, the minimax regret of
stochastic bandits with $\epsilon$-global DP satisfies

$\mathrm{Reg}_{T,\epsilon}^{\text{minimax}}\geq\max\bigg{\\{}\frac{1}{27}\underset{\text{without
global DP}}{\underbrace{\sqrt{T(K-1)}}},\leavevmode\nobreak\
\leavevmode\nobreak\ \frac{1}{131}\underset{\text{with $\epsilon$-global
DP}}{\underbrace{\frac{K-1}{\epsilon}}}\bigg{\\}}.$ (3)

Consequences of Theorem 2. Equation (3) shows two regimes of hardness: high-
privacy, corresponding to lower values of $\epsilon$, and low-privacy,
corresponding to higher values of $\epsilon$. In the high-privacy regime,
specifically for $\epsilon<\frac{131}{27}\sqrt{\frac{(K-1)}{T}}$, the hardness
depends only on the number of the arms $K$ and the privacy budget $\epsilon$
and is higher than the lower bound for bandits without privacy. In the low-
privacy regime, i.e. for $\epsilon\geq\frac{131}{27}\sqrt{\frac{(K-1)}{T}}$,
the lower bound coincides with that of the bandits without privacy. This
indicates the phenomena that for higher values of $\epsilon$, signifying lower
privacy, bandits with global DP is not harder than the bandits without
privacy. Specially, for significantly large $T$, the threshold between low and
high privacy regime is smaller than most of the practically used privacy
budget values. For example, if $T=10^{6}$ and $K=100$, the bandits with and
without global DP are equivalently hard for any privacy budget $\epsilon\geq
0.05$. This shows that for stochastic bandits, we can deploy very low privacy
budgets ($\epsilon$) without loosing anything in performance.

Problem-dependent Regret: Similar to the lower bounds specific to the
Bernoulli reward distributions (Shariff and Sheffet,, 2018), the minimax bound
indicates a separation between hardness due to global DP and partial
information. To understand whether this observation is an artefact of the
Bernoulli distribution and the worst-case environment considered in minimax
bounds, we derive a lower bound on the problem-dependent regret (Equation (2))
for general reward distributions.

Before deriving the lower bound, we define two information-theoretic terms
that quantify the distinguishability of the specific bandit environment $\nu$
where the algorithm is operating from all other bandit environments with $K$
arms and finite means. If $\mathcal{M}$ is a set of distributions with finite
means, and $\mu(P)$ is the mean of the reward distribution $P\in\mathcal{M}$,
we define the KL-distinguishability gap as
$d_{\inf}\left(P,\mu^{*},\mathcal{M}\right)\mathrel{\triangleq}\inf_{P^{\prime}\in\mathcal{M}}\left\\{D_{\mathrm{KL}}\left(P\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\
P^{\prime}\right):\mu\left(P^{\prime}\right)>\mu^{*}\right\\}$ and the TV-
distinguishability gap as
$t_{\inf}\left(P,\mu^{*},\mathcal{M}\right)\mathrel{\triangleq}\inf_{P^{\prime}\in\mathcal{M}}\left\\{\mathrm{TV}\left(P\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\
P^{\prime}\right):\mu\left(P^{\prime}\right)>\mu^{*}\right\\}$. These two
quantities indicate the minimum dissimilarity, in terms of KL-divergence and
Total Variation (TV) distance, of the reward distribution of the optimal arm
$a^{*}$ with any other distribution with finite mean higher than $\mu^{*}$.
For bandits without DP, inverse of the KL-distinguishability gap quantifies
the hardness to identify the optimal arm of the environment $\nu$ under
partial information (Lai and Robbins,, 1985).

######  Theorem 3 (Problem-dependent Regret Lower Bound).

Let the environment $\mathcal{E}$ be a set of $K$ reward distributions with
finite means and a policy $\pi^{\epsilon}\in\Pi_{\text{cons
}}(\mathcal{E})\cap\Pi^{\epsilon}$ be a consistent policy666A policy $\pi$ is
called consistent over a class of bandits $\mathcal{E}$ if for all
$\nu\in\mathcal{E}$ and $p>0$, it holds that
$\lim_{T\rightarrow\infty}\frac{R_{T}(\pi,\nu)}{T^{p}}=0$. We denote the class
of consistent policies over a set of environments $\mathcal{E}$ as
$\Pi_{\text{cons }}(\mathcal{E})$. over $\mathcal{E}$ satisfying
$\epsilon$-global DP . Then, for all
$\nu=\left(P_{i}\right)_{i=1}^{K}\in\mathcal{E}$, it holds that

$\displaystyle\liminf_{T\rightarrow\infty}\frac{\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)}{\log(T)}$
$\displaystyle\geq\sum_{a:\Delta_{a}>0}\frac{\Delta_{a}}{\min\biggl{(}\underset{\text{without
global
DP}}{\underbrace{d_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}},\underset{\text{with
$\epsilon$-global
DP}}{\underbrace{6\,\epsilon\,t_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}}\biggl{)}}.$
(4)

Consequences of Theorem 3. Now, we summarise the interesting observations led
by the lower bound.

1\. Universality: The lower bound of Theorem 3 holds for any environment with
$K$ arms and reward distributions with finite means. This is the first general
lower bound for bandits with $\epsilon$-global DP.

2\. For Bernoulli distributions of reward: TV-distinguishability gap
$t_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)=\Delta_{a}$, i.e. the
suboptimality gap of arm $a$, and the KL-distinguishability gap
$d_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)\geq 2\Delta_{a}^{2}$.
Thus, our problem-dependent lower bound reduces to $\Omega(\sum_{a\neq
a^{*}}\frac{\log T}{\min\\{\Delta_{a},\epsilon\\}})$. For Bernoulli rewards,
our lower bound is able to retrieve the lower bound of (Shariff and Sheffet,,
2018) with explicit constants.

3\. High- and Low-privacy Regimes: Like the minimax regret bound, the problem-
dependent regret also indicates two clear regimes in regret due to high and
low privacy (resp. small and large privacy budgets $\epsilon$). In the low-
privacy regime, i.e. for
$\epsilon\geq\frac{d_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}{6t_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}$,
the regret achievable by bandits with global DP and without global DP are
same. Thus, there is no loss in performance due to privacy in this regime. In
the high-privacy regime, i.e. for
$\epsilon<\frac{d_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}{6t_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}$,
the regret depends on a coupled effect of privacy and partial information.
This effect is quantified by the inverse of the privacy budget times inverse
of the TV-distinguishability gap. This interaction between privacy and partial
information was not explicated by any of the existing lower bounds. In Section
4, we propose the $\mathsf{AdaP\text{-}KLUCB}$ algorithm that demonstrates the
same interactive effect in its regret upper bound.

##### Stochastic Linear Bandits.

In order to illustrate the generality of our results, and also to investigate
how partial information and privacy in structured bandits, we derive minimax
and problem-dependent regret lower bounds for stochastic linear bandits
(Lattimore and Szepesvari,, 2017). To perform the regret analysis, we consider
a simple linear model with parameter $\theta\in\mathbb{R}^{d}$ and Gaussian
noise. It implies that for an action
$A_{t}\in\mathcal{A}\subseteq\mathbb{R}^{d}$ the reward is $R_{t}=\left\langle
A_{t},\theta\right\rangle+\eta_{t}$, where $\eta_{t}\sim\mathcal{N}(0,1)$ is a
sequence of independent Gaussian noises. The regret of a policy is
$\mathrm{Reg}_{T}(\mathcal{A},\theta)\mathrel{\triangleq}\mathbb{E}_{\theta}\left[\sum_{t=1}^{T}\Delta_{A_{t}}\right]$,
where suboptimality gap
$\Delta_{a}\mathrel{\triangleq}\max_{a^{\prime}\in\mathcal{A}}\left\langle
a^{\prime}-a,\theta\right\rangle$, and $\mathbb{E}_{\theta}[\cdot]$ is the
expectation with respect to the measure on outcomes induced by the interaction
of the policy and the linear bandit determined by $\theta$. Given this
structure, we state the minimax and problem-dependent regret lower bounds for
stochastic linear bandits.

######  Theorem 4 (Minimax regret lower bound).

Let $\mathcal{A}=[-1,1]^{d}$ and
$\Theta=\left\\{-T^{-1/2},T^{-1/2}\right\\}^{d}$. Then, there exists a vector
$\theta\in\Theta$ leading to a minimax regret of linear bandits with
$\epsilon$-global DP such that

$\displaystyle\mathrm{Reg}^{\text{minimax}}_{T}(\mathcal{A},\Theta)\geq\max\big{\\{}\underset{\text{without
global DP}}{\underbrace{\exp(-2)}},\leavevmode\nobreak\ \leavevmode\nobreak\
\underset{\text{with $\epsilon$-global DP}}{\underbrace{\exp(-6\epsilon
d\sqrt{T})}}\big{\\}}\frac{d}{8}\sqrt{T}.$ (5)

######  Theorem 5 (Problem-dependent regret lower bound).

Let $\mathcal{A}\subset\mathbb{R}^{d}$ be a finite set spanning
$\mathbb{R}^{d}$ and $\theta\in\mathbb{R}^{d}$ be such that there is a unique
optimal action. Then, for any consistent and $\epsilon$-global DP bandit
algorithm satisfies

$\liminf_{T\rightarrow\infty}\frac{\mathrm{Reg}_{T}(\mathcal{A},\theta)}{\log(T)}\geq
c(\mathcal{A},\theta),$ (6)

where the _structural distinguishability gap_ is the solution of a constraint
optimisation

$c(\mathcal{A},\theta)\mathrel{\triangleq}\inf_{\alpha\in[0,\infty)^{\mathcal{A}}}\sum_{a\in\mathcal{A}}\alpha(a)\Delta_{a},\text{
such that
}\|a\|_{H_{\alpha}^{-1}}^{2}\leq\min\bigg{\\{}\underset{\text{without global
DP}}{\underbrace{0.5\Delta_{a}^{2}}},\leavevmode\nobreak\ \leavevmode\nobreak\
\underset{\text{with $\epsilon$-global
DP}}{\underbrace{3\epsilon\rho_{a}(\mathcal{A})\Delta_{a}}}\bigg{\\}}$

for all $a\in\mathcal{A}$ with $\Delta_{a}>0$,
$H_{\alpha}=\sum_{a\in\mathcal{A}}\alpha(a)aa^{\top}$, and a structure
dependent constant $\rho_{a}(\mathcal{A})$.

Remarks. Theorems 4 and 5 are the first minimax and problem-dependent regret
lower bounds for linear bandits. The minimax regret bound also shows a clear
distinction between high- and low-privacy regimes for
$\epsilon<1/(3d\sqrt{T})$ and $\epsilon\geq 1/(3d\sqrt{T})$. Interestingly,
the threshold between two regimes decreases with increase in dimension $d$ and
allows us to use quite low values of $\epsilon$ without losing any
performance. The difference between high- and low-privacy regimes is more
subtle. The first constraint on $\|a\|_{H_{\alpha}^{-1}}^{2}$ is reminiscent
of the Graves-Lai bound for structural bandits without privacy. The second
constraint, i.e. $3\epsilon\rho_{a}(\mathcal{A})\Delta_{a}$, captures the
interaction between privacy and partial information under linear structure and
in the high-privacy regime.

##### Proof Technique.

In order to prove the lower bounds, we adopt the general canonical bandit
model. The high level idea of proving bandit lower bounds is selecting two
hard environments, which are hard to be statistically distinguished but are
conflicting, i.e. actions that may be optimal in one is suboptimal in other.
This is quantified by upper bounding the per-step KL-divergence between action
distributions for such hard environments, and then plugging in this upper
bound in the Bretagnolle-Huber inequality to obtain a regret lower bound.
Though this proof technique works to quantify the hardness due to partial
information, we need to upper bound the “confusion" created due to global DP.
Existing proofs use the information-processing lemma of Karwa-Vadhan (Karwa
and Vadhan,, 2017). Though this works for Bernoulli bandits, to proof a
general bound, we derive a sequential version of this lemma. The sequential
version leads to an upper bound of the KL-divergence dependent on both total-
variation distinguishability gap and privacy budget, and enables us to show
the coupled effect of privacy and partial-information in the high-privacy
regimes. For details of the technical results, we refer to the Supplementary
Material.

###  4 Stochastic Bandit Algorithms with $\epsilon$-global DP:
$\mathsf{AdaP\text{-}UCB}$ & $\mathsf{AdaP\text{-}KLUCB}$

In this section, we present a framework (Algorithm 1) to convert index-based
optimistic algorithms into algorithms satisfying $\epsilon$-global DP. We
instantiate this framework by proposing $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$, and derive corresponding regret upper bounds.

Algorithm 1 A framework for $\epsilon$-global DP extension of an index-based
bandit algorithm

1:Input: Privacy budget $\epsilon$, an environment $\nu$ with $K$ arms,
parameter $\alpha>3$

2:Output: A sequence of $T$-actions satisfying $\epsilon$-global DP

3:Initialisation: Choose each arm once and assign $t=K$

4:for $\ell=1,2,\dots$ do $\triangleright$ Adaptive episodes of reward
subsequences

5: Let $t_{\ell}=t+1$

6: Compute
$A_{\ell}=\operatorname{argmax}_{a}\operatorname{I}_{a}^{\epsilon}(t_{\ell}-1,\alpha)$
$\triangleright$ Arm selection with private indexes (Eqn. (7)-(8))

7: Choose arm $A_{\ell}$ until round t such that $T_{i}(t)=2T_{i}(t_{\ell}-1)$
$\triangleright$ Doubling of episodes

8:end for

Index-Based Algorithms and Private Empirical Mean. We focus on index-based
bandit algorithms that compute the empirical mean of rewards of each arm at
each step. Using the empirical means, they compute an optimistic index for
each arm that serves as a high-probability upper confidence bound on the true
mean of the corresponding arm. Examples of such algorithms with empirical
mean-based indexes include UCB (Auer et al.,, 2002), MOSS (Audibert and
Bubeck,, 2010), KL-UCB (Garivier and Cappé,, 2011), IMED (Honda and Takemura,,
2015) etc. Here, the empirical mean is the main statistics of reward sequences
used by the algorithms. Thus, by post-processing lemma, designing an
$\epsilon$-global DP bandit algorithm reduces to computing the empirical means
privately.

By Theorem 1, we know that adding a Laplacian noise with scale
${s(\hat{\mu}_{t})}/{\epsilon}$ to each empirical mean turns it $\epsilon$-DP,
where $s(\hat{\mu}_{t})$ is the sensitivity of empirical mean $\hat{\mu}_{t}$
at step $t$. For $K$ arms and horizon $T$, an index-based bandit algorithm
computes the empirical mean $KT$ times. Using the naïve composition of
$\epsilon$-DP, a first baseline is to make each computed empirical mean
$\frac{\epsilon}{KT}$-DP. This needs us to add at each step noise scaled
linearly to $T$. This might lead the corresponding bandit algorithm to yield a
linear regret. Thus, we need to add noise less number of times and with lower
sensitivity.

Empirical Mean using Reward Sub-sequence. The improvement is invoked by the
observation that a bandit algorithm does not need to calculate the empirical
mean at each time-step using all the rewards observed till that step. Thus,
motivated by the DP-SE (Sajed and Sheffet,, 2019), we calculate the empirical
mean less number of times by exploiting an episodic structure that we will
explicit later. Specifically, we use only the rewards of the last episode. We
formally express this trick in Lemma 1.

######  Lemma 1.

Let us define the private empirical mean of the rewards between steps $i$ and
$j$ $(i<j)$ as

$\displaystyle
f^{\epsilon}\\{r_{i},\dots,r_{j}\\}\mathrel{\triangleq}\frac{1}{j-i}\sum_{t=i}^{j}r_{t}+Lap\left(\frac{1}{(j-i)\epsilon}\right).$

If $1<t_{1}<\cdots<t_{\ell}<T$ and $r_{t}\in[0,1]$, the mechanism
$g^{\epsilon}$ mapping the sequence of rewards $(r_{1},r_{2},\ldots,r_{T})$ to
$(\ell+1)$-private empirical means
$(f^{\epsilon}\\{r_{1},\dots,r_{t_{1}-1}\\},f^{\epsilon}\\{r_{{t_{1}}},\dots,r_{t_{2}-1}\\},$
$\ldots,f^{\epsilon}\\{r_{{t_{\ell}}},\dots,r_{T}\\})$ satisfies
$\epsilon$-DP.

Lemma 1 implies that, if we calculate the empirical mean of each arm
$\ell+1\leavevmode\nobreak\ (\ll T)$ times on non-overlapping sub-sequences of
the reward stream, we only need to ensure that each empirical mean is
$\epsilon$-DP with respect to the corresponding reward sub-sequence. These
$(\ell+1)$ private empirical means together ensure that the sequence of
$(\ell+1)$ computed indexes and the resultant action sequence of length $T$
satisfy $\epsilon$-global DP by the post-processing lemma (Dwork and Roth,,
2014). Thus, we divide the horizon into $(\ell+1)$-episodes. This allows us to
take $T$ actions only by computing $\ell+1$ private empirical means with the
rewards observed in the last active episode of the arm. Specifically, for each
$t\in[t_{i},t_{i+1}-1]$, we play the same arm that was decided at the
beginning of the episode, i.e. at $t_{i}$, with the private empirical mean
computed from the last active episode of that arm.

Adaptive Episodes with Doubling. In order to set the episode lengths, we focus
on the specific structure of the bandit process. Specifically, we know that a
sub-optimal arm $a$ should be sampled at least
$n_{a}=\text{O}\left(\frac{\log(T)}{\Delta_{a}^{2}}\right)$ times before
discarding. Since the empirical means are computed using only rewards of one
episode, to yield a near-optimal regret, the length of the episode should be
greater at any given time than $n_{a}$. To satisfy this criterion, we deploy
adaptive episodes with doubling.

######  Example 2 (Illustration of Algortihm 1.).

To clarify the schematic, we illustrate a few steps of executing Algorithm 1
in Figure 1. After playing each arm once, the first episode begins at $t_{1}$.
To observe different ingredients, we focus on step $t_{4}=7$. The index of Arm
1 at $t_{4}$ uses the private empirical mean
$\frac{r_{4}+r_{5}}{2}+Lap(\frac{1}{2\epsilon})$ to build a high probability
upper bound of the real mean $\mu_{1}$ with confidence $t_{4}^{-\alpha}$. The
index of Arm 2 uses $r_{6}+Lap(\frac{1}{\epsilon})$. If we assume that the
index of Arm 1 is higher at $t_{4}$, Arm 1 is played for a full episode from
$t_{4}$ until $t_{5}-1$. The last time, when Arm 1 was played, the length of
the episode was $2$. Thus, following $t_{4}$, the length of the episode is
doubled to $4$.

######  Theorem 6 ($\epsilon$-global DP).

For any private index $I^{\epsilon}_{a}$ computed using the private empirical
mean of the rewards collected in the last active episode of arm $a$, Algorithm
1 satisfies $\epsilon$-global DP.

###### Proof.

The main idea is that a change in reward will only affect the empirical mean
calculated in one episode, which is made private using the Laplace Mechanism
and Lemma 1. Since the actions are only calculated using the private empirical
means, the algorithm is $\epsilon$-global DP following the post-processing
lemma. We refer to Appendix D for a complete proof. ∎

Now, to concretise an algorithm, we only need to explicit how the indexes are
calculated. In other words, we need to build a high-probability upper
confidence bound on the true mean of an arm only using a private empirical
mean. We instantiate the design details for $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$.

Step $t$ Arm 1Arm
2$r_{1}$$r_{2}$$t_{1}$$r_{3}$$t_{2}$$r_{4}$$r_{5}$$t_{3}$$r_{6}$$t_{4}$$r_{7}$$r_{8}$$r_{9}$$r_{10}$$t_{5}$$r_{11}$$r_{12}$

Figure 1: An illustration of adaptive episodes with per-arm doubling.

$\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$. Let
$\hat{\mu}_{a}^{\ell}$ be the empirical mean reward of arm $a$ computed using
the samples collected between $t_{\psi_{a}(\ell)}$ and
$t_{\psi_{a}(\ell)+1}-1$. For an episode $\ell$, $\psi_{a}(\ell)=\ell_{a}$ is
the last active episode of arm $a$. In Example 2, $\psi_{1}(4)=2$ and
$\psi_{2}(4)=3$. Thus, due to the doubling of episode length, the empirical
mean corresponds to $\frac{1}{2}N_{a}(t_{\ell}-1)$ samples of arm $a$. Since
the rewards are in $[0,1]$, the private empirical mean as
$\tilde{\mu}_{a,\epsilon}^{\ell}=\hat{\mu}_{a}^{\ell}+Lap\left(\frac{2}{\epsilon
N_{a}(t_{\ell}-1)}\right)$ satisfies $\epsilon$-DP (Theorem 1). Now, we want
to ensure that $\operatorname{I}_{a}^{\epsilon}(t_{\ell}-1,\alpha)$, computed
using only $\tilde{\mu}_{a,\epsilon}^{\ell}$, is a high-probability upper
bound on the true mean. Here, we introduce two specific indexes that satisfy
this criterion.

$\displaystyle\text{For
{$\mathsf{AdaP\text{-}UCB}$}:}\qquad\quad\leavevmode\nobreak\
\operatorname{I}_{a}^{\epsilon}(t_{\ell}-1,\alpha)=\tilde{\mu}_{a,\epsilon}^{\ell}+\sqrt{\frac{\alpha\log(t_{\ell})}{2\times\frac{1}{2}N_{a}(t_{\ell}-1)}}+\frac{\alpha\log(t_{\ell})}{\epsilon\times\frac{1}{2}N_{a}(t_{\ell}-1)}$
(7) $\displaystyle\text{For
{$\mathsf{AdaP\text{-}KLUCB}$}:}\qquad\operatorname{I}_{a}^{\epsilon}(t_{\ell}-1,\alpha)=\max\left\\{q\in[0,1]:d\left(\breve{\mu}_{a,\epsilon}^{\ell,\alpha},q\right)\leq\frac{\alpha\log(t_{\ell})}{\frac{1}{2}N_{a}(t_{\ell}-1)}\right\\},$
(8)

where
$\breve{\mu}_{a,\epsilon}^{\ell,\alpha}=\operatorname{Clip}_{0,1}\left(\tilde{\mu}_{a,\epsilon}^{\ell}+\frac{\alpha\log(t_{\ell})}{\epsilon\frac{1}{2}N_{a}(t_{\ell}-1)}\right)=\min\\{\max\\{0,\tilde{\mu}_{a,\epsilon}^{\ell}+\frac{\alpha\log(t_{\ell})}{\epsilon\times\frac{1}{2}N_{a}(t_{\ell}-1)}\\},1\\}$
is the private empirical mean clipped between zero and one.

######  Theorem 7.

For rewards in $[0,1]$, $\mathsf{AdaP\text{-}UCB}$ satisfies $\epsilon$-global
DP, and for $\alpha>3$, it yields a regret

$\mathrm{Reg}_{T}({\mathsf{AdaP\text{-}UCB}}{},\nu)\leq\sum_{a:\Delta_{a}>0}\left(\frac{16\alpha}{\min\\{\Delta_{a},\epsilon\\}}\log(T)+\frac{3\alpha}{\alpha-3}\right).$

######  Theorem 8.

When the rewards are sampled from Bernoulli distributions,
$\mathsf{AdaP\text{-}KLUCB}$ satisfies $\epsilon$-global DP, and for
$\alpha>3$ and constants $C_{1}(\alpha),C_{2}>0$, it yields a regret

$\mathrm{Reg}_{T}({\mathsf{AdaP\text{-}KLUCB}}{},\nu)\leq\sum_{a:\Delta_{a}>0}\left(\frac{C_{1}(\alpha)\Delta_{a}}{\min\\{d_{\mathrm{inf}}(\mu_{a},\mu^{*}),C_{2}\epsilon\Delta_{a}\\}}\log(T)+\frac{3\alpha}{\alpha-3}\right).$

Both the upper bounds show that for low-privacy regime, the regrets of
$\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$ are independent of
$\epsilon$, and in high-privacy regime, they depend on the coupled effect. In
Appendix E.4, we also derive problem-independent or minimax regret upper
bounds for $\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$, which
are $\text{O}(\sqrt{KT\log(T)}+\frac{K\log(T)}{\epsilon})$.

######  Remark 1.

$\alpha$ controls the width of the optimistic confidence bound. Specifically,
it dictates that the real mean is smaller than the optimistic index with high
probability, i.e. with probability $1-\frac{1}{t^{\alpha}}$ at step $t$. The
requirement that $\alpha>3$ is due to our analysis of the algorithm. To be
specific, the requirement that $\alpha>3$ is needed to use a sum-integral
inequality in the proof of Theorem 11. Since the dominant terms in the regret
upper bounds of both $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$ are multiplicative in $\alpha$, making $\alpha$
smaller will tighten the bound. We leave it for future work. We refer to
Section G.3 for a detailed discussion on choosing $\alpha$.

Summary of Algorithm Design. We propose three ingredients to design an
$\epsilon$-global DP version of a bandit algorithm (Algo. 1). Firstly, add
Laplace noise to make the empirical means private (Lemma 1). Secondly,
computed the index of an arm using the private empirical mean of rewards
collected from the last active episode of that arm and forget all the samples
obtained before that. Thirdly, use adaptive episodes with doubling. At the
beginning of an episode choose the arm with the highest index and play it
double number of times than the length of the last active episode of the arm.

###  5 Experimental Analysis

$\displaystyle{0.0}$$\displaystyle{0.2}$$\displaystyle{0.4}$$\displaystyle{0.6}$$\displaystyle{0.8}$$\displaystyle{1.0}$Step
$\displaystyle
t$$\displaystyle\times{10^{7}}{}$$\displaystyle{10^{-1}}$$\displaystyle{10^{0}}$$\displaystyle{10^{1}}$$\displaystyle{10^{2}}$$\displaystyle{10^{3}}$$\displaystyle{10^{4}}$$\displaystyle{10^{5}}$RegretDP-
UCB($\displaystyle\gamma=0.1$)DP-SEAdaP-UCB($\displaystyle\alpha=3.1$)AdaP-
KLUCB($\displaystyle\alpha=3.1$)

Figure 2: Evolution of regret over time for $\mathsf{DP\text{-}UCB}$,
$\mathsf{DP\text{-}SE}$, $\mathsf{AdaP\text{-}UCB}$, and
$\mathsf{AdaP\text{-}KLUCB}$ with $\epsilon=1$. Each algorithm is run $20$
times with $T=10^{7}$, and Bernoulli distributions with means
$\\{0.75,0.625,0.5,0.375,0.25\\}$. $\mathsf{AdaP\text{-}KLUCB}$ achieves the
lowest regret.

$\displaystyle{10^{-1}}$$\displaystyle{10^{0}}$$\displaystyle{10^{1}}$Privacy
budget
$\displaystyle\epsilon$$\displaystyle{10^{2}}$$\displaystyle{10^{3}}$Regret
for $\displaystyle T=10^{7}$High PrivacyLow Privacyno privacyglobal DPAdap-
KLUCB

Figure 3: Dependence of lower bounds and regret of
$\mathsf{AdaP\text{-}KLUCB}$ with respect to the privacy budget $\epsilon$. We
run $\mathsf{AdaP\text{-}KLUCB}$ for $20$ runs with $T=10^{7}$. Echoing the
theoretical analysis, regret of $\mathsf{AdaP\text{-}KLUCB}$ transits between
privacy regimes and is independent of $\epsilon$ for low-privacy.

In this section, we perform empirical evaluations to test two hypotheses: (i)
$\mathsf{AdaP\text{-}KLUCB}$ is the most optimal algorithm among the existing
bandit algorithms with $\epsilon$-global DP, and (ii) the transition between
high and low-privacy regimes are reflected in the upper bounds. Additional
experimental results are deferred to Appendix G.

Efficiency in Performance. First, we compare performances of
$\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$ with those of
$\mathsf{DP\text{-}SE}$ and $\mathsf{DP\text{-}UCB}$. We set $\alpha=3.1$ to
comply with the regret upper bounds of $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$. We assign $\gamma=0.1$ for
$\mathsf{DP\text{-}UCB}$ and $\beta=1/T$ for $\mathsf{DP\text{-}SE}$. We
implement all the algorithms in Python (version $3.8$) and on an 8 core
64-bits Intel<EMAIL_ADDRESS>GHz CPU. We test the algorithms for Bernoulli bandits
with $5$-arms and means $\\{0.75,0.625,0.5,0.375,0.25\\}$ (as in Sajed and
Sheffet, (2019)). We run each algorithm $20$ times for a horizon $T=10^{7}$,
and plot corresponding average and standard deviations of regrets in Figure 2.
$\mathsf{AdaP\text{-}KLUCB}$ achieves the lowest regret followed by
$\mathsf{AdaP\text{-}UCB}$. Both of them attain almost $10$ times lower regret
than the competing algorithms.

Impact of Privacy Regimes. In Figure 3, we plot regret of
$\mathsf{AdaP\text{-}KLUCB}$ at $T=10^{7}$ for a Bernoulli bandit with mean
rewards $\\{0.8,0.1,0.1,0.1,0.1\\}$. We plot the average regret over $20$ runs
as a function of the privacy budget $\epsilon\in[0.05,10]$. As indicated by
the theoretical regret lower bounds and upper bounds, the experimental
performance of $\mathsf{AdaP\text{-}KLUCB}$ demonstrates two regimes: a high-
privacy regime (for $\epsilon<0.3$), where the regret of
$\mathsf{AdaP\text{-}KLUCB}$ depends on the privacy budget $\epsilon$, and a
low privacy regime (for $\epsilon>0.3$), where the regret of
$\mathsf{AdaP\text{-}KLUCB}$ does not depend on $\epsilon$.

In brief, our experimental results validate that $\mathsf{AdaP\text{-}KLUCB}$
is the most optimal algorithm for stochastic bandits that satisfies
$\epsilon$-global DP, and performance of $\mathsf{AdaP\text{-}KLUCB}$ transits
from high- to low-privacy regimes, where its performance turns independent of
the privacy budget $\epsilon$.

###  6 Conclusion and Future Works

We revisit bandits with $\epsilon$-global DP. We prove the minimax and
problem-dependent regret lower bounds for stochastic and linear bandits
indicating two regimes of hardness. We propose a framework to design an
$\epsilon$-global DP version of an index-based optimistic bandit algorithm in
a near-optimal fashion by utilising three ingredients: adding noise with
Laplace Mechanism, using the empirical mean of rewards collected in the last
active episode of an arm, and adapting episodes with doubling.

One limitation of our analysis that the lower and upper bounds defer by
multiplicative constants. It would be a technical challenge to merge this gap.
Another future direction is to derive regret lower bounds for other variants
of DP, namely $(\epsilon,\delta)$-DP and Rényi-DP (Mironov,, 2017), especially
in the structured bandits compatible with Gaussian noise injection and also to
extend the proposed proof techniques in these settings. For the algorithm
design, it would be interesting to see how the proposed ingredients generalise
to linear and contextual bandits (Shariff and Sheffet,, 2018), and Markov
Decision Processes (Vietri et al.,, 2020).

### Acknowledgments and Disclosure of Funding

Achraf Azize acknowledges the AI_PhD@Lille grant for support. We also thank
Philippe Preux for his support in this work.

### References

  * Agrawal and Goyal, (2013) Agrawal, S. and Goyal, N. (2013).  Thompson sampling for contextual bandits with linear payoffs.  In International conference on machine learning, pages 127–135. PMLR.
  * Audibert and Bubeck, (2010) Audibert, J.-Y. and Bubeck, S. (2010).  Regret bounds and minimax policies under partial monitoring.  The Journal of Machine Learning Research, 11:2785–2836.
  * Auer et al., (2002) Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002).  Finite-time analysis of the multiarmed bandit problem.  Machine learning, 47(2-3):235–256.
  * Basu et al., (2019) Basu, D., Dimitrakakis, C., and Tossou, A. (2019).  Differential privacy for multi-armed bandits: What is it and what is its cost?  arXiv preprint arXiv:1905.12298.
  * Chan et al., (2011) Chan, T.-H. H., Shi, E., and Song, D. (2011).  Private and continual release of statistics.  ACM Trans. Inf. Syst. Secur., 14(3).
  * Duchi et al., (2013) Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013).  Local privacy, data processing inequalities, and statistical minimax rates.  arXiv preprint arXiv:1302.3203.
  * (7) Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010a).  Differential privacy under continual observation.  In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 715–724, New York, NY, USA. Association for Computing Machinery.
  * (8) Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. (2010b).  Differential privacy under continual observation.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715–724. ACM.
  * Dwork and Roth, (2014) Dwork, C. and Roth, A. (2014).  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407.
  * Even-Dar et al., (2002) Even-Dar, E., Mannor, S., and Mansour, Y. (2002).  PAC bounds for multi-armed bandit and Markov decision processes.  In Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT ’02, page 255–270, Berlin, Heidelberg. Springer-Verlag.
  * Garivier and Cappé, (2011) Garivier, A. and Cappé, O. (2011).  The KL-UCB algorithm for bounded stochastic bandits and beyond.  In Proceedings of the 24th annual conference on learning theory, pages 359–376. JMLR Workshop and Conference Proceedings.
  * Honda and Takemura, (2015) Honda, J. and Takemura, A. (2015).  Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards.  J. Mach. Learn. Res., 16:3721–3756.
  * Hu and Hegde, (2022) Hu, B. and Hegde, N. (2022).  Near-optimal thompson sampling-based algorithms for differentially private stochastic bandits.  In Uncertainty in Artificial Intelligence, pages 844–852. PMLR.
  * Hu et al., (2021) Hu, B., Huang, Z., and Mehta, N. A. (2021).  Optimal algorithms for private online learning in a stochastic environment.
  * Karwa and Vadhan, (2017) Karwa, V. and Vadhan, S. (2017).  Finite sample differentially private confidence intervals.
  * Lai and Robbins, (1985) Lai, T. L. and Robbins, H. (1985).  Asymptotically efficient adaptive allocation rules.  Advances in applied mathematics, 6(1):4–22.
  * Lattimore and Szepesvari, (2017) Lattimore, T. and Szepesvari, C. (2017).  The end of optimism? An asymptotic analysis of finite-armed linear bandits.  In Artificial Intelligence and Statistics, pages 728–737. PMLR.
  * Lattimore and Szepesvári, (2018) Lattimore, T. and Szepesvári, C. (2018).  Bandit algorithms.  preprint.
  * Mironov, (2017) Mironov, I. (2017).  Rényi differential privacy.  In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263–275. IEEE.
  * Mishra and Thakurta, (2015) Mishra, N. and Thakurta, A. (2015).  (Nearly) optimal differentially private stochastic multi-arm bandits.  In UAI.
  * Neel and Roth, (2018) Neel, S. and Roth, A. (2018).  Mitigating bias in adaptive data gathering via differential privacy.  In International Conference on Machine Learning, pages 3720–3729. PMLR.
  * Sajed and Sheffet, (2019) Sajed, T. and Sheffet, O. (2019).  An optimal private stochastic-MAB algorithm based on an optimal private stopping rule.
  * Schwartz et al., (2017) Schwartz, E. M., Bradlow, E. T., and Fader, P. S. (2017).  Customer acquisition via display advertising using multi-armed bandit experiments.  Marketing Science, 36(4):500–522.
  * Shariff and Sheffet, (2018) Shariff, R. and Sheffet, O. (2018).  Differentially private contextual linear bandits.  In Advances in Neural Information Processing Systems, pages 4296–4306.
  * Silva et al., (2022) Silva, N., Werneck, H., Silva, T., Pereira, A. C., and Rocha, L. (2022).  Multi-armed bandits in recommendation systems: A survey of the state-of-the-art and future directions.  Expert Systems with Applications, 197:116669.
  * Tenenbaum et al., (2021) Tenenbaum, J., Kaplan, H., Mansour, Y., and Stemmer, U. (2021).  Differentially private multi-armed bandits in the shuffle model.  Advances in Neural Information Processing Systems, 34:24956–24967.
  * Thompson, (1933) Thompson, W. R. (1933).  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25(3-4):285–294.
  * Tossou and Dimitrakakis, (2016) Tossou, A. C. and Dimitrakakis, C. (2016).  Algorithms for differentially private multi-armed bandits.  In Thirtieth AAAI Conference on Artificial Intelligence.
  * Tossou and Dimitrakakis, (2017) Tossou, A. C. and Dimitrakakis, C. (2017).  Achieving privacy in the adversarial multi-armed bandit.  In Thirty-First AAAI Conference on Artificial Intelligence.
  * Vietri et al., (2020) Vietri, G., Balle, B., Krishnamurthy, A., and Wu, S. (2020).  Private reinforcement learning with PAC and regret guarantees.  In International Conference on Machine Learning, pages 9754–9764. PMLR.
  * Zheng et al., (2020) Zheng, K., Cai, T., Huang, W., Li, Z., and Wang, L. (2020).  Locally differentially private (contextual) bandits learning.

##  Part Appendix

###  Appendix A The Canonical Model of Bandits

We extend the general canonical model of bandits (Chapter 4, Lattimore and
Szepesvári, (2018)) with $\epsilon$-global differential privacy. The canonical
model with $\epsilon$-global DP consists of a privacy-preserving policy
$\pi^{\epsilon}$ and an environment $\nu$. The policy interacts with the
environment up to a given time horizon $T$ to produce a history
$\mathcal{H}_{T}\mathrel{\triangleq}\\{(A_{t},R_{t})\\}_{t=1}^{T}$. The
iterative steps of this interaction process are:

  1. 1.

the probability of choosing an action $A_{t}=a$ at time $t$ is dictated only
by the policy $\pi^{\epsilon}(a|\mathcal{H}_{t-1})$,

  2. 2.

the distribution of reward $R_{t}$ is $P_{A_{t}}$ and is conditionally
independent of the previous observed history $\mathcal{H}_{t-1}$.

Let us formalise this interaction by defining an $\epsilon$-global DP policy,
the environment and the probability space produced by this interaction.

Let $T\in\mathbb{N}$ be the horizon. Let $\nu=(P_{a}:a\in[K])$ a bandit
instance with $K$ arms. For each $t\in[T]$, let
$\Omega_{t}=([K]\times)^{t}\subset^{2t}$ and
$\mathcal{F}_{t}=\mathfrak{B}(\Omega_{t})$ with $\mathfrak{B}$ being the Borel
set.

######  Definition 3.

A policy $\pi$ is a sequence $(\pi_{t})_{t=1}^{T}$ , where $\pi_{t}$ is a
probability kernel from $(\Omega_{t},\mathcal{F}_{t})$ to $([K],2^{[K]})$.
Since $[K]$ is discrete, we adopt the convention that for $i\in[K]$,

$\pi_{t}(i\mid a_{1},r_{1},\dots,a_{t-1},r_{t-1})=\pi_{t}(\\{i\\}\mid
a_{1},r_{1},\dots,a_{t-1},r_{t-1})$

and for a sequence of actions $a^{T}\triangleq[a_{1},\ldots,a_{T}]$ and a
sequence of rewards $r^{T}\triangleq[r_{1},\ldots,r_{T}]$:

$\pi(a^{T}\mid r^{T})=\prod_{t=1}^{T}\pi_{t}(a_{t}\mid
a_{1},r_{1},\dots,a_{t-1},r_{t-1})$

A policy $\pi^{\epsilon}$ is $\epsilon$-global DP, if

$\pi^{\epsilon}(a^{T}\mid r^{T})\leq e^{\epsilon}\pi^{\epsilon}(a^{T}\mid
r^{\prime T})$

for every sequence of actions $a^{T}$ and every two neighbouring reward
streams $r^{T}$, $r^{\prime T}$: $\exists j\in[1,T]$ such that $r_{j}\neq
r^{\prime}_{j}$ and $\forall$ $t\neq j$ $r_{t}=r^{\prime}_{t}$.

Let $\lambda$ be a $\sigma$-finite measure on $(,\mathfrak{B}())$ for which
$P_{a}$ is absolutely continuous with respect to $\lambda$ for all $a\in[K]$.
Let $p_{a}=dP_{a}/d\lambda$ be the Radon–Nikodym derivative of $P_{a}$ with
respect to $\lambda$, which is a function $p_{a}:\rightarrow$ such that
$\int_{B}p_{a}d\lambda=P_{a}(B)$ for all $B\in\mathfrak{B}()$. Letting $\rho$
be the counting measure with $\rho(B)=|B|$, the density
$p_{\nu\pi^{\epsilon}}:\Omega_{T}\rightarrow$ can now be defined with respect
to the product measure $(\rho\times\lambda)^{T}$ by

$p_{\nu\pi^{\epsilon}}(a_{1},r_{1},\dots,a_{T},r_{T})\mathrel{\triangleq}\prod_{t=1}^{T}\pi_{t}(a_{t}\mid
a_{1},r_{1},\dots,a_{t-1},r_{t-1})p_{a_{t}}(r_{t})$

and $\mathcal{P}_{\nu\pi^{\epsilon}}$ be defined by

$\mathcal{P}_{\nu\pi^{\epsilon}}(B)\mathrel{\triangleq}\int_{B}p_{\nu\pi^{\epsilon}}(\omega)(\rho\times\lambda)^{T}(\,\mathrm{d}\omega)\quad\textrm{for
all }B\in\mathcal{F}_{T}$

Hence $(\Omega_{T},\mathcal{F}_{T},\mathcal{P}_{\nu\pi^{\epsilon}})$ is a
probability space over histories induced by the interaction between
$\pi^{\epsilon}$ and $\nu$.

We define also a marginal distribution over sequence of actions by

$m_{\nu\pi^{\epsilon}}(a_{1},\dots,a_{T})\mathrel{\triangleq}\int_{r_{1},\dots,r_{T}}p_{\nu\pi^{\epsilon}}(a_{1},r_{1},\dots,a_{T},r_{T})\,\mathrm{d}r_{1}\dots\,\mathrm{d}r_{T},$

and $\textrm{for all }C\in\mathcal{P}([K]^{T})$,

$M_{\nu\pi^{\epsilon}}(C)\mathrel{\triangleq}\sum_{(a_{1},\dots,a_{T})\in
C}m_{\nu\pi^{\epsilon}}(a_{1},a_{2},\dots,a_{T}).$

Hence, $([K]^{T},\mathcal{P}([K]^{T}),M_{\nu\pi^{\epsilon}})$ is a probability
space over sequence of actions produced when $\pi^{\epsilon}$ interacts with
$\nu$ for $T$ time-steps.

###  Appendix B Distinguishing Environments with Partial Information and
Global DP

In this section, we first revisit the Karwa-Vadhan Lemma (Lemma 6.1, (Karwa
and Vadhan,, 2017)) that bounds the multiplicative distance between marginal
distributions induced by a differentially private mechanism, when the datasets
are generated using two different distributions $\mathbb{P}$ and $\mathbb{Q}$.
We generalise this result to the setting where the inputs are not identically
distributed. We call this Sequential Karwa-Vadhan Lemma (Lemma 2) and apply it
to upper bound the Kullback-Leibler (KL) divergence between the marginal
distributions $M_{\nu\pi^{\epsilon}}$ and $M_{\nu^{\prime}\pi^{\epsilon}}$,
when $\pi^{\epsilon}$ is an $\epsilon$-global DP policy, and $\nu$ and
$\nu^{\prime}$ are two different environments (Theorem 10).

##### Karwa-Vadhan Lemma.

Let $\mathbb{P}$ and $\mathbb{Q}$ be two distributions, and
$\mathrm{TV}\left(\mathbb{P}\leavevmode\nobreak\ \middle\|\leavevmode\nobreak\
\mathbb{Q}\right)$ be the total variation distance between these two
distributions. Let $\mathcal{M}$ be an $(\epsilon,\delta)$-differentially
private mechanism that runs on the set of samples $\\{x_{1},\ldots,x_{T}\\}$.
For any event $E$ in $\mathcal{M}$’s output space,
$\mathcal{M}(E|X_{1}=x_{1},\ldots,X_{T}=x_{T})$ denotes the probability that
$\mathcal{M}$ outputs an element in $E$ given the input $x_{1},\ldots,x_{T}$,
and

$\mathbb{M}_{\mathbb{P}}(E)\mathrel{\triangleq}\int{\mathcal{M}(E|X_{1},\ldots,X_{T})\,\mathrm{d}\mathbb{P}(X_{1},\ldots,X_{T})}$

is the marginal distribution induced by the DP mechanism when the data is
generated from the distribution $\mathbb{P}$.

######  Theorem 9 (Lemma 6.1, Karwa and Vadhan, (2017)).

If a mechanism $\mathcal{M}$ satisfies $(\epsilon,\delta)$-DP, then for every
event $E$ in the output space of $\mathcal{M}$, the marginal distributions
induced by distributions $\mathbb{P}$ and $\mathbb{Q}$ satisfy

$\mathbb{M}_{\mathbb{P}}(E)\leq
e^{\epsilon^{\prime}}\mathbb{M}_{\mathbb{Q}}(E)+\delta^{\prime},$

where $\epsilon^{\prime}\mathrel{\triangleq}(6\epsilon
T)\mathrm{TV}\left(\mathbb{P}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{Q}\right)$ and
$\delta^{\prime}\mathrel{\triangleq}(4e^{\epsilon^{\prime}}T\delta)\mathrm{TV}\left(\mathbb{P}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{Q}\right)$.

We extend this result for the setting where the data is not identically
distributed.

####  B.1 Sequential Karwa-Vadhan Lemma

Let $\\{\mathbb{P}_{1},\dots,\mathbb{P}_{T}\\}$ and
$\\{\mathbb{Q}_{1},\dots,\mathbb{Q}_{T}\\}$ two sets of independent
distributions.

Given the samples $X_{1},\dots,X_{T}$ generated from the distributions
$\mathbb{P}_{1},\dots,\mathbb{P}_{T}$, we define the corresponding marginal
distribution induced by $\mathcal{M}$ as

$\mathbb{M}_{\mathbb{P}_{1},\dots,\mathbb{P}_{T}}(E)\mathrel{\triangleq}\int{\mathcal{M}(E|X_{1},\ldots,X_{T})\,\mathrm{d}\mathbb{P}_{1}(X_{1})\,\mathrm{d}\mathbb{P}_{2}(X_{2})\ldots\,\mathrm{d}\mathbb{P}_{T}(X_{T})}$

######  Lemma 2 (Sequential Karwa-Vadhan Lemma).

If $\mathcal{M}$ is a mechanism satisfying $(\epsilon,\delta)$-DP, then for
every event $E$ in the output space of $\mathcal{M}$, the marginal
distributions induced by the two sets of independent distributions
$\\{\mathbb{P}_{1},\dots,\mathbb{P}_{T}\\}$ and
$\\{\mathbb{Q}_{1},\dots,\mathbb{Q}_{T}\\}$ satisfy

$\mathbb{M}_{\mathbb{P}_{1},\dots,\mathbb{P}_{T}}(E)\leq
e^{\epsilon^{\prime}}\mathbb{M}_{\mathbb{Q}_{1},\dots,\mathbb{Q}_{T}}(E)+\delta^{\prime},$

where
$\epsilon^{\prime}=6\epsilon\sum_{i=1}^{T}\mathrm{TV}\left(\mathbb{P}_{i}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{Q}_{i}\right)$ and
$\delta^{\prime}=4e^{\epsilon^{\prime}}\delta\sum_{i=1}^{T}\mathrm{TV}\left(\mathbb{P}_{i}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{Q}_{i}\right)$

###### Proof.

We extend the proof proposed by (Karwa and Vadhan,, 2017) to the non-identical
distribution setting. The main observation is that the proof follows naturally
if the data is generated from different distributions by just adapting the
coupling to the case of different distributions. For completeness, we present
the whole proof with all the adapted changes.

We construct a coupling between $\bigotimes_{i=1}^{T}\mathbb{P}_{i}$ and
$\bigotimes_{i=1}^{T}\mathbb{Q}_{i}$ that allows us to control the hamming
distance between samples generated from this distributions.

Let us denote
$p_{i}\mathrel{\triangleq}\mathrm{TV}\left(\mathbb{P}_{i}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{Q}_{i}\right)$,
$F_{i}\mathrel{\triangleq}\max(\mathbb{P}_{i}-\mathbb{Q}_{i},0)$,
$G_{i}\mathrel{\triangleq}\max(\mathbb{Q}_{i}-\mathbb{P}_{i},0)$, and
$C_{i}\mathrel{\triangleq}\min(\mathbb{P}_{i},\mathbb{Q}_{i})$. It is easy to
see that $\mathbb{P}_{i}=F_{i}+C_{i}$ and $\mathbb{Q}_{i}=G_{i}+C_{i}$.

Given the aforementioned notations, we consider the following algorithm to
generate $2T$ samples:

  1. For $i=1$ to $T$, generate $H_{i}$ from $\text{Bernoulli}(p_{i})$

    1. (a)

If $H_{i}=1$, sample $X_{i}\propto F_{i}$ and $X_{i}^{\prime}\propto G_{i}$

    2. (b)

If $H_{i}=0$, sample $X_{i}\propto C_{i}$ and set $X_{i}^{\prime}=X_{i}$.

Here $X_{i}\propto F_{i}$ means that $X_{i}$ is generated from a distribution
defined by normalizing $F_{i}$.

This construction satisfies the following properties:

  1. 1.

$\underline{X}\mathrel{\triangleq}(X_{1},\ldots,X_{T}){\sim}\bigotimes_{i=1}^{T}\mathbb{P}_{i}\triangleq\mathbb{D}_{0}$.

  2. 2.

$\underline{X}^{\prime}\mathrel{\triangleq}(X_{1}^{\prime},\ldots,X_{T}^{\prime}){\sim}\bigotimes_{i=1}^{T}\mathbb{Q}_{i}\triangleq\mathbb{D}_{1}$.

  3. 3.

$\|\underline{X}-\underline{X^{\prime}}\|_{\mathrm{Hamming}}=\sum_{i=1}^{T}H_{i}\triangleq
H$.

Now, we introduce the following shorthand for the marginal distributions at
step $h$

$m_{j}(h)\mathrel{\triangleq}\int_{\underline{x}}\mathcal{M}(E|\underline{X}=\underline{x})\,\mathrm{d}\mathbb{D}_{j}(\underline{X}|H=h)$

for $j\in\\{0,1\\}$ and $p(h)=\mathbb{P}(H=h)$. For $j\in\\{0,1\\}$ and any
event $E$, we have, by definition,

$\mathbb{M}_{j}(E)=\sum_{h=0}^{T}m_{j}(h)p(h)$

##### Fact 1:

For $j\in\\{0,1\\}$, $m_{j}(h)\leq e^{\epsilon}m_{j}(h-1)+\delta$ for
$h=1,\ldots,T$, and $m_{1}(0)=m_{0}(0)$.

We defer the proof of Fact 1 to the end of this proof.

By Fact 1, for $j\in\\{0,1\\}$, we have

$m_{j}(h)\leq
e^{h\epsilon}m_{j}(0)+\frac{e^{h\epsilon}-1}{e^{\epsilon}-1}\delta$

Now, we obtain

$\displaystyle\mathbb{M}_{j}(E)$ $\displaystyle=\sum_{h=0}^{T}p(h)m_{j}(h)$
$\displaystyle=\mathbb{E}[m_{j}(H)]$
$\displaystyle\leq\mathbb{E}[e^{H\epsilon}m_{j}(0)+\frac{e^{H\epsilon}-1}{e^{\epsilon}-1}\delta]$
$\displaystyle=m_{j}(0)\cdot\mathbb{E}[e^{H\epsilon}]+\frac{\delta}{e^{\epsilon}-1}\cdot\left(\mathbb{E}[e^{H\epsilon}]-1\right)$
$\displaystyle=m_{j}(0)\cdot\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{\epsilon})+\frac{\delta}{e^{\epsilon}-1}\cdot\left(\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{\epsilon})-1\right)$ (9)

The last equality holds due to that fact that for any $t>0$,
$\mathbb{E}[e^{tH}]=\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot e^{t})$.

Similarly, we obtain

$\displaystyle\mathbb{M}_{j}(E)\geq m_{j}(0)\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{-\epsilon})+\frac{\delta}{e^{-\epsilon}-1}\cdot\left(\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{-\epsilon})-1\right)$ (10)

Combining inequalities B.1 and 10, we get

$\displaystyle\mathbb{M}_{0}(E)\leq$
$\displaystyle\left[\prod_{i=1}^{T}\left(\frac{1-p_{i}+p_{i}\cdot
e^{\epsilon}}{1-p_{i}+p_{i}\cdot
e^{-\epsilon}}\right)\right]\cdot\left(\mathbb{M}_{1}(E)+\frac{1-\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{-\epsilon})}{1-e^{-\epsilon}}\cdot\delta\right)$
$\displaystyle+\frac{\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{-\epsilon})-1}{e^{\epsilon}-1}\cdot\delta$ (11)

From Lemma 6.1 of (Karwa and Vadhan,, 2017), we know that

$\log\left(\frac{1-p_{i}+p_{i}\cdot e^{\epsilon}}{1-p_{i}+p_{i}\cdot
e^{-\epsilon}}\right)\leq 6\epsilon p_{i},$

Thus,

$\displaystyle\prod_{i=1}^{T}\left(\frac{1-p_{i}+p_{i}\cdot
e^{\epsilon}}{1-p_{i}+p_{i}\cdot e^{-\epsilon}}\right)\leq
e^{6\epsilon\sum_{i=1}^{T}p_{i}}\triangleq e^{\epsilon^{\prime}},$ (12)

and

$\displaystyle
e^{\epsilon^{\prime}}\cdot\frac{1-\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{-\epsilon})}{1-e^{-\epsilon}}\cdot\delta+\frac{\prod_{i=1}^{T}(1-p_{i}+p_{i}\cdot
e^{\epsilon})-1}{e^{\epsilon}-1}\cdot\delta$ (13) $\displaystyle\leq
e^{\epsilon^{\prime}}\cdot\frac{1-\exp(2(\sum_{i=1}^{T}p_{i})\cdot(e^{-\epsilon}-1))}{1-e^{-\epsilon}}\cdot\delta+\frac{\exp(2(\sum_{i=1}^{T}p_{i})\cdot(e^{\epsilon}-1))-1}{e^{\epsilon}-1}\cdot\delta$
(14) $\displaystyle\leq e^{\epsilon^{\prime}}\cdot
2(\sum_{i=1}^{T}p_{i})\cdot\delta+2(\sum_{i=1}^{T}p_{i})\cdot\delta$ (15)
$\displaystyle\leq e^{\epsilon^{\prime}}\cdot
4\sum_{i=1}^{T}p_{i}\cdot\delta.$ (16)

Substituting Equations (12) and (16) in Equation 11, we obtain

$\mathbb{M}_{0}(E)\leq
e^{\epsilon^{\prime}}\mathbb{M}_{1}(E)+\delta^{\prime},$

where $\epsilon^{\prime}=6\epsilon(\sum_{i=1}^{T}p_{i})$ and
$\delta^{\prime}=4e^{\epsilon^{\prime}}\delta(\sum_{i=1}^{T}p_{i})$. ∎ Now, we
prove Fact 1.

######  Fact 1.

For $j\in\\{0,1\\}$, $m_{j}(h)\leq e^{\epsilon}m_{j}(h-1)+\delta$ for
$h=1,\ldots,T$, and $m_{1}(0)=m_{0}(0)$.

###### Proof.

We prove the claim for $j=0$, the other case is similar.

First, let us introduce some notations. Fix a
$(h_{1},\ldots,h_{T})\in\\{0,1\\}^{T}$. Let
$I^{\prime}\mathrel{\triangleq}\\{i:h_{i}=1\\}$,
$J\mathrel{\triangleq}\\{i:h_{i}=0\\}$, and $r$ be any fixed index in
$I^{\prime}$. Let $I=I^{\prime}/\\{r\\}$ and consider the following partition
of $\underline{X}$ into three parts:

$\underline{X}=(\underline{X}_{I},X_{r},\underline{X}_{J}),$

where $\underline{X}_{I}$ is the vector $\underline{X}$ specified by the
indices in $I$. By definition of the coupling,
$\underline{X}_{I}\sim\bigotimes_{i\in I}F_{i}\triangleq F_{I}$, $X_{r}\sim
F_{r}$, $\underline{X}_{J}\sim\bigotimes_{i\in J}C_{i}\triangleq C_{J}$. Now,
let $X^{\prime}_{r}\sim C_{r}$ and

$\underline{X}^{\prime}=(\underline{X}_{I},X^{\prime}_{r},\underline{X}_{J}).$

Also, let $h_{1}^{\prime},\ldots,h_{T}^{\prime}$ be the binary indicators
corresponding to $\underline{X}^{\prime}$. By construction, we have the
following properties:

  1. 1.

$h_{i}=h_{i}^{\prime}$ for all $i\neq r$

  2. 2.

$h_{r}=1$ and $h_{r}=0$

  3. 3.

$\sum_{i=1}^{T}h_{i}=h$ and $\sum_{i=1}^{T}h_{i}^{\prime}=h-1$

  4. 4.

$\mathbb{D}_{j}(\underline{X}|H_{1}=h_{1},\ldots,H_{T}=h_{T})=\mathbb{P}_{F_{I}}(\underline{X}_{I})\mathbb{P}_{F_{r}}(X_{r})\mathbb{P}_{C_{J}}(\underline{X}_{J})$

  5. 5.

$\mathbb{D}_{j}(\underline{X}^{\prime}|H_{1}=h^{\prime}_{1},\ldots,H_{T}=h^{\prime}_{T})=\mathbb{P}_{F_{I}}(\underline{X}_{I})\mathbb{P}_{C_{r}}(X^{\prime}_{r})\mathbb{P}_{C_{J}}(\underline{X}_{J})$

Thus, we obtain

$\displaystyle\int_{\underline{x}}\mathcal{M}(E|\underline{X}=\underline{x})\,\mathrm{d}\mathbb{D}_{j}(\underline{X}|H_{1}=h_{1},\ldots
H_{T}=h_{T})$
$\displaystyle=\int_{\underline{x}_{I}}\int_{x_{r}}\int_{\underline{x}_{J}}\mathcal{M}(E|\underline{x}_{I},x_{r},\underline{x}_{J})\,\mathrm{d}\mathbb{P}_{F_{I}}(\underline{X}_{I})\,\mathrm{d}\mathbb{P}_{F_{r}}(X_{r})\,\mathrm{d}\mathbb{P}_{C_{J}}(\underline{X}_{J})$
$\displaystyle\leq\int_{x_{r}^{\prime}}\int_{\underline{x}_{I}}\int_{x_{r}}\int_{\underline{x}_{J}}\left(e^{\epsilon}\mathcal{M}(E|\underline{x}_{I},x^{\prime}_{r},\underline{x}_{J})+\delta\right)\,\mathrm{d}\mathbb{P}_{F_{I}}(\underline{X}_{I})\,\mathrm{d}\mathbb{P}_{F_{r}}(X_{r})\,\mathrm{d}\mathbb{P}_{C_{r}}(X_{r}^{\prime})\,\mathrm{d}\mathbb{P}_{C_{J}}(\underline{X}_{J})$
$\displaystyle\leq\int_{\underline{x}_{I}}\int_{x_{r}^{\prime}}\int_{\underline{x}_{J}}\left(e^{\epsilon}\mathcal{M}(E|\underline{x}_{I},x^{\prime}_{r},\underline{x}_{J})+\delta\right)\,\mathrm{d}\mathbb{P}_{F_{I}}(\underline{X}_{I})\,\mathrm{d}\mathbb{P}_{C_{r}}(X_{r}^{\prime})\,\mathrm{d}\mathbb{P}_{C_{J}}(\underline{X}_{J})$
$\displaystyle\leq
e^{\epsilon}\int_{\underline{x}^{\prime}}\mathcal{M}(E|\underline{X}=\underline{x}^{\prime})\,\mathrm{d}\mathbb{D}_{j}(\underline{X}^{\prime}|H_{1}=h^{\prime}_{1},\ldots
H_{T}=h^{\prime}_{T})+\delta.$

Taking expectations on both sides with respect to $(H_{1},\ldots,H_{T})$
proves the claim.

∎

####  B.2 KL-divergence Decomposition with $\epsilon$-global DP

The Sequential Karwa-Vadhan Lemma (Lemma 2) allows us to show the maximum KL-
divergence induced in the distributions of actions by a global DP policy
$\pi^{\epsilon}$. The upper bound allows us to show how different the final
distributions over actions induced by a global DP policy are for two different
environments. Thus, in turn, it provides an information-theoretic limit on
distinguishability of two environments if $\pi^{\epsilon}$ is played.

######  Theorem 10 (Upper Bound on KL-divergence for Bandits with
$\epsilon$-global DP).

When an $\epsilon$-global DP policy $\pi^{\epsilon}$ interacts with two bandit
instances $\nu=(P_{a}:a\in[K])$ and $\nu^{\prime}=(P_{a}^{\prime}:a\in[K])$ we
have:

$D_{\mathrm{KL}}\left(M_{\nu\pi^{\epsilon}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ M_{\nu^{\prime}\pi^{\epsilon}}\right)\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\mathrm{TV}\left(P_{a_{t}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ P_{a_{t}}^{\prime}\right)\right]$

###### Proof.

We define the marginal over the sequence of actions induced by
$\pi^{\epsilon}$ for a given environment $\nu$ as

$m_{\nu\pi^{\epsilon}}(a_{1},\dots,a_{T})\mathrel{\triangleq}\int_{r_{1},\dots,r_{T}}\pi^{\epsilon}(a_{1},\ldots,a_{T}\mid
r_{1},\ldots,r_{T})P_{a_{1}}\,\mathrm{d}r_{1}\dots P_{a_{T}}\,\mathrm{d}r_{T}$

Since $\pi^{\epsilon}$ is $\epsilon$-global DP, using Lemma 2, we obtain

$\displaystyle\log\left(\frac{m_{\nu\pi^{\epsilon}}(a_{1},a_{2},\dots,a_{T})}{m_{\nu^{\prime}\pi^{\epsilon}}(a_{1},a_{2},\dots,a_{T})}\right)$
$\displaystyle\leq
6\epsilon\sum_{t=1}^{T}\mathrm{TV}\left(P_{a_{t}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ P_{a_{t}}^{\prime}\right)$

for every action sequence $(a_{1},\dots,a_{T})\in[K]^{T}$.

Thus,

$\displaystyle D_{\mathrm{KL}}\left(M_{\nu\pi^{\epsilon}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ M_{\nu^{\prime}\pi^{\epsilon}}\right)$
$\displaystyle=\mathbb{E}_{\nu\pi^{\epsilon}}\left[\log\left(\frac{m_{\nu\pi^{\epsilon}}(A_{1},A_{2},\hbox
to6.99997pt{.\hss.\hss.},A_{T})}{m_{\nu^{\prime}\pi^{\epsilon}}(A_{1},A_{2},\hbox
to6.99997pt{.\hss.\hss.},A_{T})}\right)\right]$ $\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\mathrm{TV}\left(P_{a_{t}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ P_{a_{t}}^{\prime}\right)\right]$

∎

This lemma explicates how the distinguishability of two environments $\nu$ and
$\nu^{\prime}$ under $\pi^{\epsilon}$ is dictated by a joint effect of global
DP, in terms of the privacy budget $\epsilon$, and the partial information
available in bandits, in terms of the total variation distance between the
rewards of the arms
$\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\mathrm{TV}\left(P_{a_{t}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ P_{a_{t}}^{\prime}\right)\right]$. We leverage
this lemma further to construct the minimax and problem-dependent regret lower
bounds for stochastic and linear bandits with $\epsilon$-global DP.

###  Appendix C Lower Bounds on Regret: Stochastic and Linear Bandits with
$\epsilon$-global DP

In order to prove the lower bounds, we adopt the general canonical bandit
model introduced in Section A. The high level idea of proving bandit lower
bounds is selecting two problem instances that are similar (the policy cannot
statistically distinguish between them) but conflicting (actions that may be
good in one instance are not good for the other).

Under $\epsilon$-global differential privacy, a new source of "confusion" is
added to the problem, i.e. any sequence of actions induced by neighbouring
reward streams must be $\epsilon$-indistinguishable. In the canonical bandit
framework, this is expressed by our Theorem 10.

In the following, we plug this upper bound on KL-divergences in the classic
proofs of regret lower bounds in bandits Lattimore and Szepesvári, (2018) to
derive our minimax and problem-dependent regret lower bounds.

Notations. Let $\Pi$ be the set of all policies, and $\Pi^{\epsilon}$ be the
set of all $\epsilon$-global DP policies.

####  C.1 Stochastic Bandits: Minimax Lower Bound

######  Theorem 2 (Minimax lower bound).

For any $K>1$ and $T\geq K-1$, and $\epsilon>0$, the minimax regret of
stochastic bandits with $\epsilon$-global DP satisfies

$\mathrm{Reg}_{T,\epsilon}^{\text{minimax}}\geq\max\bigg{\\{}\frac{1}{27}\underset{\text{without
global DP}}{\underbrace{\sqrt{T(K-1)}}},\leavevmode\nobreak\
\leavevmode\nobreak\ \frac{1}{131}\underset{\text{with $\epsilon$-global
DP}}{\underbrace{\frac{K-1}{\epsilon}}}\bigg{\\}}.$

###### Proof.

We denote the environment corresponding to the set of $K$-Gaussian reward
distributions with unit variance and means $\mu\in^{K}$ as
$\mathcal{E}_{\mathcal{N}}^{K}\left(1\right)\mathrel{\triangleq}\left\\{\left(\mathcal{N}\left(\mu_{i},1\right)\right)_{i=1}^{K}:\mu=(\mu_{1},\dots,\mu_{K})\in\mathbb{R}^{K}\right\\}$.

Since $\Pi^{\epsilon}\subset\Pi$, we can have that

$\mathrm{Reg}_{T,\epsilon}^{\text{minimax}}\geq\inf_{\pi\in\Pi}\sup_{\nu\in\mathcal{E}_{\mathcal{N}}^{K}\left(1\right)}\mathrm{Reg}_{T}(\pi,\nu)\geq\frac{1}{27}\sqrt{T(K-1)}$

The second inequality is due to Theorem 15.2 in (Lattimore and Szepesvári,,
2018).

Step 1: Choosing the ‘Hard-to-distinguish’ Environments. First, we fix a
policy $\pi^{\epsilon}$ in $\Pi^{\epsilon}$.

Let $\Delta$ be a constant (to be specified later), and $\nu$ be a Gaussian
bandit instance with unit variance and mean vector $\mu=(\Delta,0,0,...,0)$.

To choose the second bandit instance, let
$i\mathrel{\triangleq}\operatorname*{arg\,min}_{a>1}\mathbb{E}_{\nu,\pi^{\epsilon}}[N_{a}(T)]$
be the least played arm in expectation other than the optimal arm 1.

The second environment $\nu^{\prime}$ is then chosen to be a Gaussian bandit
instance with unit variance and mean vector $\mu^{\prime}=(\Delta,0,0,\dots
0,2\Delta,0\dots,0)$, where $\mu^{\prime}_{j}=\mu_{j}$ for every $j$ except
for $\mu^{\prime}_{i}=2\Delta$.

The first arm is optimal in $\nu$ and the arm $i$ is optimal in
$\nu^{\prime}$.

Since
$T=\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{1}(T)\right]+\sum_{a>1}\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{a}(T)\right]\geq(K-1)\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{i}(T)\right]$,
we observe that

$\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{i}(T)\right]\leq\frac{T}{K-1}$

Step 2: From Lower Bounding Regret to Upper Bounding KL-divergence. Now by the
classic regret decomposition and Markov Inequality 6, we get777In all regret
lower bound proofs, we are under the probability space over sequence of
actions, produced when $\pi^{\epsilon}$ interacts with $\nu$ for $T$ time-
steps. We do this to use the KL-divergence decomposition of
$\mathbb{M}_{\nu\pi^{\epsilon}}$

$\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)=\left(T-\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{1}(T)\right]\right)\Delta\geq\mathbb{M}_{\nu\pi^{\epsilon}}\left(N_{1}(T)\leq
T/2\right)\frac{T\Delta}{2},$

and

$\mathrm{Reg}_{T}(\pi^{\epsilon},\nu^{\prime})=\Delta\mathbb{E}_{\nu^{\prime}\pi^{\epsilon}}\left[N_{1}(T)\right]+\sum_{a\notin\\{1,i\\}}2\Delta\mathbb{E}_{\nu^{\prime}\pi^{\epsilon}}\left[N_{a}(T)\right]\geq\mathbb{M}_{\nu^{\prime}\pi^{\epsilon}}\left(N_{1}(T)>T/2\right)\frac{T\Delta}{2}.$

Let us define the event $A\mathrel{\triangleq}\\{N_{1}(T)\leq
T/2\\}=\\{(a_{1},a_{2},\dots,a_{T}):\textrm{card}(\\{j:a_{j}=1\\})\leq
T/2\\}$.

By applying the Bretagnolle–Huber inequality, we have:

$\displaystyle\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)+\mathrm{Reg}_{T}(\pi^{\epsilon},\nu^{\prime})$
$\displaystyle\geq\frac{T\Delta}{2}(M_{\nu\pi^{\epsilon}}(A)+M_{\nu^{\prime}\pi^{\epsilon}}(A^{c}))$
$\displaystyle\geq\frac{T\Delta}{4}\exp(-D_{\mathrm{KL}}\left(M_{\nu\pi^{\epsilon}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ M_{\nu^{\prime}\pi^{\epsilon}}\right))$

Step 3: KL-divergence Decomposition with $\epsilon$-global DP. Now, we apply
Theorem 10 to upper-bound the KL-Divergence between the marginals.

$\displaystyle D_{\mathrm{KL}}\left(M_{\nu\pi^{\epsilon}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ M_{\nu^{\prime}\pi^{\epsilon}}\right)$
$\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\mathrm{TV}\left(P_{a_{t}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ P_{a_{t}}^{\prime}\right)\right]$
$\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{i}(T)\right]\mathrm{TV}\left(p_{i}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ p_{i}^{\prime}\right)$

since $\nu$ and $\nu^{\prime}$ only differ in the arm $i$.

Finally, using Pinsker’s Inequality 9, we obtain

$\mathrm{TV}\left(p_{i}\leavevmode\nobreak\ \middle\|\leavevmode\nobreak\
p_{i}^{\prime}\right)\leq\sqrt{\frac{1}{2}D_{\mathrm{KL}}\left(\mathcal{N}(0,1)\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathcal{N}(2\Delta,1)\right)}=\Delta$

Step 4: Choosing the Worst $\Delta$. Plugging back in the regret expression,
we find

$\displaystyle\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)+\mathrm{Reg}_{T}(\pi^{\epsilon},\nu^{\prime})$
$\displaystyle\geq\frac{T\Delta}{4}\exp\left(-6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{i}(T)\right]\Delta\right)$
$\displaystyle\geq\frac{T\Delta}{4}\exp\left(-\frac{6\epsilon
T\Delta}{K-1}\right)$

By optimising for $\Delta$, we choose $\Delta=\frac{K-1}{6\epsilon T}$.

We conclude the proof by lower bounding $\exp(-1)$ with $\frac{48}{131}$, and
using $2\max(a,b)\geq a+b$. ∎

####  C.2 Stochastic Bandits: Problem-dependent Lower Bound

######  Theorem 3 (Problem-dependent Regret Lower Bound).

Let the environment $\mathcal{E}$ be a set of $K$ reward distributions with
finite means and a policy $\pi^{\epsilon}\in\Pi_{\text{cons
}}(\mathcal{E})\cap\Pi^{\epsilon}$ be a consistent policy888A policy $\pi$ is
called consistent over a class of bandits $\mathcal{E}$ if for all
$\nu\in\mathcal{E}$ and $p>0$, it holds that
$\lim_{T\rightarrow\infty}\frac{R_{T}(\pi,\nu)}{T^{p}}=0$. We denote the class
of consistent policies over a set of environments $\mathcal{E}$ as
$\Pi_{\text{cons }}(\mathcal{E})$. over $\mathcal{E}$ satisfying
$\epsilon$-global DP . Then, for all
$\nu=\left(P_{i}\right)_{i=1}^{K}\in\mathcal{E}$, it holds that

$\displaystyle\liminf_{T\rightarrow\infty}\frac{\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)}{\log(T)}$
$\displaystyle\geq\sum_{a:\Delta_{a}>0}\frac{\Delta_{a}}{\min\biggl{(}\underset{\text{without
global
DP}}{\underbrace{d_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}},\underset{\text{with
$\epsilon$-global
DP}}{\underbrace{6\,\epsilon\,t_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}}\biggl{)}}.$

###### Proof.

Let $\mu_{a}$ be the mean of the $a$-th arm in $\nu$,
$t_{a}=t_{\mathrm{inf}}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)$ and
$\pi^{\epsilon}\in\Pi_{\text{cons }}(\mathcal{E})\cap\Pi^{\epsilon}$.

Since $\pi^{\epsilon}$ is consistent, by (Theorem 16.2, Lattimore and
Szepesvári, (2018)), it holds that

$\liminf_{T\rightarrow\infty}\frac{\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)}{\log(T)}\geq\sum_{a:\Delta_{a}>0}\frac{\Delta_{a}}{d_{\inf}\left(P_{a},\mu^{*},\mathcal{M}_{a}\right)}.$

The theorem will follow by showing, for every suboptimal arm $a$:

$\liminf_{T\rightarrow\infty}\frac{\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{a}(T)\right]}{\log(T)}\geq\frac{1}{6\,\epsilon\,t_{a}}$

Fix a suboptimal arm $a$, and let $\alpha>0$ be an arbitrary constant.

Step 1: Choosing the ‘Hard-to-distinguish’ Environment. Let
$\nu^{\prime}\mathrel{\triangleq}\left(P_{j}^{\prime}\right)_{j=1}^{K}\in\mathcal{E}$
be a bandit with $P_{j}^{\prime}=P_{j}$ for $j\neq a$ and
$P_{a}^{\prime}\in\mathcal{M}_{a}$ be such that
$\mathrm{TV}\left(P_{a}\leavevmode\nobreak\ \middle\|\leavevmode\nobreak\
P_{a}^{\prime}\right)\leq t_{a}+\alpha$ and
$\mu\left(P_{a}^{\prime}\right)>\mu^{*}$, which exists by the definition of
$t_{a}$. Let $\mu^{\prime}\in\mathbb{R}^{K}$ be the vector of means of
distributions of $\nu^{\prime}$.

Step 2: From Lower Bounding Regret to Upper Bounding KL-divergence. For
simplicity of notations, we use
$\mathrm{Reg}_{T}=\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)$,
$\mathrm{Reg}_{T}^{\prime}=\mathrm{Reg}_{T}(\pi^{\epsilon},\nu)$, and
$A=\\{(a_{1},a_{2},\dots,a_{T}):\textrm{card}(\\{j:a_{j}=1\\})\leq T/2\\}$.

Then, by regret decomposition and Markov Inequality 6, we obtain

$\displaystyle\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}$
$\displaystyle\geq\frac{T}{2}\left(M_{\nu\pi^{\epsilon}}(A)\Delta_{a}+M_{\nu^{\prime}\pi^{\epsilon}}\left(A^{c}\right)\left(\mu_{a}^{\prime}-\mu^{*}\right)\right)$
(17)
$\displaystyle\geq\frac{T}{2}\min\left\\{\Delta_{a},\mu_{a}^{\prime}-\mu^{*}\right\\}\left(M_{\nu\pi^{\epsilon}}(A)+M_{\nu^{\prime}\pi^{\epsilon}}\left(A^{c}\right)\right)$
$\displaystyle\geq\frac{T}{4}\min\left\\{\Delta_{a},\mu_{a}^{\prime}-\mu^{*}\right\\}\exp(-D_{\mathrm{KL}}\left(M_{\nu\pi^{\epsilon}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ M_{\nu^{\prime}\pi^{\epsilon}}\right))$

Step 3: KL-divergence Decomposition with $\epsilon$-global DP. By Theorem 10
and the construction of the ‘hard-to-distinguish’ environments, we obtain

$\displaystyle D_{\mathrm{KL}}\left(M_{\nu\pi^{\epsilon}}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ M_{\nu^{\prime}\pi^{\epsilon}}\right)$
$\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{a}(T)\right]\mathrm{TV}\left(P_{a}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ P_{a}^{\prime}\right)$ $\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{a}(T)\right]\left(t_{a}+\alpha\right)$

Step 4: Rearranging and taking the limit inferior. Thus, we get

$\displaystyle\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}$
$\displaystyle\geq\frac{T}{4}\min\left\\{\Delta_{a},\mu_{a}^{\prime}-\mu^{*}\right\\}\exp\left(-6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{a}(T)\right]\left(t_{a}+\alpha\right)\right)$

Now, taking the limit inferior on both sides leads to

$\displaystyle\liminf_{T\rightarrow\infty}\frac{\mathbb{E}_{\nu\pi^{\epsilon}}\left[N_{a}(T)\right]}{\log(T)}$
$\displaystyle\geq\frac{1}{6\epsilon\left(t_{a}+\alpha\right)}\liminf_{T\rightarrow\infty}\frac{\log\left(\frac{T\min\left\\{\Delta_{a},\mu_{a}^{\prime}-\mu^{*}\right\\}}{4\left(\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}\right)}\right)}{\log(T)}$
$\displaystyle=\frac{1}{6\epsilon\left(t_{a}+\alpha\right)}\left(1-\limsup_{T\rightarrow\infty}\frac{\log\left(\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}\right)}{\log(T)}\right)=\frac{1}{6\epsilon\left(t_{a}+\alpha\right)}.$

The last equality follows from the definition of consistency, which says that
for any $p>0$, there exists a constant $C_{p}$ such that for sufficiently
large $T$, $\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}\leq C_{p}T^{p}$. This
property implies that

$\limsup_{T\rightarrow\infty}\frac{\log\left(\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}\right)}{\log(T)}\leq\limsup_{T\rightarrow\infty}\frac{p\log(T)+\log\left(C_{p}\right)}{\log(T)}=p,$

which gives the result since $p>0$ was an arbitrary constant.

We arrive at the claimed result by taking the limit as $\alpha$ tends to zero.

∎

######  Remark 2.

For Bernoulli distributions, $t_{a}$ is equal to $\Delta_{a}$, so the private
lower bound simplifies to:

$O\left(\sum_{a:\Delta_{a}>0}\Delta_{a}\frac{1}{\epsilon\Delta_{a}}log(T)\right)=O\left(\frac{K\log(T)}{\epsilon}\right)$

Thus, our problem-dependent regret lower bound retrieves as a special case the
lower bound found in (Shariff and Sheffet,, 2018) and established for
Bernoulli distributions of rewards.

####  C.3 Stochastic Linear Bandits: Minimax Lower Bound

######  Theorem 4 (Minimax Regret Lower Bound).

Let $\mathcal{A}=[-1,1]^{d}$ and
$\Theta=\left\\{-T^{-1/2},T^{-1/2}\right\\}^{d}$. Then, there exists a vector
$\theta\in\Theta$ leading to a minimax regret of linear bandits with
$\epsilon$-global DP such that

$\displaystyle\mathrm{Reg}^{\text{minimax}}_{T}(\mathcal{A},\Theta)\geq\max\big{\\{}\underset{\text{without
global DP}}{\underbrace{\exp(-2)}},\leavevmode\nobreak\ \leavevmode\nobreak\
\underset{\text{with $\epsilon$-global DP}}{\underbrace{\exp(-6\epsilon
d\sqrt{T})}}\big{\\}}\frac{d}{8}\sqrt{T}.$

###### Proof.

Due to Theorem 24.1,(Lattimore and Szepesvári,, 2018), it holds that for any
policy class $\Pi$,

$\mathrm{Reg}^{\text{minimax}}_{T}(\mathcal{A},\Theta)\geq\exp(-2)\frac{d}{8}\sqrt{T}.$

Now, we focus on proving the $\epsilon$-global DP part of the lower bound.

For $\theta,\theta^{\prime}\in\Theta$, let $\nu$ and $\nu^{\prime}$ be the
bandit instances corresponding resp. to $\theta$ and $\theta^{\prime}$. We
denote $\mathbb{M}_{\theta}=\mathbb{M}_{\nu,\pi^{\epsilon}}$ and
$\mathbb{M}_{\theta^{\prime}}=\mathbb{M}_{\nu^{\prime},\pi^{\epsilon}}$. Let
$\mathbb{E}_{\theta}$ and $\mathbb{E}_{\theta^{\prime}}$ the expectations
under $\mathbb{M}_{\theta}$ and $\mathbb{M}_{\theta^{\prime}}$ respectively.

Step 1: From Lower Bounding Regret to Upper Bounding KL-divergence We begin
with

$\displaystyle\mathrm{Reg}_{T}(\mathcal{A},\theta)$
$\displaystyle=\mathbb{E}_{\theta}\left[\sum_{t=1}^{T}\sum_{i=1}^{d}\left(\operatorname{sign}\left(\theta_{i}\right)-A_{ti}\right)\theta_{i}\right]$
$\displaystyle\geq\sqrt{\frac{1}{T}}\sum_{i=1}^{d}\mathbb{E}_{\theta}\left[\sum_{t=1}^{T}\mathbb{I}\left\\{\operatorname{sign}\left(A_{ti}\right)\neq\operatorname{sign}\left(\theta_{i}\right)\right\\}\right]$
$\displaystyle\geq\frac{\sqrt{T}}{2}\sum_{i=1}^{d}\mathbb{M}_{\theta}\left(\sum_{t=1}^{T}\mathbb{I}\left\\{\operatorname{sign}\left(A_{ti}\right)\neq\operatorname{sign}\left(\theta_{i}\right)\right\\}\geq
T/2\right)$

In this derivation, the first equality holds because the optimal action
satisfies $a_{i}^{*}=\operatorname{sign}\left(\theta_{i}\right)$ for
$i\in[d]$. The first inequality follows from an observation that
$\left(\operatorname{sign}\left(\theta_{i}\right)-A_{ti}\right)\theta_{i}\geq\left|\theta_{i}\right|\mathbb{I}\left\\{\operatorname{sign}\left(A_{ti}\right)\neq\operatorname{sign}\left(\theta_{i}\right)\right\\}$.
The last inequality is a direct application of Markov’s inequality 6.

For $i\in[d]$ and $\theta\in\Theta$, we define

$p_{\theta,i}\mathrel{\triangleq}\mathbb{M}_{\theta}\left(\sum_{t=1}^{T}\mathbb{I}\left\\{\operatorname{sign}\left(A_{ti}\right)\neq\operatorname{sign}\left(\theta_{i}\right)\right\\}\geq
T/2\right).$

Now, let $i\in[d]$ and $\theta\in\Theta$ be fixed. Also, let
$\theta_{j}^{\prime}=\theta_{j}$ for $j\neq i$ and
$\theta_{i}^{\prime}=-\theta_{i}$. Then, by the Bretagnolle-Huber inequality,

$p_{\theta,i}+p_{\theta^{\prime},i}\geq\frac{1}{2}\exp\left(-D_{\mathrm{KL}}\left(\mathbb{M}_{\theta}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{M}_{\theta^{\prime}}\right)\right).$

Step 2: KL-divergence Decomposition with $\epsilon$-global DP. From Theorem
10, we obtain that

$\displaystyle D_{\mathrm{KL}}\left(\mathbb{M}_{\theta}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{M}_{\theta^{\prime}}\right)$
$\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\mathrm{TV}\left(\mathcal{N}\left(\left\langle
A_{t},\theta\right\rangle,1\right)\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathcal{N}\left(\left\langle
A_{t},\theta^{\prime}\right\rangle,1\right)\right)\right]$ $\displaystyle\leq
6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\sqrt{\frac{1}{2}D_{\mathrm{KL}}\left(\mathcal{N}\left(\left\langle
A_{t},\theta\right\rangle,1\right)\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathcal{N}\left(\left\langle
A_{t},\theta^{\prime}\right\rangle,1\right)\right)}\right]$
$\displaystyle=6\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\sqrt{\frac{1}{4}\left[\left\langle
A_{t},\theta-\theta^{\prime}\right\rangle^{2}\right]}\right]$
$\displaystyle=3\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},\theta-\theta^{\prime}\right\rangle\right|\right]$ (18)
$\displaystyle\leq
3\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\left\|A_{t}\right\|(\left\|\theta-\theta^{\prime}\right\|)\right]$
$\displaystyle\leq
3\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[T\sqrt{d}\times
2\sqrt{d}\frac{1}{\sqrt{T}}\right]=6\epsilon d\sqrt{T}$

Here, the second inequality is a consequence of Pinsker’s inequality (Lemma
9). The third inequality is due to Cauchy-Scwhartz. The last inequality holds
true because $A_{t}\in[-1,1]^{d}$ and
$\theta,\theta^{\prime}\in\left\\{-T^{-1/2},T^{-1/2}\right\\}^{d}$

Step 3: Choosing the ‘Hard-to-distinguish’ $\theta$. We already have that

$p_{\theta,i}+p_{\theta^{\prime},i}\geq\frac{1}{2}\exp\left(-3\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},\theta-\theta^{\prime}\right\rangle\right|\right]\right)\geq\frac{1}{2}\exp(-6\epsilon
d\sqrt{T})$

Now, we apply an ‘averaging hammer’ over all $\theta\in\Theta$, such that
$|\Theta|=2^{d}$, to obtain

$\sum_{\theta\in\Theta}\frac{1}{|\Theta|}\sum_{i=1}^{d}p_{\theta,i}=\frac{1}{|\Theta|}\sum_{i=1}^{d}\sum_{\theta\in\Theta}p_{\theta,i}\geq\frac{d}{4}\exp(-6\epsilon
d\sqrt{T}).$

This implies that there exists a $\theta\in\Theta$ such that
$\sum_{i=1}^{d}p_{\theta,i}\geq d\exp(-6\epsilon d\sqrt{T})/4.$

Step 4: Plugging Back $\theta$ in the Regret Decomposition. With this choice
of $\theta$, we conclude that

$\displaystyle\mathrm{Reg}_{T}(\mathcal{A},\theta)$
$\displaystyle\geq\frac{\sqrt{T}}{2}\sum_{i=1}^{d}p_{\theta,i}$
$\displaystyle\geq\frac{d\sqrt{T}}{8}\exp(-6\epsilon d\sqrt{T})$

∎

####  C.4 Stochastic Linear Bandits: Problem-dependent Lower Bound

######  Theorem 5 (Problem-dependent Regret Lower Bound).

Let $\mathcal{A}\subset\mathbb{R}^{d}$ be a finite set spanning
$\mathbb{R}^{d}$ and $\theta\in\mathbb{R}^{d}$ be such that there is a unique
optimal action. Then, any consistent and $\epsilon$-global DP bandit algorithm
$\pi^{\epsilon}$ satisfies

$\liminf_{T\rightarrow\infty}\frac{\mathrm{Reg}_{T}(\mathcal{A},\theta)}{\log(T)}\geq
c(\mathcal{A},\theta),$

where the _structural distinguishability gap_ is the solution of a constraint
optimisation

$c(\mathcal{A},\theta)\mathrel{\triangleq}\inf_{\alpha\in[0,\infty)^{\mathcal{A}}}\sum_{a\in\mathcal{A}}\alpha(a)\Delta_{a},\text{
such that
}\|a\|_{H_{\alpha}^{-1}}^{2}\leq\min\bigg{\\{}\underset{\text{without global
DP}}{\underbrace{0.5\Delta_{a}^{2}}},\leavevmode\nobreak\ \leavevmode\nobreak\
\underset{\text{with $\epsilon$-global
DP}}{\underbrace{3\epsilon\rho_{a}(\mathcal{A})\Delta_{a}}}\bigg{\\}}$

for all $a\in\mathcal{A}$ with $\Delta_{a}>0$,
$H_{\alpha}=\sum_{a\in\mathcal{A}}\alpha(a)aa^{\top}$, and an arm-structure
dependent constant $\rho_{a}(\mathcal{A})$.

###### Proof.

Let $a^{*}=\operatorname{argmax}_{a\in\mathcal{A}}\langle a,\theta\rangle$ be
the optimal action, which we assumed to be unique.

By Theorem 25.1, Lattimore and Szepesvári, (2018),

$\underset{T\rightarrow\infty}{\limsup}\log(T)\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}\leq\frac{1}{2}\Delta_{a}^{2}.$
(19)

Let $\mathbb{M}$ and $\mathbb{M}^{\prime}$ be the measures on the sequence of
outcomes $A_{1},\ldots,A_{T}$ induced by $\theta$ and $\theta^{\prime}$
respectively. Let $\mathbb{E}[\cdot]$ and $\mathbb{E}^{\prime}[\cdot]$ be the
expectation operators of $\mathbb{M}$ and $\mathbb{M}^{\prime}$, respectively.

Step 1: Choosing the ‘Hard to distinguish’ $\theta^{\prime}$. Let
$\theta^{\prime}\in\mathbb{R}^{d}$ be an alternative parameter to be chosen
subsequently. We follow the usual plan of choosing $\theta^{\prime}$ to be
close to $\theta$, but also ensuring that the optimal action in the bandit
determined by $\theta^{\prime}$ is not $a^{*}$. Let
$\Delta_{\min}=\min\left\\{\Delta_{a}\right.$ :
$\left.a\in\mathcal{A},\Delta_{a}>0\right\\}$,
$\alpha\in\left(0,\Delta_{\min}\right)$ and $H$ be a positive definite matrix
(to be chosen later) such that $\left\|a-a^{*}\right\|_{H}^{2}>0$.

Given this setting, we define

$\theta^{\prime}\mathrel{\triangleq}\theta+\frac{\Delta_{a}+\alpha}{\left\|a-a^{*}\right\|_{H}^{2}}H\left(a-a^{*}\right),$

which is chosen such that $\left\langle
a-a^{*},\theta^{\prime}\right\rangle=\left\langle
a-a^{*},\theta\right\rangle+\Delta_{a}+\alpha=\alpha$.

This means that $a^{*}$ is $\alpha$-suboptimal for the environment
corresponding to $\theta^{\prime}$.

Step 2: From Lower Bounding Regret to Upper Bounding KL-divergence. For
simiplicity, we abbreviate
$\mathrm{Reg}_{T}=\mathrm{Reg}_{T}(\mathcal{A},\theta)$ and
$\mathrm{Reg}_{T}^{\prime}=\mathrm{Reg}_{T}\left(\mathcal{A},\theta^{\prime}\right)$.

Then, by applying the classic regret decomposition and Markov’s inequality 6,
we obtain

$\mathrm{Reg}_{T}=\mathbb{E}\left[\sum_{a\in\mathcal{A}}N_{a}(T)\Delta_{a}\right]\geq\frac{T\Delta_{\min}}{2}\mathbb{M}\left(N_{a^{*}}(T)<T/2\right)\geq\frac{T\alpha}{2}\mathbb{M}\left(N_{a^{*}}(T)<T/2\right),$

Since $a^{*}$ is $\alpha$-suboptimal in bandit $\theta^{\prime}$, it implies
that

$\mathrm{Reg}_{T}^{\prime}\geq\frac{T\alpha}{2}\mathbb{M}^{\prime}\left(N_{a^{*}}(T)\geq
T/2\right).$

Now, Bretagnolle–Huber inequality implies that

$\displaystyle\mathrm{Reg}_{T}+\mathrm{Reg}_{T}^{\prime}$
$\displaystyle\geq\frac{T\alpha}{2}\left(\mathbb{M}\left(N_{a^{*}}(T)<T/2\right)+\mathbb{M}^{\prime}\left(N_{a^{*}}(T)\geq
T/2\right)\right)$
$\displaystyle\geq\frac{T\alpha}{4}\exp\left(-D_{\mathrm{KL}}\left(\mathbb{M}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{M}^{\prime}\right)\right)$

Step 3: KL-divergence Decomposition with $\epsilon$-global DP. By Equation
C.3, we have that

$\displaystyle D_{\mathrm{KL}}\left(\mathbb{M}\leavevmode\nobreak\
\middle\|\leavevmode\nobreak\ \mathbb{M}\right)$ $\displaystyle\leq
3\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},\theta-\theta^{\prime}\right\rangle\right|\right]$
$\displaystyle=3\epsilon\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},\frac{\Delta_{a}+\alpha}{\left\|a-a^{*}\right\|_{H}^{2}}H\left(a-a^{*}\right)\right\rangle\right|\right]$
$\displaystyle=3\epsilon\frac{\Delta_{a}+\alpha}{\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}}\rho_{T}(H),$

where we define

$\rho_{T}(H)\mathrel{\triangleq}\frac{\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}}{\left\|a-a^{*}\right\|_{H}^{2}}\mathbb{E}_{\nu\pi^{\epsilon}}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},H\left(a-a^{*}\right)\right\rangle\right|\right]$

Thus, after re-arrangement, we get

$\frac{3\epsilon\left(\Delta_{a}+\alpha\right)}{\log(T)\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}}\rho_{T}(H)\geq
1-\frac{\log\left(\left(4R_{T}+4R_{T}^{\prime}\right)/\alpha\right)}{\log(T)}.$
(20)

Step 4: Choosing H and Taking the Limit. The definition of consistency means
that $\mathrm{Reg}_{T}$ and $\mathrm{Reg}_{T}^{\prime}$ are both sub-linear in
$T$. This implies that the second term in Equation (20) tends to zero for
large $T$. Thus, by tending $T$ to $\infty$ and $\alpha$ to zero, we obtain

$\liminf_{T\rightarrow\infty}\frac{\rho_{T}(H)}{\log(T)\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}}\geq\frac{1}{3\epsilon\Delta_{a}}.$

We now choose $H$ to be a cluster point of the sequence
$\left(\bar{G}_{T}^{-1}/\left\|\bar{G}_{T}^{-1}\right\|\right)_{T\in S}$ where
$\left\|\bar{G}_{T}^{-1}\right\|$ is the spectral norm of the matrix
$\bar{G}_{T}^{-1}$.

Fact 2: For this choice of $H$,

$\liminf_{T\rightarrow\infty}\rho_{T}(H)\leq\rho_{a}(\mathcal{A}),$

where

$\rho_{a}(\mathcal{A})\mathrel{\triangleq}\sum_{j=1,\left\|a_{j}\right\|\neq
0}^{K}\frac{\left|a_{j}^{T}(a-a^{*})\right|}{\left\|a_{j}\right\|^{2}}.$

Finally,

$\underset{T\rightarrow\infty}{\limsup}\log(T)\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}\leq
3\epsilon\Delta_{a}\rho_{a}(\mathcal{A}).$

Combined with Equation 19, we get that

$\underset{T\rightarrow\infty}{\limsup}\log(T)\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}^{2}\leq\min\left(\frac{1}{2}\Delta_{a}^{2},3\epsilon\Delta_{a}\rho_{a}(\mathcal{A})\right).$

Using that

$\lim_{T\rightarrow\infty}\frac{\left\|a-a^{*}\right\|_{\bar{G}_{T}^{-1}}}{\left\|a\right\|_{\bar{G}_{T}^{-1}}}=1$

from Theorem 25.1, Lattimore and Szepesvári, (2018), we get that

$\underset{T\rightarrow\infty}{\limsup}\log(T)\left\|a\right\|_{\bar{G}_{T}^{-1}}^{2}\leq\min\left(\frac{1}{2}\Delta_{a}^{2},3\epsilon\Delta_{a}\rho_{a}(\mathcal{A})\right).$

Step 5: Getting Back to the Regret. We conclude using the same steps as in the
Corollary 2 (Lattimore and Szepesvari,, 2017). ∎

Now, we prove Fact 2.

######  Fact 2.

If $H$ is a cluster point of the sequence
$\left(\bar{G}_{T}^{-1}/\left\|\bar{G}_{T}^{-1}\right\|\right)_{T\in S}$ and
$\left\|\bar{G}_{T}^{-1}\right\|$ is the spectral norm of the matrix
$\bar{G}_{T}^{-1}$, then the following inequality holds true:

$\liminf_{T\rightarrow\infty}\rho_{T}(H)\leq\rho_{a}(\mathcal{A}),$

where

$\rho_{a}(\mathcal{A})\mathrel{\triangleq}\sum_{j=1,\left\|a_{j}\right\|\neq
0}^{K}\frac{\left|a_{j}^{T}(a-a^{*})\right|}{\left\|a_{j}\right\|^{2}}.$

###### Proof.

We let $S$ be a subset so that
$\bar{G}_{T}^{-1}/\left\|\bar{G}_{T}^{-1}\right\|$ converges to $H$ on $T\in
S$. Then,

$\displaystyle\liminf_{T\rightarrow\infty}\rho_{T}(H)$
$\displaystyle\leq\liminf_{T\in
S}\rho_{T}(\bar{G}_{T}^{-1}/\left\|\bar{G}_{T}^{-1}\right\|)$
$\displaystyle=\liminf_{T\in
S}\mathbb{E}_{\theta}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right\rangle\right|\right]$
$\displaystyle=\liminf_{T\in
S}\sum_{j=1}^{K}\mathbb{E}_{\theta}(N_{j}(T))\left|a_{j}^{T}\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right|$
$\displaystyle=\liminf_{T\in S}\sum_{j=1,\left\|a_{j}\right\|\neq
0}^{K}\mathbb{E}_{\theta}(N_{j}(T))\left|a_{j}^{T}\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right|$

Let $j$ be such that $\left\|a_{j}\right\|\neq 0$.

Now, we aim to upper bound the term
$\left|a_{j}^{T}\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right|$

First, we decompose $a-a^{*}$ into two orthogonal components, which are
aligned and orthogonal to $a_{j}$ respectively.

$a-a^{*}=\alpha_{j}a_{j}+b_{j},$

where $a_{j}^{\top}b_{j}=0$ and
$\alpha_{j}=\frac{a_{j}^{T}(a-a^{*})}{\left\|a_{j}\right\|^{2}}$.

On the other hand, we have that

$\bar{G}_{T}=\mathbb{E}_{\theta}\left[\sum_{t=1}^{T}A_{t}A_{t}^{\top}\right]=\sum_{j=1}^{K}\mathbb{E}_{\theta}(N_{j}(T))a_{j}a_{j}^{\top}\succeq\mathbb{E}_{\theta}(N_{j}(T))a_{j}a_{j}^{\top}$

Since

$\biggl{(}\mathbb{E}_{\theta}(N_{j}(T))a_{j}a_{j}^{\top}\biggl{)}^{\dagger}=\frac{1}{\mathbb{E}_{\theta}(N_{j}(T))(a_{j}^{\top}a_{j})^{2}}a_{j}a_{j}^{\top},$

and

$\biggl{(}\mathbb{E}_{\theta}(N_{j}(T))a_{j}a_{j}^{\top}\biggl{)}^{\dagger}b_{j}=0,$

only the component of $a-a^{*}$ in the direction of $a_{j}$ matters in the dot
product $a_{j}^{T}\bar{G}_{T}^{-1}\left(a-a^{*}\right)$. Thus,

$\displaystyle\left|a_{j}^{T}\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right|$
$\displaystyle\leq\frac{\left|\alpha_{j}\right|}{\mathbb{E}_{\theta}(N_{j}(T))(a_{j}^{\top}a_{j})^{2}}a_{j}^{T}a_{j}a_{j}^{T}a_{j}$
$\displaystyle=\frac{\left|\alpha_{j}\right|}{\mathbb{E}_{\theta}(N_{j}(T))}$

Consequently,

$\displaystyle\liminf_{T\rightarrow\infty}\rho_{T}(H)\leq\sum_{j=1,\left\|a_{j}\right\|\neq
0}^{K}\frac{\left|a_{j}^{T}(a-a^{*})\right|}{\left\|a_{j}\right\|^{2}}\triangleq\rho_{a}(\mathcal{A})$

∎

######  Example 3 ($\rho_{a}(\mathcal{A})$ for an orthogonal set of arms).

If the action space is the orthogonal basis, then $\rho_{a}(\mathcal{A})=2$,
because:

$\displaystyle\bar{G}_{T}=\begin{bmatrix}\mathbb{E}(N_{1}(T))&&\\\ &\ddots&\\\
&&\mathbb{E}(N_{d}(T))\end{bmatrix}$

and:

$\left|\left\langle
A_{t},\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right\rangle\right|=\frac{1}{\mathbb{E}(N_{a}(T))}\mathbb{I}_{A_{t}=a}+\frac{1}{\mathbb{E}(N_{a^{\star}}(T))}\mathbb{I}_{A_{t}=a^{\star}}$

so:

$\mathbb{E}\left[\sum_{t=1}^{T}\left|\left\langle
A_{t},\bar{G}_{T}^{-1}\left(a-a^{*}\right)\right\rangle\right|\right]=2$

###  Appendix D Privacy Analysis of Algorithm 1

In this section, we prove that any bandit algorithm designed using the
framework of Algorithm 1 satisfies $\epsilon$-global DP. We establish the
claim by proving $\epsilon$-global DP for the set of private indices computed
in Algorithm 1 and the final result is a consequence of the post-processing
property of DP (Lemma 5).

######  Lemma 1 (Privacy of the $(l+1)$-means Computed in Algorithm 1).

Let us define the private empirical mean of the rewards between steps $i$ and
$j$ $(i<j)$ as

$\displaystyle
f^{\epsilon}\\{r_{i},\dots,r_{j}\\}\mathrel{\triangleq}\frac{1}{j-i}\sum_{t=i}^{j}r_{t}+Lap\left(\frac{1}{(j-i)\epsilon}\right).$
(21)

If $1<t_{1}<\cdots<t_{\ell}<T$ and $r_{t}\in[0,1]$, the mechanism
$g^{\epsilon}$ mapping the sequence of rewards
$(r_{1},r_{2},\ldots,r_{T-1},r_{T})$ to $(\ell+1)$-private empirical means
$(f^{\epsilon}\\{r_{1},\dots,r_{t_{1}-1}\\},f^{\epsilon}\\{r_{{t_{1}}},\dots,r_{t_{2}-1}\\},$
$\ldots,f^{\epsilon}\\{r_{{t_{\ell-1}}},\dots,r_{t_{\ell}-1}\\},f^{\epsilon}\\{r_{{t_{\ell}}},\dots,r_{T}\\})$
satisfies $\epsilon$-DP.

###### Proof.

Let $r^{T}\mathrel{\triangleq}(r_{1},\dots,r_{T})$ and $r^{\prime
T}\mathrel{\triangleq}(r_{1}^{\prime},\dots,r_{T}^{\prime})$ be two
neighbouring reward sequences in [0,1]. This implies that $\exists j\in[1,T]$
such that $r_{j}\neq r_{j}^{\prime}$ and $\forall t\neq j$,
$r_{t}=r_{t}^{\prime}$.

Let $\ell^{\prime}$ be such that $t_{\ell^{\prime}}\leq j\leq
t_{\ell^{\prime}+1}-1$, and follows the convention that $t_{0}=1$ and
$t_{\ell+1}=T+1$.

Let $\mu\mathrel{\triangleq}(\mu_{0},\dots,\mu_{\ell})$ a fixed sequence of
outcomes obtained using Equation (21). Then,

$\displaystyle\frac{\mathbb{P}(g^{\epsilon}(r^{T})=\mu)}{\mathbb{P}(g^{\epsilon}(r^{\prime
T})=\mu)}=\frac{\mathbb{P}\left(f^{\epsilon}\\{r_{{t_{\ell^{\prime}}}},\dots,r_{t_{\ell^{\prime}+1}-1}\\}=\mu_{\ell^{\prime}}\right)}{\mathbb{P}\left(f^{\epsilon}\\{r_{{t_{\ell^{\prime}}}},\dots,r_{t_{\ell^{\prime}+1}-1}\\}=\mu_{\ell^{\prime}}\right)}\leq
e^{\epsilon},$

where the last inequality holds true because $f^{\epsilon}$ satisfies
$\epsilon$-DP following Theorem 1. ∎

######  Theorem 6 ($\epsilon$-global DP for Algorithm 1).

For any index $I^{\epsilon}_{a}$ computed using the private empirical mean of
the rewards collected in the last active episode of arm $a$, Algorithm 1
satisfies $\epsilon$-global DP.

###### Proof.

Fix two neighboring reward streams $r^{T}=\\{r_{1},\dots,r_{T}\\}$ and
$r^{\prime T}=\\{r^{\prime}_{1},\dots,r^{\prime}_{T}\\}$.
This implies that $\exists j\in[1,T]$ such that $r_{j}\neq r_{j}^{\prime}$ and
$\forall t\neq j$, $r_{t}=r_{t}^{\prime}$.
We also fix a sequence of actions $a^{T}=\\{a_{1},\dots,a_{T}\\}$.
We want to show that: $Pr(\pi(r^{T})=a^{T})\leq e^{\epsilon}Pr(\pi(r^{\prime
T})=a^{T})$.

The main idea is that the change of reward in the $j$-th reward only affects
the empirical mean computed in one episode, which is made private using the
Laplace Mechanism and Lemma 1.

  * •

Since $r^{j-1}=r^{\prime j-1}$, $Pr(\pi(r^{j-1})=a^{j-1})=Pr(\pi(r^{\prime
j-1})=a^{j-1})$.

  * •

Let $t_{\ell}\leq j<t_{\ell+1}$ and $t_{\ell^{\prime}}\leq
j<t_{\ell^{\prime}+1}$ be the episodes corresponding to the $j$th reward in
$r^{T}$ and $r^{\prime T}$ respectively. Since $r^{j-1}=r^{\prime j-1}$, we
get that $\ell=\ell^{\prime}$. Thus,
$Pr(\pi(r^{t_{\ell+1}})=a^{t_{\ell}+1})=Pr(\pi(r^{\prime
t_{\ell}+1})=a^{t_{\ell}+1})$.

  * •

Let $\tilde{\mu}_{a_{j},\epsilon}^{\ell}$ and
$\tilde{\mu}_{a,\epsilon}^{{}^{\prime}\ell}$ be the private means of arm
$a_{j}$ computed in the episode $[t_{\ell},t_{\ell+1}]$, by the Laplace
mechanism, for every interval $I\in\mathcal{R}$,
$Pr(\tilde{\mu}_{a,\epsilon}^{\ell}\in I)\leq
e^{\epsilon}Pr(\tilde{\mu}_{a,\epsilon}^{{}^{\prime}\ell}\in I)$.

  * •

Finally, since
$\\{r_{j+1},\dots,r_{T}\\}=\\{r^{\prime}_{j+1},\dots,r^{\prime}_{T}\\}$,
$Pr(\pi(r^{T})=a^{T}|\tilde{\mu}_{a,\epsilon}^{\ell}\in I)=Pr(\pi(r^{\prime
T})=a^{T}|\tilde{\mu}_{a,\epsilon}^{{}^{\prime}\ell}\in I)$

Now, we conclude the argument by using a chain rule.

∎

Since Theorem 6 holds for any index-based bandit algorithm that uses only
private empirical means of rewards (Equation (21)) of the last active episode
to compute the indices, it also implies that $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$ satisfy $\epsilon$-global DP.

###  Appendix E Upper Bounds on Regret: $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$

####  E.1 Concentration Inequalities

######  Lemma 3.

Assume that $(X_{i})_{1\leq i\leq n}$ are iid random variables in $[0,1]$,
with $\mathbb{E}(X_{i})=\mu$. Then, for any $\delta\geq 0$,

$\mathbb{P}\left(\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)-\frac{\log\left(\frac{1}{\delta}\right)}{n\epsilon}-\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{2n}}\geq\mu\right)\leq\frac{3}{2}\delta,$
(22)

and

$\mathbb{P}\left(\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log\left(\frac{1}{\delta}\right)}{n\epsilon}+\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{2n}}\leq\mu\right)\leq\frac{3}{2}\delta,$
(23)

where $\hat{\mu}_{n}=\frac{1}{n}\sum_{t=1}^{n}X_{t}$

###### Proof.

We have that

$\displaystyle p_{1}$
$\displaystyle\mathrel{\triangleq}\mathbb{P}\left(\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)-\frac{\log\left(\frac{1}{\delta}\right)}{n\epsilon}-\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{2n}}\geq\mu\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{\mu}_{n}-\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{2n}}\geq\mu\right)+\mathbb{P}\left(Lap\left(\frac{1}{n\epsilon}\right)-\frac{\log\left(\frac{1}{\delta}\right)}{n\epsilon}\geq
0\right)$ $\displaystyle\leq\delta+\frac{\delta}{2}=\frac{3}{2}\delta,$

where the last inequality is due to Lemma 11 and Lemma 10.

Similarly,

$\displaystyle p_{2}$
$\displaystyle\mathrel{\triangleq}\mathbb{P}\left(\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log\left(\frac{1}{\delta}\right)}{n\epsilon}+\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{2n}}\leq\mu\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{\mu}_{n}+\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{2n}}\leq\mu\right)+\mathbb{P}\left(Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log\left(\frac{1}{\delta}\right)}{n\epsilon}\leq
0\right)$ $\displaystyle\leq\delta+\frac{\delta}{2}=\frac{3}{2}\delta,$

where the last inequality is due to Lemma 11 and Lemma 10. ∎

######  Lemma 4.

Let $X_{1},X_{2},\ldots,X_{n}$ be a sequence of independent random variables
sampled from a Bernoulli distribution with mean $\mu$, and let
$\hat{\mu}_{n}=\frac{1}{n}\sum_{t=1}^{n}X_{t}$ be the sample mean. Let

$\breve{\mu}_{n}(\delta)\mathrel{\triangleq}\operatorname{Clip}_{0,1}\left(\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log(\frac{1}{\delta})}{n\epsilon}\right)$
(24)

for $\delta>0$ be the clipped and private empirical mean.

Claim 1. For any $\delta>0$ and $\alpha\in[0,\mu]$, the following inequality
holds:

$\mathbb{P}(\mu\geq\breve{\mu}_{n}(\delta)+\alpha)\leq\exp(-nd(\mu-\alpha,\mu))+\frac{1}{2}\delta$
(25)

Claim 2. Furthermore for $\delta\geq 0$, we define

$U_{n}(\delta)\mathrel{\triangleq}\max\left\\{q\in[0,1]:d\left(\breve{\mu}_{n}\left(\delta\right),q\right)\leq\frac{\log\left(\frac{1}{\delta}\right)}{n}\right\\}$
(26)

Then,

$\mathbb{P}(\mu\geq U_{n}(\delta))\leq\frac{3}{2}\delta$ (27)

###### Proof.

Here, we prove Claim 1 followed by Claim 2.

Claim 1. Since
$\breve{\mu}_{n}(\delta)=\min\left\\{\max\left\\{0,\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log(\frac{1}{\delta})}{n\epsilon}\right\\},1\right\\}$,
we have that

$\displaystyle\mu-\alpha\geq\breve{\mu}_{n}(\delta)$
$\displaystyle\Rightarrow\mu-\alpha\geq
1\quad\text{or}\quad\mu-\alpha\geq\max\left\\{0,\left(\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log(\frac{1}{\delta})}{n\epsilon}\right)\right\\}$
$\displaystyle\Rightarrow\mu-\alpha\geq\hat{\mu}_{n}+Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log(\frac{1}{\delta})}{n\epsilon}\quad(\text{since
$\mu\leq 1$})$
$\displaystyle\Rightarrow\mu-\alpha\geq\hat{\mu}_{n}\quad\text{or}\quad
Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log(\frac{1}{\delta})}{n\epsilon}\leq
0.$

It implies that

$\displaystyle\mathbb{P}(\mu\geq\breve{\mu}_{n}(\delta)+\alpha)$
$\displaystyle\leq\mathbb{P}\biggl{(}\mu\geq\hat{\mu}_{n}+\alpha\biggl{)}+\mathbb{P}\biggl{(}Lap\left(\frac{1}{n\epsilon}\right)+\frac{\log(\frac{1}{\delta})}{n\epsilon}\leq
0\biggl{)}$ $\displaystyle\leq\exp(-nd(\mu-\alpha,\mu))+\frac{1}{2}\delta.$

The last inequality is due to Equation 38 of Lemma 13 and Lemma 10.

Claim 2.

We have that the sets

$\displaystyle\\{\mu\geq U_{n}(\delta)\\}$
$\displaystyle\underset{(a)}{=}\\{\mu\geq
U_{n}(\delta)\geq\breve{\mu}_{n}(\delta)\\}$
$\displaystyle\underset{(b)}{=}\\{d(\breve{\mu}_{n}(\delta),\mu)\geq
d(\breve{\mu}_{n}(\delta),U_{n}(\delta)),\mu\geq\breve{\mu}_{n}(\delta)\\}$
$\displaystyle\underset{(c)}{=}\\{d(\breve{\mu}_{n}(\delta),\mu)\geq\frac{\log(\frac{1}{\delta})}{n},\mu\geq\breve{\mu}_{n}(\delta)\\}$
$\displaystyle\underset{(d)}{=}\left\\{\breve{\mu}_{n}(\delta)\leq\mu-\alpha\right\\}$

Here, we chose an $\alpha>0$ such that
$d(\mu-\alpha,\mu)=\frac{\log(\frac{1}{\delta})}{n}$.

Step (a) holds because $U_{n}(\delta)\geq\breve{\mu}_{n}(\delta)$ by the
definition of $U_{n}(\delta)$. Step (b) also holds true since
$d(\breve{\mu}_{n}(\delta),\cdot)$ is increasing on
$[\breve{\mu}_{n}(\delta),1]$. Since
$d(\breve{\mu}_{n}(\delta),U_{n}(\delta))=\frac{\log(\frac{1}{\delta})}{n}$ by
the definition of $U_{n}(\delta)$, we obtain the equality in Step (c).
Finally, Step (d) is obtained by inverting the relative entropy.

We conclude the proof by

$\displaystyle\mathbb{P}\\{\mu\geq U_{n}(\delta)\\}$
$\displaystyle=\mathbb{P}\left\\{\breve{\mu}_{n}(\delta)\leq\mu-\alpha\right\\}$
$\displaystyle\leq\exp(-nd(\mu-\alpha,\mu))+\frac{1}{2}\delta\quad\text{(by
{Claim 1})}$
$\displaystyle=\delta+\frac{\delta}{2}=\frac{3}{2}\delta\quad\text{(by
substituting $\alpha$)}$

∎

####  E.2 Generic Regret Analysis for Algorithm 1

Algorithm 1 is a generic framework to construct an extension of any optimistic
index-based bandit algorithm, which would satisfy $\epsilon$-global DP.  The
algorithm is based on the index $I_{a}^{\epsilon}$ of each arm.
$I_{a}^{\epsilon}$ is computed using the private empirical mean of the last
active episode of arm $a$ and is a high probability upper bound of the real
mean $\mu_{a}$.

To explicate the two conditions on arm indexes, we introduce the notation
$I_{a}^{\epsilon}(t-1,\alpha,s)$, which is the index of arm $a$, at time-step
$t$ and computed using $s$ reward samples from arm $a$.

Thus, we can express the index computed using just the last active episode as

$I_{a}^{\epsilon}(t-1,\alpha)=I_{a}^{\epsilon}(t-1,\alpha,\frac{1}{2}N_{a}(t-1)).$
(28)

Because $I_{a}^{\epsilon}(t-1,\alpha)$ only uses samples collected from the
last active episode, and due to the doubling, the last active episode’s size
is exactly half the number of times arm $a$ was pulled since the beginning.

The optimism of the index is ensured by the fact that

$\mathbb{P}\left(I_{a}^{\epsilon}(t-1,\alpha,s)\leq\mu_{a}\right)\leq\frac{3}{2}\frac{1}{t^{\alpha}}$
(29)

for every arm $a$, every sample size $s$ and every time-step $t$, where
$\alpha$ is the confidence level.

######  Theorem 11.

Let $a$ be a suboptimal arm and $\ell\in\mathbb{N}$ such that $2^{\ell}<T$.
Then, Algorithm 1 using an index $I_{a}^{\epsilon}$ satisfying Equations 28
and 29, also satisfies that for any $\alpha>3$,

$\displaystyle\mathbb{E}[N_{a}(T)]\leq
2^{\ell+1}+\mathbb{P}\left(G_{a,\ell,T}^{c}\right)T+\frac{\alpha}{\alpha-3},$

where
$G_{a,\ell,T}=\\{\operatorname{I}_{a}^{\epsilon}(T-1,\alpha,2^{\ell})<\mu^{*}\\}$
and $G_{a,\ell,T}^{c}$ is the complement of $G_{a,\ell,T}$

###### Proof.

Without loss of generality, we assume the first arm is the optimal one
($\mu^{*}=\mu_{1}$) and denote a suboptimal arm by $a$ ($1<a\leq K$).

We leverage the standard idea of UCB-type proofs: if arm $a$ is chosen at the
beginning of an episode $\ell$, then either its index at $t_{\ell}$ is larger
than the true mean of the first arm, or the true mean of the first arm is
larger than the first arm’s index at $t_{\ell}$.

Since decisions, i.e. playing the arm with the highest index, are only taken
at the beginning of an episode, we introduce $\phi$ which takes as input a
time step and outputs the time step corresponding to the beginning of an
episode. Formally, for each $t\in[K+1,T]$, let $\phi(t)=t_{\ell}$ such that
$t_{\ell}\leq t\leq t_{\ell+1}-1$. In Example 2, $\phi(5)=4$ and $\phi(9)=7$.

Formally, $\phi(t)$ is a random variable such that

$\forall t:\phi(t)\leq t\leq 2\phi(t)$ (30)

Step 1: Decomposition of $N_{a}(T)$. We observe that

$\displaystyle N_{a}(T)$
$\displaystyle=1+\sum_{t=K+1}^{T}\mathbb{I}\\{A_{t}=a\\}$
$\displaystyle=1+\sum_{t=K+1}^{T}\mathbb{I}\\{A_{t}=a\text{ and
}\operatorname{I}_{1}^{\epsilon}(\phi(t)-1,\alpha)>\mu_{1}\\}+\mathbb{I}\\{A_{t}=a\text{
and }\operatorname{I}_{1}^{\epsilon}(\phi(t)-1,\alpha)\leq\mu_{1}\\}$
$\displaystyle\leq
1+\underset{Term1}{\underbrace{N_{a}^{\prime}(T)}}+\underset{Term2}{\underbrace{\sum_{t=K+1}^{T}\mathbb{I}\\{\operatorname{I}_{1}^{\epsilon}(\phi(t)-1,\alpha)\leq\mu_{1}\\}}}$

We define
$N_{a}^{\prime}(T)\mathrel{\triangleq}\sum_{t=K+1}^{T}\mathbb{I}\\{A_{t}=a\text{
and }\operatorname{I}_{1}^{\epsilon}(t_{\ell^{\prime}}-1,\alpha)>\mu_{1}\\}$

Step 2: Decomposition of Term 1: $N_{a}^{\prime}(T)$. Let $G_{a,\ell,T}$ be
the ‘good’ event defined by

$G_{a,\ell,T}=\\{\operatorname{I}_{a}^{\epsilon}(T-1,\alpha,2^{\ell})<\mu_{1}\\}.$

The main part of the proof is decomposing $N_{a}^{\prime}(T)$ among the ‘good’
and the ‘bad’ events, i.e.

$\mathbb{E}[N_{a}^{\prime}(T)]=\mathbb{E}[\mathbb{I}\\{G_{a,\ell,T}\\}N_{a}^{\prime}(T)]+\mathbb{E}[\mathbb{I}\\{G_{a,\ell,T}^{c}\\}N_{a}^{\prime}(T)]\leq
2^{\ell+1}+\mathbb{P}(G_{a,\ell,T}^{c})T.$

$G_{a,\ell,T}^{c}$ denotes the complement of $G_{a,\ell,T}$.

To prove the last inequality, we only need to prove that when $G_{a,\ell,T}$
happens, $N_{a}^{\prime}(T)\leq 2^{\ell+1}$. We prove it by contradiction.

Hence, let us assume that $G_{a,\ell,T}$ holds but
$N_{a}^{\prime}(T)>2^{\ell+1}$.

This assumption implies that the arm $a$ is played more than $2^{\ell+1}$
times. Thus, there must exist a round $t_{\ell^{\prime}}$, where
$N_{a}(t_{\ell^{\prime}}-1)=2^{\ell+1}$, $A_{t_{\ell^{\prime}}}=i$ and
$\operatorname{I}_{1}^{\epsilon}(t_{\ell^{\prime}}-1,\alpha)\geq\mu_{1}$.
Since indices are computed only using the samples from the last active
episode, $\operatorname{I}_{a}^{\epsilon}(t_{\ell^{\prime}}-1,\alpha)$ is
computed using exactly $2^{\ell}$ reward samples from arm $a$.

Thus, we obtain

$\displaystyle\operatorname{I}_{a}^{\epsilon}(t_{\ell^{\prime}}-1,\alpha)$
$\displaystyle=\operatorname{I}_{a}^{\epsilon}(t_{\ell^{\prime}}-1,\alpha,2^{\ell})$
$\displaystyle\leq\operatorname{I}_{a}^{\epsilon}(T-1,\alpha,2^{\ell})\quad\text{(because
$t_{\ell^{\prime}}\leq T$ and
$\operatorname{I}_{a}^{\epsilon}(\cdot,\alpha,2^{\ell})$ is increasing)}$
$\displaystyle<\mu_{1}\quad\text{ (definition of $G_{a,\ell,T}$) }$
$\displaystyle\leq\operatorname{I}_{1}^{\epsilon}(t_{\ell^{\prime}}-1,\alpha)$

The last inequality contradicts the fact that $A_{t_{\ell^{\prime}}}=i$ and
thus, establishes the claim that $N_{a}^{\prime}(T)\leq 2^{\ell+1}$ under the
‘good’ event.

Step 3: Upper-bounding Term 2. To conclude,

$\displaystyle\mathbb{E}\left[\sum_{t=K+1}^{T}\mathbb{I}\\{\operatorname{I}_{1}^{\epsilon}(\phi(t)-1,\alpha)\leq\mu_{1}\\}\right]$
$\displaystyle=\sum_{t=K+1}^{T}\mathbb{P}\\{\operatorname{I}_{1}^{\epsilon}(\phi(t)-1,\alpha)\leq\mu_{1}\\}$
$\displaystyle\leq\sum_{t=K+1}^{T}\sum_{\phi=t/2}^{t}\mathbb{P}\\{\operatorname{I}_{1}^{\epsilon}(\phi-1,\alpha)\leq\mu_{1}\\}$
$\displaystyle\leq\sum_{t=K+1}^{T}\sum_{\phi=t/2}^{t}\sum_{s=1}^{\phi}\mathbb{P}\\{\operatorname{I}_{1}^{\epsilon}(\phi-1,\alpha,s)\leq\mu_{1}\\}$
$\displaystyle\leq\sum_{t=K+1}^{T}\sum_{\phi=t/2}^{t}\sum_{s=1}^{\phi}\frac{3}{2}\frac{1}{\phi^{\alpha}}\quad\quad\text{(Equation\leavevmode\nobreak\
\ref{eq:cst1})}$
$\displaystyle=\frac{3}{2}\sum_{t=K+1}^{T}\sum_{\phi=t/2}^{t}\frac{1}{\phi^{\alpha-1}}$
$\displaystyle\leq\frac{3}{2}\sum_{t=K+1}^{T}\frac{2^{\alpha-2}}{t^{\alpha-2}}\quad\text{(because
$\phi\geq\frac{t}{2}$)}$
$\displaystyle\leq\frac{3}{2}2^{\alpha-2}\int_{K}^{T}\frac{1}{x^{\alpha-2}}dx\quad\text{(sum-
integral inequality)}$
$\displaystyle\leq\frac{3}{2}2^{\alpha-2}\frac{1}{\alpha-3}\frac{1}{K^{\alpha-3}}=\frac{3}{2}\frac{2}{\alpha-3}\left(\frac{2}{K}\right)^{\alpha-3}$
$\displaystyle\leq\frac{3}{\alpha-3}$

for $\alpha>3$ and $K\geq 2$.

Here, the first inequality is due to an union bound on $\phi(t)\in[t/2,t]$
(Equation 30), and the second inequality is due to a union bound on
$N_{1}(\phi-1)$.

Step 4: Combining the Bounds on Terms 1 and 2.

$\displaystyle\mathbb{E}[N_{a}(T)]$ $\displaystyle\leq
1+2^{\ell+1}+\mathbb{P}\left(G_{a,\ell,T}^{c}\right)T+\frac{3}{\alpha-3}$
$\displaystyle=2^{\ell+1}+\mathbb{P}\left(G_{a,\ell,T}^{c}\right)T+\frac{\alpha}{\alpha-3}$

∎

Now we design indexes that satisfy the conditions of Theorem 11, namely
$\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$.

To obtain the final regret bounds, we only have to choose $\ell$ big enough
such that
$\mathbb{P}\left(\operatorname{I}_{a}(T,2^{\ell})\geq\mu_{1}\right)T$ is
negligible. This corresponds to the leading term in the regret upper-bounds,
and this is where the regrets of $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$ differ.

We explicate the issues of designing the indexes and choosing corresponding
$\ell$ in the following section, which leads to the regret upper bounds of
$\mathsf{AdaP\text{-}UCB}$ and $\mathsf{AdaP\text{-}KLUCB}$.

####  E.3 Regret Analysis for $\mathsf{AdaP\text{-}UCB}$ and
$\mathsf{AdaP\text{-}KLUCB}$

######  Theorem 7.

For rewards in $[0,1]$, $\mathsf{AdaP\text{-}UCB}$ satisfies $\epsilon$-global
DP, and for $\alpha>3$, it yields a regret

$\mathrm{Reg}_{T}({\mathsf{AdaP\text{-}UCB}}{},\nu)\leq\sum_{a:\Delta_{a}>0}\left(\frac{16\alpha}{\min\\{\Delta_{a},\epsilon\\}}\log(T)+\frac{3\alpha}{\alpha-3}\right).$

###### Proof.

The proof is constituted of three steps.

Step 1: Designing an Index satisfying Equation (28), Equation (29), and
$\epsilon$-global DP. For $\mathsf{AdaP\text{-}UCB}$, the index is defined as

$\operatorname{I}_{a}^{\epsilon}(t_{\ell}-1,\alpha)=\tilde{\mu}_{a,\epsilon}^{\ell}+\sqrt{\frac{\alpha\log(t_{\ell})}{2\times\frac{1}{2}N_{a}(t_{\ell}-1)}}+\frac{\alpha\log(t_{\ell})}{\epsilon\times\frac{1}{2}N_{a}(t_{\ell}-1)},$

where

$\tilde{\mu}_{a,\epsilon}^{\ell}=\hat{\mu}_{a,\frac{1}{2}N_{a}(t_{\ell}-1)}+Lap\left(\frac{1}{\epsilon\times\frac{1}{2}N_{a}(t_{\ell}-1)}\right)$
(31)

is the private empirical mean of arm $a$ computed using only samples from the
last active episode, and $\hat{\mu}_{a,s}$ is the empirical mean of arm $a$
calculated using $s$ samples of reward from arm $a$.

This index verifies the first condition (Equation 28) of Theorem 11.

The second condition (Equation 29) of Theorem 11 follows directly from
Equation 23 of Lemma 3

By Theorem 6,$\mathsf{AdaP\text{-}UCB}$ is $\epsilon$-global DP.

By Theorem 11, for every suboptimal arm $a$, we have that

$\mathbb{E}[N_{a}(T)]\leq
2^{\ell+1}+\mathbb{P}\left(G_{a,\ell,T}^{c}\right)T+\frac{\alpha}{\alpha-3},$

where

$G_{a,\ell,T}=\left\\{\hat{\mu}_{a,2^{\ell}}+Lap\left(\frac{1}{2^{\ell}\epsilon}\right)+\sqrt{\frac{\alpha\log(T)}{2\times
2^{\ell}}}+\frac{\alpha\log(T)}{\epsilon 2^{\ell}}<\mu_{1}\right\\}.$

Step 2: Choosing an $\ell$. Now, we observe that

$\displaystyle\mathbb{P}(G_{a,\ell,T}^{c})$
$\displaystyle=\mathbb{P}\left(\hat{\mu}_{a,2^{\ell}}+Lap\left(\frac{1}{2^{\ell}\epsilon}\right)+\sqrt{\frac{\alpha\log(T)}{2\times
2^{\ell}}}+\frac{\alpha\log(T)}{\epsilon 2^{\ell}}\geq\mu_{1}\right)$
$\displaystyle=\mathbb{P}\left(\hat{\mu}_{a,2^{\ell}}+Lap\left(\frac{1}{2^{\ell}\epsilon}\right)-\sqrt{\frac{\alpha\log(T)}{2\times
2^{\ell}}}-\frac{\alpha\log(T)}{\epsilon 2^{\ell}}\geq\mu_{a}+\gamma\right)$

for $\gamma=\left(\Delta_{a}-2\sqrt{\frac{\alpha\log(T)}{2\times
2^{\ell}}}-2\frac{\alpha\log(T)}{\epsilon 2^{\ell}}\right)$.

The idea is to choose $\ell$ big enough so that $\gamma\geq 0$.

Let us consider the contrary, i.e.

$\displaystyle\gamma<0$
$\displaystyle\Rightarrow\sqrt{2^{\ell}}<\sqrt{\frac{\alpha\log(T)}{2\Delta_{a}^{2}}}\left(1+\sqrt{1+\frac{4\Delta_{a}}{\epsilon}}\right)$
$\displaystyle\Rightarrow
2^{\ell}<\frac{\alpha\log(T)}{2\Delta_{a}^{2}}\left(4+\frac{8\Delta_{a}}{\epsilon}\right)$
$\displaystyle\Rightarrow
2^{\ell}<\frac{4\alpha\log(T)}{\Delta_{a}\min\\{\epsilon,2\Delta_{a}\\}}.$
(32)

Thus, by choosing

$\ell=\left\lceil\frac{1}{\log(2)}\log\left(\frac{4\alpha\log(T)}{\Delta_{a}\min\\{\epsilon,2\Delta_{a}\\}}\right)\right\rceil$

we ensure $\gamma>0$. This also implies that

$\mathbb{P}(G_{a,\ell,T}^{c})\leq\mathbb{P}\left(\hat{\mu}_{a,2^{\ell}}+Lap\left(\frac{1}{2^{\ell}\epsilon}\right)-\sqrt{\frac{\alpha\log(T)}{2\times
2^{\ell}}}-\frac{\alpha\log(T)}{\epsilon
2^{\ell}}\geq\mu_{a}\right)\leq\frac{3}{2T^{\alpha}}$

The last inequality is due to Equation 22 of Lemma 3.

Step 3: The Regret Bound. Combining Steps 1 and 2, we get that

$\displaystyle\mathbb{E}[N_{a}(T)]$
$\displaystyle\leq\frac{\alpha}{\alpha-3}+2^{\ell+1}+T\times\frac{3}{2T^{\alpha}}$
$\displaystyle\leq\frac{16\alpha\log(T)}{\Delta_{a}\min\\{\epsilon,2\Delta_{a}\\}}+\frac{3\alpha}{\alpha-3}.$
(33)

Plugging this upper bound back in the definition of problem-dependent regret
concludes the proof. ∎

######  Remark 3.

The leading term of the regret is
$\frac{16\alpha\log(T)}{\Delta_{a}\min\\{\epsilon,2\Delta_{a}\\}}$, which is
$4$ times more than what we got from Equation E.3. A multiplicative factor of
$2$ is introduced due to the doubling and another multiplicative factor of $2$
is due to the forgetting. Thus, the combined price of doubling and forgetting
is a multiplicative constant $4$ in the leading term of regret.

######  Theorem 8.

When the rewards are sampled from Bernoulli distributions,
$\mathsf{AdaP\text{-}KLUCB}$ satisfies $\epsilon$-global DP, and for
$\alpha>3$ and constants $C_{1}(\alpha),C_{2}>0$, it yields a regret

$\mathrm{Reg}_{T}({\mathsf{AdaP\text{-}KLUCB}}{},\nu)\leq\sum_{a:\Delta_{a}>0}\left(\frac{C_{1}(\alpha)\Delta_{a}}{\min\\{d(\mu_{a},\mu^{*}),C_{2}\epsilon\Delta_{a}\\}}\log(T)+\frac{\alpha}{\alpha-3}\right).$

###### Proof.

The proof is constituted of three steps.

Step 1: Designing an Index satisfying Equation (28), Equation (29), and
$\epsilon$-global DP. For $\mathsf{AdaP\text{-}KLUCB}$, the index is defined
as

$\displaystyle\operatorname{I}_{a}^{\epsilon}(t_{\ell}-1,\alpha)$