# Shuffle Private Linear Contextual Bandits

Sayak Ray Chowdhury 111Boston University, Massachusetts, USA. Email:
<EMAIL_ADDRESS>Xingyu Zhou11footnotemark: 1 222Wayne State University, Detroit,
USA. Email<EMAIL_ADDRESS>Equal contributions

###### Abstract

Differential privacy (DP) has been recently introduced to linear contextual
bandits to formally address the privacy concerns in its associated
personalized services to participating users (e.g., recommendations). Prior
work largely focus on two trust models of DP – the central model, where a
central server is responsible for protecting users’ sensitive data, and the
(stronger) local model, where information needs to be protected directly on
users’ side. However, there remains a fundamental gap in the utility achieved
by learning algorithms under these two privacy models, e.g.,
$\widetilde{O}(\sqrt{T})$ regret in the central model as compared to
$\widetilde{O}(T^{3/4})$ regret in the local model, if all users are _unique_
within a learning horizon $T$. In this work, we aim to achieve a stronger
model of trust than the central model, while suffering a smaller regret than
the local model by considering recently popular _shuffle_ model of privacy. We
propose a general algorithmic framework for linear contextual bandits under
the shuffle trust model, where there exists a trusted shuffler – in between
users and the central server– that randomly permutes a batch of users data
before sending those to the server. We then instantiate this framework with
two specific shuffle protocols – one relying on privacy amplification of local
mechanisms, and another incorporating a protocol for summing vectors and
matrices of bounded norms. We prove that both these instantiations lead to
regret guarantees that significantly improve on that of the local model, and
can potentially be of the order $\widetilde{O}(T^{3/5})$ if all users are
unique. We also verify this regret behavior with simulations on synthetic
data. Finally, under the practical scenario of non-unique users, we show that
the regret of our shuffle private algorithm scale as $\widetilde{O}(T^{2/3})$,
which _matches_ that the central model could achieve in this case.

##  1 Introduction

In the linear contextual bandit problem [Aue03, CLRS11], a learning agent
observes the context information $c_{t}$ of an user at every round $t$. The
goal is to recommend an action $a_{t}$ to the user so that the resulting
reward $y_{t}$ is maximized. The mean reward is given by a linear function of
an _unknown_ parameter vector $\theta^{*}\in\mathbb{R}^{d}$, $d\in\mathbb{N}$,
i.e.,

$\displaystyle\mathbb{E}\left[{y_{t}\mid
c_{t},a_{t}}\right]=\langle\theta^{*},\phi(c_{t},a_{t})\rangle~{},$

where $\phi:\mathcal{C}\times\mathcal{X}\to\mathbb{R}^{d}$ maps a context-
action pair to a $d$-dimensional feature vector, and
$\langle\cdot,\cdot\rangle$ denotes the standard Euclidean inner product. The
context and action sets $\mathcal{C}$ and $\mathcal{X}$ are arbitrary, and can
also possibly be varying with time. An agent’s performance over $T$ rounds is
typically measured through the cumulative pseudo-regret

$\displaystyle\operatorname{Reg}(T)=\sum\nolimits_{t=1}^{T}\left[\max_{a\in\mathcal{X}}\langle\theta^{*},\phi(c_{t},a)\rangle-\langle\theta^{*},\phi(c_{t},a_{t})\rangle\right],$

which is the total loss suffered due to not recommending the actions
generating highest possible rewards corresponding to observed contexts. This
framework has found applications in many real-life settings such as internet
advertisement selection [ABL03], article recommendation in web portals
[LCLS10], mobile health [TM17], to name a few. The general applicability of
this framework has motivated a line of work [SS18, ZCH+20] studying linear
contextual bandit problems under the additional constraint of _differential
privacy_ [Dwo08], which guarantees that the users’ contexts and generated
rewards will not be inferred by an adversary during this learning process.

To illustrate the privacy concern in the contextual bandit problem, let us
consider a mobile medical application in which an mobile app recommends a
tailored treatment plan (i.e., action) to each patient (i.e., user) based on
her personal information such as age, weight, height, medical history etc.
(i.e., context). Meanwhile, this mobile app’s recommendation algorithm also
needs to be updated once in a while in a cloud server after collecting data
from a batch of patients, including treatment outcomes (i.e., rewards) and
contexts, which are often considered to be private and sensitive information.
Hence, each patient would like to obtain a personalized and effective
treatment plan while guaranteeing their sensitive information remains
protected against a potential adversarial attack in this interactive process.
Protection of privacy is typically achieved by injecting sufficient noise in
users’ data [AYN14, XJ14], which results in a loss in utility (i.e., an
increase in regret) of the recommended action. Hence, the key question is how
to balance utility and privacy carefully.

This has motivated studies of linear contextual bandits under different trust
models of differential privacy (i.e., who the user will trust with her
sensitive data). On one end of the spectrum lies the _central_ model, which
guarantees privacy to users who trust the learning agent to store their raw
data in the server and use those to update its strategy of recommending
actions. Under this trust model, [SS18] has shown that the cumulative regret
is $\widetilde{O}(\frac{\sqrt{T}(\log(1/\delta))^{1/4}}{\sqrt{\varepsilon}})$,
where $\varepsilon$ and $\delta$ are privacy parameters with smaller values
denoting higher level of protection. Perhaps unsurprisingly, this regret bound
– due to the high degree of trust – matches the optimal $\Theta(\sqrt{T})$
scaling for non-private linear contextual bandits [CLRS11]. However, this
relatively high trust model is not always feasible since the users may not
trust the agent at all. This is captured by the _local_ model, where any data
sent by the users must already be private, and the agent can only store those
randomized data in the server. This is a strictly stronger notion of privacy,
and hence, often comes at a price. Under this trust model, [ZCH+20] has shown
that the cumulative regret is
$\widetilde{O}(\frac{T^{3/4}(\log(1/\delta))^{1/4}}{\sqrt{\varepsilon}})$,
which, as expected, is much worse than that in the central model. This
naturally leads to the following question:

_Can a finer trade-off between privacy and regret in linear contextual bandits
be achieved?_

Furthermore, in both [SS18] and [ZCH+20], the learning agents update their
strategy at every round. This not only puts excessive computational burden on
the server (due to $T$ updates each taking at least $O(d^{2})$ time and
memory) but also could be be practically infeasible at times. For example,
consider the above mobile health application. The cloud server is often
infeasible to update the algorithm deployed in mobile app after interactions
with each single user. Rather, a more practical strategy is to update the
algorithm after collecting a batch of users’ data (e.g., a one-month period of
data).

Motivated by these, we consider the linear contextual bandit problem under an
intermediate trust model of differential privacy, known as the _shuffle_ model
[CSU+19, EFM+19] in the hope to attain a finer regret-privacy trade-off, while
only using batch updates. In this new trust model, there exists a shuffler
between users and the central server which permutes a _batch_ of users’
randomized data before they are viewed by the server so that it can’t
distinguish between two users’ data. Shuffling thus adds an another layer of
protection by decoupling data from the users that sent them. Here, as in the
local model, the users don’t trust the server. However, it is assumed that
they have a certain degree of trust in the shuffler since it can be
efficiently implemented using cryptographic primitives (e.g., mixnets) due to
its simple operation [BEM+17, App17]. The shuffle model provides the
possibility to achieve a stronger privacy guarantee than the central model
while suffering a smaller utility loss than the local model. The key intuition
behind this is that the additional randomness of the shuffler creates a
_privacy blanket_ [BBGN19b] so that each user now needs much less random noise
to hide her information in the crowd. Indeed, the shuffle model achieves a
better trade-off between utility and privacy as compared to central and local
model in several learning problems such as empirical risk minimization
[GDD+21], stochastic convex optimization [LR21, CJMP21], and standard multi-
arm bandits [TKMS21]. However, little is known about (linear) contextual
bandits in the shuffle model due to its intrinsic challenges. That is, in
addition to rewards, the contexts are also sensitive information that need to
be protected, which not only results in the aforementioned large gap in regret
between local and central model333In contrast, for MAB, the problem-
independent upper bounds in the local and central model are both
$\widetilde{O}(\sqrt{T})$ [RZLS20]., but also leads to new challenges in the
shuffle model. Against this backdrop, we make the following contributions:

  * •

We design a general algorithmic framework (Algorithm 1) for private linear
contextual bandits in the shuffle model. It decomposes the learning process
into three black-box components: a local randomizer at each user, an analyzer
at the central server and a shuffler in-between. We instantiate the framework
with two specific shuffle protocols. The first one directly builds on privacy
amplification of existing local mechanisms. The other one utilizes an
efficient mechanism for summing vectors with bounded $\ell_{2}$ norms.

  * •

We show that both shuffle protocols provide stronger privacy protection
compared to the central model. Furthermore, when all users are _unique_ , we
prove a regret bound of $\widetilde{O}\left(T^{3/5}\right)$ for both the
protocols, which improves over the $\widetilde{O}\left(T^{3/4}\right)$ regret
of local model. Hence, we achieve a finer trade-off between regret and
privacy. We further perform simulations on synthetic data that corroborate our
theoretical results.

  * •

As a practical application of our general framework, we show that under the
setting of non-unique or _returning_ users, the regret of both our shuffle
protocols _matches_ the one that the central model would achieve in the same
setting. This, along with the fact that both shuffle protocols also offer a
certain degree of local privacy, further elaborate usefulness of shuffle model
in private linear contextual bandits.

Related work. Due to the utility gap present between central and local models,
a significant body of recent work have focused on the shuffle model [BBGN19b,
FMT20, GGK+19, BBGN19a]. A nice overview of recent work in the shuffle model
is presented in [Che21]. Regret performance of multi-armed bandit algorithms
under central and local trust models have been considered in [MT15, SS19,
RZLS20, CZZ+20, ZT20, Dub21, TD17], whereas online learning algorithms under
full information have appeared in [GTS13, AS17]. Recently, the two models have
also been adopted to design differentially private control and reinforcement
learning algorithms [VBKW20, GPPBP20, CZS21, CZ21]. [HLWZ21] consider linear
bandits with stochastic contexts, and show that
$\widetilde{O}(\sqrt{T}/\varepsilon)$ regret can be achieved even in the local
model. In contrast, in this work, we allow the contexts to be arbitrary and
can even be adversarially generated, which pose additional challenges.

Batched linear bandits are studied in [HZZ+20, RZK20], where the authors show
that only $O(\sqrt{T})$ model update is sufficient to achieve corresponding
minimax optimal regrets. In the shuffle private model, batched learning not
only reduces the model update frequency, but more importantly plays a key role
in amplifying privacy via shuffling a batch of users’ data. Interestingly, as
a by-product, our established generic regret bound also improves over the non-
private one in [RZK20] in the sense that no restriction is required for the
regularizer.

Concurrent and independent work. While preparing this submission, we have
noticed that [GCPP21] also study linear contextual bandits in the shuffle
model. The authors claim that a single fixed batch schedule is not sufficient
to obtain a better regret-privacy trade-off in shuffle model. They propose to
use separate asynchronous schedules – a fixed batch scheme for the shuffler
and an adaptive model update scheme for the server. In contrast, thanks to a
tighter analysis, we show that _a single fixed batch schedule_ is indeed
sufficient to attain the same regret-privacy trade-off in shuffle model.
Moreover, we believe, there exists a fundamental gap in their analysis for the
adaptive model update, which might make their results ungrounded. We provide a
detailed discussion on this in Section 6, which highlights the key difference
in dealing with adaptive update in the non-private and the private settings.
Finally, in addition to the above differences in theoretical results, our
established generic framework enables to design flexible shuffle private
protocols for linear contextual bandits that are able to handle a wide range
of practically interested privacy budget $\varepsilon$ rather than a
restricted small value $\varepsilon\ll 1$ in the concurrent work [GCPP21].

##  2 Privacy in the Shuffle Model

In this section, we introduce the shuffle model, and its corresponding privacy
notion called the _shuffle differential privacy_. Before that, we recall
definitions of differential privacy under central and local models [DR+14a].

###  2.1 Central and Local Differential Privacy

Throughout, we let $\mathcal{D}$ denote the data universe, and
$n\in\mathbb{N}$ the number of (unique) users. Let
$D_{i}\in\mathcal{D},i=1,2,\ldots,n$, denote the data point of user $i$, and
$D_{-i}\in\mathcal{D}^{n-1}$ denote collection of data points of all but the
$i$-th user. Let $\varepsilon>0$ and $\delta\in(0,1]$ be given privacy
parameters.

######  Definition 2.1 (Differential Privacy (DP)).

A mechanism $\mathcal{M}$ satisfies $(\varepsilon,\delta)$-DP if for each user
$i\in[n]$, each data set $D,D^{\prime}\in\mathcal{D}^{n}$, and each event
$\mathcal{E}$ in the range of $\mathcal{M}$,

$\displaystyle\mathbb{P}\left[{\mathcal{M}(D_{i},D_{-i})\in\mathcal{E}}\right]\leqslant\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}(D^{\prime}_{i},D_{-i})\in\mathcal{E}}\right]+\delta.$

######  Definition 2.2 (Local Differential Privacy (LDP)).

A mechanism $\mathcal{M}$ satisfies $(\varepsilon,\delta)$-LDP if for each
user $i\in[n]$, each data point $D_{i},D^{\prime}_{i}\in\mathcal{D}$ and each
event $\mathcal{E}$ in the range of $\mathcal{M}$,

$\displaystyle\mathbb{P}\left[{\mathcal{M}(D_{i})\in\mathcal{E}}\right]\leqslant\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}(D^{\prime}_{i})\in\mathcal{E}}\right]+\delta.$

Roughly speaking, a central DP (or, simply, DP) mechanism ensures that the
outputs of the mechanism on two neighbouring data sets (i.e., those differ
only on one user) are approximately indistinguishable. In contrast, local DP
ensures that the output of the local mechanism for each user is
indistinguishable.

###  2.2 Shuffle Differential Privacy

A (standard) shuffle protocol
$\mathcal{P}=(\mathcal{R},\mathcal{S},\mathcal{A})$ consists of three parts:
(i) a (local) randomizer $\mathcal{R}$, (ii) a shuffler $\mathcal{S}$ and
(iii) an analyzer $\mathcal{A}$. For $n$ users, the overall protocol works as
follows. Each user $i$ first applies the randomizer on its raw data $D_{i}$
and then sends the resulting messages $\mathcal{R}(D_{i})$ to the shuffler.
The shuffler $\mathcal{S}$ permutes messages from all the users uniformly at
random and then reports the permuted messages
$\mathcal{S}(\mathcal{R}(D_{1}),\ldots,\mathcal{R}(D_{n}))$ to the analyzer.
Finally, the analyzer $\mathcal{A}$ computes the output using received
messages. In this protocol, the users trust the shuffler but not the analyzer.
Hence, the privacy objective is to ensure that the outputs of the shuffler on
two neighbouring datasets are indistinguishable in the analyzer’s view. To
this end, define the mechanism
$(\mathcal{S}\circ\mathcal{R}^{n})(D)\\!:=\\!\mathcal{S}(\mathcal{R}(D_{1}),\ldots,\mathcal{R}(D_{n}))$,
where $D\in\mathcal{D}^{n}$.

######  Definition 2.3 (Shuffle differential privacy (SDP)).

A protocol $\mathcal{P}=(\mathcal{R},\mathcal{S},\mathcal{A})$ for $n$ users
satisfies $(\varepsilon,\delta)$-SDP if the mechanism
$\mathcal{S}\circ\mathcal{R}^{n}$ satisfies $(\varepsilon,\delta)$-DP.

