Online Decision Making with Local Differential Privacy

Abstract

Contextual bandit algorithms are useful in personalized online decision-making. However, many applications, such as personalized medicine and online advertising, require the utilization of user-specific information for effective learning while maintaining user privacy due to privacy concerns. This motivates the introduction of local differential privacy (LDP), a stringent notion of privacy, to contextual bandits. In this paper, we design LDP algorithms for stochastic generalized linear bandits to achieve the same regret bound as in non-privacy settings. Our main idea is to develop a stochastic gradient-based estimator and an update mechanism to ensure LDP. We then exploit the flexibility of stochastic gradient descent (SGD), whose theoretical guarantee for bandit problems is rarely explored, to address generalized linear bandits. We further conduct experiments using both simulated and real-world datasets to demonstrate the consistently superior performance of our algorithms under LDP constraints, with reasonably small LDP parameters (ε, δ) to ensure strong privacy protection.