On The Differential Privacy of Thompson Sampling With Gaussian Prior

Understand

We show that Thompson Sampling with Gaussian Prior as detailed by Algorithm 2 in (Agrawal & Goyal, 2013) is already differentially private.

• Theorem 1 show that it enjoys a very competitive privacy loss of only $\mathcal{O}(\ln^2 T)$ after T rounds.
• Finally, Theorem 2 show that one can control the privacy loss to any desirable $\epsilon$ level by appropriately increasing the variance of the samples from the Gaussian posterior.
• And this increases the regret only by a term of $\mathcal{O}(\frac{\ln^2 T}{\epsilon})$.