(Nearly) Optimal Differentially Private Stochastic Multi-Arm Bandits

Nikita Mishra 1989, Abhradeep Thakurta Yahoo!
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:149-158, 2015.

Abstract

We study the problem of private stochastic multi-arm bandits. Our notion of privacy is the same as some of the earlier works in the general area of private online learning [13, 17, 24]. We design algorithms that are i) differentially private, and ii) have regret guarantees that (almost) match the regret guarantees for the best non-private algorithms (e.g., upper confidence bound sampling and Thompson sampling). Moreover, through our experiments on both simulated and real datasets, we empirically show the effectiveness of our algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-198915a, title = {(Nearly) Optimal Differentially Private Stochastic Multi-Arm Bandits}, author = {1989, Nikita Mishra and Yahoo!, Abhradeep Thakurta}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {149--158}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/198915a/198915a.pdf}, url = {https://proceedings.mlr.press/r13/198915a.html}, abstract = {We study the problem of private stochastic multi-arm bandits. Our notion of privacy is the same as some of the earlier works in the general area of private online learning [13, 17, 24]. We design algorithms that are i) differentially private, and ii) have regret guarantees that (almost) match the regret guarantees for the best non-private algorithms (e.g., upper confidence bound sampling and Thompson sampling). Moreover, through our experiments on both simulated and real datasets, we empirically show the effectiveness of our algorithms.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T (Nearly) Optimal Differentially Private Stochastic Multi-Arm Bandits %A Nikita Mishra 1989 %A Abhradeep Thakurta Yahoo! %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-198915a %I PMLR %P 149--158 %U https://proceedings.mlr.press/r13/198915a.html %V R13 %X We study the problem of private stochastic multi-arm bandits. Our notion of privacy is the same as some of the earlier works in the general area of private online learning [13, 17, 24]. We design algorithms that are i) differentially private, and ii) have regret guarantees that (almost) match the regret guarantees for the best non-private algorithms (e.g., upper confidence bound sampling and Thompson sampling). Moreover, through our experiments on both simulated and real datasets, we empirically show the effectiveness of our algorithms. %Z Reissued by PMLR on 04 October 2026.
APA
1989, N.M. & Yahoo!, A.T.. (2015). (Nearly) Optimal Differentially Private Stochastic Multi-Arm Bandits. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:149-158 Available from https://proceedings.mlr.press/r13/198915a.html. Reissued by PMLR on 04 October 2026.

Related Material