# Best Arm Identification for Contaminated Bandits

arXiv: https://arxiv.org/abs/1802.09514 · HTML: https://mlsanity.com/paper/1802.09514/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2018.

## Built on by (most cited first, 24 of 24)

- [Universal Off-Policy Evaluation](https://mlsanity.com/paper/2104.12820/) (2021)
- [Off-Policy Risk Assessment in Contextual Bandits](https://mlsanity.com/paper/2104.08977/) (2021)
- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (2021)
- [Conformal Off-Policy Prediction in Contextual Bandits](https://mlsanity.com/paper/2206.04405/) (2022)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Private and Byzantine-Proof Cooperative Decision-Making](https://mlsanity.com/paper/2205.14174/) (2022)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (2021)
- [Enforcing Delayed-Impact Fairness Guarantees](https://mlsanity.com/paper/2208.11744/) (2022)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination](https://mlsanity.com/paper/2111.07458/) (2021)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Reward Delay Attacks on Deep Reinforcement Learning](https://mlsanity.com/paper/2209.03540/) (2022)
- [Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians](https://mlsanity.com/paper/2301.09024/) (2023)
- [Distribution-Free Model-Agnostic Regression Calibration via Nonparametric Methods](https://mlsanity.com/paper/2305.12283/) (2023)
- [Online Robust Mean Estimation](https://mlsanity.com/paper/2310.15932/) (2023)
- [Distributional Off-Policy Evaluation for Slate Recommendations](https://mlsanity.com/paper/2308.14165/) (2023)
- [CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption](https://mlsanity.com/paper/2309.16563/) (2023)
- [Sequential Decision Making on Unmatched Data using Bayesian Kernel Embeddings](https://mlsanity.com/paper/2210.13692/) (2022)
- [Pure Exploration under Mediators' Feedback](https://mlsanity.com/paper/2308.15552/) (2023)
- [Identifying the Best Arm in the Presence of Global Environment Shifts](https://mlsanity.com/paper/2408.12581/) (2024)
- [Best of both worlds: Stochastic & adversarial best-arm identification](https://mlsanity.com/paper/2604.14860/) (2026)
- [Robust Pareto Set Identification with Contaminated Bandit Feedback](https://mlsanity.com/paper/2206.02666/) (2022)
- [Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback](https://mlsanity.com/paper/2610.17760/) (2026)

## Abstract (arXiv)

This paper studies active learning in the context of robust statistics. Specifically, we propose a variant of the Best Arm Identification problem for 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).