acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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

Primary area:
learning theory
Keywords:
Multi-armed bandits, Adversarial attacks, Warm-start learning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_GP9kOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies bounded offline attacks on warm-start stochastic multi-armed bandits with bounded rewards. Unlike attacks that focus on suppressing competing arms in existing studies, the proposed approach combines non-target suppression with direct promotion of the target arm. For UCB, the authors give an explicit attack construction and derive upper and lower bounds on the required injection cost. In a near-boundary regime, the bounds match asymptotically, including their leading constants. The analysis also characterizes the cost allocation. Under the stated conditions, an asymptotically optimal attack spends approximately two-thirds of its budget on target-arm promotion. The authors then extend the construction to Thompson Sampling, ϵ\epsilon-greedy etc. Experiments on synthetic instances and MovieLens compare the attack with existing baselines and examine its cost and effectiveness.

Critical strengths
  1. The proposed attack scheme is simple to construct: the attacker choose how many samples nin_i to inject for each arm, assign the maximum reward to the target arm and the minimum reward to the others. For this simple design, the authors are able to prove matching attack-cost bounds with the same leading constant in the near-boundary regime for UCB. The paper also illustrates why promoting the target arm is necessary for asymptotically optimal attacks.
  2. The extension to other bandit algorithms shows that the basic construction is not UCB specific (however, the optimality guarantees for these extensions are not as stronger as those obtained for UCB).
Critical weaknesses
  1. The general attack-cost bounds is tight only for specific parameter regime. Specifically, the paper shows matching gap-dependent rates when ϵ=Ω(ΔK)\epsilon =\Omega(\Delta_K) and matching leading constants under the near boundary conditions of Corollary 4.4. However, Theorem 4.2 gives an upper bound in terms of the confidence-based gap ϵ\epsilon, while Theorem 4.3 gives a lower bound in terms of the true gap ΔK\Delta_K. When ϵ\epsilon is substantially smaller than ΔK\Delta_K and the boundary scale ST/TS_T/T does not dominate both, the two bounds could be far away from each other. It is unclear this is due to the limitation of the construction or looseness of the analysis.
  2. The paper does not fully explore the dependence on the warm-start history. Assumption 4.1 takes the initial sample count NiclN^{cl}_i to be Θ(1)\Theta(1) for each arm, while the experiments considered in the paper fix it to be five observations per arm. Yet the construction in Section 4.1 uses these counts and the initial empirical means to determine the injected sample numbers. The main asymptotic optimality results therefore do not directly address histories whose size grows with TT, and the fixed-size experiments provide limited evidence about sensitivity to the initial data. The general construction in Theorem 4.8 allows more flexible initial counts, but it does not resolve the same tight optimality question.
Questions for authors
  1. Theorems 4.2 and 4.3 may leave a gap when ϵ\epsilon is much smaller than ΔK\Delta_K and ΔK\Delta_K exceeds the boundary scale ST/TS_T /T. Is there an example in which the proposed construction is provably suboptimal, or might the lower bound be sharpened in this regime?
  2. How do the attack cost and target-arm selection rate change as the warm-start history becomes larger or more imbalanced across arms? In particular, is the near-boundary optimal cost scaling expected to persist when NiclN^{cl}_i grow with TT?
  3. Theorems 4.2 and 4.3 state their guarantees for sufficiently large TT. Can the authors clarify what determines the required horizon size, and whether the bounds are informative at the horizons used in the experiments?
4 comments

W1 & Q1: Discussion of the gap between the upper and lower bounds.

A1. We thank the reviewer for raising this important question. We agree that the bounds do not generally match when ε≪ΔK\varepsilon \ll \Delta_K. We clarify below that this gap arises from the conservative nature of our construction, while our worst-case cost optimality remains valid.

Our construction uses the lower confidence estimate μ‾K\underline\mu_K obtained from the clean warm-start history to guarantee attack success uniformly over the subsequent online rounds. Since NKcl=Θ(1)N_K^{\rm cl}=\Theta(1), its confidence radius does not vanish as TT increases. Consequently, ε=μ‾K−rmin⁡\varepsilon=\underline\mu_K-r_{\min} can be zero even when the true gap ΔK\Delta_K is strictly positive. In contrast, the lower bound in Theorem 4.3 considers UCB index near round TT, when the target has accumulated Θ(T)\Theta(T) genuine observations and the statistical uncertainty is O(log⁡T/T)O(\sqrt{\log T/T}). This explains the different dependence on ε\varepsilon and ΔK\Delta_K.

