# Differentially Private Stochastic Linear Bandits:
(Almost) for Free

Osama A. Hanna The first and second authors made equal contribution. Antonious
M. Girgis11footnotemark: 1 Christina Fragouli  Suhas Diggavi

(University of California, Los Angeles, USA
Email:{ohanna, amgirgis, christina.fragouli<EMAIL_ADDRESS>)

###### Abstract

In this paper, we propose differentially private algorithms for the problem of
stochastic linear bandits in the central, local and shuffled models. In the
central model, we achieve almost the same regret as the optimal non-private
algorithms, which means we get privacy for free. In particular, we achieve a
regret of $\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$ matching the known lower
bound for private linear bandits, while the best previously known algorithm
achieves $\tilde{O}(\frac{1}{\epsilon}\sqrt{T})$. In the local case, we
achieve a regret of $\tilde{O}(\frac{1}{\epsilon}{\sqrt{T}})$ which matches
the non-private regret for constant $\epsilon$, but suffers a regret penalty
when $\epsilon$ is small. In the shuffled model, we also achieve regret of
$\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$ while the best previously known
algorithm suffers a regret of $\tilde{O}(\frac{1}{\epsilon}{T^{3/5}})$. Our
numerical evaluation validates our theoretical results.

##  1 Introduction

Stochastic linear bandits offer a sequential decision framework where a
learner interacts with an environment over rounds, and decides what is the
optimal (from a potentially infinite set) action to play so as to achieve the
best possible reward (minimize her regret). In particular, at each round, the
learner may take into account all past rewards and actions to decide the next
action to play, and in return receive a new reward. This model has been widely
adopted both in theory but also in a number of applications, including
recommendation systems, health, online education, and resource allocation [1,
2, 3, 4]. Motivated by the fact that many of these applications are privacy-
sensitive, in this paper we explore what is the performance in terms of regret
we can achieve, if we are constrained to use a privacy-preserving stochastic
linear bandit algorithm.

In particular, in this paper we aim to design algorithms that preserve the
privacy of the rewards, from an adversary that can observe all actions that
the learner plays. We assume that the learner is connected through a secure
communication channel with clients, who play the requested actions. For
example, the central learner may make restaurant recommendations to mobile
devices, may regulate the operation of on-body sensors in senior living
communities, may decide what educational exercises to provide to students, or
what jobs to allocate to workers. The actions the clients play - what
restaurant is visited, which sensor is activated, what is the exercise solved,
what is the job performed - may be naturally visible especially in public
environments. What we care to protect are the rewards, that may capture
private information, such as personal preferences in recommendation systems,
health indices in online health, perfomance in online education, and income
gained in resource allocation. Our goal is to design algorithms that preserve
the privacy of the rewards, while still (almost) achieve the same regret as
the traditional algorithms that do not take privacy into consideration.

We do so for three different setups, depicted in Figure 1, in each case
measuring the privacy using Differential Privacy (DP) measures [5, 6]. In the
central DP model, the learner is a trusted server. The server employs a DP
mechanism on aggregates of the reward realizations she collects, to ensure
that the actions do not reveal information on the rewards. In the local DP
model, the learner is an untrusted server. The clients provide privatized
rewards to the server, who then uses this noisy input to decide her next
actions. In the shuffled model, the learner is still an untrusted server, but
now a trusted node, that can act as a relay in the communication between the
clients and the server, serves as a shuffler, and can randomly permute the
privatized rewards before making them available to the server. A shuffler
offers a privacy-amplification mechanism that has recently become popular in
the literature, as it is easy to implement (simply takes a set of inputs and
randomly permutes them), and may enable better privacy-regret performance [7,
8, 9, 10, 11].

(a) Central model.

(b) Local model.

(c) Shuffled model.

Figure 1:  In case (a) the server is trusted, and we ensure that the publicly
observable actions maintain privacy of the rewards. In (b) and (c) we maintain
privacy from an untrusted server.

Our main contributions are as follows.
$\bullet$ For the central DP model, we design an algorithm that guarantees
$\epsilon$-DP (see Definition 1 in Section 2) and achieves regret that matches
existing lower bounds. In particular, over $T$ rounds, it achieves regret
$R_{T}=O\left(\sqrt{T\log T}+\frac{\log^{2}T}{\epsilon}\right)$ w.h.p., which
is optimal within a $\log T$ factor: a lower bound of $O(\sqrt{T})$ is proven
in [12] for non-private linear bandits, while a lower bound of $O(\frac{\log
T}{\epsilon})$ is shown in [13] for $\epsilon$-DP linear bandits. Note that
for $\epsilon\approx 1$ (perhaps the most common case) the dominant term
$O(\sqrt{T\log T})$ matches the regret of the best known algorithms for the
non-private case (eg., LinUCB [14, 12]), and hence, we get privacy for free.
$\bullet$ For the local DP model, we design an algorithm that guarantees
$\epsilon_{0}$-LDP (see Definition 2 in Section 2) and achieves regret
$R_{T}=\mathcal{O}\left(\sqrt{T\log(T)}/\epsilon_{0}\right)$ w.h.p.; this
regret matches the non-private regret for constant $\epsilon_{0}$, but suffers
a regret penalty when $\epsilon_{0}$ is small. Although our algorithm does not
improve the regret order as compared to the best-known algorithm for private
(contextual) linear bandits in [15], it offers an alternative approach that
serves as a foundation for the shuffled case.
$\bullet$ For the shuffled model, we leverage the help of a trusted shuffler
to ensure both that the output of each client satisfies $\epsilon_{0}$-LDP and
that the output of the secure shuffler satisfies $\epsilon$-DP requirements.
Our algorithm achieves regret
$R_{T}=\mathcal{O}\left(\sqrt{T\log(T)}+\frac{\log(T)}{\epsilon}\right)$
w.h.p. that matches the regret of the best non-private algorithms, same as the
central model. Furthermore, our algorithm outperforms the best known algorithm
for private (contextual) linear bandits in [16, 17] that use shuffling.

Our results are summarized in Table I, where we also provide known results in
the literature (see also discussion next). To the best of our knowledge, in
all three cases, our algorithms achieve the best currently known results for
private linear bandits, significantly improving from the previously best known
results in the case of the central and shuffled model, and closely matching in
some cases existing lower bounds.

Our Work vs. Related Work. Differential Privacy (DP) algorithms have been
proposed for the generic multi-armed bandits (MAB) problems [18, 19, 20], yet
these algorithms would not work well for linear bandits, as linear bandits
allow for an infinite set of actions while generic MAB have a regret that
increases with the number of actions. Closer to ours is work on DP for
contextual linear bandits [13, 21, 15, 16]; indeed, linear bandits can be
viewed as (a special case of) contextual linear bandit setup with a single
context. The work in [13] considers contextual linear bandits with DP in a
centralized setting and propose an algorithm that achieves a regret of
$\tilde{O}(\sqrt{T}/\epsilon)$. This does not match the best known lower bound
for the centralized setting of $\Omega(\sqrt{T}+\log(T)/\epsilon)$ [13]. Our
work achieves the lower bound of $\Omega(\sqrt{T}+\log(T)/\epsilon)$ up to
logarithmic factors for the special case of stochastic linear bandits. The
work in [21] considers contextual linear bandits with LDP, where the contexts
can be adversarial. The work proposes an algorithm that achieves a regret of
$\tilde{O}(T^{3/4}/\epsilon_{0})$ and conjectures that the regret is optimal
up to a logarithmic factor. The authors in [15] consider a special case, where
the contexts are generated from a distribution, and propose a method that
achieves a regret of $\tilde{O}(\sqrt{T}/\epsilon_{0})$ under certain
assumptions on the context distribution. Our algorithm for the local model
achieves the same regret order using an alternative method. The works in [16,
17] consider contextual linear bandits in the shuffled model where the best
known algorithm achieves a regret of $\tilde{O}(T^{3/5})$. Our proposed
algorithms achieve a regret of $\tilde{O}(\sqrt{T}+1/\epsilon)$, matching the
information theoretic lower bound in [13], for stochastic linear bandits in
the shuffled model. A summary of the best results for DP contextual linear
bandits and our results is presented in Table 1.

Paper organization. We present the problem formulation in Section 2. We design
and analyze privacy-preserving linear bandit algorithms for the central model
in Section 3, for the local model in Section 4 and for the shuffled model in
Section 5. We provide numerical results in Section 6.

Algorithm | Regret Bound | Context | Privacy Model
---|---|---|---
Central DP | Local DP
Central DP [13] | $\tilde{\mathcal{O}}\left(\frac{\sqrt{T}}{\epsilon}\right)$ | Adversarial | $\left(\epsilon,\delta\right)$ | N/A
LDP [21] | $\tilde{\mathcal{O}}\left(\frac{T^{3/4}}{\epsilon_{0}}\right)$ | Adversarial | $\left(\epsilon=\epsilon_{0},\delta\right)$ | $\left(\epsilon_{0},\delta\right)$
LDP+shuffling [16] | $\tilde{\mathcal{O}}\left(\frac{T^{2/3}}{\epsilon^{1/3}}\right)$ | Adversarial | $\left(\epsilon,\delta\right)$ | $\left(\epsilon_{0}=\epsilon^{2/3}T^{1/6},\delta\right)$
LDP [15] | $\tilde{\mathcal{O}}\left(\frac{\sqrt{T}}{\epsilon_{0}}\right)$ | Stochastic | $\left(\epsilon=\epsilon_{0},\delta\right)$ | $\left(\epsilon_{0},\delta\right)$
Central DP (Theorem 1) | $\tilde{\mathcal{O}}\left(\sqrt{T}+\frac{1}{\epsilon}\right)$ | Free | $\left(\epsilon,0\right)$ | N/A
LDP (Theorem 2) | $\tilde{\mathcal{O}}\left(\frac{\sqrt{T}}{\epsilon_{0}}\right)$ | Free | $\left(\epsilon=\epsilon_{0},0\right)$ | $\left(\epsilon_{0},0\right)$
LDP+shuffling(Theorem 3) | $\tilde{\mathcal{O}}\left(\sqrt{T}+\frac{1}{\epsilon}\right)$ | Free | $\left(\epsilon,\delta\right)$ | $\left(\epsilon_{0}=\epsilon T^{1/4},0\right)$
Table 1: Upper part: known results. Lower part: our results. The
$\tilde{\mathcal{O}}$ notation hides the dependencies on the dimension $d$,
privacy parameter $\delta$ and $\log$ factors.

##  2 Notation and Problem Formulation

Stochastic linear bandits. In stochastic linear bandits a learner interacts
with clients over $T$ rounds by taking a sequence of decisions and receiving
rewards. In particular, at each round $t\in[T]$, the learner plays an action
$a_{t}$ from a set $\mathcal{A}\subset\mathbb{R}^{d}$ and receives a reward
$r_{t}\in\mathbb{R}$. The reward $r_{t}$ is a noisy linear function of the
action, i.e., $r_{t}=\langle\theta_{*},a_{t}\rangle+\eta_{t}$, where
$\langle.\rangle$ denotes inner product, $\eta_{t}$ is an independent zero-
mean noise and $\theta_{*}\in\mathbb{R}^{d}$ is an unknown parameter vector.
The goal of the learner is to minimize the total regret over the $T$ rounds,
which is calculated as:

$~{}R_{T}=T\max_{a\in\mathcal{A}}\langle\theta_{*},a\rangle-\sum_{t=1}^{T}\langle\theta_{*},a_{t}\rangle.$
(1)

The regret captures the difference between the reward for the optimal action
and the rewards for the actions chosen by the learner. The basic approach in
all algorithms is to play actions that enable the learner to learn
$\theta_{*}$ well enough to identify a (near) optimal action. The best known
algorithms (for example, LinUCB [14, 12]) achieve a regret of order
$O(\sqrt{T\log T})$, which is the best we can hope for (matches existing lower
bounds [12]).

In this paper, we make the following standard assumptions (see, e.g., [14,
13]).

######  Assumption 1.

We consider stochastic linear bandits with:
1\. Sub-gaussian noise: $\mathbb{E}[\eta_{t+1}|\mathcal{F}_{t}]=0$ and
$\mathbb{E}[\exp(\lambda\eta_{t+1})|\mathcal{F}_{t}]\leq\exp(\frac{\lambda^{2}}{2})\forall\lambda\in\mathbb{R}$,
where $\mathcal{F}_{t}=\sigma(a_{1},r_{1},...,a_{t},r_{t})$ is the
$\sigma$-field summarizing the information available before round $t$.
2\. Bounded actions: $\|a\|_{2}\leq 1\ \forall a\in\mathcal{A}$.
3\. Bounded unknown parameter: $\|\theta_{*}\|_{2}\leq 1$.
4\. Bounded rewards: $|r_{t}|\leq 1$.

Privacy Goal and Measures. Our goal in this paper is to achieve the minimum
possible regret in (1) while preserving privacy of the rewards
$\\{r_{t}\\}_{t\in[T]}$ (as discussed in Section 1 the rewards can represent
sensitive information of the clients). To measure privacy, we use the popular
central and local differential privacy definitions that we provide for
completeness next. For simplicity, we assume that a different client plays
each action (e.g., visits a recommended restaurant).

Differential Privacy (DP). We say that two sequences of rewards
$\mathcal{R}=(r_{1},\ldots,r_{T})$ and
$\mathcal{R}^{\prime}=(r^{\prime}_{1},\ldots,r^{\prime}_{T})$ are neighboring
if they differ in a single reward, i.e., there is a round $t\in[T]$ such that
$r_{t}\neq r^{\prime}_{t}$, but $r_{j}=r^{\prime}_{j}$ for all $j\neq t$. To
preserve privacy, we use a randomized mechanism $\mathcal{M}$ designed for
stochastic linear bandits, that observes rewards and outputs publicly
observable actions.

######  Definition 1.

([5, 6]): A randomized mechanism $\mathcal{M}$ for stochastic linear bandits
is said to be $\left(\epsilon,\delta\right)$ Differentially Private
($\left(\epsilon,\delta\right)$-DP) if for any two neighboring sequences of
rewards $\mathcal{R}=(r_{1},\ldots,r_{T})$ and
$\mathcal{R}^{\prime}=(r^{\prime}_{1},\ldots,r^{\prime}_{T})$, and any subset
of outputs $\mathcal{O}\subset\mathcal{A}^{T}$, $\mathcal{M}$ satisfies:

$\Pr[\mathcal{M}\left(\mathcal{R}\right)\in\mathcal{O}]\leq
e^{\epsilon}\Pr[\mathcal{M}\left(\mathcal{R}^{\prime}\right)\in\mathcal{O}]+\delta.$
(2)

When $\delta=0$, we say that the mechanism $\mathcal{M}$ is pure
differentially private ($\epsilon$-DP). The DP mechanisms maintain that the
distribution on the output of the mechanism does not significantly change when
replacing a single client with reward $r_{t}$ with another client with reward
$r^{\prime}_{t}$. Thus, the adversary observing the output of the DP mechanism
does not infer the clients rewards.

Local Differential Privacy (LDP). If the central learner is untrusted, we need
a local private mechanism $\mathcal{M}$ whose output is all the information
available to the central learner. We denote the range of the output of the
local mechanism by $\mathcal{Z}$.

######  Definition 2.

([22]) A randomized mechanism $\mathcal{M}:[-1,1]\to\mathcal{Z}$ is said to be
$\left(\epsilon_{0},\delta_{0}\right)$ Local Differentially Private
($\left(\epsilon_{0},\delta_{0}\right)$-LDP) if for any rewards $r_{t}$ and
$r^{\prime}_{t}$, and any subset of outputs $\mathcal{O}\subset\mathcal{Z}$,
the algorithm $\mathcal{M}$ satisfies:

$\Pr[\mathcal{M}\left(r_{t}\right)\in\mathcal{O}]\leq
e^{\epsilon_{0}}\Pr[\mathcal{M}\left(r^{\prime}_{t}\right)\in\mathcal{O}]+\delta_{0}.$
(3)

Similar to the DP definition, we say that $\mathcal{M}$ is pure locally
differentially private ($\epsilon_{0}$-LDP) when $\delta_{0}=0$. Observe that
the input of the LDP mechanism is a single reward, and hence, each client
preserves privacy of her observed reward $r_{t}$, even if the adversary knows
what is the action she plays and observes a function of her reward.

System Model. We consider three different models for private stochastic linear
bandits. In all three cases, our setup is that of a learner, who asks clients
to play publicly observable actions, and collects the resulting rewards using
a secure communication channel (see Figure 1). The models differ on whether
the learner is a trusted or untrusted server, and whether a shuffler is
available or not. A shuffler simply performs a random permutation on its
input.
1) Central DP model: The learner is a trusted server who can collect the
clients’ rewards and take actions. Thus, the trusted server can apply a DP
mechanism (see Definition 1) to preserve the privacy of the collected rewards
against any adversary observing the actions of the clients.
2) LDP model: The learner is an untrusted server. Hence, each client needs to
privatize her own reward by applying an LDP mechanism (see Definition 2)
before sending it to the untrusted server. The server takes decisions on next
actions using the collected privatized rewards.
3) Shuffled model: Similar to the LDP model, the learner is an untrusted
server. However, we consider that there exists a trusted shuffler that
collects the LDP responses of the clients and randomly permutes them before
passing them to the server, see Figure 1.

