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 derive an algorithm that achieves the optimal (within constants)pseudo-regret in both adversarial and stochastic multi-armed bandits withoutprior knowledge of the regime and time horizon. The algorithm is based ononline mirror descent (OMD) with Tsallis entropy regularization with power$\alpha=1/2$ and reduced-variance loss estimators. More generally, we define anadversarial regime with a self-bounding constraint, which includes stochasticregime, stochastically constrained adversarial regime (Wei and Luo), andstochastic regime with adversarial corruptions (Lykouris et al.) as specialcases, and show that the algorithm achieves logarithmic regret guarantee inthis regime and all of its special cases simultaneously with the adversarialregret guarantee.} The algorithm also achieves adversarial and stochasticoptimality in the utility-based dueling bandit setting. We provide empiricalevaluation of the algorithm demonstrating that it significantly outperformsUCB1 and EXP3 in stochastic environments. We also provide examples ofadversarial environments, where UCB1 and Thompson Sampling exhibit almostlinear regret, whereas our algorithm suffers only logarithmic regret. To thebest of our knowledge, this is the first example demonstrating vulnerability ofThompson Sampling in adversarial environments. Last, but not least, we presenta general stochastic analysis and a general adversarial analysis of OMDalgorithms with Tsallis entropy regularization for $\alpha\in[0,1]$ and explainthe reason why $\alpha=1/2$ works best.

Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits