# Towards Optimal Differentially Private Regret Bounds in Linear MDPs

arXiv: https://arxiv.org/abs/2504.09339 · HTML: https://mlsanity.com/paper/2504.09339/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for energy, networks and operations, one of 15 directions in Deep reinforcement learning methods.
- Builds on 24 of its 34 references that are in the map.
- First posted on arXiv 12 Apr 2025.

## Placed in

- Deep reinforcement learning methods / [RL for energy, networks and operations](https://mlsanity.com/deeprl/rl-for-energy-networks-and-operations/)

## Builds on (most cited first, 24 of 24)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Deep Reinforcement Learning framework for Autonomous Driving](https://mlsanity.com/paper/1704.02532/) (2017)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Differentially Private Contextual Linear Bandits](https://mlsanity.com/paper/1810.00068/) (2018)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Private Reinforcement Learning with PAC and Regret Guarantees](https://mlsanity.com/paper/2009.09052/) (2020)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [Private Matchings and Allocations](https://mlsanity.com/paper/1311.2828/) (2013)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Offline Reinforcement Learning with Differential Privacy](https://mlsanity.com/paper/2206.00810/) (2022)
- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [Privately Publishable Per-instance Privacy](https://mlsanity.com/paper/2111.02281/) (2021)
- [Differentially Private Exploration in Reinforcement Learning with Linear Representation](https://mlsanity.com/paper/2112.01585/) (2021)
- [Improved Regret for Differentially Private Exploration in Linear MDP](https://mlsanity.com/paper/2202.01292/) (2022)
- [Robust Mediators in Large Games](https://mlsanity.com/paper/1512.02698/) (2015)
- [Medical Knowledge Integration into Reinforcement Learning Algorithms for Dynamic Treatment Regimes](https://mlsanity.com/paper/2407.00364/) (2024)

## 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.