Locally Differentially Private (Contextual) Bandits Learning

Abstract

We study locally differentially private (LDP) bandits learning in this paper. First, we propose simple black-box reduction frameworks that can solve a large family of context-free bandits learning problems with LDP guarantee. Based on our frameworks, we can improve previous best results for private bandits learning with one-point feedback, such as private Bandits Convex Optimization, and obtain the first result for Bandits Convex Optimization (BCO) with multi-point feedback under LDP. LDP guarantee and black-box nature make our frameworks more attractive in real applications compared with previous specifically designed and relatively weaker differentially private (DP) context-free bandits algorithms. Further, we extend our $(\epsilon ,\delta )$-LDP algorithm to Generalized Linear Bandits, which enjoys a sub-linear regret $\tilde{O}(T^{3/4}/\epsilon )$ and is conjectured to be nearly optimal. Note that given the existing $\Omega (T)$ lower bound for DP contextual linear bandits (Shariff & Sheffe, 2018), our result shows a fundamental difference between LDP and DP contextual bandits learning.

arXiv commentAccepted by NeurIPS 2020

References in corpus (11)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Differentially Private Contextual Linear Bandits
• The Price of Differential Privacy For Online Learning
• Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?
• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
• An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule

Cited by in corpus (6)

• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Local Differential Privacy for Bayesian Optimization
• Optimal Order Simple Regret for Gaussian Process Bandits
• Dynamic Global Sensitivity for Differentially Private Contextual Bandits
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles