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

We study reward poisoning attacks in reinforcement learning (RL), where an adversary manipulates rewards under a limited budget to induce a target agent to learn a policy aligned with the attacker's objectives. Most prior work focuses on constructing successful attacks, providing sufficient conditions under which poisoning is effective, while offering limited understanding of when such targeted attacks are fundamentally infeasible. In this paper, we provide the first characterization of reward-poisoning attackability in linear MDPs, establishing both necessary and sufficient conditions for whether a target policy can be induced within a bounded attack budget. This draws a clear boundary between the vulnerable RL instances and intrinsically robust ones, which cannot be attacked without high costs even when the learner uses standard, non-robust RL algorithms. We further demonstrate our framework beyond synthetic linear MDPs by approximating deep RL environments as linear MDPs. We show that our theoretical framework effectively distinguishes vulnerability, demonstrating how our theoretical predictions have practical significance.

Reward poisoning in reinforcement learning is a significant hurdle to trustworthy decision-making with AI. Research has traditionally followed an algorithmic "arms-race" approach: in creating and studying new adversarial attacks, researchers develop algorithms that are resistant to poisoning and vice versa. Our work presents intrinsic robustness in reinforcement learning, a complementary perspective to reward poisoning where the success of an adversarial attack strategy depends on the intrinsic geometry of the learning problem. We study linear MDPs and prove a theoretically-grounded characterization program to estimate intrinsic vulnerability. We demonstrate empirically our theoretical claims using synthetic and linear MDP representations of classical environments from MuJoCo and Gymnasium.