Sublinear Cost Poisoning of Sequential Learners

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 243 papers76 conceptsfrozen 2026-10-04

In sequential decision-making, an agent learns by interacting with an environment: it takes an action, observes a reward, and updates its strategy. This feedback loop is the engine of Reinforcement Learning (RL) and Bandit algorithms. However, recent research reveals a fundamental vulnerability in this loop. By subtly manipulating the rewards or actions an agent perceives, an adversary can "teach" the agent an arbitrary target policy.

Crucially, this manipulation does not require a massive, permanent intervention. Instead, attackers can achieve their goals with a sublinear cost, meaning the effort required to maintain the deception diminishes as the agent becomes more "convinced" of the false reality.

The Economics of Deception

The central insight across this research is a cost asymmetry: an adversary can spend a logarithmic or sublinear amount of effort to cause linear regret for the learner.

In a standard Multi-Armed Bandit (MAB) setting, algorithms like UCB or Thompson Sampling are designed to minimize regret by exploring arms and converging on the one with the highest mean reward. Fang Liu and Ness B. Shroff demonstrated in Data Poisoning Attacks on Stochastic Bandits that an attacker can hijack this process. By lowering the rewards of the optimal arm whenever the agent selects it, the attacker forces the agent to prefer a sub-optimal "target" arm.

The cost is sublinear because of how the agent learns. As the agent’s internal model begins to believe the target arm is superior, it chooses the true optimal arm less and less frequently. Since the attacker only pays to manipulate the rewards of the arms the agent actually selects, the frequency of required interventions drops over time. Shiliang Zuo showed that for some algorithms, the budget required to completely hijack the learner can be as low as $O(\sqrt{\log T})$, making long-term manipulation highly efficient Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses.

Geometric Barriers to Poisoning

While simple bandits are almost always vulnerable, more complex models introduce "intrinsic robustness" based on their underlying geometry. In Linear Contextual Bandits, actions are represented as vectors, and rewards are linear functions of these vectors.

Huazheng Wang, Haifeng Xu, and Hongning Wang discovered that some linear environments are mathematically "unattackable" with a sublinear budget When Are Linear Stochastic Bandits Attackable?. If the target arm is geometrically "hidden" behind other arms such that making it look optimal would require contradicting the rewards of too many other arms, the attacker's cost would grow linearly. In such cases, the environment is "intrinsically robust."

This geometric characterization was extended to Linear Markov Decision Processes (MDPs) by Jose Efraim Aguilar Escamilla and Xuezhou Zhang. They used Convex Quadratic Programming to provide a "tight" characterization of when an RL environment is vulnerable When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs. If the environment's structure allows for a sublinear attack, the adversary can eventually stop intervening entirely once the agent internalizes the target policy.

Expanding the Attack Surface

Poisoning isn't limited to reward signals. Attackers can also manipulate the "physics" of the environment or the actions the agent takes.

Vulnerability and Stability

The timing of an attack is as important as its magnitude. Yanchao Sun and Furong Huang introduced the concept of a "stability radius" to identify when an RL agent is most vulnerable Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics. During periods of high policy instability—often early in training—small perturbations have a disproportionately large impact on the agent's final convergence.

This leads to a troubling conclusion for multi-agent systems: Fan Yao and Haifeng Xu proved that poisoning just a single agent's rewards is often sufficient to ruin the learning process for the entire group, steering the whole system toward a "fake" equilibrium Single-agent Poisoning Attacks Suffice to Ruin Multi-Agent Learning.

In summary, sequential learners are vulnerable because their efficiency is their downfall. Because they learn to stop exploring "bad" options, an attacker only needs to make the truth look "bad" a sublinear number of times before the learner stops looking for it entirely.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 25 papers
  2. Version 1 · 2026-10-04 · 43 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sublinear_attack_cost_a33c9582,
  title = {sublinear attack cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-attack-cost/rdr_a33c9582957b4ac88cc4cb1869b82dad},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sublinear_cost_poisoning_of_sequential_l_a33c9582_v1,
  title = {Sublinear Cost Poisoning of Sequential Learners},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-cost-poisoning-of-sequential-learners/rdr_a33c9582957b4ac88cc4cb1869b82dad/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}