Cascading Bandit Under Differential Privacy

Abstract

This paper studies differential privacy (DP) and local differential privacy (LDP) in cascading bandits. Under DP, we propose a UCB-based algorithm which guarantees ϵ-indistinguishability and a regret of $\mathcal{O}\left( {{{\left( {\frac{{\log T}}{ \in }} \right)}^{1 + \xi }}} \right)$ for an arbitrarily small ξ. This result significantly improves $O\left( {\frac{{{{\log }^3}T}}{ \in }} \right)$ in the previous work. Under (ϵ, δ)-LDP, we relax the K <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> dependence through the tradeoff between privacy budget ϵ and error probability δ, and obtain a regret of ${\text{ }}\mathcal{O}{\text{ }}\left( {\frac{{K\log (1/\delta )\log T}}{{{ \in ^2}}}} \right)$, where K is the size of the arm subset. This result holds for both Gaussian mechanism and Laplace mechanism by analyses on the composition. Extensive experiments corroborate our theoretic findings.