betaFeedback

WorksComputer Science

RLGPA: A Reinforcement Learning-Guided Granularity Planning Attack for Decision-Based Sparse Adversarial Examples

Abstract

Decision-based sparse attacks must reduce perturbation support using only the victim's predicted label. The best restoration strategy varies as support contracts: coarse removal works early, while tail states need finer, history-aware tests. We propose RLGPA, an online reinforcement learning method that schedules support-reduction executors and their granularity under a hard query budget. A masked Dueling Double DQN selects among seven stable policy–scale actions; each action produces support-relative restoration groups that are rebuilt after every macro decision. A feasibility-preserving executor commits only adversarial restorations and feeds support gain and query cost back to the planner. Under the matched top-1-label oracle, RLGPA reaches 61% targeted ASR at sparsity 0.01 on CIFAR-10 (vs. 25% SparseEvo, 0% Pointwise), and 75.5%/73.0% on ResNet50/ViT at sparsity 0.005 (vs. 29.0%/15.5%). A fixed-probe test reduces median L0L_0 from 165 to 23 after 40 images without any update. State-blind and state-shuffled controls degrade significantly, confirming that the learned policy uses attack state; the main gains come from state-conditioned executor scheduling and dynamic repartition. The source code is publicly available at https://github.com/Acui001/RLGPA.git.

Introduction

Deep neural networks achieve strong performance across a wide range of perception tasks, yet their vulnerability to adversarial examples, which are inputs crafted by adding small, often human-imperceptible perturbations that cause incorrect predictions, introduces significant security risks to deep learning-based visual detection tasks [1, 2, 3, 4]. This vulnerability has motivated a large body of work on adversarial attacks [5, 6, 7, 8], which differ in the threat model they assume and in the constraints they place on the perturbation. Among these, sparse adversarial attacks are particularly relevant to security-critical settings, because they modify only a limited number of input dimensions and therefore correspond more closely to the practical constraint that an attacker can manipulate only a small part of the input.

Sparse adversarial attacks seek an adversarial input whose perturbation involves only a small subset of image pixels. The underlying minimum-L0L_0 adversarial problem is NP-hard [9]. In a decision-based black-box setting, the attacker observes only the top-1 predicted label and cannot access gradients, logits, or confidence scores. As a result, exact support minimization, i.e., minimizing the set of modified pixels, becomes a query-bounded combinatorial search. Starting from a feasible adversarial point, Pointwise attack [10] and SparseEvo attack [9] approach this problem through perturbation erasure: they ask which active coordinates can be restored to the original image without losing adversarial feasibility. Pointwise greedily tests restorations, whereas SparseEvo evolves binary support masks. Their results show that support erasure is central to decision-based sparse attacks, but they also expose a scheduling problem: the best restoration ordering and group size need not remain fixed throughout an attack.

This scheduling problem arises because the search has a pronounced stage dependence. Large groups can remove support quickly when many perturbed coordinates are redundant. However, as the support shrinks, the same removals cross the decision boundary more often, and the attack benefits from finer groups or from empirical knowledge about previous restoration outcomes. A fixed schedule cannot condition on current progress, stalls, acceptance rate, or remaining budget. Conversely, directly assigning reinforcement-learning actions to temporary pixel groups is ill posed: dynamic repartition changes the coordinates represented by an action index, making replay transitions semantically unstable.

To address this problem, we propose RLGPA, a reinforcement learning-guided granularity planning attack, where reinforcement learning (RL) schedules the executor policy and granularity. Instead of selecting a pixel-group index, the agent selects a stable macro-action that composes an executor policy with a relative scale. The executor instantiates that action on the current support, tests a bounded number of restorations, and commits only adversarial candidates. The next macro decision is therefore made after observing an actual support reduction and query cost. Because Primary, Safe, and Memory retain their meanings after repartition and across images, transitions can be reused by an online Dueling Double DQN.

RLGPA uses support-relative granularity. If LtL_t coordinates remain perturbed, an action selects a group size proportional to LtL_t rather than to the original image dimension. This produces the same seven action semantics on CIFAR-10 and ImageNet despite their very different resolutions. Dynamic repartition then rebuilds groups around the newly committed adversarial point. The DQN observes the optimization phase, current granularity, recent gains and acceptances, stall counts, remaining budget, recent action identity, action-specific effectiveness, and Chao Zhou, Jiaxin Mo, Qiangguo Yu are with the School of Electronic Information, Huzhou College, Huzhou, 313000, China (e-mail: [email protected]; [email protected]; [email protected]).

Shenghua He is with the School of Electronic Science and Engineering, South China Normal University, Foshan, 528225, China (e-mail: [email protected]).

Fengchuang Xing is with the School of Physics and Information Engineering, Guangdong University of Education, Guangzhou, 510303, China (e-mail: [email protected]).

Shenghua He and Chao Zhou are equally contributed to this work.

Corresponding author: Shenghua He. the valid-action mask.

Our contributions are as follows:

  • We formulate decision-based sparse attack refinement as online reinforcement learning over stable policy–granularity macro-actions. This abstraction avoids attaching persistent Q-values to temporary support groups and makes cross-decision and cross-image replay meaningful.

  • We develop a support-relative, dynamically repartitioned executor that integrates three complementary restoration policies: perturbation-ascending, magnitude-aware, and outcome-memory. Through hard-label verification and a commit-or-rollback execution scheme, this executor monotonically reduces the support while strictly preserving adversarial feasibility.

  • We provide matched causal evidence for the learning component. Frozen fixed-probe evaluation, state-blind and state-shuffled controls, random and fixed schedulers, lifecycle controls, and component ablations distinguish learned state-conditioned scheduling from executor strength and favorable initialization.

  • We evaluate targeted and untargeted attacks on CIFAR-10 and ImageNet with ResNet50 and Vision Transformer (ViT) victims. Under an oracle-matched top-1-label protocol, RLGPA achieves improved Query–Sparsity and ASR–Sparsity performance relative to comparable decision-based sparse attacks.

Related Work

Decision-Based Black-Box Attacks

Hard-label attacks observe only the top-1 decision. Boundary Attack introduced random walks along the decision boundary [11]; HopSkipJump improved this process with geometric steps and binary search [12], while Yan et al. [13] learned query placement with reinforcement learning. Other methods construct continuous boundary-distance objectives: Ilyas et al. [14] estimated a query-limited surrogate, Opt-attack minimized distance to the boundary [15], and Sign-OPT and Sign-OPT+ improved zeroth-order sign optimization [16, 17]. AdvViT further exploits transformer structure for efficient black-box attacks [8].

Sparse Adversarial Attacks

Sparse attacks restrict nonzero perturbations to a small L0L_0 support, directly modeling settings in which only a limited number of input coordinates can be changed.

Under hard-label feedback, Pointwise greedily restores coordinates while preserving adversarial feasibility [10], whereas SparseEvo evolves support masks and performs strongly on CNN and transformer victims [9]. Both reduce an existing adversarial support using top-1 queries; their main difference is the restoration controller.

Richer score-based oracles support Sparse-RS random search [18], Bayesian sparsity search in BruSLeAttack [19], and joint sparsity–magnitude optimization in SA-MOO [20]. Related score-based attacks include bandit/prior-guided gradient estimation [21, 22], SimBA [23], Square Attack [24], and the one-pixel attack [25]. Because a score vector contains more information than a top-1 label, these methods are relevant adjacent work but not oracle-matched query baselines.

White-box PGD0_0 [26] uses iterative magnitude pruning, while σ\sigma-zero [27] smooths sparse projection. They provide ASR–Sparsity references but not Query–Sparsity baselines because they use gradients rather than victim queries. Their broader lineage includes L-BFGS [3], FGSM [28], JSMA [29], DeepFool [30], C&W [31], and PGD [32]; transfer attacks instead craft examples on a surrogate [33].

Reinforcement Learning for Query Planning

Unlike gradient-based FGSM, PGD, and C&W [28, 31, 32], RL can schedule black-box queries from sequential feedback. Prior work learned query placement [13] or optimized adversarial-patch location and perturbation [34]; other black-box optimizers include NES [14] and AutoZOOM [35]. RLGPA instead uses standard DQN, Double-DQN, and Dueling components [36, 37, 38] to schedule stable support-reduction operators online. Its distinction is therefore the state-conditioned action abstraction, not a new RL backbone or a claim of broad policy generalization [39, 40].

