Randomized Least Squares Value Iteration itself is Joint Differentially Private
This work addresses the need for privacy-preserving RL in sensitive domains by demonstrating that existing exploration mechanisms can double as privacy protection, potentially simplifying the design of private RL algorithms.
The paper shows that Randomized Least Squares Value Iteration (RLSVI), an algorithm designed for randomized exploration in RL, inherently provides joint differential privacy without additional noise injection. The authors prove a privacy bound for RLSVI in tabular MDPs, achieving a specific (ε,δ)-differential privacy guarantee.
As reinforcement learning (RL) increasingly applies to sensitive domains, such as health care and recommendation systems, privacy-preserving techniques have become essential to protect users' sensitive information. We investigate privacy-preserving RL under an episodic setting, focusing on algorithms based on randomized exploration, such as Randomized Least Squares Value Iteration (RLSVI). The overall goal is to study how randomized exploration interacts with the injected noise required by privacy mechanisms. In this work, we show a new privacy analysis that characterizes how the noise in RLSVI set for exploration simultaneously provides privacy protection. Specifically, we prove that RLSVI is $(\varepsilon(δ),δ)$-joint differentially private in tabular MDP as is with $\varepsilon(δ) = \frac{2AK}{H^2\log(2HSA)} + 2\sqrt{\frac{2AK\log(1/δ)}{H^2\log(2HSA)}}$, where $S$ and $A$ are the number of states and actions respectively, $H$ is the length of an episode and $K$ is the number of episodes.