mlsanityData to 7 Oct 2026

Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards

arXiv 2306.01121 ↗First posted 1 Jun 2023cs.LG cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of (finite horizon tabular) Markov decision processes (MDPs) with heavy-tailed rewards under the constraint of differential privacy (DP). Compared with the previous studies for private reinforcement learning that typically assume rewards are sampled from some bounded or sub-Gaussian distributions to ensure DP, we consider the setting where reward distributions have only finite (1+v)-th moments with some v ∈ (0,1]. By resorting to robust mean estimators for rewards, we first propose two frameworks for heavy-tailed MDPs, i.e., one is for value iteration and another is for policy optimization. Under each framework, we consider both joint differential privacy (JDP) and local differential privacy (LDP) models. Based on our frameworks, we provide regret upper bounds for both JDP and LDP cases and show that the moment of distribution and privacy budget both have significant impacts on regrets. Finally, we establish a lower bound of regret minimization for heavy-tailed MDPs in JDP model by reducing it to the instance-independent lower bound of heavy-tailed multi-armed bandits in DP model. We also show the lower bound for the problem in LDP by adopting some private minimax methods. Our results reveal that there are fundamental differences between the problem of private RL with sub-Gaussian and that with heavy-tailed rewards.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 46 of its 79 references that are in the map. First posted on arXiv 1 Jun 2023.

Builds on

46 of 79 references.

References · 46

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2021Reinforcement learning based recommender systems: A surveycited by 187
  5. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 181
  6. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  7. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  8. 2018Differentially Private Contextual Linear Banditscited by 82
  9. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  10. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  11. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  12. 2021Robust and Differentially Private Mean Estimationcited by 66
34 more
  1. 2019Efficient Ridesharing Order Dispatching with Mean Field Multi-Agent Reinforcement Learningcited by 57
  2. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 52
  3. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  4. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2016Cascading Bandits for Large-Scale Recommendation Problemscited by 45
  7. 2021High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Datacited by 42
  8. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
  9. 2020Multi-Armed Bandits with Local Differential Privacycited by 37
  10. 2019How You Act Tells a Lot: Privacy-Leakage Attack on Deep Reinforcement Learningcited by 29
  11. 2022When Privacy Meets Partial Information: A Refined Analysis of Differentially Private Banditscited by 28
  12. 2022Shuffle Private Linear Contextual Banditscited by 27
  13. 2021Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Banditscited by 25
  14. 2021Regret Minimization in Heavy-Tailed Banditscited by 24
  15. 2013Private Matchings and Allocationscited by 23
  16. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  17. 2020Local Differential Privacy for Regret Minimization in Reinforcement Learningcited by 22
  18. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  19. 2022Towards Agnostic Feature-based Dynamic Pricing: Linear Policies vs Linear Valuation with Unknown Noisecited by 21
  20. 2018Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Casecited by 19
  21. 2020Local Differential Privacy for Bayesian Optimizationcited by 19
  22. 2020Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewardscited by 18
  23. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  24. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  25. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  26. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
  27. 2021Differential Privacy in Personalized Pricing with Nonparametric Demand Modelscited by 13
  28. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  29. 2021No-Regret Algorithms for Private Gaussian Process Bandit Optimizationcited by 11
  30. 2017A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosiscited by 9
  31. 2022Differentially Private ℓ1-norm Linear Regression with Heavy-tailed Datacited by 8
  32. 2022Differentially Private Linear Bandits with Partial Distributed Feedbackcited by 8
  33. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  34. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 1; 2026: 1.

4 papers.

  1. 2025Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Conditioncited by 2
  2. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  3. 2024Near-Optimal Reinforcement Learning with Shuffle Differential Privacycited by 1
  4. 2026Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processescited by 1