This paper studies \emph{ differential privacy (DP)} and \emph{ local differential privacy (LDP)} in cascading bandits. Under DP, we propose an algorithm which guarantees $\epsilon$-indistinguishability and a regret of $\mathcal{ O}((\frac{ \log T}{ \epsilon})^{ 1+\xi})$ for an arbitrarily small $\xi$. This is a significant improvement from the previous work of $\mathcal{ O}(\frac{ \log^3 T}{ \epsilon})$ regret. Under ($\epsilon$,$\delta$)-LDP, we relax the $K^2$ dependence through the tradeoff between privacy budget $\epsilon$ and error probability $\delta$, and obtain a regret of $\mathcal{ O}(\frac{ K\log (1/\delta) \log T}{ \epsilon^2})$, where $K$ is the size of the arm subset. This result holds for both Gaussian mechanism and Laplace mechanism by analyses on the composition. Our results extend to combinatorial semi-bandit. We show respective lower bounds for DP and LDP cascading bandits. Extensive experiments corroborate our theoretic findings.
Categories: cs.LG