mlsanityData to 7 Oct 2026

Better Algorithms for Stochastic Bandits with Adversarial Corruptions

arXiv 1902.08647 ↗First posted 22 Feb 2019cs.LG stat.MLcited by 91

Not on the map. Why?

Abstract (arXiv)

We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount of corruption with virtually no degradation in performance.

Key facts. Cited by 91 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 29; 2022: 16; 2023: 17; 2024: 12; 2025: 8; 2026: 9.

91 papers.

Sort:

By area:

  1. 2021Adapting to Misspecification in Contextual Banditscited by 81
  2. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  3. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  4. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  7. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  8. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  9. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  10. 2022On the Complexity of Adversarial Decision Makingcited by 32
  11. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  12. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
38 more
  1. 2022Learning in Stackelberg Games with Non-myopic Agentscited by 29
  2. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  3. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  4. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  5. 2021Defense Against Reward Poisoning Attacks in Reinforcement Learningcited by 20
  6. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  7. 2021Exploiting Heterogeneity in Robust Federated Best-Arm Identificationcited by 20
  8. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  9. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  10. 2021One More Step Towards Reality: Cooperative Bandits with Imperfect Communicationcited by 15
  11. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  12. 2023Multi-channel Autobidding with Budget and ROI Constraintscited by 14
  13. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  14. 2021Bandit Algorithms for Precision Medicinecited by 12
  15. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  16. 2021Bias-Robust Bayesian Optimization via Dueling Banditscited by 11
  17. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  18. 2022Best of Both Worlds Model Selectioncited by 11
  19. 2021When Are Linear Stochastic Bandits Attackable?cited by 10
  20. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  21. 2021Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verificationcited by 9
  22. 2022Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learningcited by 9
  23. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  24. 2024Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptionscited by 8
  25. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  26. 2021Combinatorial Bandits under Strategic Manipulationscited by 6
  27. 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
  28. 2022Federated Multi-Armed Bandits Under Byzantine Attackscited by 6
  29. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  30. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  31. 2021Multiplicative Reweighting for Robust Neural Network Optimizationcited by 4
  32. 2021Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximationscited by 4
  33. 2021Robust Online Convex Optimization in the Presence of Outlierscited by 4
  34. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  35. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  36. 2022Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Boundscited by 4
  37. 2022Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimizationcited by 4
  38. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4

50 most cited of 91 All 91 (JSON)