  Bandits serve as the theoretical foundation of sequential learning and an
algorithmic foundation of modern recommender systems. However, recommender
systems often rely on user-sensitive data, making privacy a critical concern.
This paper contributes to the understanding of Differential Privacy (DP) in
bandits with a trusted centralised decision-maker, and especially the
implications of ensuring zero Concentrated Differential Privacy (zCDP). First,
we formalise and compare different adaptations of DP to bandits, depending on
the considered input and the interaction protocol. Then, we propose three
private algorithms, namely AdaC-UCB, AdaC-GOPE and AdaC-OFUL, for three bandit
settings, namely finite-armed bandits, linear bandits, and linear contextual
bandits. The three algorithms share a generic algorithmic blueprint, i.e. the
Gaussian mechanism and adaptive episodes, to ensure a good privacy-utility
trade-off. We analyse and upper bound the regret of these three algorithms. Our
analysis shows that in all of these settings, the prices of imposing zCDP are
(asymptotically) negligible in comparison with the regrets incurred oblivious
to privacy. Next, we complement our regret upper bounds with the first minimax
lower bounds on the regret of bandits with zCDP. To prove the lower bounds, we
elaborate a new proof technique based on couplings and optimal transport. We
conclude by experimentally validating our theoretical results for the three
different settings of bandits.
