mlsanityData to 14 Oct 2026

Linear Contextual Bandits with Adversarial Corruptions

arXiv 2110.12615 ↗First posted 25 Oct 2021cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We study the linear contextual bandit problem in the presence of adversarial corruption, where the interaction between the player and a possibly infinite decision set is contaminated by an adversary that can corrupt the reward up to a corruption level C measured by the sum of the largest alteration on rewards in each round. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination C. The key algorithmic design includes (1) a multi-level partition scheme of the observed data, (2) a cascade of confidence sets that are adaptive to the level of the corruption, and (3) a variance-aware confidence set construction that can take advantage of low-variance reward. We further prove that the regret of the proposed algorithm is tildeO(C2d√sumt = 1T σt2 + C2R√dT), where d is the dimension of context vectors, T is the number of rounds, R is the range of noise and σt2,t=1ldots,T are the variances of instantaneous reward. We also prove a gap-dependent regret bound for the proposed algorithm, which is instance-dependent and thus leads to better performance on good practical instances. To the best of our knowledge, this is the first variance-aware corruption-robust algorithm for contextual bandits. Experiments on synthetic data corroborate our theory.

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). Builds on 21 of its 38 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

21 of 38 references.

References · 21

  1. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  3. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  4. 2016Corralling a Band of Bandit Algorithmscited by 100
  5. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  6. 2018Learning to Optimize under Non-Stationaritycited by 85
  7. 2021Adapting to Misspecification in Contextual Banditscited by 81
  8. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  9. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  10. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  11. 2019Model selection for contextual banditscited by 60
  12. 2018Adversarial Attacks on Stochastic Banditscited by 57
9 more
  1. 2019Data Poisoning Attacks on Stochastic Banditscited by 53
  2. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  3. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  4. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  5. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 43
  6. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  7. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  8. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 24
  9. 2013Linear Bandits in High Dimension and Recommendation Systemscited by 22

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 10; 2024: 7; 2025: 0; 2026: 1.

21 papers.

Sort:

By area:

  1. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  2. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  3. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  4. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  5. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 12
  6. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  7. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  8. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  9. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  10. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  11. 2023Adversarial Attacks on Adversarial Banditscited by 6
  12. 2024Strategic Linear Contextual Banditscited by 5
9 more
  1. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  2. 2023Robust Causal Bandits for Linear Modelscited by 4
  3. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  4. 2023Online Corrupted User Detection and Regret Minimizationcited by 3
  5. 2024Non-Stationary Latent Auto-Regressive Banditscited by 3
  6. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  7. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  8. 2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
  9. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1