Sublinear Cost of Hijacking Online Learning

57 concepts26 papers1 proposal

In traditional machine learning, poisoning an algorithm typically requires a massive, sustained effort. If you want to corrupt a static dataset, your attack budget generally scales linearly with the size of the data.

Intuitively, one might expect dynamic, real-time decision systems—like Multi-Armed Bandits (MABs) and Reinforcement Learning (RL) agents—to be even harder to fool. These systems constantly explore their environments, update their beliefs, and adapt to changing feedback. If an adversary injects a bit of noise, shouldn't an online learner eventually gather enough clean data to see through the manipulation?

Surprisingly, the exact opposite is true. The very mechanism that makes online learning efficient—the exploitation of historical feedback to avoid suboptimal choices—creates a profound security vulnerability. A long line of research has demonstrated a striking cost asymmetry: an adversary can permanently hijack an online learner's behavior with a total intervention budget that grows sublinearly (often logarithmically) over time, while forcing the learner to suffer linear performance loss.

The Core Intuition: Exploiting Avoidance

To understand why these attacks are so cheap, we have to look at how online algorithms balance exploration and exploitation. Consider a standard stochastic bandit algorithm like Upper Confidence Bound (UCB) or Thompson Sampling. The algorithm maintains statistical estimates of each option's (or "arm's") reward. It prefers options with high estimated rewards or high uncertainty.

If the algorithm chooses a highly rewarding arm and receives a low reward, it updates its internal parameters, reducing its preference for that arm. As Fang Liu et al. demonstrated, an adversary can exploit this by strategically poisoning rewards to force the system to prefer a suboptimal target arm indefinitely.

The secret to the sublinear cost lies in a feedback loop of avoidance. As explained by Jun et al., an attacker does not need to constantly inflate the target arm's rewards. Instead, a more efficient strategy is to suppress the perceived rewards of competing options.

[Attacker Suppresses Competitor Reward] 
                 │
                 ▼
[Learner Perceives Competitor as Suboptimal] 
                 │
                 ▼
[Learner Avoids Selecting Competitor] 
                 │
                 ▼
[Attacker No Longer Needs to Spend Budget on Competitor]

Once the learning agent begins to avoid the suppressed options, it stops gathering data about them. Because the agent rarely selects these competing options, the attacker rarely has to intervene. The agent's own exploration-exploitation mechanism locks in the manipulated state, doing the attacker's work for free. Consequently, the cumulative effort required for subversion scales logarithmically with time, meaning the cost of the attack is proportional to the agent's own diminishing learning error.

Tapering Off: Phased and Asymptotic Attacks

Because online learners freeze their preferences once they believe they have found the optimal strategy, attackers can concentrate their efforts early in the learning process and then taper off completely.

In Online Learning to Rank (OLTR) systems, which optimize search results based on user clicks, Zichen Wang et al. introduced phased feedback poisoning strategies like "Attack-Then-Quit." By focusing manipulation entirely during the initial exploration phase, the attacker tricks the algorithm's elimination mechanism into deprioritizing true competitors. Once the system locks the target item into the top ranking, the attacker can cease intervention entirely, achieving permanent manipulation at a sublinear total cost.

This means that as the number of interactions $T$ grows, the average cost of the attack per round approaches zero. Jinhang Zuo et al. proved that even under strict binary feedback constraints, an attacker can maintain a conservative lower bound of an item's performance to decouple the desired attack value from actual feedback, dominating the selection process indefinitely for a sublinear cost.

This principle extends directly from simple bandits to complex environments. In online reinforcement learning, Rakhsha et al. showed that the cost of environment poisoning diminishes to zero once the agent successfully adopts the target policy. Because the agent eventually stops exploring non-target actions that have been manipulated, the adversary no longer needs to apply active poisoning to maintain control.

Beyond Rewards: Action-Manipulation Attacks

What if an attacker cannot manipulate the rewards or feedback signals directly? The sublinear cost structure still holds if the adversary can intercept and alter the agent's chosen actions before they reach the environment.

Guanlin Liu et al. analyzed these action poisoning attacks on linear contextual bandits. By strategically swapping actions during early rounds, the attacker permanently shifts the agent's internal parameter estimates. Once the model's internal parameters are sufficiently biased, Garcelon et al. showed that the adversary needs to apply decreasingly frequent or intense perturbations to maintain control over the system's outputs.

This dynamic makes action-interception attacks highly stealthy. Because the interventions scale logarithmically, they become difficult to detect through simple frequency analysis, as the attacker interferes less frequently as time progresses. Guanlin Liu et al. proved that this black-box action poisoning remains highly effective even in full reinforcement learning settings, allowing an adversary to force an agent to follow a specific target policy with minimal long-term effort.

Multi-Agent Cascades: Exploiting Cooperation

The vulnerability to sublinear-cost attacks becomes even more pronounced in collaborative and multi-agent systems. In these environments, agents share information or converge toward shared equilibria, meaning an attacker does not need to compromise the entire network.

Yao et al. demonstrated that poisoning just a single agent's rewards is sufficient to steer an entire multi-agent learning system toward a "fake" equilibrium. As the targeted agent alters its behavior, the other agents adapt to this behavioral shift. Once the system begins to stabilize around the manipulated state, the amount of reward modification required to sustain the false equilibrium diminishes over time.

Similarly, Jinhang Zuo et al. showed that in cooperative multi-agent bandit systems, manipulating a single agent forces all agents to make suboptimal decisions for a large fraction of the time, achieving massive disruption with a sublinear budget.

However, single-channel attacks have limits in multi-agent reinforcement learning. As Guanlin Liu et al. noted, relying exclusively on either reward poisoning or action poisoning in complex multi-agent environments can sometimes cause costs to scale linearly. To bypass this, they proposed a mixed attack strategy combining both channels, which successfully restores the sublinear manipulation budget and preserves adversarial stealth.

The Limits of Attackability

While sublinear attack efficiency is widespread, online systems are not entirely defenseless; their safety is bounded by structural and geometric constraints.

  1. Target Quality Constraints: Forcing an agent to accept a moderately suboptimal option is cheap, but forcing it to accept a truly terrible option is not. Guanlin Liu et al. showed that forcing a learner to consistently choose the absolute worst-performing option requires an intervention budget that grows faster than logarithmically. If the target option consistently yields the lowest rewards across all contexts, the cost of maintaining the illusion of its optimality increases significantly.
  2. Geometric Constraints: In linear contextual bandits, options are represented as vectors in a shared space. Huazheng Wang et al. revealed that linear bandits can be intrinsically unattackable due to the geometric correlation between arms. If learning about one arm automatically reveals accurate information about another, an attacker cannot easily isolate and suppress a single option without breaking the mathematical consistency of the entire context space.

To counter these vulnerabilities, researchers are developing defenses that alter how algorithms respond to feedback. For instance, Shiliang Zuo introduced defense strategies like Smoothed and Quantal Responses. By injecting controlled behavioral stochasticity, these defenses prevent the algorithm from prematurely locking into a single manipulated choice, forcing the attacker's required budget to rise and breaking the sublinear cost advantage that makes online hijacking so dangerous.

Key Foundational Work

Adversarial Attacks on Stochastic Bandits (2018) — contributed 3 concept elements to this direction.
Data Poisoning Attacks on Stochastic Bandits (2019) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_sublinear_attack_cost_a33c9582_v2,
  title = {sublinear attack cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-attack-cost/rdr_a33c9582957b4ac88cc4cb1869b82dad/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake