Better Algorithms for Stochastic Bandits with Adversarial Corruptions

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.

• Publication year

  2019

• Venue

  Annual Conference Computational Learning Theory

• Publication date

  2019-02-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1902.08647
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously

  2019cited by this paper
• An Optimal Algorithm for Stochastic and Adversarial Bandits

  2018cited by this paper
• Efficient Algorithms for Outlier-Robust Regression

  2018cited by this paper
• Stochastic bandits robust to adversarial corruptions

  2018influential reference
• Best Arm Identification for Contaminated Bandits

  2018cited by this paper
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits

  2018cited by this paper
• Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs

  2018cited by this paper
• Corruption-tolerant bandit learning

  2018cited by this paper
• Pure Exploration of Multi-Armed Bandits with Heavy-Tailed Payoffs

  2018cited by this paper
• Learning geometric concepts with nasty noise

  2017cited by this paper
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits

  2017cited by this paper
• Robust Estimators in High Dimensions without the Computational Intractability

  2016cited by this paper
• An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits

  2016cited by this paper
• Learning from untrusted data

  2016cited by this paper
• Agnostic Estimation of Mean and Covariance

  2016cited by this paper
• One Practical Algorithm for Both Stochastic and Adversarial Bandits

  2014cited by this paper
• Bandits With Heavy Tail

  2012cited by this paper
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems

  2012cited by this paper
• Contextual Bandit Algorithms with Supervised Learning Guarantees

  2010influential reference
• Concentration of Measure for the Analysis of Randomized Algorithms

  2009influential reference
• Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems

  2006cited by this paper
• The Nonstochastic Multiarmed Bandit Problem

  2002cited by this paper
• Finite-time Analysis of the Multiarmed Bandit Problem

  2002cited by this paper
• Learning in the presence of malicious errors

  1993cited by this paper
• Asymptotically efficient adaptive allocation rules

  1985cited by this paper
• On robust estimation of the location parameter

  1980cited by this paper
• Robust Estimation of a Location Parameter

  1964cited by this paper
• 25th Annual Conference on Learning Theory The Best of Both Worlds: Stochastic and Adversarial Bandits

  year unknowncited by this paper

• Truly Adapting to Adversarial Constraints in Constrained MABs

  2026cites this paper
• A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

  2026cites this paper
• Efficient Adversarial Attacks on High-dimensional Offline Bandits

  2026cites this paper
• Communication-Corruption Coupling and Verification in Cooperative Multi-Objective Bandits

  2026cites this paper
• Human Feedback Attack on Online RLHF: Attack and Robust Defense

  2025cites this paper
• Robust Contextual Combinatorial Multi-Armed Bandits for Unreliable Network Systems

  2025cites this paper
• Does Feedback Help in Bandits with Arm Erasures?

  2025cites this paper
• A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond

  2025influential citation
• On the Adversarial Robustness of Benjamini Hochberg

  2025cites this paper
• Tracking Most Significant Shifts in Infinite-Armed Bandits

  2025cites this paper
• Robust Bayesian Optimisation with Unbounded Corruptions

  2025cites this paper
• Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach

  2025cites this paper
• Problem-dependent Regret for Lexicographic Multi-Armed Bandits with Adversarial Corruptions

  2025influential citation
• Quantum Entanglement Path Selection and Qubit Allocation via Adversarial Group Neural Bandits

  2024cites this paper
• Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptions

  2024cites this paper
• Robust Thompson Sampling Algorithms Against Reward Poisoning Attacks

  2024influential citation
• Stochastic Bandits With Non-Stationary Rewards: Reward Attack and Defense

  2024cites this paper
• Learning the Optimal Path and DNN Partition for Collaborative Edge Inference

  2024cites this paper
• Online Influence Maximization With Semi-Bandit Feedback Under Corruptions

  2024cites this paper
• Robust Q-Learning under Corrupted Rewards

  2024cites this paper
• Online Learning and Detecting Corrupted Users for Conversational Recommendation Systems

  2024influential citation
• Locally Private and Robust Multi-Armed Bandits

  2024cites this paper
• Stochastic Bandits Robust to Adversarial Attacks

  2024influential citation
• Corruption Robust Dynamic Pricing in Liner Shipping under Capacity Constraint

  2024cites this paper
• Learning for Bandits under Action Erasures

  2024cites this paper
• Supermodular Approximation of Norms and Applications

  2024cites this paper
• Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling

  2024cites this paper
• Contaminated Online Convex Optimization

  2024cites this paper
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

  2024influential citation
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits

  2024cites this paper
• Stealthy Adversarial Attacks on Stochastic Multi-Armed Bandits

  2024cites this paper
• Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption

  2024cites this paper
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions

  2024cites this paper