##  3 Stochastic Linear Bandits with central DP

In this section we consider the case where the learner is a trusted server. We
present an algorithm that offers $\epsilon$-DP (see Definition 1) for
stochastic linear bandits, with no regret penalty: we achieve the same order
regret performance as the best algorithms that operate under no privacy
considerations.

Main Idea. Our algorithm follows the structure of elimination algorithms: it
runs in batches, where in each batch $i$ we maintain a “good set of actions”
$\mathcal{A}_{i},$ that almost surely contain the optimal one, and gradually
eliminate sub-optimal actions, shrinking the sets $\mathcal{A}_{i}$ as $i$
increases. As is fairly standard in elimination algorithms, in our case as
well, during batch $i$, the learner plays actions in $\mathcal{A}_{i}$,
calculates an updated estimate $\hat{\theta}_{i}$ of the unknown parameter
vector $\theta_{*}$, and eliminates from $\mathcal{A}_{i}$ actions if their
estimated reward is $2\gamma_{i}$ from the estimated reward of the arm that
appears to be best, where $\gamma_{i}$ is the confidence of the reward
estimates.

Our new idea, that enables to make our algorithm offer $\epsilon$-DP, is at a
high level as follows. If by playing a smaller number of distinct actions we
are able to identify the optimal action, we need to overall add a smaller
amount of noise to guarantee privacy than if we play a larger number of
distinct actions. Indeed, if an action $a$ is played for $n_{a}$ times, the
learner, to estimate $\theta_{*}$, only needs to use the sum of these $n_{a}$
rewards. To offer $\epsilon$-DP we can perturb this sum by adding independent
Laplacian noise (Lap($\frac{1}{\epsilon}$)); clearly, the smaller the number
of distinct actions we play, the smaller the overall amount of noise we need
to add. Thus our algorithm, at each batch iteration $i$, plays actions from a
carefully selected subset of $\mathcal{A}_{i}$, of cardinality as small as
possible. The technical question we address is, starting from a continuous
action space $\mathcal{A}$, how to select at each batch iteration a small
cardinality subset that maintains the ability to identify the optimal action.

We next describe the steps in implementing this idea. Recall that our actions
come from a set $\mathcal{A}\subseteq\mathbb{R}^{d}$, and we assume they are
bounded, namely, $\|a\|_{2}\leq 1,\ \forall a\in\mathcal{A}$ (see Assumptions
1 in Section 2).
${\bf 1.}$ Our first step is to reduce the continuous action space to a
discrete action space problem. To do so, we finely discretize $\mathcal{A}$ to
create what we call a $\zeta$-net, a discrete set of actions
$\mathcal{N}_{\zeta}\subseteq\mathcal{A}$ such that distances are
approximately preserved. Namely, for any $a\in\mathcal{A}$, there is some
$a^{\prime}\in\mathcal{N}_{\zeta}$ with $\|a^{\prime}-a\|_{2}\leq\zeta$. Lemma
1, proved in [23, Cor. 4.2.13], states that we can always find such a discrete
set with cardinality at most $(\frac{3}{\zeta})^{d}+d$. As a result, all the
“good sets” $\mathcal{A}_{i}$ will also be discrete.

######  Lemma 1.

( $\zeta$-net for $\mathcal{A}$ [23]) For any set
$\mathcal{A}\subseteq\\{x\in\mathbb{R}^{d}|\|x\|_{2}\leq 1\\}$ that spans
$\mathbb{R}^{d}$, there is a set $\mathcal{N}_{\zeta}\subseteq\mathcal{A}$
($zeta$-net) with cardinality at most $(\frac{3}{\zeta})^{d}+d$ such that
$\mathcal{N}_{\zeta}$ spans $\mathbb{R}^{d}$, and for any $a\in\mathcal{A}$,
there is some $a^{\prime}\in\mathcal{N}_{\zeta}$ with
$\|a^{\prime}-a\|_{2}\leq\zeta$.

