Local Differential Privacy for Regret Minimization in Reinforcement Learning

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