2019/05/27 by Jaehyeok Shin, Aaditya Ramdas, Shin, Jaehyeok +3 · 12 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Computer science #Detector #Estimator #Machine Learning and Algorithms #Machine learning #Mathematical optimization #Mathematics #Monotonic function #Regret #Reinforcement Learning in Robotics #Sample (material) #Sampling (signal processing) #Statistics #Thompson sampling #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.1905.11397
published in arXiv (Cornell University) (Cornell University) · 21 pages. Advances in Neural Information Processing Systems 32 (NeurIPS 2019, Spotlight Presentation)
openalex publication_date 2019/05/27 · arxiv created 2019/10/26 · arxiv updated 2019/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that in stochastic multi-armed bandits (MAB), the sample mean of an arm is typically not an unbiased estimator of its true mean. In this paper, we decouple three different sources of this selection bias: adaptive sampling of arms, adaptive stopping of the experiment, and adaptively choosing which arm to study. Through a new notion called ``optimism'' that captures certain natural monotonic behaviors of algorithms, we provide a clean and unified analysis of how optimistic rules affect the sign of the bias. The main takeaway message is that optimistic sampling induces a negative bias, but optimistic stopping and optimistic choosing both induce a positive bias. These results are derived in a general stochastic MAB setup that is entirely agnostic to the final aim of the experiment (regret minimization or best-arm identification or anything else). We provide examples of optimistic rules of each type, demonstrate that simulations confirm our theoretical predictions, and pose some natural but hard open problems.