Local Differential Privacy for Regret Minimization in Reinforcement Learning

Abstract

Reinforcement learning algorithms are widely used in domains where it is desirable to provide a personalized service. In these domains it is common that user data contains sensitive information that needs to be protected from third parties. Motivated by this, we study privacy in the context of finite-horizon Markov Decision Processes (MDPs) by requiring information to be obfuscated on the user side. We formulate this notion of privacy for RL by leveraging the local differential privacy (LDP) framework. We establish a lower bound for regret minimization in finite-horizon MDPs with LDP guarantees which shows that guaranteeing privacy has a multiplicative effect on the regret. This result shows that while LDP is an appealing notion of privacy, it makes the learning problem significantly more complex. Finally, we present an optimistic algorithm that simultaneously satisfies $\epsilon$-LDP requirements, and achieves $\sqrt{K}/\epsilon$ regret in any finite-horizon MDP after $K$ episodes, matching the lower bound dependency on the number of episodes $K$.

References in corpus (19)

• Geo-Indistinguishability: Differential Privacy for Location-Based Systems
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Discrete Distribution Estimation under Local Privacy
• Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning
• Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates
• Differentially Private Contextual Linear Bandits
• Differentially-Private Federated Linear Bandits
• Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation
• Multi-Armed Bandits with Local Differential Privacy
• Differentially Private Summation with Multi-Message Shuffling
• Locally Private Distributed Reinforcement Learning
• Differentially Private Policy Evaluation
• Corrupt Bandits for Preserving Local Privacy
• Locally Differentially Private (Contextual) Bandits Learning
• An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule
• Improved Analysis of UCRL2 with Empirical Bernstein Inequality
• Privacy-Preserving Multi-Party Contextual Bandits
• Locally Differentially Private Data Collection and Analysis
• A bounded-noise mechanism for differential privacy

Cited by in corpus (1)

• adaPARL: Adaptive Privacy-Aware Reinforcement Learning for Sequential-Decision Making Human-in-the-Loop Systems