# Local Differential Privacy for Regret Minimization in Reinforcement Learning

December 05, 2021

## 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 $\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$.

#### AUTHORS

Written by

Evrard Garcelon

Vianney Perchet

Ciara Pike-Burke

Matteo Pirotta

Publisher

NeurIPS

Research Topics

Reinforcement Learning

### Related Publications

December 05, 2021

#### Hierarchical Skills for Efficient Exploration

Jonas Gehring, Gabriel Synnaeve, andreas krause, Nicolas Usunier

December 05, 2021

November 12, 2021

#### Bandits with Knapsacks beyond the Worst-Case Analysis

Karthik Abinav Sankararaman, Aleksandrs Slivkins

November 12, 2021

November 09, 2021

#### Interesting Object, Curious Agent: Learning Task-Agnostic Exploration

Simone Parisi, Victoria Dean, Deepak Pathak, Abhinav Gupta

November 09, 2021

November 02, 2021

#### Learning Search Space Partition for Path Planning

Kevin Yang, Tianjun Zhang, Chris Cummins, Brandon Cui, Benoit Steiner, Linnan Wang, Joseph E. Gonzalez, Dan Klein, Yuandong Tian

November 02, 2021

Tools

Research

Blog

People