Best-of-Both-Worlds Bandits under Global Differential Privacy

Best-of-both-worlds bandit algorithms exploit stochastic losses while retaining worst-case guarantees against adversarial losses, without knowing the environment in advance. Achieving this adaptivity under differential privacy requires balancing efficient learning and adversarial robustness within a fixed privacy budget. We introduce Private Detect-and-Switch (PrivDaS), which extends the detect-and-switch approach of Bubeck and Slivkins (COLT 2012) to private bandit learning. PrivDaS combines private successive elimination with tests for consistency with stochastic losses, continues to sample and monitor eliminated arms, and switches to a private adversarial algorithm when a test fails. Our construction controls the privacy cost across elimination, monitoring, and switching. For $K$ arms and a horizon of $T$ rounds, PrivDaS satisfies pure global $ϵ$-differential privacy and achieves expected regret $O(({\log }^{2}T)\sqrt{\frac{KT}{ϵ}}+\frac{1}{ϵ})$ against oblivious adversaries and $O\left({\sum }_{i:{\Delta }_i>0}\frac{(\log T)(1+\log (1/{\Delta }_i))}{\min \{{\Delta }_i,ϵ\}}\right)$ in stochastic environments, where $ϵ$ is the privacy parameter and ${\Delta }_i$ is the suboptimality gap of arm $i$. These bounds recover, up to additional logarithmic factors in the inverse gaps and the horizon, the gap-dependent stochastic guarantee of Azize and Basu (NeurIPS 2022) and the adversarial guarantee of Asi, Raman, and Talwar (ICML 2025), previously obtained by algorithms designed separately for the two environments. To our knowledge, PrivDaS is the first bandit algorithm to achieve best-of-both-worlds regret guarantees under global differential privacy.