A bandit algorithm learns by repeatedly choosing among actions ("arms") and observing rewards, and a now well-mapped class of attacks shows that a small adversary can hijack one: by corrupting feedback for only a handful of rounds, the attacker tricks the learner into permanently preferring the attacker's chosen arm, while the learner suffers linear loss over the whole run. What makes this cheap is an avoidance loop — once competing arms look bad, the learner stops trying them, so the attacker can stop paying (Adversarial Attacks on Stochastic Bandits; the gap can be squeezed to $\Theta(\sqrt{\log T})$ total corruption for UCB and Thompson Sampling, against $\Omega(\log T)$ for $\epsilon$-greedy, per Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses). The causal-inference literature has a precise name for the property this attack destroys: positivity — the requirement that every action remains a live possibility, with selection probability bounded away from zero, which is exactly what makes inverse-probability-weighted estimators valid (Statistical Inference for Online Decision Making: In a Contextual Bandit Setting).
This proposal argues the connection is not superficial, and turns it into a defense. If every sublinear attack works by driving the data-collection probability on competing arms to zero, then the propensity-score toolkit — covariate balancing, bounded weights, design-based control of what gets sampled — is simultaneously an attack-resistance mechanism and an inference-preservation mechanism. We will build a contextual-bandit learner whose exploration is governed by explicit covariate balance constraints, characterize the exact trade-off between exploration spending, regret, and the attack cost needed to hijack it, and test whether balance maintenance also exposes action-poisoning attacks that reward outliers cannot catch.
Core Claim
Every hijacking attack in this literature pays only for the rounds in which the learner actually pulls a competitor, because only those rounds need corrupting. If the adversary must depress arm $a$ by a perceived gap $\Delta_a$ on essentially every pull to keep the avoidance loop alive, then its cumulative cost obeys
$$C_{\text{attack}} \;\ge\; \sum_{a \neq a^\dagger} \Delta_a \, N_a(T),$$
where $a^\dagger$ is the target arm and $N_a(T)$ is the number of times the learner pulls arm $a$ by horizon $T$. All known sublinear attacks work by making the $N_a$ of competitors $o(T)$. Our core claim is the converse, made operational: a learner that guarantees balanced, repeated sampling of competing arms across the context space forces any successful hijacker to spend $\Omega(\gamma \Delta T)$ — a linear budget, where $\gamma$ is the enforced sampling rate — while keeping inverse-probability weights bounded, so that online weighted least squares (Statistical Inference for Online Decision Making) stays asymptotically valid under attack. The cost of this guarantee is regret, and the design question is where to spend it: uniformly (as $\epsilon$-greedy does) or only where the environment is actually attackable. When Are Linear Stochastic Bandits Attackable? proves that attackability in linear bandits is a checkable property of context geometry, certified by a convex quadratic program over perturbations in the null space of the target arm's feature vector — the perturbation direction invisible to the target's own perceived reward. That certificate gives us a map of where attacks can hide, and we claim balance should be bought exactly there.
This differs from the closest prior work in three ways. The smoothed-response defense of Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses randomizes uniformly at the arm level in non-contextual bandits and guarantees a $(1-\epsilon)$ competitive reward ratio under sublinear budgets; it does not use context geometry, gives no explicit lower bound tying the attacker's cost to the randomization rate, and says nothing about whether the randomization supports valid propensity-weighted inference. The online IPW-WLS estimator of Statistical Inference for Online Decision Making restores asymptotic normality under misspecification but assumes an honest environment — an avoidance attack makes its own weights explode, a failure mode nobody has analyzed. And streaming covariate balancing itself exists only for passive data streams (Streaming Covariate Balancing via Discrepancy-Based Feature Coresets), never as a deliberate design choice by a decision-making agent facing an adversary.
Research Program
The theory component has three targets. First, an impossibility-plus-frontier result: any learner with sublinear regret pulls constant-gap competitors $o(T)$ times, so it is hijackable at sublinear cost (formalizing the observation behind the $\Theta(\sqrt{\log T})$ bounds); therefore linear attack resistance requires linear forced exploration, and we aim to prove the matching frontier — with forced-sampling rate $\gamma$, regret degrades to $O(\gamma T)$ while any hijack costs $\Omega(\gamma \Delta T)$, with matching upper bounds from a concrete attacker. Second, a dilution lemma: with balanced forced sampling, the bias an attacker can hold in the learner's reward estimate at time $t$ is $O(C_t / \gamma T)$, where $C_t$ is the attacker's cumulative spend, so sublinear budgets yield vanishing sustained bias — continued resampling washes out old corruption, which is exactly what the avoidance loop prevents. Third, a bias-variance statement for inference: bounded-below propensities bound the IPW weights, so the martingale central limit theorem argument of Statistical Inference for Online Decision Making survives adversarial corruption of vanishing per-sample influence.
The algorithmic component builds BAE (Balance-Aware Exploration), a linear contextual bandit that estimates rewards with online IPW-weighted least squares and reserves a slice of its pulls for a design-based balancing schedule: forced samples are placed to minimize the mean discrepancy between the context distributions observed for each arm, using the Random Fourier Feature coreset machinery of Streaming Covariate Balancing via Discrepancy-Based Feature Coresets (which runs in $O(\log n)$ memory and processed roughly 600,000 streaming samples in about 6 seconds while retaining 0.5% to 1% of history), with the direct balance-optimization perspective of Optimal Covariate Balancing Conditions in Propensity Score Estimation. Crucially, the forced-sampling rate per context region is proportional to the local mass of the online-estimated attackability certificate from When Are Linear Stochastic Bandits Attackable?: in geometries where the quadratic program certifies unattackability, BAE pays almost nothing; where the certificate is positive, it concentrates balance spending there. The expected payoff over uniform $\epsilon$-greedy is attack-resistance cost proportional to geometric vulnerability rather than to arm count — against a $\tilde{O}(T^{3/4})$-cost null-space attack, both resist, but in certified-unattackable environments only $\epsilon$-greedy keeps paying $\epsilon T$ regret forever.
The diagnostic component addresses action poisoning, where the attacker silently swaps the chosen action for another, so observed rewards are perfectly in-distribution for the swapped arm and outlier filters see nothing — the failure documented in Action Poisoning Attacks on Linear Contextual Bandits, which achieves 91% to 98% target-arm selection rates against LinUCB, Linear Thompson Sampling, and $\epsilon$-greedy at $O(\log^2 T)$ (white-box) or $O(\log^3 T)$ (black-box) cost. In causal terms this is treatment misclassification: an unobserved substitution mechanism that invalidates the logged action. Because BAE's balanced design samples each arm-context region repeatedly under known probabilities, it can compare the reward distribution of each arm under the design-based sample against the exploit-phase sample; sustained divergence flags misattribution rather than reward outliers. This is the online counterpart of what offline confounded policy learning handles with proxies and integral equations at $\tilde{O}(T^{-1/2})$ suboptimality (A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observations) — but that work is batch-only and cannot rescue a system being hijacked live.
Baselines
The do-nothing reference is vanilla LinUCB with no defense. It is the reference point that establishes the attacks work: on the synthetic linear-bandit benchmark of $k = 30$ arms, $d = 10$-dimensional contexts, and $T = 10{,}000$ rounds, the two-stage null-space attack forces LinUCB to pull the target arm $T - o(T)$ times at cost $\tilde{O}(T^{3/4})$ (When Are Linear Stochastic Bandits Attackable?), and on MovieLens 25M and Jester the action-poisoning attack reaches 91% to 98% target selection (Action Poisoning Attacks on Linear Contextual Bandits). Any defense must first move these numbers.
The strongest existing competitor is Robust Phase Elimination (RobustPhE), the corruption-robust learner evaluated in When Are Linear Stochastic Bandits Attackable? — the best published defense in the file, and one the attack still defeats, with the target arm pulled $T - o(T)$ times and cost rising only from $\tilde{O}(T^{3/4})$ to $\tilde{O}(T^{4/5})$. We will re-run RobustPhE under both the null-space and action-poisoning attacks with the same data, compute, and tuning budget as BAE (a shared grid over all defense parameters), and count BAE as winning only if the budget required to sustain 90% target selection grows linearly in $T$ where RobustPhE's stays sublinear, at no more than a constant-factor regret overhead in the attack-free case. The second strong competitor is constant-$\epsilon$ uniform exploration, which already guarantees positivity (its propensities are known by construction) and therefore both a linear attack barrier and stable IPW weights; it will be tuned over the same grid, and the honest beating criterion is regret: BAE should match its hijack-resistance while paying measurably less regret in certified-unattackable geometries.
Two ablations isolate the key ingredients. The first replaces BAE's discrepancy-guided placement with uniform forced exploration at a matched total forced-sample budget, so any difference is attributable to where samples go, not how many. The second removes certificate adaptivity (fixed-rate balancing everywhere), isolating whether vulnerability-adaptive spending is what buys the regret advantage. A third comparison adapts the Smoothed Myopic / Quantal Response defense of Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses to the contextual setting, to test whether arm-level randomization without covariate balancing leaves context-geometric attack routes open.
Why not just…?
Why not just use robust regression and outlier filtering? The corpus answers this directly: robust bandit algorithms designed to filter reward outliers "are often ineffective against action poisoning because they trust the integrity of the action-reward pairing" — swapped actions produce in-distribution rewards, so nothing looks anomalous (Action Poisoning Attacks on Linear Contextual Bandits). Even for pure reward poisoning, RobustPhE — the state of the art in robustness — is still hijacked at $\tilde{O}(T^{4/5})$ cost (When Are Linear Stochastic Bandits Attackable?). The propensity literature adds a caution on the naive fix for exploding weights: trimming reduces variance but introduces substantial bias (Weight Trimming and Propensity Score Weighting). Our design-based approach bounds the weights at the source rather than trimming them afterward.
Why not just run constant $\epsilon$-greedy? This is the most serious alternative, and we treat it as a co-equal baseline rather than arguing around it: constant $\epsilon$ genuinely delivers positivity, a linear attack barrier, and known propensities, and $\epsilon$-greedy provably demands $\Omega(\log T)$ corruption versus $\Theta(\sqrt{\log T})$ for adaptive learners (Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses). Its weakness is the flat tax: it pays $\epsilon T$ regret forever, even in environments whose geometry certifies them as unattackable, and it rebalances only at the arm level, leaving context regions where null-space perturbations can concentrate unmonitored. Our matched-budget ablation is designed precisely to settle this: if uniform exploration at the same sample count matches BAE on hijack resistance, detection, and regret across both attackable and unattackable geometries, we will report that the frontier characterization — not the algorithm — is the contribution.
Why not just detect the attack with change-point methods? Two-stage attacks do leave an abrupt distributional shift that a sophisticated change-point detector might catch — the authors of the null-space attack say so themselves (When Are Linear Stochastic Bandits Attackable?) — but gap-ensuring attacks corrupt smoothly, scaling corruption exponentially in pull counts, leaving no discrete shift to trigger on (Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses), and phased attack-then-quit designs in ranking concentrate corruption early and then stop (Adversarial Attacks on Online Learning to Rank with Stochastic Click Models). Detection after the fact also cannot restore valid inference or un-hijack a live system; our experiments include a change-point detector as a diagnostic baseline and measure time-to-flag versus damage-already-inflicted.
Why not just log everything and run retrospective propensity matching offline? Once the avoidance loop locks in, the logging policy stops collecting data on competitors entirely, so the common support that retrospective matching requires is violated by construction — there is nothing left to match on. Retrospective reprocessing is also operationally prohibitive at streaming scale, which is exactly why FCore exists: it processes about 600,000 samples in roughly 6 seconds while retaining 0.5% to 1% of history (Streaming Covariate Balancing via Discrepancy-Based Feature Coresets). Production systems do care about the causal gap — LinkedIn's matching cut a naive 10% lift estimate to a true 2.4% (The Importance of Being Causal: Scaling Observational Inference at LinkedIn) — but a batch analysis after a hijack recovers neither the lost revenue nor the missing data.
Proposed Experiments
The primary testbed is the synthetic linear-bandit benchmark from When Are Linear Stochastic Bandits Attackable?: $k = 30$ arms, $d = 10$ contexts, $T = 10{,}000$ rounds, swept across both CQP-attackable and certified-unattackable geometries. We run the published two-stage null-space attack against LinUCB (expected: target pulled $T - o(T)$ times at $\tilde{O}(T^{3/4})$ cost), RobustPhE (expected: $\tilde{O}(T^{4/5})$), constant $\epsilon$-greedy, the contextualized smoothed-response defense, and BAE with both ablations. The decisive metrics are the attacker's cumulative budget needed to sustain 90% target selection as $T$ grows (BAE must show a linear slope where competitors stay sublinear) and attack-free regret (BAE must stay within a small constant of LinUCB in unattackable geometries while $\epsilon$-greedy pays its flat tax).
The second experiment replays the action-poisoning protocol of Action Poisoning Attacks on Linear Contextual Bandits on MovieLens 25M and on Jester (10 arms from matrix factorization of its 4.1 million joke ratings), where the published attack achieves 91% to 98% target selection across LinUCB, LinTS, and $\epsilon$-greedy at $O(\log^2 T)$ to $O(\log^3 T)$ cost. Success means driving the selection rate toward the no-attack policy's rate and flagging the swap via the balance diagnostic before the attacker's budget is spent; we will also report the diagnostic's false-alarm rate in attack-free runs. The third experiment evaluates inference validity in the style of Statistical Inference for Online Decision Making, whose $\epsilon$-greedy policy achieved a 4.71% click-through rate versus 4.14% for random on roughly 400,000 Yahoo! Today Module recommendations: we measure 95% Wald interval coverage of the IPW-WLS estimator under sublinear attack, expecting coverage collapse for vanilla WLS (whose weights explode as competitors' selection probabilities are driven down) and near-nominal coverage under BAE. No reported result found on Lacuna for interval coverage under adversarial attack, so this is a genuinely unmeasured quantity. Finally, the arm-level special case is checked on the synthetic stochastic corruption benchmark of Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses (where, at $\sigma = 1$, $\mu = 0.1$, the near-optimal attack costs about 14.5 units versus 114.4 for the baseline attack): in the non-contextual limit BAE should reduce to smoothed-response-style randomization, and any excess cost there bounds the price of the balancing machinery.
The decisive check for the whole proposal is a single two-panel plot: attacker budget for a sustained hijack against $T$ (slope must turn from sublinear to linear under BAE), side by side with attack-free regret across geometries (BAE's advantage must appear exactly where the certificate says attacks can hide). If both panels come out as predicted, covariate balancing is a defense; if the second panel shows no regret advantage over tuned uniform exploration, the frontier theorem stands but the algorithm does not — and we will say so.
References
- Adversarial Attacks on Stochastic Bandits
- Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses
- Statistical Inference for Online Decision Making: In a Contextual Bandit Setting
- When Are Linear Stochastic Bandits Attackable?
- Streaming Covariate Balancing via Discrepancy-Based Feature Coresets
- Optimal Covariate Balancing Conditions in Propensity Score Estimation
- Action Poisoning Attacks on Linear Contextual Bandits
- A Unified Framework of Policy Learning for Contextual Bandit with Confounding Bias and Missing Observations
- Weight Trimming and Propensity Score Weighting
- Adversarial Attacks on Online Learning to Rank with Stochastic Click Models
- The Importance of Being Causal