CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded
  Stochastic Corruption
Shubhada Agrawal Timothée Mathieu Debabrota Basu Odalric-Ambrym Maillard
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\in (0,\frac{1}{2})$, 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 $\frac{1}{2}$. Furthermore, we
develop a tight concentration result for medians in the presence of arbitrary
corruptions, even with $\varepsilon$ values up to $\frac{1}{2}$, which may be
of independent interest. We also discuss an extension of the algorithm for
handling misspecification in Gaussian model.