Consider K=2,μ1=0.9,μ2=0.1,rmin⁡=0,rmax⁡=1,σ=0.5,N1cl=N2cl=5K=2,\mu_1=0.9,\mu_2=0.1,r_{\min}=0,r_{\max}=1,\sigma=0.5,N_1^{\rm cl}=N_2^{\rm cl}=5, and δ=0.05\delta=0.05. Here, our confidence estimate gives ε=0\varepsilon=0, so our construction incurs C(n)=Θ(ST)\mathcal C(\mathbf n)=\Theta(S_T).

However, a cheaper attack exists for this instance. Consider injecting n1=⌈clog⁡T⌉n_1=\lceil c\log T\rceil zero-reward samples into the non-target arm and no samples into the target, where cc is a sufficiently large constant. As long as the non-target arm is not selected online, its UCB index satisfies u1(t)≤55+n1+3σlog⁡T5+n1<μ2u_1(t)\leq \frac{5}{5+n_1}+3\sigma\sqrt{\frac{\log T}{5+n_1}}<\mu_2 for sufficiently large TT. Meanwhile, UCB's confidence guarantee ensures u2(t)≥μ2u_2(t)\ge\mu_2 uniformly over online rounds with probability 1−o(1)1-o(1). Therefore, by induction, UCB selects the target in every online round with high probability, using only Θ(log⁡T)\Theta(\log T) injected samples. This matches the Ω(log⁡T)\Omega(\log T) lower bound in Theorem 4.3 for this instance.

Importantly, this example does not invalidate our worst-case optimality results. When μK=rmin⁡\mu_K=r_{\min}, Corollary 4.4 establishes an Ω(ST)\Omega(S_T) lower bound for every successful bounded offline attack, while our construction achieves the matching upper bound, including the optimal leading constant ΛT\Lambda_T. Thus, the Θ(ST)\Theta(S_T) worst-case cost cannot be uniformly improved by another construction.

The distinction is that the cheaper attack above is tailored to a positive-gap instance, whereas our construction provides a uniform success guarantee without knowing μK\mu_K. With only Θ(1)\Theta(1) clean observations, reliably distinguishing a positive target gap from the boundary case can be difficult. Developing sharper instance-dependent guarantees under this limited information remains an interesting direction.

We will clarify this distinction and the scope of our optimality claims in the revised paper.

Q2: How do the attack cost and target-arm selection rate change as the warm-start history becomes larger or more imbalanced across arms?

A2. We thank the reviewer for this insightful question. We would like to clarify that the more general cases raised by the reviewer are already captured by NiclN_i^{\rm cl} and BiB_i in our analysis. We focus our detailed analysis on Nicl=Θ(1)N_i^{\rm cl}=\Theta(1), which allows us to isolate the fundamental tradeoff between target promotion and competitor suppression under bounded offline injection. In the near-boundary regime, the clean history contributes only lower-order terms, while the leading costs arise from dilution of target promotion by genuine online feedback and the need to control competitor exploration. This allows us to identify why target promotion is necessary for cost optimality and derive the sharp 2:12:1 allocation.

For larger histories, the effect depends on which arms have more observations and what rewards they contain. More target-arm observations can improve μ‾K\underline\mu_K and reduce promotion cost. High-reward competitor histories may require more suppression, whereas low-reward histories can help by reducing exploration uncertainty.

If T0cl=o(T)T_0^{\rm cl}=o(T), we can reselect the threshold as z=r_{\min}+\max\left\\{z_T^\star-r_{\min},R\sqrt{\sum_{i<K}N_i^{\rm cl}/T}\right\\}. For sufficiently large TT, this choice satisfies z−rmin⁡≤R/2z-r_{\min}\le R/2 and gives the sufficient budget C(n)=O(ST+T∑i<KNicl).\mathcal C(\mathbf n)=O\left(S_T+\sqrt{T\sum_{i<K}N_i^{\rm cl}}\right). This remains sublinear, and the same UCB certificate guarantees exclusive target selection with probability at least 1−δ1-\delta for sufficiently large TT.

