Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret
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-\alpha)}\right)$-GDP and enjoys an $O \left(K\ln^{\alpha+1}(T)/\Delta \right)$ regret bound, where $\alpha \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.
Code (0)
등록된 구현이 없습니다.
Tasks
Thompson SamplingSimilar Papers 제목 키워드 기반
Batched Thompson Sampling for Multi-Armed Bandits
We study Thompson Sampling algorithms for stochastic multi-armed bandits in the batched setting, in which we want to minimize the regret over a sequence of arm pulls using a small number of policy changes (or, batches). …
Multi-Armed BanditsThompson SamplingAn Empirical Evaluation of Thompson Sampling
Thompson sampling is one of oldest heuristic to address the exploration / exploitation trade-off, but it is surprisingly not very popular in the literature. We present here some empirical results using Thompson sampling …
Multi-Armed BanditsThompson SamplingEfficient and Adaptive Posterior Sampling Algorithms for Bandits
We study Thompson Sampling-based algorithms for stochastic bandits with bounded rewards. As the existing problem-dependent regret bound for Thompson Sampling with Gaussian priors [Agrawal and Goyal, 2017] is vacuous when…
Thompson SamplingDeep Bandits Show-Off: Simple and Efficient Exploration with Deep Networks
Designing efficient exploration is central to Reinforcement Learning due to the fundamental problem posed by the exploration-exploitation dilemma. Bayesian exploration strategies like Thompson Sampling resolve this trade…
Efficient ExplorationMulti-Armed BanditsThompson SamplingPreferential Multi-Objective Bayesian Optimization
Preferential Bayesian optimization (PBO) is a framework for optimizing a decision-maker's latent preferences over available design choices. While preferences often involve multiple conflicting objectives, existing work i…
Autonomous DrivingBayesian OptimizationThompson Sampling