Learning to Attack: A Bandit Approach to Adversarial Context Poisoning

Ray Telikani; Amir H. Gandomi

cs.LGFeb 28, 2026

Learning to Attack: A Bandit Approach to Adversarial Context Poisoning

Authors: Ray Telikani, Amir H. Gandomi

Organizations: Data Science Institute, University of Technology Sydney, NSW, Australia

Abstract

Neural contextual bandits are vulnerable to adversarial attacks, where subtle perturbations to rewards, actions, or contexts induce suboptimal decisions. We introduce AdvBandit, a black-box adaptive attack that formulates context poisoning as a continuous-armed bandit problem, enabling the attacker to jointly learn and exploit the victim's evolving policy. The attacker requires no access to the victim's internal parameters, reward function, or gradient information; instead, it constructs a surrogate model using a maximum-entropy inverse reinforcement learning module from observed context-action pairs and optimizes perturbations against this surrogate using projected gradient descent. An upper confidence bound-aware Gaussian process guides arm selection. An attack-budget control mechanism is also introduced to limit detection risk and overhead. We provide theoretical guarantees, including sublinear attacker regret and lower bounds on victim regret linear in the number of attacks. Experiments on three real-world datasets (Yelp, MovieLens, and Disin) against various victim contextual bandits demonstrate that our attack model achieves higher cumulative victim regret than state-of-the-art baselines.

Figures & tables

Panel of Figure 1 — Figure 1: Performance evaluation of AdvBandit under adversarial settings in terms of regret on real datasets.

Figure 2: Distribution of continuous arm components (

\lambda^{(1)}

(effectiveness),

\lambda^{(2)}

(evasion),

\lambda^{(3)}

(temporal)) across victim algorithms on the Yelp dataset.

Figure 3: Performance of different attack strategies under varying attack budgets: averaged from the real datasets (Yelp, MovieLens, and Disin).

Figure 4: Runtime scalability of attack baselines: (a) horizon

T

(fixed

B=200

) and (b) attack budget

B

(fixed

T=5000

). Red stars (

\bigstar

) and vertical lines mark the standard experimental setting (

T=5000

B=200

) used throughout the paper.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Notation	Definition	Notation	Definition
$T$	Time horizon (total rounds)	$H(\hat{\pi}(\mathbf{x}))$	Policy entropy
$K$	Number of arms (actions)	$d$	Dimension of context vector
$\mathbf{x}_{t}$	True context, $\mathbf{x}_{t}\in\mathcal{X}\subseteq\mathbb{R}^{d}$	$\tilde{\mathbf{x}}_{t}$	Perturbed context, $\tilde{\mathbf{x}}_{t}=\mathbf{x}_{t}+\bm{\delta}_{t}$
$\mathcal{A}_{t}$	Set of available arms at $t$	$a_{t}$	Arm selected by learner at $t$
$a^{*}_{t}$	Optimal arm, $\arg\max_{a}h(\mathbf{x}_{t},a)$	$a^{\dagger}_{t}$	Target suboptimal arm
$\tilde{a}_{t}$	Victim’s action under $\tilde{\mathbf{x}}_{t}$	$h(\mathbf{x},a)$	True reward, $h:\mathcal{X}\times[K]\to[0,1]$

Appendix

Table 5

Victim Algorithm	Drift Bound $D_{\tau}$	$c_{\text{alg}}$	Drift Type	Eff. IRL Interval
NeuralUCB	$c^{\textsc{nu}}_{\beta}\sqrt{\tau/t}$	$O(\nu K)$	Sublinear	$\Delta_{\textsc{irl}}=O(\sqrt{T})$
NeuralLinUCB	$c^{\textsc{nl}}_{\beta}\cdot\tau/t$	$O(\alpha KL_{\phi})$	Faster	$\Delta_{\textsc{irl}}=O(T^{1/3})$
NeuralTS	$c^{\textsc{ts}}_{\beta}\sqrt{\tau/t}\cdot K\sigma_{\text{post}}$	$O(\nu K^{2}\sigma_{\text{post}})$	Sublinear	$\Delta_{\textsc{irl}}=O(\sqrt{T})$
R-NeuralUCB	$c^{\textsc{rn}}_{\beta}\sqrt{\tau/t}$	$O((1{+}\beta^{\text{vic}})K)$	Sublinear	$\Delta_{\textsc{irl}}=O(\sqrt{T})$
RobustBandit	$c^{\textsc{rb}}_{\beta}\cdot\tau/\sqrt{T}$	$O(K\sqrt{\log K/T})$	Linear	$\Delta_{\textsc{irl}}=O(T^{1/4})$

