mlsanityData to 7 Oct 2026

Near-Optimal Differentially Private Reinforcement Learning

arXiv 2212.04680 ↗First posted 9 Dec 2022cs.LG cs.AI cs.CRcited by 16

Not on the map. Why?

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.

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

Builds on

36 of 59 references.

References · 36

  1. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 847
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 224
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  8. 2021Reinforcement learning based recommender systems: A surveycited by 187
  9. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  10. 2021Practical and Private (Deep) Learning without Sampling or Shufflingcited by 169
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
24 more
  1. 2020When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?cited by 102
  2. 2018Differentially Private Contextual Linear Banditscited by 82
  3. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  5. 2017Continuous State-Space Models for Optimal Sepsis Treatment - a Deep Reinforcement Learning Approachcited by 68
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  7. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 52
  8. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  9. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  10. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  11. 2019Differential Privacy for Multi-armed Bandits: What Is It and What Is Its Cost?cited by 27
  12. 2013Private Matchings and Allocationscited by 23
  13. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  14. 2020Local Differential Privacy for Regret Minimization in Reinforcement Learningcited by 22
  15. 2021Logarithmic Regret in Feature-based Dynamic Pricingcited by 22
  16. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  17. 2022Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noisecited by 21
  18. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  19. 2021Privacy Amplification via Shuffling for Linear Contextual Banditscited by 17
  20. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  21. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  22. 2022Differentially Private Linear Sketches: Efficient Implementations and Applicationscited by 10
  23. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  24. 2022Doubly Fair Dynamic Pricingcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 7; 2025: 4; 2026: 4.

16 papers.

Sort:

By area:

  1. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  2. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  3. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  4. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
  5. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  6. 2025Improved Bounds for Private and Robust Alignmentcited by 3
  7. 2024Differentially Private Deep Model-Based Reinforcement Learningcited by 1
  8. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  9. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  10. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  11. 2026Exact Unlearning in Reinforcement Learningcited by 1
  12. 2024Preserving Expert-Level Privacy in Offline Reinforcement Learningcited by 0
4 more
  1. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0
  2. 2026Privacy Preserving Reinforcement Learning with One-Sided Feedbackcited by 0
  3. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0
  4. 2026ForgetMimic: Motion Unlearning for Reinforcement Learning Humanoid Controlcited by 0