Improved privacy guarantees reduce regret in tabular reinforcement learning
Improved regret bounds in tabular RL under local differential privacy
Machine Learning
Summary
This paper studies how to teach computers to make better decisions while keeping individual user data private. The authors look at a setting where the computer interacts with users who send back only private, noisy information. They provide new theoretical limits on how well the computer can learn from these private messages and propose algorithms that perform better than previous ones. These results help understand the trade-off between privacy and learning efficiency.
What this means in practice
- •For privacy engineers: Design privacy-preserving reinforcement learning systems with improved efficiency guarantees under local differential privacy.
- •For machine learning engineers: Develop algorithms for sequential decision-making tasks that maintain user data privacy with tighter performance bounds.
A theory result. No direct application yet.
Authors
Hugo Richard
Abstract
We study regret minimization for time-homogeneous episodic tabular reinforcement learning with $S$ states and $A$ actions under non-interactive $ε$-local differential privacy (LDP). In each episode $k \in [K]$, the decision-maker sends a policy to a user, the user executes the policy for $H$ steps, and sends an $ε$-locally differentially private message back to the decision-maker. When $H=1$, the problem reduces to an LDP contextual bandit with $S$ contexts, $A$ arms and horizon $K$. We prove that the minimax regret is $\min\bigg(K, \frac{ \sqrt{\max( S, \exp(ε) + 1) S A K (\exp(ε) + 1)}}{\exp(ε) - 1}\bigg)$, up to constants and a $\sqrt{\log(A)}$ factor. The upper bound is achieved by an adaptation of EXP3 and a unary encoding mechanism. When $H > 1$, and for small $ε$, we show a lower bound in $Ω(HS\frac{\sqrt{A K}}ε)$ and an upper bound in $\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}ε)$. The upper bound is achieved by an algorithm based on UCBVI and a unary encoding mechanism. For small $ε$, these bounds improve the previously known lower bound by a factor $\sqrt{S}$ and the previously known upper bound by a factor of $H \sqrt{A}$.