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 multi-armed bandit problem with subgaussian rewards. Theexplore-then-commit (ETC) strategy, which consists of an exploration phasefollowed by an exploitation phase, is one of the most widely used algorithms ina variety of online decision applications. Nevertheless, it has been shown inGarivier et al. (2016) that ETC is suboptimal in the asymptotic sense as thehorizon grows, and thus, is worse than fully sequential strategies such asUpper Confidence Bound (UCB). In this paper, we show that a variant of ETCalgorithm can actually achieve the asymptotic optimality for multi-armed banditproblems as UCB-type algorithms do and extend it to the batched bandit setting.Specifically, we propose a double explore-then-commit (DETC) algorithm that hastwo exploration and exploitation phases and prove that DETC achieves theasymptotically optimal regret bound. To our knowledge, DETC is the firstnon-fully-sequential algorithm that achieves such asymptotic optimality. Inaddition, we extend DETC to batched bandit problems, where (i) the explorationprocess is split into a small number of batches and (ii) the round complexityis of central interest. We prove that a batched version of DETC can achieve theasymptotic optimality with only a constant round complexity. This is the firstbatched bandit algorithm that can attain the optimal asymptotic regret boundand optimal round complexity simultaneously.

Double Explore-then-Commit: Asymptotic Optimality and Beyond