mlsanityData to 14 Oct 2026

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

arXiv 2603.15596 ↗First posted 16 Mar 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 (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 O(tlog T) computational cost, our algorithm reduces this to 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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 29 references that are in the map. First posted on arXiv 16 Mar 2026.

Builds on

16 of 29 references.

References · 16

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  3. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  4. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  5. 2017Adaptive Huber Regressioncited by 60
  6. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  7. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  8. 2018Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffscited by 31
  9. 2020Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffscited by 25
  10. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 24
  11. 2025Generalized Linear Bandits: Almost Optimal Regret with One-Pass Updatecited by 16
  12. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 14
4 more
  1. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
  2. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  3. 2025Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Updatecited by 5
  4. 2025Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewardscited by 4

Built on by

Not cited yet.