Faster Rates for Private Adversarial Bandits

We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of O √ KT √ ε , improving upon the existing upper bound O √ KT log(KT ) ε for all ε ≤ 1. In particular, our algorithms allow for sublinear expected regret even when ε ≤ 1 √ T , establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret O √ N T √ ε , O √ KT log(N ) log(KT ) ε , and , where K and N are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large K, N and ε.