The Typical Behavior of Bandit Algorithms

Lin Fan, Peter W. Glynn

We establish strong laws of large numbers and central limit theorems for the regret of two of the most popular bandit algorithms: Thompson sampling and UCB. Here, our characterizat…