${\bf 2.}$ We introduce the use of a core set $\mathcal{C}_{i}$, a subset of
the actions of the set of “good actions” $\mathcal{A}_{i}$. During batch $i$,
the learner only plays actions in $\mathcal{C}_{i}$, each with some
probability $\pi_{i}(a)$. Lemma 2, proved in[Ch.21] [24], states that if
$\mathcal{A}_{i}$ spans some space $\mathbf{R}^{k}$, we can find a core set of
size at most $Bk$ (with $B$ a constant) and an associated probability
distribution $\pi$, so that, playing actions only from $C_{i}$ enables to
calculate a good estimate of $\langle a,\theta_{*}\rangle$ for each
$a\in\mathcal{A}_{i}$ .

######  Lemma 2.

(Core set for $\mathcal{A}$ [24]) For any finite set of actions
$\mathcal{A}\subset\\{x\in\mathbf{R}^{d}|\|x\|_{2}\leq 1\\}$ that spans
$\mathbb{R}^{d}$, there is a subset $\mathcal{C}$ of size at most $Bd$ that
spans $\mathbb{R}^{d}$, where $B$ is a constant, and a distribution $\pi$ on
$\mathcal{C}$ such that for any $a\in\mathcal{A}$

$a^{\top}\left(\sum_{\alpha\in\mathcal{C}}\pi(\alpha)\alpha\alpha^{\top}\right)^{-1}a\leq
2d.$ (4)

Moreover, $\mathcal{C}$ and $\pi$ can be found in polynomial time in $d$.

3. To preserve the privacy of rewards, we perturb the sum rewards of each action by adding Laplace noise. Adding noise affects the confidence of the reward estimates $\gamma$ (step 5 in Algorithm 1 shows that $\gamma$ increases as $\epsilon$ decreases), and thus delays the elimination of bad actions and increases the regret by an additive term of $\tilde{O}(\frac{1}{\epsilon})$. Replacing a possibly large set $\mathcal{A}_{i}$ with the smaller core set $\mathcal{C}_{i}$ effectively decreases the cumulative noise affecting the estimate of $\theta_{*}$.

Remark. The computation of $\mathcal{C},\pi$ can be formulated as a convex
optimization problem with many efficient approximation algorithms available.
One example is the Franke-Wolfe algorithm [25, 24] that starts with an
initialization of $\pi$, $\pi_{0}$ and updates it according to

$\pi_{i+1}(a)=(1-\nu_{i})\pi_{i}(a)+\nu_{i}\mathbf{1}(a=\arg\max_{\alpha\in\mathcal{A}}\|\alpha\|^{2}_{V(\pi_{i})^{-1}}),$
(5)

where
$V(\pi_{i})=\sum_{\alpha\in\mathcal{A}}\pi_{i}(\alpha)\alpha\alpha^{\top}$ and
$\nu_{i}$ is a step size. If $\pi_{0}$ is chosen to be the uniform
distribution over $\mathcal{A}$, then in $O(d\log\log|\mathcal{A}|)$
iterations we can find a $\pi$, and $\mathcal{C}=\\{a\in\mathcal{A}|\pi(a)\neq
0\\}$ that satisfy (4). Using a more sophisticated initialization, the
dependence on $|\mathcal{A}|$ in the number of iterations can be eliminated
entirely and the core set is guaranteed to have size of $O(d)$.

Algorithm Pseudo-Code. Our algorithm pseudo-code in Algorithm 1, starts by
initializing the good action set $\mathcal{A}_{1}$ to be an $\frac{1}{T}$-net
of $\mathcal{A}$ according to Lemma 1. Then, the algorithm operates in batches
that grow exponentially in length, where the length of batch $i$ is
approximately $q^{i}$ and $q=(2T)^{1/\log T}$111We note that $e\leq q\leq
e^{2}$.. In each batch $i$, we construct the core set $C_{i}$ and the
associated distribution $\pi_{i}$ $\mathcal{A}_{i}$ as per Lemma 2. Each
action in $\mathcal{C}_{i}$ is pulled $n_{ia}=\lceil\pi(a)q^{i}\rceil$ times,
where the length of batch $i$ is $n_{i}=\sum_{a\in\mathcal{C}_{i}}n_{ia}$. To
preserve privacy, the sum of the rewards of each action is perturbed with
Lap$(\frac{1}{\epsilon})$ noise. The learner uses these privatized sum rewards
to compute the least squares estimate of $\theta_{*}$, $\hat{\theta}_{i}$. At
the end of batch $i$ the learner eliminates from $\mathcal{A}_{i}$ the actions
with estimated mean reward, $\langle a,\hat{\theta}_{i}\rangle$, that fail to
be within $2\gamma_{i}$ from the action that appears to be best, where
$\gamma_{i}$ is our confidence in the mean estimates. After the iteration
$i=\log T-1$ is completed, the learner simply plays the action that appears to
be best.

Algorithm 1 $\epsilon$-DP algorithm for stochastic linear bandits: central
model

1:Input: set of actions $\mathcal{A}$, time horizon $T$, and privacy parameter
$\epsilon$.

2:Let $\mathcal{A}_{1}$ be a $\zeta$-net for $\mathcal{A}$ as in Lemma 1, with
$\zeta=\frac{1}{T}$.

3:$q\leftarrow(2T)^{1/\log T}$.

4:for $i=1:\log(T)-1$ do

5:
$\gamma_{i}\leftarrow\sqrt{\frac{4d}{q^{i}}\log\left(4|\mathcal{A}_{i}|T^{2}\right)}+\frac{2Bd^{2}+2d\log\left(4|\mathcal{A}_{i}|T^{2}\right)}{\epsilon
q^{i}}$.

6: For $\mathcal{A}_{i}\subseteq\mathbf{R}^{m}$, $m\leq d$, let
$\mathcal{C}_{i}$ be a core set of size at most $Bm$ as in Lemma 2 and
$\pi_{i}$ the associated distribution.

7: Pull each action $a\in\mathcal{C}_{i}$,
$n_{ia}=\lceil{\pi_{i}(a)q^{i}}\rceil$ times to get rewards
$r_{ia}^{(1)},...,r_{ia}^{(n_{ia})}$.

8: $\bar{r}_{ia}\leftarrow\sum_{k=1}^{n_{ia}}r_{ia}^{(k)},\
\hat{r}_{ia}\leftarrow\bar{r}_{ia}+z_{ia}\ \forall a\in\mathcal{C}_{i}$, where
$z_{ia}$ is an independent noise that follows
$\mathsf{Lap}(\frac{1}{\epsilon})$.

9: $V\leftarrow\sum_{a\in\mathcal{C}_{i}}n_{ia}aa^{\top},\
\hat{\theta}_{i}\leftarrow V^{-1}\sum_{a\in\mathcal{C}_{i}}\hat{r}_{ia}a$.

10: $\mathcal{A}_{i+1}\leftarrow\\{a\in\mathcal{A}_{i}|\langle
a,\hat{\theta}_{i}\rangle\geq\max_{\alpha\in\mathcal{A}}\langle\alpha,\hat{\theta}_{i}\rangle-2\gamma_{i}\\}$

11:Play action
$\arg\max_{\alpha\in\mathcal{A}_{\log(T)-1}}\langle\alpha,\hat{\theta}_{\log(T)-1}\rangle$
for the remaining time.

Algorithm Performance. We next prove that Algorithm 1 is $\epsilon$-DP and
provide a bound on its regret.

######  Theorem 1.

Algorithm 1 is $\epsilon$-differentially private. Moreover, it achieves a
regret

$R_{T}\leq C\left(\sqrt{T\log T}+\frac{\log^{2}T}{\epsilon}\right),$ (6)

with probability at least $1-\frac{1}{T}$, where $C$ is a constant that does
not depend on $\epsilon,T$.

Proof Outline. The privacy result follows from the Laplace mechanism [6]. To
bound the regret, we first argue that with probability at least
$1-\frac{1}{T}$, and for all $i$ and all $a\in\mathcal{A}_{i}$, we have that
$|\langle a,\hat{\theta}_{i}\rangle-\langle
a,\hat{\theta}_{\star}\rangle|\leq\gamma_{i}$. Conditioned on this event, an
action with gap $\Delta_{a}$ is eliminated when, or before,
$\gamma_{i}<\Delta_{a}/2$. Hence, all actions in batch $i$ have gap that is at
most $4\gamma_{i}$. The regret bound follows by summing $4\gamma_{i}n_{i}$ for
all batches. The complete proof is provided in Appendix A. $\square$

######  Remark 1.

We note that the high probability bound in Theorem 1 implies a bound in
expectation

$\mathbb{E}[R_{T}]\leq C\left(\sqrt{T\log
T}+\frac{\log^{2}T}{\epsilon}\right).$ (7)

This is because the regret is trivially $O(T)$ and the algorithm fails with
probability $\frac{1}{T}$, which overall contributes $O(1)$ to the
expectation.

######  Remark 2.

The regret in Theorem 1 is optimal up to $\log T$ factor; a lower bound of
$O(\sqrt{T})$ is proven in [12] for the non-private case, while a lower bound
of $\frac{\log T}{\epsilon}$ is shown in [13] for the private case.

######  Remark 3.

We observe that the privacy parameter $\epsilon$ is typically $\approx 1$. In
this case, the dominating term in the regret in (11) is $O(\sqrt{T\log T})$
which matches the regret of the best known algorithm for the non-private case
(see LinUCB in [12, 14]), and hence, we get privacy for free.

##  4 Stochastic Linear Bandits with LDP

In this section, the learner is an untrusted server, and thus we design a
linear bandit algorithm (Algorithm 2) that operates under LDP constraints.

Main Idea. As in Algorithm 1, we here also utilize a core set of actions; the
difference is that, since the server is untrusted, each client privatizes her
own reward before providing it to the server. Our algorithm offers an
alternative approach to [15] that achieves the same regret, while using
operation in batches, which may in some applications be more implementation-
friendly, and also forms a foundation for the Algorithm 3 we discuss in the
next section.

Algorithm 2 $\epsilon_{0}$-LDP algorithm for stochastic linear bandits: local
model

1:Input: set of actions $\mathcal{A}$, time horizon $T$, and privacy parameter
$\epsilon_{0}$.

2:Let $\mathcal{A}_{1}$ be a $\zeta$-net for $\mathcal{A}$ as in Lemma 1, with
$\zeta=\frac{1}{T}$.

3:$q\leftarrow(2T)^{1/\log T}$.

4:for $i=1:\log(T)-1$ do

5: Client side:

6: Receive action $a$ from the server. Play action $a$ and receive a reward
$r$.

7: Send $\hat{r}=r+\mathsf{Lap}(\frac{1}{\epsilon_{0}})$.

8: Server side:

