Timezone: »

 
Poster
Differentially Private Multi-Armed Bandits in the Shuffle Model
Jay Tenenbaum · Haim Kaplan · Yishay Mansour · Uri Stemmer

Thu Dec 09 12:30 AM -- 02:00 AM (PST) @
in Poster Session 5 »
We give an $(\varepsilon,\delta)$-differentially private algorithm for the Multi-Armed Bandit (MAB) problem in the shuffle model with a distribution-dependent regret of $O\left(\left(\sum_{a:\Delta_a>0}\frac{\log T}{\Delta_a}\right)+\frac{k\sqrt{\log\frac{1}{\delta}}\log T}{\varepsilon}\right)$, and a distribution-independent regret of $O\left(\sqrt{kT\log T}+\frac{k\sqrt{\log\frac{1}{\delta}}\log T}{\varepsilon}\right)$, where $T$ is the number of rounds, $\Delta_a$ is the suboptimality gap of the action $a$, and $k$ is the total number of actions. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.
Keywords: Bandits · Privacy

Author Information

Jay Tenenbaum (Google Research)
Haim Kaplan
Yishay Mansour (Tel Aviv University & Google)
Uri Stemmer (Ben-Gurion University and Google Research)

More from the Same Authors