Fixed-Budget Differentially Private Best Arm Identification
Zhirui Chen P. N. Karthik Yeow Meng Chee Vincent Y. F. Tan
We study best arm identification (BAI) in linear bandits in the fixed-budget
regime under differential privacy constraints, when the arm rewards are
supported on the unit interval. Given a finite budget $T$ and a privacy
parameter $\varepsilon>0$, the goal is to minimise the error probability in
finding the arm with the largest mean after $T$ sampling rounds, subject to the
constraint that the policy of the decision maker satisfies a certain {\em
$\varepsilon$-differential privacy} ($\varepsilon$-DP) constraint. We construct
a policy satisfying the $\varepsilon$-DP constraint (called {\sc DP-BAI}) by
proposing the principle of {\em maximum absolute determinants}, and derive an
upper bound on its error probability. Furthermore, we derive a minimax lower
bound on the error probability, and demonstrate that the lower and the upper
bounds decay exponentially in $T$, with exponents in the two bounds matching
order-wise in (a) the sub-optimality gaps of the arms, (b) $\varepsilon$, and
(c) the problem complexity that is expressible as the sum of two terms, one
characterising the complexity of standard fixed-budget BAI (without privacy
constraints), and the other accounting for the $\varepsilon$-DP constraint.
Additionally, we present some auxiliary results that contribute to the
derivation of the lower bound on the error probability. These results, we
posit, may be of independent interest and could prove instrumental in proving
lower bounds on error probabilities in several other bandit problems. Whereas
prior works provide results for BAI in the fixed-budget regime without privacy
constraints or in the fixed-confidence regime with privacy constraints, our
work fills the gap in the literature by providing the results for BAI in the
fixed-budget regime under the $\varepsilon$-DP constraint.