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

1.1 Our Contributions

• The attack model injects valid action–reward samples before deployment and measures cost by sample count, reflecting the effort of generating fake interactions.The paper motivates this bounded fake-data setting with applications such as review manipulation.Source: §1 · p. 1, §1.1 · pp. 2–3

1 Introduction

• Earlier work studied offline poisoning, bounded attacks, or cost optimality separately, without characterizing how attack effort should be allocated across arms.The paper frames direct target promotion as closer to practices such as fake reviews than suppressing competitors alone.Source: §1 · p. 2

1.1 Our Contributions

• Near the lower reward boundary, cost-optimal UCB attacks that select the target in nearly all rounds must spend a nonvanishing cost fraction promoting it.The paper also reports matching leading-order upper and lower bounds for its optimal sublinear attack cost.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

• The proposed strategy jointly optimizes target promotion and non-target suppression, combining the two mechanisms rather than relying on suppression alone.The introduction describes suppression as the typical mechanism in prior stochastic-bandit attacks and contrasts it with direct promotion.Source: §1 · p. 2

1.1 Our Contributions

• The strategy extends beyond UCB to Thompson Sampling, ϵ-greedy, and a broader class of suppression-bounded algorithms.The paper reports that MovieLens experiments show lower attack costs while maintaining target-arm manipulation and validate the predicted target-centric allocation.Source: §1.1 · p. 3

1.2 Related Work

• Related work spans attack design and robust bandits, while this paper follows attack design and applies bounded fake-data injection in an offline-to-online setting.The cited attack literature commonly favors targets by suppressing non-target rewards; the robust-bandit works described do not allow adversaries to observe learner actions before corrupting feedback.Source: §1.2 · p. 3

2 Warm-Start Bandit Setup

• Each arm has an unknown reward distribution with bounded, sub-Gaussian rewards, and UCB summarizes history using arm counts and empirical means.The learner selects an arm using its index; without attacks, the setup states that it achieves sublinear regret.Source: §2 · pp. 3–4
• The warm start consists of T0 action–reward observations, followed by online interaction from round T0 + 1 through round T.The online horizon H is the number of rounds after initialization.Source: §2 · p. 3
• A general warm-start algorithm specifies a policy for each online round, samples an arm based on the current history, then appends the observed reward.The setup tracks online pulls of each arm before each round.Source: §2 · p. 4

3 Offline Attack Model

• The attacker observes the clean offline log and learner policy before deployment, but cannot alter actions, rewards, or history once online interaction begins.The setting assumes genuine offline and subsequent online observations are retained without filtering by reward value.Source: §3.1 · p. 4
• An injection plan specifies how many fake observations to add to each arm and the corresponding fake rewards.The fake action–reward pairs are assembled in the strategy's chosen order and combined with the clean log to initialize the learner.Source: §3.1 · p. 4
• Attack cost is the number of injected samples, and every injected reward must stay within the valid range and legal feedback alphabet.This makes sample validity part of the attack constraints.Source: §3.1 · p. 4
• The attack workflow determines an injection plan and constructs the fake log before deployment.The workflow then initializes the learner using the attacked warm-start log.Source: §3.1 · pp. 4–5

4.1 Attack on UCB

• The UCB construction jointly promotes the target and suppresses competitors, keeping the target’s index above each competitor throughout the online phase.It raises the target’s empirical mean above a threshold while bounding non-target UCB indices below it.Source: §4.1 · p. 5
• The upper and lower cost rates match when ε=Ω(ΔK), and when ε=Ω(1) both bounds are Θ(K log T).The latter cost order also agrees with the attack costs of Zeng et al. [2025].Source: §4.1 · p. 6
• When ΔK=o(ΛT/T), the construction achieves leading-order optimal cost by minimizing the leading costs of target promotion and non-target suppression.The boundary scale is ΛT/T, and the construction’s cost is bounded above by (1+o(1))ΛT.Source: §4.1 · p. 6
• Near the boundary, successful UCB attacks with the stated cost and tolerance conditions must spend a nonvanishing share on the target; the construction is target-centric for fixed competitor counts.For larger tolerances ξ=O(ΛT), a deterministic O(ΛT) cost cap still requires a nonvanishing target-arm share.Source: §4.1 · p. 7

4.2 Extension to Suppression-Bounded Algorithms

• The extension applies to suppression-bounded learners by raising the target mean above a threshold and offsetting clean observations on non-target arms.UCB, Thompson Sampling, and ϵ-greedy fall within this class.Source: §4.2 · pp. 7–8

Experimental setup

• The MovieLens-25M experiment treats ratings of at least four as positive and uses Glitter, with empirical positive-rating rate 11/669, as the target arm.Competitors are the most-rated remaining movies.Source: §5 · p. 8

Numerical results

• Our method consistently costs substantially less than Clipped Suppression, with the gap widening as K grows; its observed cost growth with T is consistent with a sublinear bound.Clipped Suppression intervenes whenever a non-target arm is pulled, so its cost grows faster with T.Source: §5 · p. 8
• Across tested T and K, UCB selected the target in every online round in every repeat; Clipped Suppression had more non-target pulls, nearly half the rounds at T=106.The overall ratio NK/T for the proposed method remains close to 1.Source: §5 · pp. 8–9

Near-boundary cost and allocation

• In Figure 3(a), normalized cost C(n)/ΛT approaches 1 as T increases; in Figure 3(b), the target cost share approaches 2/3 at K=10.Both trends are reported as consistent with the theoretical analysis.Source: Figure 3 · p. 9, §5 · p. 9

