Differentially Private Best-Arm Identification

这篇论文题为《Differentially Private Best-Arm Identification》（差分隐私下的最优臂识别），发表于 Journal of Machine Learning Research (2026)。文章主要研究了在**固定置信度（Fixed-Confidence, FC）设置下的多臂老虎机（Multi-Armed Bandit, MAB）最优臂识别（BAI）问题，并引入了差分隐私（Differential Privacy, DP）**约束。

以下是该论文的详细技术总结：

1. 研究背景与问题定义

• 背景：最优臂识别（BAI）广泛应用于临床试验设计、超参数调优、用户研究等场景。这些应用通常涉及敏感的个人数据，因此对隐私保护提出了严格要求。
• 核心问题：在满足差分隐私（$\epsilon$-DP）约束的前提下，如何设计算法以最小的样本复杂度（Sample Complexity）找到期望奖励最高的臂？
• 隐私模型：
  • $\epsilon$-局部差分隐私 ($\epsilon$-LDP)：用户不信任数据收集者，数据在本地被扰动后发送。
  • $\epsilon$-全局差分隐私 ($\epsilon$-GDP)：用户信任中央决策者，决策者拥有原始数据，但发布结果时需满足隐私约束。
• 目标：设计 $\delta$-correct（即以至少 $1-\delta$ 的概率返回正确最优臂）的算法，并最小化期望停止时间（样本复杂度）。

2. 主要贡献

2.1 理论下界（Lower Bounds）

论文推导了满足 $\epsilon$-LDP 和 $\epsilon$-GDP 的任意 $\delta$-correct BAI 算法的样本复杂度下界。

• 两个隐私机制（Regimes）：下界揭示了存在两个隐私困难度机制：
  1. 低隐私机制（Low-Privacy Regime）：当隐私预算 $\epsilon$ 较大时，隐私约束不增加样本复杂度，下界退化为非隐私情况下的下界（基于 KL 散度）。
  2. 高隐私机制（High-Privacy Regime）：当 $\epsilon$ 较小时，样本复杂度显著增加。
     • 对于 LDP：下界依赖于 TV 距离的平方 ($TV^2$) 和隐私预算 $\epsilon$，形式约为 $\Omega(\epsilon^{-2} T^*_{TV2}(\nu))$。
     • 对于 GDP：下界依赖于 TV 距离 ($TV$) 和隐私预算$\epsilon$，形式约为$\Omega(\epsilon^{-1} T^*_{TV}(\nu))$。
• 创新点：
  • 在 LDP 下，区分度度量是 KL 散度与 $c(\epsilon)TV^2$ 的最小值。
  • 在 GDP 下，作者提出了一个新的“改变测度（change-of-measure）”引理，利用耦合（Coupling）技术证明了 KL 散度上界与 TV 距离的线性关系，从而推导出包含 TV 距离的下界。

2.2 算法设计

作者提出了基于 Top Two 框架（具体为 TTUCB 元算法）的隐私保护变体算法。

• 针对 $\epsilon$-LDP 的算法：CTB-TT

  • 核心思想：将随机响应（Randomised Response, RR）机制嵌入到均值估计器中。
  • 方法：使用 CTB(CTB) 估计器（Convert-To-Bernoulli），将原始奖励转换为伯努利分布的扰动版本。
  • 性质：该算法等价于在非隐私的 TTUCB 算法上运行一个修改后的伯努利实例。
  • 结果：在渐近意义下达到最优，样本复杂度上界与下界仅相差一个常数因子（$\epsilon \to 0$ 时为 4，$\epsilon \to \infty$ 时为 2）。

• 针对 $\epsilon$-GDP 的算法：AdaP-TT 和 AdaP-TT$\star$

  • 核心思想：设计了一种新的均值估计器 DAF($\epsilon$) (Doubling-And-Forgetting)，结合臂独立的自适应阶段（Episodes）、遗忘机制和拉普拉斯噪声。
    • Doubling：仅当某臂的采样次数翻倍时更新均值。
    • Forgetting：仅使用当前阶段（Phase）内的数据计算均值，避免隐私累积。
    • Noise：在每个阶段结束时添加拉普拉斯噪声。
  • AdaP-TT：
    • 直接插入 DAF 估计器，但保留非隐私的传输成本（Transportation Costs）和停止规则，仅调整停止阈值以补偿隐私噪声。
    • 局限性：在高隐私机制下，对于均值差距差异较大的实例，无法达到渐近下界。
  • AdaP-TT$\star$：
    • 改进：不仅调整停止阈值，还修改了传输成本（Transportation Costs），使其适应隐私约束（基于下界中的 TV 距离特性）。
    • 结果：在渐近高隐私机制下（$\epsilon \to 0$），达到了与下界匹配的样本复杂度（相差常数因子 48），解决了 AdaP-TT 的次优性问题。

3. 关键结果与实验分析

• 理论匹配：
  • 提出的算法（CTB-TT, AdaP-TT$\star$）的样本复杂度上界与推导的下界在渐近意义下匹配（仅相差常数倍）。
  • 验证了“低隐私”和“高隐私”两个机制的存在。
• 实验表现：
  • LDP 实验：CTB-TT 在低隐私预算下表现优异，但在高隐私预算下样本复杂度随 $\epsilon^{-2}$ 急剧增加。
  • GDP 实验：
    • AdaP-TT$\star$ 在低隐私预算下表现与 AdaP-TT 相当。
    • 在高隐私预算下，AdaP-TT$\star$ 显著优于 AdaP-TT 和现有的 DP-SE 算法（Successive Elimination 的隐私版本）。
    • 实验确认了算法在不同隐私预算下的两个机制切换点。
• 自适应轮次：算法仅需要 $O(K \log^2(T^* \log(1/\delta)))$ 轮自适应（Adaptivity），即批处理（Batched）更新，这在计算上非常高效。

4. 意义与贡献总结

1. 填补空白：首次系统地研究了固定置信度 BAI 问题中的差分隐私下界和最优算法设计。此前该领域仅有少量关于 regret minimization 的研究。
2. 理论突破：
   • 揭示了隐私约束下 BAI 问题的本质困难度由 TV 距离（而非传统的 KL 散度）主导。
   • 证明了在强隐私下，样本复杂度的代价是 $\epsilon^{-1}$ (GDP) 或 $\epsilon^{-2}$ (LDP) 倍的 TV 特征时间。
3. 算法创新：
   • 提出了 DAF 估计器，巧妙地利用“遗忘”和“倍增”机制避免了隐私预算的累加，实现了全局差分隐私。
   • 提出了 AdaP-TT$\star$，通过自适应调整传输成本，成功在高隐私机制下达到了理论下界，解决了“隐私 - 效用”权衡中的次优问题。
4. 实际应用：为涉及敏感数据的自适应实验（如临床试验剂量寻找）提供了理论保证和可落地的隐私保护算法方案。

5. 结论

该论文通过严谨的理论推导和算法设计，解决了差分隐私下的最优臂识别问题。它证明了在隐私约束下，虽然样本复杂度会增加，但通过设计特定的隐私感知算法（如 CTB-TT 和 AdaP-TT$\star$），可以在保持隐私的同时，仅付出常数倍的样本代价，从而在理论和实践上均达到了高效性。