Authors: Koulik Khamaru, Cun-Hui Zhang
Abstract: In this paper, we discuss the asymptotic behavior of the Upper Confidence
Bound (UCB) algorithm in the context of multiarmed bandit problems and discuss
its implication in downstream inferential tasks. While inferential tasks become
challenging when data is collected in a sequential manner, we argue that this
problem can be alleviated when the sequential algorithm at hand satisfies
certain stability property. This notion of stability is motivated from the
seminal work of Lai and Wei (1982). Our first main result shows that such a
stability property is always satisfied for the UCB algorithm, and as a result
the sample means for each arm are asymptotically normal. Next, we examine the
stability properties of the UCB algorithm when the number of arms $K$ is
allowed to grow with the number of arm pulls $T$. We show that in such a case
the arms are stable when $\frac{\log K}{\log T} \rightarrow 0$, and the number
of near-optimal arms are large.
Source: http://arxiv.org/abs/2408.04595v1
