aiqbench analysis
This paper addresses the intersection of pure-exploration bandit problems and differential privacy, deriving new theoretical bounds for error probability decay under fixed sampling budgets. The authors introduce an adaptive algorithm that leverages Laplace-tree mechanisms to simultaneously optimize statistical efficiency and privacy guarantees without sacrificing performance in non-asymptotic settings. This work advances the foundational understanding of how to balance utility and confidentiality in resource-constrained learning environments.
Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
arXiv:2610.04600v1 Announce Type: new 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 $\epsilon$-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 $\epsilon$-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.
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 $\epsilon$-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 $\epsilon$-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.
Machine Learning (cs.LG)
arXiv:2610.04600 [cs.LG]
(or arXiv:2610.04600v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.04600 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 263 words
Related coverage
Minimax and Bayes Optimal Best-Arm Identification
arXiv · Jul 20, 2026
Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
arXiv · Oct 16, 2026
Train-to-Test (T²) Scaling Laws: Why Reasoning Models Should Be Overtrained
Snorkel AI Blog · Aug 18, 2026
Hyperloom: A Multi-Agent Harness for Autonomous Inference Optimization on AMD GPUs
AMD · Sep 21, 2026