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

The multi-armed bandit problem is a popular model for studyingexploration/exploitation trade-off in sequential decision problems. Manyalgorithms are now available for this well-studied problem. One of the earliestalgorithms, given by W. R. Thompson, dates back to 1933. This algorithm,referred to as Thompson Sampling, is a natural Bayesian algorithm. The basicidea is to choose an arm to play according to its probability of being the bestarm. Thompson Sampling algorithm has experimentally been shown to be close tooptimal. In addition, it is efficient to implement and exhibits severaldesirable properties such as small regret for delayed feedback. However,theoretical understanding of this algorithm was quite limited. In this paper,for the first time, we show that Thompson Sampling algorithm achieveslogarithmic expected regret for the multi-armed bandit problem. More precisely,for the two-armed bandit problem, the expected regret in time $T$ is$O(\frac{\ln T}{\Delta} + \frac{1}{\Delta^3})$. And, for the $N$-armed banditproblem, the expected regret in time $T$ is $O([(\sum_{i=2}^N\frac{1}{\Delta_i^2})^2] \ln T)$. Our bounds are optimal but for the dependenceon $\Delta_i$ and the constant factors in big-Oh.

Analysis of Thompson Sampling for the multi-armed bandit problem