To achieve benefits of the shuffle model in intrinsically adaptive algorithms
(e.g., gradient descent, multi-armed bandits etc.), one needs to divide the
users into multiple batches, and run a potentially different shuffle protocol
on each batch [CJMP21, TKMS21]. This is quite natural since the shuffler needs
enough users’ data to infuse sufficient randomness so as to amplify the
privacy. Moreover, each protocol might depend on the output of the preceding
protocols to foster adaptivity. Formally, a general $M$-batch,
$M\in\mathbb{N}$, shuffle protocol $\mathcal{P}$ for $n$ users works as
follows. In each batch $m$, we simply run a standard single-batch shuffle
protocol for a subset of $n_{m}$ users (such that $n=\sum_{m}n_{m}$) with
randomizer $\mathcal{R}_{m}$, shuffler $\mathcal{S}$ and analyzer
$\mathcal{A}$. To ensure adaptivity, the randomizer $\mathcal{R}_{m}$ and
number of users $n_{m}$ for the $m$-th batch could be chosen depending on
outputs of the shuffler from all the previous batches, given by
$\left\\{\mathcal{S}\left(\mathcal{R}_{m^{\prime}}(D_{1}),\ldots,\mathcal{R}_{m^{\prime}}(D_{n_{m^{\prime}}})\right)\right\\}_{m^{\prime}<m}$.
The objective of privacy is same as in the single-batch protocol – the
analyzer’s view must satisfy DP. However, instead of a single-batch output,
one need to protect outputs of all the $M$ batches. To this end, define the
(composite) mechanism $\mathcal{M}_{\mathcal{P}}=(\mathcal{S}\circ
R_{1}^{n_{1}},\ldots,\mathcal{S}\circ\mathcal{R}_{m}^{n_{m}})$, where each
individual mechanism $\mathcal{S}\circ\mathcal{R}_{m}^{n_{m}}$ operates on
$n_{m}$ users’ data, i.e., on datasets from $\mathcal{D}^{n_{m}}$.

######  Definition 2.4 ($M$-batch SDP).

An $M$-batch shuffle protocol $\mathcal{P}$ is $(\varepsilon,\delta)$-SDP if
the mechanism $\mathcal{M}_{\mathcal{P}}$ is $(\varepsilon,\delta)$-DP.

Algorithm 1 Shuffle Private LinUCB

1: Parameters: Batch size $B\in\mathbb{N}$, regularization $\lambda\\!>\\!0$,
confidence radii $\\{\beta_{m}\\}_{m\geqslant 0}$, feature map
$\phi:\mathcal{C}\\!\times\\!\mathcal{X}\\!\to\\!\mathbb{R}^{d}$

2: Initialize: Batch counter $m\\!=\\!1$, end-time $t_{0}\\!=\\!0$, batch
statistics ${V}_{0}\\!=\\!\lambda I_{d}$, ${u}_{0}\\!=\\!0$, parameter
estimate $\widehat{\theta}_{0}\\!=\\!0$

3: for local user $t\\!=\\!1,2,\dots$ do

4: Observe user’s context information $c_{t}\in\mathcal{C}$

5: Choose action
$a_{t}\in\mathop{\mathrm{argmax}}_{a\in\mathcal{X}}\langle\phi(c_{t},a),\widehat{\theta}_{m-1}\rangle+\beta_{m-1}\left\lVert\phi(c_{t},a)\right\rVert_{{V}_{m-1}^{-1}}$

6: Observe reward $y_{t}$

7: # For the local randomizer:

8: Send randomized messages $M_{t,1}=R_{1}(\phi(c_{t},a_{t})y_{t})$ and
$M_{t,2}=R_{2}(\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top})$ to the shuffler

9: if $t=mB$ then

10: # For the shuffler:

11: Set batch end-time: $t_{m}=t$

12: Permute all received messages uniformly at random
$Y_{m,1}=S_{1}\left(\\{M_{\tau,1}\\}_{t_{m-1}+1\leq\tau\leq t_{m}}\right)$ and
$Y_{m,2}=S_{2}\left(\\{M_{\tau,2}\\}_{t_{m-1}+1\leq\tau\leq t_{m}}\right)$

13: # For the analyzer (server):

14: Compute per-batch statistics $\widetilde{u}_{m}=A_{2}(Y_{m,1})$ and
$\widetilde{V}_{m}=A_{1}(Y_{m,2})$ using shuffled messages

15: Update overall batch statistics: $u_{m}=u_{m-1}+\widetilde{u}_{m}$,
$V_{m}=V_{m-1}+\widetilde{V}_{m}$

16: Compute parameter estimate $\widehat{\theta}_{m}=V_{m}^{-1}u_{m}$

17: Send updated models $(\widehat{\theta}_{m},V_{m})$ to users

18: Increase batch counter: $m=m+1$

19: end if

20: end for

##  3 A Shuffle Algorithm for Contextual Bandits

In this section, we introduce a general algorithmic framework (Algorithm 1)
for linear contextual bandits under the shuffle model. We build on the
celebrated LinUCB algorithm [CLRS11, AYPS11], which is an application of the
_optimism in the face of uncertainty_ principle to linear bandits. Throughout
the paper, we make the following assumptions, which are standard in the
literature [CLRS11, SS18].

######  Assumption 3.1 (Boundedness).

The rewards are bounded for all $t$, i.e., $y_{t}\in[0,1]$. Moreover, the
parameter vector and the features have bounded norm, i.e.,
$\left\lVert\theta^{*}\right\rVert_{2}\leqslant 1$ and
$\sup_{c,a}\left\lVert\phi(c,a)\right\rVert_{2}\leqslant 1$.444All terms are
assumed to be bounded by one via normalization.

###  3.1 Algorithm: Shuffle Private LinUCB

Our shuffle algorithm for contextual bandits consist of batches with a fixed
size $B$, i.e., we have total $M=T/B$ batches.555We assume, wlog, total number
of rounds $T$ is multiple of $B$. The central idea is to construct, for each
batch $m$, a $d$-dimensional ellipsoid $\mathcal{E}_{m}$ with centre
$\widehat{\theta}_{m}$, shape matrix $V_{m}$ and radius $\beta_{m}$ so that it
contains the unknown parameter $\theta^{*}$ with high probability. Moreover,
the ellipsoids are designed while keeping the privacy setting in mind. They
depend on the randomizer, shuffler and analyzer employed in the shuffle
protocol based on required privacy levels $\varepsilon,\delta$. The personal
data of user $t$ in batch $m$ is given by the feature vector
$\phi(c_{t},a_{t})$ and reward $y_{t}$, where the action $a_{t}$ is selected
given the context $c_{t}$ as

$\displaystyle
a_{t}\\!\in\\!\mathop{\mathrm{argmax}}_{a\in\mathcal{X}}\\{\\!\langle\phi(c_{t},a),\widehat{\theta}_{m\\!-\\!1}\rangle\\!+\\!\beta_{m\\!-\\!1}\\!\left\lVert\phi(c_{t},a)\right\rVert_{{V}_{m\\!-\\!1}^{-1}}\\!\\}.$

We consider a fixed randomizer across all the batches given by two functions
$R_{1}$ and $R_{2}$ that locally operate on the vectors
$\phi(c_{t},a_{t})y_{t}$ and matrices
$\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$, respectively. Similarly, we have
shuffler functions $S_{1}$ and $S_{2}$ operating on batches (of size $B$) of
those respective randomized messages. Finally, the analyzer functions $A_{1}$
and $A_{2}$ receive permuted messages from $S_{1}$ and $S_{2}$, and output,
for each batch $m^{\prime}$, an aggregate vector $\widetilde{u}_{m^{\prime}}$
and matrix $\widetilde{V}_{m^{\prime}}$, respectively. The central server uses
this aggregate batch statistics to construct the ellipsoid: $V_{m}=\lambda
I_{d}+\sum_{m^{\prime}=1}^{m}\widetilde{V}_{m^{\prime}}$ and
$\widehat{\theta}_{m}=V_{m}^{-1}\sum_{m^{\prime}=1}^{M}\widetilde{u}_{m^{\prime}}$.
For a given confidence level $\alpha\in(0,1]$, the radius of the ellipsoid is
set as
$\beta_{m}=O\left(\sqrt{2\log\left(\frac{2}{\alpha}\right)+d\log\left(1+\frac{t_{m}}{d\lambda}\right)}+\sqrt{\lambda}\right)$,
where $t_{m}$ is the time when batch $m$ ends. The regularizer $\lambda$ and
thus, in turn, the confidence radius $\beta_{m}$ typically depend on the total
noise infused in the shuffle protocol. On a high level, these randomizer,
shuffler and analyzer functions together provide suitable random perturbations
to the Gram matrices and feature-reward vectors based on the privacy budget
$\varepsilon,\delta$, and in turn, they affect the regret performance via the
noise levels of these perturbations. Next, we turn to discuss specific choices
of these functions, and the associated performance guarantees of Algorithm 1
under those choices.

###  3.2 Achieving SDP via LDP Amplification

In this section, we show that our general framework (Algorithm 1) enables us
to directly utilize existing LDP mechanisms for linear contextual bandits to
achieve a finer utility-privacy trade-off. The key idea here is to leverage
the explicit privacy amplification property of the shuffle protocol [FMT20].
Roughly, the privacy guarantee can be amplified by a factor of $\sqrt{B}$ by
randomly permuting the output of an LDP mechanism independently operating on a
batch of $B$ different users. In other words, the same level of privacy can be
achieved for each user by adding a $\sqrt{B}$ factor _less_ noise in the
presence of shuffler, yielding a better utility. Specifically, we instantiate
Algorithm 1 with the shuffle protocol
$\mathcal{P}_{\text{Amp}}\\!=\\!(\mathcal{R}_{\text{Amp}},\mathcal{S}_{\text{Amp}},\mathcal{A}_{\text{Amp}})$,
where we employ standard Gaussian mechanism [DR+14b] as randomizer functions.
Essentially, we inject independent Gaussian perturbation to each entry of the
vector $\phi(c_{t},a_{t})y_{t}$ and the matrix
$\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$ with variances $\sigma_{1}^{2}$
and $\sigma_{2}^{2}$, respectively. We make sure the noisy matrix is symmetric
by perturbing upper diagonal entries, and copying those to the lower terms.
The noise variances are properly tuned depending on the sensitivity of these
elements to achieve desired level of privacy. In this case, the shuffler
functions simply permute its data uniformly at random, and the job of the
analyzer is to simply add its received data (i.e., vectors or matrices). We
defer further details on the protocol $\mathcal{P}_{\text{Amp}}$ to Appendix B
and focus on performance guarantees first.

######  Theorem 3.2 (Performance under LDP amplification).

