mlsanityData to 7 Oct 2026

Private Reinforcement Learning with PAC and Regret Guarantees

arXiv 2009.09052 ↗First posted 18 Sep 2020cs.LG cs.CR stat.MLcited by 51

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 12; 2023: 6; 2024: 9; 2025: 6; 2026: 6.

51 papers.

Sort:

By area:

  1. 2021Large Scale Private Learning via Low-rank Reparametrizationcited by 87
  2. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  3. 2022Shuffle Private Linear Contextual Banditscited by 27
  4. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  5. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  6. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  7. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  8. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  9. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  10. 2023Reinforcement Unlearningcited by 16
  11. 2024MAD-TD: Model-Augmented Data stabilizes High Update Ratio RLcited by 16
  12. 2021Deceptive Reinforcement Learning for Privacy-Preserving Planningcited by 14
38 more
  1. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  2. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  3. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  4. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  5. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  6. 2022Doubly Fair Dynamic Pricingcited by 8
  7. 2021Adaptive Control of Differentially Private Linear Quadratic Systemscited by 7
  8. 2022Differentially Private Temporal Difference Learning with Stochastic Nonconvex-Strongly-Concave Optimizationcited by 7
  9. 2022New Challenges in Reinforcement Learning: A Survey of Security and Privacycited by 7
  10. 2021How Private Is Your RL Policy? An Inverse RL Based Analysis Frameworkcited by 5
  11. 2023Multi-Agent Reinforcement Learning: Methods, Applications, Visionary Prospects, and Challengescited by 5
  12. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  13. 2023Privacy Risks in Reinforcement Learning for Household Robotscited by 4
  14. 2021Membership Inference Attacks Against Temporally Correlated Data in Deep Reinforcement Learningcited by 3
  15. 2025Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learningcited by 3
  16. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  17. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  18. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  19. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  20. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  21. 2025KL-regularization Itself is Differentially Private in Bandits and RLHFcited by 2
  22. 2021Reinforcement Learning on Encrypted Datacited by 1
  23. 2022Privacy-Preserving Reinforcement Learning Beyond Expectationcited by 1
  24. 2023Privacy-Engineered Value Decomposition Networks for Cooperative Multi-Agent Reinforcement Learningcited by 1
  25. 2024Differentially Private Deep Model-Based Reinforcement Learningcited by 1
  26. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  27. 2024FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Banditscited by 1
  28. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  29. 2024Preserving the Privacy of Reward Functions in MDPs through Deceptioncited by 1
  30. 2024Noise is All You Need: Private Second-Order Convergence of Noisy SGDcited by 1
  31. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  32. 2026Exact Unlearning in Reinforcement Learningcited by 1
  33. 2024Preserving Expert-Level Privacy in Offline Reinforcement Learningcited by 0
  34. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0
  35. 2026Barriers to Counterfactual Credit Attribution for Autoregressive Modelscited by 0
  36. 2026Privacy Preserving Reinforcement Learning with One-Sided Feedbackcited by 0
  37. 2026Private and Stable Test-Time Adaptation with Differential Privacycited by 0
  38. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0

50 most cited of 51 All 51 (JSON)