The lower bound has a similar interpretation. Under zero-tolerance success, each competitor's UCB at round TT must be no larger than the target's. Since injected rewards are at least rmin⁡r_{\min}, this requires BiNicl+ni+3σlog⁡TNicl+ni≤ρ,ρ=uK(T)−rmin⁡.\frac{B_i}{N_i^{\rm cl}+n_i}+3\sigma\sqrt{\frac{\log T}{N_i^{\rm cl}+n_i}}\le\rho,\qquad \rho=u_K(T)-r_{\min}. A simple worst-case result is obtained when genuine target rewards equal rmin⁡r_{\min} and competitor clean rewards equal rmax⁡r_{\max}. Under T0cl=o(T)T_0^{\rm cl} = o(T), any successful zero-tolerance attack requires C(n)=Ω(ST+T∑i<KNicl),\mathcal C(\mathbf n)=\Omega\left(S_T+\sqrt{T\sum_{i<K}N_i^{\rm cl}}\right), matching the upper bound in order. Thus the worst-case optimal cost remains Θ(ST)\Theta(S_T) if ∑i<KNicl=O(ST2/T)\sum_{i<K}N_i^{\rm cl}=O(S_T^2/T), and grows as Θ(T∑i<KNicl)\Theta(\sqrt{T\sum_{i<K}N_i^{\rm cl}}) for larger histories. When ∑i<KNicl=o(ST2/T)\sum_{i<K}N_i^{\rm cl} = o(S_T^2/T), similar analysis also gives the asymptotic 2:12:1 allocation between target and total non-target injections for attacks attaining the optimal leading cost. We leave a sharp characterization for general histories and their optimal allocations as future work. We will include the above analysis in the revised version.

Q3: When is TT large enough and whether the experiment is informative?

A3. We thank the reviewer for this insightful question. The horizon must (1) accommodate the offline log; and (2) make the cost scale sublinear. For the first requirement, let ρT=zT⋆−rmin⁡=(18Rσ2(K−1)log⁡TT)1/3<R.\rho_T=z_T^\star-r_{\min}=\left(\frac{18R\sigma^2(K-1)\log T}{T}\right)^{1/3}<R. Using the injection formula and Bi≤RNiclB_i\le R N_i^{\rm cl}, a sufficient condition for T0<TT_0<T is T>T0cl+K+1+TρTR−ρT+TρT2R+2R∑i<KNiclρT.T>T_0^{\rm cl}+K+1+\frac{T\rho_T}{R-\rho_T}+\frac{T\rho_T}{2R}+\frac{2R\sum_{i<K}N_i^{\rm cl}}{\rho_T}. The terms on the right bound the clean log, rounding, target promotion, competitor exploration, and suppression of historical rewards, respectively. For the second requirement, we need K=o(T/log⁡T)K=o(T/\log T). All tested experimental configurations satisfy the displayed feasibility condition and have Klog⁡T/TK\log T / T well below one.

Thanks for the detailed reply, which partially addressed my concerns. However, the main concern regarding the tightness of bounds remains. Hence I maintain my current score.

We thank the reviewer for the follow-up and understand the remaining concern regarding the tightness of our bounds. We would like to further clarify two points.

1. Our construction is minimax rate-optimal, although not necessarily instance-optimal. Theorem 4.2 establishes a uniform O(ST)O(S_T) upper bound, while Corollary 4.4 establishes an Ω(ST)\Omega(S_T) lower bound for every successful bounded offline attack when μK=rmin⁡\mu_K=r_{\min}. Together, these results establish the minimax-optimal worst-case rate Θ(ST)\Theta(S_T). Moreover, in the near-boundary regime, our construction achieves the optimal leading constant ΛT\Lambda_T. Thus, no alternative construction can improve the worst-case rate.

2. The instance-dependent gap also reflects a fundamental information limitation. Consider two Bernoulli instances with K=2K=2, μ1=0.9\mu_1=0.9, and target mean μ2=0\mu_2=0 or 0.10.1, respectively, with five clean observations per arm. In the second instance, all five clean target rewards are zero with probability 0.95≈0.590.9^5\approx 0.59. Conditional on this event, the distributions of the entire clean histories are identical in the two instances. Therefore, any offline attack based only on the clean history cannot distinguish them.

For the boundary instance μ2=0\mu_2=0, Corollary 4.4 requires cost at least (1−o(1))ΛT(1-o(1))\Lambda_T with probability 1−δ−1/T1-\delta-1/T. Consequently, any attack that guarantees success on both instances must also incur this cost on the positive-gap instance with probability at least 0.95(1−δ−1/T).0.9^5(1-\delta-1/T). Thus, although an instance-tailored O(log⁡T)O(\log T)-cost attack exists when μ2=0.1\mu_2=0.1, achieving this lower cost while maintaining a uniform success guarantee is generally impossible with only five clean observations.

This further explains why the instance-dependent upper and lower bounds need not match under limited warm-start information. We acknowledge that a complete characterization of instance-dependent optimality remains open. We will clarify the minimax guarantee, the distinction from instance-dependent optimality, and this information limitation in the revised paper.

We appreciate the reviewer's constructive feedback.

Reviewer_Mw1aOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates offline data-poisoning attacks on ”warm-start” multiarmed bandit (MAB) problems with bounded rewards. Unlike existing attack methods—which primarily rely on modifying rewards in real-time or suppressing the rewards of non-target arms—this study considers a scenario where an attacker can only inject valid reward samples into the historical dataset before the algorithm is deployed. The cost of an attack is defined as the number of injected samples.

The paper proposes an offline attack strategy that combines the promotion of a target arm with the suppression of non-target (competitor) arms. For the Upper Confidence Bound (UCB) algorithm, the authors derive both upper and lower bounds on the attack cost. In the specific case where the expected reward of the target arm is close to the lower bound of the reward range, the authors further demonstrate that the optimal attack cost scales asymptotically as: Θ(T2/3(Klog⁡T)1/3)\Theta\left(T^{2/3}(K\log T)^{1/3}\right), with the upper and lower bounds matching in their leading constants. A key theoretical finding is that an asymptotically optimal attack must allocate approximately two-thirds of the injection budget to promoting the target arm, while the remaining one-third is used to suppress non-target arms. Furthermore, the paper extends this attack strategy to Thompson Sampling, ϵ\epsilon-greedy, and a broader class of "suppression-bounded" algorithms. The authors evaluate the attack cost, success rate, and the optimal distribution of the injection budget using both the MovieLens-25M dataset and synthetic experiments.

Critical strengths
  1. The paper makes a clear and non-trivial theoretical contribution. Beyond proposing a construction for an offline attack, the paper analyzes the upper and lower bounds of attack costs, as well as the optimal allocation of resources. Notably, Corollary 4.4 and Lemma 4.5 provide the optimal cost—matching the leading constant—for the near-boundary case, along with a required cost-allocation ratio of approximately 2:1. These findings demonstrate that boosting the reward of a target arm is not merely an effective attack strategy; in certain scenarios, it is essential for achieving an asymptotically optimal attack cost. This carries greater theoretical significance than simply proving that a given attack can succeed.
  2. The attack model holds practical relevance, with a strong connection between theoretical analysis and algorithm design. The paper assumes that an attacker can only inject rewards—within a valid range—prior to deployment, and cannot alter the actual feedback generated post-deployment. This framework effectively captures real-world scenarios such as the injection of fake reviews or the poisoning of historical interaction data in recommendation systems. Within this model, the authors derive an attack scheme with rigorous theoretical guarantees by jointly optimizing the boosting of the target arm and the suppression of competing arms. Furthermore, the paper examines various bandit algorithms and uses experimental results to validate the theoretically predicted trends in attack costs and resource allocation patterns.
