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 Oleft(frac√KT√εright), improving upon the existing upper bound Oleft(frac√KT log(KT)εright) for all ε ≤ 1. In particular, our algorithms allow for sublinear expected regret even when ε ≤ frac1√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 Oleft(frac√NT√εright), Oleft(frac√KTlog(N)log(KT)εright), and tildeOleft(fracN1/6K1/2T2/3log(NT)ε 1/3 + fracN1/2log(NT)εright), 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 ε.