Cascading Bandit under Differential Privacy

This paper studies differential privacy (DP) and local differential privacy (LDP) in cascading bandits. Under DP, we propose an algorithm which guarantees ε-indistinguishability and a regret of O((fraclog Tε)1+xi) for an arbitrarily small xi. This is a significant improvement from the previous work of O(fraclog3 Tε) regret. Under (ε,δ)-LDP, we relax the K2 dependence through the tradeoff between privacy budget ε and error probability δ, and obtain a regret of O(fracKlog (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.