Skip to main navigation Skip to search Skip to main content

Differentially Private Best-Arm Identification

  • Achraf Azize
  • , Marc Jourdan
  • , Aymen Al Marjani
  • , Debabrota Basu
  • ENAC-IIC-GEL
  • Amazon Machine Learning Solutions Lab
  • Université de Lille

Research output: Contribution to journal › Article › peer-review

Abstract

Best Arm Identification (BAI) problems are progressively used for data-sensitive applications, such as designing adaptive clinical trials, tuning hyper-parameters, and conducting user studies. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence in both the local and central models, i.e. under ϵ-local and ϵ-global Differential Privacy (DP). First, to quantify the cost of privacy, we derive lower bounds on the sample complexity of any δ-correct BAI algorithm satisfying ϵ-global DP or ϵ-local DP. Our lower bounds suggest the existence of two privacy regimes. In the high-privacy regime, the hardness depends on a coupled effect of privacy and novel information-theoretic quantities involving the Total Variation distance. In the low-privacy regime, the lower bounds reduce to the non-private lower bounds. We propose ϵ-local DP and ϵ-global DP variants of a Top Two algorithm, namely CTB-TT and AdaP-TT★, respectively. For ϵ-local DP, CTB-TT is asymptotically optimal by plugging in a private estimator of the means based on Randomised Response. For ϵ-global DP, our private estimator of the mean runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. By adapting the transportation costs, the expected sample complexity of AdaP-TT★ reaches the asymptotic lower bound in the asymptotic high-privacy regime, up to a small multiplicative constant.

Original languageEnglish
Article number73
JournalJournal of Machine Learning Research
Volume27
Publication statusPublished - 1 Jan 2026

Keywords

  • best arm identification
  • differential privacy
  • fixed confidence
  • multi-armed bandits
  • top two algorithm

Fingerprint

Dive into the research topics of 'Differentially Private Best-Arm Identification'. Together they form a unique fingerprint.

Cite this