# Optimal Attack and Defense for Reinforcement Learning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 34 references that are in the map.
- First posted on arXiv 30 Nov 2023.

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Adversarial Attacks on Neural Network Policies](https://mlsanity.com/paper/1702.02284/) (2017)
- [Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations](https://mlsanity.com/paper/2003.08938/) (2020)
- [Action Robust Reinforcement Learning and Applications in Continuous Control](https://mlsanity.com/paper/1901.09184/) (2019)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [Robust Reinforcement Learning on State Observations with Learned Optimal Adversary](https://mlsanity.com/paper/2101.08452/) (2021)
- [Delving into adversarial attacks on deep policies](https://mlsanity.com/paper/1705.06452/) (2017)
- [Vulnerability of Deep Reinforcement Learning to Policy Induction Attacks](https://mlsanity.com/paper/1701.04143/) (2017)
- [Adaptive Reward-Poisoning Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12613/) (2020)
- [Stealthy and Efficient Adversarial Attacks against Deep Reinforcement Learning](https://mlsanity.com/paper/2005.07099/) (2020)
- [Who Is the Strongest Enemy? Towards Optimal and Efficient Evasion Attacks in Deep RL](https://mlsanity.com/paper/2106.05087/) (2021)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing](https://mlsanity.com/paper/2106.09292/) (2021)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Defense Against Reward Poisoning Attacks in Reinforcement Learning](https://mlsanity.com/paper/2102.05776/) (2021)
- [Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.13663/) (2022)
- [Sequential Attacks on Agents for Long-Term Adversarial Goals](https://mlsanity.com/paper/1805.12487/) (2018)
- [Query-based Targeted Action-Space Adversarial Policies on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/2011.07114/) (2020)
- [Minimax Sample Complexity for Turn-based Stochastic Game](https://mlsanity.com/paper/2011.14267/) (2020)
- [On Stackelberg Mixed Strategies](https://mlsanity.com/paper/1705.07476/) (2017)
- [The Stackelberg Equilibrium for One-sided Zero-sum Partially Observable Stochastic Games](https://mlsanity.com/paper/2109.08339/) (2021)

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

- [Adversarial Inception Backdoor Attacks against Reinforcement Learning](https://mlsanity.com/paper/2410.13995/) (2024)
- [Adversarially Robust Decision Transformer](https://mlsanity.com/paper/2407.18414/) (2024)
- [Robust Deep Reinforcement Learning against Adversarial Behavior Manipulation](https://mlsanity.com/paper/2406.03862/) (2024)
- [On Minimizing Adversarial Counterfactual Error in Adversarial RL](https://mlsanity.com/paper/2406.04724/) (2024)
- [Policy Teaching via Data Poisoning in Learning from Human Preferences](https://mlsanity.com/paper/2503.10228/) (2025)
- [A General Control-Theoretic Approach for Reinforcement Learning: Theory and Algorithms](https://mlsanity.com/paper/2406.14753/) (2024)
- [Provably Efficient Action-Manipulation Attack Against Continuous Reinforcement Learning](https://mlsanity.com/paper/2411.13116/) (2024)
- [Efficient Preference Poisoning Attack on Offline RLHF](https://mlsanity.com/paper/2605.02495/) (2026)
- [Advantage-based Temporal Attack in Reinforcement Learning](https://mlsanity.com/paper/2602.19582/) (2026)
- [Multi-Agent LLM Governance for Safe Two-Timescale Reinforcement Learning in SDN-IoT Defense](https://mlsanity.com/paper/2604.01127/) (2026)
- [When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs](https://mlsanity.com/paper/2604.10062/) (2026)
- [Improving Generalization and Robustness in Offline Reinforcement Learning via Boundary-Aware Data Augmentation](https://mlsanity.com/paper/2609.20300/) (2026)

## Abstract (arXiv)

To ensure the usefulness of Reinforcement Learning (RL) in real systems, it is crucial to ensure they are robust to noise and adversarial attacks. In adversarial RL, an external attacker has the power to manipulate the victim agent's interaction with the environment. We study the full class of online manipulation attacks, which include (i) state attacks, (ii) observation attacks (which are a generalization of perceived-state attacks), (iii) action attacks, and (iv) reward attacks. We show the attacker's problem of designing a stealthy attack that maximizes its own expected reward, which often corresponds to minimizing the victim's value, is captured by a Markov Decision Process (MDP) that we call a meta-MDP since it is not the true environment but a higher level environment induced by the attacked interaction. We show that the attacker can derive optimal attacks by planning in polynomial time or learning with polynomial sample complexity using standard RL techniques. We argue that the optimal defense policy for the victim can be computed as the solution to a stochastic Stackelberg game, which can be further simplified into a partially-observable turn-based stochastic game (POTBSG). Neither the attacker nor the victim would benefit from deviating from their respective optimal policies, thus such solutions are truly robust. Although the defense problem is NP-hard, we show that optimal Markovian defenses can be computed (learned) in polynomial time (sample complexity) in many scenarios.