Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
Abstract
Best arm identification under differential privacy is a pure-exploration problem in which both statistical efficiency and privacy protection must be achieved simultaneously. We study fixed-budget best arm identification for bandits under pure ε-differential privacy, where the learner must recommend an arm after a prescribed sampling budget while protecting the full transcript. We prove that the optimal exponential decay rate of the error probability is upper bounded by an instance-dependent privacy-aware transportation exponent that differs from the analogous quantity used to characterize the stopping time in fixed-confidence analysis by Jourdan and Azize [2025]. Guided by this exponent, we propose AO-Pri-BAI, an adaptive algorithm that maintains private running estimates through Laplace-tree mechanisms and learns a sampling design through a min--max interaction between hard alternatives and arm allocations. We prove that AO-Pri-BAI satisfies pure ε-differential privacy. We also establish that the exponent of the failure probability of AO-Pri-BAI matches the privacy-aware benchmark. Numerical studies show that even in the non-asymptotic setting, AO-Pri-BAI outperforms benchmark algorithms on various instances, complementing the theoretical analyses.
Related
- Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
- Optimal Conversion from Zero-Concentrated to Gaussian Differential Privacy
- Prophet Inequalities under Local Differential Privacy
- A class of asymptotically optimal authentication codes with secrecy
- Performative Privacy: When Differential Privacy Maximizes Utility
BibTeX
@misc{chen2026asymptotically,
title = {{Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy}},
author = {Keqin Chen and Jie Bian and Yulian Wu and Vincent Y. F. Tan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04600},
eprint = {2610.04600},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04600},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
AU - Keqin Chen
AU - Jie Bian
AU - Yulian Wu
AU - Vincent Y. F. Tan
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04600
UR - https://arxiv.org/abs/2610.04600
AB - Best arm identification under differential privacy is a pure-exploration problem in which both statistical efficiency and privacy protection must be achieved simultaneously. We study fixed-budget best arm identification for bandits under pure ε-differential privacy, where the learner must recommend an arm after a prescribed sampling budget while protecting the full transcript. We prove that the optimal exponential decay rate of the error probability is upper bounded by an instance-dependent privacy-aware transportation exponent that differs from the analogous quantity used to characterize the stopping time in fixed-confidence analysis by Jourdan and Azize [2025]. Guided by this exponent, we propose AO-Pri-BAI, an adaptive algorithm that maintains private running estimates through Laplace-tree mechanisms and learns a sampling design through a min--max interaction between hard alternatives and arm allocations. We prove that AO-Pri-BAI satisfies pure ε-differential privacy. We also establish that the exponent of the failure probability of AO-Pri-BAI matches the privacy-aware benchmark. Numerical studies show that even in the non-asymptotic setting, AO-Pri-BAI outperforms benchmark algorithms on various instances, complementing the theoretical analyses.
ER -