Achieving Privacy in the Adversarial Multi-Armed Bandit

Understand

In this paper, we improve the previously best known regret bound to achieve $\epsilon$-differential privacy in oblivious adversarial bandits from $\mathcal{O}{(T^{2/3}/\epsilon)}$ to $\mathcal{O}{(\sqrt{T} \ln T /\epsilon)}$.

• This is achieved by combining a Laplace Mechanism with EXP3.
• We show that though EXP3 is already differentially private, it leaks a linear amount of information in $T$.
• However, we can improve this privacy by relying on its intrinsic exponential mechanism for selecting actions.