# Near-Optimal Differentially Private Reinforcement Learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 59 references that are in the map.
- First posted on arXiv 9 Dec 2022.

## Builds on (most cited first, 30 of 36)

- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?](https://mlsanity.com/paper/2012.06421/) (2020)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Continuous State-Space Models for Optimal Sepsis Treatment - a Deep Reinforcement Learning Approach](https://mlsanity.com/paper/1705.08422/) (2017)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Private Reinforcement Learning with PAC and Regret Guarantees](https://mlsanity.com/paper/2009.09052/) (2020)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2206.11489/) (2022)
- [Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?](https://mlsanity.com/paper/1905.12298/) (2019)
- [Private Matchings and Allocations](https://mlsanity.com/paper/1311.2828/) (2013)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Local Differential Privacy for Regret Minimization in Reinforcement Learning](https://mlsanity.com/paper/2010.07778/) (2020)
- [Logarithmic Regret in Feature-based Dynamic Pricing](https://mlsanity.com/paper/2102.10221/) (2021)
- [Differentially Private Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2201.07052/) (2022)
- [Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noise](https://mlsanity.com/paper/2201.11341/) (2022)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)

## Built on by (most cited first, 16 of 16)

- [Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes](https://mlsanity.com/paper/2406.06838/) (2024)
- [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)
- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignment](https://mlsanity.com/paper/2505.21395/) (2025)
- [On the Sample Complexity of Differentially Private Policy Optimization](https://mlsanity.com/paper/2510.21060/) (2025)
- [Differentially Private Deep Model-Based Reinforcement Learning](https://mlsanity.com/paper/2402.05525/) (2024)
- [Differentially Private Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2404.07559/) (2024)
- [Privacy Preserving Reinforcement Learning for Population Processes](https://mlsanity.com/paper/2406.17649/) (2024)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)
- [Exact Unlearning in Reinforcement Learning](https://mlsanity.com/paper/2606.04182/) (2026)
- [Preserving Expert-Level Privacy in Offline Reinforcement Learning](https://mlsanity.com/paper/2411.13598/) (2024)
- [Towards Optimal Differentially Private Regret Bounds in Linear MDPs](https://mlsanity.com/paper/2504.09339/) (2025)
- [Privacy Preserving Reinforcement Learning with One-Sided Feedback](https://mlsanity.com/paper/2605.18246/) (2026)
- [Randomized Least Squares Value Iteration itself is Joint Differentially Private](https://mlsanity.com/paper/2606.01952/) (2026)
- [ForgetMimic: Motion Unlearning for Reinforcement Learning Humanoid Control](https://mlsanity.com/paper/2609.28378/) (2026)

## Abstract (arXiv)

Motivated by personalized healthcare and other applications involving sensitive data, we study online exploration in reinforcement learning with differential privacy (DP) constraints. Existing work on this problem established that no-regret learning is possible under joint differential privacy (JDP) and local differential privacy (LDP) but did not provide an algorithm with optimal regret. We close this gap for the JDP case by designing an ε-JDP algorithm with a regret of widetildeO(√SAH2T+S2AH3/ε) which matches the information-theoretic lower bound of non-private learning for all choices of ε> S1.5A0.5 H2/√T. In the above, S, A denote the number of states and actions, H denotes the planning horizon, and T is the number of steps. To the best of our knowledge, this is the first private RL algorithm that achieves privacy for free asymptotically as Trightarrow ∞. Our techniques -- which could be of independent interest -- include privately releasing Bernstein-type exploration bonuses and an improved method for releasing visitation statistics. The same techniques also imply a slightly improved regret bound for the LDP case.