Appendix

Table 1: Summary of victim-specific policy drift bounds. All bounds are stated for

\tau

rounds of drift starting from round

t

. The “Effective IRL interval” column gives the maximum

\Delta_{\textsc{irl}}

such that the tracking error (Theorem E.21 ) remains

O(1/T^{1/4})

Query Selection Variant	Victim Regret	Success Rate	Detection Rate	Budget Used
Pareto + Chebyshev (full, Eq. 12 )	$\mathbf{673\pm 52}$	0.42	0.19	197/200
Chebyshev only (no Pareto filter)	$651\pm 54$	0.41	0.20	195/200
Product scalarization ( $f_{1}\cdot f_{2}\cdot f_{3}$ )	$618\pm 55$	0.39	0.22	193/200
Single-objective ( $\Delta\cdot P$ , no stealth)	$601\pm 49$	0.40	0.28	198/200
$\epsilon$ -greedy ( $\epsilon=0.1$ , best-tuned)	$448\pm 45$	0.35	0.27	189/200
Random ( $B/T$ )	$289\pm 38$	0.25	0.27	200/200

Appendix

Table 2: Query selection variant comparison on Yelp (R-NeuralUCB,

B=200

). The full method (Pareto + Chebyshev) achieves the best performance; the single-objective variant retains

89\%

effectiveness and may be preferred when simplicity is prioritized.

Panel of Figure 5 — Figure 5: Distribution of continuous arm components ( $\lambda^{(1)}$ (effectiveness), $\lambda^{(2)}$ (evasion), $\lambda^{(3)}$ (temporal)) across victim algorithms on the MovieLens and Disin datasets.

Remove IRL (use ground-truth reward)
Variant	Victim Regret	Success Rate	Detection Rate	Runtime (s)
AdvBandit (Full)	673 $\pm$ 52	0.42	0.19	142.3
Oracle reward	628 $\pm$ 48	0.47	0.18	89.5
Replace IRL with alternatives
Behavior cloning	412 $\pm$ 45	0.34	0.24	136.7
Inverse Q-learning	468 $\pm$ 49	0.38	0.21	158.2

Appendix

Table 3: Component ablation on Yelp (R-NeuralUCB victim,

B=200

). Each row removes one component. Values are victim regret (higher is better for attacker).

Dimension	Victim Regret	Success Rate	Detection Rate	Samples Needed	Runtime (s)
1D $(\lambda^{(1)},0,0)$	245 $\pm$ 32	0.31	0.42	87	12.3
2D-A $(\lambda^{(1)},\lambda^{(2)},0)$	412 $\pm$ 41	0.38	0.28	134	18.7
2D-B $(\lambda^{(1)},0,\lambda^{(3)})$	389 $\pm$ 38	0.36	0.35	128	17.9
3D $(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)})$	573 $\pm$ 52	0.42	0.19	686	26.4
4D $(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)})$	581 $\pm$ 49	0.43	0.18	3,972	51.2
5D $(\lambda^{(1)},\lambda^{(2)},\lambda^{(3)},\lambda^{(4)},\lambda^{(5)})$	587 $\pm$ 51	0.43	0.17	20,648	89.7

Appendix

Table 4: Attack performance vs. dimensionality on the Yelp dataset (R-NeuralUCB victim,

B=200

Budget $B$	Victim Regret $R_{v}(T)$					Best	Advantage	Efficiency
Budget $B$	AdvBandit	Liu	Ma	Garcelon	Ilyas	Baseline	Advantage	Efficiency
50	112	59	55	38	36	59	1.90×	2.23
100	200	126	115	67	60	126	1.59×	2.00
150	295	178	164	85	82	178	1.66×	1.97
200	393	231	219	114	102	231	1.71×	1.97
250	447	333	283	128	115	333	1.34×	1.79

Appendix

Table 5: Budget-Regret Trade-off Analysis on Yelp with R-NeuralUCB victim (

T=5000

). AdvBandit achieves 1.3×–1.9× higher regret than best baseline across all budgets, with power-law scaling

R_{v}(B)\approx 3.25\cdot B^{0.90}

confirming diminishing returns beyond

B=250

Feature Set	Dimension	Victim Regret	Success Rate	GP $\gamma_{n}$
Raw context $x$	20	287 $\pm$ 45	0.24	$O((\log n)^{21})$
PCA (top 5)	5	421 $\pm$ 38	0.34	$O((\log n)^{6})$
Random projection	5	398 $\pm$ 41	0.32	$O((\log n)^{6})$
Autoencoder	5	445 $\pm$ 39	0.36	$O((\log n)^{6})$
$\psi_{1}$ only (entropy)	1	312 $\pm$ 36	0.28	$O((\log n)^{2})$
$\psi_{1},\psi_{4}$ (entropy, gap)	2	456 $\pm$ 42	0.37	$O((\log n)^{3})$

Appendix

Table 6: Feature ablation on Yelp (R-NeuralUCB,

B=200

)

Figure 6: Correlation between features

\psi_{i}

and attack reward

r

on 1000 held-out attacks. All features show significant correlation (

p<0.001

), validating their predictiveness.

$W$	$\Delta_{\text{IRL}}$	Yelp ( $d=20$ )				MovieLens ( $d=20$ )				Disin ( $d=8$ )
$W$	$\Delta_{\text{IRL}}$	Regret	KL	Track	Time	Regret	KL	Track	Time	Regret	KL	Track	Time
50	50	453	0.20	0.12	110	425	0.20	0.12	109	360	0.20	0.12	91
100	50	513	0.12	0.13	119	529	0.11	0.12	111	443	0.12	0.11	95
200	100	553	0.09	0.06	115	589	0.06	0.05	116	545	0.09	0.06	101
400	100	684	0.03	0.03	138	718	0.05	0.04	138	558	0.04	0.04	124
800	200	505	0.04	0.06	135	494	0.03	0.06	143	–	–	–	–

Appendix

Table 7: IRL hyperparameter ablation across three datasets (

T=5000

B=200

). Window size

W

controls training data; retraining interval

\Delta_{\text{IRL}}

controls update frequency. Optimal:

W=400,\Delta_{\text{IRL}}=100

for

d=20

;

W=300,\Delta_{\text{IRL}}=75

for

d=8

Strategy	Attacks Used	Avg. $v(x_{t})$	Victim Regret	Success Rate	Efficiency
Random ( $B/T$ )	200	0.312	289 $\pm$ 38	0.25	0.0145
Fixed threshold ( $\tau=0.5$ )	143 $\pm$ 27	0.581	378 $\pm$ 42	0.31	0.0264
$\epsilon$ -greedy ( $\epsilon=0.1$ )	189 $\pm$ 15	0.487	448 $\pm$ 45	0.35	0.0237
Top- $B$ oracle (offline)	200	0.734	712 $\pm$ 61	0.48	0.0356
Quantile (Ours)	197 $\pm$ 8	0.689	673 $\pm$ 52	0.42	0.0291

Appendix

Table 8: Query selection ablation on Yelp (R-NeuralUCB,

B=200

)

Figure 7: Evolution of query threshold

\tau_{v}(b,T-t)

over time. Threshold increases as budget depletes, ensuring selective attacks at the end (red line: Threshold

\tau_{v}

, gray dots: not attacked, green dots: attacked, and blue shaded area: remaining budget).

Perturbation Method	Victim Regret	Success Rate	Surrogate Queries	Runtime (s)	Gradient-Free?
PGD (default)	$673\pm 52$	0.42	$100$ (grad steps)	142	No (surrogate grads)
NES ( $N=50$ )	$565\pm 58$	0.37	$5{,}000$ (fwd passes)	189	✓
Random search	$312\pm 41$	0.24	$500$ (fwd passes)	108	✓
Random $\bm{\delta}$ (no surrogate)	$134\pm 29$	0.15	$0$	88	✓

Appendix

Table 9: Zero-order perturbation ablation on Yelp (R-NeuralUCB,

B=200

). PGD on the surrogate achieves the best performance, but NES retains 84% effectiveness using only forward evaluations of the surrogate.

Method	Runtime (seconds)			Complexity	Key Operations
Method	Yelp	MovieLens	Disin	Complexity	Key Operations
Liu et al.	46.3	48.8	41.6	$O(T+B\cdot I_{\text{PGD}})$	PGD on fixed objective
Garcelon et al.	52.4	54.8	43.5	$O(T+B\cdot I_{\text{PGD}})$	Gradient-free perturbations
Ma et al.	40.0	37.8	32.2	$O(T+B\cdot I_{\text{PGD}})$	Greedy context selection
Ilyas et al.	96.1	91.7	79.0	$O(T+B\cdot N_{\text{grad}}\cdot I_{\text{PGD}})$	Bandit gradient estimation
Wang et al.	66.6	65.8	58.2	$O(T+B\cdot N_{\text{sample}}\cdot I_{\text{PGD}})$	Random sampling

Appendix

Table 10: Baseline method runtimes and complexity across three datasets (

T=5000

B=200

). AdvBandit incurs 3.5×–3.7× runtime overhead due to IRL learning, GP updates, and multi-start optimization, but achieves 2.9×–3.0× higher victim regret across all datasets.

Component	Memory (MB)			Scaling
Component	Yelp	MovieLens	Disin	Scaling
IRL networks ( $\hat{h}_{\theta},\hat{\sigma}_{\phi}$ )	128.0	128.0	51.2	$O(d\cdot d_{h}\cdot K)$
IRL training buffer ( $W$ samples)	3.1	3.1	1.2	$O(W\cdot d)$
GP kernel matrix ( $K\in\mathbb{R}^{B\times B}$ )	91.6	91.6	91.6	$O(B^{2})$
GP observations ( $\{(\psi_{i},\lambda_{i},r_{i})\}$ )	0.1	0.1	0.1	$O(B\cdot 9)$
Gradient statistics ( $\mu_{g},\Sigma_{g}$ )	0.1	0.1	<0.1	$O(d^{2})$

Appendix

Table 11: Memory usage breakdown across three datasets (

T=5000

B=200

). Dominant components are IRL networks (57% for

d=20

, 35% for

d=8

) and GP kernel matrix (41% for

d=20

, 63% for

d=8

). Lower-dimensional datasets require 35% less memory overall.

Dataset	Regret		Runtime (s)		Memory (MB)		Efficiency		Improvement
Dataset	Ma	AdvBandit	Ma	AdvBandit	Ma	AdvBandit	R/T	R/M	Improvement
Yelp	211	616	40.0	140.6	181	223	0.83×	2.37×	2.92×
MovieLens	226	683	37.8	139.0	181	223	0.82×	2.45×	3.02×
Disin	191	573	32.2	118.5	102	144	0.81×	2.13×	3.00×
Average	209	624	36.7	132.7	155	197	0.82×	2.32×	2.98×
R/T = Regret per second (time efficiency); R/M = Regret per MB (memory efficiency)

Appendix

Table 12: Cost-benefit trade-off: AdvBandit vs. best baseline (Ma et al.) across three datasets. AdvBandit achieves 2.9×–3.0× higher regret despite 3.5×–3.7× runtime overhead and 1.2×–1.4× memory overhead, maintaining 81–83% efficiency per computational unit.

Black-Box Adversarial Attacks

Black-box adversarial attacks study how inputs can fool AI systems when attackers cannot inspect model parameters or gradients.

See all 174 papers

Oct 7, 2026

Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards

Adversarial attacks on bandits aim to mislead a learner toward a target arm while keeping the attack cost small. Existing attacks typically achieve this by suppressing non-target arms. In practice, however, manipulation such as fake reviews often directly promotes the target item. We study this gap through bounded offline attacks on warm-start bandits, where an attacker can inject only valid action-reward pairs into the warm-start history before deployment. We show that target promotion is not merely a heuristic: when the target arm lies near the lower reward boundary, any order-optimal-cost attack against UCB that makes it selected in nearly all online rounds must allocate a nonvanishing fraction of its cost to the target arm. We then design an attack that achieves the optimal sublinear cost and characterize its allocation between target promotion and non-target suppression. We further extend the attack to Thompson Sampling,

ε

-greedy, and a broader class of bandit algorithms. Experiments on real-world and synthetic data validate the effectiveness of our attacks.

Qirun Zeng, Manhin Poon, Xiangxiang Dai +2

City University of Hong Kong, Hong Kong SAR, China · The Chinese University of Hong Kong, Hong Kong SAR, China · Nanyang Technological University, Singapore

Adversarial Attacks Multi-Armed Bandits Bandit Learning Data Poisoning Attacks

Ask PDF

May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal

\mathsf{SquareCB}

algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most

U_T

, our algorithm achieves

O(\sqrt{KTU_T})

regret and

O(\sqrt{KTU_T}\log T)

cumulative expected cost, with high probability, improving upon the previous

O(T^{3/4})

type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Contextual Bandits Adversarial Bandits

Ask PDF

Mar 16, 2026

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite

(1+ε)

-th moments for some

ε\in (0,1]

. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs

\mathcal{O}(t\log T)

computational cost, our algorithm reduces this to

\mathcal{O}(1)

per round. We establish an additive regret bound consisting of a term depending on the

(1+ε)

-moment bound of the noise and a term depending on the total amount of corruption. In particular, when

ε= 1

, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.

Naoto Tani, Futoshi Futami

The University of Osaka · RIKEN AIP · The University of Tokyo

Contextual Bandits Linear Contextual Bandits Multi-Armed Bandits

Ask PDF

Abstract

Black-Box Adversarial Attacks

Explore similar work

Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards

Constrained Contextual Bandits with Adversarial Contexts

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise