Inference with the Upper Confidence Bound Algorithm
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:CFH7U4E4record.jsonopen to challenge →
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Bandit Simulation for Average Reward Inference
BSI fits an environment simulator from bandit data and propagates parameter uncertainty to produce asymptotically valid confidence intervals for mean reward under arbitrary evaluation policies, including black-box ada...
-
Statistical Inference for Misspecified Contextual Bandits
Develops IPW-Z estimation framework for misspecified contextual bandits, establishing consistency and asymptotic normality under scaled inverse-propensity convergence for marginal moment targets.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.