English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the best-arm identification problem in multi-armed bandits withstochastic, potentially private rewards, when the goal is to identify the armwith the highest quantile at a fixed, prescribed level. First, we propose a(non-private) successive elimination algorithm for strictly optimal best-armidentification, we show that our algorithm is $\delta$-PAC and we characterizeits sample complexity. Further, we provide a lower bound on the expected numberof pulls, showing that the proposed algorithm is essentially optimal up tologarithmic factors. Both upper and lower complexity bounds depend on a specialdefinition of the associated suboptimality gap, designed in particular for thequantile bandit problem, as we show when the gap approaches zero, best-armidentification is impossible. Second, motivated by applications where therewards are private, we provide a differentially private successive eliminationalgorithm whose sample complexity is finite even for distributions withinfinite support-size, and we characterize its sample complexity. Ouralgorithms do not require prior knowledge of either the suboptimality gap orother statistical information related to the bandit problem at hand.

Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme