Cascading Bandit under Differential Privacy

2021/05/24 by Wang, Kun, Dong, Jing, Wang, Baoxiang +2
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2105.11126

Abstract

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+ξ) for an arbitrarily small ξ. This is a significant improvement from the previous work of O(\fraclog³ Tε) regret. Under (ε,δ)-LDP, we relax the K² dependence through the tradeoff between privacy budget ε and error probability δ, and obtain a regret of O((Klog (1/δ) log T)/(ε²)), 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.

Related

• When Privacy Meets Partial Information: A Refined Analysis of\n Differentially Private Bandits
• Differential Privacy for Multi-armed Bandits: What Is It and What Is Its\n Cost?
• Multi-Armed Bandits with Local Differential Privacy
• (Locally) Differentially Private Combinatorial Semi-Bandits
• Optimal Regret of Bernoulli Bandits under Global Differential Privacy