mlsanityData to 7 Oct 2026

Stochastic Linear Bandits Robust to Adversarial Attacks

arXiv 2007.03285 ↗First posted 7 Jul 2020stat.ML cs.LGcited by 65

Not on the map. Why?

Abstract (arXiv)

We consider a stochastic linear bandit problem in which the rewards are not only subject to random noise, but also adversarial attacks subject to a suitable budget C (i.e., an upper bound on the sum of corruption magnitudes across the time horizon). We provide two variants of a Robust Phased Elimination algorithm, one that knows C and one that does not. Both variants are shown to attain near-optimal regret in the non-corrupted case C = 0, while incurring additional additive terms respectively having a linear and quadratic dependency on C in general. We present algorithm independent lower bounds showing that these additive terms are near-optimal. In addition, in a contextual setting, we revisit a setup of diverse contexts, and show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing C.

Key facts. Cited by 65 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 10; 2023: 15; 2024: 10; 2025: 4; 2026: 8.

65 papers.

Sort:

By area:

  1. 2021Federated Linear Contextual Banditscited by 61
  2. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  3. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  4. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  5. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  6. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  7. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  8. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  9. 2022Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learningcited by 21
  10. 2021Defense Against Reward Poisoning Attacks in Reinforcement Learningcited by 20
  11. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  12. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
38 more
  1. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  2. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 19
  3. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  4. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  5. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  6. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  7. 2021Bias-Robust Bayesian Optimization via Dueling Banditscited by 11
  8. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  9. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  10. 2021Syndicated Bandits: A Framework for Auto Tuning Hyper-parameters in Contextual Bandit Algorithmscited by 10
  11. 2021When Are Linear Stochastic Bandits Attackable?cited by 10
  12. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  13. 2021Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verificationcited by 9
  14. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  15. 2021Game Redesign in No-regret Game Playingcited by 8
  16. 2021Combinatorial Bandits under Strategic Manipulationscited by 6
  17. 2022Federated Multi-Armed Bandits Under Byzantine Attackscited by 6
  18. 2023Adversarial Attacks on Adversarial Banditscited by 6
  19. 2023Adversarial Attacks on Online Learning to Rank with Stochastic Click Modelscited by 6
  20. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  21. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  22. 2021Adversarial Attacks on Gaussian Process Banditscited by 5
  23. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  24. 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 4
  25. 2022Robust Contextual Linear Banditscited by 4
  26. 2023Optimal Sample Selection Through Uncertainty Estimation and Its Application in Deep Learningcited by 4
  27. 2023Robust Causal Bandits for Linear Modelscited by 4
  28. 2024Strategic Linear Contextual Banditscited by 4
  29. 2021Efficient Action Poisoning Attacks on Linear Contextual Banditscited by 3
  30. 2023Online Corrupted User Detection and Regret Minimizationcited by 3
  31. 2023Online Robust Mean Estimationcited by 3
  32. 2025Linear Bandits with Partially Observable Featurescited by 3
  33. 2025Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysiscited by 3
  34. 2025Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injectioncited by 3
  35. 2022Distributed Stochastic Bandit Learning with Delayed Context Observationcited by 2
  36. 2024Stealthy Adversarial Attacks on Stochastic Multi-Armed Banditscited by 2
  37. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  38. 2024Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Duelingcited by 2

50 most cited of 65 All 65 (JSON)