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 regret of Thompson sampling (TS) algorithms for exponentialfamily bandits, where the reward distribution is from a one-dimensionalexponential family, which covers many common reward distributions includingBernoulli, Gaussian, Gamma, Exponential, etc. We propose a Thompson samplingalgorithm, termed ExpTS, which uses a novel sampling distribution to avoid theunder-estimation of the optimal arm. We provide a tight regret analysis forExpTS, which simultaneously yields both the finite-time regret bound as well asthe asymptotic regret bound. In particular, for a $K$-armed bandit withexponential family rewards, ExpTS over a horizon $T$ is sub-UCB (a strongcriterion for the finite-time regret that is problem-dependent), minimaxoptimal up to a factor $\sqrt{\log K}$, and asymptotically optimal, forexponential family rewards. Moreover, we propose ExpTS$^+$, by adding a greedyexploitation step in addition to the sampling distribution used in ExpTS, toavoid the over-estimation of sub-optimal arms. ExpTS$^+$ is an anytime banditalgorithm and achieves the minimax optimality and asymptotic optimalitysimultaneously for exponential family reward distributions. Our prooftechniques are general and conceptually simple and can be easily applied toanalyze standard Thompson sampling with specific reward distributions.

Finite-Time Regret of Thompson Sampling Algorithms for Exponential Family Multi-Armed Bandits