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. $\epsilon$-local and
$\epsilon$-global Differential Privacy (DP). First, to quantify the cost of
privacy, we derive lower bounds on the sample complexity of any
$\delta$-correct BAI algorithm satisfying $\epsilon$-global DP or
$\epsilon$-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. In the low-privacy regime, the lower bounds reduce to the
non-private lower bounds. We propose $\epsilon$-local DP and $\epsilon$-global
DP variants of a Top Two algorithm, namely CTB-TT and AdaP-TT*, respectively.
For $\epsilon$-local DP, CTB-TT is asymptotically optimal by plugging in a
private estimator of the means based on Randomised Response. For
$\epsilon$-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 up to multiplicative constants.

最佳臂识别（BAI）问题在数据敏感应用中得到广泛应用，研究此问题时考虑了固定置信度下的本地和中心模型的差分隐私（DP）要求，并提出了相应的算法，以实现隐私与效用之间的权衡。