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 $K$-armed stochastic bandits and consider cumulative regretbounds up to time $T$. We are interested in strategies achieving simultaneouslya distribution-free regret bound of optimal order $\sqrt{KT}$ and adistribution-dependent regret that is asymptotically optimal, that is, matchingthe $\kappa\ln T$ lower bound by Lai and Robbins (1985) and Burnetas andKatehakis (1996), where $\kappa$ is the optimal problem-dependent constant.This constant $\kappa$ depends on the model $\mathcal{D}$ considered (thefamily of possible distributions over the arms). M\'enard and Garivier (2017)provided strategies achieving such a bi-optimality in the parametric case ofmodels given by one-dimensional exponential families, while Lattimore (2016,2018) did so for the family of (sub)Gaussian distributions with variance lessthan $1$. We extend this result to the non-parametric case of all distributionsover $[0,1]$. We do so by combining the MOSS strategy by Audibert and Bubeck(2009), which enjoys a distribution-free regret bound of optimal order$\sqrt{KT}$, and the KL-UCB strategy by Capp\'e et al. (2013), for which weprovide in passing the first analysis of an optimal distribution-dependent$\kappa\ln T$ regret bound in the model of all distributions over $[0,1]$. Wewere able to obtain this non-parametric bi-optimality result while working hardto streamline the proofs (of previously known regret bounds and thus of the newanalyses carried out); a second merit of the present contribution is thereforeto provide a review of proofs of classical regret bounds for index-basedstrategies for $K$-armed stochastic bandits.

KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints