# Private Reinforcement Learning with PAC and Regret Guarantees

arXiv: https://arxiv.org/abs/2009.09052 · HTML: https://mlsanity.com/paper/2009.09052/

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2020.

## Built on by (most cited first, 30 of 51)

- [Large Scale Private Learning via Low-rank Reparametrization](https://mlsanity.com/paper/2106.09352/) (2021)
- [When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Bandits](https://mlsanity.com/paper/2209.02570/) (2022)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits](https://mlsanity.com/paper/2106.02575/) (2021)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Differentially Private Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2201.07052/) (2022)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)
- [Privacy Amplification via Shuffling for Linear Contextual Bandits](https://mlsanity.com/paper/2112.06008/) (2021)
- [Reinforcement Unlearning](https://mlsanity.com/paper/2312.15910/) (2023)
- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [MAD-TD: Model-Augmented Data stabilizes High Update Ratio RL](https://mlsanity.com/paper/2410.08896/) (2024)
- [Deceptive Reinforcement Learning for Privacy-Preserving Planning](https://mlsanity.com/paper/2102.03022/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2110.10133/) (2021)
- [No-Regret Algorithms for Private Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2102.12467/) (2021)
- [Differentially Private Exploration in Reinforcement Learning with Linear Representation](https://mlsanity.com/paper/2112.01585/) (2021)
- [Improved Regret for Differentially Private Exploration in Linear MDP](https://mlsanity.com/paper/2202.01292/) (2022)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Adaptive Control of Differentially Private Linear Quadratic Systems](https://mlsanity.com/paper/2108.11563/) (2021)
- [Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimization](https://mlsanity.com/paper/2201.10447/) (2022)
- [New Challenges in Reinforcement Learning: A Survey of Security and Privacy](https://mlsanity.com/paper/2301.00188/) (2022)
- [How Private Is Your RL Policy? An Inverse RL Based Analysis Framework](https://mlsanity.com/paper/2112.05495/) (2021)
- [Multi-Agent Reinforcement Learning: Methods, Applications, Visionary Prospects, and Challenges](https://mlsanity.com/paper/2305.10091/) (2023)
- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Privacy Risks in Reinforcement Learning for Household Robots](https://mlsanity.com/paper/2306.09273/) (2023)
- [Membership Inference Attacks Against Temporally Correlated Data in Deep Reinforcement Learning](https://mlsanity.com/paper/2109.03975/) (2021)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learning](https://mlsanity.com/paper/2505.20621/) (2025)
- [SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignment](https://mlsanity.com/paper/2505.21395/) (2025)

## Abstract (arXiv)

Motivated by high-stakes decision-making domains like personalized medicine where user information is inherently sensitive, we design privacy preserving exploration policies for episodic reinforcement learning (RL). We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP)--a strong variant of differential privacy for settings where each user receives their own sets of output (e.g., policy recommendations). We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee. Our algorithm only pays for a moderate privacy cost on exploration: in comparison to the non-private bounds, the privacy parameter only appears in lower-order terms. Finally, we present lower bounds on sample complexity and regret for reinforcement learning subject to JDP.