9: Let $\mathcal{C}_{i}$ be a core set for $\mathcal{A}_{i}$ as in Lemma 2
with distribution $\pi_{i}$, and $n_{ia}=\lceil{\pi_{i}(a)q^{i}}\rceil$.

10: Send each action $a\in\mathcal{C}_{i}$ to a set of $n_{ia}$ clients to get
rewards $\hat{r}_{ia}^{(1)},...,\hat{r}_{ia}^{(n_{ia})}$.

11: $n_{i}\leftarrow\sum_{a\in\mathcal{C}_{i}}n_{ia}$.

12:
$\gamma_{i}\leftarrow\sqrt{\frac{4d}{q^{i}}\log\left(4|\mathcal{A}_{i}|T^{2}\right)}+\frac{2d}{q^{i}\epsilon_{0}}\sqrt{n_{i}\log(4|\mathcal{A}_{i}|T^{2})}$.

13: $\hat{r}_{ia}\leftarrow\sum_{k=1}^{n_{j}}\hat{r}_{ia}^{(1)}\ \forall
a\in\mathcal{C}_{i}$.

14: $V\leftarrow\sum_{a\in\mathcal{C}_{i}}n_{ia}aa^{\top},\
\hat{\theta}_{i}\leftarrow V^{-1}\sum_{a\in\mathcal{C}_{i}}\hat{r}_{ia}a$.

15: $\mathcal{A}_{i+1}\leftarrow\\{a\in\mathcal{A}_{i}|\langle
a,\hat{\theta}_{i}\rangle\geq\max_{\alpha\in\mathcal{A_{i}}}\langle\alpha,\hat{\theta}_{i}\rangle-2\gamma_{i}\\}$.

16:Play action
$\arg\max_{\alpha\in\mathcal{A}_{\log(T)-1}}\langle\alpha,\hat{\theta}_{\log(T)-1}\rangle$
for the remaining time.

Algorithm Pseudocode. Algorithm 2 operates like Algorithm 1, except for the
addition of $\mathsf{Lap}(1/\epsilon_{0})$ noise for each reward individually
as opposed to adding $\mathsf{Lap}(1/\epsilon)$ to the sum of the rewards of
each arm in the central model. The value of $\gamma_{i}$ is adjusted to
account for this change. Algorithm Performance. The following Theorem 2
presents the privacy-regret tradeoffs of the LDP stochastic bandits Algorithm
2. The proof is deferred to Appendix B and follows the same main steps as the
proof of Theorem 1, but with the modified values of $\gamma_{i}$.

######  Theorem 2.

Algorithm 2 is $\epsilon_{0}$-LDP. Moreover, it achieves a regret

$R_{T}\leq C(1+\frac{1}{\epsilon_{0}})\left(d\sqrt{dT\log T}\right),$ (8)

with probability at least $1-\frac{1}{T}$, where $C$ is a constant that does
not depend on $\epsilon_{0}$ and $T$.

######  Remark 4.

Since the regret is trivially bounded by $O(T)$ when Algorithm 2 fails, which
happens with probability $\frac{1}{T}$, we can upper bound the expected regret
as

$\mathbb{E}[R_{T}]\leq C(1+\frac{1}{\epsilon_{0}})\left(d\sqrt{dT\log
T}\right).$ (9)

######  Remark 5.

When $\epsilon_{0}>1$, the regret $R_{T}$ would be
$\mathcal{O}\left(\sqrt{T}\log(T)\right)$ that matches the non-private case.
However, the constants of the regret convergence are larger than that of the
non-private case.

######  Remark 6.

(Comparison to the central $(\epsilon,\delta)$-DP model.) Observe that when
$\epsilon_{0}<1$, the dominating term in the regret bound is
$R_{T}=\mathcal{O}\left(\frac{T\log(T)}{\epsilon_{0}}\right)$. In other words,
we obtain the regret of the non-private case divided by the LDP parameter
$\epsilon_{0}$. In contrast, the central DP parameter $\epsilon$ appears as an
additive term in the regret of the central model. This difference is because,
in the local model noise is added on every reward, while in the central model
directly on the reward aggregates; thus the noise variance of the aggregate
rewards and the confidence parameter $\gamma_{i}$ increases in the local
model. In the high privacy regimes; for example, assume that
$\epsilon_{0}=\mathcal{O}\left(\frac{1}{T^{\alpha}}\right)$ for some
$0<\alpha\leq\frac{1}{2}$, we get a regret $R_{T}$ of order
$\mathcal{O}\left(T^{\frac{1}{2}+\alpha}\right)$ that becomes linear function
of $T$ as $\epsilon_{0}\to\frac{1}{\sqrt{T}}$.

##  5 Stochastic Linear Bandits in the Shuffled Model

Algorithm 3 DP algorithm for stochastic linear bandits: shuffled model

1:Input: set of actions $\mathcal{A}$, time horizon $T$, and privacy
parameters $(\epsilon,\delta)$.

2:Let $\mathcal{A}_{1}$ be a $\zeta$-net for $\mathcal{A}$ as in Lemma 1, with
$\zeta=\frac{1}{T}$.

3:$q\leftarrow(2T)^{1/\log T}$.

4:for $i=1:\log(T)-1$ do

5: Client side:

6: Receive action $a$ and the value $n_{i}$ from the shuffler.

7: Play action $a$ and receive a reward $r$.

8: $\epsilon_{0}^{(i)}\leftarrow f_{n_{i},\delta}^{-1}(\epsilon)$

9: Send $\hat{r}=r+\mathsf{Lap}(\frac{1}{\epsilon_{0}^{(i)}})$ to the
shuffler.

10: Shuffler:

11: Let $\mathcal{C}_{i}$ be a core set for $\mathcal{A}_{i}$ as in Lemma 2
with distribution $\pi_{i}$.

12: Let
$n_{ia}=\lceil{\pi_{i}(a)q^{i}}\rceil,n_{i}\leftarrow\sum_{a\in\mathcal{C}_{i}}n_{ia}$.

13: Let
$\mathcal{A}_{\mathcal{C}_{i}}=\cup_{a\in\mathcal{C}_{i}}\\{a\\}_{l=1}^{n_{ia}}$
be a set of $n_{i}$ actions where action $a\in\mathcal{C}_{i}$ is repeated
$n_{ia}$ times.

14: Let $a_{1},...,a_{n_{i}}$ be an enumeration of
$\mathcal{A}_{\mathcal{C}_{i}}$.

15: Send action $a_{\pi(j)}$ and the value $n_{i}$ to client $j,\
j=1,...,n_{i}$, where $\pi$ is a random permutation of $1,...,n_{i}$.

16: Receive the action-reward pairs
$\\{(a_{1},\hat{r}_{ia_{1}}),...,(a_{n_{i}},\hat{r}_{ia_{n_{i}}})\\}$, and
send them to the server.

17: Server side:

18: Receive the action-reward pairs from the shuffler.

19:
$\gamma_{i}\leftarrow\sqrt{\frac{4d}{q^{i}}\log\left(4|\mathcal{A}_{i}|T^{2}\right)}+\frac{2d}{q^{i}\epsilon_{0}^{(i)}}\sqrt{n_{i}\log(4|\mathcal{A}_{i}|T^{2})}$.

20: $\hat{r}_{ia}\leftarrow\sum_{k=1}^{n_{j}}\hat{r}_{ia}^{(1)}\ \forall
a\in\mathcal{C}_{i}$.

21: $V\leftarrow\sum_{a\in\mathcal{C}_{i}}n_{ia}aa^{\top},\
\hat{\theta}_{i}\leftarrow V^{-1}\sum_{a\in\mathcal{C}_{i}}\hat{r}_{ia}a$.

22: $\mathcal{A}_{i+1}\leftarrow\\{a\in\mathcal{A}_{i}|\langle
a,\hat{\theta}_{i}\rangle\geq\max_{\alpha\in\mathcal{A}}\langle\alpha,\hat{\theta}_{i}\rangle-2\gamma_{i}\\}$.

23:Play action
$\arg\max_{\alpha\in\mathcal{A}_{\log(T)-1}}\langle\alpha,\hat{\theta}_{\log(T)-1}\rangle$
for the remaining time.

In this section, we consider the case of an untrusted server and a trusted
shuffler. We propose Algorithm 3 that (almost) achieves the same order regret
as the best non-private algorithms.

Main idea. To use shuffling, we need to use an algorithm that operates over
batches of actions, so as to be able to shuffle them. The use of a core set is
critical to enable a selection of actions that lead to a good estimate for
$\theta\star$. For example, if the original set $\mathcal{A}$ contains a large
number of actions along one direction in the space, but only a few actions
along other directions, then pulling each action in $\mathcal{A}$ once will
not result in a good estimate of $\theta_{\star}$. Use of the core set and the
associated distribution $\pi$ will balance such assymetries and enable to
explore multiple directions of the space for a sufficient number of times to
acquire a good estimate of $\theta_{\star}$.

Accordingly, we follow the same approach as in Algorithm 2 with two changes:
we use a shuffler (in a manner tailored to bandits) to realize privacy
amplification gains, and we adjust the amount of Laplace noise we add in each
batch, depending on the batch size.

We use the trusted shuffler as follows. The actions to be played in the $i$th
batch are shuffled by the trusted shuffler at the beginning of the batch. The
shuffler asks clients to play actions in the shuffled order. Then, at the end
of the batch, the shuffler reverses the shuffling operation, associates every
action with its observed LDP reward, and conveys it to the untrusted
learner.222We assume that the server cannot directly observe which action is
played by which client, for instance due to geographical separation.

We adjust the amount of added Laplace noise per batch as follows. To offer
privacy guarantees, we want to add noise to the rewards so that the output of
the shuffler is $\left(\epsilon,\delta\right)$-DP for each batch
$i\in[\log(T)]$. This implies that the entire algorithm will be
$\left(\epsilon,\delta\right)$-DP, since we assume that each each client
contributes at only one of the batches. The privacy amplification of the
shuffling depends on the size of the batch (see e.g. [10, Theorem $1$]); thus
the larger the batch size, the less noise needs to be added to the rewards of
the clients. To ensure that the output of batch $i$ is
$\left(\epsilon,\delta\right)$-DP, it is suffcient to add to each reward noise
$\mathsf{Lap}(\frac{1}{\epsilon_{0}^{(i)}})$, where
$\epsilon_{0}^{(i)}\leftarrow f_{n_{i},\delta}^{-1}(\epsilon)$, and $n_{i}$ is
the size of batch $i$. The function
$f_{n,\delta}:\mathbb{R}^{+}\to\mathbb{R}^{+}$ captures privacy amplification
via shuffling [10] and is defined as follows

