- 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, -greedy etc. Experiments on synthetic instances and MovieLens compare the attack with existing baselines and examine its cost and effectiveness.
Critical strengths
- The proposed attack scheme is simple to construct: the attacker choose how many samples 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.
- 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
- The general attack-cost bounds is tight only for specific parameter regime. Specifically, the paper shows matching gap-dependent rates when 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 , while Theorem 4.3 gives a lower bound in terms of the true gap . When is substantially smaller than and the boundary scale 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.
- The paper does not fully explore the dependence on the warm-start history. Assumption 4.1 takes the initial sample count to be 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 , 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
- Theorems 4.2 and 4.3 may leave a gap when is much smaller than and exceeds the boundary scale . Is there an example in which the proposed construction is provably suboptimal, or might the lower bound be sharpened in this regime?
- 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 grow with ?
- Theorems 4.2 and 4.3 state their guarantees for sufficiently large . 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
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 and in our analysis. We focus our detailed analysis on , 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 allocation.
For larger histories, the effect depends on which arms have more observations and what rewards they contain. More target-arm observations can improve and reduce promotion cost. High-reward competitor histories may require more suppression, whereas low-reward histories can help by reducing exploration uncertainty.
If , 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 , this choice satisfies and gives the sufficient budget This remains sublinear, and the same UCB certificate guarantees exclusive target selection with probability at least for sufficiently large .
The lower bound has a similar interpretation. Under zero-tolerance success, each competitor's UCB at round must be no larger than the target's. Since injected rewards are at least , this requires A simple worst-case result is obtained when genuine target rewards equal and competitor clean rewards equal . Under , any successful zero-tolerance attack requires matching the upper bound in order. Thus the worst-case optimal cost remains if , and grows as for larger histories. When , similar analysis also gives the asymptotic 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 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 Using the injection formula and , a sufficient condition for is 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 . All tested experimental configurations satisfy the displayed feasibility condition and have 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 upper bound, while Corollary 4.4 establishes an lower bound for every successful bounded offline attack when . Together, these results establish the minimax-optimal worst-case rate . Moreover, in the near-boundary regime, our construction achieves the optimal leading constant . 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 , , and target mean or , respectively, with five clean observations per arm. In the second instance, all five clean target rewards are zero with probability . 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 , Corollary 4.4 requires cost at least with probability . Consequently, any attack that guarantees success on both instances must also incur this cost on the positive-gap instance with probability at least Thus, although an instance-tailored -cost attack exists when , 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.
A1. We thank the reviewer for raising this important question. We agree that the bounds do not generally match when ε≪Δ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 obtained from the clean warm-start history to guarantee attack success uniformly over the subsequent online rounds. Since NKcl=Θ(1), its confidence radius does not vanish as T increases. Consequently, ε=μK−rmin can be zero even when the true gap ΔK is strictly positive. In contrast, the lower bound in Theorem 4.3 considers UCB index near round T, when the target has accumulated Θ(T) genuine observations and the statistical uncertainty is O(logT/T). This explains the different dependence on ε and ΔK.
Consider K=2,μ1=0.9,μ2=0.1,rmin=0,rmax=1,σ=0.5,N1cl=N2cl=5, and δ=0.05. Here, our confidence estimate gives ε=0, so our construction incurs C(n)=Θ(ST).
However, a cheaper attack exists for this instance. Consider injecting n1=⌈clogT⌉ zero-reward samples into the non-target arm and no samples into the target, where c is a sufficiently large constant. As long as the non-target arm is not selected online, its UCB index satisfies u1(t)≤5+n15+3σ5+n1logT<μ2 for sufficiently large T. Meanwhile, UCB's confidence guarantee ensures u2(t)≥μ2 uniformly over online rounds with probability 1−o(1). Therefore, by induction, UCB selects the target in every online round with high probability, using only Θ(logT) injected samples. This matches the Ω(logT) lower bound in Theorem 4.3 for this instance.
Importantly, this example does not invalidate our worst-case optimality results. When μK=rmin, Corollary 4.4 establishes an Ω(ST) lower bound for every successful bounded offline attack, while our construction achieves the matching upper bound, including the optimal leading constant ΛT. Thus, the Θ(ST) 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. With only Θ(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.