Critical weaknesses
  1. The scope of the theoretical results and the conditions regarding the growth of parameters require more precise clarification. Assumption 4.1 (page 5) posits that the reward range, the sub-Gaussian parameter, and the number of "clean" offline samples for each arm are of constant order, leading to the expression: T0cl=Θ(K)=o(T)T_0^\mathrm{cl} = \Theta(K) = o(T). However, if the number of arms (KK) is permitted to grow with the time horizon (TT), then T0cl=Θ(K)T_0^\mathrm{cl} = \Theta(K) does not, by itself, imply T0cl=o(T)T_0^\mathrm{cl} = o(T). Specifically, in the near-boundary case, the authors derive an attack cost of: ST=T2/3(Klog⁡T)1/3S_T = T^{2/3}(K\log T)^{1/3}. To satisfy the sublinear attack cost requirement (C(n)=o(T)C(n) = o(T)) stipulated in Definition 3.2, an additional condition is necessary: Klog⁡T=o(T)K\log T = o(T). If the authors intend to assume that K remains fixed, this should be explicitly stated. As currently presented, the theorems include an explicit dependence on K, which may lead readers to infer that the results apply to more general scenarios where both K and T grow. Furthermore, the paper’s strongest optimality guarantees pertain primarily to the near-boundary case for UCB. For general reward gaps, the upper and lower bounds derived by the authors depend on the estimated gap (ϵ) and the true gap (∆K ), respectively; these do not always align. Moreover, similarly robust necessity or optimality results have not yet been established for extensions involving TS (Thompson Sampling) or ϵ-greedy strategies. It is recommended that the authors clearly distinguish between feasibility guarantees for the general case and asymptotic optimality conclusions for specific scenarios, while providing a more explicit account of how these results depend on K and T.
  2. The fairness of the experimental comparisons and the transparency of certain key experimental settings require improvement.

To begin with, Figures 1 and 2 (on page 8) compare the proposed method against "Clipped Suppression." However, "Clipped Suppression" intervenes during the online phase whenever a non-target arm is selected, whereas the attack proposed in this paper is executed entirely prior to deployment.

Given that these two types of attacks differ in terms of intervention timing, available information, and operational privileges, a direct comparison of attack costs—while potentially useful as a reference—does not sufficiently demonstrate that the proposed method offers superior cost-efficiency under an identical threat model. A more compelling set of experiments would include viable baselines subject to the same offline injection constraints.

Furthermore, regarding Figure 3, the main text describes the experiment as a Bernoulli bandit constructed based on the empirical mean rewards from the MovieLens dataset. However, the supplementary code (\texttt{theory_alignment_runner.py}) reveals that the mean reward for the target arm actually varies as a function of TT: μK(T)=μKML100000T\mu_K(T) = \mu_K^\mathrm{ML}\sqrt{\dfrac{100000}{T}}.

While this design is logically sound—as it allows the target arm’s reward to gradually approach the lower bound, thereby facilitating the verification of asymptotic behavior near the boundary—the main text fails to explicitly mention this TT-dependent modification. This omission may lead readers to mistakenly assume that Figure 3 relies on the static, empirical reward distribution derived from the MovieLens dataset.

It is recommended that the authors explicitly disclose this experimental setup and clarify which figures utilize the original empirical means versus the adjusted, near-boundary construction.

Additionally, the current experiments on real-world data employ an environment based on binarized ratings with independent resampling, where each arm is associated with only five "clean" historical observations. While this setup is useful for theoretical validation, it is insufficient to fully capture the performance of an attack when faced with larger-scale historical datasets and the practical constraints inherent in data poisoning.

Questions for authors

Do Theorem 4.2, Theorem 4.3, and Corollary 4.4 allow KK to grow as a function of TT? If so, please specify the required growth conditions---particularly those necessary to ensure that the attack cost remains o(T)o(T). If the results are intended to hold only for a fixed KK, this should be explicitly stated in Assumption 4.1 and the relevant theorems.

The supplementary code constructs "near-boundary" experiments by scaling the means of the target arms by T−1/2T^{-1/2}. This procedure is not explicitly described in the main text. Could the authors provide a detailed explanation of this design and clarify the distinction between the original MovieLens distribution and the artificially adjusted one? Furthermore, could the authors include experiments with fixed target means to demonstrate the boundaries of the theory's applicability?

The current comparisons involve different attack timings and levels of intervention authority. Could the authors add a baseline that restricts sample injection to an offline setting and ensures it remains within "legitimate" bounds, then compare the costs under the same success criteria? This would help clarify whether the advantages of the combined "Target Promotion" and "Competitor Suppression" strategy stem from the algorithm's design or from differences in the underlying attack models.

3 comments

W1 & Q1: Growth of KK.

