Robustness Guarantees for Mode Estimation with an Application to Bandits
This work addresses robustness in mode estimation and bandits for applications with outliers or adversarial corruptions, offering incremental improvements by extending existing bandit frameworks to modal settings.
The paper tackles the lack of robustness guarantees in mode estimation under adversarial data contamination, providing precise robustness and privacy guarantees, and applies this to multi-armed bandits by using modes instead of means, proving regret guarantees for various bandit problems and showing robustness to adversarial noise in simulations.
Mode estimation is a classical problem in statistics with a wide range of applications in machine learning. Despite this, there is little understanding in its robustness properties under possibly adversarial data contamination. In this paper, we give precise robustness guarantees as well as privacy guarantees under simple randomization. We then introduce a theory for multi-armed bandits where the values are the modes of the reward distributions instead of the mean. We prove regret guarantees for the problems of top arm identification, top m-arms identification, contextual modal bandits, and infinite continuous arms top arm recovery. We show in simulations that our algorithms are robust to perturbation of the arms by adversarial noise sequences, thus rendering modal bandits an attractive choice in situations where the rewards may have outliers or adversarial corruptions.