# Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 50 references that are in the map.
- First posted on arXiv 9 Oct 2021.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Universal adversarial perturbations](https://mlsanity.com/paper/1610.08401/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Unlabeled Data Improves Adversarial Robustness](https://mlsanity.com/paper/1905.13736/) (2019)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Adversarial Attacks on Neural Network Policies](https://mlsanity.com/paper/1702.02284/) (2017)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [Are Labels Required for Improving Adversarial Robustness?](https://mlsanity.com/paper/1905.13725/) (2019)
- [Delving into adversarial attacks on deep policies](https://mlsanity.com/paper/1705.06452/) (2017)
- [Deep Reinforcement Learning for Page-wise Recommendations](https://mlsanity.com/paper/1805.02343/) (2018)
- [Vulnerability of Deep Reinforcement Learning to Policy Induction Attacks](https://mlsanity.com/paper/1701.04143/) (2017)
- [FinRL: A Deep Reinforcement Learning Library for Automated Stock Trading in Quantitative Finance](https://mlsanity.com/paper/2011.09607/) (2020)
- [Adaptive Reward-Poisoning Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12613/) (2020)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation](https://mlsanity.com/paper/1811.00145/) (2018)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Interpreting Adversarially Trained Convolutional Neural Networks](https://mlsanity.com/paper/1905.09797/) (2019)
- [Policy Poisoning in Batch Reinforcement Learning and Control](https://mlsanity.com/paper/1910.05821/) (2019)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (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)
- [Deceptive Reinforcement Learning Under Adversarial Manipulations on Cost Signals](https://mlsanity.com/paper/1906.10571/) (2019)
- [Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics](https://mlsanity.com/paper/2009.00774/) (2020)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)

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

- [Watch Out for Your Agents! Investigating Backdoor Threats to LLM-Based Agents](https://mlsanity.com/paper/2402.11208/) (2024)
- [BadRL: Sparse Targeted Backdoor Attack Against Reinforcement Learning](https://mlsanity.com/paper/2312.12585/) (2023)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attacks](https://mlsanity.com/paper/2302.13851/) (2023)
- [Optimal Attack and Defense for Reinforcement Learning](https://mlsanity.com/paper/2312.00198/) (2023)
- [When Are Linear Stochastic Bandits Attackable?](https://mlsanity.com/paper/2110.09008/) (2021)
- [Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2307.07670/) (2023)
- [Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learning](https://mlsanity.com/paper/2205.14842/) (2022)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Fox in the Henhouse: Supply-Chain Backdoor Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2505.19532/) (2025)
- [Efficient Action Poisoning Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2112.05367/) (2021)
- [Advancing Robustness in Deep Reinforcement Learning with an Ensemble Defense Approach](https://mlsanity.com/paper/2507.17070/) (2025)
- [Collaborative Shadows: Distributed Backdoor Attacks in LLM-Based Multi-Agent Systems](https://mlsanity.com/paper/2510.11246/) (2025)
- [Security of Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2212.06123/) (2022)
- [Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty](https://mlsanity.com/paper/2307.07666/) (2023)
- [Stealthy Adversarial Attacks on Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2402.13487/) (2024)
- [Online Poisoning Attack Against Reinforcement Learning under Black-box Environments](https://mlsanity.com/paper/2412.00797/) (2024)
- [Reinforcement Learning for Linear Quadratic Control is Vulnerable Under Cost Manipulation](https://mlsanity.com/paper/2203.05774/) (2022)
- [Data Poisoning to Fake a Nash Equilibrium in Markov Games](https://mlsanity.com/paper/2306.08041/) (2023)
- [Optimal Cost Constrained Adversarial Attacks For Multiple Agent Systems](https://mlsanity.com/paper/2311.00859/) (2023)
- [Provably Efficient Action-Manipulation Attack Against Continuous Reinforcement Learning](https://mlsanity.com/paper/2411.13116/) (2024)
- [Action Robust Reinforcement Learning via Optimal Adversary Aware Policy Optimization](https://mlsanity.com/paper/2507.03372/) (2025)
- [AI Security in the Foundation Model Era: A Comprehensive Survey from a Unified Perspective](https://mlsanity.com/paper/2603.24857/) (2026)
- [Efficient Preference Poisoning Attack on Offline RLHF](https://mlsanity.com/paper/2605.02495/) (2026)
- [Privacy and Security Implications of Cloud-Based AI Services : A Survey](https://mlsanity.com/paper/2402.00896/) (2024)
- [Provably Invincible Adversarial Attacks on Reinforcement Learning Systems: A Rate-Distortion Information-Theoretic Approach](https://mlsanity.com/paper/2510.13792/) (2025)
- [When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs](https://mlsanity.com/paper/2604.10062/) (2026)
- [Safe-RULE: Safe Reinforcement UnLEarning](https://mlsanity.com/paper/2606.09559/) (2026)
- [Robust Policy Optimization via Adversarial Importance Sampling](https://mlsanity.com/paper/2609.13044/) (2026)

## Abstract (arXiv)

Due to the broad range of applications of reinforcement learning (RL), understanding the effects of adversarial attacks against RL model is essential for the safe applications of this model. Prior theoretical works on adversarial attacks against RL mainly focus on either observation poisoning attacks or environment poisoning attacks. In this paper, we introduce a new class of attacks named action poisoning attacks, where an adversary can change the action signal selected by the agent. Compared with existing attack models, the attacker's ability in the proposed action poisoning attack model is more restricted, which brings some design challenges. We study the action poisoning attack in both white-box and black-box settings. We introduce an adaptive attack scheme called LCB-H, which works for most RL agents in the black-box setting. We prove that the LCB-H attack can force any efficient RL agent, whose dynamic regret scales sublinearly with the total number of steps taken, to choose actions according to a policy selected by the attacker very frequently, with only sublinear cost. In addition, we apply LCB-H attack against a popular model-free RL algorithm: UCB-H. We show that, even in the black-box setting, by spending only logarithm cost, the proposed LCB-H attack scheme can force the UCB-H agent to choose actions according to the policy selected by the attacker very frequently.