mlsanityData to 7 Oct 2026

Differentially Private Exploration in Reinforcement Learning with Linear Representation

arXiv 2112.01585 ↗First posted 2 Dec 2021cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

This paper studies privacy-preserving exploration in Markov Decision Processes (MDPs) with linear representation. We first consider the setting of linear-mixture MDPs (Ayoub et al., 2020) (a.k.a. model-based setting) and provide an unified framework for analyzing joint and local differential private (DP) exploration. Through this framework, we prove a widetildeO(K3/4/√ε) regret bound for (ε,δ)-local DP exploration and a widetildeO(√K/ε) regret bound for (ε,δ)-joint DP. We further study privacy-preserving exploration in linear MDPs (Jin et al., 2020) (a.k.a. model-free setting) where we provide a widetildeOleft(K^frac35/ε^frac25right) regret bound for (ε,δ)-joint DP, with a novel algorithm based on low-switching. Finally, we provide insights into the issues of designing local DP algorithms in this model-free setting.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 18 of its 47 references that are in the map. First posted on arXiv 2 Dec 2021.

Builds on

18 of 47 references.

References · 18

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2013The Composition Theorem for Differential Privacycited by 290
  4. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  7. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  8. 2018Distributed Differential Privacy via Shufflingcited by 115
  9. 2018Differentially Private Contextual Linear Banditscited by 82
  10. 2019The Privacy Blanket of the Shuffle Modelcited by 73
  11. 2020Locally Differentially Private (Contextual) Bandits Learningcited by 52
  12. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
6 more
  1. 2015Algorithms for Differentially Private Multi-Armed Banditscited by 44
  2. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  3. 2019An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rulecited by 37
  4. 2013Private Matchings and Allocationscited by 23
  5. 2020Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsificationcited by 13
  6. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13

Built on by

Cited by year

Citing papers per year: 2022: 4; 2023: 0; 2024: 4; 2025: 3.

11 papers.

  1. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  2. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  3. 2022Distributed Differential Privacy in Multi-Armed Banditscited by 14
  4. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  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. 2025Towards Optimal Differentially Private Regret Bounds in Linear MDPscited by 0