2019/02/02 by Jaehyeok Shin, Aaditya Ramdas, Shin, Jaehyeok +3 · 19 citations
Computer Science · Decision Sciences · Mathematics · Psychology · #Advanced Bandit Algorithms Research #Artificial intelligence #Computer science #Consistency (knowledge bases) #Estimator #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Intuition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Martingale (probability theory) #Mathematical proof #Mathematics #Mean squared error #Nonparametric statistics #Psychology #Sample (material) #Sample size determination #Statistics #Statistics Theory (math.ST) #Upper and lower bounds #cs.LG #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.1902.00746
published in arXiv (Cornell University) (Cornell University) · 48 pages
openalex publication_date 2019/02/02 · arxiv created 2021/04/30 · arxiv updated 2021/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
The sample mean is among the most well studied estimators in statistics, having many desirable properties such as unbiasedness and consistency. However, when analyzing data collected using a multi-armed bandit (MAB) experiment, the sample mean is biased and much remains to be understood about its properties. For example, when is it consistent, how large is its bias, and can we bound its mean squared error? This paper delivers a thorough and systematic treatment of the bias, risk and consistency of MAB sample means. Specifically, we identify four distinct sources of selection bias (sampling, stopping, choosing and rewinding) and analyze them both separately and together. We further demonstrate that a new notion of effective sample size can be used to bound the risk of the sample mean under suitable loss functions. We present several carefully designed examples to provide intuition on the different sources of selection bias we study. Our treatment is nonparametric and algorithm-agnostic, meaning that it is not tied to a specific algorithm or goal. In a nutshell, our proofs combine variational representations of information-theoretic divergences with new martingale concentration inequalities.