Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise
2026-03-16 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a problem where an algorithm tries to make decisions based on data that can be both noisy and partly manipulated. Unlike earlier work that needed stricter assumptions about noise and was slow to run, they design a faster method that handles weaker noise conditions and attacks. Their method updates its strategy efficiently over time and guarantees that errors grow slowly as more decisions are made. It also works without knowing how much noise or manipulation exists beforehand.
linear contextual banditsadversarial corruptionheavy-tailed noisefinite momentsonline mirror descentcomputational efficiencyregret boundssublinear regret
Authors
Naoto Tani, Futoshi Futami
Abstract
We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite $(1+ε)$-th moments for some $ε\in (0,1]$. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs $\mathcal{O}(t\log T)$ computational cost, our algorithm reduces this to $\mathcal{O}(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. In particular, when $ε= 1$, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.