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

Achraf Azize, Debabrota Basu

We study the problem of multi-armed bandits with $\epsilon$-global Differential Privacy (DP). First, we prove the minimax and problem-dependent regret lower bounds for stochastic and line…