$f_{n,\delta}(\epsilon_{0})=\log\left(1+\frac{e^{\epsilon_{0}}-1}{e^{\epsilon_{0}}+1}\left(\frac{8\sqrt{e^{\epsilon_{0}}\log(4/\delta)}}{\sqrt{n}}+\frac{8e^{\epsilon_{0}}}{n}\right)\right).$
(10)

Since the noise added to the rewards varies for each batch $i$, we modify the
confidence bounds, $\gamma_{i}$, to reflect this. The pseudo-code is provided
in Algorithm 3.

Algorithm Performance. The following theorem proves that Algorithm 3 is
$(\epsilon,\delta)$-DP and provides an upper bound on its regret that matches
the information theoretic lower bound for
$\epsilon=\tilde{O}(\frac{1}{\sqrt{T}})$.

######  Theorem 3.

Algorithm 3 is $(\epsilon,\delta)$-differentially private. Moreover, for
$\epsilon=O(\sqrt{\frac{\log(1/\delta)}{T}})$ it achieves a regret

$R_{T}\leq C\left(\sqrt{T\log
T}+\frac{\sqrt{\log(1/\delta)}\log^{3/2}T}{\epsilon}\right),$ (11)

with probability at least $1-\frac{1}{T}$, where $C$ is a constant that does
not depend on $\epsilon$ and $T$.

Proof Outline. The proof of Theorem 3 is deferred to Appendix C. The privacy
guarantee is proved by reducing the scheme to one that shuffles the rewards
but does not shuffle the corresponding actions and using results from [10].
The regret analysis follows similar ideas as in Theorem 1 and Theorem 2.

######  Remark 7.

Note that if we had the shuffler to simply permute the collected rewards of
the clients (and not the actions) we would get no privacy gains in some cases.
For example, consider the case where all actions to be pulled in a batch are
unique and the action pulled by each client is known to the central learner
(e.g., for MAB algorithms where the policy is a deterministic function of the
history), then the learner can undo the shuffling using the action associated
with each shuffled reward.

######  Remark 8.

Algorithm 3 almost achieves the same order regret as the best non-private
algorithms. Indeed, Theorem 3 proves that Algorithm 3 achieves a regret that
matches the regret of the central DP Algorithm 1 for the high privacy regimes
$\epsilon=O(\sqrt{\log(1/\delta)/T})$. For the low privacy regime
$\epsilon>1$, the shuffling does not offer privacy gains,
$\epsilon_{0}^{(i)}\approx\epsilon$ for all $i\in[\log(T)]$ and the regret of
Algorithm 3 is similar to the regret of Algorithm 2 of the local DP model.
However, for the low privacy regime the local DP model also achieves the same
regret as non-private algorithms up to constant factors (see Remark 5). Hence
in both cases, Algorithm 3 achieves the same order regret as Algorithm 1 which
almost matches the regret of non-private algorithms.

######  Remark 9.

Algorithm’s 3 improved regret performance over Algorithm 2 is thanks to the
smaller amount of noise added to rewards. In particular, the noise added in
Step 9 of Algorithm 3 has variance
$\frac{2}{{\epsilon_{0}^{(i)}}^{2}}\approx\frac{2}{n_{i}\epsilon^{2}}$ for
small $\epsilon$.

##  6 Numerical Results

Figure 2: Regret-privacy trade-offs for stochastic linear bandits algorithms.

We here present indicative results on the performance of our proposed
Algorithms 1, 2 and 3; additional details and numerical evaluation plots are
provided in Appendix D. We consider synthetic data generated as follows. The
set of actions $\mathcal{A}$ contains $K=10$ actions, where each action
$a\in\mathcal{A}$ is a $d=2$-dimensional vector. The actions $a\in\mathcal{A}$
and the optimal parameter $\theta_{*}$ are generated uniformly at random from
the unit ball $\mathcal{S}^{d-1}=\\{x\in\mathbb{R}^{d}:||x||_{2}=1\\}$ (a
similar method is considered in [15]). Figure 2 plots the total regret $R_{T}$
over an horizon $T=10^{6}$ as a function of the privacy budget ($\epsilon$ or
$\epsilon_{0}$). Figure 2 shows that the regret achieved by all three
algorithms, Algorithm 1 (central model), Algorithm 2 (local model), and
Algorithm 3 (shuffled model) converges to the regret of non-private stochastic
linear bandit algorithms [24, Ch. $22$] as $\epsilon\to\infty$
($\epsilon_{0}\to\infty$), albeit at different rates. As predicted from the
theoretical analysis, Algorithms 1 (central) and 3 (shuffled) offer privacy
(almost) for free, closely following the non-private regret.

##  Appendix A Regret and Privacy Analysis of The Central DP Model (Proof of
Theorem 1)

###  A.1 Privacy Analysis

We first show that Algorithm 1 is $\epsilon$-DP. Let
$\bar{r}_{i}=[\bar{r}_{ia_{1}},...,\bar{r}_{ia_{|\mathcal{C}_{i}|}}],\
\hat{r}_{i}=[\hat{r}_{ia_{1}},...,\hat{r}_{ia_{|\mathcal{C}_{i}|}}]=\bar{r}_{i}+z_{i},z_{i}=[z_{ia_{1}},...,z_{ia_{|\mathcal{C}_{i}|}}]$,
where $a_{1},...,a_{|\mathcal{C}_{i}|}$ is an enumeration of the elements of
$\mathcal{C}_{i}$. We construct the concatenated reward vector denoted by
$\bar{r}=[\bar{r}_{1},...,\bar{r}_{\log(T)-1}]$, and let
$\hat{r}=[\hat{r}_{1},...,\hat{r}_{\log(T)-1}]=\bar{r}+z,z=[z_{1},...,z_{\log(T)-1}]$.

Now consider two neighboring sequence of rewards
$\mathcal{R},\mathcal{R}^{\prime}$, that only differ in
$r_{k},r^{\prime}_{k}$, with corresponding concatenated reward vectors
$\bar{r},\bar{r}^{\prime}$. We notice that each reward in $\mathcal{R}$
appears once in $\bar{r}$, and similarly for
$\mathcal{R}^{\prime},\bar{r}^{\prime}$. Thus, we get:

$\|\bar{r}-\bar{r}^{\prime}\|_{1}\leq\max_{r_{k},r^{\prime}_{k}}|r_{k}-r^{\prime}_{k}|\leq
1,$ (12)

where the last inequality follows from Assumption 1 with bounded rewards
$|r_{k}|\leq 1$. Then, from [5, Theorem $3.6$], $\hat{r}$ is $\epsilon$-DP. We
notice that the output of Algorithm 1 depends on $r_{1},...,r_{T}$ only
through $\hat{r}$. Hence, by post processing, Algorithm 1 is $\epsilon$-DP.

###  A.2 Regret Analysis

We next prove the regret bound of Algorithm 1 for stochastic linear bandits.

Our analysis follows the known confidence bound technique in [26] by designing
confidence intervals (in step 5) that take into consideration the privacy
effect.

Let $K=\left({3T}\right)^{d}$ be the size of the $\frac{1}{T}$-net set
$\mathcal{N}_{1/T}$ from Lemma 1. We first bound the following regret:

$\tilde{R}_{T}=T\max_{a\in\mathcal{N}_{1/T}}\langle
a,\theta_{*}\rangle-\sum_{t=1}^{T}\langle a_{t},\theta_{*}\rangle,$ (13)

where $a_{1},a_{2},\ldots,a_{T}\in\mathcal{N}_{1/T}$. We then bound the regret
$R_{T}$ by showing that we only loose a constant term when we choose actions
from $\mathcal{N}_{1/T}$ instead of the bigger set $\mathcal{A}$.

We start with a set of actions $\mathcal{A}_{0}=\mathcal{N}_{1/T}$ with
cardinality $|\mathcal{A}_{0}|=K$. Furthermore, we have
$|\mathcal{A}_{i}|\leq|\mathcal{A}_{i-1}|$, and hence, we get
$|\mathcal{A}_{i}|\leq K$ for all $i\in[\log(T)]$.

For given batch $i\in[\log(T)]$, let $\mathcal{C}_{i}$ be the core set of
$\mathcal{A}_{i}$ that has at most $Bd$ actions. At the $i$th batch, each
action $a\in\mathcal{C}_{i}$ is picked $n_{ia}$ times, where
$n_{ia}=\lceil\pi_{i}(a)q^{i}\rceil$. Let $\mathcal{G}$ be the good event
$\left\\{\left|\langle a,\hat{\theta}_{i}-\theta_{*}\rangle\right|<\gamma_{i}\
\forall i\in[\log T]\ \forall a\in\mathcal{A}_{i}\right\\}$. Lemma 3 shows
that the event $\mathcal{G}$ holds with probability at least $1-\frac{1}{T}$.
In the remaining part of the proof, we condition on the event $\mathcal{G}$.

We first show that the best action
$a_{*}=\arg\max_{a\in\mathcal{N}_{1/T}}\langle a,\theta_{*}\rangle$ will not
be eliminated at any batch $i\in[\log T]$; this is because the elimination
criterion will not hold for the optimal action $a_{*}$:

$\langle a,\hat{\theta}_{i}\rangle-\langle
a_{*},\hat{\theta}_{i}\rangle<(\langle
a,{\theta}_{*}\rangle+\gamma_{i})-(\langle
a_{*},{\theta}_{*}\rangle-\gamma_{i})\leq 2\gamma_{i}\qquad\forall
a\in\mathcal{A}_{i}\ \forall i\in[\log T].$ (14)

For each sub-optimal action $a\in\mathcal{A}_{0}$ with $\Delta_{a}=\langle
a_{*}-a,\theta_{*}\rangle$, let $i$ be the smallest integer for which
$\gamma_{i}<\frac{\Delta_{a}}{4}$. From the triangle inequality, we get that

$\langle a_{*},\hat{\theta_{i}}\rangle-\langle
a,\hat{\theta_{i}}\rangle\geq(\langle
a_{*},\hat{\theta_{*}}\rangle-\gamma_{i})-(\langle
a,\hat{\theta_{i}}\rangle+\gamma_{i})=\Delta_{a}-2\gamma_{i}>2\gamma_{i}.$
(15)

This implies that $a$ will be eliminated before the beginning of batch $i+1$.
Hence, each action $a\in\mathcal{A}_{i+1}$ at batch $i+1$ has a gap at most
$4\gamma_{i}$. Let $n_{i}=\sum_{a\in\mathcal{C}_{i}}n_{ia}\leq Bd+q^{i}$
denote the total number of rounds at the $i$-th batch. Note that the number of
batches is upper bounded by $\log T$ since $\sum_{i=1}^{\log T}q^{i}\geq T$.
When $q^{i}<Bd$, the regret can be bounded by $2Bd$, and when $q^{i}\geq Bd$,
we bound $n_{i}\leq 2q^{i}$. Thus, there is universal constants $C^{\prime},C$
such that the total regret in (13) can be bounded as

