Inference with the Upper Confidence Bound Algorithm

Autor:	Khamaru, Koulik, Zhang, Cun-Hui
Rok vydání:	2024
Předmět:	Statistics - Machine Learning Computer Science - Artificial Intelligence Computer Science - Machine Learning Electrical Engineering and Systems Science - Systems and Control Mathematics - Statistics Theory
Druh dokumentu:	Working Paper
Popis:	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. Comment: 17 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.04595 Zobrazit plný text záznamu View this record from Arxiv