• Distributed Robust Bandits With Efficient Communication

  2023influential citation
• Best-of-Both-Worlds Linear Contextual Bandits

  2023influential citation
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits

  2023cites this paper
• Reward Teaching for Federated Multiarmed Bandits

  2023cites this paper
• Reward Teaching for Federated Multi-armed Bandits

  2023cites this paper
• Robust Near-Optimal Arm Identification With Strongly-Adaptive Adversaries

  2023influential citation
• Online Robust Mean Estimation

  2023cites this paper
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation

  2023cites this paper
• Action Poisoning Attacks on Linear Contextual Bandits

  2023cites this paper
• Online Corrupted User Detection and Regret Minimization

  2023influential citation
• Adversarial Attacks on Combinatorial Multi-Armed Bandits

  2023cites this paper
• Trade-off Analysis in Learning-augmented Algorithms with Societal Design Criteria

  2023cites this paper
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption

  2023cites this paper
• Adversarial Group Linear Bandits and Its Application to Collaborative Edge Inference

  2023cites this paper
• Multi-Arm Bandits over Action Erasure Channels

  2023cites this paper
• Distributed Stochastic Bandits with Corrupted and Defective Input Commands

  2023cites this paper
• Robust and private stochastic linear bandits

  2023cites this paper
• Bandit Online Linear Optimization with Hints and Queries

  2023cites this paper
• Corruption-Robust Lipschitz Contextual Search

  2023cites this paper
• On the Robustness of Epoch-Greedy in Multi-Agent Contextual Bandit Mechanisms

  2023cites this paper
• On the Model-Misspecification in Reinforcement Learning

  2023cites this paper
• Robust Lipschitz Bandits to Adversarial Corruptions

  2023influential citation
• Constrained Online Two-stage Stochastic Optimization: New Algorithms via Adversarial Learning

  2023cites this paper
• Robust and differentially private stochastic linear bandits

  2023cites this paper
• Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds

  2023cites this paper
• A Blackbox Approach to Best of Both Worlds in Bandits and Beyond

  2023cites this paper
• Multi-channel Autobidding with Budget and ROI Constraints

  2023cites this paper
• Federated Multiarmed Bandits Under Byzantine Attacks

  2022cites this paper
• Bridging Adversarial and Nonstationary Multi-Armed Bandit

  2022cites this paper
• Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms

  2022cites this paper
• Collaborative Learning in General Graphs with Limited Memorization: Learnability, Complexity and Reliability

  2022cites this paper
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits

  2022cites this paper
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences

  2022cites this paper
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions

  2022cites this paper
• Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learning

  2022cites this paper
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs

  2022cites this paper
• Robust Pareto Set Identification with Contaminated Bandit Feedback

  2022cites this paper
• Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds

  2022cites this paper
• Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization

  2022cites this paper
• On the Complexity of Adversarial Decision Making

  2022cites this paper
• Best of Both Worlds Model Selection

  2022cites this paper
• Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences

  2022cites this paper
• Revisiting Online Submodular Minimization: Gap-Dependent Regret Bounds, Best of Both Worlds and Adversarial Robustness

  2022influential citation
• Learning in Stackelberg Games with Non-myopic Agents

  2022cites this paper
• Covert Best Arm Identification of Stochastic Bandits

  2022cites this paper
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes

  2022influential citation
• Robust Stochastic Bandit algorithms to defend against Oracle attack using Sample Dropout

  2022cites this paper
• Collaborative Learning in General Graphs With Limited Memorization: Complexity, Learnability, and Reliability

  2022cites this paper
• Robust Federated Best-Arm Identification in Multi-Armed Bandits

  2021cites this paper
• On Reinforcement Learning with Adversarial Corruption and Its Application to Block MDP

  2021cites this paper
• Robust Online Convex Optimization in the Presence of Outliers

  2021cites this paper
• Bayesian decision-making under misspecified priors with applications to meta-learning

  2021cites this paper
• Corruption Robust Active Learning

  2021influential citation
• Corruption-Robust Linear Bandits

  2021cites this paper
• Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations

  2021influential citation
• Bias-Robust Bayesian Optimization via Dueling Bandit

  2021influential citation
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

  2021cites this paper
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions

  2021influential citation
• Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks

  2021influential citation
• Stochastic Graphical Bandits with Adversarial Corruptions

  2021influential citation
• High-Dimensional Experimental Design and Kernel Bandits

  2021cites this paper
• Stochastic Dueling Bandits with Adversarial Corruption

  2021influential citation
• Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits

  2021cites this paper
• Secure-UCB: Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification

  2021influential citation
• Combinatorial Bandits under Strategic Manipulations

  2021influential citation
• Multiplicative Reweighting for Robust Neural Network Optimization

  2021cites this paper
• Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification

  2021cites this paper