$\displaystyle\tilde{R}_{T}$ $\displaystyle\leq 2Bd\log(T)+\sum_{i=1}^{\log
T}4n_{i}\gamma_{i-1}$ (16) $\displaystyle\leq 2Bd\log(T)+\sum_{i=1}^{\log
T}8q^{i}\left(\sqrt{\frac{4d}{q^{i-1}}\log\left(4KT^{2}\right)}+\frac{2Bd^{2}+2d\log\left(4KT^{2}\right)}{\epsilon
q^{i-1}}\right)$ $\displaystyle\leq C^{\prime}\left(d\log(T)+d\sqrt{\log
T}\sum_{i=1}^{\log T}q^{(i-1)/2}+\frac{d^{2}\log^{2}T}{\epsilon}\right)q$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}C^{\prime}q\left(d\log(T)+d\sqrt{\log
T}q^{\log T/2}+\frac{d^{2}\log^{2}T}{\epsilon}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}C^{\prime}q\left(d\log(T)+d\sqrt{T\log
T}+\frac{d^{2}\log^{2}T}{\epsilon}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}C\left(d\sqrt{T\log
T}+\frac{d^{2}\log^{2}T}{\epsilon}\right),$ (17)

where step $(a)$ follows from the sum of a geometric series and $q>1$, step
$(b)$ uses $q=(2T)^{1/\log T}$, and step $(c)$ follows from the facts $q\leq
e^{2},\ \log T=O(\sqrt{T})$.

Hence, with probability at least $1-\frac{1}{T}$ the regret in (13) is bounded
as

$\tilde{R}_{T}\leq C\left(d\sqrt{T\log
T}+\frac{d^{2}\log^{2}T}{\epsilon}\right).$ (18)

Next, we bound the exact regret $R_{T}$. Observe that the first step in our
Algorithm is to use the finite $\frac{1}{T}$-net set $\mathcal{N}_{1/T}$ of
actions. Thus, for any round $t\in[T]$ and any action $a\in\mathcal{A}$, there
exists an action $a^{\prime}\in\mathcal{N}_{1/T}$ such that
$\|a-a^{\prime}\|\leq\frac{1}{T}$. As a result, we get $\langle
a,\theta_{*}\rangle-\langle
a^{\prime},\theta_{*}\rangle\leq\|a-a^{\prime}\|\|\theta_{*}\|\leq\frac{1}{T}$,
where $\|\theta_{*}\|\leq 1$. Hence, there is a universal constant $C$ such
that we can bound the regret $R_{T}$ as

$\displaystyle R_{T}$ $\displaystyle=T\max_{a\in\mathcal{A}}\langle
a,\theta_{*}\rangle-\sum_{t=1}^{T}\langle a_{t},\theta_{*}\rangle$ (19)
$\displaystyle=\left[T\max_{a\in\mathcal{A}}\langle
a,\theta_{*}\rangle-T\max_{a^{\prime}\in\mathcal{N}_{1/T}}\langle
a^{\prime},\theta_{*}\rangle\right]+\left[T\max_{a^{\prime}\in\mathcal{N}_{1/T}}\langle
a^{\prime},\theta_{*}\rangle-\sum_{t=1}^{T}\langle
a_{t},\theta_{*}\rangle\right]$ $\displaystyle\leq T\frac{1}{T}+\tilde{R}_{T}$
$\displaystyle=1+\tilde{R}_{T}.$

Hence, with probability at least $1-\frac{1}{T}$ the regret $R_{T}$ is bounded
as

$R_{T}\leq C\left(d\sqrt{T\log T}+\frac{d^{2}\log^{2}T}{\epsilon}\right).$
(20)

This concludes the proof of Theorem 1.

######  Lemma 3.

Let $\hat{\theta}_{i}$ be the least square estimate of $\theta_{*}$ at the end
of the $i$th batch of Algorithm 1. Then, we have that

$\Pr\left[\left|\langle
a,\hat{\theta}_{i}-\theta_{*}\rangle\right|>\gamma_{i}\ \forall i\in[\log
T]\forall a\in\mathcal{A}_{i}\right]\leq\frac{1}{T},$ (21)

where
$\gamma_{i}=\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}+\frac{2Bd^{2}+2d\log\left(4KT^{2}\right)}{\epsilon
q^{i}}$.

###### Proof.

Let $\hat{\theta}_{i}=V_{i}^{-1}\sum_{a\in\mathcal{C}_{i}}\hat{r}_{ia}a$ be
the private estimate of $\theta_{*}$ and
$\overline{\theta}_{i}=V_{i}^{-1}\sum_{a\in\mathcal{C}_{i}}\overline{r}_{ia}a$
be the non-private estimate of $\theta_{*}$ as $\\{\overline{r}_{ia}\\}$ are
the non-private rewards, where
$V_{i}=\sum_{a\in\mathcal{C}_{i}}n_{ia}aa^{\top}$. From [Chapter $21$, Eqn
$21.1$], for each $a\in\mathcal{A}_{i}$, we get:

$~{}\Pr\left[\langle
a,\overline{\theta}_{i}-\theta_{*}\rangle\geq\sqrt{2\|a\|^{2}_{V_{i}^{-1}}\log\left(\frac{1}{\beta}\right)}\right]\leq\beta,$
(22)

where $\beta\in(0,1)$ and $\|a\|^{2}_{V_{i}^{-1}}=a^{\top}V_{i}^{-1}a$. Let
$V_{i}(\pi_{i})=\sum_{a\in\mathcal{C}_{i}}\pi_{i}(a)aa^{\top}$ and hence we
have

$V_{i}=\sum_{a\in\mathcal{C}_{i}}n_{ia}aa^{\top}\geq
q^{i}\sum_{a\in\mathcal{C}_{i}}\pi_{i}(a)aa^{\top}=q^{i}V_{i}(\pi_{i}).$ (23)

Observe that for any symmetric random variable $x$ if $\Pr[x\geq t]\leq\beta$,
then $\Pr[|x|\geq t]=\Pr[x\geq t]+\Pr[-x\geq t]\leq 2\beta$. Thus, from lemma
2, we have
$\|a\|^{2}_{V_{i}^{-1}}=\frac{1}{q^{i}}a^{\top}V_{i}(\pi_{i})^{-1}a\leq\frac{2d}{q^{i}}$
for each $a\in\mathcal{A}_{i}$. By setting $\beta=\frac{1}{4KT^{2}}$ and
$\|a\|^{2}_{V_{i}^{-1}}\leq\frac{2d}{q^{i}}$ for each $a\in\mathcal{A}_{i}$ in
(22), we get that:

$\Pr\left[\left|\langle
a,\bar{\theta}_{i}-\theta_{*}\rangle\right|\geq\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}\right]\leq\frac{1}{2KT^{2}},$
(24)

for each $a\in\mathcal{A}_{i}$. Now, we compute the effect of the privacy in
estimating $\theta_{*}$ by bounding difference $\langle
a,\bar{\theta}_{i}-\hat{\theta}_{i}\rangle$. Observe that
$\hat{r}_{ia}=\bar{r}_{ia}+z_{ia}$, where
$z_{ia}\sim\mathsf{Lap}(\frac{1}{\epsilon})$, and hence, we can write
$\hat{\theta}_{i}-\bar{\theta}_{i}=V_{i}^{-1}\sum_{a\in\mathcal{C}_{i}}z_{ia}a$.
Thus, for any $\alpha\in\mathcal{A}_{i}$, we have that:

$\langle\alpha,\hat{\theta}_{i}-\bar{\theta}_{i}\rangle=\sum_{a\in\mathcal{C}_{i}}\alpha^{\top}V_{i}^{-1}az_{ia},$
(25)

where
$\alpha^{\top}V_{i}^{-1}a\leq\max_{b\in\mathcal{A}_{i}}\|b\|^{2}_{V_{i}^{-1}}\leq\frac{2d}{q^{i}}$
for each $a\in\mathcal{C}_{i}$ that holds from the fact that $V_{i}$ is
positive semi-definite. From Lemma 4 presented at the end of the section, by
setting $b=\epsilon$, $n=Bd$, $c=\frac{2d}{q^{i}}$, and
$t=2\frac{Bd^{2}}{\epsilon q^{i}}+\frac{2d\log\left(4KT^{2}\right)}{\epsilon
q^{i}}$, we get that:

$\Pr\left[\left|\langle a,\bar{\theta}_{i}-\hat{\theta}_{i}\rangle\right|\geq
2\frac{Bd^{2}}{\epsilon q^{i}}+\frac{2d\log\left(4KT^{2}\right)}{\epsilon
q^{i}}\right]\leq\frac{1}{2KT^{2}},$ (26)

Then, by the union bound and triangle inequality we have that

$\Pr\left[\left|\langle
a,\hat{\theta}_{i}-\theta_{*}\rangle\right|>\gamma_{i}\ \forall i\in[\log
T]\forall a\in\mathcal{A}_{i}\right]\leq\frac{1}{T},$ (27)

where
$\gamma_{i}=\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}+\frac{2Bd^{2}+2d\log\left(4KT^{2}\right)}{\epsilon
q^{i}}$. This concludes the proof of Lemma 3. ∎

######  Lemma 4.

Let $x_{i}=l_{i}z_{i}$ for $i\in[n]$, where $z_{i}\sim\mathsf{Lap}(1/b)$ and
$l_{i}$ is constant such that $|l_{i}|\leq c$. Let
$\bar{x}=\sum_{i=1}^{n}x_{i}$. We have that

