# When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Adversarial robustness and RL in finance, one of 15 directions in Deep reinforcement learning methods.
- Builds on 34 of its 50 references that are in the map.
- First posted on arXiv 11 Apr 2026.

## Placed in

- Deep reinforcement learning methods / [Adversarial robustness and RL in finance](https://mlsanity.com/deeprl/adversarial-robustness-and-rl-in-finance/)

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

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Tactics of Adversarial Attack on Deep Reinforcement Learning Agents](https://mlsanity.com/paper/1703.06748/) (2017)
- [Survey on Large Language Model-Enhanced Reinforcement Learning: Concept, Taxonomy, and Methods](https://mlsanity.com/paper/2404.00282/) (2024)
- [Adaptive Reward-Poisoning Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12613/) (2020)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics](https://mlsanity.com/paper/2009.00774/) (2020)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environments](https://mlsanity.com/paper/2102.08492/) (2021)
- [BAFFLE: Hiding Backdoors in Offline Reinforcement Learning Datasets](https://mlsanity.com/paper/2210.04688/) (2022)
- [Beyond Sparse Rewards: Enhancing Reinforcement Learning with Language Model Critique in Text Generation](https://mlsanity.com/paper/2401.07382/) (2024)
- [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)
- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [SleeperNets: Universal Backdoor Poisoning Attacks Against Reinforcement Learning Agents](https://mlsanity.com/paper/2405.20539/) (2024)
- [Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attacks](https://mlsanity.com/paper/2302.13851/) (2023)
- [Admissible Policy Teaching through Reward Design](https://mlsanity.com/paper/2201.02185/) (2022)
- [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)
- [Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification](https://mlsanity.com/paper/2102.07711/) (2021)
- [Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learning](https://mlsanity.com/paper/2205.14842/) (2022)
- [EasyRL4Rec: An Easy-to-use Library for Reinforcement Learning Based Recommender Systems](https://mlsanity.com/paper/2402.15164/) (2024)
- [Game Redesign in No-regret Game Playing](https://mlsanity.com/paper/2110.11763/) (2021)
- [Efficient and Generalized end-to-end Autonomous Driving System with Latent Deep Reinforcement Learning and Demonstrations](https://mlsanity.com/paper/2401.11792/) (2024)
- [Black-Box Targeted Reward Poisoning Attack Against Online Deep Reinforcement Learning](https://mlsanity.com/paper/2305.10681/) (2023)

## Abstract (arXiv)

We study reward poisoning attacks in reinforcement learning (RL), where an adversary manipulates rewards within constrained budgets to force the target RL agent to adopt a policy that aligns with the attacker's objectives. Prior works on reward poisoning mainly focused on sufficient conditions to design a successful attacker, while only a few studies discussed the infeasibility of targeted attacks. This paper provides the first precise necessity and sufficiency characterization of the attackability of a linear MDP under reward poisoning attacks. Our characterization draws a bright line between the vulnerable RL instances, and the intrinsically robust ones which cannot be attacked without large costs even running vanilla non-robust RL algorithms. Our theory extends beyond linear MDPs -- by approximating deep RL environments as linear MDPs, we show that our theoretical framework effectively distinguishes the attackability and efficiently attacks the vulnerable ones, demonstrating both the theoretical and practical significance of our characterization.