A Joint CLT for UCB-Generated Data

We characterize a joint central limit theorem (CLT) for the number of pulls and the sample mean rewards of the arms in a stochastic two-armed bandit under generalized UCB1. The result explicitly describes sample adaptivity across large, moderate, and small arm-gap regimes. Under UCB1, the typical deviation of the number of pulls changes from $\Theta(\sqrt{\log T})$ in the constant-gap setting to $\Theta(T/\sqrt{\log T})$ in the moderate-to-small gap regimes; the same joint CLT yields a CLT for pseudo-regret. The joint CLT also explicitly characterizes the asymptotic correlation between the number of pulls and sample means. Our analysis is based on a perturbation argument that characterizes the stochastic bandit dynamics beyond their fluid approximation.