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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

This paper considers a stochastic Multi-Armed Bandit (MAB) problem with dualobjectives: (i) quick identification and commitment to the optimal arm, and(ii) reward maximization throughout a sequence of $T$ consecutive rounds.Though each objective has been individually well-studied, i.e., best armidentification for (i) and regret minimization for (ii), the simultaneousrealization of both objectives remains an open problem, despite its practicalimportance. This paper introduces \emph{Regret Optimal Best Arm Identification}(ROBAI) which aims to achieve these dual objectives. To solve ROBAI with bothpre-determined stopping time and adaptive stopping time requirements, wepresent an algorithm called EOCP and its variants respectively, which not onlyachieve asymptotic optimal regret in both Gaussian and general bandits, butalso commit to the optimal arm in $\mathcal{O}(\log T)$ rounds withpre-determined stopping time and $\mathcal{O}(\log^2 T)$ rounds with adaptivestopping time. We further characterize lower bounds on the commitment time(equivalent to the sample complexity) of ROBAI, showing that EOCP and itsvariants are sample optimal with pre-determined stopping time, and almostsample optimal with adaptive stopping time. Numerical results confirm ourtheoretical analysis and reveal an interesting "over-exploration" phenomenoncarried by classic UCB algorithms, such that EOCP has smaller regret eventhough it stops exploration much earlier than UCB, i.e., $\mathcal{O}(\log T)$versus $\mathcal{O}(T)$, which suggests over-exploration is unnecessary andpotentially harmful to system performance.

Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms