Differentially Private Contextual Linear Bandits

Abstract

We study the contextual linear bandit problem, a version of the standard stochastic multi-armed bandit (MAB) problem where a learner sequentially selects actions to maximize a reward which depends also on a user provided per-round context. Though the context is chosen arbitrarily or adversarially, the reward is assumed to be a stochastic function of a feature vector that encodes the context and selected action. Our goal is to devise private learners for the contextual linear bandit problem. We first show that using the standard definition of differential privacy results in linear regret. So instead, we adopt the notion of joint differential privacy, where we assume that the action chosen on day $t$ is only revealed to user $t$ and thus needn't be kept private that day, only on following days. We give a general scheme converting the classic linear-UCB algorithm into a joint differentially private algorithm using the tree-based algorithm. We then apply either Gaussian noise or Wishart noise to achieve joint-differentially private algorithms and bound the resulting algorithms' regrets. In addition, we give the first lower bound on the additional regret any private algorithms for the MAB problem must incur.

21 pages, 5 figures; to appear in NIPS 2018

References in corpus (1)

• Private Approximations of the 2nd-Moment Matrix Using Existing Techniques in Linear Regression

Cited by in corpus (13)

• Differentially-Private Federated Linear Bandits
• Privacy-Preserving Dynamic Personalized Pricing with Demand Learning
• Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?
• Locally Differentially Private (Contextual) Bandits Learning
• Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• Dynamic Global Sensitivity for Differentially Private Contextual Bandits
• Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing
• Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes
• Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients
• Privacy-Preserving Bandits
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles