Towards Optimal Differentially Private Regret Bounds in Linear MDPs

2025/04/12 by Sahu, Sharan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2504.09339

Abstract

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(√(d³ H⁴ K)) regret in the non-private setting. Building on recent advances that improve this to near minimax optimal regret \widetildeO(d√H³K) 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 √(H³ K) + H^15/4 d^7/6 K^1/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.

Related

• Improved Regret for Differentially Private Exploration in Linear MDP
• Differentially Private Regret Minimization in Episodic Markov Decision Processes
• Differentially Private Reinforcement Learning with Linear Function Approximation
• Differentially Private Exploration in Reinforcement Learning with Linear Representation
• Local Differential Privacy for Regret Minimization in Reinforcement Learning