Comparison with Xu et al. [2021]

• In the near-boundary regime, our attack retains sublinear cost and achieves target selection in every online round with high probability, while Xu et al. [2021]’s cost grows rapidly as ΔK approaches zero.Their points are omitted when their cost is undefined at ΔK=0 or is at least T; their target-selection ratio remains below 1 in the most challenging settings.Source: Figure 4 · p. 9, §5 · p. 9

Additional experiments

• Appendix experiments also evaluate Thompson Sampling and ϵ-greedy.The paper reports these alongside the main experiments.Source: §5 · p. 9

6 Concluding Remarks

• Near the reward boundary, an order-optimal UCB attack that selects the target in nearly all online rounds must spend a nonvanishing fraction of its cost promoting that arm.The UCB construction attains the O(ST) cost scale in this regime.Source: §6 · p. 9
• The analysis assumes the learner uncritically trusts offline data, and its cost and allocation results assume a small clean offline log.The conclusion identifies larger clean logs as a setting where both optimal cost and allocation may change.Source: §6 · p. 10

A.1 Upper Bound Proof

• The upper-bound proof shows UCB selects the target in every online round after initialization under its stated conditions.The proof repeats the index comparison inductively from round T0 + 1 through T.Source: §A.1 · p. 13
• The upper-bound cases combine to give the asserted cost bound, with the non-target injection counts summing to O(ST).The cited proof passage reports the O(ST) scale when ε = O(rT).Source: §A.1 · p. 13

A.2 Lower Bound Proof

• The lower-bound proof establishes attack cost at least Ω(K log T/(∆K ∨ rT)^2) under its stated conditions.The bound follows in both cases of the proof.Source: §A.2 · p. 14

A.3 Optimality Proofs

• At both thresholds in the stated case, the target count is one, while raising z only reduces non-target counts.This is a construction-side observation within the optimality proof.Source: §A.3 · p. 14
• The allocation variable x = nK/C(n) must satisfy x^2(1 − x) = 4/27 − o(1), forcing the target cost share toward 2/3.The bound is stated for x ∈ [0, 1].Source: §A.3 · p. 15
• For near-boundary UCB attacks with the stated success and deterministic cost bounds, the target's share of attack cost is Ω(1).The proof derives nK = Ω(ΛT), hence nK/C(n) = Ω(1).Source: §A.3 · p. 15

B.1 Attack Strategy

• The threshold certificate states that the construction makes TS select the target in every online round on Eδ ∩ F.The construction injects rmax on the target and rmin on each non-target arm.Source: §B.1 · p. 16
• Theorem B.2 gives an upper-bound and allocation result for TS, with the stated near-boundary condition ∆K = o(ST/T).The supplied theorem passage names the cost and allocation result; its detailed bound is not included here.Source: §B.1 · p. 16

B.2 Numerical Illustration

• The TS attack costs less than Clipped Suppression except at the smallest arm count, where the baseline costs less but still pulls non-target arms.The attack selects the target exclusively online in every repeat.Source: Figure 5 · p. 17, §B.2 · p. 17
• Near the boundary, TS's normalized cost approaches one, with cost shares approaching 2/3 for the target and 1/3 for non-target arms collectively.Every repeat has zero non-target online pulls.Source: §B.2 · p. 17, Figure 7 · p. 18

C.1 Attack Strategy

• The construction assumes the entire offline log is attacker-generated.This assumption is stated for simplicity in the attack analysis.Source: §C.1 · p. 18

C.2 Numerical Illustration

• The attack has lower mean costs and higher mean target-arm selection ratios than Clipped Suppression across the reported settings.All greedy decisions selected the target; remaining non-target pulls were exploratory and stayed below the theoretical bound.Source: Figure 8 · p. 19, Figure 9 · p. 19, §C.2 · p. 19

C.1 Attack Strategy

• On the stated event, every greedy decision selects the target, so non-target pulls are exploratory and total at most (K − 1)B.The construction injects rmax on the target and rmin on each non-target arm.Source: §C.1 · pp. 18–19
• With ϵs = min{1, cK/s}, the attack has cost O(√(TK log T)) and (ξ, δ)-success with ξ(T) = O(K log T).The stated schedule condition is K log T = o(T).Source: §C.1 · p. 19

• On Eδ, every empirical average of genuine target-arm rewards is at least μK = rmin + ε.Source: D Analysis of Suppression-Bounded… · p. 20
• The argument uses nondecreasing genuine pull counts and the upper bound rmax on genuine rewards.Source: D Analysis of Suppression-Bounded… · p. 20
• Intersecting Eδ with the K−1 pull-bound events gives an event with probability at least 1−2δ.Source: D Analysis of Suppression-Bounded… · p. 20
• Summing the displayed injection counts gives the cost bound with an O(K) rounding overhead.Source: D Analysis of Suppression-Bounded… · p. 20

Exploration and Allocation

• Near the reward boundary, target injections must sustain a mean increase of approximately ρ over T observations, giving nK ∼ Tρ/R.Source: E Exploration and Allocation · p. 20
• At the minimizing threshold, UCB and Thompson Sampling allocate two-thirds of total cost to target promotion.For both, target cost grows linearly with ρ while aggregate non-target cost falls as ρ^-2.Source: E Exploration and Allocation · p. 20
• For ε-greedy, target promotion accounts for one-half of total cost because non-target cost falls only as ρ^-1.Its prescribed exploration cannot be removed by increasing observation counts.Source: E Exploration and Allocation · p. 20