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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We address online combinatorial optimization when the player has a prior overthe adversary's sequence of losses. In this framework, Russo and Van Royproposed an information-theoretic analysis of Thompson Sampling based on theinformation ratio, resulting in optimal worst-case regret bounds. In this paperwe introduce three novel ideas to this line of work. First we propose a newquantity, the scale-sensitive information ratio, which allows us to obtain morerefined first-order regret bounds (i.e., bounds of the form $\sqrt{L^*}$ where$L^*$ is the loss of the best combinatorial action). Second we replace theentropy over combinatorial actions by a coordinate entropy, which allows us toobtain the first optimal worst-case bound for Thompson Sampling in thecombinatorial setting. Finally, we introduce a novel link between Bayesianagents and frequentist confidence intervals. Combining these ideas we show thatthe classical multi-armed bandit first-order regret bound $\tilde{O}(\sqrt{dL^*})$ still holds true in the more challenging and more general semi-banditscenario. This latter result improves the previous state of the art bound$\tilde{O}(\sqrt{(d+m^3)L^*})$ by Lykouris, Sridharan and Tardos.  Moreover we sharpen these results with two technical ingredients. The firstleverages a recent insight of Zimmert and Lattimore to replace Shannon entropywith more refined potential functions in the analysis. The second is a\emph{Thresholded} Thompson sampling algorithm, which slightly modifies theoriginal algorithm by never playing low-probability actions. This thresholdingresults in fully $T$-independent regret bounds when $L^*$ is almost surelyupper-bounded, which we show does not hold for ordinary Thompson sampling.

First-Order Bayesian Regret Analysis of Thompson Sampling