Fix time horizon $T\\!\in\\!\mathbb{N}$, batch size $B\\!\in\\![T]$,
confidence level $\alpha\\!\in\\!(0,1]$, privacy budgets
$\delta\\!\in\\!(0,1]$,
$\varepsilon\\!\in\\!(0,\sqrt{\frac{\log(2/\delta)}{B}}]$. Then, Algorithm 1
instantiated using shuffle protocol $\mathcal{P}_{\text{Amp}}$ with noise
$\sigma_{1}\\!=\\!\sigma_{2}\\!=\\!\frac{4\sqrt{2\log(2.5B/\delta)\log(2/\delta)}}{\varepsilon\sqrt{B}}$,
and regularizer
$\lambda\\!=\\!\Theta(\sqrt{T}\sigma_{1}(\sqrt{d}\\!+\\!\sqrt{\log(T/B\alpha)})$,
enjoys the regret

$\displaystyle\text{Reg}(T)\\!=\\!O\\!\\!\left(\\!\\!dB\log
T\\!+\\!\frac{\log^{1/2}(B/\delta)}{\varepsilon^{1/2}B^{1/4}}d^{3/4}T^{3/4}\log^{2}\\!(T\\!/\alpha)\\!\\!\right)\\!,$

with probability at least $1-\alpha$. Moreover, it satisfies
$O(\varepsilon,\delta)$-shuffle differential privacy (SDP).

######  Corollary 3.3.

Setting batch size $B=O(T^{3/5})$ in Algorithm 1, we can achieve regret
$\widetilde{O}\left(\frac{T^{3/5}}{\sqrt{\varepsilon}}\log^{1/2}(T/\delta)\right)$.666Note
that with a careful choice of $B$ (depending on privacy parameters
$\varepsilon,\delta$), we can have a better regret dependence on
$\varepsilon,\delta$. See Corollary B.2 for details.

#### Comparsion with central and local DP models.

At this point, we turn to compare the regret of our Shuffle Private LinUCB
algorithm to that of LinUCB under central model with JDP guarantee777JDP, or,
joint differential privacy, is a notion of privacy under central trust model
specific to contextual bandits. See Appendix D. [SS18] and local model with
LDP [ZCH+20] guarantee. As mentioned before, LinUCB achieves
$\tilde{O}\left(\sqrt{\frac{T}{\varepsilon}}\right)$ and
$\tilde{O}\left(\frac{T^{3/4}}{\sqrt{\varepsilon}}\right)$ regret under JDP
and LDP guarantees, respectively. As seen in Corollary 3.3, our regret bound
in the shuffle trust model lies perfectly in between these two extremes.
Importantly, it improves over the $T^{3/4}$ scaling in the (stronger) local
trust model, achieving a better trade-off between regret and privacy. However,
it couldn’t achieve the optimal $\sqrt{T}$ scaling in the (weaker) central
trust model. It remains an open question whether $\sqrt{T}$ regret can be
achieved under any notion of privacy stronger than the central model.

######  Remark 3.4.

Our shuffle protocol $\mathcal{P}_{\text{Amp}}$, by design, provides a certain
level of local privacy to each user. Specifically, for batch size $B$,
Algorithm 1 is $O(\varepsilon\sqrt{B/\log(2/\delta)},\delta/B)$-LDP.
Furthermore, since shuffe model ensures a higher level of trust than the
central model, Algorithm 1 is also $O(\varepsilon,\delta)$-JDP. See Appendix B
for details.

Apart from achieving a refined utility-privacy trade-off, the above shuffle
protocol $\mathcal{P}_{\text{Amp}}$ requires minimum modifications over
existing LDP mechanisms. However, the privacy guarantee in Theorem 3.2 holds
only for small privacy budget $\varepsilon$ particularly when the batch size
$B$ is large, which could potentially limit its application in some practical
scenarios (e.g., when $\varepsilon$ is around $1$ or larger [App17]).
Moreover, $\mathcal{P}_{\text{Amp}}$ needs to communicate and shuffle _real_
vectors and matrices, which are often difficult to encode on finite computers
in practice [CKS20, KLS21] and a naive use of finite precision approximation
may lead to a possible failure of privacy protection [Mir12]. To overcome
these limitations of $\mathcal{P}_{\text{Amp}}$, we introduce a different
instantiation of Algorithm 1 in the next section.

###  3.3 Achieving SDP via Vector Summation

We instantiate Algorithm 1 with the shuffle protocol
$\mathcal{P}_{\text{Vec}}\\!=\\!(\mathcal{R}_{\text{Vec}},\mathcal{S}_{\text{Vec}},\mathcal{A}_{\text{Vec}})$,
where we rely on a particularly efficient and accurate mechanism for summing
vectors with bounded $\ell_{2}$ norms [CJMP21]. First, the local randomizer
$\mathcal{R}_{\text{Vec}}$ adopts a one-dimensional randomizer that operates
independently on each entry of the vector $\phi(c_{t},a_{t})y_{t}$ and the
matrix $\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$, respectively. This adopted
one-dimensional randomizer transmits only bits ($0/1$) via a fixed-point
encoding scheme [CSU+19], and ensures privacy by injecting binomial noise. In
particular, given any entry $x\\!\in\\![0,1]$, it is first encoded as
$\widehat{x}\\!=\\!\bar{x}\\!+\\!\gamma_{1}$, using an accuracy parameter
$g\\!\in\\!\mathbb{N}$, where $\bar{x}\\!=\\!\lfloor{xg}\rfloor$ and
$\gamma_{1}\\!\sim\\!\texttt{Ber}(xg-\bar{x})$. Then a binomial noise is
generated, $\gamma_{2}\\!\sim\\!\texttt{Bin}(b,p)$, where parameters
$b\\!\in\\!\mathbb{N},p\\!\in\\!(0,1)$ control the privacy noise. The output
of the one-dimensional randomizer is simply a collection of total $g+b$ bits,
in which $\widehat{x}\\!+\\!\gamma_{2}$ bits are $1$ and the rest are $0$.
Combining the outputs of the one-dimensional randomizer for each entry of
vector $\phi(c_{t},a_{t})y_{t}$ and matrix
$\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$, yield final outputs of
randomizer. The shuffler functions in $\mathcal{S}_{\text{Vec}}$ simply
permutes all the received bits uniformly at random. The job of the analyzer
$\mathcal{A}_{\text{Vec}}$ is to add the received bits for each entry, and
remove the bias introduced due to encoding and binomial noise. This is
possible since bits are already labeled entry-wise when leaving
$\mathcal{R}_{\text{Vec}}$. The constants $g,b,p$ are left as tunable
parameters of $\mathcal{P}_{\text{Vec}}$, and need to be set properly
depending on the desired level of privacy. The detailed implementation of this
scheme is deferred to Appendix C. The following theorem states the performance
guarantees of Algorithm 1 instantiated with $\mathcal{P}_{\text{Vec}}$.

######  Theorem 3.5 (Performance under vector sum).

Fix batch size $B\\!\in\\![T]$, privacy budgets $\varepsilon\\!\in\\!(0,15]$,
$\delta\\!\in\\!(0,1/2)$. Then, Algorithm 1 instantiated with
$\mathcal{P}_{\text{Vec}}$ with parameters $p\\!=\\!1/4$,
$g\\!=\\!\max\\{2\sqrt{B},d,4\\}$ and $b\\!=\\!\frac{C\cdot
g^{2}\cdot\log^{2}\left(d^{2}/\delta\right)}{\varepsilon^{2}B}$ is
$(\varepsilon,\delta)$-SDP, where $C>>1$ is some sufficiently large constant.
Furthermore, for any $\alpha\\!\in\\!(0,1]$, setting
$\lambda\\!=\\!\Theta\\!\left(\\!\frac{\log(d^{2}/\delta)\sqrt{T}}{\varepsilon\sqrt{B}}(\\!\sqrt{d}\\!+\\!\sqrt{\log(T/B\alpha)}\\!\right)$,
it enjoys the regret

$\displaystyle\text{Reg}(T)\\!=\\!O\\!\left(\\!\\!dB\log
T\\!+\\!\frac{\log^{1/2}(d^{2}/\delta)}{\varepsilon^{1/2}B^{1/4}}d^{3/4}T^{3/4}\log^{2}\\!(T\\!/\alpha)\\!\\!\right)\\!,$

with probability at least $1-\alpha$.

######  Remark 3.6.

Similar to Corollary 3.3, an
$\widetilde{O}\left(\frac{T^{3/5}}{\sqrt{\varepsilon}}\right)$ regret can also
be achieved in this case by setting $B\\!=\\!O(T^{3/5})$, but the dependence
on $\delta$ is now: $\log^{1/2}(d^{2}/\delta)$ as compared to
$\log^{1/2}(T/\delta)$. Moreover, in contrast to Theorem 3.2, the guarantees
hold for a wide range of $\varepsilon$, making $\mathcal{P}_{\text{Vec}}$
better suitable for practical purposes [App17]. Finally, as before, if $B$
also depends on privacy parameters, the dependence on $\varepsilon,\delta$ can
be improved, see Corollary C.2.

######  Remark 3.7.

$\mathcal{P}_{\text{Vec}}$ can also be regarded as privacy amplification of
Binomial mechanism (rather than Gaussian mechanism in
$\mathcal{P}_{\text{Amp}}$), which is the reason that it also offers a certain
degree, $O(\varepsilon\sqrt{B},\delta)$, to be precise, of LDP guarantee.

######  Remark 3.8.

Both shuffle protocols, $\mathcal{P}_{\text{Amp}}$ and
$\mathcal{P}_{\text{Vec}}$, in fact, can be tuned to satisfy
$(\varepsilon,\delta)$-LDP by sacrificing on regret performance. See
Corollaries B.3 and C.3 for details.

###  3.4 Key Techniques: Overview

In this section, we provide a generic template of regret bound for linear
contextual bandits under the shuffle model of privacy. To this end, we need
following notations to discuss the effect of noise added by shuffle protocol,
in the learning process. Let
$n_{m}\\!=\\!\widetilde{u}_{m}\\!-\\!\sum_{t=t_{m-1}+1}^{t_{m}}\phi(c_{t},a_{t})y_{t}$
and
$N_{m}\\!=\\!\widetilde{V}_{m}\\!-\\!\sum_{t=t_{m-1}+1}^{t_{m}}\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$
denote the total noise added during batch $m$ in the feature-reward vector,
and in the Gram-matrix, respectively. Furthermore, assume that there exist
constants $\widetilde{\sigma}_{1}$ and $\widetilde{\sigma}_{2}$ such that for
each batch $m$, (i) $\sum_{m^{\prime}=1}^{m}n_{m^{\prime}}$ is a random vector
whose entries are independent, mean zero, sub-Gaussian with variance at most
$\widetilde{\sigma}_{1}^{2}$, and (ii) $\sum_{m^{\prime}=1}^{m}N_{m^{\prime}}$
is a random symmetric sub-Gaussian matrix whose entries on and above the
diagonal are independent with variance at most $\widetilde{\sigma}_{2}^{2}$.
Let
$\sigma^{2}\\!=\\!\max\\{\widetilde{\sigma}_{1}^{2},\widetilde{\sigma}_{2}^{2}\\}$.
Then, we have the following result.

######  Lemma 3.9 (Informal).

With the choice of $\lambda\approx\sigma(\sqrt{d}+\sqrt{\log(T/(B\alpha))})$,
the regret of Algorithm 1 satisfies

$\displaystyle\text{Reg}(T)\\!=\\!\widetilde{O}\\!\left(\\!{dB}\\!+\\!d\sqrt{T}\\!+\\!\sqrt{\sigma
T}d^{3/4}\\!\right)\,\text{with high probability.}$

With the above result, one only needs to determine the noise variance
$\sigma^{2}$ under different privacy protocols. We illustrate this with the
shuffle protocols introduced in previous sections. First, note that since we
assume unique users, Algorithm 1 is SDP if each batch is SDP. Now, for the LDP
amplification protocol $\mathcal{P}_{\text{Amp}}$, in order to guarantee SDP
for each batch with sufficiently small privacy loss $\varepsilon$, it suffices
to work with an LDP mechanism with loss $\varepsilon\sqrt{B}$ by virtue of
amplification.888We provide intuition without worrying about the details
related to $\delta$-dependent terms. Refer to Appendix A for formal proofs. We
ensure this by choosing Gaussian mechanism with noise variance
$O(1/(\varepsilon^{2}B))$. Hence, the total noise variance added by
$\mathcal{P}_{\text{Amp}}$ is $\sigma^{2}\approx
O(\frac{T}{\varepsilon^{2}B})$. Thus, by Lemma 3.9, we obtain the result in
Theorem 3.2. Similarly, for the vector sum protocol
$\mathcal{P}_{\text{Vec}}$, we ensure $\mathcal{P}_{\text{Vec}}$ to be SDP by
properly setting parameters $g,b,p$. Moreover, the analyzer’s outputs are
unbiased estimates of the sum of the non-private vectors (matrices) within
that batch, and the entry-wise private noise is sub-Gaussian with variance of
$O(\frac{1}{\varepsilon^{2}})$. Thus, the total noise variance added by
$\mathcal{P}_{\text{Vec}}$ is $\sigma^{2}\approx
O(\frac{T}{\varepsilon^{2}B})$, and hence, by Lemma 3.9, we have the result in
Theorem 3.5.

######  Remark 3.10.

Lemma 3.9, in fact, can serve as a general template of regret for private
linear contextual bandit algorithms. For example, for the local model
[ZCH+20], $B\\!=\\!1$ and $\sigma^{2}\\!\approx\\!\frac{T}{\varepsilon^{2}}$,
yielding $\widetilde{O}\left(\frac{T^{3/4}}{\sqrt{\varepsilon}}\right)$
regret. Similarly, for the central model [SS18], $B\\!=\\!1$ and
$\sigma^{2}\\!\approx\\!\frac{\log T}{\varepsilon^{2}}$, which yields
$\widetilde{O}\left(\frac{T^{1/2}}{\sqrt{\varepsilon}}\right)$ regret.

##  4 Regret Performance under Returning Users

Similar to existing work on differentially private bandits, in previous
sections, we have assumed that all participating users are unique, i.e., each
user participates in the protocol only at one round. A more practical scenario
is that an user can contribute with her data at multiple rounds. For example,
consider the mobile medical application described in the introduction. The
cloud server can collect one particular user’s data during multiple batches to
track the effectiveness of its treatment plan over a period, and hence, use
same user’s data multiple times to update its recommendation algorithm.
Motivated by this, we provide privacy and regret guarantees of Algorithm 1
under the setting of _returning users_ in linear contextual bandits. We first
define the setting of returning users that we consider in this section, and
then state the performance guarantee for Algorithm 1.

######  Assumption 4.1 (Returning Users).

For a given time horizon $T\in\mathbb{N}$ and batch size $B\in[T]$, any user
can participate in _all_ $M=T/B$ batches, but within each batch $m\in[M]$, she
only contributes once.

In addition to the above motivating example, this assumption also captures
many practical adaptive learning scenarios such as clinical trials and product
recommendations, in which each trial (batch) involves a group of unique
people, but the same person may participate in multiple trials [RZK20, SBF17].

######  Theorem 4.2 (Performance guarantees (informal)).

Under Assumption 4.1, we obtain the following results for
$\mathcal{P}_{\text{Amp}}$ and $\mathcal{P}_{\text{Vec}}$, respectively.

(i) For any $\varepsilon\\!\leqslant\\!\frac{2}{B}\log(2/\delta)\sqrt{2T}$ and
$\delta\\!\in\\!(0,1]$, Algorithm 1 instantiated using
$\mathcal{P}_{\text{Amp}}$ with noise levels
$\sigma_{1}\\!=\\!\sigma_{2}\\!=\\!\frac{16\log(2/\delta)\sqrt{T(\log(5T/\delta))}}{\varepsilon{B}}$
is $O(\varepsilon,\delta)$-SDP, and enjoys, with high-probability, the regret
bound

$\displaystyle\text{Reg}(T)=\widetilde{O}\left(\frac{dT}{M}+\sqrt{\frac{MT}{\varepsilon}}d^{3/4}\log^{3/4}(T/\delta)\right).$

(ii) For any $\varepsilon\\!\leqslant\\!15$, $\delta\\!\in\\!(0,1/2)$, there
exist choices of parameters $g,b\\!\in\\!\mathbb{N}$, $p\\!\in\\!(0,1/2)$
depending on $B,\varepsilon,\delta$ such that Algorithm 1 instantiated using
$\mathcal{P}_{\text{Vec}}$ is $(\varepsilon,\delta)$-SDP, and, enjoys, with
high probability, the regret bound

$\displaystyle\text{Reg}(T)\\!=\\!\widetilde{O}\left(\frac{dT}{M}\\!+\\!\sqrt{\frac{MT}{\varepsilon}}d^{3/4}\log^{3/4}(d^{2}M/\delta)\right).$

###### Proof sketch.

In contrast to Section 3 for unique users, where $(\varepsilon,\delta)$-SDP
guarantee for Algorithm 1 can be established by showing each batch is
$(\varepsilon,\delta)$-SDP, we now need to guarantee that outputs of all the
batches together have a total privacy loss of $(\varepsilon,\delta)$. This is
due to the fact that now each batch can potentially operate on same set of
users, and hence, one need to use advanced decomposition to calculate the
total privacy loss. This leads to scaling up the noise variance by a
multiplicative factor of $O(M)$ at each batch, which eventually leads to the
above bound (the additional $M$ factor in $\delta$ also comes from advance
composition). ∎

Interestingly, the privacy ($\varepsilon,\delta$)-dependent term in above
regret bounds match the one that can be achieved in the _user-level_ central
trust model that handles returning users. Note that, since existing work in
the central model of privacy (i.e., under JDP guarantee) assume unique users
[SS18], we first generalize it to handle returning users. This can be viewed
as the same form of generalization from _event-level_ DP to _user-level_ DP
under continual observation, where the adjacent relation between two data
streams changes from the flip of one single round to the flip of multiple
rounds associated with a single user [DNPR10].999See Appendix D for formal
definitions of event-level and user-level joint differential privacy (JDP). As
in standard notion of DP, one straightforward approach for converting event-
level JDP to user-level JDP is to use group privacy [DR+14b]. However, this
black-box approach would blow up the terms dependent on $\delta$. To overcome
this, we propose a simple modification of original (event-level) algorithm in
[SS18] so that it can handle returning users. In particular, user-level JDP
can be achieved by scaling up the noise variance by a multiplicative factor of
$M_{0}^{2}$, if any user participates in at most $M_{0}$ rounds. This follows
from the fact that flipping one user now would change the $\ell_{2}$
sensitivity of the expanded binary-tree nodes from $O(\sqrt{\log T})$ to
$O(M_{0}\sqrt{\log T})$. Note that we use $M_{0}$ to distinguish from the
number of batches $M$ since there is no batch concept in standard central
model. This modified version enjoys the following regret guarantee.

######  Proposition 4.3.

If any user participates in at most $M_{0}$ rounds, the algorithm in [SS18],
with the above modification to handle user-level privacy, achieves the high-
probability regret bound

$\displaystyle\text{Reg}(T)=\widetilde{O}\left(d\sqrt{T}+\sqrt{\frac{M_{0}T}{\varepsilon}}d^{3/4}\log^{1/4}(1/\delta)\right).$

######  Remark 4.4.

Comparing Theorem 4.2 and Proposition 4.3, we observe that the cost of privacy
in the shuffle model is essentially same (upto a log factor) as in the central
model under the setting of returning users. In particular, if
$M=M_{0}=T^{1/3}$ rounds (i.e., the same number of possible returning rounds
for any user), the regret is
$\widetilde{O}\left(\frac{T^{2/3}}{\sqrt{\varepsilon}}\right)$ in both shuffle
and user-level central trust models. See Appendix E for complete proofs and
more details.

##  5 Simulation Results

(a) $\varepsilon=0.2$

(b) $\varepsilon=1$

(c) $\varepsilon=10$

Figure 1: Comparison of cumulative regret for LinUCB (non-private), LinUCB-JDP
(central model), LinUCB-SDP (shuffle model) and LinUCB-LDP (local model) with
varying privacy level $\varepsilon=0.2$ (a), $\varepsilon=1$ (b) and
$\varepsilon=10$ (c). For $\varepsilon=0.2$ (higher privacy level), gap
between private and non-private regret is higher as compared to
$\varepsilon=10$ (lower privacy level). In all cases, regret of LinUCB-SDP
lies perfectly in between LinUCB-JDP and LinUCB-LDP, achieving finer regret-
privacy trade-off.

In this section, we empirically evaluate the regret performance of Algorithm 1
(under shuffle model), which we abbreviate as LinUCB-SDP-Amp and LinUCB-SDP-
Vec when instantiated with $\mathcal{P}_{\text{Amp}}$ and
$\mathcal{P}_{\text{Vec}}$, respectively. We compare them with the algorithms
of [SS18] and [ZCH+20] under central and local models, which we call LinUCB-
JDP and LinUCB-LDP, respectively. We benchmark these against the non-private
algorithm of [AYPS11], henceforth referred as LinUCB. For all the experiments,
we consider $100$ arms, set $T=20000$ rounds, and average our results over 50
randomly generated bandit instances. Each instance is characterized by an
(unknown) parameter $\theta^{*}$ and feature vectors of dimension $d=5$. To
ensure boundedness, similar to [VMDK20], we generate each $\theta^{*}$ and
feature vectors by sampling a $(d\\!-\\!1)$-dimensional vectors of norm
$1/\sqrt{2}$ uniformly at random, and append it with a $1/\sqrt{2}$ entry. We
consider Bernoulli $\\{0,1\\}$ rewards. We fix $\delta\\!=\\!0.1$ and plot the
results for varying privacy level $\varepsilon\in\\{0.2,1,10\\}$ in Figure 1.
We use Batchsize $B=20$ for LinUCB-SDP. We postpone the results for $d=10,15$
to Appendix G.

From Figure 1, we observe that the regret performance of LinUCB-SDP (under
both shuffle protocols $\mathcal{P}_{\text{Amp}}$ and
$\mathcal{P}_{\text{Vec}}$) is indeed better than LinUCB-LDP. In addition, it
is not surprising that LinUCB-SDP incurs a larger regret than LinUCB-JDP.
Moreover, the regret performance of LinUCB-SDP (in fact for any private
algorithm) comes closer to that of LinUCB as $\varepsilon$ increases, i.e, as
the privacy guarantee becomes weaker. The experimental findings are consistent
with our theoretical results.

##  6 Concluding Remarks

We conclude by discussing some important theoretical and practical aspects
about shuffle protocols, and in general, about privacy in linear contextual
bandits.

Communications. In the protocol $\mathcal{P}_{\text{Amp}}$, each participating
user at each round need to send one $d$-dimensional real vector and one
$d\times d$ real matrix. On the other hand, the protocol
$\mathcal{P}_{\text{Vec}}$ only communicates $0/1$ bits. In particular, each
participating user at each round sends out a total of $O(d^{2}(g+b))$ bits,
where $g+b\approx\sqrt{B}+\log(1/\delta)/\varepsilon^{2}$. Hence,
$\mathcal{P}_{\text{Vec}}$ might be more feasible in practice than
$\mathcal{P}_{\text{Amp}}$.

Batched algorithms for local and central models. Existing work on
differentially private linear contextual bandits under both local and central
models perform sequential update, i.e., the model estimates are updated after
each round. As mentioned before, this may not be feasible in practice due to
computational load. Fortunately, our proposed algorithm (Algorithm 1) along
with its generic regret bound (Lemma 3.9) also offers a simple way to design
and analyze private algorithms for local and central models with batched
update. In particular, we show that it suffices to update after every
$B=\widetilde{O}(T^{3/4})$ rounds to achieve the same privacy-regret trade-off
as in the sequential local model and every $B=\widetilde{O}(\sqrt{T})$ to
match the sequential central model. See Appendix F for the details.

Adaptive model update. One might wonder whether we can further reduce the
update frequency to $O(\log T)$ via an adaptive model update schedule based on
the standard determinant trick (Lemma 12 of [AYPS11]). In this approach, the
key step is to establish that
$\left\lVert\phi(c,a)\right\rVert_{V_{\tau_{t}}^{-1}}\\!\leqslant\\!\eta\left\lVert\phi(c,a)\right\rVert_{V_{t}^{-1}}$,
where $\tau_{t}\\!<\\!t$ is the most recent model update time before $t$. To
this end, if one uses the determinant trick, one can obtain that

$\displaystyle\left\lVert\phi(c,a)\right\rVert_{V_{\tau_{t}}^{-1}}\leqslant\sqrt{\frac{\det(V_{t})}{\det(V_{\tau_{t}})}}\left\lVert\phi(c,a)\right\rVert_{V_{t}^{-1}},$

_if the condition $V_{t}\succeq V_{\tau_{t}}$ holds_. Note that this is true
in the non-private setting. However, this does not necessarily hold in private
settings due to the added noise, which, to the best of our knowledge, is the
key analytical gap in the current proof of the main result (Theorem 10) in
[GCPP21]. As we can see, this issue exists in all three trust models when one
needs to use the _noisy_ design matrix to determine the update frequency via
the determinant trick.

Future work. One immediate future research direction is to address the above
adaptive model update in the private settings. We also believe our framework
can be generalized to design shuffle private algorithms for reinforcement
learning with linear function approximation (e.g., linear mixture Markov
decision processes (MDPs)) to achieve finer trade-off compared to the local
model [LHG21] and the central model [Zho22].

## References

  * [ABL03] Naoki Abe, Alan W Biermann, and Philip M Long.  Reinforcement learning with immediate rewards and linear hypotheses.  Algorithmica, 37(4):263–293, 2003.
  * [App17] Apple.  Learning with privacy at scale.  2017\.
  * [AS17] Naman Agarwal and Karan Singh.  The price of differential privacy for online learning.  In International Conference on Machine Learning, pages 32–40. PMLR, 2017.
  * [Aue03] Peter Auer.  Using confidence bounds for exploitation-exploration trade-offs.  Journal of Machine Learning Research, 3:397–422, March 2003.
  * [AYN14] Shifali Arora, Jennifer Yttri, and Wendy Nilsen.  Privacy and security in mobile health (mhealth) research.  Alcohol research: current reviews, 36(1):143, 2014.
  * [AYPS11] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In Advances in Neural Information Processing Systems, pages 2312–2320, 2011.
  * [BBGN19a] Borja Balle, James Bell, Adria Gascon, and Kobbi Nissim.  Differentially private summation with multi-message shuffling.  arXiv preprint arXiv:1906.09116, 2019.
  * [BBGN19b] Borja Balle, James Bell, Adria Gascón, and Kobbi Nissim.  The privacy blanket of the shuffle model.  In Annual International Cryptology Conference, pages 638–667. Springer, 2019.
  * [BEM+17] Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld.  Prochlo: Strong privacy for analytics in the crowd.  In Proceedings of the 26th Symposium on Operating Systems Principles, pages 441–459, 2017.
  * [Che21] Albert Cheu.  Differential privacy in the shuffle model: A survey of separations.  arXiv preprint arXiv:2107.11839, 2021.
  * [CJMP21] Albert Cheu, Matthew Joseph, Jieming Mao, and Binghui Peng.  Shuffle private stochastic convex optimization.  2021\.
  * [CKS20] Clément L Canonne, Gautam Kamath, and Thomas Steinke.  The discrete gaussian for differential privacy.  In NeurIPS, 2020.
  * [CLRS11] W. Chu, L. Li, L. Reyzin, and R. E. Schapire.  Contextual bandits with linear payoff functions.  In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 15, pages 208–214, 2011.
  * [CSS10] TH Hubert Chan, Elaine Shi, and Dawn Song.  Private and continual release of statistics.  In International Colloquium on Automata, Languages, and Programming, pages 405–417. Springer, 2010.
  * [CSU+19] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev.  Distributed differential privacy via shuffling.  In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 375–403. Springer, 2019.
  * [CZ21] Sayak Ray Chowdhury and Xingyu Zhou.  Differentially private regret minimization in episodic markov decision processes.  arXiv preprint arXiv:2112.10599, 2021.
  * [CZS21] Sayak Ray Chowdhury, Xingyu Zhou, and Ness Shroff.  Adaptive control of differentially private linear quadratic systems.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 485–490. IEEE, 2021.
  * [CZZ+20] Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, and Liwei Wang.  (locally) differentially private combinatorial semi-bandits.  In International Conference on Machine Learning, pages 1757–1767. PMLR, 2020.
  * [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum.  Differential privacy under continual observation.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 715–724, 2010.
  * [DR+14a] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * [DR+14b] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  2014\.
  * [Dub21] Abhimanyu Dubey.  No-regret algorithms for private gaussian process bandit optimization.  In International Conference on Artificial Intelligence and Statistics, pages 2062–2070. PMLR, 2021.
  * [Dwo08] Cynthia Dwork.  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer, 2008.
  * [EFM+19] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468–2479. SIAM, 2019.
  * [FMT20] Vitaly Feldman, Audra McMillan, and Kunal Talwar.  Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling.  arXiv preprint arXiv:2012.12803, 2020.
  * [GCPP21] Evrard Garcelon, Kamalika Chaudhuri, Vianney Perchet, and Matteo Pirotta.  Privacy amplification via shuffling for linear contextual bandits.  arXiv preprint arXiv:2112.06008, 2021.
  * [GDD+21] Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh.  Shuffled model of differential privacy in federated learning.  In International Conference on Artificial Intelligence and Statistics, pages 2521–2529. PMLR, 2021.
  * [GGK+19] Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker.  On the power of multiple anonymous messages.  arXiv preprint arXiv:1908.11358, 2019.
  * [GPPBP20] Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, and Matteo Pirotta.  Local differentially private regret minimization in reinforcement learning.  arXiv preprint arXiv:2010.07778, 2020.
  * [GTS13] Abhradeep Guha Thakurta and Adam Smith.  (nearly) optimal algorithms for private online learning in full-information and bandit settings.  Advances in Neural Information Processing Systems, 26:2733–2741, 2013.
  * [HHR+16] Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu.  Private matchings and allocations.  SIAM Journal on Computing, 45(6):1953–1984, 2016.
  * [HLWZ21] Yuxuan Han, Zhipeng Liang, Yang Wang, and Jiheng Zhang.  Generalized linear bandits with local differential privacy.  arXiv preprint arXiv:2106.03365, 2021.
  * [HZZ+20] Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W Glynn, and Yinyu Ye.  Sequential batch learning in finite-action linear contextual bandits.  arXiv preprint arXiv:2004.06321, 2020.
  * [KLS21] Peter Kairouz, Ziyu Liu, and Thomas Steinke.  The distributed discrete gaussian mechanism for federated learning with secure aggregation.  In NeurIPS, 2021.
  * [KPRU14] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman.  Mechanism design in large games: Incentives and privacy.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403–410, 2014.
  * [LCLS10] Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010.
  * [LHG21] Chonghua Liao, Jiafan He, and Quanquan Gu.  Locally differentially private reinforcement learning for linear mixture markov decision processes.  arXiv preprint arXiv:2110.10133, 2021.
  * [LR21] Andrew Lowy and Meisam Razaviyayn.  Private federated learning without a trusted server: Optimal algorithms for convex losses.  arXiv preprint arXiv:2106.09779, 2021.
  * [Mir12] Ilya Mironov.  On significance of the least significant bits for differential privacy.  In Proceedings of the 2012 ACM conference on Computer and communications security, pages 650–661, 2012.
  * [MT15] Nikita Mishra and Abhradeep Thakurta.  (nearly) optimal differentially private stochastic multi-arm bandits.  In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pages 592–601, 2015.
  * [RZK20] Zhimei Ren, Zhengyuan Zhou, and Jayant R Kalagnanam.  Batched learning in generalized linear contextual bandits with general decision sets.  IEEE Control Systems Letters, 2020.
  * [RZLS20] Wenbo Ren, Xingyu Zhou, Jia Liu, and Ness B Shroff.  Multi-armed bandits with local differential privacy.  arXiv preprint arXiv:2007.03121, 2020.
  * [SBF17] Eric M Schwartz, Eric T Bradlow, and Peter S Fader.  Customer acquisition via display advertising using multi-armed bandit experiments.  Marketing Science, 36(4):500–522, 2017.
  * [SS18] Roshan Shariff and Or Sheffet.  Differentially private contextual linear bandits.  Advances in Neural Information Processing Systems, 31:4296–4306, 2018.
  * [SS19] Touqir Sajed and Or Sheffet.  An optimal private stochastic-mab algorithm based on optimal private stopping rule.  In International Conference on Machine Learning, pages 5579–5588. PMLR, 2019.
  * [TD17] Aristide Tossou and Christos Dimitrakakis.  Achieving privacy in the adversarial multi-armed bandit.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
  * [TKMS21] Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer.  Differentially private multi-armed bandits in the shuffle model.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
  * [TM17] Ambuj Tewari and Susan A Murphy.  From ads to interventions: Contextual bandits in mobile health.  In Mobile Health, pages 495–517. Springer, 2017.
  * [VBKW20] Giuseppe Vietri, Borja Balle, Akshay Krishnamurthy, and Steven Wu.  Private reinforcement learning with pac and regret guarantees.  In International Conference on Machine Learning, pages 9754–9764. PMLR, 2020.
  * [Ver18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [VMDK20] Sharan Vaswani, Abbas Mehrabian, Audrey Durand, and Branislav Kveton.  Old dog learns new tricks: Randomized ucb for bandit problems.  In International Conference on Artificial Intelligence and Statistics, pages 1988–1998. PMLR, 2020.
  * [WZG21] Tianhao Wang, Dongruo Zhou, and Quanquan Gu.  Provably efficient reinforcement learning with linear function approximation under adaptivity constraints.  arXiv preprint arXiv:2101.02195, 2021.
  * [XJ14] Yu Xin and Tommi Jaakkola.  Controlling privacy in recommender systems.  Neural Information Processing Systems, 2014.
  * [ZCH+20] Kai Zheng, Tianle Cai, Weiran Huang, Zhenguo Li, and Liwei Wang.  Locally differentially private (contextual) bandits learning.  In NeurIPS, 2020.
  * [Zho22] Xingyu Zhou.  Differentially private reinforcement learning with linear function approximation.  arXiv preprint arXiv:2201.07052, 2022.
  * [ZT20] Xingyu Zhou and Jian Tan.  Local differential privacy for bayesian optimization.  arXiv preprint arXiv:2010.06709, 2020.

##  Appendix A A Unified Regret Analysis Under Differential Privacy

In this section, we will formally state Lemma 3.9, i.e., the generic regret of
Algorithm 1 under sub-Gaussian private noise and then present its proof.

Let’s first recall the following notations. For each batch $m\in[M]$, let
$N_{m}:=\widetilde{V}_{m}-\sum_{t=t_{m-1}+1}^{t_{m}}\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$
denote the additional noise injected into the non-private Gram-matrix and
similarly let
$n_{m}:=\widetilde{u}_{m}-\sum_{t=t_{m-1}+1}^{t_{m}}\phi(c_{t},a_{t})y_{t}$
denote the additional noise injected into the non-private feature-reward
vector. Then, we let $H_{m}:=\lambda I_{d}+\sum_{i=1}^{m}N_{i}$ to denote the
_total_ noise in the first $m$ batches plus the regularizer, and similarly let
$h_{m}:=\sum_{i=1}^{m}n_{i}$.

######  Assumption A.1 (Regularity).

For any $\alpha\in(0,1]$, $H_{m}$ is positive definite and there exist
constants $\lambda_{\max}$, $\lambda_{\min}$ and $\nu$ depending on $\alpha$,
such that with probability at least $1-\alpha$, for all $m\in[M]$

$\displaystyle\left\lVert H_{m}\right\rVert\leq\lambda_{\max},\quad\left\lVert
H_{m}^{-1}\right\rVert\leq 1/\lambda_{\min},\quad\left\lVert
h_{m}\right\rVert_{H_{m}^{-1}}\leq\nu.$

With the above regularity assumption and the boundedness in Assumption 3.1, we
fist establish the following general regret bound of Algorithm 1, which can be
viewed as a direct generalization of the results in [SS18] to the batched
case.

######  Lemma A.2.

Let Assumptions A.1 and 3.1 hold. Fix any $\alpha\in(0,1]$, with probability
at least $1-\alpha$, the regret of Algorithm 1 satisfies

$\displaystyle\text{Reg}(T)\leq\frac{dB}{\log
2}\log\left(1+\frac{T}{d\lambda_{\min}}\right)+8\beta_{M}\sqrt{dT\log\left(1+\frac{T}{d\lambda_{\min}}\right)},$

where

$\displaystyle\beta_{M}:=\sqrt{2\log\left(\frac{2}{\alpha}\right)+d\log\left(1+\frac{T}{d\lambda_{\min}}\right)}+\sqrt{\lambda_{\max}}+\nu.$

In fact, Lemma 3.9 in the main paper is a simple application of Lemma A.2 by
considering the following assumption.

######  Assumption A.3 (sub-Gaussian private noise).

There exist constants $\widetilde{\sigma}_{1}$ and $\widetilde{\sigma}_{2}$
such that for all $m\in[M]$: (i) $\sum_{m^{\prime}=1}^{m}n_{m^{\prime}}$ is a
random vector whose entries are independent, mean zero, sub-Gaussian with
variance at most $\widetilde{\sigma}_{1}^{2}$, and (ii)
$\sum_{m^{\prime}=1}^{m}N_{m^{\prime}}$ is a random symmetric matrix whose
entries on and above the diagonal are independent sub-Gaussian random
variables with variance at most $\widetilde{\sigma}_{2}^{2}$. Let
$\sigma^{2}\\!=\\!\max\\{\widetilde{\sigma}_{1}^{2},\widetilde{\sigma}_{2}^{2}\\}$.

Now, we are well-prepared to formally state Lemma 3.9 in the main paper.

######  Lemma A.4 (Formal statement of Lemma 3.9).

Let Assumptions A.3 and 3.1 hold. Fix time horizon $T\in\mathbb{N}$, batch
size $B\in[T]$, confidence level $\alpha\in(0,1]$. Set
$\lambda=\Theta(\max\\{1,\sigma(\sqrt{d}+\sqrt{\log(T/(B\alpha))}\\})$ and
$\beta_{m}=\sqrt{2\log\left(\frac{2}{\alpha}\right)+d\log\left(1+\frac{T}{d\lambda}\right)}+\sqrt{\lambda}$.
Then, Algorithm 1 achieves regret

$\displaystyle Reg(T)=O\left({dB}\log
T+d\sqrt{T}\log(T/\alpha)\right)+O\left(\sqrt{\sigma T}d^{3/4}\log
T\log(T/\alpha)\right)$

with probability at least $1-\alpha$.

######  Remark A.5.

The above lemma also presents a regret bound for non-private batched LCB when
$\sigma=0$. Note that in this case, our regret bound is achieved with a
_dimension-independent_ regularizer, in contrast to the necessary condition on
$\lambda=\tilde{\Theta}(d)$ as required in [RZK20] to attain the optimal
regret.

###  A.1 Proofs

In this section, we present proofs for Lemma A.2 and Lemma A.4 above,
respectively.

###### Proof of Lemma A.2.

Let $\mathcal{E}$ be the event given in Assumption A.1, which holds with
probability at least $1-\alpha$ under Assumption A.1. In the following, we
condition on the event $\mathcal{E}$. We first show that
$\widehat{\theta}_{m}$ concentrates around the true parameter $\theta^{*}$
with a properly chosen confidence radius $\beta_{m}$ for all $m\in[M]$. To
this end, note that

$\displaystyle\widehat{\theta}_{m}$ $\displaystyle=V_{m}^{-1}u_{m}$
$\displaystyle=\left(\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}+\lambda
I_{d}+\sum_{i=1}^{m}N_{m}\right)^{-1}\left(\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})y_{t}+\sum_{i=1}^{m}n_{m}\right)$
$\displaystyle=\left(\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}+H_{m}\right)^{-1}\left(\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})y_{t}+h_{m}\right).$

By the linear reward function
$y_{t}=\langle\phi(c_{t},a_{t}),\theta^{*}\rangle+\eta_{t}$ and elementary
algebra, we have

$\displaystyle\theta^{*}-\widehat{\theta}_{m}=V_{m}^{-1}\left(H_{m}\theta^{*}-\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\eta_{t}-h_{m}\right).$

Thus, multiplying both sides by $V_{m}^{1/2}$, yields

$\displaystyle\left\lVert\theta^{*}-\widehat{\theta}_{m}\right\rVert_{V_{m}}$
$\displaystyle\leq\left\lVert\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\eta_{t}\right\rVert_{V_{m}^{-1}}+\left\lVert
H_{m}\theta^{*}\right\rVert_{V_{m}^{-1}}+\left\lVert
h_{m}\right\rVert_{V_{m}^{-1}}$
$\displaystyle\mathop{\leq}\limits^{(a)}\left\lVert\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\eta_{t}\right\rVert_{(G_{m}+\lambda_{\min}I)^{-1}}+\left\lVert\theta^{*}\right\rVert_{H_{m}}+\left\lVert
h_{m}\right\rVert_{H_{m}^{-1}},$

where (a) holds by $V_{m}\succeq H_{m}$ and $V_{m}\succeq
G_{m}+\lambda_{\min}I$ with
$G_{m}:=\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}$ under
event $\mathcal{E}$. Further, by the boundedness condition of $\theta^{*}$ and
event $\mathcal{E}$,
$\left\lVert\theta^{*}\right\rVert_{H_{m}}\leq\sqrt{\lambda_{\max}}$ and
$\left\lVert h_{m}\right\rVert_{H_{m}^{-1}}\leq\nu$. For the remaining first
term, we can use self-normalized inequality (cf. Theorem 1 in [AYPS11]) with
the filtration
$\mathcal{F}_{t}=\sigma(c_{1},a_{1},y_{1},\ldots,c_{t},a_{t},y_{t},c_{t+1},a_{t+1})$.
In particular, we have with probability at least $1-\alpha$, for all $m\in[M]$

$\displaystyle\left\lVert\sum_{t=1}^{t_{m}}\phi(c_{t},a_{t})\eta_{t}\right\rVert_{(G_{m}+\lambda_{\min}I)^{-1}}\leq\sqrt{2\log\left(\frac{1}{\alpha}\right)+\log\left(\frac{\det(G_{m}+\lambda_{\min}I)}{\det(\lambda_{\min}I)}\right)}.$
(1)

Now, using the trace-determinant lemma (cf. Lemma 10 in [AYPS11]) and the
boundedness condition on $\left\lVert\phi(c,a)\right\rVert$, we have

$\displaystyle\det(G_{m}+\lambda_{\min}I)\leq\left(\lambda_{\min}+\frac{t_{m}}{d}\right)^{d}.$

Putting everything together, we have with probability at least $1-2\alpha$,
for all $m\in[M]$,
$\left\lVert\theta^{*}-\widehat{\theta}_{m}\right\rVert_{V_{m}}\leq\beta_{m}$,
where

$\displaystyle\beta_{m}:=\sqrt{2\log\left(\frac{1}{\alpha}\right)+d\log\left(1+\frac{t_{m}}{d\lambda_{\min}}\right)}+\sqrt{\lambda_{\max}}+\nu.$

With the above concentration result and our OFUL-type algorithm, the regret
can be upper bounded as follows.

$\displaystyle\mathcal{R}(T)$
$\displaystyle=\sum_{m=1}^{M}\left[2\beta_{m-1}\sum_{t=t_{m-1}+1}^{t_{m}}\left(\left\lVert\phi(c_{t},a_{t})\right\rVert_{V_{m-1}^{-1}}\right)\right]$
$\displaystyle\leq\sum_{m=1}^{M}\left[2\beta_{M}\sum_{t=t_{m-1}+1}^{t_{m}}\left(\left\lVert\phi(c_{t},a_{t})\right\rVert_{(G_{m-1}+\lambda_{\min}I)^{-1}}\right)\right]$
(2)

At this moment, we note that the standard elliptical potential lemma (cf.
Lemma 11 in [AYPS11]) cannot be applied to our batch setting due to the delay
of $G_{m}$.

To handle this, inspired by [WZG21], we let
$\widehat{V}_{k}:=\sum_{t=1}^{k}\phi(c_{t},a_{t})\phi(c_{t},a_{t})^{\top}+\lambda_{\min}I_{d}$,
that is, a (virtual) design matrix at the end of time $k$. Hence, we have
$G_{m-1}+\lambda_{\min}I_{d}=\widehat{V}_{t_{(m-1)}}$. Moreover, for any
$t_{m-1}<t\leq t_{m}$, let $m_{t}=t_{m-1}$, that is, mapping $t$ to the
starting time of the batch that includes $t$. Finally, let
$\Gamma_{i}(\cdot,\cdot):=\beta_{M}\cdot\left\lVert\phi(\cdot,\cdot)\right\rVert_{\widehat{V}_{i}^{-1}}$.

With above notations, the bound in (A.1) can be rewritten as follows.

$\displaystyle R(T)$
$\displaystyle\leq\sum_{m=1}^{M}\left[2\beta_{M}\sum_{t=t_{m-1}+1}^{t_{m}}\left(\left\lVert\phi(c_{t},a_{t})\right\rVert_{(G_{m-1}+\lambda_{\min})^{-1}}\right)\right]$
$\displaystyle=\sum_{t=1}^{T}2\Gamma_{m_{t}}(c_{t},a_{t})$

In the sequential case (i.e., $B=1$), we always have $m_{t}=t-1$. Thus, the
key is to bound the difference between $\Gamma_{m_{t}}(c_{t},a_{t})$ and
$\Gamma_{t-1}(c_{t},a_{t})$. To this end, we have the following claim, which
will be proved at the end.

######  Claim A.6.

Define the set $\Psi$ as follows

$\displaystyle\Psi=\\{t\in[T]:\Gamma_{m_{t}}(c_{t},a_{t})/\Gamma_{t-1}(c_{t},a_{t})>2\\}.$

Then, we have

$\displaystyle|\Psi|\leq\frac{dT}{2M\log
2}\log\left(1+\frac{T}{d\lambda_{\min}}\right).$

According to Claim A.6, we can decompose regret as follows.

$\displaystyle R(T)$
$\displaystyle\mathop{\leq}\limits^{(a)}\sum_{t=1}^{T}\min\\{2\Gamma_{m_{t}}(c_{t},a_{t}),1\\}$
$\displaystyle=\sum_{t\in\Psi}\min\\{2\Gamma_{m_{t}}(c_{t},a_{t}),1\\}+\sum_{t\notin\Psi}\min\\{2\Gamma_{m_{t}}(c_{t},a_{t}),1\\}$
$\displaystyle\mathop{\leq}\limits^{(b)}|\Psi|+\sum_{t\notin\Psi}\min\\{4\Gamma_{t-1}(c_{t},a_{t}),1\\}$
$\displaystyle\mathop{\leq}\limits^{(c)}|\Psi|+\sum_{t=1}^{T}4\beta_{M}\min\\{\left\lVert\phi(c_{t},a_{t})\right\rVert_{\widehat{V}_{t-1}^{-1}},1\\}$
$\displaystyle\mathop{\leq}\limits^{(d)}\frac{dT}{2M\log
2}\log\left(1+\frac{T}{d\lambda_{\min}}\right)+8\beta_{M}\sqrt{dT\log\left(1+\frac{T}{d\lambda_{\min}}\right)}$

where (a) holds by the boundedness of reward; (b) holds by definition of
$\Psi$; (c) holds by the fact that $\beta_{M}\geq 1$; (d) follows from Claim
A.6 and standard argument for linear bandit, i.e., Cauchy-Schwartz and
standard elliptical potential lemma (cf. Lemma 11 in [AYPS11]). Hence, we have
finished the proof of Lemma A.2.

Finally, we give the proof of Claim A.6.

For any $t\in\Psi$, suppose $t_{m-1}<t\leq t_{m}$ for some $m$. Then, we have
$m_{t}=t_{(m-1)}$ and

$\displaystyle\log\det(\widehat{V}_{t_{m}})-\log\det(\widehat{V}_{t_{(m-1)}})\mathop{\geq}\limits^{(a)}\log\det(\widehat{V}_{t-1})-\log\det(\widehat{V}_{m_{t}})\mathop{\geq}\limits^{(b)}2\log(\Gamma_{m_{t}}(c_{t},a_{t})/\Gamma_{t-1}(c_{t},a_{t}))>2\log
2,$

where (a) holds by the fact $\widehat{V}_{t_{m}}\succeq\widehat{V}_{t-1}$; (b)
holds by Lemma 12 in [AYPS11], that is, for two positive definite matrices
$A,B\in\mathbb{R}^{d\times d}$ satisfying $A\succeq B$, then for any
$x\in\mathbb{R}^{d}$, $\left\lVert x\right\rVert_{A}\leq\left\lVert
x\right\rVert_{B}\cdot\sqrt{\det(A)/\det(B)}$. Note that here we also use
$\det(A)=1/\det(A^{-1})$ for any matrix;

Therefore, if we let
$\widehat{\Psi}:=\\{m\in[M]:\log\det(\widehat{V}_{t_{m}})-\log\det(\widehat{V}_{t_{(m-1)}})>2\log
2\\}$, then we have $|\Psi|\leq(T/M)|\widehat{\Psi}|$. Thus, we only need to
bound $|\widehat{\Psi}|$. Note that for each $m$,
$\log\det(\widehat{V}_{t_{m}})-\log\det(\widehat{V}_{t_{(m-1)}})\geq 0$, and
hence

$\displaystyle 2\log
2\cdot|\widehat{\Psi}|\leq\sum_{m\in\widehat{\Psi}}\log\det(\widehat{V}_{t_{m}})-\log\det(\widehat{V}_{t_{(m-1)}})$
$\displaystyle\leq\sum_{m=1}^{M}\log\det(\widehat{V}_{t_{m}})-\log\det(\widehat{V}_{t_{(m-1)}})$
$\displaystyle=\log\left(\frac{\det(G_{M}+\lambda_{\min}I)}{\det(\lambda_{\min}I)}\right)$

Finally, using the same analysis as in (1), yields

$\displaystyle|\widehat{\Psi}|\leq\frac{d}{2\log
2}\log\left(1+\frac{T}{d\lambda_{\min}}\right),$

which directly implies the result of Claim A.6. ∎

###### Proof of Lemma A.4.

To prove the result, thanks to Lemma A.2, we only need to determine the three
constants $\lambda_{\max},\lambda_{\min}$ and $\nu$ under the sub-Gaussian
private noise assumption in Assumption A.3. To this end, we resort to
concentration bounds for sub-Gaussian random vector and random matrix.

To start with, under (i) in Assumption A.3, by the concentration bound for the
norm of a vector containing sub-Gaussian entries (cf. Theorem 3.1.1 in
[Ver18]) and a union bound over $m$, we have for all $m\in[M]$ and any
$\alpha\in(0,1]$, with probability at least $1-\alpha/2$, for some absolute
constant $c_{1}$,

$\displaystyle\left\lVert\sum_{i=1}^{m}n_{i}\right\rVert=\left\lVert
h_{m}\right\rVert\leq\Sigma_{n}:=c_{1}\cdot\widetilde{\sigma}_{1}\cdot(\sqrt{d}+\sqrt{\log(M/\alpha)}).$

By (ii) in Assumption A.3, the concentration bound for the norm of a sub-
Gaussian symmetric random matrix (cf. Corollary 4.4.8 [Ver18]) and a union
bound over $m$, we have for all $m\in[M]$ and any $\alpha\in(0,1]$, with
probability at least $1-\alpha/2$,

$\displaystyle\left\lVert\sum_{i=1}^{m}N_{i}\right\rVert\leq\Sigma_{N}:=c_{2}\cdot\widetilde{\sigma}_{2}\cdot(\sqrt{d}+\sqrt{\log(M/\alpha)})$

for some absolute constant $c_{2}$. Thus, if we choose $\lambda=2\Sigma_{N}$,
we have $\left\lVert H_{m}\right\rVert=\left\lVert\lambda
I_{d}+\sum_{i=1}^{m}N_{i}\right\rVert\leq 3\Sigma_{N}$, i.e.,
$\lambda_{\max}=3\Sigma_{N}$, and $\lambda_{\min}=\Sigma_{N}$. Finally, to
determine $\nu$, we note that

$\displaystyle\left\lVert
h_{m}\right\rVert_{H_{m}^{-1}}\leq\frac{1}{\sqrt{\lambda_{\min}}}\left\lVert
h_{m}\right\rVert\leq
c\cdot\left(\sigma\cdot(\sqrt{d}+\sqrt{\log(M/\alpha)})\right)^{1/2}:=\nu,$

where $\sigma=\max\\{\widetilde{\sigma}_{1},\widetilde{\sigma}_{2}\\}$. The
final regret bound is obtained by plugging the three values into the result
given by Lemma A.2. ∎

##  Appendix B Analysis of LDP Amplification Protocol

###  B.1 Pseudocode of $\mathcal{P}_{\text{Amp}}$

The shuffle protocol is given by
$\mathcal{P}_{\text{Amp}}\\!=\\!(\mathcal{R}_{\text{Amp}},\mathcal{S}_{\text{Amp}},\mathcal{A}_{\text{Amp}})$,
in which $\mathcal{R}_{\text{Amp}}$ is presented in Algorithm 2,
$\mathcal{S}_{\text{Amp}}$ is presented in Algorithm 3, and
$\mathcal{A}_{\text{Amp}}$ is presented in Algorithm 4.

Algorithm 2 Local Randomizer $\mathcal{R}_{\text{Amp}}$

1: Parameters: $\sigma_{1},\sigma_{2},d$

2: function $R_{1}(\phi(c,a)y)$

3: Sample fresh noise $n\sim\mathcal{N}(0,\sigma_{2}^{2}I_{d\times d})$

4: $M_{1}=\phi(c,a)y+n$

5: return $M_{t,1}$

6: end function

7: function $R_{2}(\phi(c,a)\phi(c,a)^{\top})$

8: Sample fresh noise $N_{(i,j)}\sim\mathcal{N}(0,\sigma_{1}^{2}),\forall
i\leq j\leq d$ and let $N_{(j,i)}=N_{(i,j)}$

9: $M_{2}=\phi(c,a)\phi(c,a)^{\top}+N$

10: return $M_{2}$

11: end function

Algorithm 3 Shuffler $\mathcal{S}_{\text{Amp}}$

1: Input: $\\{M_{\tau,1}\\}_{\tau\in\mathcal{B}}$ and
$\\{M_{\tau,2}\\}_{\tau\in\mathcal{B}}$, in which $\mathcal{B}$ is a batch and
$M_{\tau,1}\in\mathbb{R}^{d}$, $M_{\tau,2}\in\mathbb{R}^{d\times d}$ come from
user $\tau$

2: function $S_{1}(\\{M_{\tau,1}\\}_{\tau\in\mathcal{B}})$

3: Generate a uniform permutation $\pi$ of indexes in $\mathcal{B}$

4: Set $Y_{1}=(M_{\pi(1),1},\ldots,M_{\pi(B),1})$

5: return $Y_{1}$

6: end function

7: function $S_{2}(\\{M_{\tau,2}\\}_{\tau\in\mathcal{B}})$

8: Generate a uniform permutation $\pi$ of indexes in $\mathcal{B}$

9: Set $Y_{2}=(M_{\pi(1),2},\ldots,M_{\pi(B),2})$

10: return $Y_{2}$

11: end function

Algorithm 4 Analyzer $\mathcal{A}_{\text{Amp}}$

1: Input: Shuffled outputs $Y_{1}=(M_{\pi(1),1},\ldots,M_{\pi(B),1})$ and
$Y_{2}=(M_{\pi(1),2},\ldots,M_{\pi(B),2})$

2: function $A_{1}(Y_{1})$

3: return $\sum_{i=1}^{B}M_{\pi(i),1}$

4: end function

5: function $A_{1}(Y_{2})$

6: return $\sum_{i=1}^{B}M_{\pi(i),2}$

7: end function

###  B.2 Main Results

######  Theorem B.1 (Restatement of Theorem 3.2).

Fix time horizon $T\in\mathbb{N}$, batch size $B\in[T]$, confidence level
$\alpha\in(0,1]$, , and privacy budgets
$\varepsilon\in(0,\sqrt{\frac{{\log(2/\delta)}}{{B}}}]$, $\delta\in(0,1]$.
Then, Algorithm 1 instantiated with shuffle protocol
$\mathcal{P}_{\text{Amp}}$ with noise levels
$\sigma_{1}\\!=\\!\sigma_{2}\\!=\\!\frac{4\sqrt{2\log(2.5B/\delta)\log(2/\delta)}}{\varepsilon\sqrt{B}}$,
and regularizer
$\lambda=\Theta(\sqrt{T}\sigma_{1}(\sqrt{d}+\sqrt{\log(T/B\alpha)})$, enjoys
the regret

$\displaystyle\text{Reg}(T)\\!=\\!O\\!\\!\left(\\!dB\log
T\\!+\\!\frac{\log^{1/4}(B/\delta)\log^{1/4}(2/\delta)}{\varepsilon^{1/2}B^{1/4}}d^{3/4}T^{3/4}\log
T\log(T/\alpha)\\!\\!\right),$

with probability at least $1-\alpha$. Moreover, it satisfies
$O(\varepsilon,\delta)$-shuffle differential privacy (SDP).

######  Corollary B.2 (Utility-targeted).

Under the same assumption in Theorem B.1 and Algorithm 1 is instantiated with
$\mathcal{P}_{\text{Amp}}$. Let
$B=O(d^{-1/5}\varepsilon^{-2/5}T^{3/5}\log^{1/5}(T/\delta)\log^{1/5}(2/\delta)$,
Algorithm 1 achieves $O(\varepsilon,\delta)$-SDP with regret

$\displaystyle
Reg(T)=\widetilde{O}\left(d^{4/5}T^{3/5}\varepsilon^{-2/5}\log^{1/5}(T/\delta)\log^{1/5}(2/\delta)\right).$

Simultaneously, Algorithm 1 also achieves ${O}(\varepsilon,\delta)$-JDP and
${O}(\varepsilon_{0},\delta_{0})$-LDP where

$\displaystyle\varepsilon_{0}=O\left(\varepsilon^{4/5}T^{3/10}d^{-1/10}\log^{1/10}(T/\delta)\log^{-2/5}(2/\delta)\right),\quad\delta_{0}=O\left(\delta
d^{1/5}T^{-3/5}\varepsilon^{2/5}\log^{-1/5}(T/\delta)\log^{-1/5}(2/\delta)\right).$

######  Corollary B.3 (Privacy-targeted).

Let Assumption 3.1 hold and Algorithm 1 is instantiated with
$\mathcal{P}_{\text{Amp}}$. For any $\varepsilon_{0}\in[0,1]$ and
$\delta_{0}\in(0,1]$, let
$\sigma_{1}=\sigma_{2}=\frac{4\sqrt{2\log(2.5/\delta_{0})}}{\varepsilon_{0}}$.
Then, for all $B\in[T]$, Algorithm 1 is $(\varepsilon_{0},\delta_{0})$-LDP.
Further suppose
$B=O(d^{-1/4}T^{3/4}\varepsilon_{0}^{-1/2}\log^{1/4}(1/\delta_{0}))$, then
Algorithm 1 achieves regret

$\displaystyle
Reg(T)=\tilde{O}\left(d^{3/4}T^{3/4}\varepsilon_{0}^{-1/2}\log^{1/4}(1/\delta_{0})\right).$

Simultaneously, Algorithm 1 achieves $O(\varepsilon,\delta)$-SDP and
$O(\varepsilon,\delta)$-JDP where

$\displaystyle\varepsilon=O\left(\varepsilon_{0}^{5/4}T^{-3/8}d^{1/8}\log^{3/8}(1/\delta_{0})\right),\quad\delta=O(\delta_{0}d^{-1/4}T^{3/4}\varepsilon_{0}^{-1/2}\log^{1/4}(1/\delta_{0})).$

###  B.3 Proofs

To prove Theorem B.1, we need the following important lemma, which can be seen
as a special case of Theorem 3.8 in [FMT20]. In particular, in our paper, we
consider a fixed local randomizer rather than the more general adaptive one in
[FMT20]. Another difference is that we consider the case of _randomizer-then-
shuffle_ rather than the _shuffle-then-randomizer_. However, as pointed in
[FMT20], the two cases are equivalent when the local randomizer is a fixed
one.

######  Lemma B.4 (Amplification by shuffling).

Consider a one-round protocol
$\mathcal{P}=(\mathcal{R},\mathcal{S},\mathcal{A})$ over $n$ users. Let
$\mathcal{R}$ be an $(\varepsilon_{0},\delta_{0})$-LDP mechanism. Then, for
any $\delta^{\prime}\in[0,1]$ such that
$\varepsilon_{0}\leq\log(\frac{n}{16\log(2/\delta^{\prime})})$, $\mathcal{P}$
is $(\widetilde{\varepsilon},\widetilde{\delta})$-SDP, i.e., the analyzer’s
view is $(\widetilde{\varepsilon},\widetilde{\delta})$-DP, where

$\displaystyle\widetilde{\varepsilon}\leq\log\left(1+\frac{e^{\varepsilon_{0}}-1}{e^{\varepsilon_{0}}+1}\left(\frac{8\sqrt{e^{\varepsilon_{0}}\log(4/\delta^{\prime})}}{\sqrt{n}}+\frac{8e^{\varepsilon_{0}}}{n}\right)\right),\widetilde{\delta}=\delta^{\prime}+(e^{\varepsilon}+1)\left(1+\frac{e^{-\varepsilon_{0}}}{2}\right)n\delta_{0},$

That is, when $\varepsilon_{0}>1$,
$\widetilde{\varepsilon}=O\left(\frac{\sqrt{e^{\varepsilon_{0}}\log(1/\delta^{\prime})}}{\sqrt{n}}\right)$
and when $\varepsilon_{0}\leq 1$,
$\widetilde{\varepsilon}=O\left(\varepsilon_{0}\frac{\sqrt{\log(1/\delta^{\prime})}}{\sqrt{n}}\right)$.

Roughly speaking, we have a privacy amplification by a factor $\sqrt{n}$ due
to shuffling, which is the key to our analysis.

###### Proof of Theorem B.1.

To apply Lemma B.4, we choose $\delta^{\prime}=\delta/2$ and
$\varepsilon_{0}=\frac{\varepsilon\sqrt{B}}{\sqrt{\log(1/\delta^{\prime})}}=\frac{\varepsilon\sqrt{B}}{\sqrt{\log(2/\delta)}}$.
For any $\varepsilon\in(0,\sqrt{\log(2/\delta)}/\sqrt{B}]$, we have
$\varepsilon_{0}\leq 1$, which implies
$\widetilde{\varepsilon}=O(\varepsilon)$. Meanwhile, we let
$\delta_{0}=\delta/B$ for any $\delta\in[0,1]$, which implies that
$\widetilde{\delta}=O(\delta)$. Now, we are only left to choose $\sigma_{1}$
and $\sigma_{2}$ in $\mathcal{R}_{\text{Amp}}$ so that it is
$(\varepsilon_{0},\delta_{0})$-LDP. To this end, via the standard Gaussian
mechanism and boundedness assumption, we have when

$\displaystyle\sigma_{1}=\sigma_{2}=\frac{4\sqrt{2\log(2.5/\delta_{0})}}{\varepsilon_{0}},$

$\mathcal{R}_{\text{Amp}}$ is $(\varepsilon_{0},\delta_{0})$-LDP. Finally,
plugging in $\varepsilon_{0}=\varepsilon\sqrt{B}/\sqrt{\log(2/\delta)}$ and
$\delta_{0}=\delta/B$, yields

$\displaystyle\sigma_{1}=\sigma_{2}=\frac{4\sqrt{2\log(2.5B/\delta)\log(2/\delta)}}{\varepsilon\sqrt{B}}.$

Finally, plugging the value
$\sigma=\frac{4\sqrt{2T\log(2.5B/\delta)\log(2/\delta)}}{\varepsilon\sqrt{B}}$
(since there are total at most $T$ noise) into the regret bound in Lemma A.4
yields the required results. ∎

###### Proof of Corollary B.2.

To establish the regret bound, we simply choose a balanced $B$ in the regret
bound given by Theorem B.1. To prove the JDP guarantee, we will use the
powerful _Billboard lemma_ (cf. Lemma 9 in [HHR+16]), which says that an
algorithm is JDP if the action recommended to each user is a function of her
private data and a common signal computed in a differential private way. In
our case, the private data is user’s context and the common signal is the
updated policy (i.e., $\widehat{\theta}_{m}$ and design matrix $V_{m}$), which
is a post-processing of shuffle outputs. Thus, the SDP guarantee directly
implies the JDP guarantee in our case. Finally, the LDP guarantee simply
follows from the standard Gaussian mechanism with parameter
$\varepsilon_{0}=\varepsilon\sqrt{B}/\sqrt{\log(2/\delta)}$ and
$\delta_{0}=\delta/B$. ∎

###### Proof of Corollary B.3.

The LDP guarantee follows from standard Gaussian mechanism. To show the regret
bound, we will use the result in Theorem B.1. In particular, comparing the
values of $\sigma_{1},\sigma_{2}$ in Corollary B.3 and the values in Theorem
B.1, we can plug
$\varepsilon=\frac{\varepsilon_{0}\sqrt{\log(2/\delta)}}{\sqrt{B}}$ and
$\delta=\delta_{0}B$ into the regret bound in Theorem B.1. Then, with a
balanced choice of $B$, we obtain the required regret. The SDP guarantee also
follows from Theorem B.1 with
$\varepsilon=\frac{\varepsilon_{0}\sqrt{\log(2/\delta)}}{\sqrt{B}}$ and
$\delta=\delta_{0}B$. Finally, as in the proof of Corollary B.2, the JDP
guarantee follows from SDP guarantee and Billboard lemma. ∎

##  Appendix C Analysis of Vector Summation Protocol

###  C.1 Pseudocode of $\mathcal{P}_{\text{Vec}}$

The shuffle protocol is given by
$\mathcal{P}_{\text{Vec}}\\!=\\!(\mathcal{R}_{\text{Vec}},\mathcal{S}_{\text{Vec}},\mathcal{A}_{\text{Vec}})$,
in which $\mathcal{R}_{\text{Vec}}$ is presented in Algorithm 5,
$\mathcal{S}_{\text{Vec}}$ is presented in Algorithm 6, and
$\mathcal{A}_{\text{Vec}}$ is presented in Algorithm 7. Note that the original
algorithm for the analyzer in [CJMP21] has a small issue in the de-bias
process (cf. Algorithm 2 in [CJMP21]). In particular, instead of subtracting
the norm $\Delta$, one needs to subtract $B\cdot\Delta$, see Lines 11 and 19
in Algorithm 7. Here, $B$ corresponds to $n$ in Algorithm 2 of [CJMP21].

Algorithm 5 Local Randomizer $\mathcal{R}_{\text{Vec}}$

1: Parameters: $g,b,p,d$

2: # Local randomizer for a scalar within $[0,\Delta]$

3: function $\mathcal{R}^{*}(x,\Delta)$

4: Set $\bar{x}=\lfloor{xg/\Delta}\rfloor$

5: Sample rounding value $\gamma_{1}\sim\textbf{Ber}(xg/\Delta-\bar{x})$

6: Set $\widehat{x}=\bar{x}+\gamma_{1}$

7: Sample binomial noise $\gamma_{2}\sim\textbf{Bin}(b,p)$

8: Set $m$ be a multi-set containing $\widehat{x}+\gamma_{2}$ copies of $1$
and $(g+b)-(\widehat{x}+\gamma_{2})$ copies of $0$.

9: return $m$

10: end function

11: function $R_{1}(\phi(c,a)y)$

12: Set $\Delta_{1}=1$

13: for each coordinate $k\in[d]$ do

14: Shift data $w_{k}=[\phi(c,a)y]_{k}+\Delta_{1}$

15: Run the scalar randomizer $m_{k}=\mathcal{R}^{*}(w_{k},\Delta_{1})$

16: end for

17: # Labeled outputs (all bits in $m_{k}$ are labeled by $k$)

18: $M_{1}=\\{(k,m_{k})\\}_{k\in[d]}$

19: return $M_{1}$

20: end function

21: function $R_{2}(\phi(c,a)\phi(c,a)^{\top})$

22: Set $\Delta_{2}=1$

23: for all $i\leq j\leq d$ do

24: Shift data $w_{(i,j)}=[\phi(c,a)\phi(c,a)^{\top}]_{(i,j)}+\Delta_{2}$

25: Run the scalar randomizer to obtain
$m_{(i,j)}=\mathcal{R}^{*}(w_{(i,j)},\Delta_{2})$ and $m_{(j,i)}=m_{(i,j)}$

26: end for

27: # Labeled outputs

28: $M_{2}=\\{((i,j),m_{(i,j)})\\}_{(i,j)\in[d]\times[d]}$

29: return $M_{2}$

30: end function

Algorithm 6 Shuffler $\mathcal{S}_{\text{Vec}}$

1: Input: $\\{M_{\tau,1}\\}_{\tau\in\mathcal{B}}$ and
$\\{M_{\tau,2}\\}_{\tau\in\mathcal{B}}$, in which $\mathcal{B}$ is a batch of
users. $M_{\tau,1}=\\{(k,m_{k})\\}_{k\in[d]}$ and
$M_{2}=\\{((i,j),m_{(i,j)})\\}_{(i,j)\in[d]\times[d]}$ are labeled data of
user $\tau$

2: function $S_{1}(\\{M_{\tau,1}\\}_{\tau\in\mathcal{B}})$

3: Uniformly permutes all messages, i.e., a total of $(g+b)\cdot B\cdot d$
bits

4: Set $y_{k}$ be the collection of bits labeled by $k\in[d]$

5: Set $Y_{1}=\\{y_{1},\ldots,y_{d}\\}$

6: return $Y_{1}$

7: end function

8: function $S_{2}(\\{M_{\tau,2}\\}_{\tau\in\mathcal{B}})$

9: Uniformly permutes all messages, i.e., a total of $(g+b)\cdot B\cdot d^{2}$
bits

10: Set $y_{(i,j)}$ be the collection of bits labeled by
$(i,j)\in[d]\times[d]$

11: Set $Y_{2}=\\{y_{(i,j)}\\}_{(i,j)\in[d]\times d}$

12: return $Y_{2}$

13: end function

Algorithm 7 Analyzer $\mathcal{A}_{\text{Vec}}$

1: Input: Shuffled outputs $Y_{1}=\\{y_{k}\\}_{k\in[d]}$ and
$Y_{2}=\\{y_{(i,j)}\\}_{(i,j)\in[d]\times d}$

2: Initialize: $g,b,p$

3: # Analyzer for a collection $y$ of $(g+b)\cdot B$ bits using $\Delta$

4: function $\mathcal{A}^{*}(y,\Delta)$

5: return $\frac{\Delta}{g}\left((\sum_{i=1}^{(g+b)\cdot B}y_{i})-p\cdot
b\cdot B\right)$

6: end function

7: function $A_{1}(Y_{1})$

8: $\Delta_{1}=1$

9: for each coordinate $k\in[d]$ do

10: Run analyzer on $k$-th labeled data to obtain
$z_{k}=\mathcal{A}^{*}(y_{k},\Delta_{1})$

11: Re-center: $o_{k}=z_{k}-B\cdot\Delta_{1}$

12: end for

13: return $\\{o_{1},\ldots,o_{k}\\}$

14: end function

15: function $A_{2}(Y_{2})$

16: $\Delta_{2}=1$

17: for all $i\leq j\leq d$ do

18: Run analyzer on $(i,j)$-th labeled data to obtain
$z_{(i,j)}=\mathcal{A}^{*}(y_{(i,j)},\Delta_{2})$

19: Re-center: $o_{(i,j)}=z_{(i,j)}-B\cdot\Delta_{2}$ and
$o_{(j,i)}=o_{(i,j)}$

20: end for

21: return $\\{o_{(i,j)}\\}_{(i,j)\in[d]\times[d]}$

22: end function

###  C.2 Main Results

######  Theorem C.1 (Restatement of Theorem 3.5).

Fix batch size $B\\!\in\\![T]$, privacy budgets $\varepsilon\\!\in\\!(0,15]$,
$\delta\\!\in\\!(0,1/2)$. Then, Algorithm 1 instantiated with
$\mathcal{P}_{\text{Vec}}$ with parameters $p\\!=\\!1/4$,
$g\\!=\\!\max\\{2\sqrt{B},d,4\\}$ and $b\\!=\\!\frac{24\cdot 10^{4}\cdot
g^{2}\cdot\log^{2}\left(4(d^{2}+1)/\delta\right)}{\varepsilon^{2}B}$ is
$(\varepsilon,\delta)$-SDP. Furthermore, for any $\alpha\\!\in\\!(0,1]$,
setting
$\lambda\\!=\\!\Theta\\!\left(\\!\frac{\log(d^{2}/\delta)\sqrt{T}}{\varepsilon\sqrt{B}}(\\!\sqrt{d}\\!+\\!\sqrt{\log(T/(B\alpha))}\\!\right)$,
it enjoys the regret

$\displaystyle\text{Reg}(T)\\!=\\!O\\!\left(dB\log
T\\!+\\!\frac{\log^{1/2}(d^{2}/\delta)}{\varepsilon^{1/2}B^{1/4}}d^{3/4}T^{3/4}\log
T\log(T/\alpha)\right)\\!,$

with probability at least $1-\alpha$.

######  Corollary C.2 (Utility-targeted).

Under the same assumption in Theorem C.1 and Algorithm 1 is instantiated with
$\mathcal{P}_{\text{Vec}}$. Let
$B=O(d^{-1/5}\varepsilon^{-2/5}T^{3/5}\log^{2/5}(d^{2}/\delta))$, Algorithm 1
achieves $(\varepsilon,\delta)$-SDP with regret

$\displaystyle
Reg(T)=\widetilde{O}\left(d^{4/5}T^{3/5}\varepsilon^{-2/5}\log^{2/5}(d^{2}/\delta)\right).$

Simultaneously, Algorithm 1 also achieves $O(\varepsilon,\delta)$-JDP and
$O(\varepsilon_{0},\delta_{0})$-LDP where

$\displaystyle\varepsilon_{0}=O\left(\varepsilon^{4/5}T^{3/10}d^{-1/10}\log^{1/5}(d^{2}/\delta)\right),\quad\delta_{0}=O(\delta).$

######  Corollary C.3 (Privacy-targeted).

Let Assumption 3.1 hold and Algorithm 1 is instantiated with
$\mathcal{P}_{\text{Vec}}$. For any $\varepsilon_{0}\in(0,15]$ and
$\delta_{0}\in(0,1/2)$, let

$\displaystyle g=\max\\{d,4\\},\quad b=\frac{24\cdot 10^{4}\cdot
g^{2}\cdot\left(\log\left(\frac{4\cdot(d^{2}+1)}{\delta_{0}}\right)\right)^{2}}{\varepsilon_{0}^{2}},\quad
p=1/4,$

Then, for all $B\in[T]$, Algorithm 1 is $(\varepsilon_{0},\delta_{0})$-LDP.
Further suppose
$B=O(d^{-1/4}T^{3/4}\varepsilon_{0}^{-1/2}(\log(d^{2}/\delta_{0}))^{1/2})$,
then Algorithm 1 achieves regret

$\displaystyle
Reg(T)=\widetilde{O}\left(d^{3/4}T^{3/4}\frac{\log^{1/2}(d^{2}/\delta_{0})}{\sqrt{\varepsilon_{0}}}\right).$

Simultaneously, Algorithm 1 also achieves $O(\varepsilon,\delta)$-SDP and
$O(\varepsilon,\delta)$-JDP where

$\displaystyle\varepsilon=O\left(\varepsilon^{5/4}T^{-3/8}d^{1/8}(\log(d^{2}/\delta_{0}))^{-1/4}\right),\quad\delta=O(\delta_{0}).$

###  C.3 Proofs

###### Proof of Theorem C.1.

The privacy part follows from the one-round SDP guarantee of vector summation
protocol in [CJMP21]. In particular, by Theorem 3.2 in [CJMP21], we have to
properly choose parameters $g,b,p$ in $\mathcal{R}_{\text{Vec}}$. To this end,
by adapting the results of Lemma 3.1 in [CJMP21], we have in our case when one
chooses

$\displaystyle g=\max\\{2\sqrt{B},d,4\\},\quad b=\frac{24\cdot 10^{4}\cdot
g^{2}\cdot\left(\log\left(\frac{4\cdot(d^{2}+1)}{\delta}\right)\right)^{2}}{\varepsilon^{2}B},\quad
p=1/4,$

$\mathcal{P}_{\text{Vec}}$ is $(\varepsilon,\delta)$-SDP. It is worth pointing
out that here we choose $b$ such that $p=1/4$, which is necessary for our
following analysis on the tail of the private noise. This is the key
difference compared to the original one in [CJMP21] where the variance of the
noise is sufficient.

Now, we turn to regret analysis. Thanks to our general regret bound in
Corollary A.4, we only need to verify the condition of sub-Gaussian private
noise in the protocol $\mathcal{P}_{\text{Vec}}$ (in particular
$\mathcal{R}_{\text{Vec}}$). To this end, we need a more careful analysis
compared to [CJMP21] as the issue pointed above. Fix any coordinate $k\in[d]$,
we will determine the private noise in $k$, which motivates us to check the
scalar randomizer $\mathcal{R}^{*}$ in $\mathcal{R}_{\text{Vec}}$. Consider a
batch of users. Let $z_{i}$ denote the sum of $g+b$ bits generated by user $i$
using $\mathcal{R}^{*}$. That is, we have

$\displaystyle z_{i}=\bar{x}_{i}+\gamma_{1,i}+\gamma_{2,i}.$

This implies that

$\displaystyle
z_{i}-bp=\frac{g}{\Delta}x_{i}+\gamma_{1,i}+\bar{x}_{i}-\frac{g}{\Delta}x_{i}+\gamma_{2,i}-bp.$

Define shifted random variables
$\iota_{1,i}:=\gamma_{1,i}+\bar{x}_{i}-\frac{g}{\Delta}x_{i}$ and
$\iota_{2,i}:=\gamma_{2,i}-bp$. Thus, taking the summation over all $i$ within
a given batch $\mathcal{B}$ of size $B$, yields

$\displaystyle\sum_{i\in\mathcal{B}}z_{i}-B\cdot b\cdot
p=\frac{g}{\Delta}\sum_{i\in\mathcal{B}}x_{i}+\sum_{i\in\mathcal{B}}\iota_{1,i}+\sum_{i\in\mathcal{B}}\iota_{2,i},$

which implies that

$\displaystyle\frac{\Delta}{g}\left(\sum_{i\in\mathcal{B}}z_{i}-B\cdot b\cdot
p\right)=\sum_{i\in\mathcal{B}}x_{i}+\frac{\Delta}{g}\sum_{i\in\mathcal{B}}\iota_{1,i}+\frac{\Delta}{g}\sum_{i\in\mathcal{B}}\iota_{2,i}.$

Note that the above is exactly the output of the analyzer $\mathcal{A}^{*}$ in
$\mathcal{P}_{\text{Vec}}$. Thus, to verify the sub-Gaussian condition in
Assumption A.3, we only need to show that the last two terms above are zero-
mean and sub-Gaussian random variables. To this end, we note that
$\gamma_{1,i}$ is draw from Ber$(\frac{g}{\Delta}x_{i}-\bar{x}_{i})$. Hence,
$\mathbb{E}\left[\iota_{1,i}\right]=0$ and $\iota_{1,i}$ is sub-Gaussian with
variance $1/4$ since $\iota_{1,i}\in[0,1]$. By independence of private noise
across $i$, we have $\sum_{i\in\mathcal{B}}\iota_{1,i}$ is sub-Gaussian with
variance of $B/4$. Similarly, since $\gamma_{2,i}$ is independently sampled
from binomial Bin$(b,p)$, we have $\mathbb{E}\left[\iota_{2,i}\right]=0$ and
$\sum_{i\in\mathcal{B}}\iota_{2,i}$ can be viewed as a sum of $B\cdot b$
bounded random variable within $[0,1]$, hence it is sub-Gaussian with variance
of $B\cdot b/4$. Therefore, the total noise
$\frac{\Delta}{g}\sum_{i\in\mathcal{B}}\iota_{1,i}+\frac{\Delta}{g}\sum_{i\in\mathcal{B}}\iota_{2,i}$
is sub-Gaussian with variance given by

$\displaystyle\frac{\Delta^{2}}{g^{2}}\cdot\frac{B}{4}+\frac{\Delta^{2}}{g^{2}}\cdot
B\cdot
b/4\mathop{=}\limits^{(a)}\frac{1}{g^{2}}\cdot\frac{B}{4}+\frac{1}{g^{2}}\cdot
B\cdot b/4=O\left(\frac{(\log(d^{2}/\delta))^{2}}{\varepsilon^{2}}\right).$

where (a) holds by the fact that in $\mathcal{P}_{\text{Vec}}$, $\Delta=1$.
Thus, this implies that
$\widetilde{\sigma}_{1}^{2},\widetilde{\sigma}_{2}^{2}$ in Assumption A.3 are
satisfied with
$O\left(M\frac{(\log(d^{2}/\delta))^{2}}{\varepsilon^{2}}\right)$, hence
$\sigma$ in Lemma A.4 is given by
$\sigma=O\left(\sqrt{T/B}\frac{\log(d^{2}/\delta)}{\varepsilon}\right)$, which
leads to the following regret bound

$\displaystyle
R(T)=\tilde{O}\left(dB+\frac{(\log(d^{2}/\delta))^{1/2}}{\sqrt{\varepsilon}}d^{3/4}B^{-1/4}T^{3/4}\right),$

Hence, we finish the proof. ∎

###### Proof of Corollary C.2.

The regret bound simply follows from a balanced choice of $B$ in Theorem C.1.
As before, JDP follows from SDP and Billboard lemma. To show the LDP
guarantee, one way is to use DP property of Binomial mechanism and the refined
advanced composition in [CJMP21] across dimensions (cf. Lemma 3.3 in
[CJMP21]). However, there is a simple way to achieve this by noting that when
$B=1$, the SDP guarantee of $\mathcal{P}_{\text{Vec}}$ also implies LDP
guarantee since now the shuffle output is the same as the output at each local
randomizer101010Here, we can assume that each local randomizer already
randomly orders the $g+b$ bits before they are sent out.. Thus, by comparing
the values of $b$ for a general $B$ and the case when $B=1$, we can see that
$\varepsilon_{0}=\varepsilon\sqrt{B}$ and $\delta_{0}=\delta$, i.e., an
implicit privacy amplification by $\sqrt{B}$. Note that, this simple way might
lead to a larger term in $\delta$. A careful analysis via Binomial mechanism
and the (refined) advanced composition could yield something like
$\varepsilon_{0}=\varepsilon\sqrt{B}/\sqrt{\log(d^{2}/\delta)}$ and
$\delta_{0}=\delta/d^{2}$, where $d^{2}$ comes from the $d\times d$ matrix in
the computation. Here we choose the simple way to avoid additional complexity
for clarity. ∎

###### Proof of Corollary C.3.

The LDP guarantee follows from the same trick as in the proof of Corollary C.2
which helps to avoid Binomial mechanism and advance composition over
dimensions. To establish the regret bound, we can compare the values of $b$ in
Corollary C.3 and the one in Theorem C.1. In particular, we can plug
$\varepsilon=\frac{\varepsilon_{0}}{\sqrt{B}}$ and $\delta=\delta_{0}$ into
the regret bound in Theorem C.1. Then, with a balanced choice of $B$, we
obtain the required regret. The SDP guarantee also follows from Theorem C.1
with $\varepsilon=\frac{\varepsilon_{0}}{\sqrt{B}}$ and $\delta=\delta_{0}$.
Finally, as in the proof of Corollary B.2, the JDP guarantee follows from SDP
guarantee and Billboard lemma. ∎

##  Appendix D Joint Differenital Privacy

In this section, we will give formal DP definitions in the central model for
linear contextual bandits. In particular, we first present the standard
(event-level) definition which assumes all users are unique and then
generalize it to (user-level) definition that allows for returning users. To
this end, we first give the following general DP definition.

######  Definition D.1 (General DP).

A randomized mechanism $\mathcal{M}:\mathcal{D}\to\mathcal{R}$ satisfies
$(\varepsilon,\delta)$-differential privacy if for any two adjacent datasets
$X,X^{\prime}\in\mathcal{D}$ and for any measurable subsets of outputs
$\mathcal{Y}\subseteq\mathcal{R}$ it holds that

$\displaystyle\mathbb{P}\left[{\mathcal{M}(X)\in\mathcal{Y}}\right]\leq\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}(X^{\prime})\in\mathcal{Y}}\right]+\delta.$

