Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
Abstract Overview
This paper studies fixed-budget best-arm identification for Bernoulli bandits under pure ε-differential privacy, where the entire adaptive transcript must be protected. It introduces a privacy-aware transportation exponent that characterizes the asymptotic decay rate of the recommendation error and differs from the fixed-confidence private BAI quantity because the divergence is evaluated in the reverse argument order. Guided by this exponent, the authors propose AO-Pri-BAI, an adaptive algorithm that combines Laplace-tree private running estimates, challenger sampling from Gibbs distributions, and AdaHedge-based allocation updates. The paper provides both an information-theoretic lower bound and an algorithmic upper bound, and also reports experiments against private baselines.
Novelty
The paper's main novelty is the identification of a new privacy-aware transportation exponent for fixed-budget private best-arm identification, which is not the same as the fixed-confidence characterization because the KL-asymmetric divergence appears in alternative-to-true order. Algorithmically, it pairs this exponent with a private min-max learning procedure that uses Laplace-tree continual release and Gibbs-sampled challengers rather than standard non-private empirical or posterior updates.
Results
The authors prove that any consistent ε-DP policy with a limiting allocation cannot asymptotically beat the proposed exponent, and that AO-Pri-BAI is ε-DP for the full transcript. They further show that AO-Pri-BAI achieves an asymptotic upper bound whose exponent matches the lower-bound benchmark, establishing asymptotic optimality in their sense. In experiments, AO-Pri-BAI outperforms private benchmark methods in moderate-to-large budget regimes and approaches near-perfect accuracy on the reported synthetic instances.
Key Points
- The work formulates fixed-budget private best-arm identification through an instance-dependent privacy-aware transportation game, yielding a new lower-bound exponent.
- AO-Pri-BAI maintains private running means with Laplace trees and adaptively learns sampling allocations via a min-learner/max-learner interaction with AdaHedge.
- Theoretical guarantees include pure ε-differential privacy and exponent matching between lower and upper bounds, while experiments show stronger large-budget performance than the reported private baselines.