Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense

Abstract

Due to the broad range of applications of stochastic multi-armed bandit model, understanding the effects of adversarial attacks and designing bandit algorithms robust to attacks are essential for the safe applications of this model. In this paper, we introduce a new class of attack named action-manipulation attack. In this attack, an adversary can change the action signal selected by the user. We show that without knowledge of mean rewards of arms, our proposed attack can manipulate Upper Confidence Bound (UCB) algorithm, a widely used bandit algorithm, into pulling a target arm very frequently by spending only logarithmic cost. To defend against this class of attacks, we introduce a novel algorithm that is robust to action-manipulation attacks when an upper bound for the total attack cost is given. We prove that our algorithm has a pseudo-regret upper bounded by $\mathcal{O}(\max \{\log T,A\})$, where $T$ is the total number of rounds and $A$ is the upper bound of the total attack cost.

arXiv comment13 pages, 7 figures, submitted to IEEE Transaction on Signal Processing

References in corpus (14)

• Explaining and Harnessing Adversarial Examples
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Poisoning Attacks against Support Vector Machines
• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Is feature selection secure against training data poisoning?
• Data Poisoning Attacks on Factorization-Based Collaborative Filtering
• Online Learning of Rested and Restless Bandits
• Cascading Bandits: Learning to Rank in the Cascade Model
• Tactics of Adversarial Attack on Deep Reinforcement Learning Agents
• Adversarial Attacks on Neural Network Policies
• Adversarial Attacks on Stochastic Bandits
• Data Poisoning Attacks on Stochastic Bandits
• On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
• The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation

Cited by in corpus (4)

• Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning
• Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning
• Optimal Stochastic Nonconvex Optimization with Bandit Feedback
• Generalized Likelihood Ratio Test for Adversarially Robust Hypothesis Testing