######  Remark D.2.

All the DP definitions in our main paper can be viewed as a particular
instantiation of Definition D.1 in terms of adjacent relation between two
datasets and the corresponding output sequences.

A straightforward adaptation of Definition D.1 to linear contextual bandits in
the central model is to consider the sequence of $T$ unique users as the
dataset, denoted by $U_{T}:=\\{u_{1},\ldots,u_{T}\\}\in\mathcal{U}^{T}$, and
the corresponding prescribed actions as the output sequence, denoted by
$\mathcal{M}(U_{T}):=\\{a_{1},\ldots,a_{t}\\}\in\mathcal{A}^{T}$. This is the
central trust model because the learning agent in the protocol can have direct
access to users’ sensitive information, but all the prescribed actions via the
deployed algorithm are indistinguishable on two neighboring user sequences.
Unfortunately, it is not hard to see that this is in conflict with the goal of
personalization of linear contextual bandits, which essentially requires the
algorithm to prescribe different actions to different users according to their
contexts. Indeed, as shown in [SS18], any learning protocol that satisfy the
above notion of privacy protection has to incur a linear regret. Hence, to
obtain a non-trivial utility-privacy trade-off, we need to relax DP to the
notion called _joint differential privacy_ (JDP) [KPRU14] in the central
model, which requires that simultaneously for any user $u_{t}\in U_{T}$, the
joint distribution of the actions recommended to all users other than $u_{t}$
be differentially private in the type of the user $u_{t}$. It weakens the
classic DP notion only in that the action suggested specifically to $u_{t}$
may be sensitive in her type (i.e., context and reward
responses111111Technically speaking, the type of the user is identified by the
reward response she would give to all possible actions recommended based on
her context information.), as required by personalization. However, JDP is
still a very strong definition since it protects $u_{t}$ from any arbitrary
collusion of other users against her, so long as she does not herself reveal
the action suggested to her. Formally, we let
$\mathcal{M}_{-t}(U_{T}):=\mathcal{M}(U_{T})\setminus\\{a_{t}\\}$ to denote
all the actions prescribed by the deployed algorithm excluding the one
recommended to $u_{t}$ and based on it we have the definition of JDP as
follows.

