Paper deep dive
Learning to Attack: A Bandit Approach to Adversarial Context Poisoning
Ray Telikani, Amir H. Gandomi
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 7/20/2026, 5:17:32 AM
Summary
The paper introduces AdvBandit, a black-box adaptive adversarial attack framework for neural contextual bandits. It formulates context poisoning as a continuous-armed bandit problem, using a maximum-entropy inverse reinforcement learning module to build a surrogate model of the victim's policy from observed context-action pairs. The attacker employs a Gaussian Process Upper Confidence Bound (GP-UCB) for arm selection and projected gradient descent to optimize perturbations, aiming to maximize victim regret while minimizing detection risk through an attack-budget control mechanism.
Entities (9)
Relation Signals (8)
AdvBandit → evaluatedon → Yelp
confidence 95% · Experiments on three real-world datasets (Yelp...)
AdvBandit → evaluatedon → Disin
confidence 95% · Experiments on three real-world datasets (...Disin)
AdvBandit → evaluatedon → MovieLens
confidence 95% · Experiments on three real-world datasets (...MovieLens...)
AdvBandit → targets → Neural Contextual Bandits
confidence 95% · Neural contextual bandits are vulnerable to adversarial attacks... We introduce AdvBandit
AdvBandit → performs → Context Poisoning
confidence 94% · formulates context poisoning as a continuous-armed bandit problem
AdvBandit → uses → GP-UCB
confidence 93% · An upper confidence bound-aware Gaussian process guides arm selection
AdvBandit → uses → Maximum-Entropy Inverse Reinforcement Learning
confidence 92% · constructs a surrogate model using a maximum-entropy inverse reinforcement learning module
AdvBandit → uses → Projected Gradient Descent
confidence 91% · optimizes perturbations against this surrogate using projected gradient descent
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.00567v1
- Canonical: https://arxiv.org/abs/2603.00567v1
Trouble viewing inline? Open PDF directly →
Full Text
168,117 characters extracted from source content.
Expand or collapse full text
An Adversarial Nested Bandit Approach for Neural Contextual bandits Ray Telikani Amir H. Gandomi 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. Keywords Adversarial Attacks ⋅· Contextual Bandits ⋅· Context Poisoning ⋅· Online Learning 1 Introduction Neural contextual bandit (NCB) algorithms are a major evolution of multi-armed bandits, where the learner has access to arm context information before making a decision and also leverages the representation power of neural networks to handle highly complex and non-linear relationships between context and reward Ban et al. (2021b); Wang et al. (2024). These algorithms are widely applied in domains such as recommendation systems Kveton et al. (2015), cloud resource allocation Dang’ana et al. (2026), clinical trials Kuleshov and Precup (2014), and dynamic pricing Tullii et al. (2024), and more recently, in large language models (LLMs) such as ChatGPT Achiam et al. (2023), Gemini Team et al. (2023), and DeepSeek Guo et al. (2025). It has been shown that NCBs are vulnerable to adversarial attacks, where an attacker subtly perturbs rewards Garcelon et al. (2020); Ding et al. (2022), actions Liu and Lai (2022), or contexts to mislead the learner into suboptimal decisions Ma et al. (2018); Zeng et al. (2025); Hosseini et al. (2025). In applications, such as human-centric AI, data packets between the AI agent and the user contain the reward signals and action decisions; therefore, an adversary can intercept and modify these data packets to force the contextual bandits system to learn a specific policy Liu and Lai (2022). In the attack on context, the adversary attacks before the agent pulls an arm; therefore, the context poisoning attack is the most difficult to carry out. Adversarial defenses for linear contextual bandits He et al. (2022) and more recently Qi et al. (2024) for NCBs. Inspired by prior bandit-based adversarial attacks on static machine learning models, such as Graph Neural Networks (GNNs) and Convolutional Neural Networks (CNNs) Ilyas et al. (2019); Wang et al. (2022), which cannot directly be extended to sequential decision-making processes, we introduce a two-player game framework. In this setup, the attacker learns an adaptive attack policy in a black-box setting, without access to the victim’s rewards, internal parameters, or gradient computations, while the victim learns its decision policy. The attacker observes only contexts and the victim’s actions and builds a surrogate model of the victim’s behavior from these observations and uses gradient-based optimization on this surrogate (not the victim) to generate perturbations. We make the following contributions: 1. We formulate the adversarial attack as a continuous-armed bandit problem over a 3D space =((1),(2),(3))∈ℝ+3 λ=( λ^(1), λ^(2), λ^(3)) ^3_+, in which each arm corresponds to three weighting parameters representing (1) attack effectiveness, (2) anomaly detection evasion, and (3) temporal pattern detection evasion, respectively. Due to the lack of reward availability, an adaptive UCB-Aware Maximum Entropy Inverse Reinforcement Learning (MaxEnt IRL Ziebart et al. (2008) is employed for reward estimation. We employ GP-UCB Srinivas et al. (2010) for arm selection, where each raw context is first transformed into a low-level feature vector based on gradient statistics for efficiency. To reduce resource consumption and detection risks, a query selection strategy is introduced to control attack timing and attack budget. Finally, the projected gradient descent (PGD) algorithm Madry et al. (2017) is utilized to compute the optimal perturbation for the context. 2. Theoretical Analysis: We provide regret guarantees for both the attacker and victim under non-stationary policies. For the attacker, we derive a sublinear cumulative regret bound, ensuring convergence to optimal attack parameters despite the continuous arm space. For the victim, we establish a lower bound on cumulative regret that is linear in the number of attacks, up to sublinear terms from the victim’s standard regret. Additionally, we analyze the tracking error of our IRL component under bounded policy drift, showing that periodic retraining achieves low error rates. 3. Experimental Analysis: We evaluate AdvBandit on three real-world datasets (Yelp, MovieLens, Disin) against five state-of-the-art attacks and five victim NCB algorithms. Experiments demonstrate that AdvBandit achieves 2.8× higher cumulative victim regret for NCBS compared to other attack baselines, with a 1.7-2.5× improvement in target arm pull ratios over the baselines. 2 Related Works Neural Contextual Bandits. NCBs extend classical contextual bandits by leveraging neural networks to model nonlinear reward functions, reducing reliance on domain knowledge Zhou et al. (2020). While early work established sublinear regret guarantees, these bounds were later shown to be linear under certain assumptions Deb et al. (2023). Subsequent studies improved theoretical guarantees using kernel-based analyses Kassraie and Krause (2022). Related extensions include contextual dueling bandits, which rely on preference feedback rather than numeric rewards, with recent neural UCB and Thompson sampling methods achieving sublinear regret Dudík et al. (2015); Verma et al. (2024). A major challenge in NCBs is accurate uncertainty estimation and the high computational cost of exploration. Variance-aware UCB methods address uncertainty miscalibration by incorporating reward noise variance Di et al. (2023); Zhang et al. (2021b); Zhou and Gu (2022); Bui et al. (2024), while shallow exploration techniques reduce complexity by restricting exploration to the last network layer Xu et al. (2022); Oh et al. (2025). Alternative designs, such as E-Net Ban et al. (2021b), decouple exploration and exploitation using dual networks, and multi-facet bandits model rewards across multiple aspects with provable sublinear regret Ban et al. (2021a). Finally, implicit exploration via reward perturbation has been proposed to avoid explicit parameter-space exploration while maintaining optimal regret rates Jia et al. (2022). Adversarial Attacks on Contextual Bandits. There have been studies working on tackling adversarial reward corruptions under linear contextual bandit settings for reward perturbation Garcelon et al. (2020); Ding et al. (2022), action manipulation Liu and Lai (2022), and context perturbation Ma et al. (2018); Zeng et al. (2025); Hosseini et al. (2025). In the attack on context, the adversary attacks before the agent pulls an arm; therefore, the context poisoning attack is the most difficult to carry out. Adversarial defenses for linear contextual bandits He et al. (2022) and more recently Qi et al. (2024) for NCBs. Bandit-based Adversarial Attacks. Ilyas et al. Ilyas et al. (2019) proposed a bandit-based black-box attack for image classifiers. However, their approach does not have a theoretical regret bound and is less efficient due to using multiple gradient estimations in each iteration. Wang et al. Wang et al. (2022) used bandit optimization for black-box structure perturbations on Graph neural networks (GNNs), where perturbations are arms, and queries to the GNN provide bandit feedback (loss values). The algorithm achieved sublinear regret O(NT3/4)O( NT^3/4). Unlike these attacks on static machine learning models (Wang et al., 2022; Ilyas et al., 2019), our attack targets the sequential decision-making process where both the victim’s policy and the attacker’s strategy evolve over time. 3 Problem Statement In a K-armed contextual bandit setting with horizon T, at each round t∈[T]t∈[T], the learner observes a context set consisting of K feature vectors with d dimensions: t=t,i∈ℝd∣i∈[K]X_t=\x_t,i ^d i∈[K]\. The agent selects an arm at∈[K]a_t∈[K] and receives a reward rt,at=h(t,at)+ξtr_t,a_t=h(x_t,a_t)+ _t, where h:ℝd→ℝh:R^d is an unknown reward function and ξt _t is zero-mean σ-sub-Gaussian noise Qi et al. (2024). The learner’s goal is to minimize cumulative pseudo-regret: RT=∑t=1T[h(t,at∗)−h(t,at)],R_T= _t=1^TE [h(x_t,a^*_t)-h(x_t,a_t) ], where at∗=argmaxi∈[K]h(t,i)a^*_t= *arg\,max_i∈[K]h(x_t,i) is the optimal arm at round t. Attack Setting. We consider a black-box attacker situated between the environment and the learner. The attacker can observe the true context t=t,ii∈[K]X_t=\x_t,i\_i∈[K] and the learner’s chosen arm ata_t, but has no access to the rewards rt,ir_t,i or the learner’s internal parameters θt _t. The attacker perturbs the context of each arm i∈[K]i∈[K] of the learner, presenting a perturbed context xt,i~=t,i+t,i x_t,i=x_t,i+ δ_t,i with ‖t,i‖∞≤ϵ\| δ_t,i\|_∞≤ε, subject to a total attack budget B≥∑t=1T∑i=1K‖t,i‖∞B≥ _t=1^T _i=1^K\| δ_t,i\|_∞, where t,i δ_t,i is the perturbation vector and ϵε is the perturbation magnitude. The learner selects arm ata_t based on the corrupted context ~t,i x_t,i, and thus, the observed reward by the learner is r^t,at=rt,at+ϵ r_t,a_t=r_t,a_t+ε, and the arm selection may be suboptimal due to reliance on ~t,i x_t,i instead of t,ix_t,i. The attacker’s goal is to hijack the learner’s behavior by forcing it to select a suboptimal arm at†∈[K]a _t∈[K] (a round-dependent target selected by the attacker), where at†≠at∗a _t≠ a^*_t. Definition 3.0 (Bandit-Powered Attack). Unlike standard MABs with a finite arm set, inspired by Wang et al. (2022); Ilyas et al. (2019), we formalize the attack as a bilevel problem over a continuous arm space =[0,1]3 =[0,1]^3. Each arm is a three-parameter vector =(λ(1),λ(2),λ(3))∈ λ=(λ^(1),λ^(2),λ^(3))∈ , where each element governs one axis of the effectiveness-evasion trade-off (the trade-off properties are analyzed in Appendix E.3): λ(1)λ^(1): attack effectiveness, weight on making the target arm at†a _t appear optimal; λ(2)λ^(2): statistical evasion, weight on keeping perturbed contexts close to the benign distribution; λ(3)λ^(3): temporal evasion, penalty on abrupt changes between consecutive perturbations. The attacker solves a bilevel optimization at each round t: t=argmin∈f(t∗(),at†), λ_t= *arg\,min_ λ∈ \;f\! ( δ_t^*( λ),\;a _t ), (1) where f is the attacker’s feedback measuring attack success (e.g., the learner selected at†a _t), and t λ_t is chosen by the bandit policy. Given the selected t λ_t, the attacker computes the perturbation for each arm i∈[K]i∈[K]: t∗(t,i;t)=argmin‖∞≤ϵℒ(t,i,;t), δ_t^*(x_t,i;\, λ_t)\;=\; _\| δ\|_∞\,≤\,ε\;L\! (x_t,i,\, δ;\, λ_t ), (2) where ℒL is the weighted attack objective defined in Eq. (18). 4 Periodical Attack Model Here, we present our bandit attack model. At each round t, the attack model observes the true context set t=t,ii∈[K]X_t=\x_t,i\_i∈[K] and evaluates whether it is sufficiently valuable to query. For this reason, we first develop a UCB-Aware MaxEnt IRL Ziebart et al. (2008) to estimate the victim’s reward from context-action pairs alone (Sec. 4.1). For an efficient attack, a feature extraction is introduced to discover attack-relevant features (Sec. 4.2). Then, a query selection strategy chooses the context to be attacked (Sec. 4.3). The model then selects t λ_t using GP-UCB (Sec. 4.4). Afterwards, the algorithm computes t,at δ_t,a_t using PGD (Sec. 4.5). Finally, the model applies the perturbation to the chosen arm’s context and receives an attack reward ρt _t measuring the regret incurred by the victim learner under the true contexts, reflecting the attacker’s progress toward hijacking the victim’s arm selection toward a†a . Algorithm 1 Adversarial Bandit Attack (AdvBandit) 1:Horizon T, attack budget B, perturbation bound ϵε, window size W, IRL retraining interval ΔIRL _IRL 2:Initialize remaining budget b←Bb← B 3:Step 1: Observe context tx_t and victim’s action ata_t in the first sliding window W0W_0 and generate t=(i,ai)i=1WD_t= \ (x_i,a_i ) \_i=1^W. 4:Step 2: Train MaxEnt IRL: reward function h^ϕr h_ φ_r and uncertainty function σϕu _ φ_u on tD_t 5:Compute gradient statistics g μ_g and g _g 6:Extract features ψ1 _1–ψ4 _4 using g μ_g and g _g 7:for t=W+1t=W+1 to T do 8: Step 3: Select context using MOO (Eq. 10) 9: Compute context weight v(xt)v(x_t) (Eq. 12) and threshold τv _v (Eq. 13) 10: if v(xt)≥τv(x_t)≥ _v and b>0b>0 then 11: Step 4: Employ GP-UCB to select t λ_t 12: Step 5: Utilize PGD(t,t) PGD(x_t, λ_t) to compute t δ_t 13: Submit perturbed context ~t←t+t x_t _t+ δ_t to victim 14: Observe victim’s action a~t a_t on ~t x_t 15: b←b−1b← b-1 16: end if 17: t=(i,ai)i=t−WtD_t= \ (x_i,a_i ) \_i=t-W^t (Step 1) 18: if tmodΔIRL=0t _IRL=0 then 19: Retrain MaxEnt IRL (t)(D_t) (Step 2) 20: Update gradient statistics g μ_g and g _g 21: end if 22:end for 23:return Attack sequence (ti,ti,ti)i=1B−b\(t_i, λ_t_i, δ_t_i)\_i=1^B-b 4.1 Surrogate Modeling Due to the unavailability of the victim’s internal parameters, a UCB-Aware MaxEnt IRL module Ziebart et al. (2008) is developed to jointly estimate the victim’s reward and epistemic uncertainty, producing a surrogate policy π^ϕ π_ φ trained on observed context-action pairs (t,at)(x_t,a_t). Since NCB algorithms are inherently non-stationary (i.e., they continuously update reward estimates and reduce epistemic uncertainty σt _t), the victim’s policy evolves over time. To track this drift, we retrain the MaxEnt IRL module every ΔIRL _IRL round using a sliding window of recent observations t=(τ,aτ)τ=t−WtD_t=\(x_τ,a_τ)\_τ=t-W^t, where W is the window size. This ensures the policy π^ϕ π_ φ reflects the victim’s behavior. Reward and Uncertainty Networks. We model the victim’s reward function and epistemic uncertainty using a neural network with a shared feature backbone and two sets of arm-specific linear heads: h^ϕr(,a) h_ φ_r(x,a) =a⊤fϕs(), =w_a f_ φ_s(x), (3) σϕu(,a) _ φ_u(x,a) =Softplus(a⊤fϕs()), =Softplus\! (v_a f_ φ_s(x) ), (4) where fϕs:ℝd→ℝdhf_ φ_s:R^d ^d_h is a shared feature backbone parameterized by ϕs φ_s with hidden dimension dhd_h, a∈ℝdhw_a ^d_h are arm-specific reward heads, and a∈ℝdhv_a ^d_h are arm-specific uncertainty heads with a Softplus activation to ensure non-negativity. UCB-Aware Surrogate Policy. The reward and uncertainty estimates are combined into a Q-value that mirrors the victim’s UCB decision rule: Q(,a)=h^ϕr(,a)+βtσϕu(,a),Q(x,a)= h_ φ_r(x,a)+ _t\, _ φ_u(x,a), (5) where βt>0 _t>0 is the exploration coefficient governing the confidence width. The surrogate policy is obtained by applying a softmax over these Q-values: π^ϕ(a∣)=exp(Q(,a)/τ)∑a′=1Kexp(Q(,a′)/τ), π_ φ(a )= \! (Q(x,a)/τ ) _a =1^K \! (Q(x,a )/τ ), (6) where τ>0τ>0 is a temperature parameter; a smaller τ makes the policy greedy toward the highest Q-value arm, while a larger τ yields a more uniform distribution over arms. Training Objective. Following the MaxEnt IRL framework, the full parameter set ϕ=(ϕs,a,a) φ=( φ_s,\w_a\,\v_a\) is trained jointly to maximize the log-likelihood of the observed context-action pairs in tD_t: J(ϕ)=1|t|∑(τ,aτ)∈tlogπ^ϕ(aτ∣τ),J( φ)= 1|D_t| _(x_τ,a_τ) _t π_ φ(a_τ _τ), (7) which encourages the surrogate to assign high probability to the victim’s observed arm selections given the corresponding contexts (see Appendix E.4 for the analysis). 4.2 Context Feature Extraction The high dimensionality of the raw context x∈ℝdx ^d (e.g., d=100d=100) degrades GP performance, and also the non-stationary relationship between the raw x and the perturbation parameters λ undermines generalization Djolonga et al. (2013); Xu et al. (2025). Therefore, we extract a compact, attack-relevant feature vector ()∈ℝ5 ψ(x) ^5 by characterizing the local geometry of the learned reward landscape h^ϕr h_ φ_r using gradient statistics computed over a recent window of observations ii=t−W+1t\x_i\_i=t-W+1^t. Specifically, we estimate the mean gradient g μ_g and covariance g _g: g=1N∑i=1N∇h^ϕr(i) μ_g= 1N _i=1^N _x h_ φ_r(x_i) (8) g=∑i=1N(∇h^(i)−g)(∇h^(i)−g)⊤N−1 _g= _i=1^N ( _x h(x_i)- μ_g ) ( _x h(x_i)- μ_g ) N-1 (9) Given a new context x, we compute five features ()∈ℝ5 ψ(x) ^5. The first four are derived from the UCB-aware MaxEnt IRL outputs and the gradient statistics: (1) ψ1: _1: Policy Entropy, the uncertainty in the victim’s action selection; (2) ψ2 _2: Predicted Weight, the trust level the defense assigns to the input; (3) ψ3 _3: Mahalanobis Distance, the distance between the current gradient and the gradient distribution (g,g)N( μ_g, _g); and (4) ψ4 _4: Regret Gap, the gap between optimal and induced action values. The fifth feature, ψ5=t/T _5=t/T, captures the relative time within the horizon. A more detailed description of these features is provided in Appendix C. 4.3 Query Selection We design a query selection to control the attack timing under a limited budget B<TB<T. This also reduces computational cost and detection risk. Intuitively, the attacker should target contexts that are simultaneously likely to succeed, high-impact, and stealthy. We formalize this via three per-context objectives: f(t)=(P(t)⏟f1:success,Δ(t)⏟f2:impact,w^(t)⏟f3:stealth)∈[0,1]3,f(x_t)= ( P(x_t)_f_1:\;success,\; (x_t)_f_2:\;impact,\; w(x_t)_f_3:\;stealth )∈[0,1]^3, (10) where P(t)P(x_t) is the attack success probability based on historical outcomes (Eq. 11), Δ(t)=ψ4(t) (x_t)= _4(x_t) is the regret gap, and w^(t)=ψ2(t) w(x_t)= _2(x_t) is the predicted defense trust level. We estimate the probability P(t)P(x_t) that a perturbation successfully flips the victim’s action using kernel-weighted historical outcomes: P(t)=∑(s,Ss)∈ℋkP(t,s)⋅Ss∑(s,⋅)∈ℋkP(t,s),P(x_t)= _(x_s,S_s) k_P(x_t,x_s)· S_s _(x_s,·) k_P(x_t,x_s), (11) where ℋH is the historical attack record, Ss∈0,1S_s∈\0,1\ indicates success, and kP(⋅,⋅)k_P(·,·) is a similarity kernel. These three objectives conflict: high-impact contexts (large Δ ) may be harder to attack stealthily (low w w). We aggregate them into a single score via a budget-adaptive scalarization: v(t)=minj∈1,2,3ωj(b,t)⋅fj(t),v(x_t)= _j∈\1,2,3\ _j(b,t)· f_j(x_t), (12) where ω1=1 _1=1, ω2=1+γ⋅bT−t _2=1+γ· bT-t, and ω3=1+η⋅(1−bT−t) _3=1+η·(1- bT-t) are adaptive weights that shift emphasis from impact (when budget is plentiful) to stealth (when budget is scarce), and b is the remaining budget. Query Selection Rule. Context tx_t is chosen for attack if its score v(t)v(x_t) exceeds a budget-adaptive threshold τv _v: τv(b,T−t)=Q1−b/(T−t)(v(s)s<t), _v(b,T-t)\;=\;Q_1-b/(T-t)\! (\v(x_s)\_s<t ), (13) where Qp(⋅)Q_p(·) denotes the p-th quantile of scores observed so far. This rule’s efficiency is analyzed theoretically in Appendix E.6 and empirically in Table 8. 4.4 Attacker arm Selection The continuous arm space =[0,1]3 =[0,1]^3 makes standard finite-armed strategies such as UCB1 Auer et al. (2002) and Thompson Sampling Thompson (1933) directly inapplicable. We therefore employ GP-UCB Srinivas et al. (2010), which models the attacker’s reward function over the continuous space with a Gaussian process prior. GP-UCB also guarantees sublinear cumulative regret in continuous domains Djolonga et al. (2013), enables sample-efficient learning of smooth reward surfaces via kernel-based generalization Iwazaki (2025a, b), and naturally supports contextual optimization Li and Laber (2025); Sandberg et al. (2025). A contextual state ts_t stores the attacker’s information at round t, comprising (i) the extracted context features of the target arm (t,at†) ψ(x_t,a _t) and the optimal arm (t,at∗) ψ(x_t,a^*_t), (i) the estimated reward gap between them under the surrogate model Δ^t _t, and (i) the running attack success rate r¯t r_t: t=[(t,at†),(t,at∗),Δ^t,r¯t]s_t= [ ψ(x_t,a _t),\; ψ(x_t,a^*_t),\; _t,\; r_t ] (14) At each attacked round t, the attacker selects t λ_t by maximizing the UCB acquisition function over : t=argmax∈[0,1]3μt−1(t,)+βtgp⋅σt−1(t,), λ_t= *arg\,max_ λ∈[0,1]^3\; _t-1(s_t, λ)+β gp_t· _t-1(s_t, λ), (15) where μt−1 _t-1 and σt−1 _t-1 are the GP posterior mean and standard deviation (Eqs. 16–17), and βtgp>0β^gp_t>0 is the exploration parameter. By balancing exploitation (arms λ with high predicted reward μ) against exploration (arms with high uncertainty σ), the attacker efficiently identifies the effectiveness–evasion trade-off that maximizes attack success. After the victim selects arm ata_t, the attacker receives a reward rtr_t that reflects the feedback f(t∗(t),at†)f( δ_t^*( λ_t),a _t) in the bilevel formulation (Eq. 1). The GP learns which trade-off parameters most reliably hijack the victim’s behavior under different contextual states. Gaussian Process Model. We model the reward function r(,)r(s, λ) as a sample from a GP with a squared-exponential (SE) kernel over the joint input =(,)z=(s, λ): k(,′)=σf2exp(−‖−′‖22ℓ2),k(z,z )= _f^2 \! (- \|z-z \|^22 ^2 ), where σf2 _f^2 is the signal variance and ℓ is the length scale. Given the observation history t−1=(i,i,ri)i=1t−1G_t-1=\(s_i, λ_i,r_i)\_i=1^t-1, the GP posterior yields the predicted reward and uncertainty: μt−1() _t-1(z) =∗⊤(+σn2)−1 =k_* (K+ _n^2I)^-1r (16) σt−12() _t-1^2(z) =k(,)−∗⊤(+σn2)−1∗ =k(z,z)-k_* (K+ _n^2I)^-1k_* (17) where ∗∈ℝt−1k_* ^t-1 is the cross-covariance vector between the query point z and the observations, ∈ℝ(t−1)×(t−1)K ^(t-1)×(t-1) is the kernel matrix over past inputs, σn2 _n^2 is the observation noise variance, and =[r1,…,rt−1]⊤r=[r_1,…,r_t-1] is the reward vector. Intuitively, a query similar to past observations yields larger entries in ∗k_*, reducing posterior variance and concentrating the prediction around the observed rewards. Since the acquisition function (Eq. 15) is non-convex over [0,1]3[0,1]^3, we adopt a two-phase multi-start strategy. First, NrandN_rand candidates are drawn uniformly from [0,1]3[0,1]^3 and ranked by their UCB values; the top C are retained. Second, projected gradient ascent is launched from each retained candidate, with iterates clipped to [0,1]3[0,1]^3, and the globally best solution is returned as t λ_t. The full procedure is given in Algorithm 2 (Appendix D). 4.5 Perturbation Generation Given the true context t,ix_t,i for each arm i∈[K]i∈[K] and the parameter t λ_t, we solve the inner problem of Definition 3 (Eq. 2) to compute the perturbation t,i∗ δ_t,i^*. We use PGD because it does not critically depend on backpropagation Kotary et al. (2023) (see Appendix F.7). Importantly, all gradient computations in this step are performed through the attacker’s surrogate model π^ϕ π_ φ, not through the victim’s model. The perturbation is obtained by solving the constrained problem in Eq. 2 with a weighted attack objective ℒL that instantiates the three axes of Definition 3: ℒ(,;)= (x, δ;\, λ)\;= λ(1)ℒeff(,) λ^(1)L_eff(x, δ) (18) +λ(2)[Rs(,)+Rn(,)] +λ^(2)\, [R_s(x, δ)+R_n(x, δ) ] +λ(3)Rt(,t−1). +λ^(3)\,R_t( δ,\, δ_t-1). We now describe each component and its role in the effectiveness–evasion trade-off. Attack loss ℒeffL_eff. This term drives the victim toward the target suboptimal arm at†a _t: ℒeff(,)=−logπ^ϕ(at†∣+)L_eff(x, δ)=- π_ φ(a _t + δ), where π^ϕ π_ φ is the attacker’s surrogate policy estimated via IRL (Eq. 6) and at†=argminah^ϕr(,a)a _t= *arg\,min_a h_ φ_r(x,a) is the arm with the lowest estimated reward. Minimizing ℒeffL_eff increases the predicted probability that the victim selects at†a _t. Gradient-norm regularizer RnR_n. This term penalizes deviations in gradient magnitude induced by the perturbation, making the attack less detectable by gradient-based anomaly monitors: ‖∇h^ϕr(+)‖2−‖∇h^ϕr()‖2. \| _x h_ φ_r(x+ δ) \|_2- \| _x h_ φ_r(x) \|_2. Since this term directly constrains a detectable side-effect of the perturbation on the surrogate reward landscape, we group it with ℒeffL_eff under λ(1)λ^(1); both require access to the same surrogate model. Statistical regularizer RsR_s. This measures how unusual the gradient at the perturbed context is by computing its Mahalanobis distance from the gradient distribution observed under normal inputs: Rs(,)=((+)−g)⊤g−1((+)−g),R_s(x, δ)= (g(x+ δ)- μ_g ) _g^-1 (g(x+ δ)- μ_g ), (19) where (⋅)=∇h^ϕr(⋅)g(·)= _x h_ φ_r(·), and g μ_g, g _g are the gradient mean and covariance estimated from clean contexts (Eqs. 8–9). Minimizing RsR_s keeps the perturbed gradient within the statistical profile, evading distribution-aware defenses. Temporal Regularizer RtR_t. Defenses might detect sudden changes in input patterns. Therefore, we penalize large differences between consecutive perturbations to ensure smooth temporal transitions: ‖−t−1‖22 \| δ- δ_t-1 \|_2^2. 5 Theoretical Guarantees We analyze AdvBandit under the following setting. The true reward function h:ℝd→[0,1]h:R^d→[0,1] is LhL_h-Lipschitz w.r.t. context, and the victim employs R-NeuralUCB with exploration bonus βtvicσtvic(,a)β vic_tσ vic_t(x,a), achieving O(T)O( T) regret without attacks. The attacker’s reward function r(,)r(s, λ) lies in the RKHS ℋkH_k with bounded norm ‖r‖ℋk≤Brkhs\|r\|_H_k≤ B_ rkhs, and observations are corrupted by σn _n-sub-Gaussian noise. Let dgp=||+||=||+3d_gp=|s|+| λ|=|s|+3 denote the GP input dimension; the squared exponential kernel yields maximum information gain γn=O((logn)dgp+1) _n=O(( n)^d_gp+1). This section states our main regret guarantees; full proofs and supporting lemmas are deferred to Appendix E. 5.1 Victim’s Cumulative Regret We first introduce the key structural quantity that governs attack success. Definition 5.0 (Attackability Margin). For an attacked round t with target arm at†a_t , the attackability margin is αt≔Δ(t,at†)−2Lhϵ _t (x_t,a_t )-2L_hε, where Δ(t,at†)=h(t,at∗)−h(t,at†) (x_t,a_t )=h(x_t,a_t^*)-h(x_t,a_t ) is the true suboptimality gap. A positive αt _t indicates the perturbation budget ϵε is sufficient to close the reward gap between the optimal and target arms. Using this, we establish that attack success is governed by the margin exceeding the combined IRL error and victim exploration bonus (Lemma E.1 in Appendix E.1). This leads to our main victim regret bound: Theorem 5.0 (Victim’s Cumulative Regret). With attack budget B, perturbation bound ϵε, and IRL retraining interval Δirl _ irl with window size W, the victim’s cumulative regret satisfies with probability at least 1−ρ1-ρ: Rv(T)≥B⋅α¯−O(B⋅dΘW) R_v(T)\;≥\;B· α\;-\;O\! ( B· d_ W ) −O(B⋅Δirl)−O(TlogT). -\;O\! ( B· _ irl )\;-\;O\! ( T T ). (20) where α¯=1B∑t:zt=1[Δ(t,at†)−2Lhϵ]+ α= 1B _t:\,z_t=1\![ (x_t,a_t )-2L_hε]^+ is the average positive attackability margin, dΘ=O(d⋅dh⋅K)d_ =O(d· d_h· K) is the number of IRL parameters, and [⋅]+=max(⋅,0)[·]^+= (·,0). Proof sketch. Decompose Rv(T)R_v(T) into attacked (zt=1z_t=1) and non-attacked (zt=0z_t=0) rounds. For attacked rounds, Lemma E.1 and Lipschitzness give rtvic≥Δ(t,a~t)−Lhϵr^vic_t≥ (x_t, a_t)-L_hε. On successful attacks (a~t=at† a_t=a_t ), this yields rtvic≥αtr^vic_t≥ _t. On failed attacks with positive margin, Lemma E.1 bounds each failure’s cost by ϵirl(t)+βtvicσtvic _ irl(t)+β vic_tσ vic_t. Summing the IRL errors via Theorem E.4 gives O(B⋅dΘ/W)O( B· d_ /W), and summing the victim exploration bonuses (σtvic=O(1/t)σ vic_t=O(1/ t)) yields O(B⋅Δirl)O( B· _ irl). Non-attacked rounds contribute at most O(TlogT)O( T T) by R-NeuralUCB’s standard guarantee. The full proof appears in Appendix E.1. ∎ The bound is expressed entirely in structural quantities—the attackability margin α¯ α, IRL model capacity (dΘ,Wd_ ,W), retraining frequency (Δirl _ irl), and victim algorithm properties—with no dependence on empirical attack success rates. Corollary E.1 (Appendix E.1) further shows that the attack is profitable whenever B>O(TlogT)/(α¯−O(dΘ/W))B>O( T T)/( α-O( d_ /W)). 5.2 Attacker’s Cumulative Regret We relax the exact realizability assumption (Assumption E.2) to accommodate model misspecification. Assumption 5.0 (Approximate Realizability). The victim’s policy is approximately realizable by the IRL model class with misspecification error: ϵmis≔infϕsuptv(πθt∗(⋅|),π^ϕ(⋅|))≥0 _mis _ φ _x tv(π^*_ _t(·|x),\, π_ φ(·|x))≥ 0. When ϵmis=0 _mis=0, this recovers exact realizability. Theorem 5.0 (Attacker’s Regret under Approximate Realizability). Let ∗()=argmaxr(,) λ^*(s)= _ λr(s, λ). Under Assumption 5.2, with probability at least 1−ρ1-ρ, the attacker’s cumulative regret over n attack rounds satisfies: Rattack(n)≤O(nγnlog(n/ρ))+O(ndΘW) R_attack(n)≤ O\! ( n _n (n/ρ) )+O\! ( n d_ W ) +O(nΔirl)+nϵmis. +O\! ( n _ irl )+n _mis. (21) where γn=O((logn)dgp+1) _n=O(( n)^d_gp+1). Under exact realizability (ϵmis=0 _mis=0), this simplifies to Rattack(n)≤O(nγnlog(n/ρ)+n)R_attack(n)≤ O( n _n (n/ρ)+ n). Proof sketch. Decompose per-round regret via the approximate state ^ti s_t_i (from surrogate h^ϕr h_ φ_r) versus the true state tis_t_i (from h) into: (a) state bias at ∗ λ^*, (b) GP-UCB selection regret on approximate states, and (c) state bias at ti λ_t_i. Terms (a) and (c) are bounded by Lipschitzness of r and the IRL error decomposition (46) (Appendix E.2). Term (b) follows standard GP-UCB analysis with the information gain bound ∑iσi−12≤2γn _i _i-1^2≤ 2 _n. Summing and applying Cauchy–Schwarz yields (5.0). The full proof is in Appendix E.2. ∎ Remark 5.0. The n⋅ϵmisn· _mis term is the only linear-in-n contribution. Universal approximation guarantees (barron1993universal) give ϵmis=O(1/dh) _mis=O(1/ d_h) for Barron-class functions. Our architecture (dh=128d_h=128) yields empirical ϵmis≈0.02 _mis≈ 0.02 (Table 5), contributing ≤4≤ 4 total regret over n=200n=200 attacks—negligible compared to the O(nγn)≈50O( n _n)≈ 50 GP-UCB term. Unlike GP-UCB on stationary functions, our setting handles non-stationarity via IRL retraining (drift term) and sliding-window gradient statistics, while γn _n remains poly-logarithmic (see Appendix E.5). (a) Analysis of AdvBandit against contextual bandits. (b) Adversarial attack models against R-NeuralUCB. Figure 1: Performance evaluation of AdvBandit under adversarial settings in terms of regret on real datasets. Figure 2: Distribution of continuous arm components (λ(1)λ^(1)(effectiveness), λ(2)λ^(2) (evasion), λ(3)λ^(3) (temporal)) across victim algorithms on the Yelp dataset. 6 Experimental Analysis In this section, we compare AdvBandit with SOTA attack models against NCBs on three real datasets (i.e., Yelp, Movielens Harper and Konstan (2015), and Disin Ahmed et al. (2018)). We used five NCB algorithms (RobustBandit Ding et al. (2022), R-NeuralUCB Qi et al. (2024), NeuralUCB Zhou et al. (2020), Neural-LinUCB Xu et al. (2022), and NeuralTS Zhang et al. (2021a)) as the victims of adversarial attacks. We also consider five attack baselines Liu and Lai (2022), Garcelon et al. (2020), Ma et al. (2018), Ilyas et al. (2019), Wang et al. (2022) and compare with our AdvBandit model. The details and settings of datasets with the configurations of both victim NCB algorithms and attack baselines are explained in Appendix B. Fig. 1 compares the effectiveness of our attack models against the other adversarial attack baselines on various NCB algorithms over 5,000 time steps. Fig. 1(a) shows the cumulative regret of NCB algorithms under AdvBandit on the datasets. From the figure, it is clear that standard methods such as NeuralUCB and NeuralLinUCB experience rapid regret growth, indicating high vulnerability to adaptive context and action perturbations generated by our model. NeuralTS consistently achieves lower regret, suggesting that stochastic action selection provides inherent resistance to targeted attacks. In contrast, explicitly robust methods, R-NeuralUCB and RobustBandit, reduce regret accumulation by mitigating corrupted observations; however, their performance varies across datasets, reflecting trade-offs between robustness and learning efficiency. Fig. 1(b) illustrates the cumulative regret incurred by R-NeuralUCB Qi et al. (2024) under various adversarial attacks. The results demonstrate that AdvBandit consistently achieves the highest cumulative regret, outperforming all baselines by inducing up to 2-3x more regret in later steps, highlighting its superior effectiveness in disrupting Gaussian process-based surrogates through targeted gradient perturbations, while the unattacked baseline exhibits sublinear regret growth as expected. Fig. 2 shows how AdvBandit reallocates its budget across effectiveness (λ(1)λ^(1)), statistical evasion (λ(2)λ^(2)), and temporal consistency (λ(3)λ^(3)) on Yelp. For the deterministic UCB-style models, NeuralUCB and NeuralLinUCB, the attack emphasizes effectiveness, with weights (0.92,0.86,0.75)(0.92,0.86,0.75) and (0.95,0.89,0.91)(0.95,0.89,0.91) and high success rates (78.8% and 76.6%), indicating that direct perturbations suffice to mislead optimism-based policies because these algorithms primarily focus on λ(1)λ^(1). In contrast, the stochastic NeuralTS shifts weight toward temporal coordination (0.93,0.87,0.97)(0.93,0.87,0.97) with a lower success rate (66.0%), as stochastic arm sampling reduces the reliability of single-shot perturbations and favors sustained influence via λ(3)λ^(3). For robustness-aware variants, R-NeuralUCB and RobustBandit focusing on λ(2)λ^(2), the allocation moves toward evasion and temporal smoothness—(0.85,0.93,0.92)(0.85,0.93,0.92) and (0.93,0.88,0.92)(0.93,0.88,0.92)—with reduced success rates (53.4% and 58.2%), reflecting suppression of abrupt or statistically deviant attacks. Overall, stronger robustness systematically shifts the attack from brute-force effectiveness to stealthy, temporally coordinated strategies. Additional results on MovieLens and Disin are provided in Appendix F. Fig. 3 compares AdvBandit against baseline attacks on R-NeuralUCB Qi et al. (2024) across varying attack budgets B∈60,350B∈\60,350\, averaged over Yelp, MovieLens, and Disin datasets. The left plot demonstrates that AdvBandit achieves target pull ratios of 0.470.47–0.550.55, representing 1.7×1.7×–2.5×2.5× improvement over the best baseline (Liu and Lai (2022), 0.210.21–0.330.33). The right plot reveals a superior cost-efficiency across all budget regimes. At B=60B=60, the efficiency (0.93×10−20.93× 10^-2) is 2.1×2.1× higher than the baselines, with slower decay at larger budgets. This demonstrates that our continuous optimization avoids wasteful perturbations characteristic of discrete attack strategies. These results validate our central hypothesis: treating attack parameter selection as a continuous bandit problem enables more effective and efficient attacks than existing discrete approaches. The AdvBandit’s exploration-exploitation trade-off successfully navigates the high-dimensional attack parameter space, avoiding both premature convergence to suboptimal strategies (unlike greedy methods such as Garcelon et al. (2020)) and wasteful random exploration (unlike Ilyas et al. (2019) and Wang et al. (2022)). In contrast, AdvBandit’s continuous arm formulation with temporal smoothing (λ(3)λ^(3)) explicitly addresses these limitations. Figure 3: Performance of different attack strategies under varying attack budgets: averaged from the real datasets (Yelp, MovieLens, and Disin). Figure 4 depicts the average runtime of AdvBandit compared with the attack baselines as the horizon T and attack budget B vary, averaged on Yelp, MovieLens, and Disin under R-NeuralUCB. The left plot shows sublinear scaling with T in which runtime increases from 58s58\,s at T=1000T=1000 to 207s207\,s at T=8000T=8000 (3.6× growth for an 8× increase in T, i.e., 45% of linear scaling). This occurs because only 74% of the computation depends on T, consisting of IRL retraining ((T⋅W)O(T· W), 34%) and context processing (40%). The remaining 26% (GP updates and overhead) depends only on B, causing deviation from the (T)O(T) reference. The right plot exhibits superlinear scaling with B, runtime growing from 59s59\,s at B=50B=50 to 389s389\,s at B=400B=400 (6.6× for an 8× increase), exceeding the (BlogB)O(B B) trend. While IRL cost remains constant (34%) and optimization scales linearly (44%), the GP kernel update (B3)O(B^3) dominates at large budgets. At the standard setting (T=5000,B=200)(T=5000,B=200) (red markers), AdvBandit achieves a victim regret of 673673 in 132s132\,s, incurring a 3.5×3.5× runtime overhead while delivering 2.8×2.8× higher attack effectiveness than baselines. More results for computational experiments are provided in Appendix G. Figure 4: Runtime scalability of attack baselines: (a) horizon T (fixed B=200B=200) and (b) attack budget B (fixed T=5000T=5000). Red stars (★ ) and vertical lines mark the standard experimental setting (T=5000T=5000, B=200B=200) used throughout the paper. 7 Conclusion This work introduced a black-box context poisoning attack against contextual bandits, formulating the problem as a continuous-armed bandit to learn an adaptive attack policy in a low-dimensional parameter space. Our approach, AdvBandit, integrates UCB-aware MaxEnt IRL for reward and uncertainty estimation, a query selection strategy to optimize attack budget allocation, GP-UCB for efficient exploration of the continuous attack parameters, and PGD for computing evasion-aware perturbations. We provided theoretical guarantees, including sublinear regret bounds for the attacker and lower bounds on the victim’s induced regret under non-stationary policies. Empirical evaluations on real-world datasets (Yelp, MovieLens, and Disin) demonstrated that AdvBandit significantly outperforms existing attack baselines in inducing victim regret while maintaining stealth against robust defenses. Notably, our method adapted dynamically to different victim algorithms, shifting emphasis from effectiveness to statistical and temporal evasion as robustness increases. Future work could explore extensions to multi-agent settings or attacks on more complex reinforcement learning environments. The formulation of attack and defense as a two-player Stackelberg game is the next step, where the defender commits first and the attacker best responds, reflecting realistic threat dynamics. References J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, et al. (2023) Gpt-4 technical report. arXiv preprint arXiv:2303.08774. Cited by: §1. H. Ahmed, I. Traore, and S. Saad (2018) Detecting opinion spams and fake news using text classification. Security and Privacy 1 (1), p. e9. Cited by: Appendix B, §6. P. Auer, N. Cesa-Bianchi, and P. Fischer (2002) Finite-time analysis of the multiarmed bandit problem. Machine learning 47 (2), p. 235–256. Cited by: §4.4. Y. Ban, J. He, and C. B. Cook (2021a) Multi-facet contextual bandits: a neural network perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, p. 35–45. Cited by: §2. Y. Ban, Y. Yan, A. Banerjee, and J. He (2021b) Ee-net: exploitation-exploration neural networks in contextual bandits. arXiv preprint arXiv:2110.03177. Cited by: Appendix B, §1, §2. H. M. Bui, E. Mallada, and A. Liu (2024) Variance-aware linear ucb with deep representation for neural contextual bandits. arXiv preprint arXiv:2411.05979. Cited by: §2. M. Dang’ana, Y. Zhang, and H. Jacobsen (2026) Ksurf-drone: attention kalman filter for contextual bandit optimization in cloud resource allocation. IEEE Transactions on Cloud Computing. Cited by: §1. R. Deb, Y. Ban, S. Zuo, J. He, and A. Banerjee (2023) Contextual bandits with online neural regression. arXiv preprint arXiv:2312.07145. Cited by: §2. Q. Di, T. Jin, Y. Wu, H. Zhao, F. Farnoud, and Q. Gu (2023) Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv preprint arXiv:2310.00968. Cited by: §2. Q. Ding, C. Hsieh, and J. Sharpnack (2022) Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statistics, p. 7111–7123. Cited by: Appendix B, §1, §2, §6. J. Djolonga, A. Krause, and V. Cevher (2013) High-dimensional gaussian process bandits. Advances in neural information processing systems 26. Cited by: §4.2, §4.4. M. Dudík, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi (2015) Contextual dueling bandits. In Conference on Learning Theory, p. 563–587. Cited by: §2. D. Fu and J. He (2021) Sdg: a simplified and dynamic graph neural network. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 2273–2277. Cited by: Appendix B. E. Garcelon, B. Roziere, L. Meunier, J. Tarbouriech, O. Teytaud, A. Lazaric, and M. Pirotta (2020) Adversarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems 33, p. 14362–14373. Cited by: Appendix B, §1, §2, §6, §6. D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. (2025) Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: §1. F. M. Harper and J. A. Konstan (2015) The movielens datasets: history and context. Acm transactions on interactive intelligent systems (tiis) 5 (4), p. 1–19. Cited by: Appendix B, §6. J. He, D. Zhou, T. Zhang, and Q. Gu (2022) Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in neural information processing systems 35, p. 34614–34625. Cited by: §1, §2. S. M. H. Hosseini, A. Najafi, and M. S. Baghshah (2025) Efficient adversarial attacks on high-dimensional offline bandits. In NeurIPS 2025 Workshop: Second Workshop on Aligning Reinforcement Learning Experimentalists and Theorists, Cited by: §1, §2. A. Ilyas, L. Engstrom, and A. Madry (2019) Prior convictions: black-box adversarial attacks with bandits and priors. In International Conference on Learning Representations, Cited by: Appendix B, item 1, §1, §2, Definition 3.0, §6, §6. S. Iwazaki (2025a) Gaussian process upper confidence bound achieves nearly-optimal regret in noise-free gaussian process bandits. arXiv preprint arXiv:2502.19006. Cited by: §4.4. S. Iwazaki (2025b) Improved regret bounds for gaussian process upper confidence bound in bayesian optimization. arXiv preprint arXiv:2506.01393. Cited by: §4.4. Y. Jia, W. Zhang, D. Zhou, Q. Gu, and H. Wang (2022) Learning neural contextual bandits through perturbed rewards. arXiv preprint arXiv:2201.09910. Cited by: §2. P. Kassraie and A. Krause (2022) Neural contextual bandits without regret. In International Conference on Artificial Intelligence and Statistics, p. 240–278. Cited by: §2. J. Kotary, M. H. Dinh, and F. Fioretto (2023) Backpropagation of unrolled solvers with folded optimization. International Joint Conference on Artificial Intelligence (IJCAI). Cited by: §4.5. V. Kuleshov and D. Precup (2014) Algorithms for multi-armed bandit problems. arXiv preprint arXiv:1402.6028. Cited by: §1. B. Kveton, C. Szepesvari, Z. Wen, and A. Ashkan (2015) Cascading bandits: learning to rank in the cascade model. In International conference on machine learning, p. 767–776. Cited by: §1. K. Li and E. Laber (2025) Exploiting concavity information in gaussian process contextual bandit optimization. arXiv preprint arXiv:2503.10836. Cited by: §4.4. G. Liu and L. Lai (2022) Action poisoning attacks on linear contextual bandits. Transactions on Machine Learning Research. Cited by: Appendix B, §1, §2, §6, §6. Y. Ma, K. Jun, L. Li, and X. Zhu (2018) Data poisoning attacks in contextual bandits. In International Conference on Decision and Game Theory for Security, p. 186–204. Cited by: Appendix B, §1, §2, §6. A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu (2017) Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083. Cited by: item 1. K. Miettinen (1999) Nonlinear multiobjective optimization. Vol. 12, Springer Science & Business Media. Cited by: item 2, §E.6.2. Y. Oh, J. Park, T. Paik, and J. Park (2025) Neural variance-aware dueling bandits with deep representation and shallow exploration. arXiv preprint arXiv:2506.01250. Cited by: §2. Y. Qi, Y. Ban, A. Banerjee, and J. He (2024) Robust neural contextual bandit against adversarial corruptions. Advances in Neural Information Processing Systems 37, p. 19378–19446. Cited by: §1, §2, §3, §6, §6, §6. J. Sandberg, N. Åkerblom, and M. H. Chehreghani (2025) Bayesian analysis of combinatorial gaussian process bandits. ICLR. Cited by: §4.4. N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger (2010) Gaussian process optimization in the bandit setting: no regret and experimental design. ICML. Cited by: §E.2, §E.3, item 1, §4.4. G. Team, R. Anil, S. Borgeaud, J. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al. (2023) Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805. Cited by: §1. W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3/4), p. 285–294. Cited by: §4.4. M. Tullii, S. Gaucher, N. Merlis, and V. Perchet (2024) Improved algorithms for contextual dynamic pricing. Advances in Neural Information Processing Systems 37, p. 126088–126117. Cited by: §1. A. Verma, Z. Dai, X. Lin, P. Jaillet, and B. K. H. Low (2024) Neural dueling bandits: preference-based optimization with human feedback. arXiv preprint arXiv:2407.17112. Cited by: §2. B. Wang, Y. Li, and P. Zhou (2022) Bandits for structure perturbation-based black-box attacks to graph neural networks with theoretical guarantees. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 13379–13387. Cited by: Appendix B, §1, §2, Definition 3.0, §6, §6. Z. Wang, X. Huo, and H. Wang (2024) Towards domain adaptive neural contextual bandits. arXiv preprint arXiv:2406.09564. Cited by: §1. P. Xu, Z. Wen, H. Zhao, and Q. Gu (2022) Neural contextual bandits with deep representation and shallow exploration. In International Conference on Learning Representations, Cited by: §2, §6. Z. Xu, H. Wang, J. M. Phillips, and S. Zhe (2025) Standard gaussian process is all you need for high-dimensional bayesian optimization. ICLR. Cited by: §4.2. Q. Zeng, E. He, R. Hoffmann, X. Wang, and J. Zuo (2025) Practical adversarial attacks on stochastic bandits via fake data injection. arXiv preprint arXiv:2505.21938. Cited by: §1, §2. W. Zhang, D. Zhou, L. Li, and Q. Gu (2021a) Neural thompson sampling. ICLR. Cited by: Appendix B, §6. Z. Zhang, J. Yang, X. Ji, and S. S. Du (2021b) Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems 34, p. 4342–4355. Cited by: §2. D. Zhou and Q. Gu (2022) Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems 35, p. 36337–36349. Cited by: §2. D. Zhou, L. Li, and Q. Gu (2020) Neural contextual bandits with ucb-based exploration. In International conference on machine learning, p. 11492–11502. Cited by: Appendix B, §2, §6. B. D. Ziebart, A. L. Maas, J. A. Bagnell, A. K. Dey, et al. (2008) Maximum entropy inverse reinforcement learning.. In Aaai, Vol. 8, p. 1433–1438. Cited by: item 1, §4.1, §4. Appendix A Notations Notation Definition Notation Definition T Time horizon (total rounds) H(π^())H( π(x)) Policy entropy K Number of arms (actions) d Dimension of context vector tx_t True context, t∈⊆ℝdx_t ^d ~t x_t Perturbed context, ~t=t+t x_t=x_t+ δ_t tA_t Set of available arms at t ata_t Arm selected by learner at t at∗a^*_t Optimal arm, argmaxah(t,a) _ah(x_t,a) at†a _t Target suboptimal arm a~t a_t Victim’s action under ~t x_t h(,a)h(x,a) True reward, h:×[K]→[0,1]h:X×[K]→[0,1] rt(at)r_t(a_t) Observed reward, h(t,at)+ξth(x_t,a_t)+ _t ξt _t Zero-mean σ-sub-Gaussian noise πθt _ _t Learner’s policy at round t LhL_h Lipschitz constant of h t δ_t Perturbation vector, t∈ℝd δ_t ^d ϵε Perturbation budget, ‖t‖∞≤ϵ\| δ_t\|_∞≤ε B Total attack budget btb_t Remaining budget, bt=B−∑s<tzsb_t=B- _s<tz_s ztz_t Attack decision, zt∈0,1z_t∈\0,1\ n Total executed attacks, n≤Bn≤ B Q1−b/(T−t)Q_1-b/(T-t) Quantile function λ Attack parameters, ∈[0,1]3 λ∈[0,1]^3 λ(1)λ^(1) Attack effectiveness weight λ(2)λ^(2) Statistical evasion weight λ(3)λ^(3) Temporal smoothness weight ∗() λ^*(s) Optimal parameter, argmaxr(,) _ λr(s, λ) R(T)R(T) Cumulative pseudo-regret RtR_t Instantaneous regret at t Rv(T)R_v(T) Victim’s cumulative regret Rattack(n)R_attack(n) Attacker’s cumulative regret Δ(t,a) (x_t,a) Regret gap, maxa′h(t,a′)−h(t,a) _a h(x_t,a )-h(x_t,a) Δ¯ Average regret gap, 1B∑t:zt=1Δ(t) 1B _t:z_t=1 (x_t) h^ϕr(,a) h_ φ_r(x,a) Estimated reward function σϕ(,a) _ φ(x,a) Estimated uncertainty function π^ϕ π_ φ Estimated victim policy πθt∗π^*_ _t True victim policy at t Q(,a)Q(x,a) Q-value, h^ϕr(,a)+βvicσϕ(,a) h_ φ_r(x,a)+β^vic _ φ(x,a) τ Temperature parameter βvicβ^vic Victim exploration bonus weight βgpβ gp Fixed GP-UCB exploration constant W Sliding window size ΔIRL _IRL IRL retraining interval tD_t Training data, (i,ai)i=t−Wt\(x_i,a_i)\_i=t-W^t ϵIRL(t) _IRL(t) IRL approximation error at t fθ()f_θ(x) Reward backbone, ℝd→ℝdhR^d ^d_h WaW_a Arm-specific reward weights gϕ()g_φ(x) Uncertainty backbone VaV_a Arm-specific uncertainty weights () ψ(x) Feature extractor, ()∈ℝ5 ψ(x) ^5 ψ1() _1(x) Policy entropy, H(π^())H( π(x)) ψ2() _2(x) Predicted defense weight ψ3() _3(x) Mahalanobis distance ψ4() _4(x) Regret gap, Δ() (x) ψ5 _5 Relative time, t/Tt/T ts_t GP-UCB contextual state (Eq. 14) dgpd_gp GP input dimension, ||+3|s|+3 g μ_g Mean gradient, 1N∑∇h^ϕr(i) 1NΣ _x h_ φ_r(x_i) g _g Gradient covariance matrix r(,)r(s, λ) Attack reward function (GP) μt(,) _t(s, λ) GP posterior mean at t σt(,) _t(s, λ) GP posterior std. deviation σt2(,)σ^2_t(s, λ) GP posterior variance k(⋅,⋅)k(·,·) Kernel function (SE/RBF) ∗k_* Cross-covariance vector K Kernel matrix, ∈ℝ(t−1)×(t−1)K ^(t-1)×(t-1) r Reward vector, [r1,…,rt−1]⊤[r_1,…,r_t-1] σf2 _f^2 Signal variance in kernel σn2σ^2_n Observation noise variance ℓ Length scale in kernel γn _n Max info gain, O((logn)dgp+1)O(( n)^d_gp+1) BRKHSB_RKHS RKHS norm bound ρ Confidence parameter, ρ∈(0,1)ρ∈(0,1) UCB(,)UCB(s, λ) Upper confidence bound NrandN_rand Random samples in multi-start v(t)v(x_t) Value/priority of context tx_t τv(b,T−t) _v(b,T-t) Query selection threshold P()P(x) Attack success probability w^() w(x) Predicted defense weight ℋH Historical attack dataset S Binary outcome, S∈0,1S∈\0,1\ ∗(;) δ^*(x; λ) Optimal perturbation ℒ(,;)L(x, δ; λ) Total attack loss ℒeff(+)L_eff(x+ δ) Attack effectiveness loss Rn(,)R_n(x, δ) Gradient norm regularizer Rs(,)R_s(x, δ) Statistical regularizer Rt(,t−1)R_t( δ, δ_t-1) Temporal regularizer IPGDI_PGD Number of PGD iterations η Step size in PGD LrL_r Lipschitz constant of r ϵfail _fail Attack failure rate w¯ w Avg defense weight, 1B∑w(~t) 1BΣ w( x_t) DτD_τ Policy drift over τ rounds TV(⋅,⋅)TV(·,·) Total variation distance cβc_β UCB-dependent constant Appendix B Datasets and Setup Datasets. (1) The Yelp dataset consists of 4.7 million rating entries for 1.57×1051.57× 10^5 restaurants by 1.18 million users. (2) MovieLens Dataset [16] consists of 25 million ratings between 1.6×1051.6× 10^5 users and 6×1046× 10^4 movies. (3) Disin [2] is a dataset on Kaggle consisting of 12,600 fake news articles and 12,600 real news articles, with each entry represented by its textual content. Data Preprocessing: For Yelp and MovieLens datasets, we follow the experimental setup conducted in [5]. A rating matrix was constructed by selecting the top 2,000 users and the top 10,000 restaurants (or movies), and singular value decomposition (SVD) was applied to obtain 10-dimensional latent feature vectors for both users and items. In Yelp and MovieLens datasets, the bandit learner aims to identify restaurants (or movies) associated with poor ratings. Context Construction. At each round t we randomly sample one user and form a candidate set of K=10K=10 items. The set consists of one item with reward 1 (rating <2<2 stars) and nine items with reward 0 (rating ≥2≥ 2 stars). The context for each arm is the concatenation of user and item latent vectors t,a∈ℝ20.x_t,a ^20. For the Disin dataset, we followed [13] to convert the text into vector representations, with each article encoded as a 300-dimensional vector. In each round, a 10-arm pool was constructed by randomly sampling 9 real news articles and 1 fake news article. Selecting the fake news article yielded a reward of 1, while selecting any real news article resulted in a reward of 0. Victim Algorithm Configuration. For NeuralUCB and NeuralTS [48, 45], we use a neural network with two hidden layers of size [100,100][100,100] and ReLU activations. Training is performed using SGD with the learning rate η=0.01η=0.01, batch size 32, and 100 gradient steps per round. The confidence scaling parameter is set to ν=1.0ν=1.0. R-NeuralUCB: the architecture matches NeuralUCB, augmented with a trust-weight mechanism. The trust threshold is τtrust=0.1 _trust=0.1. Gradient covariance is estimated using an exponential moving average with decay α=0.95α=0.95. RobustBandit [10]: We use linear UCB with FTRL-based adversarial robustness. The regularization parameter is λ=0.1λ=0.1, and the learning rate is ηFTRL=logKT _FTRL= KT. AdvBandit Hyperparameters. MaxEnt IRL Configuration: The MaxEnt IRL reward function is parameterized by a fully connected neural network with input dimension din=20d_in=20 (concatenated user and item features), two hidden layers of sizes 128128 and 6464 with ReLU activations, and a scalar output, resulting in 10,43310,433 trainable parameters. Training is performed using the Adam optimizer with a base learning rate ηIRL=0.001 _IRL=0.001 scheduled via cosine annealing over Tmax=500T_ =500 steps, batch size 6464, ℓ2 _2 gradient clipping at 1.01.0, and weight decay 10−510^-5. Each IRL update consists of 500 optimization steps (approximately eight epochs over the current data window), minimizing the negative log-likelihood of the MaxEnt policy. To balance adaptivity and sample efficiency, training data are drawn from a sliding window of size W=min(400,⌊0.08T⌋)W= (400, 0.08T ), with the reward model retrained every ΔIRL=⌊W/4⌋=100 _IRL= W/4 =100 steps as the window advances. The ablation study for the definition of W and ΔIRL _IRL is provided in Appendix F.5 (Table 7). The GP-UCB optimizer employs a Gaussian process with a squared exponential (RBF) kernel defined over the joint state–parameter space (,)(s, λ), using signal variance σf2=1.0 _f^2=1.0, observation noise σn2=0.01 _n^2=0.01, and lengthscale ℓ=0.5 =0.5 selected via five-fold cross-validation over ℓ∈0.1,0.3,0.5,0.7,1.0 ∈\0.1,0.3,0.5,0.7,1.0\. The effective dimension of the GP input space is dgp=||+3d_gp=|s|+3, yielding a maximum information gain γn=((logn)dgp+1) _n=O(( n)^d_gp+1). Action selection follows the standard GP-UCB acquisition rule UCB(t,)=μt−1(t,)+βgpσt−1(t,)UCB(s_t, λ)= _t-1(s_t, λ)+β gp\, _t-1(s_t, λ) with a fixed exploration constant βgp=2.0β gp=2.0. We also set Nrand=100N_rand=100, Nrefine=20N_refine=20, and NK=5N_K=5 in the multi-start optimization strategy (Subsection 4.4 and a detailed description in Appendix D, Algorithm 2). The number of iterations IPGDI_PGD, step size η, and ℓ∞ _∞ perturbation budget ϵε in the PGD Attack Generation algorithm were set to 100, 0.02, and 0.3, respectively. Attack Budget Selection. We set the standard attack budget to B=⌊0.04T⌋B= 0.04T correspond to a 4%4\% attack rate, which provides an effective balance between attack impact and stealthiness. This value was defined based on our experiment in Table 5 (Appendix F.3). Baseline Configurations. The attack models in [28, 40] were configured by a fixed perturbation strategy ϵ=0.3ε=0.3 at every round, corresponding to a 100%100\% attack rate and no adaptive parameter tuning. Step size α in [29] was set to 0.05. Garcelon et al. [14] used a zeroth-order optimization scheme based on finite-difference gradient estimation with Nsamples=20N_samples=20 queries per update and perturbation scale σnoise=0.1 _noise=0.1. The parameters NgradN_grad, step size η, and optimization iterations in [19] were set to 20, 0.03, and 100, respectively. Computational Environment. All experiments were conducted on a machine equipped with a 20-core Intel CPU running at 3.9GHz, 64GB of RAM, and a NVIDIA GeForce RTX5070 GPU with 12GB of memory, ensuring efficient training of neural networks. The software environment included Python3.10, PyTorch2.5.1, and NumPy2.1.3. Appendix C Feature Extraction Raw context ∈ℝdx ^d (e.g., d=20d=20 user-item features in MovieLens) is problematic for GP-UCB: (i) High dimensionality, γn=O((logn)d+1) _n=O(( n)^d+1) becomes vacuous for d=20d=20, (i) Non-stationarity, as victim policy evolves, the mapping ↦r(,)x r(x, λ) changes, violating GP stationarity, and (i) Irrelevant information, many dimensions of x (e.g., item genre in MovieLens) are irrelevant to attack success. To handle these issues, we extract low-dimensional, attack-relevant, stationary features via the feature extractor ()∈ℝ5 ψ(x) ^5 from gradients of the learned reward h^ϕr(,a) h_ φ_r(x,a). Feature ψ1 _1: Policy Entropy. This is uncertainty in the victim’s action selection: ψ1()=H(π^())=−∑a=1Kπ^(a|)logπ^(a|) _1(x)=H( π(x))=- _a=1^K π(a|x) π(a|x) (22) where the policy π^(ai|i) π(a_i|x_i) over the victim’s arms is computed using Eq. 6. High entropy means the victim is uncertain; low entropy means the victim is confident. Proposition C.0 (Entropy Predicts Attack Success). Given attack success as S()=ℙ(a~≠a∗|)S(x)=P( a≠ a^*|x) where a∗=argmaxah^ϕr(,a)a^*= _a h_ φ_r(x,a). Then: [S()|H(π^())=h1]≥[S()|H(π^())=h2]for h1>h2E[S(x)|H( π(x))=h_1] [S(x)|H( π(x))=h_2] h_1>h_2 (23) i.e., attack success increases with policy entropy. Proof. When H(π^())H( π(x)) is high, the victim’s confidence in a∗a^* is low. Small perturbations can shift probability mass from a∗a^* to suboptimal arms. Formally, for softmax policy π^(a|)∝exp(Q(,a)) π(a|x) (Q(x,a)): ∂π^(a∗|)∂Q(,a′)=−π^(a∗|)π^(a′|)for a′≠a∗ ∂ π(a^*|x)∂ Q(x,a )=- π(a^*|x) π(a |x) a ≠ a^* (24) When entropy is high, π^(a′|) π(a |x) is non-negligible, so perturbing contexts to increase Q(,a′)Q(x,a ) effectively decreases π^(a∗|) π(a^*|x). ∎ Feature ψ2 _2: Predicted Defense Weight. This feature is the estimated trust level defense assigns to this input. A low value for this feature represents a high suspicion, resulted in a reduced impact from attacks. We first compute the gradient ∇h^ϕr()∈ℝd _x h_ φ_r(x) ^d via backpropagation. Then, we compute the squared Mahalanobis norm using precomputed g−1 _g^-1 (Eq. 9). Finally, defense weight is calculated: ψ2()=w^()=11+‖∇h^ϕr()‖g−12 _2(x)= w(x)= 11+\| _x h_ φ_r(x)\|_ _g^-1^2 (25) Proposition C.0 (Weight Predicts Induced Regret). The expected victim regret from a successful attack satisfies: [Rt|success,]=Δ()⋅w(+)+O(Lhϵ)E[R_t|success,x]= (x)· w(x+ δ)+O(L_hε) (26) where w(+)≈w()=ψ2()w(x+ δ)≈ w(x)= _2(x) for small perturbations. Feature ψ3 _3: Mahalanobis Distance. This feature is the statistical distance of the gradient from “normal” gradients: ψ3()=(∇h^ϕr()−g)⊤g−1(∇h^ϕr()−g) _3(x)= ( _x h_ φ_r(x)- μ_g) _g^-1( _x h_ φ_r(x)- μ_g) (27) A high value for this feature represents that the context tx_t is already suspicious and additional perturbations will trigger detection. This feature directly models the statistical regularizer Rs(,)R_s(x, δ) in Eq. 19, enabling the GP to predict which contexts can absorb perturbations without detection. Feature ψ4 _4: Regret Gap. This feature is the gap between optimal and induced action: ψ4()=Δ()=maxah^ϕr(,a)−minah^ϕr(,a) _4(x)= (x)= _a h_ φ_r(x,a)- _a h_ φ_r(x,a) (28) A larger gap implies higher potential regret upon a successful attack, thereby prioritizing contexts where flipping the selected action yields the greatest impact. Proposition C.0 (Regret Gap Upper Bounds Induced Regret). For any perturbation δ with ‖∞≤ϵ\| δ\|_∞≤ε: Rt≤Δ()+2LhϵR_t≤ (x)+2L_hε (29) Proof. By Lipschitzness: h(+,a)∈[h(,a)−Lhϵ,h(,a)+Lhϵ]h(x+ δ,a)∈[h(x,a)-L_hε,h(x,a)+L_hε] for all a. Thus the maximum achievable regret is bounded by the range of h(,⋅)h(x,·) plus perturbation effects. ∎ Feature ψ5 _5: Relative Time t/Tt/T. Remark C.0 (Effective Dimension). The GP operates on the dgpd_gp-dimensional joint space (,)(s, λ), where t∈ℝ||s_t ^|s| is the contextual state (Eq. 14) constructed from the extracted features ()∈ℝ5 ψ(x) ^5 and attack statistics. While the original context space may be high-dimensional (∈ℝdx ^d with d=20d=20 in our experiments), the gradient-based feature extraction (Subsection 4.1) compresses attack-relevant information into the low-dimensional state ts_t, capturing policy entropy, predicted weight, Mahalanobis distance, regret gap, and relative time. This dimensionality reduction is critical: GP-UCB with raw contexts (d=20d=20) would yield γn=O((logn)24) _n=O(( n)^24), making the regret bound vacuous. With the compressed state (dgp=||+3d_gp=|s|+3), we achieve tractable γn _n, enabling efficient learning. Temporal non-stationarity: While ψ5=t/T _5=t/T introduces time-dependence, the mapping from (,)→r(s, λ)→ r remains stationary because: (i) The victim’s learning dynamics follow a predictable trajectory (uncertainty decreases as O(1/t)O(1/ t)), (i) Features ψ1 _1–ψ4 _4 already capture the victim’s state (entropy, gradient statistics), and (i) ψ5 _5 serves as a “meta-feature” that modulates the importance of other features (e.g., early attacks prioritize ψ1 _1, late attacks prioritize ψ2 _2). Proposition C.0 (Time-Augmented GP Stationarity). If the victim policy evolves according to πt=π(;θt) _t=π(x; _t) where ‖θt−θt′‖≤C|t−t′|−α\| _t- _t \|≤ C|t-t |^-α for α>0α>0 (sublinear drift), then the attack reward function r(,)r(s, λ) with ts_t defined by Eq. 14 satisfies |r(t,)−r(t′,)|≤Lr‖t−t′‖2|r(s_t, λ)-r(s_t , λ)|≤ L_r\|s_t-s_t \|_2 for Lipschitz constant LrL_r independent of t,t′t,t . Proof. The features ψ1 _1–ψ4 _4 absorb the victim’s state changes: when θt _t changes, and consequently changes in h^ϕr h_ φ_r, ψ1 _1 (entropy), ψ2 _2 (weight), ψ3 _3 (Mahalanobis), and ψ4 _4 (regret gap) are updated accordingly. The residual time effect captured by ψ5=t/T _5=t/T is deterministic and smooth. Thus the composite state ts_t evolves smoothly, preserving Lipschitzness of r. ∎ An analysis of these gradient-based features against features have been provided in Appendix F.4 (Table 6 and Fig. 6). Algorithm 2 Continuous Arm Selection via GP-UCB 1:Contextual state ts_t, round t, GP model GP, historical data t−1G_t-1 2:Number of random samples NrandN_rand, refinement candidates NrefineN_refine, gradient iterations NKN_K, learning rate η, fixed exploration constant βgpβ gp 3:Step 1: Check if sufficient historical data exists for informed decision 4:if number of past observations is below minimum threshold NminN_ then 5: return random attack parameter sampled uniformly from [0,1]3[0,1]^3 6:end if 7:Step 2: Perform global exploration via random sampling 8:// Phase 1: Global exploration 9:Initialize empty candidate set C 10:for each of NrandN_rand random candidates do 11: Sample candidate (j)∼Uniform([0,1]3) λ^(j) ([0,1]^3) 12: Compute UCB(t,(j))=μt−1(t,(j))+βgp⋅σt−1(t,(j))UCB(s_t, λ^(j))= _t-1(s_t, λ^(j))+β gp· _t-1(s_t, λ^(j)) 13: Add candidate and its UCB value to candidate set C 14:end for 15:Retain top NrefineN_refine candidates with highest UCB values 16:Step 3: Refine candidates via projected gradient ascent 17:// Phase 2: Local refinement 18:Initialize best solution from top candidate in C 19:for each candidate (0) λ^(0) in refined set C do 20: for NKN_K gradient iterations do 21: Compute gradient ∇UCB(t,(k)) _ λUCB(s_t, λ^(k)) 22: (k+1)←Π[0,1]3[(k)+η∇UCB(t,(k))] λ^(k+1)← _[0,1]^3[ λ^(k)+η _ λUCB(s_t, λ^(k))] 23: end for 24: if refined UCB exceeds current best then 25: Update best solution 26: end if 27:end for 28:return Optimal attack parameter t λ_t that maximizes UCB acquisition function Appendix D Multi-Start Optimization Strategy in GP-UCB To mitigate local optima in acquisition maximization, we employ a multi-start optimization strategy (Algorithm 2) combining randomized exploration with local refinement. Specifically, Nrand=100N_rand=100 initial candidates are generated via Latin Hypercube Sampling over the attack-parameter domain [0,1]3[0,1]^3, providing space-filling coverage of the 3D search space. The top Nrefine=20N_refine=20 candidates according to the acquisition value are then refined using L-BFGS with line search, subject to box constraints λ(i)∈[0,1]λ^(i)∈[0,1], a maximum of 50 iterations per refinement, and a convergence tolerance of 10−610^-6. Finally, the top NK=5N_K=5 optimized candidates are retained and used to initialize subsequent PGD steps, promoting solution diversity and improving robustness against poor local maxima. Since the UCB function is non-convex over the continuous domain [0,1]3[0,1]^3, we employ a multi-start optimization strategy consisting of two phases: Phase 1: Global Exploration. We first perform a global search by sampling NrandN_rand candidate points uniformly from the feasible region: (j)∼Uniform([0,1]3),j=1,…,Nrand λ^(j) ([0,1]^3), j=1,…,N_rand (30) For each candidate, we evaluate the UCB acquisition function and retain the top NrefineN_refine candidates with highest UCB values: =Top-Nrefine(j):j∈[Nrand]sorted by UCB(t,(j))C=Top-N_refine \ λ^(j):j∈[N_rand] \ by UCB(s_t, λ^(j)) (31) Phase 2: Local Gradient-Based Refinement. For each candidate (0)∈ λ^(0) , we perform projected gradient ascent to find a local maximum of the UCB function: (k+1)=Π[0,1]3[(k)+η∇UCB(t,(k))] λ^(k+1)= _[0,1]^3 [ λ^(k)+η _ λUCB(s_t, λ^(k)) ] (32) where η>0η>0 is the learning rate, Π[0,1]3[⋅] _[0,1]^3[·] denotes projection onto the feasible box, and k=0,…,NK−1k=0,…,N_K-1 indexes the gradient iterations. The gradient ∇UCB _ λUCB is computed via finite differences: ∂UCB∂λ(i)≈UCB(t,+εi)−UCB(t,)ε ∂λ^(i)≈ UCB(s_t, λ+ _i)-UCB(s_t, λ) (33) where ie_i is the i-th standard basis vector and ε>0 >0 is a small step for finite differences. After refinement, we select the globally best solution: t=argmax~∈~UCB(t,~) λ_t= *arg\,max_ λ∈ CUCB(s_t, λ) (34) where ~ C contains all refined candidates. The complete procedure is summarized in Algorithm 2. Appendix E Additional Theoretical Guarantees E.1 Victim’s Cumulative Regret: Full Analysis Lemma E.0 (Per-Round Regret Decomposition). When the attacker perturbs context tx_t, the victim’s per-round regret decomposes as: rtvic r^vic_t =h(t,at∗)−h(~t,a~t) =h(x_t,a_t^*)-h( x_t, a_t) =[h(t,at∗)−h(t,a~t)]⏟suboptimality gap Δ(t,a~t)+[h(t,a~t)−h(~t,a~t)]⏟perturbation effect = [h(x_t,a_t^*)-h(x_t, a_t)]_suboptimality gap (x_t, a_t)+ [h(x_t, a_t)-h( x_t, a_t)]_perturbation effect where at∗a_t^* is the optimal arm for the true context, a~t a_t is the victim’s action under perturbed context ~t x_t, and the perturbation effect is bounded by Lh‖t‖∞≤LhϵL_h\| δ_t\|_∞≤ L_hε by Lipschitzness of h. Lemma E.0 (Structural Attack Success Condition). Let αt=Δ(t,at†)−2Lhϵ _t= (x_t,a_t )-2L_hε be the attackability margin (Definition 5.1). The attack at round t succeeds (i.e., the victim selects at†a_t ) whenever: αt>ϵirl(t)+βtvicσtvic(~t,at†), _t\;>\; _ irl(t)+β vic_t\,σ vic_t( x_t,a_t ), (35) where ϵirl(t)=suptv(πθt∗(⋅|),π^ϕ(⋅|)) _ irl(t)= _x tv(π^*_ _t(·|x),\, π_ φ(·|x)) is the IRL approximation error and βtvicσtvicβ vic_tσ vic_t is the victim’s exploration bonus. Proof. Under the victim’s UCB rule, the victim selects at†a_t when Q(~t,at†)>Q(~t,a)Q( x_t,a_t )>Q( x_t,a) for all a≠at†a≠ a_t , where Q(,a)=h^(,a)+βtvicσtvic(,a)Q(x,a)= h(x,a)+β vic_tσ vic_t(x,a). PGD optimizes the surrogate policy to maximize π^ϕ(at†∣~t) π_ φ(a_t x_t), which succeeds when the true gap Δ(t,at†) (x_t,a_t ) exceeds three costs: 1. Perturbation cost (2Lhϵ2L_hε): Lipschitz continuity means shifting contexts of both the target and optimal arms incurs at most LhϵL_hε distortion each, for a total cost of 2Lhϵ2L_hε. 2. Surrogate error (ϵirl(t) _ irl(t)): the attack optimizes the surrogate π^ϕ π_ φ, which may disagree with the true victim policy πθt∗π^*_ _t. The TV distance ϵirl(t) _ irl(t) bounds the resulting action-selection discrepancy. 3. Victim exploration (βtvicσtvicβ vic_tσ vic_t): even under corrupted Q-values, the victim’s UCB bonus may cause it to explore at∗a_t^* if the uncertainty at at∗a_t^* is large. Combining: the attack succeeds when Δ(t,at†)−2Lhϵ>ϵirl(t)+βtvicσtvic (x_t,a_t )-2L_hε> _ irl(t)+β vic_tσ vic_t, which is (35). ∎ Theorem (5.1, restated). Under AdvBandit with attack budget B, perturbation bound ϵε, and IRL retraining interval Δirl _ irl with window size W, the victim’s cumulative regret satisfies with probability at least 1−ρ1-ρ: Rv(T)≥B⋅α¯−O(B⋅dΘW)−O(B⋅Δirl)−O(TlogT).R_v(T)\;≥\;B· α\;-\;O\! ( B· d_ W )\;-\;O\! ( B· _ irl )\;-\;O\! ( T T ). (5.0) Proof. Decompose Rv(T)=∑t:zt=1rtvic+∑t:zt=0rtvicR_v(T)= _t:\,z_t=1r^vic_t+ _t:\,z_t=0r^vic_t. Step 1: Attacked rounds. For each round with zt=1z_t=1, apply Lemma E.1 and Lipschitzness: rtvic≥Δ(t,a~t)−Lhϵ.r^vic_t\;≥\; (x_t, a_t)-L_hε. (36) Partition attacked rounds by outcome. For a successful attack (a~t=at† a_t=a_t ): rtvic≥Δ(t,at†)−Lhϵ≥αt+Lhϵ≥αt,r^vic_t\;≥\; (x_t,a_t )-L_hε\;≥\; _t+L_hε\;≥\; _t, (37) using Definition 5.1. For a failed attack (a~t≠at† a_t≠ a_t ), we use rtvic≥0r^vic_t≥ 0. Step 2: Bounding failure costs. Thus: ∑t:zt=1rtvic≥∑t:zt=1successαt=∑t:zt=1αt+−∑t:zt=1fail,αt>0αt. _t:\,z_t=1r^vic_t\;≥\; _ subarrayct:\,z_t=1\\ success subarray _t\;=\; _t:\,z_t=1 _t^+\;-\; _ subarrayct:\,z_t=1\\ fail,\; _t>0 subarray _t. (38) By Lemma E.1, every failure with αt>0 _t>0 satisfies αt≤ϵirl(t)+βtvicσtvic _t≤ _ irl(t)+β vic_tσ vic_t, so: ∑t:zt=1fail,αt>0αt≤∑t:zt=1[ϵirl(t)+βtvicσtvic]+. _ subarrayct:\,z_t=1\\ fail,\; _t>0 subarray _t\;≤\; _t:\,z_t=1\! [ _ irl(t)+β vic_tσ vic_t ]^+. (39) Recognizing ∑t:zt=1αt+=B⋅α¯ _t:\,z_t=1 _t^+=B· α yields the more general form: Rv(T)≥B⋅α¯−∑t:zt=1[ϵirl(t)+βtvicσtvic]+−O(TlogT).R_v(T)\;≥\;B· α\;-\; _t:\,z_t=1\! [ _ irl(t)+β vic_tσ vic_t ]^+\;-\;O\! ( T T ). (40) Step 3: Simplification via IRL and exploration bounds. Under periodic retraining with interval Δirl _ irl and window size W, Theorem E.4 gives: ∑t:zt=1ϵirl(t)≤O(B⋅dΘW). _t:\,z_t=1 _ irl(t)\;≤\;O\! ( B· d_ W ). (41) For R-NeuralUCB, the exploration bonus satisfies σtvic=O(1/t)σ vic_t=O(1/ t). When attacks are distributed across the horizon (as ensured by the query selection mechanism), the attack rounds ti\t_i\ span intervals of length ∼T/B T/B, so: ∑t:zt=1βtvicσtvic≤βvic∑i=1BO(1ti)≤O(B⋅Δirl), _t:\,z_t=1β vic_tσ vic_t\;≤\;β vic _i=1^BO\! ( 1 t_i )\;≤\;O\! ( B· _ irl ), (42) where the last step uses ∑i=1B1/ti≤O(B) _i=1^B1/ t_i≤ O( B) for evenly spaced attacks and the drift contribution between retrainings. Substituting into (40) yields (5.0). Step 4: Non-attacked rounds. For zt=0z_t=0, the victim operates on true contexts. The standard R-NeuralUCB guarantee gives ∑t:zt=0rtvic≤O(TlogT) _t:\,z_t=0r^vic_t≤ O( T T). Since this upper bounds what the victim loses without attack influence, it subtracts from the lower bound. ∎ Corollary E.0 (Attack Profitability Condition). AdvBandit induces victim regret exceeding the unattacked baseline whenever: B>O(TlogT)α¯−O(dΘ/W),B\;>\; O( T T) α-O\! ( d_ /W ), (43) provided α¯>O(dΘ/W) α>O( d_ /W), i.e., the average attackability margin exceeds the IRL approximation rate. This provides a structural lower bound on required attack budget expressed entirely in terms of problem parameters (Lh,ϵ,dΘ,W)(L_h,ε,d_ ,W) and the context distribution, with no dependence on empirical attack success rates. Proof. Set the right-hand side of (5.0) to exceed zero: B⋅α¯−O(B⋅dΘ/W)−O(B⋅Δirl)−O(TlogT)>0B· α-O( B· d_ /W)-O( B· _ irl)-O( T T)>0. For B large enough that B B terms are dominated by the linear term B⋅α¯B· α, the condition simplifies to B>O(TlogT)/(α¯−O(dΘ/W))B>O( T T)/( α-O( d_ /W)), provided the denominator is positive. ∎ E.2 Attacker’s Cumulative Regret: Full Analysis Theorem (5.2, restated). Under Assumption 5.2 with misspecification error ϵmis _mis, periodic IRL retraining with interval Δirl _ irl and window size W, with probability at least 1−ρ1-ρ, the attacker’s cumulative regret over n attack rounds satisfies: Rattack(n)≤O(nγnlog(n/ρ))⏟(I) GP-UCB exploration+O(n⋅dΘW)⏟(I) IRL estimation+O(n⋅Δirl)⏟(I) policy drift+n⋅ϵmis⏟(IV) misspecification.R_attack(n)\;≤\; O\! ( n _n (n/ρ) )_(I) GP-UCB exploration+ O\! ( n· d_ W )_(I) IRL estimation+ O\! ( n· _ irl )_(I) policy drift+ n· _mis_(IV) misspecification. (5.0) Proof. We decompose the per-round regret at each attack round i∈[n]i∈[n] via the approximate state ^ti s_t_i (computed from the surrogate h^ϕr h_ φ_r) versus the true state tis_t_i (computed from h): r(ti,∗)−r(ti,ti)⏟total regret=r(ti,∗)−r(^ti,∗)⏟(a) state bias at ∗+r(^ti,∗)−r(^ti,ti)⏟(b) GP selection regret+r(^ti,ti)−r(ti,ti)⏟(c) state bias at ti. r(s_t_i, λ^*)-r(s_t_i, λ_t_i)_total regret\;=\; r(s_t_i, λ^*)-r( s_t_i, λ^*)_(a) state bias at λ^*\;+\; r( s_t_i, λ^*)-r( s_t_i, λ_t_i)_(b) GP selection regret\;+\; r( s_t_i, λ_t_i)-r(s_t_i, λ_t_i)_(c) state bias at λ_t_i. (44) Terms (a) and (c): State bias from IRL approximation. By Lipschitzness of r with constant LrL_r: |r(ti,)−r(^ti,)|≤Lr‖ti−^ti‖2≤Lr⋅Cs⋅ϵirl(ti),|r(s_t_i, λ)-r( s_t_i, λ)|\;≤\;L_r\|s_t_i- s_t_i\|_2\;≤\;L_r· C_s· _ irl(t_i), (45) where CsC_s absorbs the feature extraction Lipschitz constant (Theorem E.4). Under Assumption 5.2, each ϵirl(ti) _ irl(t_i) decomposes as: ϵirl(ti)≤ϵmis⏟irreducible+O(dΘlog(K/ρ)W)⏟finite-sample estimation+cβΔirlti⏟drift since last retraining, _ irl(t_i)\;≤\; _mis_irreducible\;+\; O\! ( d_ (K/ρ)W )_finite-sample estimation\;+\; c_β _ irlt_i_drift since last retraining, (46) where the estimation term follows from Theorem E.4 and the drift term from Lemma E.5. Summing terms (a) and (c) over n rounds: ∑i=1n[|(a)|+|(c)|]≤ 2LrCs(n⋅ϵmis+O(n⋅dΘW)+O(n⋅Δirl)), _i=1^n [|(a)|+|(c)| ]\;≤\;2L_rC_s (n· _mis+O\! ( n· d_ W )+O\! ( n· _ irl ) ), (47) where we used ∑i=1n1/ti≤O(n) _i=1^n1/ t_i≤ O( n) for the drift contribution (since attack rounds ti≥it_i≥ i are monotonically increasing). Term (b): GP-UCB selection regret on approximate states. Conditioned on the approximate states ^ti\ s_t_i\, the GP-UCB acquisition ti=argmaxμi−1(^ti,)+βgpσi−1(^ti,) λ_t_i= _ λ _i-1( s_t_i, λ)+β gp _i-1( s_t_i, λ) yields standard regret. Applying Cauchy–Schwarz: ∑i=1n[r(^ti,∗)−r(^ti,ti)]≤ 2βgpn∑i=1nσi−12(^ti,ti). _i=1^n [r( s_t_i, λ^*)-r( s_t_i, λ_t_i) ]\;≤\;2β gp n _i=1^n _i-1^2( s_t_i, λ_t_i). (48) By the information gain bound ∑iσi−12≤2γn _i _i-1^2≤ 2 _n [35], with βgp=O(log(n/ρ))β gp=O( (n/ρ)): Term (b)≤O(nγnlog(n/ρ)).Term~(b)\;≤\;O\! ( n _n (n/ρ) ). (49) Combining all terms. Summing (a)+(b)+(c) and absorbing constants into O(⋅)O(·) notation yields (5.0). Under exact realizability (ϵmis=0 _mis=0) with W=Ω(dΘ)W= (d_ ) and constant Δirl _ irl, the remaining terms simplify to O(nγnlog(n/ρ)+n)O( n _n (n/ρ)+ n). ∎ Remark E.0 (Misspecification Impact). The n⋅ϵmisn· _mis term in (5.0) is the only contribution linear in n. For the overall bound to remain sublinear, ϵmis _mis must decrease as n grows. Universal approximation guarantees for two-layer ReLU networks ensure ϵmis=O(1/dh) _mis=O(1/ d_h) for Barron-class reward functions, where dhd_h is the hidden dimension. Our architecture (dh=128d_h=128) yields empirical ϵmis≈0.02 _mis≈ 0.02 (measured via held-out KL divergence, Table 5), contributing ≤4≤ 4 total regret over n=200n=200 attacks—negligible compared to the O(nγn)≈50O( n _n)≈ 50 GP-UCB term. This bridges the gap between the theoretical bound and experimental observation that IRL accurately tracks the victim’s policy. Remark E.0 (Non-Stationarity). Unlike GP-UCB applied to stationary functions, our setting introduces two sources of non-stationarity: (i) victim policy evolution, handled via periodic IRL retraining (Appendix E.5), contributing the O(n⋅Δirl)O( n· _ irl) drift term, and (i) state drift in ts_t, controlled by gradient statistics computed over sliding windows. The maximum information gain γn=O((logn)dgp+1) _n=O(( n)^d_gp+1) remains poly-logarithmic despite this non-stationarity, since the feature extraction (Section 4.2) absorbs victim state changes into the stationary mapping (,)↦r(s, λ) r (Proposition C). Remark E.0 (Attack Rounds vs. Budget). While the attack budget limits n≤Bn≤ B, the actual number of attacks n may be smaller due to: (i) contexts with low value v(t)<τv(b,T−t)v(x_t)< _v(b,T-t) being skipped, and (i) early termination if the remaining budget becomes unprofitable. When the query selection (Section 4.3) filters out contexts with αt≤0 _t≤ 0 (negative attackability margin), the effective misspecification cost in (5.0) is further reduced, since only positively-margined contexts are attacked. E.3 Attack Parameter Space [0,1]3[0,1]^3 Theorem E.0 (3D Pareto Frontier Sufficiency). Consider the multi-objective attack optimization problem: min∈()=(f1()f2()f3())=(ℒeff(+)Rs(,)Rt(,t−1)) _ δ F( δ)= pmatrixf_1( δ)\\ f_2( δ)\\ f_3( δ) pmatrix= pmatrixL_eff(x+ δ)\\ R_s(x, δ)\\ R_t( δ, δ_t-1) pmatrix (50) where =:‖∞≤ϵD=\ δ:\| δ\|_∞≤ε\ is the feasible perturbation set. Then, the Pareto frontier =∗∈:∄′∈ with (′)≺(∗)P=\ δ^* : δ with F( δ ) ( δ^*)\ can be fully parameterized by ∈[0,1]3 λ∈[0,1]^3 via: ∗()=argmin∈⟨,()⟩=argmin∈∑i=13λ(i)fi() δ^*( λ)= _ δ λ,F( δ) = _ δ _i=1^3λ^(i)f_i( δ) (51) Furthermore, the GP-UCB sample complexity for learning optimal λ scales as O(γn)O( _n) where γn=O((logn)dgp+1) _n=O(( n)^d_gp+1). For a fixed budget n, reducing ||| λ| from 5 to 3 improves sample efficiency by a factor of O((logn)2)≈28×O(( n)^2)≈ 28× for n=200n=200. Proof. For convex objectives f1,f2,f3f_1,f_2,f_3 (our ℒeff,Rs,RtL_eff,R_s,R_t are all convex in δ by construction), every Pareto-optimal solution corresponds to minimizing a weighted sum ∑i=13λ(i)fi _i=1^3λ^(i)f_i for some ≥ λ 0. Since the objective space is 3-dimensional (:→ℝ3F:D ^3), we need exactly 3 weights to span all trade-off directions. Any convex combination of 3 objectives can be represented by a simplex in 3D weight space. Suppose we have ~=(λ(1),…,λ(d))∈ℝ+d λ=(λ^(1),…,λ^(d)) ^d_+ with d>3d>3. The equivalent 3D parameterization is defined as: λ(i)′=λ(i)∑j=13λ(j)for i∈1,2,3λ^(i) = λ^(i) _j=1^3λ^(j) i∈\1,2,3\ (52) argmin∑i=1dλ~(i)fi() _ δ _i=1^d λ^(i)f_i( δ) =argmin(∑i=13λ(i)fi()+∑i=4dλ(i)⋅0) = _ δ ( _i=1^3λ^(i)f_i( δ)+ _i=4^dλ^(i)· 0 ) =argmin∑i=13λ(i)fi() = _ δ _i=1^3λ^(i)f_i( δ) =argmin∑i=13λ(i)′fi() = _ δ _i=1^3λ^(i) f_i( δ) where we set λ(4),…,λ(d)λ^(4),…,λ^(d) to weight non-existent objectives (or linear combinations of existing ones), making them redundant. Based on the nature of GP-UCB theory [35], sample complexity dramatically increases with ||| λ|. Given the cumulative regret bound in GP-UCB Rattack(B)≤O(Bγnlog(B/ρ))R_attack(B)≤ O ( B _n (B/ρ) ), the total dimensions for squared-exponential kernels in d dimensions with dgp=||+||=||+d_gp=|s|+| λ|=|s|+d is γn=O((logn)dgp+1)=O((logB)||+d+1) _n=O (( n)^d_gp+1 )=O (( B)^|s|+d+1 ). For B=200B=200: • 3D: γ200≈(log200)||+4 _200≈( 200)^|s|+4 • 5D: γ200≈(log200)||+6 _200≈( 200)^|s|+6 • Ratio: (log200)2≈28×( 200)^2≈ 28× Therefore, 5D requires 28×28× more samples than 3D to achieve the same accuracy. The experimental validation of these theoretical analyses is provided in Table 4 (Subsection F.2). ∎ E.4 IRL Sample Complexity and Approximation Error Our attack critically depends on accurately estimating the victim’s reward function h^ϕr h_ φ_r and uncertainty σ^ϕ σ_ φ via MaxEnt IRL. Here we bound the sample complexity and approximation error. Assumption E.0 (Realizability). The victim’s policy lies in the hypothesis class of our IRL model, i.e., there exist parameters ϕr∗,ϕ∗ φ_r^*, φ^* such that π∗(⋅|)=exp(Qϕr∗,ϕ∗(,⋅)/τ)/Z()π^*(·|x)= (Q_ φ_r^*, φ^*(x,·)/τ)/Z(x) for all ∈x . Theorem E.0 (IRL Sample Complexity). Under Assumption E.4, with window size W≥Ω(dΘlog(K/ρ))W≥ (d_ (K/ρ)), where dΘ=O(d⋅dh⋅K)d_ =O(d· d_h· K) is the total number of IRL parameters, the estimated policy satisfies: (,a)∼t[KL(πθt∗(⋅|)∥π^ϕ(⋅|))]≤ϵIRL2=O(dΘlog(K/ρ)W)E_(x,a) _t [KL( _ _t^*(·|x)\| π_ φ(·|x)) ]≤ _IRL^2=O ( d_ (K/ρ)W ) (53) with probability at least 1−ρ1-ρ, where tD_t is the empirical distribution in the sliding window. Proof. MaxEnt IRL minimizes negative log-likelihood: ℒ(ϕr,ϕ)=−∑ilogπ^ϕ(ai|i)L( φ_r, φ)=- _i π_ φ(a_i|x_i). Standard statistical learning theory (generalization bounds for maximum likelihood) shows that with W i.i.d. samples, the excess risk satisfies: ℒ(ϕ^r,ϕ^)−ℒ(ϕr∗,ϕ∗)≤O(dΘlog(K/ρ)W)L( φ_r, φ)-L( φ_r^*, φ^*)≤ O ( d_ (K/ρ)W ) (54) By Pinsker’s inequality, KL divergence is bounded by twice the excess ℓ1 _1 risk, which itself is bounded by the likelihood gap. ∎ Theorem E.0 (Feature Extraction Error). The gradient-based features () ψ(x) computed from approximate reward h^ϕr h_ φ_r satisfy: ‖(;h^ϕr,^g,^g)−(;h∗,g∗,g∗)‖2≤O(LhϵIRL+Lh2ϵIRLW)\| ψ(x; h_ φ_r, μ_g, _g)- ψ(x;h^*, μ_g^*, _g^*)\|_2≤ O (L_h _IRL+ L_h^2 _IRL W ) (55) where the first term comes from reward approximation error and the second from gradient statistic estimation error. Theorem E.0 (Cumulative IRL Error). Over n attack rounds with periodic retraining every ΔIRL _IRL steps, the cumulative IRL approximation error satisfies: ∑i=1nϵIRL(ti)≤O(n⋅dΘW+n⋅ΔIRLt) _i=1^n _IRL(t_i)≤ O ( n· d_ W+n· _IRL t ) (56) Proof. Partition attack rounds into retraining epochs. Within each epoch of length ΔIRL _IRL, the IRL error remains O(dΘ/W)O( d_ /W) from Theorem E.4. Across ⌈n/ΔIRL⌉ n/ _IRL epochs, this contributes O(n⋅dΘ/W)O( n· d_ /W). Additionally, policy drift between retrainings contributes O(ΔIRL/t)O( _IRL/ t) per round (see §E.5), accumulating to O(n⋅ΔIRL/t)O(n· _IRL/ t). ∎ E.5 Non-Stationarity Analysis The victim’s policy πθt _ _t evolves over time, creating non-stationarity in the attack objective. We now provide a unified drift analysis covering all five victim algorithms evaluated in our experiments. We first establish a general framework, then derive algorithm-specific bounds. Definition E.0 (Policy Drift). The policy drift over τ rounds is: Dτ=maxt∈[T−τ]sup∈TV(πθt(⋅|),πθt+τ(⋅|)),D_τ= _t∈[T-τ] _x TV( _ _t(·|x),\; _ _t+τ(·|x)), (57) where TV denotes total variation distance. Lemma E.0 (Unified Policy Drift Bound). For any victim algorithm whose action-selection scores St(,a)S_t(x,a) satisfy |St(,a)−St+τ(,a)|≤δscore(t,τ)|S_t(x,a)-S_t+τ(x,a)|≤ _score(t,τ) uniformly over (,a)(x,a), the policy drift satisfies: Dτ≤calg⋅δscore(t,τ),D_τ\;≤\;c_alg· _score(t,τ), (58) where calgc_alg depends on the policy parameterization: • Softmax policies (NeuralUCB, NeuralLinUCB, R-NeuralUCB): calg=K−1c_alg=K-1, since the softmax mapping π(a|)=exp(S(,a))/∑a′exp(S(,a′))π(a|x)= (S(x,a))/ _a (S(x,a )) is (K−1)(K-1)-Lipschitz in ℓ∞ _∞ score perturbations w.r.t. TV distance. • Argmax policies (RobustBandit): calgc_alg depends on the score gap (see Lemma E.5). • Stochastic sampling policies (NeuralTS): the score is itself random, requiring a different treatment (see Lemma E.5). Proof. For softmax policies, the TV distance between πt _t and πt+τ _t+τ satisfies: TV(πt(⋅|),πt+τ(⋅|))=12∑a=1K|πt(a|)−πt+τ(a|)|.TV( _t(·|x), _t+τ(·|x))= 12 _a=1^K| _t(a|x)- _t+τ(a|x)|. (59) For a softmax policy π(a|)∝exp(S(,a)/τtemp)π(a|x) (S(x,a)/ _temp), the sensitivity of each action probability to score perturbations is: |∂π(a|)∂S(,a′)|=1τtemp⋅π(a|)(1−π(a|))if a=a′,π(a|)π(a′|)if a≠a′. | ∂π(a|x)∂ S(x,a ) |= 1 _temp· casesπ(a|x)(1-π(a|x))&if a=a ,\\ π(a|x)π(a |x)&if a≠ a . cases (60) By a first-order Taylor expansion and summing over K arms: TV(πt,πt+τ)≤K−12τtemp⋅maxa|St(,a)−St+τ(,a)|=K−12τtemp⋅δscore(t,τ).TV( _t, _t+τ)≤ K-12 _temp· _a|S_t(x,a)-S_t+τ(x,a)|= K-12 _temp· _score(t,τ). (61) Setting calg=(K−1)/(2τtemp)c_alg=(K-1)/(2 _temp) (with τtemp=1 _temp=1 absorbed into the score definition for UCB-based algorithms) yields (58). ∎ Lemma E.0 (R-NeuralUCB Policy Drift). For R-NeuralUCB with exploration bonus βtvicσtvic(,a)β^vic_tσ^vic_t(x,a) where σtvic(,a)=O(1/t)σ^vic_t(x,a)=O(1/ t), the policy drift satisfies Dτ≤cβτtD_τ≤ c_β τt for constant cβ=O(βvic⋅K⋅Lh)c_β=O(β^vic· K· L_h) depending on the victim’s UCB exploration parameter. Proof. The R-NeuralUCB policy is πt(a|)∝exp(Qt(,a)) _t(a|x) (Q_t(x,a)) where Qt(,a)=ht(,a)+βtvicσtvic(,a)Q_t(x,a)=h_t(x,a)+β^vic_tσ^vic_t(x,a). Between rounds t and t+τt+τ: |πt(a|)−πt+τ(a|)|≤K⋅|Qt(,a)−Qt+τ(,a)|exp(−K⋅‖Q‖∞)| _t(a|x)- _t+τ(a|x)|≤ K·|Q_t(x,a)-Q_t+τ(x,a)| (-K·\|Q\|_∞) (62) Since hth_t converges to h∗h^* at rate O(1/t)O(1/ t) (from R-NeuralUCB regret bound) and σtvic=O(1/t)σ^vic_t=O(1/ t): |Qt(,a)−Qt+τ(,a)|≤O(1t−1t+τ)+βvic⋅O(1t−1t+τ)|Q_t(x,a)-Q_t+τ(x,a)|≤ O ( 1 t- 1 t+τ )+β^vic· O ( 1 t- 1 t+τ ) (63) Using Taylor expansion 1t−1t+τ=O(τ/t3/2) 1 t- 1 t+τ=O(τ/t^3/2) and summing over arms yields TV distance O(τ/t)O( τ/t). ∎ Lemma E.0 (R-NeuralUCB Policy Drift). For R-NeuralUCB with score St(,a)=h^t(,a)+βtvicσtvic(,a)S_t(x,a)= h_t(x,a)+β^vic_tσ^vic_t(x,a), where h^t h_t converges to h∗h^* at rate O(1/t)O(1/ t) and σtvic(,a)=O(1/t)σ^vic_t(x,a)=O(1/ t), the policy drift satisfies: Dτ≤cβrnτt,cβrn=O((1+βvic)⋅K).D_τ\;≤\;c rn_β τt, c rn_β=O\! ((1+β^vic)· K ). (64) Proof. The score difference decomposes as: |St(,a)−St+τ(,a)| |S_t(x,a)-S_t+τ(x,a)| ≤|h^t(,a)−h^t+τ(,a)|⏟reward estimate drift+βvic|σtvic(,a)−σt+τvic(,a)|⏟confidence width drift. ≤ | h_t(x,a)- h_t+τ(x,a)|_reward estimate drift+β^vic |σ^vic_t(x,a)-σ^vic_t+τ(x,a)|_confidence width drift. (65) Reward estimate drift. By the R-NeuralUCB regret bound, the reward estimate satisfies |h^t(,a)−h∗(,a)|=O(1/t)| h_t(x,a)-h^*(x,a)|=O(1/ t) uniformly. Thus: |h^t−h^t+τ|≤|h^t−h∗|+|h∗−h^t+τ|=O(1/t)+O(1/t+τ)=O(1/t),| h_t- h_t+τ|≤| h_t-h^*|+|h^*- h_t+τ|=O(1/ t)+O(1/ t+τ)=O(1/ t), (66) where the last step uses t+τ≥t+τ≥ t. More precisely, by the mean value theorem applied to g(s)=1/sg(s)=1/ s: 1t−1t+τ=τ2⋅ξ−3/2≤τ2t3/2 1 t- 1 t+τ= τ2·ξ^-3/2≤ τ2t^3/2 (67) for some ξ∈[t,t+τ]ξ∈[t,t+τ], yielding |h^t−h^t+τ|=O(τ/t3/2)| h_t- h_t+τ|=O(τ/t^3/2). Confidence width drift. Similarly, σtvic=O(1/t)σ^vic_t=O(1/ t) gives: |σtvic−σt+τvic|=O(τ/t3/2).|σ^vic_t-σ^vic_t+τ|=O(τ/t^3/2). (68) Combining. Substituting into (65): δscore(t,τ)=O((1+βvic)⋅τ/t3/2) _score(t,τ)=O((1+β^vic)·τ/t^3/2). By Lemma E.5: Dτ≤(K−1)⋅O((1+βvic)⋅τt3/2)=O((1+βvic)K⋅τt3/2).D_τ≤(K-1)· O\! ((1+β^vic)· τt^3/2 )=O\! ((1+β^vic)K· τt^3/2 ). (69) Since τ/t3/2≤τ/t⋅(1/t)≤τ/tτ/t^3/2≤ τ/t·(1/ t)≤ τ/t for t≥1t≥ 1, we obtain Dτ≤cβrnτ/tD_τ≤ c rn_β τ/t with cβrn=O((1+βvic)K)c rn_β=O((1+β^vic)K). ∎ Lemma E.0 (NeuralUCB Policy Drift). For NeuralUCB with score St(,a)=h^t(,a)+ν~t(,a)⊤t−1~t(,a)S_t(x,a)= h_t(x,a)+ν g_t(x,a) Z_t^-1 g_t(x,a), where ~t=∇θfθ(,a)/m g_t= _θf_θ(x,a)/ m is the normalized gradient and t=+∑s=1t~s~s⊤Z_t=I+ _s=1^t g_s g_s is the Gram matrix, the policy drift satisfies: Dτ≤cβnuτt,cβnu=O(ν⋅K).D_τ\;≤\;c nu_β τt, c nu_β=O(ν· K). (70) Proof. The analysis parallels Lemma E.5, but without the trust-weight mechanism. The key difference is in the confidence width: σtnu(,a)=~t⊤t−1~tσ nu_t(x,a)= g_t Z_t^-1 g_t. Since tZ_t accumulates gradients monotonically (t+τ⪰tZ_t+τ _t), we have σt+τnu≤σtnuσ nu_t+τ≤σ nu_t. Standard NTK-based analysis shows σtnu=O(1/t)σ nu_t=O(1/ t), yielding the same O(τ/t3/2)O(τ/t^3/2) score drift as R-NeuralUCB. Without the trust-weight filtering, NeuralUCB does not down-weight suspicious observations, so the reward estimate h^t h_t converges at the same O(1/t)O(1/ t) rate but with potentially larger constants under adversarial corruption. The drift bound follows from Lemma E.5 with cβnu=O(νK)c nu_β=O(ν K). ∎ Lemma E.0 (NeuralLinUCB Policy Drift). For NeuralLinUCB, which restricts exploration to the last network layer with score St(,a)=t⊤ϕt(,a)+αtϕt(,a)⊤t−1ϕt(,a)S_t(x,a)=w_t _t(x,a)+ _t _t(x,a) A_t^-1 _t(x,a), where ϕt(,a)=fθt(,a) _t(x,a)=f_ _t(x,a) is the last-layer representation and t=+∑s=1tϕsϕs⊤A_t=I+ _s=1^t _s _s , the policy drift satisfies: Dτ≤cβnl⋅τt,cβnl=O(α⋅K⋅Lϕ),D_τ\;≤\;c nl_β· τt, c nl_β=O(α· K· L_φ), (71) where LϕL_φ is the Lipschitz constant of the feature map ϕt _t w.r.t. parameter updates. Proof. NeuralLinUCB freezes the feature backbone periodically and only updates the last-layer weights tw_t and covariance tA_t. This creates faster drift than full-network methods because: (i) the last-layer weights tw_t update via closed-form ridge regression at each round, so ‖t−t+τ‖=O(τ/t)\|w_t-w_t+τ\|=O(τ/t) (each new observation shifts the ridge solution by O(1/t)O(1/t)); and (i) the confidence width decays as σtnl=O(1/t)σ nl_t=O(1/ t) but the feature map ϕt _t changes at backbone retraining points, introducing discrete jumps. Between backbone retrainings (where ϕt _t is fixed), the score drift is: |St−St+τ|≤‖ϕ‖⋅‖t−t+τ‖+α⋅|σtnl−σt+τnl|=O(τ/t)+O(τ/t3/2)=O(τ/t).|S_t-S_t+τ|≤\|φ\|·\|w_t-w_t+τ\|+α·|σ nl_t-σ nl_t+τ|=O(τ/t)+O(τ/t^3/2)=O(τ/t). (72) The O(τ/t)O(τ/t) term dominates (versus O(τ/t3/2)O(τ/t^3/2) for full-network methods), yielding faster drift. At backbone retraining points (occurring every TretrainT_retrain rounds), an additional O(Lϕ⋅‖θt−θt+τ‖)O(L_φ·\| _t- _t+τ\|) jump occurs. Between consecutive retrainings, applying Lemma E.5: Dτ≤cβnl⋅τ/tD_τ≤ c nl_β·τ/t. ∎ Lemma E.0 (NeuralTS Policy Drift). For NeuralTS with action selection at=argmaxar~t(,a)a_t= _a r_t(x,a) where r~t(,a)=h^t(,a)+ν⋅σtvic(,a)⋅ξt r_t(x,a)= h_t(x,a)+ν·σ^vic_t(x,a)· _t and ξt∼(0,1) _t (0,1) is a fresh sample each round, the expected policy drift satisfies: [Dτ]≤cβtsτt⋅K⋅σpost,cβts=O(ν⋅K),E[D_τ]\;≤\;c ts_β τt· K· _post, c ts_β=O(ν· K), (73) where σpost=maxaσtvic(,a) _post= _aσ^vic_t(x,a) is the maximum posterior standard deviation. Proof. The NeuralTS policy at round t is the marginal distribution over actions induced by the posterior sampling procedure: πt(a|)=Pr[a=argmaxa′r~t(,a′)]=Pr[a=argmaxa′(h^t(,a′)+νσtvic(,a′)ξt,a′)], _t(a|x)= \! [a= _a r_t(x,a ) ]= \! [a= _a ( h_t(x,a )+νσ^vic_t(x,a ) _t,a ) ], (74) where ξt,a′∼i.i.d.(0,1) _t,a .i.d. N(0,1). This is fundamentally different from the deterministic softmax policies of UCB-based algorithms: even at fixed parameters (h^t,σtvic)( h_t,σ^vic_t), the action distribution is stochastic due to posterior sampling. Score drift decomposition. The “effective score” for NeuralTS is the perturbed reward r~t(,a)=h^t(,a)+νσtvic(,a)ξt r_t(x,a)= h_t(x,a)+νσ^vic_t(x,a) _t. Unlike UCB, the noise ξt _t is resampled independently at each round. The drift in the marginal action distribution πt(a|) _t(a|x) arises from changes in the mean h^t h_t and the sampling width σtvicσ^vic_t. Specifically: TV(πt(⋅|),πt+τ(⋅|))≤∑a=1K|πt(a|)−πt+τ(a|)|.TV( _t(·|x), _t+τ(·|x))≤ _a=1^K| _t(a|x)- _t+τ(a|x)|. (75) Each πt(a|) _t(a|x) is the probability that arm a has the highest perturbed reward. This probability depends on the gaps h^t(,a)−h^t(,a′) h_t(x,a)- h_t(x,a ) relative to the noise scale νσtvicνσ^vic_t. Gaussian comparison. Let t=(h^t(,a))a∈[K]m_t=( h_t(x,a))_a∈[K] and t=diag((νσtvic(,a))2)a∈[K] _t=diag((νσ^vic_t(x,a))^2)_a∈[K]. The policy πt(a|)=Pr[argmaxaZa=a] _t(a|x)= [ _aZ_a=a] where Z∼(t,t)Z (m_t, _t). By Gaussian comparison inequalities (e.g., Theorem 1 of devroye2018total), the TV distance between the argmax distributions under two Gaussians (t,t)N(m_t, _t) and (t+τ,t+τ)N(m_t+τ, _t+τ) is bounded by: TV(πt,πt+τ)≤CK⋅(‖t−t+τ‖∞σmin+‖t1/2−t+τ1/2‖Fσmin),TV( _t, _t+τ)≤ C_K· ( \|m_t-m_t+τ\|_∞ _ + \| _t^1/2- _t+τ^1/2\|_F _ ), (76) where σmin=minaνσtvic(,a) _ = _aνσ^vic_t(x,a) and CK=O(K)C_K=O(K) accounts for the K-way argmax . Bounding each term. For the mean shift: ‖t−t+τ‖∞=maxa|h^t(,a)−h^t+τ(,a)|=O(τ/t3/2)\|m_t-m_t+τ\|_∞= _a| h_t(x,a)- h_t+τ(x,a)|=O(τ/t^3/2) as in Lemma E.5. For the covariance shift: since σtvic=O(1/t)σ^vic_t=O(1/ t), each diagonal entry satisfies |νσtvic−νσt+τvic|=O(τ/t3/2)|νσ^vic_t-νσ^vic_t+τ|=O(τ/t^3/2), so ‖t1/2−t+τ1/2‖F=O(K⋅τ/t3/2)\| _t^1/2- _t+τ^1/2\|_F=O( K·τ/t^3/2). Key distinction: noise floor. For NeuralTS, σmin=Θ(1/t) _ = (1/ t), so the ratios in (76) become: O(τ/t3/2)O(1/t)=O(τ/t)andO(Kτ/t3/2)O(1/t)=O(Kτ/t). O(τ/t^3/2)O(1/ t)=O(τ/t) O( Kτ/t^3/2)O(1/ t)=O( Kτ/t). (77) Thus: TV(πt,πt+τ)≤O(K3/2⋅τ/t)TV( _t, _t+τ)≤ O(K^3/2·τ/t). However, this bound is tighter than it appears: the effective drift is modulated by σpost _post because when the posterior is wide (high σpost _post), the sampling distribution is diffuse and small mean shifts have less effect on the argmax distribution. More precisely, the marginal selection probability for the optimal arm satisfies πt(a∗|)≤1−(K−1)Φ(−Δmin/(νσpost)) _t(a^*|x)≤ 1-(K-1) (- _ /(ν _post)), where Δmin _ is the minimum reward gap. This means the policy is already stochastic (not concentrating on a∗a^*), making it inherently less sensitive to parameter drift but simultaneously harder to attack (consistent with the lower attack success rates in Fig. 2 for NeuralTS). Taking expectations over the posterior sampling and using τ/t≤τ/tτ/t≤ τ/t for τ≤tτ≤ t: [Dτ]≤cβtsτt⋅K⋅σpost,E[D_τ]≤ c ts_β τt· K· _post, (78) where cβts=O(νK)c ts_β=O(ν K) and the additional K⋅σpostK· _post factor captures the posterior-width modulation. ∎ Lemma E.0 (RobustBandit Policy Drift). For RobustBandit with FTRL-based policy πt(a|)∝exp(ηftrl∑s=1tr^s(,a)) _t(a|x) ( _ ftrl _s=1^t r_s(x,a)) with learning rate ηftrl=logK/T _ ftrl= K/T, the policy drift satisfies: Dτ≤cβrb⋅τT,cβrb=O(K⋅ηftrl)=O(KlogKT).D_τ\;≤\;c rb_β· τ T, c rb_β=O(K· _ ftrl)=O\! (K KT ). (79) Proof. RobustBandit uses a fundamentally different update mechanism: FTRL accumulates reward estimates and regularizes with negative entropy −∑aπ(a)logπ(a)- _aπ(a) π(a). The score at round t is the cumulative reward St(,a)=ηftrl∑s=1tr^s(,a)S_t(x,a)= _ ftrl _s=1^t r_s(x,a). Score drift. Between rounds t and t+τt+τ: |St(,a)−St+τ(,a)|=ηftrl|∑s=t+1t+τr^s(,a)|≤ηftrl⋅τ,|S_t(x,a)-S_t+τ(x,a)|= _ ftrl | _s=t+1^t+τ r_s(x,a) |≤ _ ftrl·τ, (80) since |r^s|≤1| r_s|≤ 1. Policy sensitivity. For the FTRL exponential weights policy, the TV sensitivity to score changes is bounded by: TV(πt,πt+τ)≤(K−1)⋅|St−St+τ|≤(K−1)⋅ηftrl⋅τ.TV( _t, _t+τ)≤(K-1)·|S_t-S_t+τ|≤(K-1)· _ ftrl·τ. (81) Substituting ηftrl=logK/T _ ftrl= K/T: Dτ≤(K−1)logKT⋅τ=O(KlogKT⋅τ).D_τ≤(K-1) KT·τ=O\! (K KT·τ ). (82) This drift is linear in τ (not τ τ) because FTRL accumulates at a constant rate, unlike UCB methods where the learning rate effectively decreases as 1/t1/ t. However, the small prefactor logK/T K/T ensures the drift remains moderate: for our setting (K=10K=10, T=5000T=5000), the per-round drift is ≈0.02≈ 0.02 per arm, yielding D100≈0.18D_100≈ 0.18 — comparable to the UCB-based algorithms. ∎ Table 1: Summary of victim-specific policy drift bounds. All bounds are stated for τ rounds of drift starting from round t. The “Effective IRL interval” column gives the maximum Δirl _ irl such that the tracking error (Theorem E.5) remains O(1/T1/4)O(1/T^1/4). Victim Algorithm Drift Bound DτD_τ calgc_alg Drift Type Eff. IRL Interval NeuralUCB cβnuτ/tc nu_β τ/t O(νK)O(ν K) Sublinear Δirl=O(T) _ irl=O( T) NeuralLinUCB cβnl⋅τ/tc nl_β·τ/t O(αKLϕ)O(α KL_φ) Faster Δirl=O(T1/3) _ irl=O(T^1/3) NeuralTS cβtsτ/t⋅Kσpostc ts_β τ/t· K _post O(νK2σpost)O(ν K^2 _post) Sublinear Δirl=O(T) _ irl=O( T) R-NeuralUCB cβrnτ/tc rn_β τ/t O((1+βvic)K)O((1+β^vic)K) Sublinear Δirl=O(T) _ irl=O( T) RobustBandit cβrb⋅τ/Tc rb_β·τ/ T O(KlogK/T)O(K K/T) Linear Δirl=O(T1/4) _ irl=O(T^1/4) Remark E.0 (Implications for IRL Retraining). Table 1 reveals that different victims require different IRL retraining strategies. Algorithms with sublinear drift (NeuralUCB, R-NeuralUCB, NeuralTS) permit infrequent retraining (Δirl=O(T) _ irl=O( T)), while NeuralLinUCB’s faster drift from last-layer updates requires Δirl=O(T1/3) _ irl=O(T^1/3), and RobustBandit’s linear FTRL accumulation requires Δirl=O(T1/4) _ irl=O(T^1/4). In practice, our fixed Δirl=100 _ irl=100 with T=5000T=5000 satisfies all constraints (since T1/4≈8.4≪100≪T≈70.7T^1/4≈ 8.4 100 T≈ 70.7). The slightly more conservative retraining needed for RobustBandit is consistent with the experimental observation that AdvBandit’s success rate against RobustBandit (41%, Fig. 2) is lower than against NeuralUCB (57.8%). Theorem E.0 (Unified IRL Tracking Error). Under the victim-specific drift bound Dτ≤calg⋅g(τ,t)D_τ≤ c_alg· g(τ,t) from Table 1, with IRL retraining interval Δirl _ irl and window size W, the tracking error satisfies: [TV(πt∗,π^t)]≤O(dΘW)+calg⋅g(Δirl,t),E[TV(π^*_t, π_t)]≤ O\! ( d_ W )+c_alg· g( _ irl,t), (83) where the first term is the IRL statistical error (Theorem E.4) and the second is the policy drift between retrainings. Proof. Let tk=k⋅Δirlt_k=k· _ irl be the k-th retraining time. For t∈[tk,tk+1)t∈[t_k,t_k+1), via triangle inequality: TV(πt∗,π^t)≤TV(πt∗,πtk∗)⏟policy drift+TV(πtk∗,π^tk)⏟IRL error at retraining.TV(π^*_t, π_t)≤ TV(π^*_t,π^*_t_k)_policy drift+ TV(π^*_t_k, π_t_k)_IRL error at retraining. (84) The first term is bounded by Dt−tk≤calg⋅g(Δirl,tk)D_t-t_k≤ c_alg· g( _ irl,t_k) using the appropriate entry from Table 1. The second term is bounded by O(dΘ/W)O( d_ /W) from Theorem E.4. ∎ E.6 Multi-Objective Query Selection This section provides the complete formulation and theoretical analysis of the query selection mechanism summarized in Section 4.3. We first present the full multi-objective optimization framework, then prove the approximation guarantee stated in the main text. E.6.1 Multi-Objective Formulation Recall the three per-context objectives (Eq. 10): (t)=(P(t),Δ(t),w^(t))∈[0,1]3f(x_t)= (P(x_t),\; (x_t),\; w(x_t) )∈[0,1]^3, where P(t)P(x_t) is the attack success probability (Eq. 11), Δ(t)=ψ4(t) (x_t)= _4(x_t) is the regret gap, and w^(t)=ψ2(t) w(x_t)= _2(x_t) is the predicted defense trust level. These objectives often conflict: a context with a large regret gap (high Δ ) may have unusual gradient statistics (low w w), making attacks on it more detectable. Given the attack decision zt∈0,1z_t∈\0,1\ at each round t, the query selection problem is: maxzt[∑t=1Tzt⋅v(t)]s.t.∑t=1Tzt≤B,zt=0∀t∉(t), _\z_t\\;E\! [ _t=1^Tz_t· v(x_t) ] .t. _t=1^Tz_t≤ B, z_t=0\;\;∀\,x_t (A_t), (85) where v(⋅)v(·) is the scalarized value (Eq. 12) and (t)P(A_t) is the Pareto front of the running archive at round t. This extends the classical secretary problem with multiple selections by introducing a Pareto feasibility constraint. E.6.2 Pareto Non-Dominance Filter At each round t, we maintain an archive tA_t of objective vectors from previously observed (but not necessarily attacked) contexts. Before evaluating the scalarized score v(t)v(x_t), we first check whether tx_t is Pareto non-dominated: Definition E.0 (Pareto Non-Dominance). Context tx_t is Pareto non-dominated in archive tA_t if there is no s∈tx_s _t such that fj(s)≥fj(t)f_j(x_s)≥ f_j(x_t) for all j∈1,2,3j∈\1,2,3\ with at least one strict inequality. The Pareto filter serves two purposes: (i) it eliminates contexts that are strictly inferior across all three objectives, reducing variance in the scalarized scores, and (i) it ensures the scalarization only compares among “efficient” contexts, avoiding pathological cases where a dominated context scores highly under a particular weight vector. Lemma E.0 (Pareto Front Coverage). Let ∗∈argmaxv()x^*∈ _xv(x) be the context maximizing the Chebyshev scalarization v(⋅)v(·) for any fixed weight vector ∈ℝ+3 ω ^3_+. Then ∗∈()x^* (A) for any archive A containing ∗x^*. Proof. By Miettinen [31], every optimal solution of the Chebyshev scalarization minjωjfj() _j _jf_j(x) for strictly positive weights >0 ω>0 is Pareto optimal. Since ∗x^* maximizes v()=minjωjfj()v(x)= _j _jf_j(x), it is Pareto optimal and belongs to ()P(A). ∎ Corollary E.0 (No Optimal Context is Discarded). For any weight configuration (b,t) ω(b,t) defined by the adaptive weights in Eq. 12, the Pareto filtering step never removes the context that would be selected by the scalarized ranking. Consequently, the Pareto constraint in (85) does not reduce the optimal objective value. E.6.3 Chebyshev Scalarization and Adaptive Weights Among Pareto non-dominated candidates, we rank by the Chebyshev (min-based) scalarization: v(t)=minj∈1,2,3ωj(b,t)⋅fj(t),v(x_t)= _j∈\1,2,3\ _j(b,t)· f_j(x_t), (86) with budget- and time-adaptive weights: ω1=1,ω2=1+γ⋅bT−t,ω3=1+η⋅(1−bT−t), _1=1, _2=1+γ· bT-t, _3=1+η· (1- bT-t ), (87) where b is the remaining budget and γ>0γ>0, η>0η>0 are hyperparameters. Weight dynamics. When budget is plentiful (b≈Bb≈ B), ω2 _2 is large (emphasizing high-impact contexts) while ω3≈1 _3≈ 1 (stealth is less critical since many attacks remain). As budget depletes (b→0b→ 0), ω2→1 _2→ 1 and ω3 _3 increases (emphasizing stealth for the remaining attacks). This ensures early attacks prioritize impact while late attacks prioritize evasion. Remark E.0 (Why Chebyshev over Weighted Sum). A weighted-sum scalarization vsum=∑jωjfjv_sum= _j _jf_j suffers from two deficiencies in our setting: 1. Zero-objective pathology: If any single objective fj≈0f_j≈ 0 (e.g., near-zero success probability), the sum can remain high due to the other objectives, leading to attacks on contexts that are certain to fail. 2. Non-convex Pareto regions: Weighted sums cannot recover Pareto-optimal solutions in non-convex regions of the objective space [31], while the Chebyshev formulation can. The min -based Chebyshev form requires all objectives to be adequate for a high score, providing a natural “veto” mechanism: a single weak objective drags down the entire score. E.6.4 Quantile-Based Threshold Context tx_t is selected for attack if v(t)≥τv(b,T−t)v(x_t)≥ _v(b,T-t), where: τv(b,T−t)=Q1−b/(T−t)(v(s)s<t), _v(b,T-t)=Q_1-b/(T-t)\! (\v(x_s)\_s<t ), (88) and Qp(⋅)Q_p(·) denotes the p-th quantile of observed scalarized values. Threshold dynamics. The quantile level 1−b/(T−t)1-b/(T-t) increases as b decreases (budget consumed) or T−tT-t increases (more rounds remaining relative to budget). This automatically calibrates selectivity: early rounds use a permissive threshold (low quantile) to learn the score distribution, while later rounds become highly selective (high quantile) to conserve budget for the best contexts. Figure 7 in Appendix F.6 illustrates this evolution empirically. E.6.5 Theoretical Guarantee Assumption E.0 (Regularity Conditions). We assume: 1. (Sub-Gaussian objectives): Each fj(t)f_j(x_t) is sub-Gaussian with parameter σf _f, i.e., [exp(λ(fj(t)−[fj(t)]))]≤exp(λ2σf2/2)E[ (λ(f_j(x_t)-E[f_j(x_t)]))]≤ (λ^2 _f^2/2) for all λ. 2. (Slow weight variation): The adaptive weights satisfy ‖(b,t)−(b,t+1)‖∞≤Lω/(T−t)\| ω(b,t)- ω(b,t+1)\|_∞≤ L_ω/(T-t) for some constant Lω>0L_ω>0. 3. (Pareto front density): The fraction of Pareto non-dominated contexts satisfies |(t)|/t≥ϱ|P(A_t)|/t≥ for some constant ϱ>0 >0. Assumption 1 is standard for bounded objectives on [0,1][0,1]. Assumption 2 holds by construction, where weight changes are O(1/(T−t))O(1/(T-t)) per step. Assumption 3 ensures the Pareto front does not degenerate; this is mild when objectives are not perfectly correlated. Theorem E.0 (Multi-Objective Quantile Approximation Guarantee). Under Assumption E.6.5, the quantile-based query selection policy (Eq. 13) achieves: [∑t=1Tzt⋅v(t)]≥(1−O(1ϱB)⏟quantile estimation−O(LωB)⏟weight drift)⋅OPT,E\! [ _t=1^Tz_t· v(x_t) ]\;≥\; (1- O\! ( 1 B )_quantile estimation- O\! ( L_ω B )_weight drift )·OPT_P, (89) where OPTOPT_P is the optimal value achievable by an oracle that knows all contexts in advance and selects only from the Pareto front. Proof. We decompose the analysis into three steps. Step 1: Budget utilization. The quantile threshold τv(b,T−t) _v(b,T-t) is calibrated so that, in expectation, b out of the remaining T−tT-t Pareto non-dominated contexts exceed the threshold. By Assumption 3, at least ϱ(T−t) (T-t) candidates are available, so the effective selection rate is b/(ϱ(T−t))b/( (T-t)), ensuring full budget utilization: [∑t=1Tzt]=BE[ _t=1^Tz_t]=B. Step 2: Quantile estimation error. At round t, the empirical quantile is computed from |(t)|≥ϱ⋅t|P(A_t)|≥ · t Pareto non-dominated observations. By the Dvoretzky–Kiefer–Wolfowitz (DKW) inequality: supu|F^t(u)−F(u)|≤ln(2/ρ)2ϱt _u | F_t(u)-F(u) |≤ (2/ρ)2 t (90) with probability at least 1−ρ1-ρ. This induces a quantile estimation error of O(1/ϱt)O(1/ t), which, aggregated over T rounds, contributes O(1/ϱB)O(1/ B) suboptimality relative to OPTOPT_P. Step 3: Adaptive weight drift. Between consecutive rounds, the scalarized value of a fixed context x changes by: |v(b,t)()−v(b,t+1)()|≤‖(b,t)−(b,t+1)‖∞≤LωT−t.|v_ ω(b,t)(x)-v_ ω(b,t+1)(x)|≤\| ω(b,t)- ω(b,t+1)\|_∞≤ L_ωT-t. (91) Summing over T rounds, the cumulative drift contributes at most O(LωlnT)O(L_ω T) absolute error. Normalizing by OPT=Θ(B)OPT_P= (B) yields O(Lω/B)O(L_ω/ B) relative suboptimality for T=O(B2)T=O(B^2). ∎ Remark E.0 (Pareto Filtering Reduces Variance). By restricting selection to Pareto non-dominated contexts, the effective distribution of v()v(x) has reduced variance compared to the unfiltered population. Specifically, if σv2σ^2_v is the variance of v()v(x) over all contexts and σ2σ^2_P is the variance over the Pareto front, then σ2≤σv2σ^2_P≤σ^2_v since Pareto filtering removes low-value dominated points. This tighter distribution improves quantile estimation and reduces the constant in the O(1/ϱB)O(1/ B) term. E.6.6 Comparison with Simpler Alternatives To justify the multi-objective formulation, we compare against lightweight alternatives that progressively remove components: 1. Single-objective variant. Use only the regret-gap–weighted success probability: vsimple(t)=Δ(t)⋅P(t)v_simple(x_t)= (x_t)· P(x_t), with the same quantile threshold (Eq. 13). This ignores stealth entirely. 2. Product scalarization. Use vprod=f1⋅f2⋅f3v_prod=f_1· f_2· f_3, which avoids the Chebyshev form but retains all three objectives. 3. Chebyshev without Pareto. Use the full Chebyshev scalarization (Eq. 12) but skip the Pareto non-dominance filter. Table 2: Query selection variant comparison on Yelp (R-NeuralUCB, B=200B=200). The full method (Pareto + Chebyshev) achieves the best performance; the single-objective variant retains 89%89\% effectiveness and may be preferred when simplicity is prioritized. Query Selection Variant Victim Regret Success Rate Detection Rate Budget Used Pareto + Chebyshev (full, Eq. 12) ±673± 52 0.42 0.19 197/200 Chebyshev only (no Pareto filter) 651±54651± 54 0.41 0.20 195/200 Product scalarization (f1⋅f2⋅f3f_1· f_2· f_3) 618±55618± 55 0.39 0.22 193/200 Single-objective (Δ⋅P · P, no stealth) 601±49601± 49 0.40 0.28 198/200 ϵε-greedy (ϵ=0.1ε=0.1, best-tuned) 448±45448± 45 0.35 0.27 189/200 Random (B/TB/T) 289±38289± 38 0.25 0.27 200/200 Table 2 shows that the full Pareto + Chebyshev method achieves the highest regret (673673), but the single-objective variant Δ⋅P · P retains 89%89\% of this performance (601601) with a simpler implementation. The main cost of dropping stealth is a higher detection rate (0.280.28 vs. 0.190.19), which is acceptable in settings where detection is not penalized. The Pareto filter provides a modest but consistent improvement (673673 vs. 651651), confirming Remark E.6.5. The product scalarization (618618) underperforms Chebyshev (673673) due to the zero-product pathology: contexts where one objective is near zero receive near-zero scores regardless of the others. Recommendation. For settings where stealth matters (e.g., attacking robust victims with anomaly detection), we recommend the full Pareto + Chebyshev formulation. For settings prioritizing simplicity, the single-objective variant v(t)=Δ(t)⋅P(t)v(x_t)= (x_t)· P(x_t) with quantile thresholding provides a competitive and lightweight alternative. Appendix F Additional Experiments Fig. 5 extends results in Fig. 2 demonstrating AdvBandit’s ability to discover victim-specific attack strategies through GP-UCB optimization for the MovieLens and Disin datasets. Against standard algorithms (NeuralUCB, NeuralLinUCB), AdvBandit maximized attack effectiveness (λ(1)λ^(1)) with mean values of around 1.2, while against robust algorithms (R-NeuralUCB, RobustBandit), it prioritizes statistical evasion (λ(2)λ^(2)) to avoid detection. For the stochastic NeuralTS, AdvBandit emphasizes temporal smoothness (λ(3)λ^(3)) to maintain consistent influence despite random arm selection. These patterns persist across both datasets, confirming that AdvBandit learns generalizable attack strategies aligned with the theoretical properties of each victim algorithm. The near-zero trend values (Δ≈±0.01 ≈± 0.01) across all configurations indicate that AdvBandit rapidly converges to stable attack strategies. (a) MovieLens Dataset. (b) Disin Dataset. Figure 5: Distribution of continuous arm components (λ(1)λ^(1)(effectiveness), λ(2)λ^(2) (evasion), λ(3)λ^(3)(temporal)) across victim algorithms on the MovieLens and Disin datasets. F.1 Ablation Analysis on AdvBandit’s Components Table 3 compares AdvBandit against variants with different components on Yelp using R-NeuralUCB victim (B=200B=200, T=5000T=5000). AdvBandit with MaxEnt IRL achieves performance close to oracle access to ground-truth rewards (673 vs. 628, a 7% gap), indicating that IRL accurately captures the victim’s policy, while alternative IRL methods perform substantially worse, including behavior cloning (412, 39% degradation) and inverse Q-learning (468, 30% degradation). Regarding adaptive parameter selection via GP-UCB, random λ selection (198) and fixed λ=(1,1,1)λ=(1,1,1) (287) achieve only 29% and 43% of AdvBandit’s performance, respectively, whereas grid search approaches AdvBandit (534, 79%) at the cost of 2.2× higher runtime, and Bayesian optimization is competitive but still inferior (548, 81%). Query selection plays a key role in efficient budget allocation, as random selection wastes attacks on low-value contexts (289, 43%), fixed thresholds partially improve performance (378, 56%) but lack adaptivity, and attacking all rounds (B=TB=T) achieves the highest regret (721) at the expense of prohibitive runtime (13× slower) and high detection (0.42), whereas AdvBandit’s quantile-based strategy attains 93% of this upper bound (673/721) with low detection (0.19) and high efficiency. Finally, removing PGD and using random perturbations leads to a huge failure (134, 20%), confirming that gradient-based optimization of δ under the multi-objective loss is necessary. Table 3: Component ablation on Yelp (R-NeuralUCB victim, B=200B=200). Each row removes one component. Values are victim regret (higher is better for attacker). Variant Victim Regret Success Rate Detection Rate Runtime (s) AdvBandit (Full) 673 ± 52 0.42 0.19 142.3 Remove IRL (use ground-truth reward) Oracle reward 628 ± 48 0.47 0.18 89.5 Replace IRL with alternatives Behavior cloning 412 ± 45 0.34 0.24 136.7 Inverse Q-learning 468 ± 49 0.38 0.21 158.2 Replace GP-UCB with alternatives Random λ 198 ± 38 0.19 0.38 98.1 Fixed λ=(1,1,1)λ=(1,1,1) 287 ± 41 0.26 0.31 95.3 Grid search (10×10×10) 534 ± 50 0.40 0.20 312.7 Bayesian Opt. (BO) 548 ± 51 0.41 0.19 167.8 Replace Query Selection Random selection 289 ± 38 0.25 0.27 138.9 Fixed threshold 378 ± 42 0.31 0.26 119.4 Attack all (B=TB=T) 721 ± 63 0.51 0.42 1847.2 Remove PGD (use random perturbations) Random δ 134 ± 29 0.15 0.19 87.6 F.2 Ablation Analysis on Attack Parameter Space Table 4 compares attack performance across different attack parameter dimensions on the Yelp dataset with R-NeuralUCB as the victim. The results show that 3D achieves the highest victim regret (573) despite having moderate sample complexity, while 4D and 5D perform significantly worse (581 and 587, respectively) despite similar theoretical expressiveness. Empirical results demonstrate that in practice, the number of required samples is lower than that proven in the theoretical claim because of conditions (i) smoothness of the actual reward function r(,)r( ψ, λ) and (i) convergence criteria (not worst-case bounds). Table 4: Attack performance vs. dimensionality on the Yelp dataset (R-NeuralUCB victim, B=200B=200). Dimension Victim Regret Success Rate Detection Rate Samples Needed Runtime (s) 1D (λ(1),0,0)(λ^(1),0,0) 245 ± 32 0.31 0.42 87 12.3 2D-A (λ(1),λ(2),0)(λ^(1),λ^(2),0) 412 ± 41 0.38 0.28 134 18.7 2D-B (λ(1),0,λ(3))(λ^(1),0,λ^(3)) 389 ± 38 0.36 0.35 128 17.9 3D (λ(1),λ(2),λ(3))(λ^(1),λ^(2),λ^(3)) 573 ± 52 0.42 0.19 686 26.4 4D (λ(1),λ(2),λ(3),λ(4))(λ^(1),λ^(2),λ^(3),λ^(4)) 581 ± 49 0.43 0.18 3,972 51.2 5D (λ(1),λ(2),λ(3),λ(4),λ(5))(λ^(1),λ^(2),λ^(3),λ^(4),λ^(5)) 587 ± 51 0.43 0.17 20,648 89.7 F.3 Ablation Analysis on Attack Budget In Table 5, we have evaluated fixed budgets B∈50,100,150,200,250,300,350,400B∈50,100,150,200,250,300,350,400 for a horizon of T=5000T=5000 to analyze scalability and the budget–regret trade-off. The results have shown that AdvBandit achieved 1.3×–1.9× higher victim regret than the best baseline across all budgets, following power-law scaling Rv(B)≈3.25B0.90R_v(B)≈ 3.25B^0.90 with exponent <1<1 confirming diminishing returns. Attack efficiency (regret per attack) peaks at B=200B=200 before declining, validating our selection of B=200 (4% attack rate) as the standard budget that balances absolute regret (393), efficiency (1.97 regret/attack), and practical constraints. Table 5: Budget-Regret Trade-off Analysis on Yelp with R-NeuralUCB victim (T=5000T=5000). AdvBandit achieves 1.3×–1.9× higher regret than best baseline across all budgets, with power-law scaling Rv(B)≈3.25⋅B0.90R_v(B)≈ 3.25· B^0.90 confirming diminishing returns beyond B=250B=250. Budget B Victim Regret Rv(T)R_v(T) Best Advantage Efficiency AdvBandit Liu Ma Garcelon Ilyas Baseline 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 300 525 368 304 149 139 368 1.43× 1.75 350 645 436 358 165 159 436 1.48× 1.84 400 703 461 435 205 191 461 1.53× 1.76 Marginal gains: ΔRv R_v decreases from 1.96 (B=150→200) to 1.17 (B=350→400) regret per attack Standard budget: B=200B=200 (4% attack rate) highlighted—balances regret, efficiency, and detection F.4 Ablation Analysis on Feature Set Extraction Table 6 compares our gradient-based features against feature selection baselines (i.e., PCA, random projection, and autoencoder) as well as different combinations of gradient-based features. Raw context caused GP to require 10×10× more samples, resulting in poor performance (victim regret 287 vs. 573). Table 6: Feature ablation on Yelp (R-NeuralUCB, B=200B=200) Feature Set Dimension Victim Regret Success Rate GP γn _n Raw context x 20 287 ± 45 0.24 O((logn)21)O(( n)^21) PCA (top 5) 5 421 ± 38 0.34 O((logn)6)O(( n)^6) Random projection 5 398 ± 41 0.32 O((logn)6)O(( n)^6) Autoencoder 5 445 ± 39 0.36 O((logn)6)O(( n)^6) ψ1 _1 only (entropy) 1 312 ± 36 0.28 O((logn)2)O(( n)^2) ψ1,ψ4 _1, _4 (entropy, gap) 2 456 ± 42 0.37 O((logn)3)O(( n)^3) ψ1,ψ2,ψ4 _1, _2, _4 (no Maha., no time) 3 501 ± 47 0.39 O((logn)4)O(( n)^4) ψ1,ψ2,ψ3,ψ4 _1, _2, _3, _4 (no time) 4 548 ± 50 0.41 O((logn)5)O(( n)^5) Full ,…, _1,…, _5 5 673 ± 52 0.42 (()) O(( n)^6) Fig. 6 analyzes the correlation between extracted features ψ1−ψ1 _1- _1 and attack reward r and also validate that all features are predictive of attack success, as shown in Fig. 6. All features show significant correlation with attack reward (p<0.001p<0.001): ψ4 _4 (Regret Gap, ρ=+0.81) is strongest, followed by ψ2 _2 (Defense Weight, ρ=+0.73) and ψ1 _1 (Entropy, ρ=+0.68). Negative correlations for ψ3 _3 (Mahalanobis, ρ=-0.52) and ψ5 _5 (Time, ρ=-0.34) validate defense-awareness and temporal adaptation." Figure 6: Correlation between features ψi _i and attack reward r on 1000 held-out attacks. All features show significant correlation (p<0.001p<0.001), validating their predictiveness. F.5 Ablation Analysis on IRL’s Window Size and Retraining Frequency In this subsection, we analyze two critical IRL hyperparameters: window size W (i.e., the number of recent observations stored for training) and retraining interval ΔIRL _IRL (i.e., how often the reward model is updated). Table 7 shows results across three datasets with T=5000T=5000 and B=200B=200, measuring victim regret (attack effectiveness), IRL KL divergence DKL(h^θ∥h)D_KL( h_θ\|h) (reward approximation quality), tracking error ‖h^θ(x)−h(x)‖2\| h_θ(x)-h(x)\|_2 (how well we follow victim behavior changes), and runtime overhead. Table 7: IRL hyperparameter ablation across three datasets (T=5000T=5000, B=200B=200). Window size W controls training data; retraining interval ΔIRL _IRL controls update frequency. Optimal: W=400,ΔIRL=100W=400, _IRL=100 for d=20d=20; W=300,ΔIRL=75W=300, _IRL=75 for d=8d=8. W ΔIRL _IRL Yelp (d=20d=20) MovieLens (d=20d=20) Disin (d=8d=8) 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 – – – – 400 50 742 0.05 0.04 180 699 0.03 0.04 184 543 0.07 0.03 163 400 200 615 0.05 0.04 118 618 0.06 0.06 119 484 0.06 0.06 92 300 75 – – – – – – – – 564 0.08 0.07 117 KL = KL divergence DKL(h^θ∥h)D_KL( h_θ\|h); Track = Tracking error ‖h^θ(x)−h(x)‖2\| h_θ(x)-h(x)\|_2; Time = Runtime (seconds) Optimal configurations highlighted. Regret averaged over 10 seeds; KL/Track measured on 1000-context validation set Effect of Window Size W. Small windows (W≤100W≤ 100) severely degrade performance, achieving only 425–529 regret on Yelp/MovieLens compared to 684–718 for W=400W=400. This occurs because insufficient training data leads to high-variance reward estimates, reflected in elevated KL divergence (0.11–0.20 for W≤100W≤ 100 vs. 0.03–0.05 for W=400W=400) and tracking error (0.11–0.13 vs. 0.03–0.04). With only 50–100 samples, the IRL neural networks cannot learn stable reward functions, particularly for distinguishing subtle differences in context values that determine optimal attack timing. Conversely, excessively large windows (W=800W=800) provide minimal gains (494–505 regret, actually worse than W=400W=400) despite lower KL divergence (0.03–0.04), because the inclusion of stale observations from early rounds when victim behavior was different impedes adaptation to the victim’s current policy. The optimal W=400W=400 provides sufficient data for stable learning (approximately 6–8 epochs with batch size 64 over ΔIRL=100 _IRL=100 rounds of retraining) while maintaining responsiveness to victim adaptation. For lower-dimensional datasets (Disin, d=8d=8), the optimal window size decreases to W=300W=300 since fewer parameters require less training data. Effect of Retraining Interval ΔIRL _IRL. Given a fixed W=400W=400, a frequent ΔIRL=50 _IRL=50 achieved a near-optimal regret (699–742) and maintained a low tracking error (0.03–0.04), but introduced 30% runtime overhead (163–184s vs. 124–138s) since we retrain twice as often (T/ΔIRL=5000/50=100T/ _IRL=5000/50=100 retrainings vs. 50 for ΔIRL=100 _IRL=100). In contrast, infrequent retraining ΔIRL=200 _IRL=200 reduced runtime to 92–119s but degrades regret to 484–618 (10–15% loss) and increased tracking error to 0.06, because the model becomes stale between updates, by the time we retrain at round 200, the buffer contains observations from rounds 1–200, but the victim’s behavior at round 200 may have shifted significantly from round 1 due to learning or adaptation. The optimal ΔIRL=100 _IRL=100 balances these trade-offs: frequent enough to track victim behavior (tracking error 0.03–0.04, updated every 2% of horizon) yet infrequent enough to avoid excessive retraining overhead. The W/ΔIRLW/ _IRL Ratio. Across configurations, the ratio W/ΔIRLW/ _IRL emerges as a key design parameter. The optimal configuration W=400,ΔIRL=100W=400, _IRL=100 yields ratio 4, meaning we accumulate ΔIRL=100 _IRL=100 new samples between retrainings while maintaining a sliding window of the most recent W=400W=400 samples. This creates 75% overlap in training data between consecutive retrainings (300 out of 400 samples persist), providing stability while incorporating 25% fresh observations to track changing victim behavior. Ratios that are too small (W/ΔIRL=1W/ _IRL=1 for W=50,ΔIRL=50W=50, _IRL=50) cause high variance from insufficient data (regret drops 34–40%), while ratios that are too large (W/ΔIRL=4W/ _IRL=4 for W=800,ΔIRL=200W=800, _IRL=200) lead to staleness and slow adaptation (regret drops 26–31%). The ratio 4 appears robust across datasets and an optimal performance at this ratio was achieved, though the absolute values differ (W=400W=400 for d=20d=20 vs. W=300W=300 for d=8d=8), confirming that both the ratio and absolute scale matter. Cross-Dataset Consistency. The optimal W/ΔIRLW/ _IRL ratio remains consistent at 4 across all three datasets, demonstrating the robustness of this design principle. However, the absolute optimal window size scales with problem dimension: W=400W=400 for d=20d=20 (Yelp, MovieLens) vs. W=300W=300 for d=8d=8 (Disin). This reflects the fact that neural networks with larger input dimensions require more training samples to achieve stable parameter estimates. The performance degradation from suboptimal configurations is consistent across datasets: small windows (W≤100W≤ 100) cause 34–40% loss, oversized windows (W=800W=800) cause 26–31% loss, and mismatched retraining frequencies (ΔIRL≠W/4 _IRL≠ W/4) cause 10–15% loss. These patterns validate our hyperparameter choices and provide guidance for adapting AdvBandit to new domains: set W proportional to d d (more parameters need more data) and maintain ΔIRL=⌊W/4⌋ _IRL= W/4 to balance stability and responsiveness. F.6 Ablation Analysis on Query Selection Threshold Table 8 evaluates AdvBandit algorithm with different thresholds (fixed threshold, Greedy Top-B, Random selection, ϵε-Greedy, top-B oracle (offline), and quantile-based) on Yelp dataset against R-NeuralUCB. In greedy top-B, all contexts are stored in the memory and the top B is attacked at the end. This requires O(T)O(T) memory and violates the online constraint. Random selection chooses contexts with probability B/TB/T at each round. This method ignores context values entirely. Expected regret is [∑ztv(xt)]=(B/T)∑v(xt)E[Σ z_tv(x_t)]=(B/T)Σ v(x_t), which is suboptimal compared to selecting high-value contexts. In ϵε-Greedy, an attack is conducted if v(xt)v(x_t) exceeds current average with probability 1−ϵ1-ε. However, ϵε is an additional hyperparameter. From the table, random selection expends the full budget but targets low-value contexts (average v=0.312v=0.312), resulting in low victim regret (289), while the fixed-threshold method underutilizes the budget (143/200 attacks) due to its inability to adapt to the remaining budget and consequently misses high-value contexts; the ϵε-greedy strategy improves over random selection but remains suboptimal and sensitive to tuning of ϵε; the offline oracle provides an upper bound with perfect foresight, achieving 712 regret by selecting the top 200 contexts; in contrast, the proposed quantile-based method attains 94% of oracle performance (673/712673/712) in a fully online setting, uses nearly the full budget (197/200), and targets substantially higher-value contexts (average v=0.689v=0.689 compared to 0.7340.734 for the oracle). Table 8: Query selection ablation on Yelp (R-NeuralUCB, B=200B=200) Strategy Attacks Used Avg. v(xt)v(x_t) Victim Regret Success Rate Efficiency Random (B/TB/T) 200 0.312 289 ± 38 0.25 0.0145 Fixed threshold (τ=0.5τ=0.5) 143 ± 27 0.581 378 ± 42 0.31 0.0264 ϵε-greedy (ϵ=0.1ε=0.1) 189 ± 15 0.487 448 ± 45 0.35 0.0237 Top-B oracle (offline) 200 0.734 712 ± 61 0.48 0.0356 Quantile (Ours) 197 ± 8 0.689 673 ± 52 0.42 0.0291 Fig. 7 illustrates how AdvBandit’s adaptive query selection threshold τv(b,T−t) _v(b,T-t) evolves over time, ensuring efficient budget allocation to efficiently allocate the attack budget. On Yelp with T=5000T=5000 rounds and budget B=200B=200, the threshold consistently tracks approximately the 96th percentile of observed context values throughout the horizon, becoming increasingly selective as the ratio b/(T−t)b/(T-t) evolves. The attacked contexts (green points) have a mean value v¯=0.927 v=0.927, while rejected contexts (gray points) have v¯=0.386 v=0.386, corresponding to a 2.4×2.4× improvement in context quality via adaptive selection. AdvBandit captures 93.5%93.5\% of the top-200 highest-value contexts, approaching the oracle baseline (100%) despite operating fully online without future knowledge, and fully utilizes the budget (200/200 attacks). These results guarantee that quantile-based selection achieves (1−ϵq)(1- _q)-optimality with ϵq=(1/B) _q=O(1/ B), demonstrating effective online attack scheduling without hyperparameter tuning. Figure 7: Evolution of query threshold τv(b,T−t) _v(b,T-t) over time. Threshold increases as budget depletes, ensuring selective attacks at the end (red line: Threshold τv _v, gray dots: not attacked, green dots: attacked, and blue shaded area: remaining budget). F.7 Ablation Analysis on Zero-Order Perturbation To validate that AdvBandit’s effectiveness does not critically depend on gradient-based perturbation optimization, we replace PGD (Section 4.5) with two gradient-free alternatives that require no backpropagation through the surrogate: 1. NES (Natural Evolution Strategy): Estimates ∇ℒ _ δL via Gaussian-smoothed finite differences [19]: ∇^ℒ=1Nnesσnes∑j=1Nnesℒ(,+σnesj)⋅j,j∼(,), ∇_ δL= 1N_nes _nes _j=1^N_nesL(x, δ+ _nesu_j)·u_j, _j (0,I), (92) with Nnes=50N_nes=50 samples and smoothing σnes=0.01 _nes=0.01, iterated for Ines=100I_nes=100 steps. 2. Random search: Samples Nrand=500N_rand=500 perturbations uniformly from :‖∞≤ϵ\ δ:\| δ\|_∞≤ε\ and selects the one minimizing ℒL. Both alternatives evaluate the surrogate loss ℒL as a black-box function, using only forward passes (no backpropagation). This reduces the computational requirements of the attacker at the cost of perturbation quality. Table 9: Zero-order perturbation ablation on Yelp (R-NeuralUCB, B=200B=200). PGD on the surrogate achieves the best performance, but NES retains 84% effectiveness using only forward evaluations of the surrogate. Perturbation Method Victim Regret Success Rate Surrogate Queries Runtime (s) Gradient-Free? PGD (default) 673±52673± 52 0.42 100100 (grad steps) 142 No (surrogate grads) NES (N=50N=50) 565±58565± 58 0.37 5,0005,000 (fwd passes) 189 ✓ Random search 312±41312± 41 0.24 500500 (fwd passes) 108 ✓ Random δ (no surrogate) 134±29134± 29 0.15 0 88 ✓ Results (Table 9). PGD achieves the best victim regret (673673), but NES retains 84%84\% of this performance (565565) using only forward evaluations of the surrogate—no backpropagation required. Random search achieves 46%46\% (312312), and random perturbations without any surrogate achieve only 20%20\% (134134). This reveals two insights: (i) the surrogate model itself is the primary source of attack effectiveness (comparing 312312 with 134134 shows a 2.3×2.3× improvement from surrogate guidance alone, even without gradient optimization); and (i) gradient-based PGD provides a meaningful but not critical 1.2×1.2× improvement over NES, suggesting that the attack’s observation-only access pattern (building a surrogate from context–action pairs) is more important than the specific optimization method used for perturbation generation. This ablation confirms that AdvBandit’s core contribution—the bandit formulation over the (λ(1),λ(2),λ(3))(λ^(1),λ^(2),λ^(3)) trade-off space combined with IRL-based surrogate modeling—is robust to the choice of inner optimization method. The PGD variant is presented as the default due to its superior performance, but the framework remains effective even under a strictly gradient-free perturbation regime. Appendix G Computational Cost G.1 Runtime comparison for attack baselines Table 10: Baseline method runtimes and complexity across three datasets (T=5000T=5000, B=200B=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. Method Runtime (seconds) Complexity Key Operations Yelp MovieLens Disin Liu et al. 46.3 48.8 41.6 O(T+B⋅IPGD)O(T+B· I_PGD) PGD on fixed objective Garcelon et al. 52.4 54.8 43.5 O(T+B⋅IPGD)O(T+B· I_PGD) Gradient-free perturbations Ma et al. 40.0 37.8 32.2 O(T+B⋅IPGD)O(T+B· I_PGD) Greedy context selection Ilyas et al. 96.1 91.7 79.0 O(T+B⋅Ngrad⋅IPGD)O(T+B· N_grad· I_PGD) Bandit gradient estimation Wang et al. 66.6 65.8 58.2 O(T+B⋅Nsample⋅IPGD)O(T+B· N_sample· I_PGD) Random sampling AdvBandit 140.6 139.0 118.5 O(T⋅W+B3+B⋅IPGD)O(T· W+B^3+B· I_PGD) IRL + GP + multi-start + PGD Yelp and MovieLens: d=20d=20 (user + item features); Disin: d=8d=8 (simplified context) Parameters: W=400W=400, IPGD=100I_PGD=100, Ngrad=20N_grad=20, Nsample=10N_sample=10, Nrandom=100N_random=100, Nrefine=20N_refine=20 Table 10 compares AdvBandit’s runtime with five attack baselines across three datasets (Yelp, MovieLens, Synthetic) with T=5000T=5000 and B=200B=200. AdvBandit requires 118–141 seconds depending on dimension d, making it 3.5×–3.7× slower than baselines due to three overhead sources: (1) MaxEnt IRL must learn reward functions from observed context-action pairs at cost O(T⋅W)O(T· W) with W=400W=400, whereas baselines assume direct gradient access or use fixed heuristics; (2) GP posterior updates require O(B3)O(B^3) Cholesky decompositions for each of B=200B=200 attacks; and (3) non-convex UCB acquisition optimization requires Nrandom=100N_random=100 random initializations plus Nrefine=20N_refine=20 L-BFGS gradient-based refinements per attack. Despite this overhead, AdvBandit achieves 2.9×–3.0× higher victim regret than the fastest baseline (Ma et al.), demonstrating that the computational cost is justified by substantially improved attack effectiveness. The modest runtime variation across datasets (141s for Yelp vs. 119s for Synthetic) reflects dimension scaling: higher d increases IRL training cost O(T⋅W⋅d)O(T· W· d) and gradient statistics storage O(d2)O(d^2), while the dominant GP term O(B3)O(B^3) remains constant. For time-critical applications, sparse GP approximations using M=50M=50 inducing points can reduce the O(B3)O(B^3) bottleneck to O(M⋅B2)O(M· B^2), yielding an estimated 5× speedup with minimal performance loss (<2%<2\% regret degradation in preliminary experiments). Table 11: Memory usage breakdown across three datasets (T=5000T=5000, B=200B=200). Dominant components are IRL networks (57% for d=20d=20, 35% for d=8d=8) and GP kernel matrix (41% for d=20d=20, 63% for d=8d=8). Lower-dimensional datasets require 35% less memory overall. Component Memory (MB) Scaling Yelp MovieLens Disin IRL networks (h^θ,σ^ϕ h_θ, σ_φ) 128.0 128.0 51.2 O(d⋅dh⋅K)O(d· d_h· K) IRL training buffer (W samples) 3.1 3.1 1.2 O(W⋅d)O(W· d) GP kernel matrix (K∈ℝB×BK ^B× B) 91.6 91.6 91.6 O(B2)O(B^2) GP observations ((ψi,λi,ri)\( _i, _i,r_i)\) 0.1 0.1 0.1 O(B⋅9)O(B· 9) Gradient statistics (μg,Σg _g, _g) 0.1 0.1 <0.1 O(d2)O(d^2) Multi-start candidates 0.1 0.1 0.1 O(Nrandom⋅3)O(N_random· 3) PGD intermediate states 0.4 0.4 0.2 O(d⋅IPGD)O(d· I_PGD) Total 223.3 223.3 144.4 – Memory includes parameters, gradients, optimizer states (Adam), and framework overhead (PyTorch/GPyTorch) Hidden dimensions: dh(1)=128d_h^(1)=128, dh(2)=64d_h^(2)=64; Arms: K=10K=10; Window: W=400W=400; Budget: B=200B=200 G.2 Memory Breakdown Table 11 decomposes AdvBandit’s memory usage across three datasets with T=5000T=5000 and B=200B=200. Total memory ranges from 144 MB (Disin, d=8d=8) to 223 MB (Yelp/MovieLens, d=20d=20), dominated by two components: IRL neural networks (128 MB for d=20d=20, 57% of total; 51 MB for d=8d=8, 35% of total) storing two 2-layer networks with hidden dimensions [128,64][128,64] for reward and uncertainty estimation, including parameters, gradients, and Adam optimizer states (momentum and variance buffers); and the GP kernel matrix (92 MB, 41% for d=20d=20 or 63% for d=8d=8) storing the full B×B× B Gram matrix plus Cholesky decomposition, inverse, and derivative caching in GPyTorch. IRL networks scale linearly with dimension (O(d⋅dh⋅K)O(d· d_h· K)), explaining the 2.5× difference between d=20d=20 (128 MB) and d=8d=8 (51 MB) datasets, while the GP kernel matrix remains constant at 92 MB regardless of d since it depends only on budget B. Gradient statistics (μg∈ℝd _g ^d, Σg∈ℝd×d _g ^d× d) require 0.1 MB for d=20d=20 to maintain empirical mean and covariance for anomaly detection in robust defenses. The remaining components, IRL training buffer (3.1 MB for d=20d=20, 1.2 MB for d=8d=8), GP observations (0.1 MB), multi-start candidates (0.1 MB), and PGD states (0.4 MB), collectively account for <2%<2\% of total memory. This usage is modest for modern hardware (similar to training a small CNN) but can be reduced via sparse GP methods: replacing the full kernel matrix with M=50M=50 inducing points reduces memory from 92 MB to 18 MB (5× savings) while introducing <2%<2\% approximation error, making AdvBandit practical even for resource-constrained adversarial evaluation scenarios. 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. Dataset Regret Runtime (s) Memory (MB) Efficiency Improvement Ma AdvBandit Ma AdvBandit Ma AdvBandit R/T R/M 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) G.3 Cost-Benefit Analysis Table 12 quantifies the cost-benefit trade-off between AdvBandit and the most competitive baseline (Ma et al.) across three datasets with T=5000T=5000 and B=200B=200. While AdvBandit incurs 3.5×–3.7× higher runtime (119–141s vs. 32–40s) and 1.2×–1.4× higher memory (144–223 MB vs. 102–181 MB), it achieves 2.9×–3.0× higher victim regret (573–683 vs. 191–226), translating to substantially greater absolute attack impact. The normalized efficiency metrics reveal AdvBandit maintains 82% time efficiency (regret per second: 4.70 vs. 5.71 for baselines) and 232% memory efficiency (regret per MB: 2.76 vs. 1.16 for baselines on average). This trade-off is favorable for adversarial robustness evaluation, where the primary objective is maximizing attack effectiveness to identify vulnerabilities, not minimizing computational cost. Notably, AdvBandit’s relative computational overhead decreases on lower-dimensional datasets (Synthetic: 3.68× runtime vs. Yelp: 3.52× runtime) due to reduced IRL training costs, while attack effectiveness improvements remain consistent (2.9×–3.0× across all datasets), demonstrating robustness to problem dimensionality. In security-critical applications where a single successful attack can have severe consequences, the 2.98× average improvement in attack success justifies the moderate increase in computational resources, particularly since both methods complete within 2–3 minutes on standard hardware (Intel Xeon Gold 6248R @ 3.0 GHz, NVIDIA V100 32GB). For large-scale evaluations, the computational cost can be amortized: once AdvBandit identifies vulnerabilities on a representative sample, targeted defenses can be developed and validated more efficiently.