Method

RLGPA formulates decision-based sparse attack as online, query-bounded support reduction. A compact state-conditioned planner selects a restoration policy and relative granularity, while PSSE executes and verifies every restoration; the following subsections define the objective and the resulting closed loop.

Problem Formulation

Let f:[0,1]C×H×W→{1,…,K}f : [0,1]^{C \times H \times W} \to\{1,\ldots,K\} return only the top-1 class. For an image x\mathbf{x} with y=f(x)y=f(\mathbf{x}), the untargeted and targeted feasibility predicates Au\mathcal{A}_u and At\mathcal{A}_t for a candidate image z\mathbf{z} are:

Au(z)=I[f(z)≠y],At(z)=I[f(z)=y∗],(1)\mathcal{A}_u(\mathbf{z}) = \mathbb{I}[f(\mathbf{z}) \ne y], \qquad\mathcal{A}_t(\mathbf{z}) = \mathbb{I}[f(\mathbf{z}) = y^\ast], \tag*{(1)}

where I[⋅]\mathbb{I}[\cdot] is the indicator function and y∗≠yy^\ast\ne y is the prescribed target label.

RLGPA measures support over scalar tensor coordinates:

Ich={(c,h,w):c∈[C],h∈[H],w∈[W]},\mathcal{I}_{\mathrm{ch}} = \{(c,h,w) : c \in[C], h \in[H], w \in[W]\},
Ω(z,x)={i∈Ich:zi≠xi},\Omega(\mathbf{z},\mathbf{x}) = \{i \in\mathcal{I}_{\mathrm{ch}} : z_i \ne x_i\},
L(z,x)=∣Ω(z,x)∣,L(\mathbf{z},\mathbf{x}) = |\Omega(\mathbf{z},\mathbf{x})|,
s(z,x)=L(z,x)/(CHW),(2)s(\mathbf{z},\mathbf{x}) = L(\mathbf{z},\mathbf{x})/(CHW), \tag*{(2)}

where [n]={1,…,n}[n] = \{1,\ldots,n\}, i=(c,h,w)i=(c,h,w) indexes one scalar entry, xix_i and ziz_i are the corresponding values, Ω\Omega is the active support, LL its cardinality, and ss normalized sparsity. If all CC channels share a spatial mask of size LpixL_{\mathrm{pix}}, then L=CLpixL = CL_{\mathrm{pix}} and s=Lpix/(HW)s = L_{\mathrm{pix}}/(HW), so channel-coordinate and spatial-pixel representations yield the same normalized sparsity.

Starting from a feasible adversarial image z0\mathbf{z}_0, RLGPA restores coordinates rather than estimating new amplitudes. Let Ω0=Ω(z0,x)\Omega_0 = \Omega(\mathbf{z}_0,\mathbf{x}) and r∈{0,1}∣Ω0∣\mathbf{r} \in\{0,1\}^{|\Omega_0|} be its initial support and a binary retention vector over that support. The induced candidate is

