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+ϵ)-th moments for some ϵ∈ (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 𝒪(tlog T) computational cost per round, our algorithm reduces this to 𝒪(1) per round. We establish an additive regret bound consisting of a term depending on the (1+ϵ)-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 ϵ = 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.