In “Analysis of Thompson Sampling for the multi-armed bandit problem“, Agrawal and Goyal show that Thompson Sampling (“The basic idea is to choose an arm to play according to its probability of being the best arm.”) has logarithmic regret. More specifically, if there are $n$ bandits and the regret $R$ at time $T$ is defined by

$$R(T) := \sum_{t=1}^T (\mu^* – \mu_{i(t)})$$

where $\mu_i$ is the expected return of the $i$th arm and $\mu^* = \max_{i = 1, \ldots, n} \mu_i$, then

$$E[R(T)] \in O\left(\left(\sum_{i\neq i^*} 1/\Delta_i^2\right)^2 \log T \right)$$

where $\mu(i^*) = \mu^*$ and $\Delta_i = \mu^* – \mu_i$.

Related Posts via Categories

• Link/Book(pdf): “Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems”
• Link: AlphaGo Wins against one of the best Go Players on the Planet
• Ted Dunning on Bandits
• “Stochastic Superoptimization” and “Programming by Optimization”
• “Generalized Thompson sampling for sequential decision-making and causal inference”
• “Trustworthy Online Controlled Experiments: Five Puzzling Outcomes Explained”
• “An Empirical Evaluation of Thompson Sampling”
• “Linear Bandits in High Dimension and Recommendation Systems”
• “A Survey of Monte Carlo Tree Search Methods”
• Schwarzenegger Bandit Success Formula