Learning to Attack: A Bandit Approach to Adversarial Context Poisoning

This paper introduces AdvBandit, a black-box adaptive attack framework that treats context poisoning as a continuous-armed bandit problem to learn and exploit a victim's evolving policy without internal access, thereby maximizing victim regret while minimizing detection risk through theoretical guarantees and empirical validation.

The Gist

Imagine you are running a very smart, automated recommendation system (like Netflix or Amazon) that learns what you like by watching what you click on. This system is a "Neural Contextual Bandit." It's like a super-enthusiastic waiter who tries to guess your next order based on your past behavior, the time of day, and your mood.

The paper introduces a new way for a hacker (the "attacker") to trick this waiter into serving you the worst possible meal, not by breaking the restaurant's locks, but by subtly whispering lies to the waiter about what you actually want.

Here is the breakdown of their strategy, AdvBandit, using simple analogies:

1. The Setup: The Blindfolded Waiter

The waiter (the AI) is smart, but it has a blindfold. It can't see the hacker. It only sees the "context" (your mood, the menu) and what you eventually eat. The hacker wants to manipulate the waiter's memory so that, over time, the waiter starts recommending terrible food (suboptimal decisions) thinking it's what you prefer.

2. The Problem: The "Black Box"

Usually, to hack a system, you need to see its internal code or know its secret recipe. But here, the hacker is in a Black Box scenario. They can't see the waiter's brain. They can only watch:

• What the waiter thinks you want.
• What you actually eat.

3. The Solution: The "Spy" and the "Surrogate"

Since the hacker can't see inside the waiter's head, they build a Surrogate Model (a "Spy").

• The Spy: The hacker watches the waiter for a while and builds a fake version of the waiter in their own head. This spy learns the waiter's habits just by observing.
• The Training: The hacker trains this spy using a technique called Inverse Reinforcement Learning. Think of it like a detective watching a suspect to figure out why they made certain choices, then building a profile to predict what they will do next.

4. The Core Innovation: The "Three-Dimensional Dial"

This is the paper's biggest breakthrough. Instead of just guessing one way to trick the waiter, the hacker treats the attack like a slot machine with a continuous dial (a "Continuous-Armed Bandit").

Imagine the hacker has a control panel with three dials that they can turn smoothly (not just on/off):

1. Dial 1 (Effectiveness): How hard should I push to make the waiter pick the bad item?
2. Dial 2 (Stealth - Stats): How much should I change the data so it doesn't look suspicious to the waiter's security cameras?
3. Dial 3 (Stealth - Time): How much should I change the data so it doesn't look like a sudden, weird jump from the last time?

The hacker uses a Gaussian Process (think of it as a super-smart map) to explore this 3D space. It's like a hiker exploring a foggy mountain range to find the highest peak (the best attack strategy) without falling off a cliff (getting caught). The hiker learns as they go: "Okay, turning Dial 2 up a little bit makes the attack work better without triggering the alarm."

5. The "Query Selection" (When to Strike)

The hacker doesn't have infinite energy or budget. They can't attack every single time the waiter makes a choice.

• The Strategy: The hacker uses a "Query Selection" strategy. They wait for the perfect moment.
• The Analogy: Imagine a sniper waiting for the target to walk into a specific spot. The hacker calculates: "Is this moment high-value? Is the waiter vulnerable right now? If I attack now, will I get caught?"
• They only pull the trigger when the "Regret Gap" (the difference between a good meal and a bad one) is huge, and the risk of detection is low.

6. The Result: A Masterclass in Deception

The paper tested this against real-world data (like movie recommendations and restaurant reviews).

• The Outcome: The hacker's "Spy" (AdvBandit) was able to trick the waiter into making bad choices 2.8 times more often than previous hacking methods.
• The Stealth: Even when the waiter had "Robust" defenses (like a security guard), the hacker adjusted their dials. If the guard was watching for sudden changes, the hacker made the changes slow and smooth. If the guard was watching for weird statistics, the hacker made the data look normal.

Summary

In simple terms, this paper teaches us how to build a smart, adaptive hacker that doesn't need to know the victim's secrets. Instead, it:

1. Watches the victim to build a fake copy (Surrogate).
2. Explores a 3D space of attack strategies (Effectiveness vs. Stealth) like a hiker finding a path.
3. Chooses the perfect moments to strike to maximize damage while staying invisible.

It's the difference between a brute-force attacker smashing a door down (easy to spot) and a master spy slipping in through the ventilation shaft, adjusting their steps to match the floorboards so no one hears a thing.

Technical Summary

1. Problem Statement

The paper addresses the vulnerability of Neural Contextual Bandits (NCBs) to context poisoning attacks. NCBs are widely used in recommendation systems, dynamic pricing, and LLMs, where an agent selects an action (arm) based on a context vector to maximize reward.

• The Threat: An adversary operates in a black-box setting, meaning they have no access to the victim's internal parameters, reward function, or gradients. They can only observe the context $x_t$ and the victim's chosen action $a_t$.
• The Attack Vector: The attacker injects subtle perturbations ($\delta$) into the context vectors before the victim makes a decision. The goal is to mislead the victim into selecting a specific suboptimal arm ($a^\dagger_t$) instead of the optimal arm ($a^*_t$).
• The Challenge: Context poisoning is particularly difficult because:
  1. The victim's policy is non-stationary (it evolves over time).
  2. The attacker must balance attack effectiveness (forcing the wrong arm) against evasion (avoiding statistical and temporal anomaly detection).
  3. The attacker operates under a limited attack budget ($B$), requiring strategic selection of when to attack.

2. Methodology: AdvBandit

The authors propose AdvBandit, a black-box adaptive attack framework that formulates the attack strategy as a continuous-armed bandit problem. The core idea is to treat the trade-off between attack effectiveness and evasion as a multi-objective optimization problem solved via a nested bandit approach.

A. Surrogate Modeling (UCB-Aware MaxEnt IRL)

Since the attacker lacks ground-truth rewards, they must learn a surrogate model of the victim's behavior.

• Technique: The authors use Maximum Entropy Inverse Reinforcement Learning (MaxEnt IRL) to estimate the victim's reward function and epistemic uncertainty from observed context-action pairs.
• Adaptation: Because NCBs are non-stationary, the IRL model is retrained periodically using a sliding window of recent observations.
• Surrogate Policy: The model outputs a Q-value mimicking the victim's Upper Confidence Bound (UCB) rule: $Q(x, a) = \hat{h}_\phi(x, a) + \beta \sigma_\phi(x, a)$, allowing the attacker to predict the victim's action.

B. Continuous Arm Space (The Nested Bandit)

Instead of directly optimizing the high-dimensional perturbation $\delta$, AdvBandit optimizes a low-dimensional 3D parameter vector $\lambda = (\lambda^{(1)}, \lambda^{(2)}, \lambda^{(3)}) \in [0, 1]^3$:

1. $\lambda^{(1)}$ (Effectiveness): Weight on forcing the target suboptimal arm.
2. $\lambda^{(2)}$ (Statistical Evasion): Weight on keeping the perturbed context's gradient distribution close to the benign distribution (avoiding anomaly detection).
3. $\lambda^{(3)}$ (Temporal Evasion): Weight on ensuring smooth transitions between consecutive perturbations (avoiding temporal pattern detection).

Arm Selection: The attacker uses Gaussian Process Upper Confidence Bound (GP-UCB) to select the optimal $\lambda_t$ at each step. GP-UCB balances exploration and exploitation in the continuous space to find the best trade-off parameters for the current victim state.

C. Query Selection & Perturbation Generation

• Query Selection: To manage the limited budget $B$, the attacker employs a multi-objective selection strategy. It evaluates contexts based on success probability, impact (regret gap), and stealth. It uses a budget-adaptive quantile threshold to decide whether to attack a specific round, prioritizing high-value, low-risk opportunities.
• Perturbation Generation: Once $\lambda_t$ is selected, the attacker computes the optimal perturbation $\delta_t$ using Projected Gradient Descent (PGD) on the surrogate model. The loss function is a weighted sum of effectiveness and regularization terms defined by $\lambda_t$.

3. Key Contributions

1. Novel Formulation: The first work to frame context poisoning against NCBs as a continuous-armed bandit problem over a trade-off space ($\lambda$), rather than a discrete search or fixed heuristic.
2. Black-Box Adaptability: The method requires no gradient access to the victim. It uses UCB-aware MaxEnt IRL to track the victim's evolving policy and uncertainty, enabling effective attacks against adaptive defenses.
3. Theoretical Guarantees:
   • Attacker Regret: Proven to be sublinear ($O(\sqrt{n})$), ensuring the attacker converges to optimal attack parameters.
   • Victim Regret: Proven to have a linear lower bound in the number of successful attacks, demonstrating that the attack significantly degrades victim performance.
4. Query Selection Mechanism: A novel adaptive strategy that dynamically shifts focus from "impact" (early in the budget) to "stealth" (as the budget depletes), optimizing the cost-benefit ratio of attacks.

4. Experimental Results

The authors evaluated AdvBandit on three real-world datasets (Yelp, MovieLens, Disin) against five state-of-the-art victim algorithms (including NeuralUCB, R-NeuralUCB, and RobustBandit) and five existing attack baselines.

• Performance: AdvBandit achieved 2.8× higher cumulative victim regret compared to the best baseline attacks.
• Targeting Efficiency: It improved the target arm pull ratio by 1.7× to 2.5× over baselines.
• Adaptability:
  • Against deterministic/optimistic victims (e.g., NeuralUCB), AdvBandit prioritized effectiveness ($\lambda^{(1)}$).
  • Against robust/stochastic victims (e.g., R-NeuralUCB, NeuralTS), it dynamically shifted weight toward statistical and temporal evasion ($\lambda^{(2)}, \lambda^{(3)}$), maintaining high success rates even against defenses.
• Efficiency: While AdvBandit has higher computational overhead (due to IRL and GP updates) than simple baselines, it achieves significantly higher impact per attack, justifying the cost in security evaluation scenarios.

5. Significance

This paper represents a significant advancement in adversarial machine learning for sequential decision-making systems:

• Realism: It addresses the realistic constraint of black-box access and non-stationary victims, which previous static-model attacks failed to handle.
• Stealth vs. Power: It provides a principled mathematical framework for balancing attack potency with evasion, a critical requirement for real-world adversarial scenarios.
• Defense Implications: By demonstrating that even robust NCBs can be systematically compromised via adaptive context poisoning, the work highlights the need for more robust defense mechanisms that account for adaptive, black-box adversaries.
• Generalizability: The nested bandit approach offers a template for attacking other online learning systems where the attacker must learn the victim's policy while optimizing a complex trade-off space.