# Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack

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

## Key facts

- Cited by 13 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 17 Feb 2020.

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

- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Exploring the Training Robustness of Distributional Reinforcement Learning against Noisy State Observations](https://mlsanity.com/paper/2109.08776/) (2021)
- [When Are Linear Stochastic Bandits Attackable?](https://mlsanity.com/paper/2110.09008/) (2021)
- [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)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Efficient Action Poisoning Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2112.05367/) (2021)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Stealthy Adversarial Attacks on Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2402.13487/) (2024)
- [A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2602.10971/) (2026)
- [Robust Pareto Set Identification with Contaminated Bandit Feedback](https://mlsanity.com/paper/2206.02666/) (2022)
- [Reward Teaching for Federated Multi-armed Bandits](https://mlsanity.com/paper/2305.02441/) (2023)

## Abstract (arXiv)

The multi-armed bandit formalism has been extensively studied under various attack models, in which an adversary can modify the reward revealed to the player. Previous studies focused on scenarios where the attack value either is bounded at each round or has a vanishing probability of occurrence. These models do not capture powerful adversaries that can catastrophically perturb the revealed reward. This paper investigates the attack model where an adversary attacks with a certain probability at each round, and its attack value can be arbitrary and unbounded if it attacks. Furthermore, the attack value does not necessarily follow a statistical distribution. We propose a novel sample median-based and exploration-aided UCB algorithm (called med-E-UCB) and a median-based ε-greedy algorithm (called med-ε-greedy). Both of these algorithms are provably robust to the aforementioned attack model. More specifically we show that both algorithms achieve O(log T) pseudo-regret (i.e., the optimal regret without attacks). We also provide a high probability guarantee of O(log T) regret with respect to random rewards and random occurrence of attacks. These bounds are achieved under arbitrary and unbounded reward perturbation as long as the attack probability does not exceed a certain constant threshold. We provide multiple synthetic simulations of the proposed algorithms to verify these claims and showcase the inability of existing techniques to achieve sublinear regret. We also provide experimental results of the algorithm operating in a cognitive radio setting using multiple software-defined radios.