Best Arm Identification for Contaminated Bandits
원문 초록
This paper studies active learning in the context of robust statistics. Specifically, we propose a variant of the Best Arm Identification problem for \emph{contaminated bandits}, where each arm pull has probability $\varepsilon$ of generating a sample from an arbitrary contamination distribution instead of the true underlying distribution. The goal is to identify the best (or approximately best) true distribution with high probability, with a secondary goal of providing guarantees on the quality of this distribution. The primary challenge of the contaminated bandit setting is that the true distributions are only partially identifiable, even with infinite samples. To address this, we develop tight, non-asymptotic sample complexity bounds for high-probability estimation of the first two robust moments (median and median absolute deviation) from contaminated samples. These concentration inequalities are the main technical contributions of the paper and may be of independent interest. Using these results, we adapt several classical Best Arm Identification algorithms to the contaminated bandit setting and derive sample complexity upper bounds for our problem. Finally, we provide matching information-theoretic lower bounds on the sample complexity (up to a small logarithmic factor).
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Near-Polynomially Competitive Active Logistic Regression
CriticLean: Critic-Guided Reinforcement Learning for Mathematical Formalization
Active Learning for Manifold Gaussian Process Regression
The Catechol Benchmark: Time-series Solvent Selection Data for Few-shot Machine Learning
Info-Coevolution: An Efficient Framework for Data Model Coevolution
ALINE: Joint Amortization for Bayesian Inference and Active Data Acquisition
토론
이 논문과 연결된 포럼 글이 아직 없습니다.