2026/08/02 by Lisu Wang, Yilun Chen, Jiaqi Lu
Computer Science · Mathematics · #cs.LG #math.PR #stat.ML
arxiv created 2026/08/02 · arxiv published 2026/08/02 · arxiv updated 2026/08/04
Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected Z-statistic. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order √(log T), and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate 1/√(log T). We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.