zi(r)={xi+ri(z0,i−xi),i∈Ω0,xi,i∉Ω0,(3)z_i(\mathbf{r}) = \begin{cases} x_i + r_i(z_{0,i} - x_i), & i \in\Omega_0, \\ x_i, & i \notin\Omega_0, \end{cases} \tag*{(3)}

where zi(r)z_i(\mathbf{r}) is coordinate ii of z(r)z(\mathbf{r}), z0,iz_{0,i} and xix_i are its initial adversarial and clean values, and ri=1r_i = 1 retains whereas ri=0r_i = 0 restores the coordinate. Coordinates outside Ω0\Omega_0 already equal xx. The query-bounded restoration problem is

min⁡r∈{0,1}∣Ω0∣∥r∥0s.t.A(z(r))=1,Q≤B,(4)\min_{\mathbf{r}\in\{0,1\}^{|\Omega_0|}} \|\mathbf{r}\|_0 \quad\text{s.t.} \quad A(z(\mathbf{r})) = 1,\quad Q \le B, \tag*{(4)}

where ∥r∥0\|\mathbf{r}\|_0 counts retained coordinates, QQ is the cumulative number of top-1 victim queries, and BB is the query budget. Each candidate needs one hard-label query, including the initial feasibility check Q0=1Q_0 = 1. The 2∣Ω0∣2^{|\Omega_0|} restoration search is a restricted NP-hard minimum-L0L_0 problem [9]; RLGPA is a query-efficient heuristic, not a global optimizer.

RLGPA Framework

Figure 1 summarizes the closed loop. A compact state records support progress, remaining budget, and recent operator outcomes; a masked Dueling Double DQN selects a policy–scale macro-action; PSSE rebuilds and tests restoration groups; and the observed support reduction and query cost update the state and planner. The policy controls group construction and ordering, while the scale controls relative granularity. The planner therefore schedules stable operator semantics rather than pixel identities, and every accepted restoration is independently verified by the hard-label oracle.

Figure 1. Overview of RLGPA. The planner selects a policy–scale action from the current attack state, PSSE performs hard-label-verified support restoration, and the observed support reduction and query cost are returned for online updating.

Attack-State Representation

The state describes search progress rather than raw pixels. Let L0=L(z0,x)L_0 = L(z_0, x) and Lt=L(zt,x)L_t = L(z_t, x) be the initial and current support sizes, QtQ_t the cumulative queries before decision tt, HtH_t the number of consecutive preceding zero-gain decisions, and N^t\widehat{N}_t the group-count descriptor carried from the preceding decision. At t=0t = 0, N^t\widehat{N}_t is initialized from the clipped initial partition; subsequently it is updated by (24). The normalized progress variables are

ℓt=Ltmax⁡(1,L0),νt=N^tmax⁡(1,Lt),ϱt=B−QtB,(5)\ell_t = \frac{L_t}{\max(1,L_0)},\quad \nu_t = \frac{\widehat{N}_t}{\max(1,L_t)},\quad \varrho_t = \frac{B-Q_t}{B}, \tag*{(5)}

where ℓt\ell_t, νt\nu_t, and ϱt\varrho_t are the remaining-support, carried-group-density, and remaining-budget ratios, and max⁡(1,⋅)\max(1,\cdot) prevents division by zero. The continuous feature vector is

ξt=[ℓt, νt, min⁡(1,Ht/5), clip⁡(ζt−1,0,1), clip⁡(αt−1,0,1), clip⁡(ϱt,0,1)],(6)\xi_t = \left[\ell_t,\ \nu_t,\ \min(1,H_t/5),\ \operatorname{clip}(\zeta_{t-1},0,1),\ \operatorname{clip}(\alpha_{t-1},0,1),\ \operatorname{clip}(\varrho_t,0,1)\right], \tag*{(6)}

where ξt∈R6\xi_t \in\mathbb{R}^6, ζt−1=ΔLt−1/max⁡(1,Lt−1)\zeta_{t-1} = \Delta L_{t-1}/\max(1,L_{t-1}) is the preceding relative support reduction, ΔLt−1=Lt−1−Lt\Delta L_{t-1} = L_{t-1} - L_t, αt−1\alpha_{t-1} is the preceding acceptance ratio, and clip⁡(v,0,1)=min⁡(1,max⁡(0,v))\operatorname{clip}(v,0,1) = \min(1,\max(0,v)); initially ζ−1=α−1=0\zeta_{-1} = \alpha_{-1} = 0. The categorical vector ct∈{0,1}21c_t \in\{0,1\}^{21} concatenates one-hot bins for: phase ϕt\phi_t, which is early for ℓt>0.35\ell_t > 0.35, middle for 0.08<ℓt≤0.350.08 < \ell_t \le0.35, and late otherwise; granularity over [0,0.25)[0,0.25), [0.25,0.75)[0.25,0.75), [0.75,0.95)[0.75,0.95), and [0.95,1][0.95,1] of νt\nu_t; three bins each for stall Ht∈{0,1,≥2}H_t \in\{0,1, \ge2\}, gain ζt−1\zeta_{t-1} at 0 and 0.05, acceptance αt−1\alpha_{t-1} at 0 and 0.25, and budget ϱt\varrho_t at 0.15 and 0.5; plus a binary legacy-safety flag fixed off in the official configuration.

Let Wt\mathcal{W}_t contain the latest W=8W = 8 within-image outcomes and Wt(a)={τ∈Wt:aτ=a}\mathcal{W}_t(a) = \{\tau\in\mathcal{W}_t : a_\tau= a\} the subset generated by action aa. Its recent gain efficiency and hit rate are

et(a)=min⁡(1,∑τ∈Wt(a)ΔLτmax⁡(1,∑τ∈Wt(a)uτ)),(7)e_t(a) = \min\left(1,\frac{\sum_{\tau\in\mathcal{W}_t(a)}\Delta L_\tau}{\max(1,\sum_{\tau\in\mathcal{W}_t(a)}u_\tau)}\right), \tag*{(7)}
ht(a)=∑τ∈Wt(a)I[ΔLτ>0]max⁡(1,∣Wt(a)∣),h_t(a) = \frac{\sum_{\tau\in\mathcal{W}_t(a)} \mathbb{I}[\Delta L_\tau> 0]}{\max(1,|\mathcal{W}_t(a)|)},

where τ\tau indexes a stored decision, ΔLτ\Delta L_\tau and uτu_\tau are its support reduction and query use, et(a)e_t(a) is clipped accumulated gain per query, and ht(a)h_t(a) its positive-outcome fraction; both are zero for unseen actions. Mean per-decision efficiency is

eˉt(a)=1max⁡(1,∣Wt(a)∣)∑τ∈Wt(a)ΔLτmax⁡(1,uτ),(8)\bar{e}_t(a)=\frac{1}{\max(1,|\mathcal{W}_t(a)|)}\sum_{\tau\in\mathcal{W}_t(a)}\frac{\Delta L_\tau}{\max(1,u_\tau)}, \tag*{(8)}

where eˉt(a)=0\bar{e}_t(a)=0 when Wt(a)\mathcal{W}_t(a) is empty. The vector ot∈{0,1}M+1\mathbf{o}_t\in\{0,1\}^{M+1} marks arg max⁡aeˉt(a)\operatorname{arg\,max}_a\bar{e}_t(a) among actions with positive accumulated gain, with an extra “none” slot otherwise. Let μt∈{0,1}M\boldsymbol{\mu}_t\in\{0,1\}^M be the valid-action mask, with μt(a)=1\mu_t(a)=1 iff action aa may be selected. The complete state is

st=concat⁡(ct,ot,ξt,{et(a),ht(a)}a=1M,μt),\mathbf{s}_t=\operatorname{concat}(\mathbf{c}_t,\mathbf{o}_t,\boldsymbol{\xi}_t,\{e_t(a),h_t(a)\}_{a=1}^{M},\boldsymbol{\mu}_t),
ds=21+(M+1)+6+2M+M=28+4M,(9)d_s=21+(M+1)+6+2M+M=28+4M, \tag*{(9)}

where MM is the action count, {et(a),ht(a)}a=1M\{e_t(a),h_t(a)\}_{a=1}^{M} concatenates both statistics for every action, and dsd_s is the state dimension. With M=7M=7, ds=56d_s=56. Actions with κ>1\kappa>1 are masked when νt≥0.95\nu_t\geq0.95, i.e., at one-coordinate granularity. Histories and coordinate memories reset per image, while declared planner weights and replay may persist. Thus the state schedules support-reduction operators but contains neither support geometry nor semantic pixel identities.

Online RL-Based Macro-Action Planner

RLGPA models operator scheduling as the finite-horizon discounted process P=(S,M,P,r,γ)\mathcal{P}=(\mathcal{S},\mathcal{M},P,r,\gamma), where S\mathcal{S}, M\mathcal{M}, P(st+1∣st,at)P(s_{t+1}\mid s_t,a_t), rr, and γ∈[0,1)\gamma\in[0,1) are the scheduler-state space, macro-action set, executor-induced transition, reward, and discount factor. Because sts_t omits image geometry, this is an observable scheduling approximation rather than an exact Markov claim. Each action is

at=(pt,κt)∈M,pt∈{Primary,Safe,Memory},(10)a_t=(p_t,\kappa_t)\in\mathcal{M},\quad p_t\in\{\mathrm{Primary},\mathrm{Safe},\mathrm{Memory}\}, \tag*{(10)}

where ata_t is the decision at step tt, ptp_t selects an executor, and κt>0\kappa_t>0 its relative scale. The seven coordinate-independent policy–scale pairs in Table I retain their meanings after repartition and across images.

ActionExecutorOrderingκ\kappa
Coarse PrimaryPrimaryperturbation ascending0.5
Base PrimaryPrimaryperturbation ascending1.0
Coarse SafeSafemean magnitude descending0.5
Base SafeSafemean magnitude descending1.0
Fine SafeSafemean magnitude descending2.0
Base MemoryMemoryrestoration memory descending1.0
Fine MemoryMemoryrestoration memory descending2.0

Table I. Canonical RLGPA macro-actions. Policy–scale semantics remain fixed when the current support is repartitioned.

The masked Dueling Double DQN decomposes action value as

Qθ(s,a)=Vθ(s)+Aθ(s,a)−1M∑a′=1MAθ(s,a′),(11)Q_\theta(s,a)=V_\theta(s)+A_\theta(s,a)-\frac{1}{M}\sum_{a'=1}^{M}A_\theta(s,a'), \tag*{(11)}

where Qθ(s,a)Q_\theta(s,a) is the estimated return, θ\theta the online parameters, Vθ(s)V_\theta(s) and Aθ(s,a)A_\theta(s,a) the value and advantage streams, and a′a' indexes all MM actions. An ϵ\epsilon-greedy policy samples only Mt={a∈M:μt(a)=1}\mathcal{M}_t=\{a\in\mathcal{M}:\mu_t(a)=1\}, with invalid values masked to −∞-\infty. For terminal flag dtd_t, the Double-DQN update is

at⋆=arg max⁡a∈Mt+1 Qθ(st+1,a),(12)a_t^\star=\underset{a\in\mathcal{M}_{t+1}}{\operatorname{arg\,max}}\ Q_\theta(s_{t+1},a), \tag*{(12)}
yt=rt+γ(1−dt)Qθˉ(st+1,at⋆),(13)y_t=r_t+\gamma(1-d_t)Q_{\bar{\theta}}(s_{t+1},a_t^\star), \tag*{(13)}
L(θ)=ED[Huber⁡(Qθ(st,at)−yt)],(14)L(\theta)=\mathbb{E}_{D}\left[\operatorname{Huber}(Q_\theta(s_t,a_t)-y_t)\right], \tag*{(14)}

where Mt+1\mathcal{M}_{t+1} is the next valid set, at⋆a_t^\star its online-network maximizer, rtr_t the observed reward, yty_t the target, θˉ\bar{\theta} the target-network parameters, DD replay memory, and Huber the smooth-L1L_1 loss. The stored next mask defines Mt+1\mathcal{M}_{t+1}.

dt∈{0,1}d_t\in\{0,1\} removes bootstrapping at terminal transitions and image boundaries. Both networks use a 128–128 ReLU trunk and separate 64-unit heads. Adam uses learning rate 10−310^{-3}, γ=0.8\gamma=0.8, batch size 64, replay capacity 20,000, warm-up 128, gradient clipping 5, and target synchronization every 250 updates. Exploration decays 0.15 →\to 0.02 by factor 0.995 per decision and resets per image. Continual-online evaluation preserves weights and replay; frozen evaluation disables exploration and all learning-state mutation, separating executor capability from policy learning.

Policy-Scale Support Executor

PSSE instantiates at=(pt,κt)a_t=(p_t,\kappa_t) on the verified incumbent zt\mathbf{z}_t, whose active support and size are Ωt=Ω(zt,x)\Omega_t=\Omega(\mathbf{z}_t,\mathbf{x}) and Lt=L(zt,x)=∣Ωt∣L_t=L(\mathbf{z}_t,\mathbf{x})=|\Omega_t|. Given base erase ratio ρ>0\rho>0, it computes

ηt=ρ/κt,\eta_t=\rho/\kappa_t,
gt=min⁡(Lt,max⁡(gmin⁡,⌊Ltηt⌋)),g_t=\min(L_t,\max(g_{\min},\lfloor L_t\eta_t\rfloor)),
Jt=⌈Lt/gt⌉,(15)J_t=\lceil L_t/g_t\rceil, \tag*{(15)}

where ηt\eta_t, gtg_t, and JtJ_t are the requested support fraction per group, integer target group size, and group count; gmin⁡g_{\min} is the size lower bound and ⌈⋅⌉\lceil\cdot\rceil the ceiling operator. We use ρ=0.002\rho=0.002, gmin⁡=1g_{\min}=1, and κt∈{0.5,1,2}\kappa_t\in\{0.5,1,2\} for coarse, base, and fine scales. The realized ratio η^t=gt/Lt\hat{\eta}_t=g_t/L_t may differ from ηt=ρ/κt\eta_t=\rho/\kappa_t because of integer clipping.

Let gtlo=⌊Lt/Jt⌋g_t^{\mathrm{lo}}=\lfloor L_t/J_t\rfloor be the smaller balanced size and Rtbal=Lt−JtgtloR_t^{\mathrm{bal}}=L_t-J_tg_t^{\mathrm{lo}} the number of groups receiving one extra coordinate. The partition {Gt,j}j=1Jt\{G_{t,j}\}_{j=1}^{J_t} satisfies

∣Gt,j∣={gtlo+1,1≤j≤Rtbal,gtlo,Rtbal<j≤Jt,(16)|G_{t,j}|= \begin{cases} g_t^{\mathrm{lo}}+1, & 1\leq j\leq R_t^{\mathrm{bal}},\\ g_t^{\mathrm{lo}}, & R_t^{\mathrm{bal}}<j\leq J_t, \end{cases} \tag*{(16)}
Gt,j∩Gt,k=∅ (j≠k),⋃j=1JtGt,j=Ωt,G_{t,j}\cap G_{t,k}=\varnothing\ (j\ne k),\qquad\bigcup_{j=1}^{J_t}G_{t,j}=\Omega_t,

where ⌊⋅⌋\lfloor\cdot\rfloor is the floor operator, Gt,j⊆ΩtG_{t,j}\subseteq\Omega_t is group jj, and j,k∈{1,…,Jt}j,k\in\{1,\ldots,J_t\}. The groups are exhaustive, disjoint, and directly generated by PSSE. Rebuilding them from committed support before every macro-action preserves policy–scale semantics without assigning Q-values to temporary group indices.

Policy ptp_t controls group construction and order. For i∈Ωti\in\Omega_t, let ωi=∣zt,i−xi∣\omega_i=|z_{t,i}-x_i| be perturbation magnitude. Primary shuffles ties, sorts coordinates by increasing ωi\omega_i, and chunks the sequence. Safe randomly groups coordinates and ranks groups by decreasing

Smag(G)=1∣G∣∑i∈Gωi,(17)S_{\mathrm{mag}}(G)=\frac{1}{|G|}\sum_{i\in G}\omega_i, \tag*{(17)}

where G⊆ΩtG\subseteq\Omega_t, ∣G∣|G| is its size, and Smag(G)S_{\mathrm{mag}}(G) its mean magnitude. Memory maintains image-local accepted and rejected group attributions (ni+,ni−)(n_i^+,n_i^-) and ranks groups by

mi=ni++1ni++ni−+2,Smem(G)=1∣G∣∑i∈Gmi,(18)m_i=\frac{n_i^+ + 1}{n_i^+ + n_i^- + 2},\qquad S_{\mathrm{mem}}(G)=\frac{1}{|G|}\sum_{i\in G}m_i, \tag*{(18)}

where ni+n_i^+ and ni−n_i^- count accepted and rejected tests containing ii, mi∈(0,1)m_i\in(0,1) is the Beta(1,1)(1,1)-smoothed attribution, and Smem(G)S_{\mathrm{mem}}(G) its group mean. Testing GG increments ni+n_i^+ for every i∈Gi\in G on acceptance and ni−n_i^- otherwise. These per-image executor statistics are ordering scores, not identified coordinate-level causal probabilities or cross-image DQN state.

Set zt(0)=ztz_t^{(0)}=z_t. For group Gt,jG_{t,j}, the restoration operator and candidate are

[RG(z;x)]i={xi,i∈G,zi,i∉G,z~t(j)=RGt,j(zt(j−1);x),(19)[\mathcal{R}_G(\mathbf{z};\mathbf{x})]_i= \begin{cases} x_i, & i\in G,\\ z_i, & i\notin G, \end{cases} \qquad \tilde{\mathbf{z}}_t^{(j)}=\mathcal{R}_{G_{t,j}}(\mathbf{z}_t^{(j-1)};\mathbf{x}), \tag*{(19)}

where RG(z;x)\mathcal{R}_G(\mathbf{z};\mathbf{x}) copies xix_i into scalar coordinates i∈Gi\in G and retains ziz_i elsewhere, zt(j−1)\mathbf{z}_t^{(j-1)} is the latest verified incumbent, and z~t(j)\tilde{\mathbf{z}}_t^{(j)} is the unverified candidate. One victim query returns χt,j=A(z~t(j))∈{0,1}\chi_{t,j}=\mathcal{A}(\tilde{\mathbf{z}}_t^{(j)})\in\{0,1\}, after which PSSE applies

zt(j)={z~t(j),χt,j=1,zt(j−1),χt,j=0,(20)\mathbf{z}_t^{(j)}= \begin{cases} \tilde{\mathbf{z}}_t^{(j)}, & \chi_{t,j}=1,\\ \mathbf{z}_t^{(j-1)}, & \chi_{t,j}=0, \end{cases} \tag*{(20)}
L(zt(j),x)=L(zt(j−1),x)−χt,j∣Gt,j∣,L(\mathbf{z}_t^{(j)},\mathbf{x})=L(\mathbf{z}_t^{(j-1)},\mathbf{x})-\chi_{t,j}|G_{t,j}|,

where zt(j)\mathbf{z}_t^{(j)} is the verified incumbent after test jj; χt,j=1\chi_{t,j}=1 commits the candidate and χt,j=0\chi_{t,j}=0 rolls it back. Since tested groups are active and disjoint, every incumbent remains feasible and support never increases. A macro-action executes

ut=min⁡(qc,Jt,B−Qt),qc=32,(21)u_t=\min(q_c,J_t,B-Q_t),\qquad q_c=32, \tag*{(21)}

tests, where utu_t is both the number of tested groups and consumed victim queries, qc=32q_c=32 is the per-decision cap, JtJ_t the available group count, and B−QtB-Q_t the remaining budget. It returns

zt+1=zt(ut),\mathbf{z}_{t+1}=\mathbf{z}_t^{(u_t)},
ΔLt=Lt−Lt+1=∑j=1utχt,j∣Gt,j∣,\Delta L_t=L_t-L_{t+1}=\sum_{j=1}^{u_t}\chi_{t,j}|G_{t,j}|,
αt=1max⁡(1,ut)∑j=1utχt,j,(22)\alpha_t=\frac{1}{\max(1,u_t)}\sum_{j=1}^{u_t}\chi_{t,j}, \tag*{(22)}

where zt+1=zt(ut)\mathbf{z}_{t+1}=\mathbf{z}_t^{(u_t)} is the returned incumbent, Lt+1=L(zt+1,x)L_{t+1}=L(\mathbf{z}_{t+1},\mathbf{x}), ΔLt\Delta L_t the accepted support reduction, and αt\alpha_t the accepted-test ratio. Thus PSSE performs feasibility-preserving support reduction; RL only schedules its executor and scale.

Algorithm 1 RLGPA continual-online support search

Figure 1 (PDF p. 5).

Query-Aware Feedback

PSSE returns (ΔLt,ut,αt)(\Delta L_t,u_t,\alpha_t), acceptance bits {χt,j}j=1ut\{\chi_{t,j}\}_{j=1}^{u_t}, and updated coordinate memory. Let gˉt=Lt/Jt\bar{g}_t=L_t/J_t be the mean planned group size, HtH_t the pre-action stall length, and ϕt\phi_t the phase determined by ℓt=Lt/L0\ell_t=L_t/L_0. The reward is

rt=wϕtΔLtmax⁡(1,utgˉt)+βtailI[ΔLt>0∧ϕt=late]+βstallI[ΔLt>0∧Ht≥2]+c0I[ΔLt=0]−λqutB,(23)r_t=w_{\phi_t}\frac{\Delta L_t}{\max(1,u_t\bar{g}_t)}+\beta_{\mathrm{tail}}\mathbb{I}[\Delta L_t>0\land\phi_t=\mathrm{late}] +\beta_{\mathrm{stall}}\mathbb{I}[\Delta L_t>0\land H_t\ge2] +c_0\mathbb{I}[\Delta L_t=0]-\lambda_q\frac{u_t}{B}, \tag*{(23)}

where rtr_t is scalar feedback, wϕtw_{\phi_t} the phase weight, βtail\beta_{\mathrm{tail}} and βstall\beta_{\mathrm{stall}} bonuses for late and post-stall progress, c0<0c_0<0 the zero-gain penalty, and λq≥0\lambda_q\ge0 the explicit query-penalty coefficient. We use (wearly,wmiddle,wlate)=(0.25,0.5,1)(w_{\mathrm{early}},w_{\mathrm{middle}},w_{\mathrm{late}})=(0.25,0.5,1), βtail=βstall=0.25\beta_{\mathrm{tail}}=\beta_{\mathrm{stall}}=0.25, c0=−0.02c_0=-0.02, and λq=0\lambda_q=0. The leading term already normalizes gain by approximate attempted support utgˉtu_t\bar{g}_t; the reward is a scale-aware surrogate, not a probability.

After updating coordinate counts and appending (at,ΔLt,ut)(a_t,\Delta L_t,u_t) to Wt\mathcal{W}_t, feedback updates

Qt+1=Qt+ut,Q_{t+1}=Q_t+u_t,
Ht+1={0,ΔLt>0,Ht+1,ΔLt=0,(24)H_{t+1}= \begin{cases} 0, & \Delta L_t>0,\\ H_t+1, & \Delta L_t=0, \end{cases} \tag*{(24)}
N^t+1=min⁡(Jt,max⁡(1,Lt+1)),\hat{N}_{t+1}=\min(J_t,\max(1,L_{t+1})),

where Qt+1Q_{t+1} is the updated query count, Ht+1H_{t+1} resets after positive gain and otherwise increments, and N^t+1\hat{N}_{t+1} carries JtJ_t clipped to the nonzero range supported by Lt+1L_{t+1}. The encoder then recomputes st+1s_{t+1} and valid-action mask μt+1\mu_{t+1}, producing

τt=(st,at,rt,st+1,dt,μt+1),(25)\tau_t=(s_t,a_t,r_t,s_{t+1},d_t,\mu_{t+1}), \tag*{(25)}

where τt\tau_t contains current state sts_t, action ata_t, reward rtr_t, next state st+1s_{t+1}, terminal flag dtd_t, and next mask μt+1\mu_{t+1}. We set dt=1d_t=1 at Qt+1≥BQ_{t+1}\ge B, Lt+1=0L_{t+1}=0, or the image boundary, and zero otherwise. After warm-up, stored transitions update DDQN. The shaped reward is only an online signal: its necessity is not claimed, and useful state-conditioned learning is assessed against frozen, untrained, random, fixed, state-blind, and state-shuffled controls. Algorithm 1 summarizes the loop.

Experiments and Evaluation

Experimental Setup

a) Datasets and target models: We evaluate CIFAR-10 with ResNet18, and ImageNet-1k with ResNet50 and ViT. The cross-method evaluation uses 100 CIFAR-10 images and 200 ImageNet images per attack mode. The query budgets of Targeted and untargeted attacks are 2,000 and 500 on CIFAR-10, and 20,000 and 5,000 on ImageNet, respectively.

b) Baselines: Pointwise and SparseEvo are the numerical external baselines because they share RLGPA’s decision-only oracle and sparse-support objective. Score-based sparse attacks are excluded from numerical query comparison: a score query returns substantially richer information than a top-1-label query, so treating both as an equal unit would not constitute an oracle-matched efficiency comparison. PGD0_0 and σ\sigma-zero are included only as white-box ASR–Sparsity references. The untargeted σ\sigma-zero curves follow its published threat model; for completeness, the targeted panels use our target-class-margin extension of the same gradient-based optimizer and are not presented as an official targeted σ\sigma-zero result. Neither white-box method appears in Query–Sparsity curves or query-efficiency rankings. For a fair comparison, all numerically compared decision-based attacks use the same model preprocessing and success denominator within a setting.

c) Metrics: On the one hand, we evaluate query efficiency using Query–Sparsity, which reports the median normalized support over hard-label queries together with the first and third quartiles; only oracle-matched decision-based methods are included in this view. On the other hand, we measure attack strength using ASR–Sparsity, defined as the percentage of evaluation images that remain adversarial after reaching a given sparsity threshold. White-box references appear only in the ASR–Sparsity view and are visually separated from black-box attacks. In addition, we report the median, mean, and 90th-percentile L0L_0 of the final perturbations. For paired ablations, we use identical manifests and starting points across configurations, and analyze the results with win/tie/loss counts and Wilcoxon signed-rank tests.

d) RLGPA configuration: The seven-action relative planner uses ρ=0.002\rho= 0.002, query chunks of 32, discount γ=0.8\gamma= 0.8, initial/minimum exploration 0.15/0.02, and exploration decay 0.995. The Dueling network has two 128-unit hidden layers. Replay capacity is 20,000, batch size is 64, warmup is 128 transitions, learning rate is 10−310^{-3}, the target network is synchronized every 250 updates, and one optimizer step is taken per eligible decision.

Main Comparison

Table II summarizes the final-budget results under the matched top-1-label oracle. We use a strict threshold of 0.01 for CIFAR-10 targeted attacks, 0.005 for ImageNet targeted attacks, and 0.001 for untargeted attacks. Full threshold curves are given in Figure 2; the conclusion does not depend on a single operating point. PGD0_0 and σ\sigma-zero are reference curves for sparse robustness only and are excluded from the query-efficiency claim.

SettingQueryMethodsCIFAR10 (ResNet18)QueryImageNet (ResNet50)
Median[email protected]Median[email protected]
Untargetedσ\sigma-zero0.0013100%0.0001100%
PGD0_00.0068100%0.0005100%
200Pointwise0.005991.0%20000.002468.0%
SparseEvo0.021585.0%0.002687.0%
RLGPA0.003393.0%0.000496.0%
500Pointwise0.005996.0%50000.001680.0%
SparseEvo0.021586.0%0.002387.5%
RLGPA0.0026100.0%0.000499.5%
Targetedσ\sigma-zero0.0036100%0.0009100%
PGD0_00.0156100%0.003797.0%
1000Pointwise0.42240.0%100000.74640.0%
SparseEvo0.021090.0%0.027520.0%
RLGPA0.086924.0%0.011645.5%
2000Pointwise0.223611.0%200000.65640.0%
SparseEvo0.018195.0%0.007071.5%
RLGPA0.008599.0%0.003488.5%

Table II. Median sparsity and ASR at different query budgets. A comprehensive comparison among different attacks (σ\sigma-zero, PGD0_0, Pointwise, SparseEvo, and RLGPA) on small and large scale balance datasets. The two white-box rows are reported at their converged distortion for reference only: their optimization cost is not a sequence of victim queries, so they are excluded from every query-efficiency comparison.

Figure 2. Comparison of RLGPA on CIFAR-10 (ResNet18) and ImageNet (ResNet50 and ViT). Rows correspond to dataset–model pairs, while columns present untargeted/targeted ASR–Sparsity and Query–Sparsity results. PGD0\mathrm{PGD}_0 and σ\sigma-zero are white-box references included only in the ASR–Sparsity panels.

On CIFAR-10, RLGPA achieves lower median sparsity and higher ASR than Pointwise and SparseEvo at both untargeted budgets. In the targeted setting, Pointwise largely fails,

SparseEvo is the strongest baseline, and RLGPA is weaker at the half budget but clearly best at the full budget (median sparsity 0.0085, ASR 99.0%). This pattern is consistent with the online-learning characterization in Section IV-D: the shared planner improves over the stream, so its advantage concentrates at larger budgets.

On ImageNet, the same ordering holds. Untargeted median sparsity remains at 0.0004 with 96.0% and 99.5% ASR, and targeted median sparsity improves from 0.0116 to 0.0034 with ASR rising from 45.5% to 88.5% as the budget grows. Notably, RLGPA attains sparsity levels comparable to the white-box methods σ\sigma-zero and PGD0\mathrm{PGD}_0, despite using only hard-label feedback.

Table III further reports ImageNet results separately for ResNet50 and ViT at sparsity 0.001 and 0.005. Under both untargeted and targeted settings, RLGPA leads at strict sparsity and full budget on both architectures. SparseEvo retains an advantage only in the lowest-budget, loose-threshold ViT cell. The transformer result confirms that the policy–executor decomposition is not tied to convolutional victims.

SettingQueryMethodsResNet50ViT
0.0010.0050.0010.005
Untargetedσ\sigma-zero100%100%100%100%
PGD0_074.0%100.0%46.5%91.5%
2000SparseEvo21.0%68.5%27.0%74.0%
RLGPA76.5%92.0%32.5%51.5%
5000SparseEvo21.5%72.0%30.0%93.0%
RLGPA89.0%99.5%63.0%98.0%
Targetedσ\sigma-zero60.5%100%57.5%98.0%
PGD0_01.0%73.5%1.5%41.5%
10000SparseEvo0.0%11.5%0.5%14.0%
RLGPA3.5%27.0%3.5%49.0%
20000SparseEvo0.5%29.0%0.5%15.5%
RLGPA3.5%75.5%3.5%73.0%

Table III. ASR of ResNet50 and ViT under attacks at different query budgets and sparsity thresholds. A comprehensive comparison among different attacks (σ\sigma-zero, PGD0_0, SparseEvo, and RLGPA) on small and large scale balanced evaluation sets from ImageNet.

Figure 2 confirms that RLGPA leads in the low-sparsity region across all three settings and throughout the budget range. White-box references appear only in the ASR–Sparsity panels and are visually separated from the black-box curves. Overall, RLGPA dominates the decision-based field at strict sparsity and full budget on both CNN and transformer victims, conceding only the lowest-budget, loose-threshold ViT cells to SparseEvo.

Qualitative Evolution Across Queries

Section IV-B quantitatively demonstrates that the RLGPA attack achieves strong performance on both CNN and Transformer victim models. By contrast, Figures 3 and 4 qualitatively illustrate the attack effectiveness of different methods by showing how individual targeted adversarial examples evolve with the query budget.

Visual evolution of targeted adversarial examples generated by RLGPA on ViT and ResNet50 on ImageNet

Figure 4. Visual evolution of targeted adversarial examples generated by RLGPA on ViT and ResNet50 on ImageNet. Two source–target pairs are shown. Query budgets: 1,000, 5,000, 10,000, 15,000, and 20,000. Target-class reference (left), source image (right); enlarged crops highlight residual perturbations at the final budget.

Figure 3 shows that both attacks progressively restore the visual structure of the source image while retaining targeted feasibility. On this example, RLGPA contracts the diffuse perturbation more rapidly at the early budgets and reaches a lower final sparsity at 20,000 queries. The perturbation maps make the support contraction visible rather than relying only on the scalar sparsity values.

Visual comparison of targeted attacks between RLGPA and SparseEvo on ImageNet

Figure 3. Visual comparison of targeted attacks between RLGPA and SparseEvo on ImageNet. Query budgets: 100, 500, 1,000, 5,000, 10,000, and 20,000. For each method, the upper row shows the adversarial image and the lower row its perturbation map with normalized sparsity. Target-class reference (left) and source image (right).

Figure 4 further illustrates the same restoration process on both a convolutional and a transformer victim. At lower budgets, the perturbation remains spatially widespread; as the query budget increases, the adversarial image progressively resembles the source image, and the residual changes become localized. The similar trends observed on ResNet50 and ViT provide a qualitative complement to the architecture-specific quantitative results in Table III.

Does the Planner Learn? Fixed-Probe Evaluation

The main curves measure continual-online attack performance but do not by themselves prove learning, because image difficulty can vary with stream position. We therefore construct four non-overlapping CIFAR-10 targeted splits: 100 attribution images, 120 adaptation images, 20 validation images, and 20 fixed probe images. Checkpoints are frozen and evaluated with ϵ=0\epsilon= 0; parameter hashes, optimizer steps, and replay sizes are checked before and after every validation/probe run. The probe split is never used for checkpoint selection, so any improvement on it reflects transfer rather than fitting to the evaluation images.

Table 4 reports the frozen performance on the fixed, disjoint 20-image probe set across different numbers of adaptation images. No probe-time parameter or replay update is allowed. At 0 adaptation images, the median L0L_0 is 165.0 and the [email protected] is 0.20. As the number of adaptation images increases, the median L0L_0 decreases steadily—reaching 23.0 at 40 adaptation images and stabilizing around 21.5 at 120 adaptation images—while [email protected] rises from 0.20 to 0.65. These results show that the planner improves on the probe set as it accumulates attack experience, without any test-time updates.

Adaptation images[email protected]MedianMeanP90
0.20165.0136.20226.2
20.4541.540.6570.6
40.6023.028.2057.4
60.5025.527.7555.7
80.5521.527.5552.0
100.6021.028.3554.1
120.6521.525.1550.2

Table 4. Frozen performance on a fixed, disjoint 20-image probe set. No probe-time parameter or replay update is allowed. Median, Mean, and P90 are for L0L_0.

To isolate this transfer effect, we select checkpoint 40 using the validation split only and compare it against checkpoint 0 on the 20 fixed probe images. All 20 probe images improve, the median paired reduction is 131 coordinates, and the Wilcoxon test gives p=1.91×10−6p = 1.91 \times10^{-6}. This improvement is accompanied by a stable evaluation state: across all 14 frozen validation/probe runs, parameter SHA256, optimizer-step count, and replay size remain unchanged. Together, these results provide the clearest evidence that prior attack experience produces reusable policy parameters rather than merely improving later images through an easier stream order.

Matched Planner Attribution

Table 5 compares planners using the same 100-image targeted manifest, starting points, executor, and 2,000-query budget. Full shared-online DQN significantly outperforms uniform random, train-disabled, and per-image-reset controls. It is not significantly better than the strongest fixed Base Memory policy or the deterministic schedule on this set. The fixed-probe result above is therefore the primary learning evidence, while this experiment identifies the relevant baselines and limits the claim.

Planner/control[email protected]MedianMeanP90pp
Full shared-online DQN.5924.535.5667.0–
Base Memory only.5725.533.6563.1.8535
Deterministic schedule.5030.533.4557.1.1117
Uniform random.4635.038.0468.5.0028
Train-disabled DQN.21122.5112.32199.1<10−15< 10^{-15}
Per-image-reset DQN.21122.5112.32199.1<10−15< 10^{-15}

Table 5. Matched planner attribution on targeted CIFAR-10. The final column is the paired Wilcoxon test against Full DQN. Median, Mean, and P90 are for L0L_0.

To further test whether the learned policy is genuinely necessary, we also examine how much of the observed performance can be attributed to the network’s initialization rather than to adaptation. Five frozen-untrained network seeds are highly unstable, with aggregate median L0=217.5±169.3L_0 = 217.5 \pm169.3; the best seed reaches median 29.0. Thus a favorable random output bias can occasionally imitate a useful fixed action preference, but it is not a reliable substitute for adaptation.

State variantASR @.01MedianMeanP90
Full state.5924.535.5667.0
No action history/effectiveness.5427.037.7771.1
No recent progress/stall.5429.038.6473.7
No phase/budget.5030.536.4171.0
Minimal legal mask.4831.546.6790.2
State-shuffled, five-seed mean.48232.845.3589.16
State-blind.4444.582.01203.4

Table VI. State ablation for the final relative planner. Median, Mean, and P90 are for L0L_0.

Variant[email protected]MedianMeanP90
Erase ratio .01.6323.029.8358.2
Full seven-action, ratio .002.5924.535.5667.0
Erase ratio .005.5925.030.7063.2
Policy DQN, fixed base scale.6225.534.6660.1
Policy DQN, random scale.5426.536.2366.1
Memory-only.5228.038.1868.4
No Memory actions.5130.079.36184.5
Erase ratio .001.2959.5119.16313.1
Fixed partition.21128.0336.591115.0
Primary-only.36173.0235.28625.1
Safe-only.03301.0343.95569.1

Table VIII. Relative granularity and executor ablation. Median, Mean, and P90 are for L0L_0.

RewardASR @.01MedianMeanP90
Support gain/query.5624.034.4668.0
Full shaped reward.5924.535.5667.0
No stall bonus.5229.039.0071.1
No tail/stall bonuses.5030.039.4274.2
No phase weights.4931.040.2972.2
No tail bonus.4731.044.0071.3

Table VII. Reward ablation on targeted CIFAR-10. Median, Mean, and P90 are for L0L_0.

LifecycleASR @.01MedianMeanP90Updates
Keep weights + replay.5924.535.5667.07936
Preadapt, frozen inference.5826.029.6060.00
Reset weights + replay per image.21122.5112.32199.1107
Keep weights, clear replay per image.20126.5173.73361.6147

Table IX. Cross-image learning lifecycle on the matched targeted attribution set. Median, Mean, and P90 are for L0L_0.

State Conditioning and Reward

tbl:VI removes groups of state features while retaining the same action space and executor. Full state significantly outperforms state-blind inference with 66/9/25 wins/ties/losses and p=3.76×10−9p = 3.76 \times10^{-9}. It also outperforms each of five state-shuffled seeds at p<0.05p < 0.05. The final relative planner therefore uses state alignment rather than learning only a global action prior.

The reward ablation in tbl:VII presents a more nuanced picture. Removing individual phase or tail terms degrades performance, yet the full shaped reward is statistically indistinguishable from a simple support-gain-per-query reward (p=.8392p = .8392). We therefore do not claim that the shaped reward is intrinsically superior.

Granularity and Executor Composition

tbl:VIII separates scale selection from executor choice. Dynamic repartition is indispensable: fixing the partition increases median L0L_0 from 24.5 to 128. Removing Memory substantially worsens the mean and tail, whereas Memory-only remains competitive in the median. Learned scale selection is not significantly better than fixed base scale or random scale. Thus the main learned contribution is state-conditioned executor scheduling, with granularity planning providing a useful shared action representation but not yet an independently significant gain.

The apparent advantage of ratio .01 over .002 on CIFAR-10 is not significant in the paired comparison (p=.0861p = .0861) and has not been repeated across CIFAR-10 training seeds. We therefore retain .002 as the common CIFAR-10/ImageNet default rather than selecting the most favorable row after observing the evaluation set. The independent three-seed ImageNet sensitivity study below further tests this fixed choice without retuning the main experiments.

Lifecycle of Online Experience

tbl:IX studies what is inherited across images. A planner adapted on 120 images and then frozen reaches median L0=26L_0 = 26 without test-time updates, close to continual online learning and far better than per-image reset. Retaining weights while clearing replay performs poorly, but it also receives only 147 optimizer updates because most single images do not reach the 128-transition warmup. This comparison therefore establishes the importance of the complete cross-image learning state but does not isolate replay-distribution effects from update count.

Mechanistic Analysis

The learned behavior agrees with the intended stage structure. Table X reports the most productive action in each phase. Coarse Primary dominates early and middle support contraction, while Base Memory is markedly more effective in the late phase. In that late phase, Base Memory obtains support gain/query 0.459, compared with 0.038 for Base Primary and 0.096 for Base Safe. Combined with the state-shuffle result, this provides a mechanism-level explanation for why state-conditioned switching improves the tail.

PhaseActionSupport gain /queryInterpretation
EarlyCoarse Primary6.970aggressive initial contraction
MiddleCoarse Primary1.884continued coarse removal
LateBase Memory0.459history-guided tail refinement

Table X. Most productive action by support-search phase.

Every reported matched ablation records zero illegal commits. The feasibility invariant is therefore preserved across planner, state, reward, granularity, and lifecycle variants.

Hyperparameter Sensitivity

We assess sensitivity to hyperparameter choice by varying one parameter at a time on targeted ResNet50, using the same 100-image stream, a 20,000-query budget, and DQN seeds 42, 123, and 3407. The official configuration (ρ=0.002\rho= 0.002, learning rate 10−310^{-3}) remains fixed; this is a post-hoc analysis, not a search that changes the reported setting. Figure 5 reports the geometric mean of the three median-sparsity trajectories with 95% confidence intervals.

ImageNet targeted hyperparameter sensitivity plots for relative erase ratio and DQN learning rate

Figure 5. ImageNet targeted hyperparameter sensitivity on ResNet50. Curves aggregate three seed-specific median-sparsity trajectories over the same 100-image stream; shaded regions denote 95% confidence intervals. The horizontal line marks the sparsity threshold 0.005 used in the main targeted comparison. Lower is better.

The relative erase ratio controls a granularity trade-off. Default ρ=0.002\rho= 0.002 reaches sparsity 0.005 at about 11.5K queries, earlier than ρ=0.001\rho= 0.001 (14.5K) and ρ=0.005\rho= 0.005 (15.5K). At 20K queries, these three converge to 0.00299, 0.00293, and 0.00352, respectively, while ρ=0.01\rho= 0.01 remains at 0.01993 and never reaches 0.005. The default is therefore chosen for fastest threshold crossing, not lowest terminal value, while avoiding the instability of overly coarse groups.

Learning-rate sensitivity is weaker. For rates from 2.5×10−42.5 \times10^{-4} to 2×10−32 \times10^{-3}, all curves reach sparsity 0.005 between 11.5K and 12K queries and finish between 0.00276 and 0.00299, with overlapping confidence bands. This eightfold range indicates that ImageNet performance is not tied to a finely tuned DQN step size, supporting 10−310^{-3} as the shared default.

Conclusion

We introduced RLGPA, an online reinforcement learning-guided granularity planning attack for decision-based sparse adversarial examples. RLGPA exposes stable executor–scale actions, converts them into support-relative groups, and dynamically rebuilds those groups around a feasibility-preserving adversarial incumbent. A shared Dueling Double DQN learns from hard-label support gains during the attack stream and can be frozen for update-free evaluation. Under the matched top-1-label oracle, results on CIFAR-10 and ImageNet show strong improvements over the directly comparable Pointwise and SparseEvo attacks in the low-sparsity region. Matched controls establish that the policy learns reusable state-conditioned scheduling, while ablations identify dynamic repartition and

Memory-guided late refinement as the principal mechanisms. The evidence also shows where the current method does not yet win: learned scale selection and shaped reward are not significantly superior to simpler alternatives. This combination of attack performance, causal attribution, and explicit limitations provides a reproducible basis for studying online reinforcement learning in query-bounded support search.

References

  1. [1]Z. Yu, X. Liu, Y.-M. Cheung, L. Zhu, X. Xu, and N. Wang, “Fpad: Fuzzy-prototype-guided adversarial attack and defense for deep cross-modal hashing,” IEEE Trans. Circuits Syst. Video Technol., vol. 36, no. 2, pp. 2568–2580, 2026.DOI
  2. [2]M. Xie, Y. He, Z. Qin, and M. Fang, “Retouchuaa: Unconstrained adversarial attack via realistic image retouching,” IEEE Trans. Circuits Syst. Video Technol., vol. 35, no. 3, pp. 2586–2602, 2025.DOI
  3. [3]C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” arXiv:1312.6199, 2013.arxiv.org/abs/1312.6199
  4. [4]C. Zhou, Y.-G. Wang, and G. Zhu, “Object-attentional untargeted adversarial attack,” J. Inf. Secur. Appl., vol. 81, p. 103710, 2024.
  5. [5]J. Hu, J. Zhou, Z. Yang, H. Zheng, D. He, and Y. Li, “Adaguard: Location-aware adaptive defense against adversarial patch attacks in vision transformers,” IEEE Trans. Circuits Syst. Video Technol., vol. 36, no. 10, pp. 15305–15316, 2026.DOI
  6. [6]C. Jiang, Z. Wang, M. Dong, J. Gui, L. Dong, Y. Y. Tang, and J. T.-Y. Kwok, “Gradient perturbation guidance for boosting sparse adversarial attack transferability,” IEEE Trans. Circuits Syst. Video Technol., vol. 36, no. 5, pp. 6361–6373, 2026.DOI
  7. [7]C. Zhou, Y.-G. Wang, Z.-J. Wang, and X. Kang, “Lp-norm distortion-efficient adversarial attack,” Signal Process. Image Commun., vol. 131, p. 117241, 2025.DOI
  8. [8]C. Zhou, X. Shi, and Y.-G. Wang, “Query-efficient hard-label black-box attack against vision transformers,” Appl. Soft Comput., vol. 183, p. 113686, 2025.arxiv.org/abs/2407.00389
  9. [9]V. Q. Vo, E. Abbasnejad, and D. C. Ranasinghe, “Query efficient decision based sparse attacks against black-box deep learning models,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2022.arxiv.org/abs/2202.00091
  10. [10]L. Schott, J. Rauber, M. Bethge, and W. Brendel, “Towards the first adversarially robust neural network model on mnist,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2019.arxiv.org/abs/1805.09190
  11. [11]W. Brendel, J. Rauber, and M. Bethge, “Decision-based adversarial attacks: Reliable attacks against black-box machine learning models,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2018.arxiv.org/abs/1712.04248
  12. [12]J. Chen, M. I. Jordan, and M. J. Wainwright, “Hop-skipjumpattack: A query-efficient decision-based attack,” in Proc. IEEE Symp. Secur. Privacy (S&P), 2020, pp. 1277–1294.
  13. [13]Z. Yan, Y. Guo, J. Liang, and C. Zhang, “Policy-driven attack: Learning to query for hard-label black-box adver- serial examples,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2021.
  14. [14]A. Ilyas, L. Engstrom, A. Athalye, and J. Lin, “Black-box adversarial attacks with limited queries and information,” in Proc. Int. Conf. Mach. Learn. (ICML), 2018, pp. 2137–2146.arxiv.org/abs/1804.08598
  15. [15]M. Cheng, T. Le, P.-Y. Chen, H. Zhang, J. Yi, and C.-J. Hsieh, “Query-efficient hard-label black-box attack: an optimization-based approach,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2019, pp. 1–14.arxiv.org/abs/1807.04457
  16. [16]M. Cheng, S. Singh, P. H. Chen, P.-Y. Chen, S. Liu, and C.-J. Hsieh, “Sign-opt: a query-efficient hard-label adversarial attack,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2020.
  17. [17]Y. Ran and Y.-G. Wang, “Sign-opt+: An improved sign optimization adversarial attack,” in Proc. IEEE Int. Conf. Image Process. (ICIP), 2022, pp. 461–465.DOI
  18. [18]F. Croce, M. Andriushchenko, N. D. Singh, N. Flammarion, and M. Hein, “Sparse-rs: A versatile framework for query-efficient sparse black-box adversarial attacks,” in Proc. AAAI Conf. Artif. Intell. (AAAI), vol. 36, no. 6, 2022, pp. 6437–6445.
  19. [19]Q. V. Vo, E. Abbasnejad, and D. Ranasinghe, “Brusleattack: A query-efficient score-based black-box sparse adversarial attack,” in Proc. Int. Conf. Learn. Represent. (ICLR), vol. 2024, 2024, pp. 54 462–54 499.arxiv.org/abs/2404.05311
  20. [20]P. N. Williams and K. Li, “Black-box sparse adversarial attack via multi-objective optimisation cvpr proceedings,” in Proc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR). IEEE, 2023, pp. 12 291–12 301.DOI
  21. [21]A. Ilyas, L. Engstrom, A. Athalye, and J. Lin, “Prior convictions: Black-box adversarial attacks with bandits and priors,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2018.arxiv.org/abs/1807.07978
  22. [22]A. Ilyas, L. Engstrom, and A. Madry, “Black-box adversarial attacks using evolution strategies,” arXiv:1904.04433, 2019.
  23. [23]C. Guo, J. Gardner, Y. You, A. G. Wilson, and K. Weinberger, “Simple black-box adversarial attacks,” in Proc. Int. Conf. Mach. Learn. (ICML), 2019, pp. 2484–2493.arxiv.org/abs/1905.07121
  24. [24]M. Andriushchenko, F. Croce, N. Flammarion, and M. Hein, “Square attack: A query-efficient black-box adversarial attack via random search,” in Proc. Eur. Conf. Comput. Vis. (ECCV), 2020, pp. 484–501.arxiv.org/abs/1912.00049
  25. [25]J. Su, D. V. Vargas, and K. Sakurai, “One pixel attack for fooling deep neural networks,” IEEE Trans. Evol. Comput., vol. 23, no. 5, pp. 828–841, 2019.DOI
  26. [26]F. Croce and M. Hein, “Sparse and imperceivable adversarial attacks,” in Proc. IEEE/CVF Int. Conf. Comput. Vis. (ICCV). IEEE, 2019, pp. 4723–4731.arxiv.org/abs/1909.05040
  27. [27]A. E. Cinà, F. Villani, M. Pintor, L. Schönherr, B. Biggio, and M. Pelillo, “ℓ0-zero: Gradient-based optimization of ℓ0-norm adversarial examples,” in Proc. Int. Conf. Learn. Represent. (ICLR), vol. 2025, 2025, pp. 91 199–91 211.DOI
  28. [28]I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2015.DOI
  29. [29]N. Papernot, P. McDaniel, S. Jha, M. Fredrikson, Z. B. Celik, and A. Swami, “The limitations of deep learning in adversarial settings,” in Proc. IEEE Eur. Symp. Secur. Privacy (EuroS&P). IEEE, 2016, pp. 372–387.
  30. [30]S.-M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard, “Deepfool: A simple and accurate method to fool deep neural networks,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), 2016, pp. 2574–2582.
  31. [31]N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in Proc. IEEE Symp. Secur. Privacy (S&P), 2017, pp. 39–57.arxiv.org/abs/1608.04644
  32. [32]A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” arXiv:1706.06083, 2017.arxiv.org/abs/1706.06083
  33. [33]Y. Liu, X. Chen, C. Liu, and D. Song, “Delving into transferable adversarial examples and black-box attacks,” arXiv:1611.02770, 2016.arxiv.org/abs/1611.02770
  34. [34]X. Wei, Y. Guo, J. Yu, and B. Zhang, “Simultaneously optimizing perturbations and positions for black-box adversarial patch attacks,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 45, no. 7, pp. 9041–9054, 2022.arxiv.org/abs/2212.12995
  35. [35]C.-C. Tu, T. Yu, T.-C. Chen, S. Liu, H. Zhang, J. Yi, C.-J. Hsieh, and S.-M. Cheng, “Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks,” in Proc. AAAI Conf. Artif. Intell. (AAAI), vol. 33, no. 01, 2019, pp. 742–749.arxiv.org/abs/1805.11770
  36. [36]V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Ve-ness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
  37. [37]H. Van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in Proc. AAAI Conf. Artif. Intell. (AAAI), vol. 30, no. 1, 2016.arxiv.org/abs/1509.06461
  38. [38]Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas, “Deepmind network architectures for deep reinforcement learning,” in Proc. Int. Conf. Mach. Learn. (ICML), 2016, pp. 1995–2003.
  39. [39]D. Hafner, J. Pasukonis, J. Ba, and T. Lillicrap, “Mastering diverse control tasks through world models,” Nature, vol. 640, no. 8059, pp. 647–653, 2025.DOI
  40. [40]P. Leroy, P. G. Morato, J. Pisane, A. Kolios, and D. Ernst, “Imp-marl: A suite of environments for large-scale infrastructure management planning via marl,” in Adv. Neural Inf. Process. Syst. (NeurIPS), vol. 36, 2023, pp. 53 522–53 551.

Paper details

vlnc:W_ycyrap2d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents