Differentially Private Multi-Armed Bandits in the Shuffle Model
share
We give an (ε,δ)-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model with a distribution-dependent regret of O((∑_a∈ [k]:Δ_a>0log T/Δ_a)+k√(log1/δ)log T/ε), and a distribution-independent regret of O(√(kTlog T)+k√(log1/δ)log T/ε), where T is the number of rounds, Δ_a is the suboptimality gap of the arm a, and k is the total number of arms. 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.
READ FULL TEXT