Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite $(1+\epsilon)$-th moments for some $\epsilon \in (0,1]$. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance assumption and suffers from computational inefficiency. We propose the first computationally efficient algorithm based on online mirror descent that is robust to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs $\mathcal{O}(t\log T)$ computational cost per round, our algorithm reduces this to $\mathcal{O}(1)$ per round. We establish an additive regret bound consisting of a term depending on the $(1+\epsilon)$-moment bound of the noise and a term depending on the total amount of corruption. This bound unifies and extends previous guarantees for (generalized) linear contextual bandits under adversarial corruption and heavy-tailed noise. In particular, when $\epsilon = 1$, it recovers existing guarantees under finite-variance assumptions. When no corruption is present, it achieves the same regret rate as existing results for linear contextual bandits with heavy-tailed noise in the general setting. Moreover, the algorithm requires only upper bounds on the noise moment and the total amount of corruption, while still guaranteeing sublinear regret.