Near-Optimal Reinforcement Learning with Shuffle Differential Privacy
作者: Shaojie Bai, Mohammad Sadegh Talebi, Chengcheng Zhao, Peng Cheng, Jiming Chen
分类: cs.LG, cs.AI, cs.CR
发布日期: 2024-11-18 (更新: 2025-11-17)
💡 一句话要点
提出SDP-PE算法，在Shuffle差分隐私下实现近优强化学习，解决网络系统隐私泄露问题。
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 强化学习 差分隐私 Shuffle模型 隐私保护 策略消除
📋 核心要点
- 现有中心化差分隐私强化学习存在单点故障风险，本地差分隐私强化学习性能损失大，难以满足网络系统需求。
- 提出Shuffle差分隐私策略消除(SDP-PE)算法，利用Shuffle模型在隐私保护和性能之间取得平衡。
- 理论分析表明SDP-PE实现了近优的遗憾界限，数值实验验证了其有效性，优于本地模型，接近中心化模型。
📝 摘要（中文）
强化学习(RL)是序贯决策的强大工具，但其应用常因交互数据引发的隐私问题而受阻。在高级网络系统中，从运营和用户数据中学习会使系统暴露于隐私推断攻击。现有的RL差分隐私(DP)模型通常不足：中心化模型需要完全可信的服务器，存在单点故障风险，而本地模型会导致显著的性能下降，不适用于许多网络应用。本文利用新兴的Shuffle差分隐私模型弥补了这一差距，该模型提供强大的隐私保证，无需中心化信任假设。我们提出了Shuffle差分隐私策略消除(SDP-PE)，这是第一个基于策略消除的通用算法，用于Shuffle模型下的情景RL。我们的方法引入了一种新颖的指数批处理调度和一个“遗忘”机制，以平衡隐私和学习性能的竞争需求。分析表明，SDP-PE实现了近优的遗憾界限，展示了优于本地模型的隐私-遗憾权衡，其效用与中心化模型相当。数值实验也证实了我们的理论结果，并证明了SDP-PE的有效性。这项工作确立了Shuffle模型在网络系统中安全数据驱动决策中的可行性。
🔬 方法详解
问题定义：论文旨在解决在强化学习中，由于交互数据可能泄露用户隐私，导致在网络系统等场景下应用受限的问题。现有的中心化差分隐私强化学习方法依赖于完全可信的服务器，存在单点故障风险；而本地差分隐私强化学习方法则会引入过大的噪声，导致性能显著下降，无法满足许多实际应用的需求。
核心思路：论文的核心思路是利用Shuffle差分隐私模型，该模型介于中心化和本地模型之间，可以在不需要完全可信服务器的前提下，提供更强的隐私保护，同时减少对性能的影响。通过设计合适的算法，在隐私保护和学习性能之间取得平衡。
技术框架：SDP-PE算法基于策略消除框架，主要包含以下几个阶段： 1. 数据收集：智能体与环境交互，收集经验数据。 2. 指数批处理：将收集到的数据进行分批，并采用指数方式调整批次大小，以平衡隐私和学习效率。 3. 隐私处理：对每个批次的数据进行差分隐私处理，例如添加噪声。 4. Shuffle：将处理后的数据进行混洗，进一步增强隐私保护。 5. 策略更新：根据混洗后的数据，更新策略。 6. 遗忘机制：引入“遗忘”机制，定期丢弃旧的数据，以减少隐私泄露的风险。
关键创新：论文的关键创新在于： 1. 首次将Shuffle差分隐私模型应用于情景强化学习。 2. 提出了新颖的指数批处理调度方法，能够动态调整批次大小，以适应不同的学习阶段。 3. 设计了“遗忘”机制，有效降低了隐私泄露的风险，同时保持了较好的学习性能。
关键设计： 1. 指数批处理调度：批次大小按照指数规律增长，前期小批次保证隐私，后期大批次加速学习。 2. 遗忘机制：定期删除旧数据，减少隐私累积泄露，具体删除频率和数据量需要根据隐私预算和性能需求进行调整。 3. 噪声添加：根据差分隐私的要求，向数据中添加拉普拉斯噪声或高斯噪声，噪声的大小与隐私预算成反比。
🖼️ 关键图片
📊 实验亮点
实验结果表明，SDP-PE算法在保证一定隐私水平的前提下，能够实现接近最优的遗憾界限，其性能明显优于本地差分隐私强化学习算法，并且与中心化差分隐私强化学习算法的性能相当。这验证了Shuffle差分隐私模型在强化学习中的有效性，以及SDP-PE算法在隐私保护和性能之间的良好平衡。
🎯 应用场景
该研究成果可应用于各种需要保护用户隐私的强化学习场景，例如联邦学习、智能推荐系统、智能医疗、自动驾驶等。通过在数据收集和模型训练过程中引入Shuffle差分隐私保护，可以有效防止用户数据泄露，提高系统的安全性，从而促进强化学习技术在更多敏感领域的应用。
📄 摘要（原文）
Reinforcement learning (RL) is a powerful tool for sequential decision-making, but its application is often hindered by privacy concerns arising from its interaction data. This challenge is particularly acute in advanced networked systems, where learning from operational and user data can expose systems to privacy inference attacks. Existing differential privacy (DP) models for RL are often inadequate: the centralized model requires a fully trusted server, creating a single point of failure risk, while the local model incurs significant performance degradation that is unsuitable for many networked applications. This paper addresses this gap by leveraging the emerging shuffle model of privacy, an intermediate trust model that provides strong privacy guarantees without a centralized trust assumption. We present Shuffle Differentially Private Policy Elimination (SDP-PE), the first generic policy elimination-based algorithm for episodic RL under the shuffle model. Our method introduces a novel exponential batching schedule and a ``forgetting'' mechanism to balance the competing demands of privacy and learning performance. Our analysis shows that SDP-PE achieves a near-optimal regret bound, demonstrating a superior privacy-regret trade-off with utility comparable to the centralized model while significantly outperforming the local model. The numerical experiments also corroborate our theoretical results and demonstrate the effectiveness of SDP-PE. This work establishes the viability of the shuffle model for secure data-driven decision-making in networked systems.