######  Definition D.3 (Joint Differential Privacy (JDP)).

A learning process of linear contextual bandits is
$(\varepsilon,\delta)$-joint differentially private if its deployed algorithm
$\mathcal{M}:\mathcal{U}^{T}\to\mathcal{A}^{T}$ satisfies that for all
$t\in[T]$, for all neighboring user sequences
$U_{T},U_{T}^{\prime}\in\mathcal{U}^{T}$ differing only on the $t$-th user and
for all set of actions $\mathcal{A}_{-t}\subseteq\mathcal{A}^{T-1}$ given to
all but the $t$-th user,

$\displaystyle\mathbb{P}\left[{\mathcal{M}_{-t}(U_{T})\in\mathcal{A}_{-t}}\right]\leq\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}_{-t}(U_{T}^{\prime})\in\mathcal{A}_{-t}}\right]+\delta.$

The above JDP definition assumes that all the $T$ users are unique, which is
the standard event-level DP considered in existing similar works [SS18,
VBKW20, CZ21]. That is, since each user only contributes one event in the
total $T$ rounds, two user sequences $U_{T}$ and $U^{\prime}_{T}$ are said to
be adjacent if they only differ at one round $t\in[T]$.

However, a more practical situation is that one user could contribute her data
at multiple rounds, i.e., returning users. This motivates us to consider a
user-level JDP, in which two user sequences $U_{T}$ and $U^{\prime}_{T}$ are
adjacent if one replaces all the data associated with user $u$ to $u^{\prime}$
in $U_{T}$ results in $U^{\prime}_{T}$. In this case, changing one user in the
sequence could affect the data at multiple rounds. Accordingly, the output
sequences need to remove all the actions at these rounds to avoid the conflict
with personalization. Following the notations in [DNPR10], we say $U_{T}$ and
$U^{\prime}_{T}$ are neighboring sequences if there exist $u,u^{\prime}$ such
that if one replace some of $u$ in $U_{T}$, the resultant sequence is
$U^{\prime}_{T}$. Formally, $U_{T},U^{\prime}_{T}$ are neighboring with
neighboring indices $\mathcal{I}$, if there exist $u,u^{\prime}\in\mathcal{U}$
and index set $\mathcal{I}\subseteq[T]$ such that $U_{T}|_{\mathcal{I}:u\to
u^{\prime}}=U^{\prime}_{T}$, in which $U_{T}|_{\mathcal{I}:u\to u^{\prime}}$
means replacing $u$ by $u^{\prime}$ in $U_{T}$ at all indices in
$\mathcal{I}$. Meanwhile, we let
$\mathcal{M}_{-\mathcal{I}}(U_{T}):=\mathcal{M}(U_{T})\setminus
a_{\mathcal{I}}$, where $a_{\mathcal{I}}$ is the set of actions at indices in
$\mathcal{I}$. With these notations, we have the following formal definition.

######  Definition D.4 (User-level JDP).

A learning process of linear contextual bandits is
$(\varepsilon,\delta)$-joint differentially private if its deployed algorithm
$\mathcal{M}:\mathcal{U}^{T}\to\mathcal{A}^{T}$ satisfies that for all
neighboring user sequences $U_{T},U_{T}^{\prime}\in\mathcal{U}^{T}$ with
neighboring indices given by $\mathcal{I}$, and for all set of actions
$\mathcal{A}_{-\mathcal{I}}\subseteq\mathcal{A}^{T-|\mathcal{I}|}$,

$\displaystyle\mathbb{P}\left[{\mathcal{M}_{-\mathcal{I}}(U_{T})\in\mathcal{A}_{-\mathcal{I}}}\right]\leq\exp(\varepsilon)\mathbb{P}\left[{\mathcal{M}_{-\mathcal{I}}(U_{T}^{\prime})\in\mathcal{A}_{-\mathcal{I}}}\right]+\delta.$

######  Remark D.5.

A straightforward way to achieve user-level JDP via event-level JDP is to use
group privacy property of DP [DR+14b, VBKW20]. In particular, suppose a
mechanism is $(\varepsilon,\delta)$-JDP (event-level), then it is
$(k\varepsilon,ke^{(k-1)\varepsilon}\delta)$-JDP (user-level) if each user
contributes at most $k$ rounds. This black-box approach leads to a large
increase in $\delta$. We will show that a careful and direct analysis can
improve this part while the linear increase in $\varepsilon$ is unchanged.
This makes sense since the sensitivity now increases by a factor of $k$.

##  Appendix E Regret and Privacy Analysis Under Returning Users

We consider the following returning users case.

######  Assumption E.1 (Returning Users).

Fix a batch size $B$, any particular user can potentially participates in
_all_ $M=T/B$ batches, but within each batch $m\in[M]$, she only contributes
once.

Under the above assumption, our previous SDP guarantee from one-round SDP
protocol is no longer true. Instead, we now need to guarantee that outputs of
all the batches together have a total privacy loss of $(\varepsilon,\delta)$,
since all of them may reveal the sensitive information of a given user if she
participates in all the batches, i.e., worst-case scenario. To this end, we
resort to advanced composition theorem [DR+14b], which is restated as follows
for an easy reference.

######  Theorem E.2 (Advanced composition).

Given target privacy parameters $\varepsilon^{\prime}\in(0,1)$ and
$\delta^{\prime}>0$, to ensure
$(\varepsilon^{\prime},k\delta+\delta^{\prime})$-DP for the composition of $k$
(adaptive) mechanisms, it suffices that each mechanism is
$(\varepsilon,\delta)$-DP with
$\varepsilon=\frac{\varepsilon^{\prime}}{2\sqrt{2k\log(1/\delta^{\prime})}}$.

###  E.1 LDP Amplification Protocol

######  Theorem E.3 (Formal statement of (i) in Theorem 4.2).

Let Assumption 3.1 and Assumption E.1 hold. For any
$\varepsilon\in[0,\frac{2}{B}\log(2/\delta)\sqrt{2T}]$, $\delta\in(0,1]$ and
$B\in[T]$, let
$\sigma_{1}=\sigma_{2}=\frac{16\log(2/\delta)\sqrt{T(\log(5T/\delta))}}{\varepsilon{B}}$.
Then, Algorithm 1 instantiated using $\mathcal{P}_{\text{Amp}}$ is
$O(\varepsilon,\delta)$-SDP. Furthermore, for any $\alpha\in(0,1]$, setting
$\lambda=\Theta(\sqrt{T}\sigma_{1}(\sqrt{d}+\sqrt{\log(T/B\alpha)})$, it has
the following regret

$\displaystyle\text{Reg}(T)={O}\left(\frac{dT}{M}\log
T+\sqrt{\frac{MT}{\varepsilon}}d^{3/4}\log^{1/4}(T/\delta)\log^{1/2}(2/\delta)\log
T\log(T/\alpha)\right).$

The following corollary says that if the batch schedule also depends on
privacy parameters, one can improve the dependence on $\varepsilon$, i.e.,
from $\varepsilon^{-1/2}$ to $\varepsilon^{-1/3}$.

######  Corollary E.4 (Utility-targeted).

Under the same assumption in Theorem E.3 and
$B=O(d^{-1/6}\varepsilon^{-1/3}T^{2/3}(\log(T/\delta))^{1/2})$, Algorithm 1
instantiated using $\mathcal{P}_{\text{Amp}}$ achieves
$O(\varepsilon,\delta)$-SDP with regret

$\displaystyle
R(T)=\tilde{O}\left(d^{5/6}T^{2/3}\varepsilon^{-1/3}\left(\log(T/\delta)\right)^{1/2}\right).$

###### Proof of Theorem E.3.

First, by advanced composition in Theorem E.2, if we let each batch’s privacy
parameters be $\varepsilon_{m}=\frac{\varepsilon}{2\sqrt{2M\log(2/\delta)}}$
and $\delta_{m}=\delta/(2M)$, then final privacy guarantee is
$(\varepsilon,\delta)$-DP. Thus, we only need to replace $\varepsilon$ by
$\varepsilon_{m}$ and $\delta$ by $\delta_{m}$ in Theorem B.1 ∎

###  E.2 Vector Summation Protocol

######  Theorem E.5 (Formal statement of (ii) in Theorem 4.2).

Let Assumption 3.1 and Assumption E.1 hold. Then, for any $\varepsilon\leq
15$, $\delta\in(0,1/2)$ and $B\in[T]$, let

$\displaystyle g=\max\\{2\sqrt{B},d,4\\},\quad
b=\frac{10^{7}\cdot\log(2/\delta)\cdot g^{2}\cdot
T\cdot\left(\log\left(\frac{8\cdot
T(d^{2}+1)}{B\delta}\right)\right)^{2}}{\varepsilon^{2}B^{2}},\quad p=1/4.$

Algorithm 1 instantiated using $\mathcal{P}_{\text{Vec}}$ is
$(\varepsilon,\delta)$-SDP. Furthermore, for any $\alpha\in(0,1]$, setting

$\displaystyle\lambda=\Theta\left(\frac{T\sqrt{\log(2/\delta)}\log(d^{2}T/(B\delta))}{B}\left(\sqrt{d}+\sqrt{\log(T/(B\alpha))}\right)\right),$

then it has the regret bound

$\displaystyle\text{Reg}(T)\\!=\\!{O}\left(\frac{dT}{M}\log
T\\!+\\!\sqrt{\frac{MT}{\varepsilon}}d^{3/4}\log^{3/4}(d^{2}M/\delta)\log
T\log(T/\alpha)\right).$

######  Corollary E.6 (Utility-targeted).

Under the same assumption in Theorem E.5,
$B=O(d^{-1/6}\varepsilon^{-1/3}T^{2/3}(\log(Td^{2}/\delta))^{1/2})$, Algorithm
1 instantiated using $\mathcal{P}_{\text{Vec}}$ achieves
$(\varepsilon,\delta)$-SDP with regret

$\displaystyle
R(T)=\widetilde{O}\left(d^{5/6}T^{2/3}\varepsilon^{-1/3}\left(\log(d^{2}T/\delta)\right)^{1/2}\right).$

###### Proof of Theorem E.5.

First, by advanced composition in Theorem E.2, if we let each batch’s privacy
parameters be $\varepsilon_{m}=\frac{\varepsilon}{2\sqrt{2M\log(2/\delta)}}$
and $\delta_{m}=\delta/(2M)$, then final privacy guarantee is
$(\varepsilon,\delta)$-DP. Thus, we only need to replace $\varepsilon$ by
$\varepsilon_{m}$ and $\delta$ by $\delta_{m}$ in Theorem C.1 ∎

###  E.3 JDP under Returning Users

As mentioned before, existing algorithm with JDP guarantee assumes _unique_
users, i.e., event-level JDP given by Definition D.3. To handle returning
users, we need to consider user-level JDP given by Definition D.4. One
straightforward way is to resort to group privacy [DR+14b]. That is, if any
user appears at most $M_{0}$ rounds in the process, the original
$(\varepsilon,\delta)$-JDP algorithm proposed in [SS18] now achieves
$(M_{0}\varepsilon,M_{0}\exp((M_{0}-1)\varepsilon)\delta)$-JDP (user-level).
However, this black-box will incur a large loss in the $\delta$ term. To
overcome this, we note that a simple modification of the added noise in the
original algorithm in [SS18] will work. In particular, we scale up the noise
variance by a multiplicative factor of $M_{0}^{2}$, if any user participates
in at most $M_{0}$ rounds. This follows from the fact that flipping one user
now would change the $\ell_{2}$ sensitivity of the expanded binary-tree nodes
from $O(\sqrt{\log T})$ to $O(M_{0}\sqrt{\log T})$. Then, utilizing our
derived generic regret bound in Lemma A.4, yields the following result.

######  Proposition E.7 (Restatement of Proposition 4.3).

If any user participates in at most $M_{0}$ rounds, the algorithm in [SS18],
with the above modification to handle user-level privacy, achieves the high-
probability regret bound

$\displaystyle\text{Reg}(T)=\widetilde{O}\left(d\sqrt{T}+\sqrt{\frac{M_{0}T}{\varepsilon}}d^{3/4}\log^{1/4}(1/\delta)\right).$

###### Proof.

The key idea behind the regret analysis in the central model for linear
contextual bandits in [SS18] is to utilize the following two properties of the
so-called tree-based mechanism (or binary counting mechanism) [CSS10]: (i)
change of each leaf-node (corresponding to a user’s data) only incurs the
change of $l_{2}$-sensitivity of the expanded binary-tree by $O(\sqrt{\log
T})$; (ii) for any $t\in[T]$, the summation of data from time $1$ to $t$ only
involves at most $O({\log T)}$ tree nodes. Property (i) is used to compute the
added noise at each node to guarantee privacy while property (ii) is used to
compute the total noise in the private sum when bounding the regret. Now, in
the case of returning users, if we flip one user’s data, it will change the
$l_{2}$-sensitivity of the expanded binary-tree by $O(M_{0}\sqrt{\log T})$,
i.e., an additional $M_{0}$ factor in the sensitivity, which leads to the
additional $M_{0}^{2}$ factor in the added noise. Property (ii) is the same as
before, i.e., total number of noise is at most $O(\log T)$. Finally, by Lemma
A.4, we have the result. ∎

##  Appendix F Batched Algorithms for Local and Central Models

To start with, for the batched algorithm in the local model, one can simply
replace the shuffler in Algorithm 1 by an identity mapping while using the
same local randomizer as in [ZCH+20] (i.e., Gaussian mechanism). We call this
algorithm Batched-Local-LinUCB. Thanks to Lemma A.4, we have the following
privacy and regret guarantees.

######  Proposition F.1.

Let Assumption 3.1 hold. Fix any $\varepsilon_{0}\in[0,1]$,
$\delta_{0}\in(0,1]$ and $\alpha\in[0,1]$, let
$\sigma_{1}=\sigma_{2}=\frac{4\sqrt{2\log(2.5/\delta_{0})}}{\varepsilon_{0}}$.
Then, for all $B\in[T]$, Bathed-Local-LinUCB is
$(\varepsilon_{0},\delta_{0})$-LDP and with probability at least $1-\alpha$

$\displaystyle\operatorname{Reg}(T)=\tilde{O}\left(dB+T^{3/4}d^{3/4}\frac{(\log(1/\delta))^{1/4}}{\sqrt{\varepsilon}}\log(T/\alpha)\right).$

######  Remark F.2.

The above theorem indicates that it suffices to update every
$B=\tilde{O}(T^{3/4})$ to ensure the same privacy and regret guarantees as in
the sequential case.

For the batched algorithm in the central model, we can make the following
simple modification over the sequential one in [SS18], which relies on the
seminal tree-based algorithm [CSS10] at the central server (analyzer) to
balance between privacy and regret. In the batched case, instead of updating
the binary-tree nodes after every round, the server updates them only after
each batch by treating the the sum of the statistics (i.e., vectors or
matrices) within the batch as a single new observation. We call this algorithm
_Batched-Central-LinUCB_. With this modification and Lemma A.4, we have the
following privacy and regret guarantees.

######  Proposition F.3.

Let Assumption 3.1 hold. Fix any $\varepsilon\in[0,1]$, $\delta\in(0,1]$ and
$\alpha\in[0,1]$. Then, for all $B\in[T]$, Bathed-Central-LinUCB is
$(\varepsilon,\delta)$-JDP and with probability at least $1-\alpha$

$\displaystyle\operatorname{Reg}(T)=\tilde{O}\left(dB+\sqrt{T}d^{3/4}\frac{(\log(1/\delta))^{1/4}}{\sqrt{\varepsilon}}\log(T/\alpha)\right).$

######  Remark F.4.

The above theorem indicates that it suffices to update every
$B=\tilde{O}(\sqrt{T})$ to attain the same privacy-regret trade-off as in the
sequential case.

##  Appendix G Additional Experimental Results

(a) $d=10$

(b) $d=15$

Figure 2: Comparison of cumulative regret for LinUCB (non-private), LinUCB-JDP
(central model), LinUCB-SDP (shuffle model) and LinUCB-LDP (local model) with
privacy level $\varepsilon=1$ for varying feature dimension $d=10$ (a) and
$d=15$ (b). In all cases, regret of LinUCB-SDP lies perfectly in between
LinUCB-JDP and LinUCB-LDP, achieving finer regret-privacy trade-off.