A1. We thank the reviewer for this question. We would like to clarify that KK is typically fixed before the algorithm is deployed and is commonly treated as a constant in theoretical analyses. This convention is particularly prevalent in the attack literature, where an attack cost of O(Klog⁡T)O(K\log T) is considered sublinear in TT (Jun et al., 2018; Zuo et al., 2024). Nevertheless, we agree that explicitly specifying the condition Klog⁡T=o(T)K\log T=o(T) would improve the rigor and clarity of our theoretical guarantees. We will therefore incorporate this condition into the revised manuscript.

W2 & Q2: Clarification of the choice of μK\mu_K in Figure 3.

A2. We thank the reviewer for raising this concern. Figure 3 shows that our construction approaches the predicted 2:12:1 allocation in the "near-boundary" regime. However, the smallest positive mean in MovieLens is 11/66911/669, which may not be sufficiently close to the boundary as TT increases, since the near-boundary condition requires ΔK=o(ST/T)\Delta_K = o(S_T/T). To better illustrate the 2:12:1 allocation, we retain the MovieLens competitors but scale the target's mean as μK(T)=(11/669)105/T\mu_K(T) = (11/669)\sqrt{10^5/T}, ensuring that ΔK=o(ST/T)\Delta_K = o(S_T/T). This allows us to better examine the predicted attack cost and allocation in the near-boundary regime. We will add these illustrations in the revision.

W2 & Q3: Clarification of the experimental comparisons.

A3. We thank the reviewer for raising this question. Our setting combines bounded rewards with attacks restricted to offline data injection, and we are not aware of a directly matching baseline. We therefore include Xu et al. (2021) as a representative bounded-reward baseline. As shown in Figure 4, their attack cost grows as the target mean approaches zero and can exceed the available horizon, whereas our construction achieves a sublinear injection cost under our assumptions, including at μK=0\mu_K=0. Related suppression-based approaches also face limitations at this boundary. Specifically, the UCB attack of Zuo et al. (2023) reduces non-target feedback without promoting the target and cannot ensure T−o(T)T-o(T) target selections when the target mean is close to 0. The bounded-injection analysis of Zeng et al. (2025) requires sufficient separation between the target mean and the lower bound on injected rewards.

Existing offline attacks also differ in their intervention mechanisms and objectives. Liu and Shroff (2019) perturb rewards in a historical data batch to induce target selection at the next decision, whereas we inject bounded samples before deployment and seek sustained target selection throughout subsequent online learning. Hosseini et al. (2026) instead perturb the parameters of the reward model before bandit training. These methods therefore do not directly instantiate our attack model.

Our experiments illustrate the effectiveness of the proposed allocation and its agreement with the predicted cost and budget shares. UCB scores depend only on the current empirical means, observation counts, and time index. Therefore, identical values of these quantities yield identical scores, regardless whether the rewards are observed online or offline. Nevertheless, we provide two additional baselines for comparison, demonstrating the necessity of attacking the target arm and non-target arms simultaneously, as stated in A2 to Reviewer Yb38.

W2. The rewards from MovieLens are resampled.

A4. We thank the reviewer for raising this concern. The primary reason for resampling rewards is the limited size of the MovieLens dataset. For example, the selected target arm has only 669 observations in the original dataset, whereas our experiments consider horizons of T≥105T \geq 10^5. Importantly, the action-selection rules of UCB, TS, and ϵ\epsilon-greedy in our implementations depend on the empirical means and observation counts of the arms, rather than the exact sequence of historical rewards. Since resampling preserves the empirical reward distribution and its mean in expectation, the resampled empirical means concentrate around their original values as the number of samples increases. Therefore, we expect resampling to have a limited impact on the experimental results, particularly for large TT.

Thanks for the replies, which addressed some of my concerns. Given the positive score, I will keep the score unchanged.

We thank the reviewer for the follow-up. We are glad that our response has addressed some of the concerns.

Reviewer_Yb38OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies offline data-injection attacks against warm-start stochastic bandits with bounded rewards. Rather than only suppressing non-target arms, it promotes the target arm using valid high-reward fake samples. For UCB, it derives sublinear attack-cost bounds and, in a near-lower-boundary regime, a leading-order optimal \Theta(T^{2/3}(K\log T)^{1/3}) cost with an asymptotic 2:1 split between target promotion and aggregate non-target suppression. It also gives attack constructions for Thompson Sampling, epsilon-greedy, and a broader suppression-bounded class, with MovieLens-inspired simulations.

