Paper deep dive
Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards
Qirun Zeng, Manhin Poon, Xiangxiang Dai, Qixin Zhang, Jinhang Zuo
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/11/2026, 3:39:34 AM
Summary
This paper investigates bounded offline attacks on warm-start stochastic multi-armed bandits, specifically focusing on 'target promotion' (injecting high rewards for the target arm) versus 'non-target suppression' (injecting low rewards for competitors). The authors demonstrate that for algorithms like UCB, when the target arm is near the lower reward boundary, cost-optimal attacks must allocate a significant portion of their budget to promoting the target arm. They derive near-optimal cost bounds and extend their attack strategy to Thompson Sampling and epsilon-greedy algorithms, validating their findings through experiments on MovieLens data.
Entities (9)
Relation Signals (5)
Warm-Start Bandits → isvulnerableto → Bounded Offline Attacks
confidence 98% · We study this gap through bounded offline attacks on warm-start bandits
UCB → istargetofattack → Target Promotion
confidence 95% · 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.
Target Promotion → iscomplementaryto → Non-Target Suppression
confidence 93% · characterize its allocation between target promotion and non-target suppression
MovieLens → isusedforevaluation → Bounded Offline Attacks
confidence 92% · Experiments on real-world and synthetic data validate the effectiveness of our attacks... evaluate our attacks on MovieLens
Thompson Sampling → issupportedbyattack → Bounded Offline Attacks
confidence 90% · We further extend the attack to Thompson Sampling
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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, $\epsilon$-greedy, and a broader class of bandit algorithms. Experiments on real-world and synthetic data validate the effectiveness of our attacks.
Tags
Links
- Source: https://arxiv.org/abs/2610.10000v1
- Canonical: https://arxiv.org/abs/2610.10000v1
Trouble viewing inline? Open PDF directly →
Full Text
70,657 characters extracted from source content.
Expand or collapse full text
Beyond Reward Suppression: Near-Optimal Offline Attacks on Warm-Start Bandits with Bounded Rewards Qirun Zeng Manhin Poon Xiangxiang Dai Qixin Zhang Jinhang Zuo Email: qirun.zeng,manhpoon4-c@my.cityu.edu.hkxxdai23@cse.cuhk.edu.hk qixin.zhang@ntu.edu.sg Affiliation: City University of Hong Kong, Hong Kong SAR, China Affiliation: The Chinese University of Hong Kong, Hong Kong SAR, China Affiliation: Nanyang Technological University, Singapore Email: jinhang.zuo@cityu.edu.hk 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. 1 Introduction Multi-armed bandit (MAB) algorithms provide a principled framework for sequential decision-making under uncertainty and have been widely adopted in applications such as recommender systems and online advertising. In many practical applications, however, bandit algorithms are not deployed from scratch. Instead, they are initialized with historical interaction data, giving rise to the warm-start bandit setting (Shivaswamy and Joachims, 2012; Li et al., 2021; Banerjee et al., 2022; Oetomo et al., 2023). While such historical data can improve early decisions and reduce exploration costs, they also create a natural attack surface: fake feedback injected before deployment can bias the learner’s initial estimates, and this bias may persist even when all subsequent feedback is genuine. Adversarial attacks on bandits have been studied extensively, but most existing work (Jun et al., 2018; Liu and Shroff, 2019; Zuo, 2024) focuses on manipulating rewards during online interaction, typically allowing arbitrary modifications to observed rewards and measuring attack cost by the total magnitude of these modifications. Zeng et al. (2025) takes a step further by injecting fake action–reward records to model fake users. Building on these works, we consider a more natural setting in which the learner is initialized with offline logs before online deployment, and the attacker can inject fake action–reward records only during this offline stage. We further measure attack cost by the number of injected samples, which more closely reflects the practical cost of generating fake interactions. This bounded fake-data perspective not only better reflects settings such as review manipulation, but also makes how the attacker allocates its limited effort across arms a central question. More importantly, existing attacks on stochastic bandits typically steer the learner toward a target arm by suppressing the observed rewards of non-target arms (Jun et al., 2018; Zuo et al., 2023; Zuo, 2024; Zeng et al., 2025). Although such attacks admit strong theoretical guarantees with controlled cost, their mechanism differs from common real-world manipulation practices, where attackers often directly promote a chosen item through favorable feedback. For example, researchers have observed Amazon sellers recruiting reviewers through private Facebook groups and reimbursing purchases in exchange for five-star reviews, sometimes with additional commissions (He et al., 2022b). Direct promotion is also intuitively attractive: a favorable review benefits the target itself, whereas suppressing a single competitor affects only one of many alternatives. This gap raises a natural question: when is directly promoting the target not only effective, but necessary for a cost-efficient attack? Motivated by this mismatch, we study bounded offline attacks on warm-start stochastic bandits under two practical constraints. First, every injected reward must lie within the valid feedback range, such as binary clicks or 11–55 star ratings. Second, the attacker can intervene only before deployment, since maintaining access throughout the online learning process may be difficult or impossible. Under these constraints, target promotion and non-target suppression play fundamentally different roles. Injecting favorable feedback on the target improves its comparison against all competitors, but this initial advantage is gradually diluted as genuine online feedback accumulates. In contrast, suppressing a competitor requires injecting unfavorable feedback specifically for that arm, and bounded rewards limit how much each injected sample can change its empirical estimate. The attacker must therefore decide not only how many samples to inject, but also how to allocate these injections across arms. This leads to our central question: How should an attacker allocate its power between the target arm and its competitors? We answer this question by jointly optimizing target promotion and non-target suppression. We propose a bounded offline attack against warm-start UCB and establish both an upper bound on its cost and a lower bound for any successful attack. Our lower bound analysis further reveals that the optimal allocation is necessarily target-centric: any attack achieving the leading-order optimal cost that makes the target arm selected in nearly all online rounds must spend a nonvanishing fraction of its cost on promoting the target. We further extend our strategy to the class of suppression-bounded algorithms studied by Zeng et al. (2025), with algorithm-specific analyses for Thompson Sampling and ϵε-greedy in Appendices B and C. These results demonstrate the broader applicability of our strategy beyond UCB. Table 1: Comparison of bandit attack models and guarantees. Attack Strategy Timing Bounded Rewards Target Promotion Allocation Analysis Opt. Jun et al. (2018) online ✗ ✗ ✗ ✗ Liu and Shroff (2019) offline ✗ ✓ ✗ ✓ Xu et al. (2021) online ✓ ✓ ✗ ✗ Zuo (2024) online ✗ ✗ ✗ ✓ Zeng et al. (2025) online ✓ ✗ ✗ ✗ Hosseini et al. (2026) offline ✗ ✗ ✗ ✗ Ours (Sec. 4) offline ✓ ✓ ✓ ✓ • Prior work separately studies offline poisoning, bounded attacks, or attack-cost optimality, but does not characterize how attack effort should be allocated across arms. Our work combines bounded offline injection with direct target promotion and proves that cost-optimal attacks require substantial effort on the target arm itself. The online variant of Liu and Shroff (2019) is omitted since it does not satisfy any of the properties in the columns. 1.1 Our Contributions We summarize our contributions as follows: • We formulate bounded offline attacks on warm-start stochastic bandits, measuring attack cost by the number of valid action–reward samples injected before deployment. This model captures settings such as fake-review manipulation, where the cost is associated with generating fake interactions rather than the magnitude of reward modification. • We establish upper and lower bounds on the cost of bounded offline attacks against UCB. In the near-boundary regime, these bounds match to leading order, yielding the optimal sublinear cost scale Θ(T2/3(KlogT)1/3) \! (T^2/3(K T)^1/3 ) for K arms and T rounds. Notably, we bridge this theory–practice gap by showing that cost-optimal attacks must allocate a nonvanishing fraction of their cost to the target arm. • We extend our attack strategy beyond UCB to Thompson Sampling, ϵε-greedy, and the broader class of suppression-bounded algorithms introduced by Zeng et al. (2025). This extension shows that the same combination of target promotion and non-target suppression applies to a broad class of bandit algorithms. • We evaluate our attacks on MovieLens (Harper and Konstan, 2015) against existing baselines. The experiments demonstrate lower attack costs while maintaining effective target-arm manipulation, and empirically validate the predicted target-centric cost allocation. 1.2 Related Work Research on adversarial manipulation of bandits follows two complementary directions: designing attack algorithms, and developing robust algorithms against adversarial attack. Adversarial Attacks. Jun et al. (2018) showed that sublinear-cost attacks can steer UCB and ϵε-greedy toward a target arm, while Liu and Shroff (2019) developed an adaptive attack without knowledge of the learner’s algorithm. Zuo (2024) established near-optimal attacks against UCB and TS with matching lower bounds. Other work studies restricted intervention: Xu et al. (2021) proposed an observation-free attack during prescribed online phases, and Zeng et al. (2025) introduced bounded fake data injection with constraints on injection timing and frequency. A common strategy in this line of work is to favor the target by suppressing the observed rewards of non-target arms. Attacks have also been studied in contextual, linear, adversarial, and learning-to-rank bandits (Garcelon et al., 2020; Wang et al., 2022; Ma and Zhou, 2023; Zuo et al., 2023). Beyond these works, Liu and Shroff (2019) formulated offline reward-poisoning attacks as convex optimization problems for several bandit algorithms. Hosseini et al. (2026) studied reward-model perturbations before training an offline bandit, without subsequent online interaction. Robust Bandits. Lykouris et al. (2018) established corruption-dependent regret bounds for stochastic bandits without prior knowledge of the corruption level, and Gupta et al. (2019) improved these guarantees. Kapoor et al. (2019) used robust statistical estimation to tolerate corrupted rewards in multi-armed and linear contextual bandits. For linear bandits, robust phased elimination (Bogunovic et al., 2021) and confidence-weighted regression (He et al., 2022a) control the influence of corrupted observations, with guarantees that account for whether the corruption level is known. Robustness has also been studied in Gaussian process (Bogunovic et al., 2022), Lipschitz (Kang et al., 2023), and combinatorial bandits (Xu and Li, 2021). The threat models considered in these works are typically weaker than those studied in the attack literature, since the adversary is not allowed to observe the learner’s actions before corrupting the feedback. Our work follows the attack-design direction and adopts the fake data injection model of Zeng et al. (2025) in an offline-to-online setting. 2 Warm-Start Bandit Setup We consider a stochastic multi-armed bandit with arm set ≜1,…,KK \1,…,K\. Each arm i∈i is associated with an unknown reward distribution with mean μi _i. Rewards are supported on [rmin,rmax][r_ ,r_ ] and are σ2σ^2-sub-Gaussian, where σ2σ^2 is known to the learner. The learner is initialized with an offline log off≜((as,rs))s=1T0D^off ((a_s,r_s) )_s=1^T_0 containing T0T_0 action–reward observations, where as∈a_s denotes the arm selected in observation round s, and rs∈[rmin,rmax]r_s∈[r_ ,r_ ] denotes the corresponding observed reward. For each arm i, let Nioff≜∑s=1T0as=iN_i^off _s=1^T_01\a_s=i\ denote its offline count. After initialization, the learner interacts with the bandit environment from round T0+1T_0+1 through round T. Thus, the online rounds are on≜T0+1,…,TT^on \T_0+1,…,T\, with online horizon H≜|on|=T−T0H |T^on|=T-T_0. At the beginning of each online round t∈ont ^on, the learner’s history consists of the offline log and the preceding online observations: ℋt≜(off,((as,rs))s=T0+1t−1).H_t (D^off, ((a_s,r_s) )_s=T_0+1^t-1 ). A general warm-start bandit algorithm is specified by a policy sequence Π≜πtt∈on \ _t\_t ^on, where πt(⋅∣ℋt)∈Δ() _t(· _t)∈ (K). In round t, the learner samples at∼πt(⋅∣ℋt)a_t _t(· _t), observes the corresponding reward rtr_t, and appends (at,rt)(a_t,r_t) to its history. We write Nion(t)≜∑s=T0+1t−1as=iN_i^on(t) _s=T_0+1^t-11\a_s=i\ for the number of online pulls of arm i before round t. UCB Specialization. We next instantiate this general framework using the UCB algorithm considered by Jun et al. (2018), following the prototype in Bubeck and Cesa-Bianchi (2012, Section 2.2). UCB summarizes the available history ℋtH_t through the number of observations and the empirical mean associated with each arm. For every arm i∈i , define Ni(t)≜∑s=1t−1as=i=Nioff+Nion(t)N_i(t) _s=1^t-11\a_s=i\=N_i^off+N_i^on(t) and μ^i(t)≜∑s=1t−1as=irs/Ni(t) μ_i(t) _s=1^t-11\a_s=i\r_s/N_i(t) whenever Ni(t)>0N_i(t)>0. The UCB index of arm i is ui(t)≜μ^i(t)+3σlogtNi(t),Ni(t)>0,+∞,Ni(t)=0.u_i(t) cases μ_i(t)+3σ tN_i(t),&N_i(t)>0,\\ +∞,&N_i(t)=0. cases The learner selects at∈argmaxi∈ui(t)a_t∈ _i u_i(t). In the absence of attacks, it achieves sublinear regret. 3 Offline Attack Model 3.1 Attack Setting and Attack Cost Let cl≜((as,rs))s=1T0clD cl ((a_s,r_s) )_s=1^T_0 cl denote the clean offline log, where T0cl=|cl|T_0 cl=|D cl| is the number of genuine observations. For each arm, its clean-log and subsequent online rewards form a prefix of the same i.i.d. reward stream. Arm choices may depend on past observations; each chosen arm’s next reward is then observed and retained, with no filtering based on its value. Before deployment, the attacker observes clD cl and knows the learner’s policy Π , the terminal time T, and the valid reward range [rmin,rmax][r_ ,r_ ]. The attacker acts only at this stage and cannot modify the learner’s actions, observed rewards, or history after online interaction begins. For each arm i, define its clean offline count and empirical mean as Nicl≜∑s=1T0clas=i,μ^icl≜1Nicl∑s=1T0clas=irs,N_i cl _s=1^T_0 cl1\a_s=i\, μ_i cl 1N_i cl _s=1^T_0 cl1\a_s=i\r_s, where the empirical mean is defined whenever Nicl>0N_i cl>0. During online interaction, Nicl(t)N_i cl(t) and μ^icl(t) μ_i cl(t) denote the count and empirical mean of all genuine observations of arm i available before round t, including the clean offline observations but excluding injected samples. Thus, at the start of online interaction, Nicl(T0+1)=NiclN_i cl(T_0+1)=N_i cl and μ^icl(T0+1)=μ^icl μ_i cl(T_0+1)= μ_i cl. A candidate injection plan is represented by (,)(n,y), where ≜(n1,…,nK)∈ℤ≥0Kn (n_1,…,n_K) _≥ 0^K specifies the number of fake observations injected for each arm and ≜(yi,j:i∈,j=1,…,ni)y (y_i,j:i ,\ j=1,…,n_i) specifies the corresponding fake rewards. Every injected reward must lie in [rmin,rmax][r_ ,r_ ] and, for discrete feedback, in the legal feedback alphabet. Let F(,)D^F(n,y) denote the collection of fake action–reward pairs (i,yi,j):i∈,j=1,…,ni\(i,y_i,j):i ,\ j=1,…,n_i\ in the order chosen by the strategy. The learner is initialized using the attacked warm-start log off(,)≜cl∥F(,),D^off(n,y) cl \|D^F(n,y), where ∥ \| denotes sequence concatenation. Definition 3.1 (Attack Cost). The attack cost is the number of injected samples: ()≜∑i=1Kni.C(n) _i=1^Kn_i. (1) Consequently, Nioff=Nicl+niN_i^off=N_i cl+n_i and T0=|off|=T0cl+(),H=T−T0.T_0= |D^off |=T_0 cl+C(n), H=T-T_0. Without loss of generality, we label the target arm as K. Definition 3.2 ((ξ,δ)(ξ,δ)-Success Criterion). Fix δ∈(0,1)δ∈(0,1) and ξ:ℕ→ℝ≥0ξ _≥ 0. An offline attack is (ξ,δ)(ξ,δ)-successful if Pr(∑i=1K−1Nion(T+1)≤ξ)≥1−δand()=o(T). ( _i=1^K-1N_i^on(T+1)≤ξ )≥ 1-δ (n)=o(T). (2) We summarize the offline injection workflow in Algorithm 1; concrete allocation strategies are developed in the next section. Algorithm 1 Offline Injection Attack Input: clD cl, K, Π , T, [rmin,rmax][r_ ,r_ ], ξ and δ, Target Arm (K in our analysis) Output: Attacked warm-start log offD^off 1 Determine an injection plan (,)(n,y) satisfying Eq. (2); 2 Construct a fake log F(,)D^F(n,y) containing (i,yi,j)(i,y_i,j) for every i∈i and j=1,…,nij=1,…,n_i; 3 Set off←cl∥F(,)D^off cl \|D^F(n,y); 4 return offD^off; 4 Attack Strategies We first instantiate Algorithm 1 for UCB, then extend the strategy to suppression-bounded algorithms from Zeng et al. (2025). 4.1 Attack on UCB We consider the zero-tolerance case ξ=0ξ=0, where the attacker aims to make UCB select the target arm in every online round. The high-level idea is to (1) enlarge the gap between the target arm and the non-target arms, and (2) make the exploration bonus sufficiently small for each non-target arm, so that uK(t)>ui(t)u_K(t)>u_i(t) throughout the online phase. To ensure this, we seek to solve min,()subject touK(t)>ui(t),∀i<K,t∈on. _n,y (n) to u_K(t)>u_i(t), ∀ i<K,\ t ^on. Let R≜rmax−rminR r_ -r_ and assume Nicl≥1N_i cl≥ 1 for every arm. Write bi(t)=3σlogt/Ni(t)b_i(t)=3σ t/N_i(t). Our construction keeps the target arm’s empirical mean above a threshold z and bounds each non-target arm’s UCB index by z+bK(t)z+b_K(t). Specifically, we enforce ui(t)=μ^i(t)+bi(t)≤z+bK(t)<μ^K(t)+bK(t)=uK(t),∀i<K,t∈on.u_i(t)= μ_i(t)+b_i(t)≤ z+b_K(t)< μ_K(t)+b_K(t)=u_K(t), ∀ i<K,\ t ^on. For a confidence parameter δ∈(0,1/2)δ∈(0,1/2), define βδ(N)≜2σ2Nlogπ2KN23δ,μ¯K≜maxrmin,μ^Kcl−2βδ(NKcl). _δ(N) 2σ^2N π^2KN^23δ, μ_K \r_ , μ_K cl-2 _δ(N_K cl)\. Set ε≜μ¯K−rmin μ_K-r_ . We choose zT⋆=rmin+(18Rσ2(K−1)logT)1/3,z=rmin+maxzT⋆−rmin,minε,R/2.z_T =r_ + ( 18Rσ^2(K-1) TT )^1/3, z=r_ + \z_T -r_ ,\, \ ,R/2\ \. Write Bi=Nicl(μ^icl−rmin)B_i=N_i cl( μ_i cl-r_ ) and d(z)=z−rmin+3σlogT/Td(z)=z-r_ +3σ T/T. We set ni=⌈T(z−μ¯K)+rmax−z⌉+1,for i=K;⌈[(3σlogT+9σ2logT+4d(z)Bi2d(z))2−Nicl]+⌉,for i<K.n_i= \ aligned & T(z- μ_K)_+r_ -z +1, i=K;\\ & [ ( 3σ T+ 9σ^2 T+4d(z)B_i2d(z) )^2-N_i cl ]_+ , i<K. aligned . (3) Using these counts, construct the fake log in Algorithm 1 as F=(∥i=1K−1((i,rmin))j=1ni)∥((K,rmax))j=1nK.D^F= ( \|_i=1^K-1 ((i,r_ ) )_j=1^n_i ) \| ((K,r_ ) )_j=1^n_K. We analyze this construction under the following scaling assumptions. Assumption 4.1. R=Θ(1)R= (1), σ=Θ(1)σ= (1), and Nicl=Θ(1)N_i cl= (1) uniformly over i∈i . In particular, T0cl=Θ(K)=o(T)T_0 cl= (K)=o(T), so every attack satisfying ()=o(T)C(n)=o(T) has H=T(1−o(1))H=T(1-o(1)). Define ST≜T2/3(KlogT)1/3S_T T^2/3(K T)^1/3. We now give the theoretical guarantee of our attack strategy. Theorem 4.2. Fix δ∈(0,1/2)δ∈(0,1/2). Under Assumption 4.1, for all sufficiently large T, the above attack satisfies Pr(∑i=1K−1Nion(T+1)=0)≥1−δand()=(KlogT(ε∨(ST/T))2). ( _i=1^K-1N_i^on(T+1)=0 )≥ 1-δ (n)=O ( K T( (S_T/T))^2 ). Proof Sketch. If ε≤zT⋆−rmin ≤ z_T -r_ , then z=zT⋆z=z_T ; substituting into Eq. (3) gives nK=O(ST)n_K=O(S_T) and ∑i<Kni=O(ST) _i<Kn_i=O(S_T). If ε>zT⋆−rmin >z_T -r_ , then z≤μ¯Kz≤ μ_K and z−rmin=Θ(ε)z-r_ = ( ), giving nK=1n_K=1 and ∑i<Kni=O(KlogT/ε2) _i<Kn_i=O(K T/ ^2). Combining the two cases yields the stated cost bound. ∎ Theorem 4.3. Under Assumption 4.1, fix δ∈(0,1/2)δ∈(0,1/2). Let ΔK≜μK−rmin _K _K-r_ . For all sufficiently large T, every (0,δ)(0,δ)-successful bounded offline attack on UCB satisfies ()=Ω(KlogT(ΔK∨(ST/T))2)C(n)= ( K T( _K (S_T/T))^2 ) with probability at least 1−δ−1/T1-δ-1/T. Proof Sketch. Consider the final round T, when UCB selects the target on the zero-tolerance success event. By then, target injections have been diluted by Θ(T) (T) genuine observations. Writing uK(T)=rmin+ρu_K(T)=r_ +ρ, we have ρ≤ΔK+O(nK/T+logT/T)ρ≤ _K+O(n_K/T+ T/T) with high probability. Since the target is selected at T, every competitor satisfies ui(T)≤uK(T)u_i(T)≤ u_K(T). Its empirical mean is at least rminr_ , so its exploration bonus cannot exceed ρ, forcing Nicl+ni≥9σ2logT/ρ2N_i cl+n_i≥ 9σ^2 T/ρ^2. Combining these constraints on target and non-target injection costs and minimizing over ρ yields the cost lower bound. ∎ The upper and lower bounds depend on ε and ΔK _K, respectively. Their gap-dependent rates match when ε=Ω(ΔK) = ( _K). When ε=Ω(1) = (1), our upper and lower bounds match at Θ(KlogT) (K T). This cost order also agrees with the attack costs of Zeng et al. (2025). Our bounds identify ST/TS_T/T as the boundary scale for the target arm’s gap from the lower reward bound rminr_ . We refer to the regime ΔK=o(ST/T) _K=o(S_T/T) as the near-boundary regime. In this regime, we further sharpen the bounds to match in their leading constants, thereby establishing the asymptotic optimality of our construction. The optimal leading cost is obtained by minimizing the sum of the leading costs of target promotion and non-target suppression. This minimization yields the closed-form value ΛT≜3(9σ2(K−1)T2logT4R2)1/3=Θ(ST). _T 3 ( 9σ^2(K-1)T^2 T4R^2 )^1/3= (S_T). Corollary 4.4. Under Assumption 4.1, fix δ∈(0,1/2)δ∈(0,1/2) and assume ΔK=o(ΛT/T) _K=o( _T/T). For all sufficiently large T, our construction has ()≤(1+o(1))ΛTC(n)≤(1+o(1)) _T. And every (0,δ)(0,δ)-successful bounded offline attack on UCB satisfies Pr[()≥(1−o(1))ΛT]≥1−δ−1T. [C(n)≥(1-o(1)) _T ]≥ 1-δ- 1T. We next characterize the cost allocated to the target arm and show that this allocation is necessary for asymptotic optimality. Lemma 4.5. Under Assumption 4.1, fix δ∈(0,1/2)δ∈(0,1/2). For ε=o(ΛT/T) =o( _T/T), our construction satisfies nK=(23+o(1))ΛTn_K= ( 23+o(1) ) _T. If ΔK=o(ΛT/T) _K=o( _T/T), then for all sufficiently large T, every (o(ΛT),δ)(o( _T),δ)-successful bounded offline attack on UCB with ()≤(1+o(1))ΛTC(n)≤(1+o(1)) _T satisfies Pr[nK=(23+o(1))ΛT]≥1−δ−1T. \! [n_K= ( 23+o(1) ) _T ]≥ 1-δ- 1T. Remark 4.6. The 2:12:1 cost split balances target promotion against non-target suppression. In the near-boundary regime, raising the target’s empirical mean has a leading cost linear in its elevation above the lower reward bound. UCB’s Ni−1/2N_i^-1/2 exploration bonuses make each competitor’s required injection count, and hence their sum, decrease as the inverse square of that elevation. Minimizing the sum of these leading cost terms yields the 2:12:1 split between target and aggregate non-target costs. Appendix E compares this mechanism across algorithms. For larger tolerances ξ=O(ΛT)ξ=O( _T), Lemma A.2 establishes that near-boundary successful attacks with a deterministic O(ΛT)O( _T) cost bound must still incur a nonvanishing fraction of their total cost on the target arm. Proofs of Theorems 4.2 and 4.3 appear in Appendices A.1 and A.2, respectively; those of Corollary 4.4 and Lemma 4.5 appear in Appendix A.3. In the near-boundary regime, our construction is target-centric: for any fixed number of competitors, injections on the target account for most of the total cost with high probability, as required for leading-order optimality. This emphasis on favorable feedback for the target qualitatively reflects real-world manipulation practices, such as sellers purchasing positive reviews for their own products (He et al., 2022b). Comparison to Xu et al. (2021). In the near-boundary regime, the prescribed cost of Xu et al. (2021)’s UCB-based attack scales as Θ(KlogT/ΔK2) (K T/ _K^2). Consequently, the cost is Ω(ST) (S_T) when ΔK=(ST/T) _K=O(S_T/T), ceases to be sublinear when ΔK=(KlogT/T) _K=O( K T/T), and is undefined at ΔK=0 _K=0. In contrast, our attack remains applicable and covers this boundary case. 4.2 Extension to Suppression-Bounded Algorithms We extend the strategy to algorithms whose additional pulls of persistently dominated arms admit a high-probability bound. Definition 4.7 (Suppression-Bounded Algorithms from Zeng et al. (2025)). Fix a horizon T and a confidence level δ∈(0,1)δ∈(0,1). A bandit algorithm A is said to be suppression-bounded if, for any arm i, there exists a deterministic bound Bi(t,T,δ)B_i^A(t,T,δ) such that the following implication holds with probability at least 1−δ1-δ: if μ^i(s)<maxj∈μ^j(s),for all s∈t+1,…,T, μ_i(s)< _j μ_j(s), all s∈\t+1,…,T\, then Ni(T)−Ni(t)≤Bi(t,T,δ).N_i(T)-N_i(t)≤ B_i^A(t,T,δ). The quantity Bi(t,T,δ)B_i^A(t,T,δ) is referred to as the post-suppression pull bound for arm i. This is a conservative upper bound and Bi(t,T,δ)≥Bi(t,T′,δ)B_i^A(t,T,δ)≥ B_i^A(t,T ,δ) for all T′<T <T. Theorem 4.8 (Generic Suppression-Bounded Attack). Suppose A is suppression-bounded and write Bi≜Bi(T0cl,T,δ/K)B_i^A B_i^A(T_0 cl,T,δ/K). Assume Nicl≥1N_i cl≥ 1 for every arm. There exists a bounded offline attack that satisfies: Pr(∑i=1K−1Nion(T+1)≤∑i=1K−1Bi)≥1−2δ ( _i=1^K-1N_i^on(T+1)≤ _i=1^K-1B_i^A )≥ 1-2δ and ()≤(infρ∈(0,R)K+T(ρ−ε)+R−ρ+R−ρ∑i=1K−1(Nicl+Bi)).C(n) ( _ρ∈(0,R) \K+T (ρ- )_+R-ρ+ R-ρ _i=1^K-1 (N_i cl+B_i^A ) \ ). The construction raises the target’s empirical mean above rmin+ρr_ +ρ and keeps each non-target mean at or below this threshold. The target injections counteract dilution by genuine feedback. The non-target injections offset the clean observations and up to BiB_i^A online observations, even if each has reward rmaxr_ . Each such observation requires approximately (R−ρ)/ρ(R-ρ)/ρ compensating injections at rminr_ . Under Assumption 4.1, if ∑i<KBi=o(T) _i<KB_i^A=o(T), let AT≜∑i<K(Nicl+Bi)=o(T)A_T _i<K(N_i cl+B_i^A)=o(T). Choosing ρ=RAT/T/(1+AT/T)ρ=R A_T/T/(1+ A_T/T) and using ε≥0 ≥ 0 gives ()=O(K+TAT)=o(T).C(n)=O (K+ TA_T )=o(T). Consequently, H=T(1−o(1))H=T(1-o(1)) and NKon(T+1)/H=1−o(1)N_K^on(T+1)/H=1-o(1) with probability at least 1−2δ1-2δ, yielding a successful attack. UCB, TS, and ϵε-greedy all fall into the scope of suppression-bounded algorithms (Zeng et al., 2025). 5 Numerical Illustration 0.10.10.40.40.70.711⋅106· 10^6002244⋅105· 10^5Horizon TTAttack Cost (a) Attack Cost vs. Horizon T 5510102020303040405050000.20.20.40.40.60.60.80.811⋅106· 10^6Number of Arms KKAttack Cost (b) Attack Cost vs. Number of Arms K Clipped Suppression Total Attack Cost Figure 1: Attack Cost for UCB. 0.10.10.40.40.70.711⋅106· 10^6000.250.250.50.50.750.7511Horizon TTTarget-arm Ratio (a) Target-arm Selection Ratio vs. Horizon T 5510102020303040405050000.250.250.50.50.750.7511Number of Arms KKTarget-arm Ratio (b) Target-arm Selection Ratio vs. Number of Arms K NK/TN_K/T NKon/HN_K^on/H Clipped Suppression NK/TN_K/T Figure 2: Target-arm Selection Ratio for UCB. 0.10.12.52.5557.57.51010⋅106· 10^6111.051.051.11.1Horizon T/ΛTC/ _T K=5K=5 K=10K=10 K=15K=15 K=20K=20 K=25K=25 (a) Normalized Attack Cost vs. Horizon T 0.10.12.52.5557.57.51010⋅106· 10^61/31/32/32/3Horizon TTCost Share Target nK/n_K/C Non-target ∑i<Kni/ _i<Kn_i/C (b) Cost Share vs. Horizon T Figure 3: Near-Boundary Cost and Allocation for UCB. 0011223344556600224466⋅105· 10^5ΔK/(ST/T) _K/(S_T/T)Attack Cost (a) Attack Cost vs. ΔK/(ST/T) _K/(S_T/T) Ours Xu (2021) 001122334455660.30.30.50.50.70.70.90.911ΔK/(ST/T) _K/(S_T/T)Target-arm Ratio (b) Target-arm Selection Ratio vs. ΔK/(ST/T) _K/(S_T/T) Ours NK/TN_K/T Ours NKon/HN_K^on/H Xu (2021) NK/TN_K/T Figure 4: Comparison with Xu et al. (2021) for UCB. We evaluate our attacks on MovieLens-25M (Harper and Konstan, 2015), mapping ratings of at least four to one and the rest to zero. Each movie defines a Bernoulli arm with its empirical positive-rating rate as the mean; clean and online rewards are sampled independently with replacement. The target, Glitter (ID 47754775), has the smallest positive mean, μK=11/669 _K=11/669; competitors are the most-rated remaining movies. We use Nicl=5N_i cl=5, σ=0.5σ=0.5, and δ=0.05δ=0.05. Figure 1 compares our attack strategy with Clipped Suppression by varying T at K=10K=10 and K at T=106T=10^6. Our method consistently incurs a substantially lower attack cost. As T increases, the observed cost growth is consistent with the sublinear bound in Theorem 4.2. In contrast, Clipped Suppression intervenes whenever a non-target arm is pulled, so its attack cost is T−NKT-N_K and grows faster with T. The cost gap also increases as K grows. Figure 2 further shows that our method achieves lower attack cost while maintaining success. For our method, NKon/H=1N_K^on/H=1 in every repeat across all tested values of T and K, meaning that UCB selects the target arm in every online round after deployment. The overall ratio NK/TN_K/T, which also includes the warm-start samples, remains close to 11. In contrast, Clipped Suppression yields more non-target pulls. Even at T=106T=10^6, the learner selects non-target arms in nearly half of the rounds, and its target-arm selection ratio decreases further as K increases. We next illustrate the leading-order optimality and target-centric allocation predicted by our theory. As shown in Figure 3(a), for each fixed K, the normalized attack cost ()/ΛTC(n)/ _T approaches 11 as T increases, consistent with Corollary 4.4. In Figure 3(b), at K=10K=10, the target-arm cost share nK/()n_K/C(n) approaches 2/32/3, consistent with Lemma 4.5. We then compare our method with the attack of Xu et al. (2021) under the same experimental setting. When ΔK/(ST/T)<1 _K/(S_T/T)<1, the target lies within the boundary scale ST/TS_T/T, where attacks become challenging. Our attack maintains sublinear cost in this regime and makes UCB select the target arm in every online round after deployment with high probability. In contrast, the attack cost of Xu et al. (2021) scales as O(KlogT/ΔK2)O(K T/ _K^2) and grows rapidly as ΔK _K approaches zero. Hence, their points are omitted when this cost is undefined at ΔK=0 _K=0 or is at least T, while their target-arm selection ratio remains below 11 in the most challenging near-boundary settings. These experiments demonstrate the effectiveness of our method, with cost shares consistent with the theoretical analysis. We also provide experiments for TS and ϵε-greedy in Section B.2 and Section C.2, respectively. 6 Concluding Remarks In the near-boundary regime, target-centric allocation is necessary for successful UCB attacks with tolerance ξ=O(ST)ξ=O(S_T) and a deterministic O(ST)O(S_T) cost cap: the target must receive a nonvanishing share of the injections on the high-probability event of our lower bound. Our UCB construction attains this cost scale in the near-boundary regime. We also give constructions for TS and ϵε-greedy in the Appendix, while the suppression-bounded analysis covers a broader class of learners. However, our analysis assumes a learner that uncritically trusts all offline data. A possible direction for future work is to investigate whether discounting, filtering, or auditing offline observations can mitigate the effects of favorable target injections, and how such defenses trade off the benefits of a clean warm start against robustness to corrupted initialization. Furthermore, our cost and allocation results assume a small clean offline log. More clean observations make empirical means harder to shift but also reduce exploration uncertainty, potentially changing both the optimal attack cost and its allocation. Characterizing how these competing effects depend on the size and distribution of clean observations across arms is an interesting direction for future work. References Agrawal and Goyal (2017) S. Agrawal and N. Goyal Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM) 64 (5), p. 1–24. Cited by: §B.1. Banerjee et al. (2022) S. Banerjee, S. R. Sinclair, M. Tambe, L. Xu, and C. L. Yu Artificial replay: a meta-algorithm for harnessing historical data in bandits. arXiv preprint arXiv:2210.00025. Cited by: §1. Bogunovic et al. (2022) I. Bogunovic, Z. Li, A. Krause, and J. Scarlett A robust phased elimination algorithm for corruption-tolerant gaussian process bandits. Advances in Neural Information Processing Systems 35, p. 23951–23964. Cited by: §1.2. Bogunovic et al. (2021) I. Bogunovic, A. Losalka, A. Krause, and J. Scarlett Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, p. 991–999. Cited by: §1.2. Bubeck and Cesa-Bianchi (2012) S. Bubeck and N. Cesa-Bianchi Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning 5 (1), p. 1–122. Cited by: §2. Garcelon et al. (2020) E. Garcelon, B. Roziere, L. Meunier, J. Tarbouriech, O. Teytaud, A. Lazaric, and M. Pirotta Adversarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems 33, p. 14362–14373. Cited by: §1.2. Gupta et al. (2019) A. Gupta, T. Koren, and K. Talwar Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, p. 1562–1578. Cited by: §1.2. Harper and Konstan (2015) F. M. Harper and J. A. Konstan The movielens datasets: history and context. Acm transactions on interactive intelligent systems (tiis) 5 (4), p. 1–19. Cited by: 4th item, §5. He et al. (2022a) J. He, D. Zhou, T. Zhang, and Q. Gu Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in neural information processing systems 35, p. 34614–34625. Cited by: §1.2. He et al. (2022b) S. He, B. Hollenbeck, G. Overgoor, D. Proserpio, and A. Tosyali Detecting fake-review buyers using network structure: direct evidence from amazon. Proceedings of the National Academy of Sciences 119 (47), p. e2211932119. External Links: Document Cited by: §1, §4.1. Hosseini et al. (2026) S. M. H. Hosseini, A. Najafi, and M. Baghshah Efficient adversarial attacks on high-dimensional offline bandits. In International Conference on Learning Representations, Vol. 2026, p. 37587–37612. Cited by: §1.2, Table 1. Jun et al. (2018) K. Jun, L. Li, Y. Ma, and J. Zhu Adversarial attacks on stochastic bandits. Advances in neural information processing systems 31. Cited by: Appendix A, §1.2, Table 1, §1, §1, §2. Kang et al. (2023) Y. Kang, C. Hsieh, and T. C. M. Lee Robust lipschitz bandits to adversarial corruptions. Advances in Neural Information Processing Systems 36, p. 10897–10908. Cited by: §1.2. Kapoor et al. (2019) S. Kapoor, K. K. Patel, and P. Kar Corruption-tolerant bandit learning. Machine Learning 108 (4), p. 687–715. Cited by: §1.2. Li et al. (2021) Y. Li, H. Xie, Y. Lin, and J. C. Lui Unifying offline causal inference and online bandit learning for data driven decision. In Proceedings of the Web Conference 2021, p. 2291–2303. Cited by: §1. Liu and Shroff (2019) F. Liu and N. Shroff Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, p. 4042–4050. Cited by: 1st item, §1.2, Table 1, §1. Lykouris et al. (2018) T. Lykouris, V. Mirrokni, and R. Paes Leme Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, p. 114–122. Cited by: §1.2. Ma and Zhou (2023) Y. Ma and Z. Zhou Adversarial attacks on adversarial bandits. arXiv preprint arXiv:2301.12595. Cited by: §1.2. Oetomo et al. (2023) B. Oetomo, R. M. Perera, R. Borovica-Gajic, and B. I. Rubinstein Cutting to the chase with warm-start contextual bandits. Knowledge and Information Systems 65 (9), p. 3533–3565. Cited by: §1. Shivaswamy and Joachims (2012) P. Shivaswamy and T. Joachims Multi-armed bandit problems with history. In Artificial intelligence and statistics, p. 1046–1054. Cited by: §1. Wang et al. (2022) H. Wang, H. Xu, and H. Wang When are linear stochastic bandits attackable?. In International Conference on Machine Learning, p. 23254–23273. Cited by: §1.2. Xu and Li (2021) H. Xu and J. Li Simple combinatorial algorithms for combinatorial bandits: corruptions and approximations. In Uncertainty in Artificial Intelligence, p. 1444–1454. Cited by: §1.2. Xu et al. (2021) Y. Xu, B. Kumar, and J. D. Abernethy Observation-free attacks on stochastic bandits. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. W. Vaughan (Eds.), Vol. 34, p. 22550–22561. Cited by: §1.2, Table 1, §4.1, §4.1, Figure 4, §5. Zeng et al. (2025) Q. Zeng, E. He, R. Hoffmann, X. Wang, and J. Zuo Practical adversarial attacks on stochastic bandits via fake data injection. arXiv preprint arXiv:2505.21938. Cited by: §B.1, §B.1, Lemma C.1, 3rd item, §1.2, §1.2, Table 1, §1, §1, §1, §4.1, §4.2, Definition 4.7, §4. Zuo et al. (2023) J. Zuo, Z. Zhang, Z. Wang, S. Li, M. Hajiesmaili, and A. Wierman Adversarial attacks on online learning to rank with click feedback. Advances in Neural Information Processing Systems 36, p. 41675–41692. Cited by: §1.2, §1. Zuo (2024) S. Zuo Near optimal adversarial attacks on stochastic bandits and defenses with smoothed responses. In International Conference on Artificial Intelligence and Statistics, p. 2098–2106. Cited by: §1.2, Table 1, §1, §1. Contents 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Warm-Start Bandit Setup 3 Offline Attack Model 3.1 Attack Setting and Attack Cost 4 Attack Strategies 4.1 Attack on UCB 4.2 Extension to Suppression-Bounded Algorithms 5 Numerical Illustration 6 Concluding Remarks References A Proofs for UCB A.1 Upper Bound Proof A.2 Lower Bound Proof A.3 Optimality Proofs B Analysis for Thompson Sampling B.1 Attack Strategy B.2 Numerical Illustration C Analysis for ϵε-Greedy C.1 Attack Strategy C.2 Numerical Illustration D Analysis of Suppression-Bounded Algorithms E Exploration and Allocation Appendix A Proofs for UCB For δ∈(0,1)δ∈(0,1), recall that βδ(N)=2σ2Nlogπ2KN23δ. _δ(N)= 2σ^2N π^2KN^23δ. Define the event ℰδ≜∀i∈,∀t∈on,|μ^icl(t)−μi|<βδ(Nicl(t)).E_δ \∀ i ,\ ∀ t ^on, | μ_i cl(t)- _i |< _δ(N_i cl(t)) \. By Jun et al. [2018, Lemma 1], Pr(ℰδ)≥1−δ (E_δ)≥ 1-δ. The radius is decreasing on the positive integers when K≥2K≥ 2 and δ∈(0,1)δ∈(0,1). On ℰδE_δ, we have 0≤ε≤ΔK0≤ ≤ _K, and μ^Kcl(t) μ_K cl(t) ≥maxrmin,μK−βδ(NKcl(t)) ≥ \r_ , _K- _δ(N_K cl(t))\ ≥maxrmin,μ^Kcl−2βδ(NKcl)=μ¯K(∀t∈on). ≥ \r_ , μ_K cl-2 _δ(N_K cl)\= μ_K (∀ t ^on). A.1 Upper Bound Proof Under the event ℰδE_δ and by Eq. (3), at round t=T0+1t=T_0+1, we have μ^K(t)≥nKrmax+NKcl(t)μ¯KnK+NKcl(t)≥nKrmax+Tμ¯KnK+T>z. μ_K(t)≥ n_Kr_ +N_K cl(t) μ_Kn_K+N_K cl(t)≥ n_Kr_ +T μ_Kn_K+T>z. Since NK(t)≤t−1N_K(t)≤ t-1 and logt/(t−1) t/(t-1) decreases for t>1t>1, we have uK(t)=μ^K(t)+3σlogtNK(t)>z+3σlogTTu_K(t)= μ_K(t)+3σ tN_K(t)>z+3σ TT. Similarly, for every non-target arm i<Ki<K, ui(t)≤z+3σlogT.u_i(t)≤ z+3σ TT. Together, these inequalities imply that uK(t)>ui(t),∀i<K,u_K(t)>u_i(t), ∀ i<K, and hence UCB selects the target arm at round t. Repeating the same argument inductively from round T0+1T_0+1 through round T shows that UCB selects the target arm in every online round. Proof of Theorem 4.2. Write ρ=z−rminρ=z-r_ , rT=ST/Tr_T=S_T/T, and ρT⋆=zT⋆−rmin=Θ(rT) _T =z_T -r_ = (r_T). We have nK=T(ρ−ε)+R−ρ+O(1)≤TρR−ρ+2.n_K= T(ρ- )_+R-ρ+O(1)≤ TρR-ρ+2. Since d(rmin+ρ)=ρ+3σlogT/T∼ρd(r_ +ρ)=ρ+3σ T/T ρ and Bi,Nicl=O(1)B_i,N_i cl=O(1) uniformly, Eq. (3) gives ni=(1+o(1))9σ2logTρ2(i<K).n_i=(1+o(1)) 9σ^2 Tρ^2 (i<K). (1) If ε≤ρT⋆ ≤ _T , then ρ=ρT⋆ρ= _T , and the preceding estimates give nK=O(TrT)n_K=O(Tr_T) and ni=O(logT/rT2)n_i=O( T/r_T^2) uniformly over i<Ki<K. Their sum is O(ST)O(S_T), the asserted scale since ε=O(rT) =O(r_T). (2) If ε>ρT⋆ > _T , then ρ=minε,R/2≤ερ= \ ,R/2\≤ and ρ=Θ(ε)ρ= ( ). Thus nK=1n_K=1, while Eq. (3) gives ni=O(1+Bi/ρ+σ2logT/ρ2)=O(logT/ε2)(i<K).n_i=O (1+B_i/ρ+σ^2 T/ρ^2 )=O( T/ ^2) (i<K). Combining these two cases yields the result. ∎ A.2 Lower Bound Proof Lemma A.1. Under Assumption 4.1, there exist constants c0,c1,c2,c3>0c_0,c_1,c_2,c_3>0 such that the following holds for all sufficiently large T. On ℰ1/TE_1/T, every bounded offline UCB attack realization with at most ξ≥0ξ≥ 0 non-target online pulls and ()+ξ≤T/2C(n)+ξ≤ T/2 admits a ρ>0ρ>0 satisfying nK n_K ≥c1T(ρ−ΔK−c0logT/T)+, ≥ c_1T(ρ- _K-c_0 T/T)_+, ∑i<Kni _i<Kn_i ≥(c2KlogTρ2−ξ−c3K)+. ≥ (c_2 K Tρ^2-ξ-c_3K )_+. Proof. Since H−ξ≥T/2−T0cl>0H-ξ≥ T/2-T_0 cl>0 for large T, the target is selected in at least one online round. Let t⋆t be its last such round and set ρ=uK(t⋆)−rmin>0ρ=u_K(t )-r_ >0. We have NK(t⋆) N_K(t ) =NKoff+NKon(T+1)−1, =N_K^off+N_K^on(T+1)-1, NKcl(t⋆) N_K cl(t ) =NKcl+NKon(T+1)−1. =N_K cl+N_K^on(T+1)-1. The bound NKon(T+1)≥H−ξN_K^on(T+1)≥ H-ξ gives NKcl(t⋆)≥T/3N_K cl(t )≥ T/3 for large T. Since all rounds after t⋆t select non-target arms, we also have t⋆≥T−ξ≥T/2t ≥ T-ξ≥ T/2. On ℰ1/TE_1/T, the genuine target observations have empirical mean at most μK+β1/T(NKcl(t⋆)) _K+ _1/T(N_K cl(t )), and each injected target reward is at most rmaxr_ . Meanwhile, every non-target empirical mean is at least rminr_ , and its index is at most the selected target’s index rmin+ρr_ +ρ. These comparisons give ρ ρ ≤ΔK+(R−ΔK)nKNK(t⋆)+β1/T(NKcl(t⋆))+3σlogt⋆NK(t⋆), ≤ _K+ (R- _K)n_KN_K(t )+ _1/T(N_K cl(t ))+3σ t N_K(t ), (4) Ni(t⋆)≥9σ2logt⋆ρ2(i<K). N_i(t )≥ 9σ^2 t ρ^2 (i<K). The concentration radius and target exploration bonus are both O(logT/T)O( T/T) for large T. Thus the first inequality gives ρ≤ΔK+3RnKT+c0logT.ρ≤ _K+ 3Rn_KT+c_0 TT. Rearranging and using R=Θ(1)R= (1) and nK≥0n_K≥ 0 yields the target cost constraint. Write M=∑i<KniM= _i<Kn_i. Summing the second inequality and using Ni(t⋆)=Nicl+ni+Nion(t⋆)N_i(t )=N_i cl+n_i+N_i^on(t ) and ∑i<KNion(t⋆)≤ξ _i<KN_i^on(t )≤ξ gives M+T0cl+ξ≥∑i<KNi(t⋆)≥9σ2(K−1)logt⋆ρ2.M+T_0 cl+ξ≥ _i<KN_i(t )≥ 9σ^2(K-1) t ρ^2. Using K−1≥K/2K-1≥ K/2, t⋆≥T/2t ≥ T/2, T0cl=O(K)T_0 cl=O(K), and M≥0M≥ 0 yields the non-target cost constraint with uniform constants c2,c3>0c_2,c_3>0. ∎ Proof of Theorem 4.3. Work on the intersection of the attack’s success event with ℰ1/TE_1/T, which has probability at least 1−δ−1/T1-δ-1/T by a union bound. Recall rT=ST/Tr_T=S_T/T and set aT=(ΔK+c0logT/T)∨rTa_T=( _K+c_0 T/T) r_T, with c0c_0 from Lemma A.1. On paths with ()≤T/2C(n)≤ T/2, add the two constraints in Lemma A.1 at ξ=0ξ=0. Enlarging the offset to aTa_T only decreases the linear term, giving ()+c3K≥infρ>0c1T(ρ−aT)++c2KlogTρ2.C(n)+c_3K≥ _ρ>0 \c_1T(ρ-a_T)_++ c_2K Tρ^2 \. (1) If ρ≤2aTρ≤ 2a_T, the inverse-square term is at least c2KlogT/(4aT2)c_2K T/(4a_T^2). (2) Otherwise, the linear term is at least c1TaT≥c1KlogT/aT2c_1Ta_T≥ c_1K T/a_T^2, since aT≥rTa_T≥ r_T and TrT3=KlogTTr_T^3=K T. Both cases give Ω(KlogT/(ΔK∨rT)2) (K T/( _K r_T)^2), because aT∼ΔK∨rTa_T _K r_T by logT/T=o(rT) T/T=o(r_T). ∎ A.3 Optimality Proofs Proof of Corollary 4.4. Upper bound. Recall ρT⋆=zT⋆−rmin _T =z_T -r_ . The cost expansions in Appendix A.1 give, uniformly over clean logs and including rounding, ((zT⋆))≤(1+o(1))TρT⋆R+9σ2(K−1)logT(ρT⋆)2=(1+o(1))ΛT.C(n(z_T ))≤(1+o(1)) \ T _T R+ 9σ^2(K-1) T( _T )^2 \=(1+o(1)) _T. (1) If ε≤ρT⋆ ≤ _T , our construction uses z=zT⋆z=z_T . (2) Otherwise, the target count is one at both thresholds, and raising z only reduces non-target counts. Lower bound. Consider a (0,δ)(0,δ)-successful attack on the intersection of its success event with ℰ1/TE_1/T, which has probability at least 1−δ−1/T1-δ-1/T. It suffices to consider paths with ()≤2ΛTC(n)≤ 2 _T, since larger costs already satisfy the conclusion. Write M=∑i<KniM= _i<Kn_i. Zero tolerance gives NKon(T+1)=HN_K^on(T+1)=H and t⋆=Tt =T. Since ()+T0cl=o(T)C(n)+T_0 cl=o(T), the count identities in the proof of Lemma A.1 give NK(T),NKcl(T)=T(1−o(1))N_K(T),N_K cl(T)=T(1-o(1)). Set ρ=uK(T)−rminρ=u_K(T)-r_ . Since ΔK=o(ΛT/T) _K=o( _T/T) and logT/T=o(ΛT/T) T/T=o( _T/T), the index constraints in Eq. (4) imply, uniformly over these paths, ρ≤RT(nK+o(ΛT)),M+T0cl≥9σ2(K−1)logTρ2.ρ≤ RT (n_K+o( _T) ), M+T_0 cl≥ 9σ^2(K-1) Tρ^2. Eliminating ρ gives (nK+o(ΛT))2(M+T0cl)≥9σ2(K−1)T2logTR2=4ΛT327. (n_K+o( _T) )^2(M+T_0 cl)≥ 9σ^2(K-1)T^2 TR^2= 4 _T^327. Since nK,M=O(ΛT)n_K,M=O( _T) and T0cl=o(ΛT)T_0 cl=o( _T), this yields nK2M≥(1−o(1))4ΛT327.n_K^2M≥(1-o(1)) 4 _T^327. (5) AM–GM applied to nK/2,nK/2,Mn_K/2,n_K/2,M gives (1−o(1))4ΛT327≤nK2M≤4(nK+M)327=4()327,(1-o(1)) 4 _T^327≤ n_K^2M≤ 4(n_K+M)^327= 4C(n)^327, so ()≥(1−o(1))ΛTC(n)≥(1-o(1)) _T on the stated event. ∎ Proof of Lemma 4.5. ε=o(ΛT/T) =o( _T/T) gives ε=o(ρT⋆) =o( _T ) and hence z=zT⋆z=z_T . Eq. (3) then gives nK=T(ρT⋆−ε)R−ρT⋆+O(1)∼TρT⋆R=23ΛT.n_K= T( _T - )R- _T +O(1) T _T R= 23 _T. This is deterministic under the stated clean-log condition, which follows from ΔK=o(ΛT/T) _K=o( _T/T) on ℰδE_δ because 0≤ε≤ΔK0≤ ≤ _K. Necessity. Work on the intersection of the attack’s success event with ℰ1/TE_1/T, which has probability at least 1−δ−1/T1-δ-1/T. Write M=∑i<KniM= _i<Kn_i, let t⋆t be the last online round selecting the target, and set ρ=uK(t⋆)−rminρ=u_K(t )-r_ . Since ξ=o(ΛT)ξ=o( _T) and ()≤(1+o(1))ΛTC(n)≤(1+o(1)) _T, we still have t⋆≥T−ξt ≥ T-ξ, logt⋆∼logT t T, and NK(t⋆),NKcl(t⋆)=T(1−o(1))N_K(t ),N_K cl(t )=T(1-o(1)). The preceding product argument therefore applies with M+T0cl+ξM+T_0 cl+ξ in the non-target constraint. Because T0cl+ξ=o(ΛT)T_0 cl+ξ=o( _T), eliminating ρ again yields Eq. (5). Together with nK2M≤4()3/27n_K^2M≤ 4C(n)^3/27 and the cost cap, this implies ()∼ΛTC(n) _T. Set x=nK/()∈[0,1]x=n_K/C(n)∈[0,1]. Dividing the product bound by ()3C(n)^3 gives 427−o(1)≤x2(1−x)≤427. 427-o(1)≤ x^2(1-x)≤ 427. The identity 427−x2(1−x)=(x−23)2(x+13)≥13(x−23)2 427-x^2(1-x)= (x- 23 )^2 (x+ 13 )≥ 13 (x- 23 )^2 forces x=2/3+o(1)x=2/3+o(1), and hence nK=x()=(23+o(1))ΛT.n_K=xC(n)= ( 23+o(1) ) _T. ∎ Lemma A.2 (Necessary Target Cost). Under Assumption 4.1, fix δ∈(0,1/2)δ∈(0,1/2) and assume ΔK=o(ΛT/T) _K=o( _T/T) and ξ=O(ΛT)ξ=O( _T). For all sufficiently large T, every (ξ,δ)(ξ,δ)-successful bounded offline attack on UCB with a deterministic O(ΛT)O( _T) cost bound satisfies nK=Ω(ΛT),nK()=Ω(1)n_K= ( _T), n_KC(n)= (1) with probability at least 1−δ−1/T1-δ-1/T. Proof. Work on the intersection of success with ℰ1/TE_1/T, which has probability at least 1−δ−1/T1-δ-1/T. Since ()+ξ=O(ΛT)=o(T)C(n)+ξ=O( _T)=o(T), apply Lemma A.1 and use its notation. Since ∑i<Kni+ξ+c3K=O(ΛT) _i<Kn_i+ξ+c_3K=O( _T), the non-target cost constraint gives ρ=Ω(ΛT/T)ρ= ( _T/T). With ΔK,logT/T=o(ΛT/T) _K, T/T=o( _T/T), the target cost constraint gives nK=Ω(ΛT)n_K= ( _T). The deterministic cost bound then yields nK/()=Ω(1)n_K/C(n)= (1). ∎ Appendix B Analysis for Thompson Sampling B.1 Attack Strategy We consider the Thompson Sampling (TS) algorithm of Zeng et al. [2025], based on the (α,ψ)(α,ψ) framework of Agrawal and Goyal [2017]. In each online round, it independently samples νi(t)∼(μ^i(t),1/Ni(t)) _i(t) ( μ_i(t),1/N_i(t)) for every arm and selects at=argmaxi∈νi(t).a_t= _i _i(t). For δ∈(0,1)δ∈(0,1), define γ(t)≜2logπ2Kt23δ,ℱ≜∀i∈,∀t∈on,|νi(t)−μ^i(t)|<γ(t)Ni(t).γ(t) 2 π^2Kt^23δ, \∀ i ,\ ∀ t ^on,\ | _i(t)- μ_i(t)|< γ(t) N_i(t) \. By Zeng et al. [2025, Lemma B.1], Pr(ℱ)≥1−δ (F)≥ 1-δ. Fix z∈(rmin,rmax)z∈(r_ ,r_ ), write γ=γ(T)γ=γ(T), and recall Bi=Nicl(μ^icl−rmin)B_i=N_i cl( μ_i cl-r_ ). Inject rmaxr_ on the target and rminr_ on each non-target arm, with counts ni=⌈[(γ+γ2+4(z−rmin)Bi2(z−rmin))2−Nicl]+⌉,i<K,n_i= [ ( γ+ γ^2+4(z-r_ )B_i2(z-r_ ) )^2-N_i cl ]_+ , i<K, (6) and nK=1+minn∈ℤ≥0:(rmax−z)n≥(z−μ¯K)m+γn+m,∀m∈[NKcl,T].n_K=1+ \n _≥ 0:\;(r_ -z)n≥(z- μ_K)m+γ n+m,\ ∀ m∈[N_K cl,T] \. (7) Lemma B.1 (TS Threshold Certificate). For any z∈(rmin,rmax)z∈(r_ ,r_ ), the above construction makes TS select the target in every online round on ℰδ∩ℱE_δ . Proof. On ℰδ∩ℱE_δ , suppose every preceding online pull selected the target. Applying the count constraints with m=NKcl(t)m=N_K cl(t) gives νK(t) _K(t) >nKrmax+NKcl(t)μ¯KnK+NKcl(t)−γnK+NKcl(t)≥z, > n_Kr_ +N_K cl(t) μ_Kn_K+N_K cl(t)- γ n_K+N_K cl(t)≥ z, νi(t) _i(t) <rmin+BiNicl+ni+γNicl+ni≤z(i<K). <r_ + B_iN_i cl+n_i+ γ N_i cl+n_i≤ z (i<K). And hence νK(t)>νi(t) _K(t)> _i(t). Induction from the first online round proves the claim. ∎ Theorem B.2 (Attack Cost Upper Bound and Allocation for TS). Fix δ∈(0,1/2)δ∈(0,1/2). Under Assumption 4.1, define ΛTts≜3((K−1)γ(T)2T24R2)1/3=Θ(ST). _T ts 3 ( (K-1)γ(T)^2T^24R^2 )^1/3= (S_T). The following hold for all sufficiently large T. If ΔK=o(ST/T) _K=o(S_T/T), there exists a threshold for the above allocation satisfying Pr(∑i=1K−1Nion(T+1)=0)≥1−2δand()≤(1+o(1))ΛTts. ( _i=1^K-1N_i^on(T+1)=0 )≥ 1-2δ (n)≤(1+o(1)) _T ts. Moreover, under ℰδE_δ, nK=(23+o(1))ΛTtsandni=(1+o(1))ΛTts3(K−1) for i<K.n_K= ( 23+o(1) ) _T ts n_i=(1+o(1)) _T ts3(K-1) for i<K. Proof of Theorem B.2. For ρ=z−rmin=Θ(ST/T)ρ=z-r_ = (S_T/T), expanding the count formulas gives, uniformly over clean logs and including rounding, nK=T(ρ−ε)+R+O(Tρ2+γT+1),ni=(1+o(1))γ2ρ2(i<K).n_K= T(ρ- )_+R+O(Tρ^2+γ T+1), n_i=(1+o(1)) γ^2ρ^2 (i<K). The target lower bound follows by setting m=Tm=T in its constraint; the upper bound uses (ρ−ε)m≤T(ρ−ε)+(ρ- )m≤ T(ρ- )_+ and n+m≤T+n/(2T) n+m≤ T+n/(2 T). The error is o(ST)o(S_T). Choose ρ=(2R(K−1)γ2T)1/3,TρR=23ΛTts,(K−1)γ2ρ2=13ΛTts.ρ= ( 2R(K-1)γ^2T )^1/3, TρR= 23 _T ts, (K-1)γ^2ρ^2= 13 _T ts. Since (ρ−ε)+≤ρ(ρ- )_+≤ρ, the cost bound holds deterministically and T0cl+()=o(T)T_0 cl+C(n)=o(T). On ℰδE_δ, 0≤ε≤ΔK=o(ρ)0≤ ≤ _K=o(ρ), giving the stated allocation. Finally, Lemma B.1 and Pr(ℰδ∩ℱ)≥1−2δ (E_δ )≥ 1-2δ give the success guarantee. ∎ B.2 Numerical Illustration 0.10.10.40.40.70.711⋅106· 10^6001122⋅105· 10^5Horizon TTAttack Cost (a) Attack Cost vs. Horizon T 55101020203030404050500022446688⋅105· 10^5Number of Arms KKAttack Cost (b) Attack Cost vs. Number of Arms K Clipped Suppression Total Attack Cost Figure 5: Attack Cost for TS. 0.10.10.40.40.70.711⋅106· 10^6000.250.250.50.50.750.7511Horizon TTTarget-arm Ratio (a) Target-arm Selection Ratio vs. Horizon T 5510102020303040405050000.250.250.50.50.750.7511Number of Arms KKTarget-arm Ratio (b) Target-arm Selection Ratio vs. Number of Arms K NK/TN_K/T NKon/HN_K^on/H Clipped Suppression NK/TN_K/T Figure 6: Target-arm Selection Ratio for TS. 0.10.12.52.5557.57.51010⋅106· 10^6111.11.11.21.21.31.3Horizon T/ΛTtsC/ _T ts K=5K=5 K=10K=10 K=15K=15 K=20K=20 K=25K=25 (a) Normalized Attack Cost vs. Horizon T 0.10.12.52.5557.57.51010⋅106· 10^61/31/32/32/3Horizon TTCost Share Target nK/n_K/C Non-target ∑i<Kni/ _i<Kn_i/C (b) Cost Share vs. Horizon T Figure 7: Near-Boundary Cost and Allocation for TS. We repeat the Clipped Suppression comparisons and near-boundary experiments of Section 5 with TS, and numerically minimize the continuous total count defined by Eq. (6) and Eq. (7) before rounding. All other settings and reporting conventions are unchanged. Figures 5 and 6 show exclusively target online pulls for our attack in every repeat. Its cost is lower than Clipped Suppression except at the smallest arm count, where the baseline costs less but still pulls non-target arms. Figure 7 shows normalized cost approaching one and cost shares approaching 2/32/3 for the target and 1/31/3 for the non-target arms collectively, consistent with the TS construction. Every repeat has zero non-target online pulls. Appendix C Analysis for ϵε-Greedy C.1 Attack Strategy At round s, ϵε-greedy explores with probability ϵs _s by choosing uniformly from all K arms; otherwise it selects an empirical-mean maximizer. The schedule ϵss=1T⊂[0,1]\ _s\_s=1^T⊂[0,1] is deterministic, and exploration randomization is independent across rounds. For simplicity, assume that the entire offline log is constructed by the attacker, so Nicl=0N_i cl=0 for every arm and T0=()T_0=C(n). For 0≤t<T0≤ t<T and δ∈(0,1)δ∈(0,1), define the exploration bound Bieg(t,T,δ)=∑s=t+1TϵsK+2(∑s=t+1TϵsK)log1δ+13log1δ.B_i eg(t,T,δ)= _s=t+1^T _sK+ 2 ( _s=t+1^T _sK ) 1δ+ 13 1δ. Lemma C.1 (Corollary C.1 of Zeng et al. [2025]). Fix T0≤t<T_0≤ t<T and δ∈(0,1)δ∈(0,1). With probability at least 1−δ1-δ, the following implication holds: if μ^i(s)<maxjμ^j(s) μ_i(s)< _j μ_j(s) for all s∈t+1,…,Ts∈\t+1,…,T\, then Nion(T+1)−Nion(t+1)≤Bieg(t,T,δ).N_i^on(T+1)-N_i^on(t+1)≤ B_i eg(t,T,δ). Fix δ∈(0,1/2)δ∈(0,1/2), write B=⌈Bieg(0,T,δ/(K−1))⌉B= B_i eg(0,T,δ/(K-1)) for short, and define rTeg=R(K−1)BT.r_T eg=R (K-1)BT. Inject reward rmaxr_ on the target and rminr_ on each non-target arm, with nK=⌈T(K−1)B⌉+1,ni=⌈TBK−1⌉(i<K).n_K= T(K-1)B +1, n_i= TBK-1 (i<K). Theorem C.2 (ϵε-Greedy Upper Bound). Fix δ∈(0,1/2)δ∈(0,1/2). Suppose R=Θ(1)R= (1), ∑s=1Tϵs+Klog(K/δ)=o(T) _s=1^T _s+K (K/δ)=o(T). For all sufficiently large T, the above attack satisfies Pr(∑i<KNion(T+1)≤(K−1)B)≥1−δ,()=(2+o(1))T(K−1)B. ( _i<KN_i^on(T+1)≤(K-1)B )≥ 1-δ, (n)=(2+o(1)) T(K-1)B. All greedy online decisions select the target on the same event. Proof. The definition of B gives (K−1)B=O(∑sϵs+Klog(K/δ))=o(T)(K-1)B=O( _s _s+K (K/δ))=o(T), while rounding yields 2T(K−1)B<()≤2T(K−1)B+K+1.2 T(K-1)B<C(n)≤ 2 T(K-1)B+K+1. Since B≥1B≥ 1 and K=o(T)K=o(T), the rounding term is lower order, proving the cost bound and T0=()<T_0=C(n)<T eventually. The Bernoulli bound underlying Lemma C.1 and a union bound ensure at most B potential exploratory selections per non-target arm over rounds 1,…,T1,…,T, with probability at least 1−δ1-δ. On this event, if preceding greedy decisions selected the target, bounded rewards and nKni>TBn_Kn_i>TB give μ^i(s)≤rmin+RBni+B<rmin+RnKnK+T≤μ^K(s). μ_i(s)≤ r_ + RBn_i+B<r_ + Rn_Kn_K+T≤ μ_K(s). Induction from the first online round makes every greedy decision select the target, so all non-target pulls are exploratory and total at most (K−1)B(K-1)B. ∎ For ϵs=min1,cK/s _s= \1,cK/s\ with fixed c>0c>0 and KlogT=o(T)K T=o(T), this gives rTeg=Θ(KlogT/T)r_T eg= ( K T/T), cost O(TKlogT)O( TK T), and (ξ,δ)(ξ,δ)-success with ξ(T)=O(KlogT)ξ(T)=O(K T). C.2 Numerical Illustration We use Bernoulli rewards with non-target means equally spaced in [0.2,0.8][0.2,0.8] and target mean rTeg/logT>0r_T eg/ T>0, with ϵs=min1,K/s _s= \1,K/s\ and δ=0.05δ=0.05. Online statistics use 50 independent runs per configuration; shaded bands show one sample standard deviation. Greedy ties are broken by arm index. Clipped Suppression sets every non-target online reward to zero and counts each such round as attack cost. It has no offline log and initializes with one online pull per arm, starting with the target. Figures 8 and 9 vary T at K=10K=10 and K at T=106T=10^6. Our attack has lower mean costs and higher mean target-arm selection ratios. All greedy decisions selected the target; the remaining non-target pulls were exploratory and stayed below the theoretical bound. 0.10.10.40.40.70.711⋅106· 10^6000.50.511⋅106· 10^6Horizon TTAttack Cost (a) Attack Cost vs. Horizon T 5510102020303040405050000.50.511⋅106· 10^6Number of Arms KKAttack Cost (b) Attack Cost vs. Number of Arms K Clipped Suppression Total Attack Cost Figure 8: Attack Cost for ϵε-greedy. 0.10.10.40.40.70.711⋅106· 10^6000.250.250.50.50.750.7511Horizon TTTarget-arm Ratio (a) Target-arm Selection Ratio vs. Horizon T 5510102020303040405050000.250.250.50.50.750.7511Number of Arms KKTarget-arm Ratio (b) Target-arm Selection Ratio vs. Number of Arms K NK/TN_K/T NKon/HN_K^on/H Clipped Suppression NK/TN_K/T Figure 9: Target-arm Selection Ratio for ϵε-greedy. Appendix D Analysis of Suppression-Bounded Algorithms Proof of Theorem 4.8. Fix ρ∈(0,R)ρ∈(0,R) and write Bi=Bi(T0cl,T,δ/K)B_i^A=B_i^A(T_0 cl,T,δ/K). Choose nK=⌈T(ρ−ε)+R−ρ⌉+1,ni=⌈R−ρ(Nicl+Bi)⌉, for all i<K.n_K= T (ρ- )_+R-ρ +1, n_i= R-ρ (N_i cl+B_i^A ) , for all i<K. On ℰδE_δ, every empirical average of the genuine target-arm rewards is at least μ¯K=rmin+ε μ_K=r_ + . Thus, for any t∈ont ^on, μ^K(t)≥nKrmax+NKcl(t)μ¯KnK+NKcl(t)>rmin+ρ. μ_K(t)≥ n_Kr_ +N_K cl(t) μ_Kn_K+N_K cl(t)>r_ +ρ. For any bandit algorithm A, the pull count Ni(t)N_i(t), excluding injected samples, is nondecreasing in t. Thus, for each arm i<Ki<K, we use the conservative upper bound BiB_i^A uniformly over t∈[T0cl+1,T]t∈[T_0 cl+1,T]. We now use induction over online rounds. Initially, Nion(T0+1)=0N_i^on(T_0+1)=0. At any later round t, if arm i has been suppressed at every preceding online decision, we have Nion(t)≤BiN_i^on(t)≤ B_i^A. In either case, Nicl(t)=Nicl+Nion(t)≤Nicl+BiN_i cl(t)=N_i cl+N_i^on(t)≤ N_i cl+B_i^A, so, since all genuine rewards are at most rmaxr_ , μ^i(t)≤rmaxNicl(t)+rminniNicl(t)+ni≤rmin+ρ. μ_i(t)≤ r_ N_i cl(t)+r_ n_iN_i cl(t)+n_i≤ r_ +ρ. Hence μ^i(t)≤rmin+ρ<μ^K(t). μ_i(t)≤ r_ +ρ< μ_K(t). Intersecting ℰδE_δ with the K−1K-1 pull-bound events gives probability at least 1−2δ1-2δ by a union bound. On this event, ∑i=1K−1Nion(T+1)≤∑i=1K−1Bi. _i=1^K-1N_i^on(T+1)≤ _i=1^K-1B_i^A. Summing the displayed injection counts and taking the infimum yields the claimed cost bound, including an O(K)O(K) rounding overhead. ∎ Appendix E Exploration and Allocation The allocation depends on how injections control exploration. Let ρ=z−rminρ=z-r_ and M=∑i<KniM= _i<Kn_i. In the near-boundary regime, the genuine target rewards contribute little to maintaining the threshold, so the injections must sustain a mean increase of approximately ρ over T observations. This gives the leading target cost nK∼Tρ/Rn_K Tρ/R. The same expression follows from the worst-case reward bound used in our ϵε-greedy construction. UCB and TS. For UCB, suppressing a competitor requires its exploration bonus to fit below the target’s threshold. Since the bonus decays as Ni−1/2N_i^-1/2, a threshold height ρ requires an observation count proportional to ρ−2ρ^-2. Injected samples supply this count before online learning begins. TS has the same dependence because its sampling uncertainty also decays as Ni−1/2N_i^-1/2. Because all competitors share the threshold ρ, summing their leading injection costs changes only the coefficient of ρ−2ρ^-2, so M=∑i<KniM= _i<Kn_i has the same dependence. Thus, for both constructions, raising ρ increases target cost linearly but reduces aggregate non-target cost as ρ−2ρ^-2. A small relative increase in ρ adds that fraction of nKn_K and saves twice that fraction of M. At the minimizing threshold these amounts agree, giving nK∼2Mn_K 2M: the target accounts for 2/32/3 of the total cost. ϵε-greedy. Here exploration is prescribed by the schedule and cannot be removed by increasing observation counts. Each competitor can receive up to B exploratory rewards. Even if all equal rmaxr_ , injecting nin_i rewards equal to rminr_ keeps its mean below the threshold whenever RBni+B≤ρ. RBn_i+B≤ρ. For small ρ, this requires approximately RB/ρRB/ρ injections per competitor. Hence M decreases as ρ−1ρ^-1: a small relative increase in ρ saves only that same fraction of M. Balancing this saving against the increase in target cost gives nK∼Mn_K M, so the target accounts for 1/21/2 of the total cost.