Towards Optimal Differentially Private Regret Bounds in Linear MDPs

📄 arXiv: 2504.09339v2 📥 PDF

作者: Sharan Sahu

分类: cs.LG, cs.DS, stat.ML

发布日期: 2025-04-12 (更新: 2025-04-25)

备注: 28 pages, 2 figures

💡 一句话要点

提出基于LSVI-UCB++的差分隐私线性MDP后悔界优化算法

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 差分隐私 强化学习 线性MDP 后悔最小化 在线学习

📋 核心要点

  1. 现有方法在差分隐私线性MDP中，通过私有化LSVI-UCB算法，获得的后悔界次优，限制了算法的实际应用。
  2. 本文提出了一种新的差分隐私算法，通过私有化LSVI-UCB++并结合离线RL中的方差感知分析技术，优化了后悔界。
  3. 实验结果表明，该算法在保证隐私的同时，能够保持接近最优的性能，显著优于之前的私有方法。

📝 摘要（中文）

本文研究了在具有隐私约束的 episodic inhomogeneous 线性马尔可夫决策过程（MDP）中的后悔最小化问题。该问题源于强化学习（RL）在依赖敏感用户数据的个性化决策系统中的日益普及。在此设置中，转移概率和奖励函数均假定为特征映射 φ(s, a) 的线性函数。我们的目标是通过联合差分隐私（JDP）来确保隐私，JDP 是适用于在线学习的差分隐私的放宽形式。先前的工作通过私有化 LSVI-UCB 算法建立了次优的后悔界，该算法在非私有设置中实现了 $\widetilde{O}(\sqrt{d^3 H^4 K})$ 的后悔值。本文基于最近的进展，通过带有 Bernstein 风格奖励的 LSVI-UCB++ 将其改进到接近 minimax 最优的后悔值 $\widetilde{O}(d\sqrt{H^{3}K})$。我们通过私有化 LSVI-UCB++ 并采用离线 RL 中的方差感知分析技术，设计了一种新的差分隐私算法。我们的算法实现了 $\widetilde{O}(d \sqrt{H^3 K} + H^{15/4} d^{7/6} K^{1/2} / ε)$ 的后悔界，优于以前的私有方法。实验结果表明，与非私有基线相比，我们的算法保留了接近最优的效用，表明在这种设置中，可以在最小的性能下降的情况下实现隐私。

🔬 方法详解

问题定义：论文旨在解决线性MDP中，在满足差分隐私约束的前提下，最小化累积后悔值的问题。现有方法，如直接私有化LSVI-UCB，得到的后悔界是次优的，即$\widetilde{O}(\sqrt{d^3 H^4 K})$，距离理论最优界$\widetilde{O}(d\sqrt{H^{3}K})$存在较大差距。这限制了算法在实际应用中的性能，尤其是在需要高隐私保护的场景下。

核心思路：论文的核心思路是基于LSVI-UCB++算法，并结合Bernstein-style bonuses，该算法在非隐私情况下能够达到接近minimax最优的后悔界。通过对LSVI-UCB++进行私有化改造，并引入离线RL中的方差感知分析技术，可以在保证差分隐私的同时，尽可能地降低隐私保护对算法性能的影响。

技术框架：整体框架可以概括为：1）使用LSVI-UCB++算法作为基础框架；2）引入差分隐私机制，对算法中的敏感信息进行扰动，以满足隐私约束；3）采用方差感知分析技术，对算法的性能进行更精确的分析，从而优化算法的参数设置，进一步降低后悔值。主要模块包括：数据收集模块、模型更新模块、隐私保护模块和性能分析模块。

关键创新：最重要的技术创新点在于将LSVI-UCB++算法与差分隐私保护机制相结合，并引入了方差感知分析技术。与直接私有化LSVI-UCB相比，该方法能够更有效地利用数据信息，降低隐私保护带来的性能损失，从而获得更优的后悔界。

关键设计：关键设计包括：1）如何选择合适的差分隐私机制，以在隐私保护强度和算法性能之间取得平衡；2）如何设计方差感知的奖励函数，以更准确地估计状态-动作对的价值；3）如何优化算法的参数设置，以最小化后悔值。论文中具体的技术细节（如扰动方式、奖励函数形式、参数优化方法）未知。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

该算法实现了$\widetilde{O}(d \sqrt{H^3 K} + H^{15/4} d^{7/6} K^{1/2} / ε)$的后悔界，优于之前的私有方法。实验结果表明，与非私有基线相比，该算法在保证隐私的同时，能够保持接近最优的性能，表明隐私保护对算法性能的影响较小。具体的性能提升幅度未知。

🎯 应用场景

该研究成果可应用于个性化推荐系统、医疗决策支持系统等领域。在这些场景中，用户数据包含敏感信息，需要进行隐私保护。该算法能够在保证用户隐私的前提下，提供高质量的决策支持，具有重要的实际应用价值和社会意义。未来的研究可以进一步探索更高效的隐私保护机制，以及更复杂的MDP环境。

📄 摘要（原文）

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.