mlsanityData to 14 Oct 2026

Differentially Private Regret Minimization in Episodic Markov Decision Processes

arXiv 2112.10599 ↗First posted 20 Dec 2021cs.LG cs.CR math.PRcited by 23

Not on the map. Why?

Abstract (arXiv)

We study regret minimization in finite horizon tabular Markov decision processes (MDPs) under the constraints of differential privacy (DP). This is motivated by the widespread applications of reinforcement learning (RL) in real-world sequential decision making problems, where protecting users' sensitive and private information is becoming paramount. We consider two variants of DP -- joint DP (JDP), where a centralized agent is responsible for protecting users' sensitive data and local DP (LDP), where information needs to be protected directly on the user side. We first propose two general frameworks -- one for policy optimization and another for value iteration -- for designing private, optimistic RL algorithms. We then instantiate these frameworks with suitable privacy mechanisms to satisfy JDP and LDP requirements, and simultaneously obtain sublinear regret guarantees. The regret bounds show that under JDP, the cost of privacy is only a lower order additive term, while for a stronger privacy protection under LDP, the cost suffered is multiplicative. Finally, the regret bounds are obtained by a unified analysis, which, we believe, can be extended beyond tabular MDPs.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). Builds on 36 of its 71 references that are in the map. First posted on arXiv 20 Dec 2021.

Builds on

36 of 71 references.

References · 36

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2016Benchmarking Deep Reinforcement Learning for Continuous Controlcited by 371
  6. 2016Deep Reinforcement Learning for Dialogue Generationcited by 288
  7. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  8. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  9. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  10. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  11. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  12. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
24 more
  1. 2020Exploration-Exploitation in Constrained MDPscited by 149
  2. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  3. 2018Differentially Private Contextual Linear Banditscited by 82
  4. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  5. 2016Discrete Distribution Estimation under Local Privacycited by 59
  6. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 53
  7. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  8. 2015Algorithms for Differentially Private Multi-Armed Banditscited by 45
  9. 2017The Price of Differential Privacy For Online Learningcited by 45
  10. 2019Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policycited by 43
  11. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  12. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
  13. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  14. 2019On Online Learning in Kernelized Markov Decision Processescited by 35
  15. 2019Privacy-preserving Q-Learning with Functional Noise in Continuous State Spacescited by 30
  16. 2017Achieving Privacy in the Adversarial Multi-Armed Banditcited by 24
  17. 2013Private Matchings and Allocationscited by 23
  18. 2016Differentially Private Policy Evaluationcited by 19
  19. 2020Local Differential Privacy for Bayesian Optimizationcited by 19
  20. 2020(Locally) Differentially Private Combinatorial Semi-Banditscited by 14
  21. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  22. 2020Locally Private Distributed Reinforcement Learningcited by 9
  23. 2021Adaptive Control of Differentially Private Linear Quadratic Systemscited by 7
  24. 2019Locally Differentially Private Data Collection and Analysiscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 7; 2023: 5; 2024: 5; 2025: 4; 2026: 2.

23 papers.

Sort:

By area:

  1. 2022Shuffle Private Linear Contextual Banditscited by 27
  2. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  3. 2022Offline Reinforcement Learning with Differential Privacycited by 20
  4. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  5. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  6. 2022Doubly Fair Dynamic Pricingcited by 8
  7. 2022New Challenges in Reinforcement Learning: A Survey of Security and Privacycited by 7
  8. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6
  9. 2023Multi-Agent Reinforcement Learning: Methods, Applications, Visionary Prospects, and Challengescited by 5
  10. 2025Improved Bounds for Private and Robust Alignmentcited by 5
  11. 2023Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewardscited by 4
  12. 2025SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignmentcited by 3
11 more
  1. 2025On the Sample Complexity of Differentially Private Policy Optimizationcited by 3
  2. 2023Concurrent Shuffle Differential Privacy Under Continual Observationcited by 2
  3. 2024Differentially Private Deep Model-Based Reinforcement Learningcited by 1
  4. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  5. 2024Privacy Preserving Reinforcement Learning for Population Processescited by 1
  6. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  7. 2026Exact Unlearning in Reinforcement Learningcited by 1
  8. 2023Local Differential Privacy for Sequential Decision Making in a Changing Environmentcited by 0
  9. 2024Preserving Expert-Level Privacy in Offline Reinforcement Learningcited by 0
  10. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0
  11. 2026Randomized Least Squares Value Iteration itself is Joint Differentially Privatecited by 0