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

Naoto Tani, Futoshi Futami
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6645-6676, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-tani26a, title = {Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise}, author = {Tani, Naoto and Futami, Futoshi}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6645--6676}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/tani26a/tani26a.pdf}, url = {https://proceedings.mlr.press/v337/tani26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise %A Naoto Tani %A Futoshi Futami %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-tani26a %I PMLR %P 6645--6676 %U https://proceedings.mlr.press/v337/tani26a.html %V 337 %X 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.
APA
Tani, N. & Futami, F.. (2026). Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6645-6676 Available from https://proceedings.mlr.press/v337/tani26a.html.

Related Material