2017/02/16 by Max Simchowitz, Simchowitz, Max, Kevin Jamieson +3 · 3 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1702.05186
openalex publication_date 2017/02/16 · openalex created_date 2023/04/27 · openalex updated_date 2026/07/28
We propose a novel technique for analyzing adaptive sampling called the em\nSimulator. Our approach differs from the existing methods by considering not\nhow much information could be gathered by any fixed sampling strategy, but how\ndifficult it is to distinguish a good sampling strategy from a bad one given\nthe limited amount of data collected up to any given time. This change of\nperspective allows us to match the strength of both Fano and change-of-measure\ntechniques, without succumbing to the limitations of either method. For\nconcreteness, we apply our techniques to a structured multi-arm bandit problem\nin the fixed-confidence pure exploration setting, where we show that the\nconstraints on the means imply a substantial gap between the\nmoderate-confidence sample complexity, and the asymptotic sample complexity as\n\δ \→ 0 found in the literature. We also prove the first instance-based\nlower bounds for the top-k problem which incorporate the appropriate\nlog-factors. Moreover, our lower bounds zero-in on the number of times each\n\individual arm needs to be pulled, uncovering new phenomena which are\ndrowned out in the aggregate sample complexity. Our new analysis inspires a\nsimple and near-optimal algorithm for the best-arm and top-k identification,\nthe first em practical algorithm of its kind for the latter problem which\nremoves extraneous log factors, and outperforms the state-of-the-art in\nexperiments.\n