mlsanityData to 7 Oct 2026

When Are Linear Stochastic Bandits Attackable?

arXiv 2110.09008 ↗First posted 18 Oct 2021cs.LG cs.CRcited by 10

Not on the map. Why?

Abstract (arXiv)

We study adversarial attacks on linear stochastic bandits: by manipulating the rewards, an adversary aims to control the behaviour of the bandit algorithm. Perhaps surprisingly, we first show that some attack goals can never be achieved. This is in sharp contrast to context-free stochastic bandits, and is intrinsically due to the correlation among arms in linear stochastic bandits. Motivated by this finding, this paper studies the attackability of a k-armed linear bandit environment. We first provide a complete necessity and sufficiency characterization of attackability based on the geometry of the arms' context vectors. We then propose a two-stage attack method against LinUCB and Robust Phase Elimination. The method first asserts whether the given environment is attackable; and if yes, it poisons the rewards to force the algorithm to pull a target arm linear times using only a sublinear cost. Numerical experiments further validate the effectiveness and cost-efficiency of the proposed attack method.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 18 of its 32 references that are in the map. First posted on arXiv 18 Oct 2021.

Builds on

18 of 32 references.

References · 18

  1. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  4. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  5. 2020Adaptive Reward-Poisoning Attacks against Reinforcement Learningcited by 86
  6. 2020Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learningcited by 81
  7. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  8. 2018Adversarial Attacks on Stochastic Banditscited by 56
  9. 2019Data Poisoning Attacks on Stochastic Banditscited by 52
  10. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  11. 2021Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learningcited by 29
  12. 2021Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environmentscited by 26
6 more
  1. 2018Data Poisoning Attacks in Contextual Banditscited by 22
  2. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
  3. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  4. 2020Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attackcited by 13
  5. 2020Unifying Clustered and Non-stationary Banditscited by 11
  6. 2019Efficient Policy Learning for Non-Stationary MDPs under Adversarial Manipulationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 1; 2025: 1; 2026: 1.

10 papers.

  1. 2023Adversarial Attacks on Adversarial Banditscited by 6
  2. 2023Adversarial Attacks on Online Learning to Rank with Click Feedbackcited by 6
  3. 2023Adversarial Attacks on Online Learning to Rank with Stochastic Click Modelscited by 6
  4. 2023Byzantine-Resilient Decentralized Multi-Armed Banditscited by 3
  5. 2025Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injectioncited by 3
  6. 2023Adversarial Attacks on Combinatorial Multi-Armed Banditscited by 2
  7. 2024Stealthy Adversarial Attacks on Stochastic Multi-Armed Banditscited by 2
  8. 2023Follow-ups Also Matter: Improving Contextual Bandits via Post-serving Contextscited by 1
  9. 2023Reward Teaching for Federated Multi-armed Banditscited by 0
  10. 2026When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPscited by 0