$\displaystyle\Pr[\bar{x}\geq
t]\leq\left\\{\begin{array}[]{ll}\exp\left(-\frac{t^{2}b^{2}}{2nc^{2}}\right)&\text{if
}\ t\leq\frac{nc}{b}\\\ \exp\left(\frac{n}{2}-\frac{b}{c}t\right)&\text{if }\
t>\frac{nc}{b}\end{array}\right.$ (28)

###### Proof.

The proof follows from the concentration results of the Laplace distribution
(e.g., see ). We have that

$\displaystyle\Pr\left[\bar{x}\geq t\right]$
$\displaystyle=\Pr\left[\exp\left(\lambda\bar{x}\right)\geq e^{\lambda
t}\right]\qquad\qquad$ $\displaystyle\forall\ \lambda\geq 0$ (29)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\mathbb{E}\left[\exp\left(\lambda\bar{x}\right)\right]}{e^{\lambda
t}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{\prod_{i=1}^{n}\mathbb{E}\left[e^{\lambda
x_{i}}\right]}{e^{\lambda t}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{\prod_{i=1}^{n}e^{\lambda^{2}\frac{l_{i}^{2}}{2b^{2}}}}{e^{\lambda
t}}\qquad\qquad$ $\displaystyle\forall\ 0\leq\lambda\leq\frac{b}{c}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{e^{\lambda^{2}n\frac{c^{2}}{2b^{2}}}}{e^{\lambda
t}}\qquad\qquad$ $\displaystyle\forall\ 0\leq\lambda\leq\frac{b}{c}$

where step (a) follows from Markov’s inequality and step (b) follows from the
fact that $z_{1},\ldots,z_{n}$ are independent Laplace random variables. Step
(c) follows from the fact that $z_{i}$ is sub-exponential random variable with
proxy $\frac{l_{i}^{2}}{2b^{2}}$. Step (d) follows from the fact that
$|l_{i}|\leq c$. By choosing $\lambda=\frac{tb^{2}}{nc^{2}}$ when
$t<\frac{nc}{b}$ and $\lambda=\frac{b}{c}$ when $t>\frac{nc}{b}$, we get that

$\displaystyle\Pr\left[\bar{x}\geq
t\right]{\leq}\left\\{\begin{array}[]{ll}\exp\left(-\frac{t^{2}b^{2}}{2nc^{2}}\right)&\text{if
}\ t\leq\frac{nc}{b}\\\ \exp\left(\frac{n}{2}-\frac{b}{c}t\right)&\text{if }\
t>\frac{nc}{b}\\\ \end{array}\right.,$ (32)

This completes the proof of Lemma 4. ∎

##  Appendix B Regret and Privacy Analysis of The local DP Model (Proof of
Theorem 2)

###  B.1 Privacy Analysis

The privacy proof is straightforward. For any client, since the reward is
bounded by $|r|\leq 1$, the output $\hat{r}=r+\mathsf{Lap}(1/\epsilon_{0})$ is
$\epsilon_{0}$-LDP from [5, Theorem $3.6$].

###  B.2 Regret Analysis

We next prove the regret bound of Algorithm 2 for stochastic linear bandits
with LDP. Our proof is similar to the proofs of the central DP Algorithm
presented in Section A.2.

Let $\tilde{R}_{T}$ be the regret defined in (13). Let $\mathcal{G}$ be the
good event $\left\\{\left|\langle
a,\hat{\theta}_{i}-\theta_{*}\rangle\right|<\gamma_{i}\ \forall i\in[\log
T]\forall a\in\mathcal{A}_{i}\right\\}$. Lemma 5 shows that the event
$\mathcal{G}$ holds with probability at least $1-\frac{1}{T}$. In the
remaining part of the proof we condition on the event $\mathcal{G}$. When
$q^{i}<\max\\{Bd,2\log(4KT^{2})\\}$, the regret can be bounded by
$\max\\{Bd,2\log(4KT^{2})\\}$, and when
$q^{i}\geq\max\\{Bd,2\log(4KT^{2})\\}$, we bound $n_{i}\leq 2q^{i}$, and
hence,

$\gamma_{i}\leq\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}+\frac{2d}{\epsilon_{0}}\sqrt{\frac{\log(4KT^{2})}{q^{i}}}\leq(1+\frac{1}{\epsilon_{0}})2d\sqrt{\frac{\log(4KT^{2})}{q^{i}}}.$

By following similar steps as in the central DP, we can show that there is
universal constants $C^{\prime},C$ such that the total regret in (13) can be
bounded as

$\displaystyle\tilde{R}_{T}$
$\displaystyle\leq(Bd+2\log(4KT^{2}))\log(T)+\sum_{i=1}^{\log
T}4n_{i}\gamma_{i-1}$
$\displaystyle\leq(Bd+2\log(4KT^{2}))\log(T)+(1+\frac{1}{\epsilon_{0}})2d\sum_{i=1}^{\log
T}8q^{i}\sqrt{\frac{1}{q^{i-1}}\log\left(4KT^{2}\right)}$ $\displaystyle\leq
C^{\prime}(1+\frac{1}{\epsilon_{0}})\left(d\sqrt{d}\log^{2}(T)+d\sqrt{d\log
T}\sum_{i=1}^{\log T}q^{(i-1)/2}\right)q$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}C^{\prime}(1+\frac{1}{\epsilon_{0}})q\left(d\sqrt{d}\log^{2}(T)+d\sqrt{d\log
T}q^{\log T/2}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}C^{\prime}(1+\frac{1}{\epsilon_{0}})q\left(d\sqrt{d}\log^{2}(T)+d\sqrt{dT\log
T}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}C(1+\frac{1}{\epsilon_{0}})\left(d\sqrt{dT\log
T}\right),$ (33)

where step $(a)$ follows from the sum of a geometric series and $q>1$, step
$(b)$ uses $q=(2T)^{1/\log T}$, and step $(c)$ follows from the facts $q\leq
e^{2},\ \log^{2}T=O(\sqrt{T})$.

Hence, following similar steps as in the proof of the central DP algorithm,
with probability at least $1-\frac{1}{T}$ the regret is bounded as

$R_{T}\leq\tilde{R}_{T}+1\leq C(1+\frac{1}{\epsilon_{0}})\left(d\sqrt{dT\log
T}\right).$ (34)

######  Lemma 5.

Let $\hat{\theta}_{i}$ be the least square estimate of $\theta_{*}$ at the end
of the $i$th batch of Algorithm 2. Then, we have that

$\Pr\left[\left|\langle
a,\hat{\theta}_{i}-\theta_{*}\rangle\right|>\gamma_{i}\ \forall i\in[\log
T]\forall a\in\mathcal{A}_{i}\right]\leq\frac{1}{T},$ (35)

where
$\gamma_{i}=\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}+\frac{2d}{q^{i}\epsilon_{0}}\sqrt{n_{i}\log(4KT^{2})}$.

###### Proof.

Let $\hat{\theta}_{i}=V_{i}^{-1}\sum_{a\in\mathcal{C}_{i}}\hat{r}_{ia}a$ be
the private estimate of $\theta_{*}$ and
$\overline{\theta}_{i}=V_{i}^{-1}\sum_{a\in\mathcal{C}_{i}}\overline{r}_{ia}a$
be the non-private estimate of $\theta_{*}$ as $\\{\overline{r}_{ia}\\}$ are
the non-private rewards, where
$V_{i}=\sum_{a\in\mathcal{C}_{i}}n_{ia}aa^{\top}$ and
$\hat{r}_{ia}=\sum_{j=1}^{n_{ia}}\hat{r}_{ia}^{(j)}$. Similar to the central
DP in Section 3, we have that

$\Pr\left[\left|\langle
a,\bar{\theta}_{i}-\theta_{*}\rangle\right|\geq\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}\right]\leq\frac{1}{2KT^{2}},$
(36)

for each $a\in\mathcal{A}_{i}$. Now, we compute the effect of the LDP in
estimating $\theta_{*}$ by bounding difference $\langle
a,\bar{\theta}_{i}-\hat{\theta}_{i}\rangle$. Observe that
$\hat{r}_{ia}=\sum_{j=1}^{n_{ia}}\hat{r}_{ia}^{(j)}=\bar{r}_{ia}+z_{ia}$,
where $\bar{r}_{ia}=\sum_{j=1}^{n_{ia}}r_{ia}^{(j)}$ and
$z_{ia}=\sum_{j=1}^{n_{ia}}z_{ia}^{(j)}$, where
$z_{ia}^{(j)}\sim\mathsf{Lap}(\frac{1}{\epsilon_{0}})$. Hence, we can write
$\hat{\theta}_{i}-\bar{\theta}_{i}=V_{i}^{-1}\sum_{a\in\mathcal{C}_{i}}z_{ia}a$.
Thus, for any $\alpha\in\mathcal{A}_{i}$, we have that:

$\langle\alpha,\hat{\theta}_{i}-\bar{\theta}_{i}\rangle=\sum_{a\in\mathcal{C}_{i}}\sum_{j=1}^{n_{ia}}\alpha^{\top}V_{i}^{-1}az_{ia}^{(j)},$
(37)

where
$\alpha^{\top}V_{i}^{-1}a\leq\max_{b\in\mathcal{A}_{i}}\|b\|^{2}_{V_{i}^{-1}}\leq\frac{2d}{q^{i}}$
for each $a\in\mathcal{C}_{i}$ that holds from the fact that $V_{i}$ is
positive semi-definite. From Lemma 4 presented in Section 3, by setting
$b=\epsilon_{0}$, $n=n_{i}$, $c=\frac{2d}{q^{i}}$, and
$t=\frac{2d}{q^{i}\epsilon_{0}}\sqrt{n_{i}\log(4KT^{2})}$, we get that:

$\Pr\left[\left|\langle
a,\bar{\theta}_{i}-\hat{\theta}_{i}\rangle\right|\geq\frac{2d}{q^{i}\epsilon_{0}}\sqrt{n_{i}\log(4KT^{2})}\right]\leq\frac{1}{2KT^{2}},$
(38)

Then, by the union bound and triangle inequality we have that

$\Pr\left[\left|\langle
a,\hat{\theta}_{i}-\theta_{*}\rangle\right|>\gamma_{i}\ \forall i\in[\log
T]\forall a\in\mathcal{A}_{i}\right]\leq\frac{1}{T},$ (39)

where
$\gamma_{i}=\sqrt{\frac{4d}{q^{i}}\log\left(4KT^{2}\right)}+\frac{2d}{q^{i}\epsilon_{0}}\sqrt{n_{i}\log(4KT^{2})}$.
This concludes the proof of Lemma 5. ∎

##  Appendix C Regret and Privacy Analysis of The Shuffled Model (Proof of
Theorem 3)

###  C.1 Privacy Analysis

We note that the data of each user $j$ can be represented as
$\cup_{a\in\mathcal{C}_{i}}\\{(a,r^{(j)}_{a})\\}$. We observe that our scheme
is equivalent to performing the following steps

  * •

Each user $j\in[n_{i}]$ sends its data
$\mathcal{D}_{j}=\cup_{a\in\mathcal{C}_{i}}\\{(a,r^{(j)}_{a})\\}$ to the
shuffler.

  * •

The shuffler randomly permutes the sets
$\mathcal{D}_{1},...,\mathcal{D}_{n_{i}}$ to get
$\mathcal{D}_{\pi(1)},...,\mathcal{D}_{\pi(n_{i})}$.

  * •

