  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 characterizations of the regret distribution complement the
characterizations of the tail of the regret distribution recently developed by
Fan and Glynn (2021) (arXiv:2109.13595). The tail characterizations there are
associated with atypical bandit behavior on trajectories where the optimal arm
mean is under-estimated, leading to mis-identification of the optimal arm and
large regret. In contrast, our SLLN's and CLT's here describe the typical
behavior and fluctuation of regret on trajectories where the optimal arm mean
is properly estimated. We find that Thompson sampling and UCB satisfy the same
SLLN and CLT, with the asymptotics of both the SLLN and the (mean) centering
sequence in the CLT matching the asymptotics of expected regret. Both the mean
and variance in the CLT grow at $\log(T)$ rates with the time horizon $T$.
Asymptotically as $T \to \infty$, the variability in the number of plays of
each sub-optimal arm depends only on the rewards received for that arm, which
indicates that each sub-optimal arm contributes independently to the overall
CLT variance.
