# Adversarial Attacks on Adversarial Bandits

arXiv: https://arxiv.org/abs/2301.12595 · HTML: https://mlsanity.com/paper/2301.12595/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 52 references that are in the map.
- First posted on arXiv 30 Jan 2023.

## Builds on (most cited first, 30 of 30)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Adversarial Policies: Attacking Deep Reinforcement Learning](https://mlsanity.com/paper/1905.10615/) (2019)
- [Adaptive Reward-Poisoning Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12613/) (2020)
- [Data Poisoning against Differentially-Private Learners: Attacks and Defenses](https://mlsanity.com/paper/1903.09860/) (2019)
- [Policy Poisoning in Batch Reinforcement Learning and Control](https://mlsanity.com/paper/1910.05821/) (2019)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Strategizing against No-regret Learners](https://mlsanity.com/paper/1909.13861/) (2019)
- [Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics](https://mlsanity.com/paper/2009.00774/) (2020)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Best Arm Identification for Contaminated Bandits](https://mlsanity.com/paper/1802.09514/) (2018)
- [Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks](https://mlsanity.com/paper/2011.10824/) (2020)
- [Data Poisoning Attacks in Contextual Bandits](https://mlsanity.com/paper/1808.05760/) (2018)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (2021)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation](https://mlsanity.com/paper/1906.01528/) (2019)
- [Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack](https://mlsanity.com/paper/2002.07214/) (2020)
- [When Are Linear Stochastic Bandits Attackable?](https://mlsanity.com/paper/2110.09008/) (2021)
- [Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions](https://mlsanity.com/paper/2010.07904/) (2020)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (2021)
- [Game Redesign in No-regret Game Playing](https://mlsanity.com/paper/2110.11763/) (2021)
- [What You See May Not Be What You Get: UCB Bandit Algorithms Robust to ε-Contamination](https://mlsanity.com/paper/1910.05625/) (2019)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Federated Multi-Armed Bandits Under Byzantine Attacks](https://mlsanity.com/paper/2205.04134/) (2022)
- [Efficient Action Poisoning Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2112.05367/) (2021)

## Built on by (most cited first, 6 of 6)

- [Adversarial Attacks on Online Learning to Rank with Click Feedback](https://mlsanity.com/paper/2305.17071/) (2023)
- [Adversarial Attacks on Online Learning to Rank with Stochastic Click Models](https://mlsanity.com/paper/2305.19218/) (2023)
- [Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection](https://mlsanity.com/paper/2505.21938/) (2025)
- [Efficient Preference Poisoning Attack on Offline RLHF](https://mlsanity.com/paper/2605.02495/) (2026)
- [Adversarial Attacks on Cooperative Multi-agent Bandits](https://mlsanity.com/paper/2311.01698/) (2023)
- [Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards](https://mlsanity.com/paper/2610.10000/) (2026)

## Abstract (arXiv)

We study a security threat to adversarial multi-armed bandits, in which an attacker perturbs the loss or reward signal to control the behavior of the victim bandit player. We show that the attacker is able to mislead any no-regret adversarial bandit algorithm into selecting a suboptimal target arm in every but sublinear (T-o(T)) number of rounds, while incurring only sublinear (o(T)) cumulative attack cost. This result implies critical security concern in real-world bandit-based systems, e.g., in online recommendation, an attacker might be able to hijack the recommender system and promote a desired product. Our proposed attack algorithms require knowledge of only the regret rate, thus are agnostic to the concrete bandit algorithm employed by the victim player. We also derived a theoretical lower bound on the cumulative attack cost that any victim-agnostic attack algorithm must incur. The lower bound matches the upper bound achieved by our attack, which shows that our attack is asymptotically optimal.