The shuffler reveals $n_{i}$ action reward pairs
$(a_{1},\hat{r}_{ia_{1}}),...,(a_{n_{i}},\hat{r}_{ia_{n_{i}}})$, where
$(a_{j},\hat{r}_{ia_{j}})\in\mathcal{D}_{\pi(j)}$, and $\hat{r}_{ia_{j}}$ is
the LDP version of ${r}_{ia_{j}}$
($\hat{r}_{ia_{j}}={r}_{ia_{j}}+\mathsf{Lap}(\frac{1}{\epsilon_{0}^{(i)}})$).

Hence, we shuffle the data, then feed it to an LDP mechanism with LDP
parameter $\epsilon_{0}^{(i)}$ (as proved in Theorem 2). As a result, it
follows from [10] that the output of the shuffler is
$(\epsilon_{i},\delta)$-DP where

$\epsilon_{i}=\log\left(1+\frac{e^{\epsilon_{0}^{(i)}}-1}{e^{\epsilon_{0}^{(i)}}+1}\left(\frac{8\sqrt{e^{\epsilon_{0}^{(i)}}\log(4/\delta)}}{\sqrt{n_{i}}}+\frac{8e^{\epsilon_{0}^{(i)}}}{n_{i}}\right)\right).$
(40)

By the choice of $\epsilon_{0}^{(i)}$ as an inverse of the function
$f_{n_{i},\delta}$, we have that $\epsilon_{i}=\epsilon$ for all $i\in[\log
T]$.

We observe that for any neighboring datasets $D,D^{\prime}$, there is only one
user data that is different between $D,D^{\prime}$. That user appears in
exactly one batch. It follows that Algorithm 3 is $(\epsilon,\delta)$-DP.

###  C.2 Regret Analysis

We next prove the regret bound of Algorithm 3 for stochastic linear bandits in
the shuffled model. Our proof is similar to the proofs of the LDP Algorithm
presented in Section B.2.

Let $\tilde{R}_{T}$ be the regret defined in (13). Let $\mathcal{G}$ be the
good event $\left\\{\left|\langle
a,\hat{\theta}_{i}-\theta_{*}\rangle\right|<\gamma_{i}\ \forall i\in[\log
T]\forall a\in\mathcal{A}_{i}\right\\}$. Lemma 5 shows that the event
$\mathcal{G}$ holds with probability at least $1-\frac{1}{T}$. In the
remaining part of the proof we condition on the event $\mathcal{G}$. When
$q^{i}<Bd$, the regret can be bounded by $Bd$. By following similar steps as
in the central DP, we can show that there is universal constants $C^{\prime}$
such that the total regret in (13) can be bounded as

$\displaystyle\tilde{R}_{T}$ $\displaystyle\leq Bd\log(T)+\sum_{i=1}^{\log
T}4n_{i}\gamma_{i-1}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}Bd\log(T)+\sum_{i=1}^{\log
T}8q^{i}\sqrt{\frac{4d}{q^{i-1}}\log\left(4KT^{2}\right)}+C^{\prime}\frac{2d}{\epsilon}\sum_{i=1}^{\log
T}8q\sqrt{\log\left(4KT^{2}\right)\log(1/\delta)}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}C\left(d\sqrt{T\log
T}+\frac{(d\log T)^{3/2}\sqrt{\log(1/\delta)}}{\epsilon}\right),$ (41)

where step $(a)$ follows from the fact that from the privacy analysis, when
$\epsilon_{0}^{(i)}\leq 1$, we get that
$\epsilon=O(\epsilon_{0}^{(i)}\sqrt{\frac{\log(1/\delta)}{n_{i}}})$.

Hence, following similar steps as in the proof of the central DP algorithm,
with probability at least $1-\frac{1}{T}$ the regret is bounded as

$R_{T}\leq\tilde{R}_{T}+1\leq C\left(d\sqrt{T\log T}+\frac{(d\log
T)^{3/2}\sqrt{\log(1/\delta)}}{\epsilon}\right).$ (42)

##  Appendix D Additional Numerical Results

(a) Central, local and shuffled models, $K=10,T=10^{6}$.

(b) Effect of core set size, $K=1000,T=10^{7}$.

Figure 3: Regret-privacy trade-offs for stochastic linear bandits algorithms.

Data Generation. We generate synthetic data generated as follows. The set of
actions $\mathcal{A}$ contains $K$ actions, where each action
$a\in\mathcal{A}$ is a $d=2$-dimensional vector. The actions $a\in\mathcal{A}$
and the optimal parameter $\theta_{*}$ are generated uniformly at random from
the unit sphere $\mathcal{S}^{d-1}=\\{x\in\mathbb{R}^{d}:||x||_{2}=1\\}$.
Figure 4 plots the total regret $R_{T}$ over an horizon $T=10^{6}$ as a
function of the privacy budget ($\epsilon$ or $\epsilon_{0}$ in case of LDP
mechanisms). Figure 3 plots the total regret $R_{T}$ over an horizon $T$ as a
function of the privacy budget ($\epsilon$ or $\epsilon_{0}$ in case of LDP
mechanisms).

Usefulness of Core Set. In Figure 3(b), we explore potential benefits on the
performance of Algorithm 1 that use of the core set can offer. We consider
$K=1000$ and $T=10^{7}$, and plot the regret of Algorithm 1 for two cases: (i)
when we use a core set of size $2$-$3$ actions, similar to the dimension of
our space (labeled as Alg. 1), and (ii) when no core set is used, and instead
the good set of actions of the batched algorithm is the whole action set
(labeled as Alg. 1 no-core-set). We find that, as expected from our
theoretical analysis, using a core set enables to achieve performance very
close to that of a non-private batched algorithm that adds no noise. In
contrast, using (and adding noise to) the entire action space significantly
degrades the performance.

Figure 4: Regret-privacy trade-offs for stochastic linear bandits algorithms
with $T=10^{6}$.

We here present indicative results on the performance of our proposed
Algorithms 1, 2 and 3.

Comparison of Algorithms 1, 2 and 3. In Figure 3(a), we compare the regret of
the proposed algorithms in the central, local and shuffled models using
$K=10,T=10^{6}$. We observe that all algorithms converge to the regret of non-
private stochastic linear bandit algorithms [24] as $\epsilon\to\infty$
($\epsilon_{0}\to\infty$), albeit at different rates. As predicted from the
theoretical analysis, Algorithms 1 (central) and 3 (shuffled) offer privacy
(almost) for free, closely following the non-private regret.

## References

  * [1] J. Mary, R. Gaudel, and P. Preux, “Bandits and recommender systems,” in _International Workshop on Machine Learning, Optimization and Big Data_. Springer, 2015, pp. 325–336.
  * [2] D. Bouneffouf, I. Rish, and G. A. Cecchi, “Bandit models of human behavior: Reward processing in mental disorders,” in _International Conference on Artificial General Intelligence_. Springer, 2017, pp. 237–248.
  * [3] A. N. Rafferty, H. Ying, and J. J. Williams, “Bandit assignment for educational experiments: Benefits to students versus statistical power,” in _International Conference on Artificial Intelligence in Education_. Springer, 2018, pp. 286–290.
  * [4] D. Bouneffouf and I. Rish, “A survey on practical applications of multi-armed and contextual bandits,” _arXiv preprint arXiv:1904.10040_ , 2019.
  * [5] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of Cryptography Conference (TCC)_ , 2006, pp. 265–284.
  * [6] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Foundations and Trends® in Theoretical Computer Science_ , vol. 9, no. 3–4, pp. 211–407, 2014.
  * [7] A. Cheu, A. D. Smith, J. Ullman, D. Zeber, and M. Zhilyaev, “Distributed differential privacy via shuffling,” in _Advances in Cryptology - EUROCRYPT 2019_ , vol. 11476. Springer, 2019, pp. 375–403.
  * [8] Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta, “Amplification by shuffling: From local to central differential privacy via anonymity,” in _SODA_. SIAM, 2019, pp. 2468–2479.
  * [9] B. Balle, J. Bell, A. Gascón, and K. Nissim, “The privacy blanket of the shuffle model,” in _Annual International Cryptology Conference_. Springer, 2019, pp. 638–667.
  * [10] V. Feldman, A. McMillan, and K. Talwar, “Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling,” in _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_. IEEE, 2022, pp. 954–964.
  * [11] A. M. Girgis, D. Data, S. Diggavi, A. T. Suresh, and P. Kairouz, “On the renyi differential privacy of the shuffle model,” in _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , 2021, pp. 2321–2341.
  * [12] P. Rusmevichientong and J. N. Tsitsiklis, “Linearly parameterized bandits,” _Mathematics of Operations Research_ , vol. 35, no. 2, pp. 395–411, 2010\.
  * [13] R. Shariff and O. Sheffet, “Differentially private contextual linear bandits,” vol. 31, 2018.
  * [14] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” _Advances in neural information processing systems_ , vol. 24, 2011.
  * [15] Y. Han, Z. Liang, Y. Wang, and J. Zhang, “Generalized linear bandits with local differential privacy,” vol. 34, 2021.
  * [16] E. Garcelon, K. Chaudhuri, V. Perchet, and M. Pirotta, “Privacy amplification via shuffling for linear contextual bandits,” in _International Conference on Algorithmic Learning Theory_. PMLR, 2022, pp. 381–407.
  * [17] S. R. Chowdhury and X. Zhou, “Shuffle private linear contextual bandits,” _arXiv preprint arXiv:2202.05567_ , 2022.
  * [18] T. Sajed and O. Sheffet, “An optimal private stochastic-mab algorithm based on optimal private stopping rule,” in _International Conference on Machine Learning_. PMLR, 2019, pp. 5579–5588.
  * [19] W. Ren, X. Zhou, J. Liu, and N. B. Shroff, “Multi-armed bandits with local differential privacy,” _arXiv preprint arXiv:2007.03121_ , 2020.
  * [20] J. Tenenbaum, H. Kaplan, Y. Mansour, and U. Stemmer, “Differentially private multi-armed bandits in the shuffle model,” _Advances in Neural Information Processing Systems_ , vol. 34, 2021.
  * [21] K. Zheng, T. Cai, W. Huang, Z. Li, and L. Wang, “Locally differentially private (contextual) bandits learning,” vol. 33, 2020, pp. 12 300–12 310.
  * [22] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” _SIAM Journal on Computing_ , vol. 40, no. 3, pp. 793–826, 2011.
  * [23] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge university press, 2018, vol. 47.
  * [24] T. Lattimore and C. Szepesvári, _Bandit algorithms_. Cambridge University Press, 2020.
  * [25] M. Frank and P. Wolfe, “An algorithm for quadratic programming,” _Naval research logistics quarterly_ , vol. 3, no. 1-2, pp. 95–110, 1956.
  * [26] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire, “Gambling in a rigged casino: The adversarial multi-armed bandit problem,” in _Proceedings of IEEE 36th annual foundations of computer science_. IEEE, 1995, pp. 322–331.