mlsanityData to 7 Oct 2026

Towards Optimal Differentially Private Regret Bounds in Linear MDPs

arXiv 2504.09339 ↗First posted 12 Apr 2025cs.LG cs.DS stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study regret minimization under privacy constraints in episodic inhomogeneous linear Markov Decision Processes (MDPs), motivated by the growing use of reinforcement learning (RL) in personalized decision-making systems that rely on sensitive user data. In this setting, both transition probabilities and reward functions are assumed to be linear in a feature mapping φ(s, a), and we aim to ensure privacy through joint differential privacy (JDP), a relaxation of differential privacy suited to online learning. Prior work has established suboptimal regret bounds by privatizing the LSVI-UCB algorithm, which achieves widetildeO(√d3 H4 K) regret in the non-private setting. Building on recent advances that improve this to near minimax optimal regret widetildeO(d√H3K) via LSVI-UCB++ with Bernstein-style bonuses, we design a new differentially private algorithm by privatizing LSVI-UCB++ and adapting techniques for variance-aware analysis from offline RL. Our algorithm achieves a regret bound of widetildeO(d √H3 K + H15/4 d7/6 K1/2 / ε), improving over previous private methods. Empirical results show that our algorithm retains near-optimal utility compared to non-private baselines, indicating that privacy can be achieved with minimal performance degradation in this setting.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 34 references that are in the map. First posted on arXiv 12 Apr 2025.

Builds on

24 of 34 references.

References · 24

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  5. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 224
  6. 2021Reinforcement learning based recommender systems: A surveycited by 187
  7. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  8. 2016Concentrated Differential Privacycited by 139
  9. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  10. 2018Differentially Private Contextual Linear Banditscited by 82
  11. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  12. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
12 more
  1. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  2. 2020Private Reinforcement Learning with PAC and Regret Guaranteescited by 51
  3. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  4. 2013Private Matchings and Allocationscited by 23
  5. 2021Differentially Private Regret Minimization in Episodic Markov Decision Processescited by 23
  6. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  7. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  8. 2021Privately Publishable Per-instance Privacycited by 12
  9. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  10. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  11. 2015Robust Mediators in Large Gamescited by 6
  12. 2024Medical Knowledge Integration into Reinforcement Learning Algorithms for Dynamic Treatment Regimescited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Privacy-Preserving Reinforcement Learning from Human Feedback via Decoupled Reward Modeling
  2. 2026Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits
  3. 2026Privacy Without Regret: Differentially Private Inference-Time Alignment
  4. 2025KL-regularization Itself is Differentially Private in Bandits and RLHF
  5. 2019Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces
  6. 2024Preserving Expert-Level Privacy in Offline Reinforcement Learning
  7. 2025Towards User-level Private Reinforcement Learning with Human Feedback
  8. 2025Offline and Online KL-Regularized RLHF under Differential Privacy