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 consider the problem of combining and learning over a set of adversarialbandit algorithms with the goal of adaptively tracking the best one on the fly.The CORRAL algorithm of Agarwal et al. (2017) and its variants (Foster et al.,2020a) achieve this goal with a regret overhead of order$\widetilde{O}(\sqrt{MT})$ where $M$ is the number of base algorithms and $T$is the time horizon. The polynomial dependence on $M$, however, prevents onefrom applying these algorithms to many applications where $M$ is poly$(T)$ oreven larger. Motivated by this issue, we propose a new recipe to corral alarger band of bandit algorithms whose regret overhead has only\emph{logarithmic} dependence on $M$ as long as some conditions are satisfied.As the main example, we apply our recipe to the problem of adversarial linearbandits over a $d$-dimensional $\ell_p$ unit-ball for $p \in (1,2]$. Bycorralling a large set of $T$ base algorithms, each starting at a differenttime step, our final algorithm achieves the first optimal switching regret$\widetilde{O}(\sqrt{d S T})$ when competing against a sequence of comparatorswith $S$ switches (for some known $S$). We further extend our results to linearbandits over a smooth and strongly convex domain as well as unconstrainedlinear bandits.

Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits