Adversarial Attacks on Stochastic Bandits

Abstract

We study adversarial attacks that manipulate the reward signals to control the actions chosen by a stochastic multi-armed bandit algorithm. We propose the first attack against two popular bandit algorithms: $\epsilon$-greedy and UCB, \emph{without} knowledge of the mean rewards. The attacker is able to spend only logarithmic effort, multiplied by a problem-specific parameter that becomes smaller as the bandit problem gets easier to attack. The result means the attacker can easily hijack the behavior of the bandit algorithm to promote or obstruct certain actions, say, a particular medical treatment. As bandits are seeing increasingly wide use in practice, our study exposes a significant security threat.

accepted to NIPS

Cited by in corpus (35)

• Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning
• Adaptive Reward-Poisoning Attacks against Reinforcement Learning
• Sign-OPT: A Query-Efficient Hard-label Adversarial Attack
• Data Poisoning against Differentially-Private Learners: Attacks and Defenses
• Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense
• Online Data Poisoning Attack
• Adversarial Attacks on Linear Contextual Bandits
• Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning
• Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses
• Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks
• Stochastic Linear Bandits Robust to Adversarial Attacks
• Identifying Classes Susceptible to Adversarial Attacks
• Using Machine Teaching to Investigate Human Assumptions when Teaching Reinforcement Learners
• Learning-based attacks in Cyber-Physical Systems: Exploration, Detection, and Control Cost trade-offs
• The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation
• Prediction with Corrupted Expert Advice
• Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks
• Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments
• Linear Contextual Bandits with Adversarial Corruptions
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems
• Optimal Attack against Autoregressive Models by Manipulating the Environment
• Adversarial Attacks on Gaussian Process Bandits
• Detecting Rewards Deterioration in Episodic Reinforcement Learning
• The Sample Complexity of Teaching-by-Reinforcement on Q-Learning
• Incentivized Exploration for Multi-Armed Bandits under Reward Drift
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack
• Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulation
• Robust Bandit Learning with Imperfect Context
• Combinatorial Bandits under Strategic Manipulations
• Distributed No-Regret Learning in Multi-Agent Systems
• Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs
• Accumulative Poisoning Attacks on Real-time Data
• Sequential Attacks on Kalman Filter-based Forward Collision Warning Systems