Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret

2025/05/05 by Bingshan Hu, Hu, Bingshan, Zhiming Huang +7
Computer Science · Medicine · #Ethics in Clinical Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2505.02383

openalex publication_date 2025/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 O (T^0.25(1-α))-GDP and enjoys an O (Kln^α+1(T)/Δ) regret bound, where α∈ [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.

Citations

• Thompson Sampling Itself is Differentially Private
• When Privacy Meets Partial Information: A Refined Analysis of\n Differentially Private Bandits
• Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits
• Maillard Sampling: Boltzmann Exploration Done Optimally
• MOTS: Minimax Optimal Thompson Sampling
• An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule
• Differentially Private Contextual Linear Bandits
• Thompson Sampling: An Asymptotically Optimal Finite Time Analysis

Related

• Thompson Sampling Itself is Differentially Private
• On The Differential Privacy of Thompson Sampling With Gaussian Prior
• Thompson Sampling under Bernoulli Rewards with Local Differential Privacy
• DP-NCB: Privacy Preserving Fair Bandits
• Mitigating Bias in Adaptive Data Gathering via Differential Privacy