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.

在多臂赌博机设置中，我们研究了最小化后悔问题，并引入了具有任意损坏的情况。我们对于某个给定的赌博机分布族，建立了与问题相关的后悔下界，并提出了 CRIMED 算法来实现该下界的精确后悔值，在已知方差的高斯分布赌博机环境下达到了渐近最优。此外，我们还对 CRIMED 的有限样本后悔性能进行了分析。