Corrupt Bandits for Preserving Local Privacy

Abstract

We study a variant of the stochastic multi-armed bandit (MAB) problem in which the rewards are corrupted. In this framework, motivated by privacy preservation in online recommender systems, the goal is to maximize the sum of the (unobserved) rewards, based on the observation of transformation of these rewards through a stochastic corruption process with known parameters. We provide a lower bound on the expected regret of any bandit algorithm in this corrupted setting. We devise a frequentist algorithm, KLUCB-CF, and a Bayesian algorithm, TS-CF and give upper bounds on their regret. We also provide the appropriate corruption parameters to guarantee a desired level of local privacy and analyze how this impacts the regret. Finally, we present some experimental results that confirm our analysis.

Cited by in corpus (9)

• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Multi-Armed Bandits with Local Differential Privacy
• Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• (Locally) Differentially Private Combinatorial Semi-Bandits
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption
• Combinatorial Bandits under Strategic Manipulations
• Privacy-Preserving Bandits