# CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 64 references that are in the map.
- First posted on arXiv 28 Sep 2023.

## Builds on (most cited first, 25 of 25)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python](https://mlsanity.com/paper/1907.10121/) (2019)
- [Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model](https://mlsanity.com/paper/1506.00691/) (2015)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Best Arm Identification for Contaminated Bandits](https://mlsanity.com/paper/1802.09514/) (2018)
- [Learning Product Rankings Robust to Fake Users](https://mlsanity.com/paper/2009.05138/) (2020)
- [Concentrated Differential Privacy for Bandits](https://mlsanity.com/paper/2309.00557/) (2023)
- [Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Scheme](https://mlsanity.com/paper/2006.06792/) (2020)
- [Huber-Robust Confidence Sequences](https://mlsanity.com/paper/2301.09573/) (2023)
- [Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination](https://mlsanity.com/paper/2111.07458/) (2021)
- [Bandits Corrupted by Nature: Lower Bounds on Regret and Robust Optimistic Algorithm](https://mlsanity.com/paper/2203.03186/) (2022)

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

- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Truly Adapting to Adversarial Constraints in Constrained MABs](https://mlsanity.com/paper/2602.14543/) (2026)

## Abstract (arXiv)

We investigate the regret-minimisation problem in a multi-armed bandit setting with arbitrary corruptions. Similar to the classical setup, the agent receives rewards generated independently from the distribution of the arm chosen at each time. However, these rewards are not directly observed. Instead, with a fixed varepsilon∈ (0,frac12), the agent observes a sample from the chosen arm's distribution with probability 1-varepsilon, or from an arbitrary corruption distribution with probability varepsilon. Importantly, we impose no assumptions on these corruption distributions, which can be unbounded. In this setting, accommodating potentially unbounded corruptions, we establish a problem-dependent lower bound on regret for a given family of arm distributions. We introduce CRIMED, an asymptotically-optimal algorithm that achieves the exact lower bound on regret for bandits with Gaussian distributions with known variance. Additionally, we provide a finite-sample analysis of CRIMED's regret performance. Notably, CRIMED can effectively handle corruptions with varepsilon values as high as frac12. Furthermore, we develop a tight concentration result for medians in the presence of arbitrary corruptions, even with varepsilon values up to frac12, which may be of independent interest. We also discuss an extension of the algorithm for handling misspecification in Gaussian model.