mlsanityData to 14 Oct 2026

Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions

arXiv 2205.06811 ↗First posted 13 May 2022cs.LG stat.MLcited by 51

Not on the map. Why?

Abstract (arXiv)

We study the linear contextual bandit problem in the presence of adversarial corruption, where the reward at each round is corrupted by an adversary, and the corruption level (i.e., the sum of corruption magnitudes over the horizon) is C≥ 0. The best-known algorithms in this setting are limited in that they either are computationally inefficient or require a strong assumption on the corruption, or their regret is at least C times worse than the regret without corruption. In this paper, to overcome these limitations, we propose a new algorithm based on the principle of optimism in the face of uncertainty. At the core of our algorithm is a weighted ridge regression where the weight of each chosen action depends on its confidence up to some threshold. We show that for both known C and unknown C cases, our algorithm with proper choice of hyperparameter achieves a regret that nearly matches the lower bounds. Thus, our algorithm is nearly optimal up to logarithmic factors for both cases. Notably, our algorithm achieves the near-optimal regret for both corrupted and uncorrupted cases (C=0) simultaneously.

Key facts. Cited by 51 papers in the map (data through 14 Oct 2026). Builds on 19 of its 34 references that are in the map. First posted on arXiv 13 May 2022.

Builds on

19 of 34 references.

References · 19

  1. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  4. 2016Corralling a Band of Bandit Algorithmscited by 100
  5. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  6. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  7. 2021Adapting to Misspecification in Contextual Banditscited by 81
  8. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
  9. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  10. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  11. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  12. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
7 more
  1. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  2. 2017Misspecified Linear Banditscited by 42
  3. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  4. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 24
  5. 2013Linear Bandits in High Dimension and Recommendation Systemscited by 22
  6. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  7. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 16; 2024: 15; 2025: 6; 2026: 8.

51 papers.

Sort:

By area:

  1. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  2. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  3. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 43
  4. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  5. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  6. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  7. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  8. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  9. 2024Incentivized Learning in Principal-Agent Bandit Gamescited by 13
  10. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 12
  11. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  12. 2023Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewardscited by 11
38 more
  1. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  2. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  3. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  4. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  5. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  6. 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 5
  7. 2024Strategic Linear Contextual Banditscited by 5
  8. 2025Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customizationcited by 5
  9. 2022Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimizationcited by 4
  10. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  11. 2023Optimal Sample Selection Through Uncertainty Estimation and Its Application in Deep Learningcited by 4
  12. 2023Robust Causal Bandits for Linear Modelscited by 4
  13. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  14. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  15. 2024Non-stochastic Bandits With Evolving Observationscited by 4
  16. 2025Linear Bandits with Partially Observable Featurescited by 4
  17. 2023Online Corrupted User Detection and Regret Minimizationcited by 3
  18. 2023Federated Linear Bandits with Finite Adversarial Actionscited by 3
  19. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  20. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  21. 2025Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injectioncited by 3
  22. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  23. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  24. 2024Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Duelingcited by 2
  25. 2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
  26. 2023Corruption-Robust Lipschitz Contextual Searchcited by 1
  27. 2024Stochastic Bandits Robust to Adversarial Attackscited by 1
  28. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  29. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  30. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferencescited by 1
  31. 2023Learning to Seek: Multi-Agent Online Source Seeking Against Non-Stochastic Disturbancescited by 0
  32. 2023Robust Best-arm Identification in Linear Banditscited by 0
  33. 2025Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewardscited by 0
  34. 2026Learning to Attack: A Bandit Approach to Adversarial Context Poisoningcited by 0
  35. 2026Mixing Makes Markovian Contexts Cheap for Linear Banditscited by 0
  36. 2026Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noisecited by 0
  37. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0
  38. 2026Set Membership Estimation for Stochastic Linear Contextual Banditscited by 0

50 most cited of 51 All 51 (JSON)