Critical strengths
  1. The threat model is timely and concrete: bounded, offline-only fake feedback is more realistic than arbitrary online reward corruption in several warm-start settings.

  2. The main UCB result is technically interesting. The target-promotion lower bound and asymptotic 2/32/3 target-cost share go beyond showing that an attack exists; they characterize how a cost-optimal attack must allocate effort.

  3. The analysis clearly separates dilution of target promotion by genuine feedback from the exploration bonus reduction induced by suppressing competitors.

  4. The paper has a coherent theoretical narrative, and the extensions to TS and epsilon-greedy help establish that the construction is not UCB-specific.

Critical weaknesses
  1. The strongest optimality and allocation claims hold only in a narrow regime: a target near the lower reward boundary, small clean per-arm logs N_i^{cl}=\Theta(1), and effectively T_0^{cl}=\Theta(K). This is a substantial limitation for a paper motivated by real warm-start systems, which commonly have large and highly imbalanced historical logs.

  2. The empirical comparison is not fully threat-model matched. The principal baseline, Clipped Suppression, manipulates online rewards, whereas the proposed attack is offline-only. A fair comparison needs offline-only target-only and suppression-only baselines under the same valid-reward and sample-count constraints.

  3. MovieLens is used mainly to define Bernoulli arm means and then rewards are independently resampled with replacement. This is a reasonable controlled simulation, but it does not demonstrate robustness on realistic logged, nonstationary, or heterogeneous warm-start data.

  4. The broad-algorithm claims are weaker than the UCB contribution: TS and epsilon-greedy receive constructions/upper bounds, but the near-optimal lower bound and necessary target-centric allocation are established only for UCB.

Questions for authors
  1. How does the optimal cost and target-versus-suppression allocation change when the clean warm-start log is large, uneven across arms, or scales with T? This appears central to the practical warm-start motivation, but the main theorem assumes N_i^{cl}=\Theta(1).

  2. Can the experiments include fair offline-only ablations: target-promotion only, non-target suppression only, and their optimized combination, all constrained to the same number of bounded injected samples? This would directly validate the paper’s central allocation claim without comparing primarily to an online-intervention baseline.

  3. Please sharpen the scope of the “near-optimal” and “target-centric necessity” claims. Do analogous lower bounds or allocation characterizations hold for TS/epsilon-greedy, outside the near-boundary regime, or when a small but nonzero number of non-target online pulls is allowed?

2 comments

W1 & Q1. How does the optimal cost and target-versus-suppression allocation change when the clean warm-start log per arm is not Θ(1)\Theta(1).

A1. We thank the reviewer for this insightful question. We focus on Nicl=Θ(1)N_i^{\rm cl}=\Theta(1) to isolate the fundamental tradeoff between target promotion and competitor suppression, establishing the necessity of target promotion for cost optimality and deriving the sharp 2:12:1 allocation in the near-boundary regime. For a discussion of the case where the clean warm-start history per arm is not of size Θ(1)\Theta(1), please refer to our response A2 to Reviewer GP9k.

W2 & Q2: The experiment should add offline-only baselines.

A2. We thank the reviewer for this valuable suggestion. We have added these offline-only ablations to Figure 2. In each repeat, target-only, suppression-only, and our joint strategy use the same clean log and total number of bounded injected samples. All subsequent feedback is genuine. For suppression-only, we choose the fake-sample allocation as n=arg⁡min⁡nmax⁡i<Kμ^i(T0+1)+3σlog⁡T/T\mathbf n = \arg \min_{\mathbf n} \max_{i < K} \hat \mu_i(T_0+1) + 3\sigma \sqrt{\log T / T} and nK=0n_K = 0, thereby minimizing the maximum post-attack index among non-target arms and balancing their suppression. Across Figures 2(a) and 2(b), the joint strategy consistently achieves NKon/H=1N_K^{\rm on}/H=1 across all settings. In Figure 2(a), the target-selection ratios of both the target-only and suppression-only baselines decrease as TT increases. In Figure 2(b), as KK increases, the suppression-only baseline deteriorates, whereas the target-only baseline improves but remains well below 11. For example, at K=10K=10 and T=106T=10^6, the average online target-selection ratios are 100%100\%, 2.43%2.43\%, and 3.97%3.97\% for joint, target-only, and suppression-only attacks, respectively. These results demonstrate the benefit of combining target promotion with non-target suppression, while also highlighting the increasing importance of concentrating the attack budget on the target arm as KK grows. For more discussion of our experimental setting, please see A3 to Reviewer Mw1a.

