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

This paper proposes near-optimal algorithms for the pure-exploration linearbandit problem in the fixed confidence and fixed budget settings. Leveragingideas from the theory of suprema of empirical processes, we provide analgorithm whose sample complexity scales with the geometry of the instance andavoids an explicit union bound over the number of arms. Unlike previousapproaches which sample based on minimizing a worst-case variance (e.g.G-optimal design), we define an experimental design objective based on theGaussian-width of the underlying arm set. We provide a novel lower bound interms of this objective that highlights its fundamental role in the samplecomplexity. The sample complexity of our fixed confidence algorithm matchesthis lower bound, and in addition is computationally efficient forcombinatorial classes, e.g. shortest-path, matchings and matroids, where thearm sets can be exponentially large in the dimension. Finally, we propose thefirst algorithm for linear bandits in the the fixed budget setting. Itsguarantee matches our lower bound up to logarithmic factors.

An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits