# Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Backdoor and data poisoning attacks, one of 12 directions in LLM safety and security.
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Placed in

- LLM safety and security / [Backdoor and data poisoning attacks](https://mlsanity.com/safety/backdoor-and-data-poisoning-attacks/)

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [What Doubling Tricks Can and Can't Do for Multi-Armed Bandits](https://mlsanity.com/paper/1803.06971/) (2018)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [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)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Data Poisoning Attacks in Contextual Bandits](https://mlsanity.com/paper/1808.05760/) (2018)
- [Unifying the stochastic and the adversarial Bandits with Knapsack](https://mlsanity.com/paper/1811.12253/) (2018)
- [Learning-based attacks in Cyber-Physical Systems: Exploration, Detection, and Control Cost trade-offs](https://mlsanity.com/paper/2011.10718/) (2020)

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

- [Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.13663/) (2022)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination](https://mlsanity.com/paper/2111.07458/) (2021)
- [(Almost) Free Incentivized Exploration from Decentralized Learning Agents](https://mlsanity.com/paper/2110.14628/) (2021)
- [Policy Teaching via Data Poisoning in Learning from Human Preferences](https://mlsanity.com/paper/2503.10228/) (2025)
- [Stochastic Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2408.08859/) (2024)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)
- [Observation-Free Attacks on Online Learning to Rank](https://mlsanity.com/paper/2509.22855/) (2025)
- [When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs](https://mlsanity.com/paper/2604.10062/) (2026)

## Abstract (arXiv)

We study bandit algorithms under data poisoning attacks in a bounded reward setting. We consider a strong attacker model in which the attacker can observe both the selected actions and their corresponding rewards and can contaminate the rewards with additive noise. We show that any bandit algorithm with regret O(log T) can be forced to suffer a regret Omega(T) with an expected amount of contamination O(log T). This amount of contamination is also necessary, as we prove that there exists an O(log T) regret bandit algorithm, specifically the classical UCB, that requires Omega(log T) amount of contamination to suffer regret Omega(T). To combat such attacks, our second main contribution is to propose verification based mechanisms, which use limited verification to access a limited number of uncontaminated rewards. In particular, for the case of unlimited verifications, we show that with O(log T) expected number of verifications, a simple modified version of the ETC type bandit algorithm can restore the order optimal O(log T) regret irrespective of the amount of contamination used by the attacker. We also provide a UCB-like verification scheme, called Secure-UCB, that also enjoys full recovery from any attacks, also with O(log T) expected number of verifications. To derive a matching lower bound on the number of verifications, we prove that for any order-optimal bandit algorithm, this number of verifications Omega(log T) is necessary to recover the order-optimal regret. On the other hand, when the number of verifications is bounded above by a budget B, we propose a novel algorithm, Secure-BARBAR, which provably achieves O(minC,T/√B ) regret with high probability against weak attackers where C is the total amount of contamination by the attacker, which breaks the known Omega(C) lower bound of the non-verified setting if C is large.