Abstract
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(√NT/√ε), O(√KTlog(N)log(KT)/ε), and O(N^1/6K^1/2T^2/3log(NT)/ε ^1/3 + N^1/2log(NT)/ε), 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 ε.