Abstract
In this paper, we study differentially private online learning problems in a stochastic environment under both bandit and full information feedback. For differentially private stochastic bandits, we propose both UCB and Thompson Sampling-based algorithms that are anytime and achieve the optimal O (Σ_j: Δ_j>0 ln(T)/min Δ_j, ε ) instance-dependent regret bound, where T is the finite learning horizon, Δ_j denotes the suboptimality gap between the optimal arm and a suboptimal arm j, and ε is the required privacy parameter. For the differentially private full information setting with stochastic rewards, we show an Ω (ln(K)/min Δ_min, ε ) instance-dependent regret lower bound and an Ω(√Tln(K) + ln(K)/ε) minimax lower bound, where K is the total number of actions and Δ_min denotes the minimum suboptimality gap among all the suboptimal actions. For the same differentially private full information setting, we also present an ε-differentially private algorithm whose instance-dependent regret and worst-case regret match our respective lower bounds up to an extra log(T) factor.