Local Differential Privacy for Regret Minimization in Reinforcement Learning

2020-10-15 · NeurIPS 2021 12 · Evrard Garcelon, Vianney Perchet, Ciara Pike-Burke, Matteo Pirotta

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 $\varepsilon$-LDP requirements, and achieves $\sqrt{K}/\varepsilon$ regret in any finite-horizon MDP after $K$ episodes, matching the lower bound dependency on the number of episodes $K$.

📄 PDF Abstract BibTeX arXiv:2010.07778

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Differentially Private Regret Minimization in Episodic Markov Decision Processes

2021-12-20 · Sayak Ray Chowdhury, Xingyu Zhou

We study regret minimization in finite horizon tabular Markov decision processes (MDPs) under the constraints of differential privacy (DP). This is motivated by the widespread applications of reinforcement learning (RL) …

Decision Making Reinforcement Learning (RL)Sequential Decision Making

Thompson Sampling under Bernoulli Rewards with Local Differential Privacy

2023-07-03 · Bo Jiang, Tianchi Zhao, Ming Li

This paper investigates the problem of regret minimization for multi-armed bandit (MAB) problems with local differential privacy (LDP) guarantee. Given a fixed privacy budget $\epsilon$, we consider three privatizing mec…

Thompson Sampling

Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards

2023-06-01 · Yulian Wu, Xingyu Zhou, Sayak Ray Chowdhury, Di Wang

In this paper, we study the problem of (finite horizon tabular) Markov decision processes (MDPs) with heavy-tailed rewards under the constraint of differential privacy (DP). Compared with the previous studies for private…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning

Multi-Armed Bandits with Local Differential Privacy

2020-07-06 · Wenbo Ren, Xingyu Zhou, Jia Liu, Ness B. Shroff

This paper investigates the problem of regret minimization for multi-armed bandit (MAB) problems with local differential privacy (LDP) guarantee. In stochastic bandit systems, the rewards may refer to the users' activiti…

Multi-Armed Bandits

Towards Optimal Differentially Private Regret Bounds in Linear MDPs

2025-04-12 · Sharan Sahu

We study regret minimization under privacy constraints in episodic inhomogeneous linear Markov Decision Processes (MDPs), motivated by the growing use of reinforcement learning (RL) in personalized decision-making system…

Offline RL Reinforcement Learning (RL)