Cascading Bandit under Differential Privacy
This work addresses privacy concerns in online recommendation systems for users, though it is incremental by building on prior cascading bandit models.
The paper tackles the problem of ensuring differential privacy in cascading bandits, achieving a regret of O((log T/ε)^(1+ξ)) under DP, improving from O(log^3 T/ε), and O(K log(1/δ) log T/ε^2) under LDP, with lower bounds and experimental validation.
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.