Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment

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 left(sumj: Deltaj>0 fracln(T)min leftDeltaj, ε right right) instance-dependent regret bound, where T is the finite learning horizon, Deltaj 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 Omega left(fracln(K)min leftDeltamin, ε right right) instance-dependent regret lower bound and an Omegaleft(√Tln(K) + fracln(K)εright) minimax lower bound, where K is the total number of actions and Deltamin 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.