# Thompson Sampling Itself is Differentially Private

arXiv: https://arxiv.org/abs/2407.14879 · HTML: https://mlsanity.com/paper/2407.14879/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 37 references that are in the map.
- First posted on arXiv 20 Jul 2024.

## Builds on (most cited first, 9 of 9)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [Thompson Sampling for Combinatorial Network Optimization in Unknown Environments](https://mlsanity.com/paper/1907.04201/) (2019)
- [Variable Selection via Thompson Sampling](https://mlsanity.com/paper/2007.00187/) (2020)
- [The Possibilities and Limitations of Private Prediction Markets](https://mlsanity.com/paper/1602.07362/) (2016)
- [Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment](https://mlsanity.com/paper/2102.07929/) (2021)

## Built on by (most cited first, 4 of 4)

- [Differentially Private Hyperparameter Tuning using Local Bayesian Optimization](https://mlsanity.com/paper/2502.06044/) (2025)
- [Connecting Thompson Sampling and UCB: Towards More Efficient Trade-offs Between Privacy and Regret](https://mlsanity.com/paper/2505.02383/) (2025)
- [Randomized Least Squares Value Iteration itself is Joint Differentially Private](https://mlsanity.com/paper/2606.01952/) (2026)
- [Differential Privacy of Gaussian Process Posterior Sampling](https://mlsanity.com/paper/2606.17995/) (2026)

## Abstract (arXiv)

In this work we first show that the classical Thompson sampling algorithm for multi-arm bandits is differentially private as-is, without any modification. We provide per-round privacy guarantees as a function of problem parameters and show composition over T rounds; since the algorithm is unchanged, existing O(√NTlog N) regret bounds still hold and there is no loss in performance due to privacy. We then show that simple modifications -- such as pre-pulling all arms a fixed number of times, increasing the sampling variance -- can provide tighter privacy guarantees. We again provide privacy guarantees that now depend on the new parameters introduced in the modification, which allows the analyst to tune the privacy guarantee as desired. We also provide a novel regret analysis for this new algorithm, and show how the new parameters also impact expected regret. Finally, we empirically validate and illustrate our theoretical findings in two parameter regimes and demonstrate that tuning the new parameters substantially improve the privacy-regret tradeoff.