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

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.