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

• URL: http://arxiv.org/abs/2604.10062v2
• Date: Tue, 14 Apr 2026 22:53:06 GMT
• Title: When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs
• Abstract summary: This paper provides the first precise necessity and sufficiency characterization of the attackability of a linear MDP under reward poisoning attacks.<n>By approximating deep RL environments as linear MDPs, we show that our theoretical framework effectively distinguishes the attackability and efficiently attacks the vulnerable ones.
• Score: 36.48167187368067
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Theory of Continual Learning Against Data Poisoning Attacks [24.02205412427037]
  We develop a theoretical framework to analyze strategic attacks and defenses in regularization-based CL.<n>We propose a task-to-task verification mechanism to detect data poisoning and reduce cumulative bias for learning convergence.
  arXiv  Detail & Related papers  (2026-06-29T06:28:49Z)
• PISmith: Reinforcement Learning-based Red Teaming for Prompt Injection Defenses [19.85522880335499]
  We propose PISmith, a framework that assesses existing prompt-injection defenses.<n>We find that applying standard GRPO to attack strong defenses leads to sub-optimal performance.<n>We introduce adaptive entropy regularization and dynamic advantage weighting to sustain exploration and amplify learning from scarce successes.
  arXiv  Detail & Related papers  (2026-03-13T14:34:54Z)
• SleeperNets: Universal Backdoor Poisoning Attacks Against Reinforcement Learning Agents [16.350898218047405]
  Reinforcement learning (RL) is an actively growing field that is seeing increased usage in real-world, safety-critical applications. In this work we explore a particularly stealthy form of training-time attacks against RL -- backdoor poisoning. We formulate a novel poisoning attack framework which interlinks the adversary's objectives with those of finding an optimal policy.
  arXiv  Detail & Related papers  (2024-05-30T23:31:25Z)
• Universal Black-Box Reward Poisoning Attack against Offline Reinforcement Learning [4.629358641630161]
  We study the problem of universal black-boxed reward poisoning attacks against general offline reinforcement learning with deep neural networks. We propose the first universal black-box reward poisoning attack in the general offline RL setting.
  arXiv  Detail & Related papers  (2024-02-15T04:08:49Z)
• Optimal Attack and Defense for Reinforcement Learning [11.36770403327493]
  In adversarial RL, an external attacker has the power to manipulate the victim agent's interaction with the environment. We show the attacker's problem of designing a stealthy attack that maximizes its own expected reward. We argue that the optimal defense policy for the victim can be computed as the solution to a Stackelberg game.
  arXiv  Detail & Related papers  (2023-11-30T21:21:47Z)
• Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learning [6.414910263179327]
  We study reward poisoning attacks on online deep reinforcement learning (DRL) We demonstrate the intrinsic vulnerability of state-of-the-art DRL algorithms by designing a general, black-box reward poisoning framework called adversarial MDP attacks. Our results show that our attacks efficiently poison agents learning in several popular classical control and MuJoCo environments.
  arXiv  Detail & Related papers  (2022-05-30T04:07:19Z)
• Policy Smoothing for Provably Robust Reinforcement Learning [109.90239627115336]
  We study the provable robustness of reinforcement learning against norm-bounded adversarial perturbations of the inputs. We generate certificates that guarantee that the total reward obtained by the smoothed policy will not fall below a certain threshold under a norm-bounded adversarial of perturbation the input.
  arXiv  Detail & Related papers  (2021-06-21T21:42:08Z)
• Learning and Certification under Instance-targeted Poisoning [49.55596073963654]
  We study PAC learnability and certification under instance-targeted poisoning attacks. We show that when the budget of the adversary scales sublinearly with the sample complexity, PAC learnability and certification are achievable. We empirically study the robustness of K nearest neighbour, logistic regression, multi-layer perceptron, and convolutional neural network on real data sets.
  arXiv  Detail & Related papers  (2021-05-18T17:48:15Z)
• Robust Deep Reinforcement Learning through Adversarial Loss [74.20501663956604]
  Recent studies have shown that deep reinforcement learning agents are vulnerable to small adversarial perturbations on the agent's inputs. We propose RADIAL-RL, a principled framework to train reinforcement learning agents with improved robustness against adversarial attacks.
  arXiv  Detail & Related papers  (2020-08-05T07:49:42Z)
• Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations [88.94162416324505]
  A deep reinforcement learning (DRL) agent observes its states through observations, which may contain natural measurement errors or adversarial noises. Since the observations deviate from the true states, they can mislead the agent into making suboptimal actions. We show that naively applying existing techniques on improving robustness for classification tasks, like adversarial training, is ineffective for many RL tasks.
  arXiv  Detail & Related papers  (2020-03-19T17:59:59Z)
• Challenges and Countermeasures for Adversarial Attacks on Deep Reinforcement Learning [48.49658986576776]
  Deep Reinforcement Learning (DRL) has numerous applications in the real world thanks to its outstanding ability in adapting to the surrounding environments. Despite its great advantages, DRL is susceptible to adversarial attacks, which precludes its use in real-life critical systems and applications. This paper presents emerging attacks in DRL-based systems and the potential countermeasures to defend against these attacks.
  arXiv  Detail & Related papers  (2020-01-27T10:53:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.