Geometric Robustness Against Reward Poisoning in Linear Environments

This direction is merged into another direction: input perturbation sensitivity. Its last version stays readable and citable here.

Version 1 of 15 papers22 conceptsfrozen 2026-10-04

In online reinforcement learning (RL), an agent learns by trial and error, refining its strategy based on the rewards it receives from the environment. This feedback loop is a major security vulnerability: if an adversary can slightly modify the rewards, they can "poison" the agent's learning process, tricking it into adopting a failing or malicious policy.

While researchers like Yinglun Xu and Gagandeep Singh have demonstrated that state-of-the-art agents like PPO and SAC can be broken by corrupting as little as 0.5% of rewards in Efficient Reward Poisoning Attacks on Online Deep Reinforcement Learning, a deeper question remains: Is every environment equally vulnerable?

Recent theoretical work reveals that the answer is no. Some environments are intrinsically robust due to the geometric structure of their action space.

The Geometry of Correlation

To understand why some environments resist poisoning, we must look at how rewards are modeled. In a simple multi-armed bandit, every action (arm) is independent. If an attacker wants you to stop picking Arm A, they simply lower the reward for Arm A. In this "context-free" setting, any target can be forced if the attacker has enough budget.

However, modern RL often uses linear models, where actions are represented by feature vectors $x$, and the reward is a linear function of those features: $r = x^T \theta$. Here, the arms are mathematically linked by the shared parameter $\theta$.

Huazheng Wang, Haifeng Xu, and Hongning Wang argue in When Are Linear Stochastic Bandits Attackable? that this geometric correlation acts as a natural defense. If an attacker tries to suppress a competitor arm by shifting the global parameter $\theta$, that shift might inadvertently lower the reward of the attacker's own "target" arm even more. If the feature space is sufficiently constrained, it becomes mathematically impossible to make the target arm look like the best option without also making it look terrible in absolute terms.

The Attackability Certificate

How can we tell if a specific environment is vulnerable? The research points to a formal characterization using a Convex Quadratic Program (CQP).

The CQP acts as a "certificate" of attackability. It essentially asks: Is there a direction in the feature space that suppresses all alternative actions while maintaining a positive margin for the target action?

  1. Feasible CQP: If a solution exists, the environment's geometry allows for a "Null Space Attack." The attacker can hide their influence in the dimensions where the learner is still uncertain, successfully poisoning the agent with a sublinear (efficient) cost.
  2. Infeasible CQP: If no such direction exists, the environment is intrinsically robust. No matter what algorithm the agent uses (e.g., LinUCB), the attacker cannot force the target policy without spending a prohibitive amount of effort that scales linearly with time.

Scaling to Complex MDPs

This geometric intuition isn't limited to simple bandits. In When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs, authors including Jose Efraim Aguilar Escamilla and Xuezhou Zhang extend this logic to full Reinforcement Learning.

In a Linear MDP, the transition dynamics and rewards are governed by feature representations of state-action pairs. The "tight characterization" provided by this research shows that vulnerability is an inherent property of the feature space geometry rather than a flaw in the learning algorithm.

If the features of a target policy are too similar to the features of the optimal policy—specifically, if they cannot be separated by a linear hyperplane that favors the target—the environment is fundamentally safe from low-cost reward poisoning. This shift in perspective suggests that the best defense against adversarial manipulation may not be a better training algorithm, but rather a more carefully designed feature representation.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_geometric_robustness_against_reward_pois_654386b1,
  title = {Geometric Robustness Against Reward Poisoning in Linear Environments},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-robustness-against-reward-poisoning-in-linear-environments/rdr_654386b1714a4a2cbc1565c668ba7344},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_geometric_robustness_against_reward_pois_654386b1_v1,
  title = {Geometric Robustness Against Reward Poisoning in Linear Environments},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/geometric-robustness-against-reward-poisoning-in-linear-environments/rdr_654386b1714a4a2cbc1565c668ba7344/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}