Adversarial Attacks on Linear Contextual Bandits

Abstract

Contextual bandit algorithms are applied in a wide range of domains, from advertising to recommender systems, from clinical trials to education. In many of these domains, malicious agents may have incentives to attack the bandit algorithm to induce it to perform a desired behavior. For instance, an unscrupulous ad publisher may try to increase their own revenue at the expense of the advertisers; a seller may want to increase the exposure of their products, or thwart a competitor's advertising campaign. In this paper, we study several attack scenarios and show that a malicious agent can force a linear contextual bandit algorithm to pull any desired arm $T-o(T)$ times over a horizon of $T$ steps, while applying adversarial modifications to either rewards or contexts that only grow logarithmically as $O(\log T)$. We also investigate the case when a malicious agent is interested in affecting the behavior of the bandit algorithm in a single context (e.g., a specific user). We first provide sufficient conditions for the feasibility of the attack and we then propose an efficient algorithm to perform the attack. We validate our theoretical results on experiments performed on both synthetic and real-world datasets.

References in corpus (12)

• Explaining and Harnessing Adversarial Examples
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Poisoning Attacks against Support Vector Machines
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Data Poisoning Attacks on Factorization-Based Collaborative Filtering
• The best of both worlds: stochastic and adversarial bandits
• Adversarial Attacks on Stochastic Bandits
• Policy Poisoning in Batch Reinforcement Learning and Control
• Stochastic Linear Optimization with Adversarial Corruption
• CopyCAT: Taking Control of Neural Policies with Constant Attacks
• Better Algorithms for Stochastic Bandits with Adversarial Corruptions
• Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack

Cited by in corpus (6)

• Adversarial Robustness by Design through Analog Computing and Synthetic Gradients
• Stochastic Linear Bandits Robust to Adversarial Attacks
• Linear Contextual Bandits with Adversarial Corruptions
• Exploiting Heterogeneity in Robust Federated Best-Arm Identification
• Combinatorial Bandits under Strategic Manipulations
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles