提出隐私保护强化学习新算法,实现近最优后悔界。
Towards Optimal Differentially Private Regret Bounds in Linear MDPs
- 基于改进的LSVI-UCB++算法,结合方差感知分析设计私有化方法。
- 在$ε$-差分隐私下,后悔界为$\widetilde{O}(d \sqrt{H^3 K} + H^{15/4} d^{7/6} K^{1/2} / ε)$。
- 实验显示隐私保护对性能影响极小,适合敏感数据场景下的强化学习应用。
我们研究在非同质线性马尔可夫决策过程(MDPs)中,于隐私约束下的后悔最小化问题,该问题源于依赖敏感用户数据的个性化决策系统对强化学习日益增长的应用需求。在此设定中,转移概率与奖励函数均假设为特征映射$ϕ(s, a)$的线性形式,通过联合差分隐私(JDP)实现隐私保护,这是一种适用于在线学习的差分隐私松弛形式。已有工作通过私有化LSVI-UCB算法获得次优后悔界,在非私有环境下其后悔界为$\widetilde{O}(\sqrt{d^3 H^4 K})$。基于近期进展,即通过带伯恩斯坦风格奖励项的LSVI-UCB++将后悔界提升至近极小极大最优$\widetilde{O}(d\sqrt{H^{3}K})$,我们设计了一种新的差分隐私算法,通过私有化LSVI-UCB++并引入离线强化学习中的方差感知分析技术。所提算法在$ε$-差分隐私下达到$\widetilde{O}(d \sqrt{H^3 K} + H^{15/4} d^{7/6} K^{1/2} / ε)$的后悔界,优于以往私有化方法。实验结果表明,该算法在与非私有基线相比时仍保持近最优效用,说明在此设置下隐私可实现而性能损失极小。
原文摘要 · Abstract (English)
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 $\widetilde{O}(\sqrt{d^3 H^4 K})$ regret in the non-private setting. Building on recent advances that improve this to near minimax optimal regret $\widetilde{O}(d\sqrt{H^{3}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 $\widetilde{O}(d \sqrt{H^3 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。