新算法平衡隐私与决策误差，可灵活调节
Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
- 融合汤普森采样与置信上界思想，用高斯机制实现隐私保护
- 在 $T$ 步内隐私损耗为 $\tilde{O}(T^{0.25(1-α)})$，累计损失为 $O(K\ln^{α+1}(T)/Δ)$
- 适合关注隐私与性能权衡的研究者，理论价值突出
我们从高斯先验的汤普森采样、高斯机制与高斯差分隐私（GDP）之间的深层联系出发，提出一种新型参数化私有强化学习算法 DP-TS-UCB，可在隐私与累积遗憾之间灵活权衡。该算法满足 $\tilde{O}(T^{0.25(1-α)})$-GDP，且具有 $O(K\ln^{α+1}(T)/Δ)$ 的遗憾上界，其中 $α \in [0,1]$ 控制隐私与性能的平衡。理论上，其依赖于高斯分布的反集中不等式，揭示了基于汤普森采样的探索机制与基于置信上界的探索机制之间的联系，这一发现可能具有独立研究价值。
原文摘要 · Abstract (English)
We address differentially private stochastic bandit problems from the angles of exploring the deep connections among Thompson Sampling with Gaussian priors, Gaussian mechanisms, and Gaussian differential privacy (GDP). We propose DP-TS-UCB, a novel parametrized private bandit algorithm that enables to trade off privacy and regret. DP-TS-UCB satisfies $ \tilde{O} \left(T^{0.25(1-α)}\right)$-GDP and enjoys an $O \left(K\ln^{α+1}(T)/Δ\right)$ regret bound, where $α\in [0,1]$ controls the trade-off between privacy and regret. Theoretically, our DP-TS-UCB relies on anti-concentration bounds of Gaussian distributions and links exploration mechanisms in Thompson Sampling-based algorithms and Upper Confidence Bound-based algorithms, which may be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。