W4 & Q3: Do analogous lower bounds or allocation characterizations hold for TS/epsilon-greedy, outside the near-boundary regime, or when a small but nonzero number of non-target online pulls is allowed?

A3. We thank the reviewer for this insightful question. The “near-optimal” and “target-centric necessity” claims primarily concern UCB in the “near-boundary” regime, which is also the main focus of our theoretical analysis in the paper. Here we provide more analyses for ϵ\epsilon-greedy and Thompson Sampling.

For ϵ\epsilon-greedy with ϵs=min⁡1,cK/s\epsilon_s=\min\\{1,cK/s\\}, we can use the same argument as in UCB analysis. At the last greedy round t⋆t^\star that selects arm KK. Comparing empirical means gives nKni≥NKon(t⋆)Nion(t⋆)n_Kn_i\ge N_K^{\rm on}(t^\star) N_i^{\rm on}(t^\star). Under C(n)=o(T)\mathcal C(\mathbf n)=o(T) and ξ=o(T)\xi=o(T), success implies NKon(t⋆)=Θ(T)N_K^{\rm on}(t^\star)=\Theta(T). The exploration schedule also ensures Nion(t⋆)≥1N_i^{\rm on}(t^\star)\ge1 for each competitor with high probability. Thus nK∑i<Kni=Ω((K−1)T),C(n)=Ω((K−1)T).n_K\sum_{i<K}n_i=\Omega((K-1)T),\qquad\mathcal C(\mathbf n)=\Omega(\sqrt{(K-1)T}). The existing non-target pull bound B=O(log⁡T)B=O(\log T) gives our upper cost O(T(K−1)B)=O(TKlog⁡T)O(\sqrt{T(K-1)B})=O(\sqrt{TK\log T}). This leaves a log⁡T\sqrt{\log T} gap. We leave a tighter upper and lower bound and a necessary optimal allocation characterization as future work, which may require bounding the exploration rounds from t=T0+1t = T_0+1 instead from t=1t=1.

For Thompson Sampling, the same argument is insufficient. If arm KK is always selected, competitors receive no new online observations, so their Gaussian sampling uncertainty never decreases. With too few offline samples, a competitor retains a chance of drawing above the target in every round, and these risks accumulate over Θ(T)\Theta(T) rounds. Gaussian tail bounds require Nicl+ni=Ω(log⁡T/ρ2)N_i^{\rm cl}+n_i=\Omega(\log T/\rho^2), where ρ\rho bounds the target's empirical mean above rmin⁡r_{\min} in the late rounds. In the worst-case instance, the target injections are diluted by Θ(T)\Theta(T) genuine observations with reward rmin⁡r_{\min}, so ρ=O(RnK/T)\rho=O(Rn_K/T). Substituting this into the required competitor counts and summing over i<Ki<K gives nK2∑i<Kni=Ω((K−1)T2log⁡T),C(n)=Ω(ST),n_K^2\sum_{i<K}n_i=\Omega((K-1)T^2\log T),\qquad\mathcal C(\mathbf n)=\Omega(S_T), with probability at least 1−δ−o(1)1-\delta-o(1) for successful attacks. This matches our upper bound up to constants and requires nonvanishing target and competitor shares for order-optimal attacks. However, more detailed analysis is much more complicated and we defer it as future work.

For more discussion of UCB optimality outside the near-boundary regime, or when a small but nonzero number of non-target online pulls is allowed, please see A2 to Reviewer GP9k.

W3. The rewards from MovieLens are resampled.

A4. We thank the reviewer for this question. The primary reason for resampling rewards is the limited size of the MovieLens dataset. For detailed discussion, please see A4 to Reviewer Mw1a.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.