让上下文猜拳算法在保护隐私的同时，性能接近无隐私版本。
AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification
- 用分批zCDP组合加高斯噪声，让隐私噪声被算法视为不确定性。
- 在真实数据集上，ε=0.5~5时性能达非私有算法的93%-99%。
- 适合注重隐私且需高精度推荐的场景，如医疗或金融应用。
我们提出AdaPrivate-TS，一种结合泰勒采样与分批zCDP组合的差分隐私上下文猜拳算法。核心洞察是：向参数向量添加高斯噪声 $N(0,σ^2 I)$ 会以结构化方式扩大后验协方差，使泰勒采样将其解读为增加的不确定性而非纯粹污染。在事件级隐私（保护单个交互）与随机上下文条件下，隐私成本仅为 $O(\ oot\of{d}\log T/\sqrtρ)$，对 $T$ 呈对数依赖，因并行组合可摊销噪声。此外，我们探索泊松抽样带来的隐私放大效应，可在严苛隐私预算下降低有效噪声。实验表明：(1) 在合成与真实数据集上，当 $\varepsilon \in [0.5, 5]$ 时，性能达非私有算法的93%-99%，优于UCB 0.5-3.7%，极端 $\varepsilon$ 下经自适应探索调优可达18%提升；(2) 隐私放大带来低 $\varepsilon$ 下额外2-5%增益；(3) 在MovieLens与Jester数据集上，整体性能超越所有事件级基线，尤其在 $\varepsilon \geq 2$ 时显著领先；(4) 在DP-SVD私有特征下，泰勒采样相较UCB优势增至+11%，验证噪声即不确定性机制不局限于奖励隐私。论文提供交互式zCDP组合下的严格隐私证明，并包含收敛曲线、12次种子置信区间及DP-SVD特征消融的全面评估。
原文摘要 · Abstract (English)
We present AdaPrivate-TS, a differentially private contextual bandit algorithm that combines Thompson Sampling with batched zCDP composition. Our key insight is that differential privacy noise inflates the posterior covariance in a structured way: adding Gaussian noise $N(0,σ^2 I)$ to $b$ yields sampling covariance $v^2 A^{-1} + σ^2 A^{-2}$, which Thompson Sampling interprets as increased uncertainty rather than pure corruption. Under event-level privacy (protecting individual interactions) with stochastic contexts, we prove that the privacy cost is only $O(\sqrt{d}\,\log T/\sqrtρ)$, logarithmic in $T$, because parallel composition amortizes noise across batches. Additionally, we explore privacy amplification via Poisson subsampling, which can reduce effective noise at stringent privacy budgets. Experiments on synthetic and real-world datasets demonstrate: (1) AdaPrivate-TS achieves 93-99% of non-private performance at $\varepsilon \in [0.5, 5]$, outperforming UCB by 0.5-3.7% and up to 18% with tuned adaptive exploration at extreme $\varepsilon$; (2) privacy amplification provides additional 2-5% gains at low $\varepsilon$; (3) on MovieLens and Jester, AdaPrivate-TS achieves the best overall performance among event-level baselines, dominating at $\varepsilon \geq 2$; (4) under DP-SVD private features, TS's advantage over UCB grows to +11%, confirming noise-as-uncertainty is not limited to reward privacy. We provide rigorous proofs for privacy guarantees under interactive zCDP composition and comprehensive evaluation including convergence curves, 12-seed CIs, and DP-SVD feature ablation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。