mlsanityData to 14 Oct 2026

On Optimal Robustness to Adversarial Corruption in Online Decision Problems

arXiv 2109.10963 ↗First posted 22 Sep 2021stat.ML cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

This paper considers two fundamental sequential decision-making problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus on stochastic regimes in which an adversary may corrupt losses, and we investigate what level of robustness can be achieved against adversarial corruptions. The main contribution of this paper is to show that optimal robustness can be expressed by a square-root dependency on the amount of corruption. More precisely, we show that two classes of algorithms, anytime Hedge with decreasing learning rate and algorithms with second-order regret bounds, achieve O( fraclog NDelta + √ fracC log N Delta )-regret, where N, Delta, and C represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide a matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi-armed bandit problem, we also provide a nearly tight lower bound up to a logarithmic factor.

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

Builds on

23 of 45 references.

References · 23

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  2. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  3. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  4. 2014A Second-order Bound with Excess Lossescited by 95
  5. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  6. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  7. 2013Follow the Leader If You Can, Hedge If You Mustcited by 70
  8. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  9. 2018Adversarial Attacks on Stochastic Banditscited by 57
  10. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  11. 2019Data Poisoning Attacks on Stochastic Banditscited by 53
  12. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
11 more
  1. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  2. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  3. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  4. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  5. 2018On the optimality of the Hedge algorithm in the stochastic regimecited by 33
  6. 2020Prediction with Corrupted Expert Advicecited by 27
  7. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 24
  8. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  9. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  10. 2017Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularitiescited by 11
  11. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 7; 2023: 6; 2024: 3; 2025: 2; 2026: 2.

21 papers.

Sort:

  1. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
  2. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  3. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  4. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  5. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  6. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  7. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 12
  8. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  9. 2021When Are Linear Stochastic Bandits Attackable?cited by 10
  10. 2022A Regret-Variance Trade-Off in Online Learningcited by 7
  11. 2023Accelerated Rates between Stochastic and Adversarial Online Convex Optimizationcited by 7
  12. 2023Adversarial Attacks on Adversarial Banditscited by 6
9 more
  1. 2022Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordinationcited by 5
  2. 2024Non-stochastic Bandits With Evolving Observationscited by 4
  3. 2025Robo-SGG: Exploiting Layout-Oriented Normalization and Restitution Can Improve Robust Scene Graph Generationcited by 3
  4. 2025Parameter-free Algorithms for the Stochastically Extended Adversarial Modelcited by 3
  5. 2022Bridging Adversarial and Nonstationary Multi-armed Banditcited by 2
  6. 2024A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descentcited by 2
  7. 2024Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Setscited by 1
  8. 2026Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Banditscited by 1
  9. 2026Prediction with Expert Advice under Heavy-Tailed Lossescited by 0