Shuffle Private Linear Contextual Bandits
  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 user side. However,
there remains a fundamental gap in the utility achieved by learning algorithms
under these two privacy models, e.g., $\tilde{O}(\sqrt{T})$ regret in the
central model as compared to $\tilde{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 $\tilde{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
$\tilde{O}(T^{2/3})$, which matches that the central model could achieve in
this case.
