Cascading Bandit under Differential Privacy

This paper studies \emph{differential privacy (DP)} and \emph{local differential privacy (LDP)} in cascading bandits. Under DP, we propose an algorithm which guarantees $ε$-indistinguishability and a regret of $\mathcal{O}((\frac{\log T}ε)^{1+ξ})$ for an arbitrarily small $ξ$. This is a significant improvement from the previous work of $\mathcal{O}(\frac{\log^3 T}ε)$ regret. Under ($ε$,$δ$)-LDP, we relax the $K^2$ dependence through the tradeoff between privacy budget $ε$ and error probability $δ$, and obtain a regret of $\mathcal{O}(\frac{K\log (1/δ) \log T}{ε^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.