Adversarial Attacks on Online Learning to Rank with Click Feedback
Authors: Jinhang Zuo
Zhiyao Zhang
Zhiyong Wang
Shuai Li
Mohammad Hajiesmaili
Adam Wierman
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning to rank
adversarial attack
click model

Abstract: Online learning to rank (OLTR) is a sequential decision-making problem where a learning agent selects an ordered list of items and receives feedback through user clicks. Although potential attacks against OLTR algorithms may cause serious losses in real-world applications, there is limited knowledge about adversarial attacks on OLTR. This paper studies attack strategies against multiple variants of OLTR. Our first result provides an attack strategy against the UCB algorithm on classical stochastic bandits with binary feedback, which solves the key issues caused by bounded and discrete feedback that previous works cannot handle. Building on this result, we design attack algorithms against UCB-based OLTR algorithms in position-based and cascade models. Finally, we propose a general attack strategy against any algorithm under the general click model. Each attack algorithm manipulates the learning agent into choosing the target attack item $T-o(T)$ times, incurring a cumulative cost of $o(T)$. Experiments on synthetic and real data further validate the effectiveness of our proposed attack algorithms.

Adversarial Attacks on Online Learning to Rank with Click Feedback
Jinhang Zuo Zhiyao Zhang
Zhiyong Wang'
Shuai Li
Mohammad Hajiesmaili'
Adam Wierman?
University of Massachusetts Amherst 2California Institute of Technology
Southeest University "The Chinese University Hong Kong Shanghai Jiao Tong University
(jhzuo haj lesmaili]@ss umass. edu muirheadzhang@gmall com com zywang210cse. cuhk. edu. shuaili80sjtu. edu. on adamv@caltech.edu
Abstract
Online learning to rank (OLTR) is sequential decision-makee problem where a learning agent selects an ordered list of items and receives feedback through user clicks. Although potential attacks against OLTR algorithms may cause serious losses in real-world applications, there is limited knowledge about adversarial attacks on OLTR. This paper studies attack strategies against multiple variants of OLTR. Our first result provides an attack strategy against the UCB algorithm classical stochastic bandits with binary feedback, which solves the key issues caused by bounded and discrete feedback that previous works cannot handle. Building on this result, we design attack algorithms against UCB-based OLTR algorithms in position- based and cascade models. Finally, we propose general attack strategy against any algorithm under the general click model. Each attack algorithm manipulates the learning agent into choosing the target attack item T - o(T") times, incurring cumulative cost of o(T). Experiments synthetic and real data further validate the effectiveness of our proposed attack algorithms.
Introduction
Online learning to rank (OLTR) has been extensively studied 2 3 4 5
sequential decision-
making problem where, in each round, a learning agent presents a list of items to users and receives implicit feedback from user interactions. One of the most common forms of feedback considered in literature is the form of user clicks [44 []. OLTR with such click feedback can lead to major improvements over traditional supervised learning to rank methods (6] 7 g However, there is security concern that user-generated click feedback might be generated by malicious users with the goal of manipulating the learning agent. Understanding the vulnerability of OLTR under adversarial attacks plays an essential role in developing effective defense mechanisms for trustworthy OLTR.
There has been surge of interest in adversarial attacks on multi-armed bandits 9 TO I.] For example, [9] shows that, for stochastic bandits, possible to manipulate the bandit algorithm into pulling a target arm very often with sublinear cumulative cost. Though generally follows the bandit formulation, it differs from stochastic bandits in the action space and feedback model. More specifically, OLTR chooses a list of K out of L arms, instead of just one arm, to play in each round; the realized rewards of the chosen arms are usually censored by a click model, e.g., position-basee [4] cascade model (5). Thus, it is nontrivial to design efficient adversarial attacks the censored feedback of the chosen arms for OLTR.
Moreover, previous works 9 10 can only handle unbounded and continuous reward feedback, while the (binary) click feedback of OLTR bounded and discrete. Such binary feedback brings new
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Summary of the settings and proposed attack strategies
Setting
Attack against
(T)
lim C(T)/log)
L-armed bandits
UCB 12
T (LL 1)
log T)
Eaer. Aut
37
Position-based model
PBM-UCB
T- 0 (L K)
log
Eaek
ilte((satin +o0))
Cascude model
CascadeUCB
T T-0 (L-K) K)
log
o (EEck
Autido)
p A
General model
Arbitrary
T T- T)
(Eacile , + (3(1)))
Do: purameter of the atlack algorithm; A.: mean gup between urm and L; 8: decreusing function in Section 3.2
challenges to the attack design against OLTR algorithms. Since the post-attack feedback must also be binary, this scenario introduces a new problem of deciding whether to attack when the output attack value from previous algorithms is between and 1: simple rounding up might be costly, while skipping the attack may lead to undesired non-target arm pulls. Furthermore, the attack value computed by previous attack algorithms can be larger than 1, which is higher than the maximum attack value in the click model. In other words, in the bounded and discrete model, it is impossible to always find feasible attack value ensure the required conditions for their theoretical guarantees.
Contributions. In this paper, we propose the first study of adversarial attacks on OLTR with click feedback, aiming to overcome the new issues raised by the OLTR click model well as the binary feedback. Table [ summarizes our proposed attack algorithms with their theoretical guarantees. Since the click feedback itself complicates the attack design, we first consider adversarial attacks on stochastic L-armed bandits with Bernoulli rewards where the feedback from the chosen arm is always binary. We propose an attack algorithm that mislead the well-known UCB algorithm [12 to pull the target arm L for (T) times in T rounds, with a cumulative cost CTT) in the order of log I" asymptotically, Based on this approach, we study the two most popular click models of OLTR, position-based model 4 and cascade model (5), and propose attack strategies against UCB-type OLTR algorithms. Their cumulative costs depend on Kи and p", which are instance-dependent parameters of the position based and cascade models, respectively. Lastly, we introduce the threat model for OLTR with a general click model and design an attack algorithm that can misguide arbitrary OLTR algorithms using click feedback. Our technical contributions are summarized as follows.
1. We propose the new idea of conservative estimation of the target arm for attacking UCB in stochastic bandits with binary feedback, which resolves the issues caused by the bounded and discrete requirements of the post-attack feedback. This approach is also the backbonn of other attack strategies in more complicated OLTR settings.
2. The PBM-UCB algorithm uses position bias-corrected counters rather than simple click counters to compute UCB indices; we provide the theoretical analysis of our attack algorithm against PBM-UCB by carefully treating these unusual counters.
3. The partial feedback of OLTR with the cascade click model brings a challenge to the attack design. We provide a new regret- analysis of our attack algorithm against CascadeUCB without suffering from the partial feedback issue.
4. We devise general attack strategy based on new probabilistic atlack design. It can successfully attack arbitrary OLTR algorithms without knowing the details of the algorithm.
We also conduct experiments on both synthetic and real-world data to evaluate our proposed attack strategies. Experimental results show that they can effectively attack the corresponding OLTR algorithms with less cost compared to other basclines. Due to space constraints, proofs and empirical results are included in the appendix.
Related Work. Online learning rank with different feedback models has attracted much attention in recent years. Though there are other types of feedback models such as top-K feedback [13 click feedback has been widely used in literature. 44
14
[5] consider the position- based model (PBM),
where each position of the item list has an examination probability known or unknown by the learning
20 considers the setting where the user would check the recommended items sequentially and stop at the first clicked one; all items after the clicked item will not be examined. The dependent click model (DCM) a generalization of the cascade model where the user may click multiple items 21
agent. The cascade model 5 16 17
18
19
22
There are also general click models [| 2

---

that can cover some of the previous click models. In this paper, we mainly focus on attack design on PBM and cascade models; both of them adopt bounded and discrete click feedback thus require a new design other than previous works like
[9] that can only handle unbounded and continuous feedback.
Adversarial attacks different types of multi-armed bandit problems have been studied recently [ 10 23 24, 25]. [9] proposes the first study of adversarial attacks on the classical stochastic bandit problem. It designs effective attack strategies against the e-Greedy and UCB algorithms.
[10] extends
it to a more general setting, where the algorithm of the learning agent can be unknown. 2 studies
adversarial attacks on linear contextual bandits where the adversarial modifications can be added to either rewards or contexts. To the best of our knowledge, we are the first to study adversarial attacks on OLTR where, in addition to the challenges raised by click feedback, the combinatorial action space and the censored feedback of OLTR make it non non-trivial to design efficient attack strategies.
2 Preliminaries
In this section, we briefly discuss the three problem settings we consider in this paper.
Stochastic L-armed bandit. We consider an arm set [L] = (1, 2, ... ,L), with μ4 as the expected 2 juz. In round f, the player chooses an arm Og E [ to play and receives a reward ri as feedback. In the click feedback setting, the realized reward r E {0, 1} of arm a is sampled from Bernoulli distribution with expectation Maa. The player aims to find an optimal policy to maximize the long-term cumulative reward.
reward of arm é. Without loss of generality, we assume μl A2
OLTR with caaition-basedd model [4. This setting also considers the item (arm) set [Z.] where 14; represents the click probability of item i. However, in OLTR with the position-based model (PBM), in each round f, the player chooses
ordered list of K items, a; (01...
.KK,)), with known
examination probability Ny for the k-th position in the list (assuming Ki 2 .... 2 KK). The player then observes the click feedback of the chosen list from the user, denoted as r (ri,e)
k.t) E {0. 1)* where rf, sampled from a Bernoulli distribution with expectation KefMo,,. The reward obtained by the player is the sum of the clicks, i.e., Ek=1 " The goal of the player is to find an optimal policy that can maximize the long-term cumulative user clicks.
OLTR with cascade model (5). Here, we consider the same item set [4] that in the PBM model. For OLTR with cascade model, in each round f, the player chooses an ordered list of K items, a, = (a1,1, ... ax,)). .) for the user. The user then checks the list from 01,t to ax,t, with probability Mar, to click the k-thh item. She immediately stops at the first clicked item, and returns the click result back to the player. We denote the position of the first clicked item as C, (C, = oo if no item was clicked). The click feedback of the player is r = (r
..))) E {0, 1). where only rC., = and rh, 0 for all k f C. The reward obtained by the player is again the sum of user clicks Ekmi r2 but in the cascade model, it is at most 1. The goal of the player is also to find optimal policy that can maximize the long-term cumulative user clicks.
3 Attacks on Stochastic L-armed Bandits with Binary Feedback
As mentioned in the introduction, one main challenge of attacking OLTR algorithms comes from the binary click feedback: such binary feedback limits the possible actions of the attacker since they need ensure the post-attack reward feedback is still valid (binary). This is a common issue for all OLTR with click feedback. Hence, in this section, we focus on adversarial attacks on the L-armed bandit problem with binary feedback. We propose an attack algorithm against the UCB algorithm, which is the backbone of the attack strategies for more complicated OLTR settings.
3.1 Threat Model
We first introduce the threat model for the L-armed bandit problem with binary feedback. In each round i, the player chooses an arm d, E [L] to play. The environment generates the pre-attack reward feedback r E (0, 1} based on a Bernoulli distribution with mean Ma,- The attacker then observes at, r., and decides the post-attack feedback r, E {0. 1). The player only receives r as the feedback and uses that to decide the next arm to pull, a++1, for round + 1. Without loss of generality,
3

---

Algorithm Attacks against the UCB algorithm on stochastic bandits with binary feedback
1: Initialization: (0) 1 for all a E [Z]
2: for /= 1,2,3.... 3.... do
3: Observe 0g
4: if' a: * L then
5: Calculate Ye, Yo according to Eqs. (2) and 3
6: if yt S ri then
7:
02 m. Ba, (t) =
8:
else
9:
0₁ [% 1. Bay (t) hoo (t 1)
10:
end if
11:
end if
12: Return Y2 = o4: update ha(l) = laat 1) for all a + az
13:
end for
assume arm L is sub-optimal targer arm. The attacker's goal is misguide the player to pull the target arm L very often while using small attack costs. Let (t) denote the number of pulls of arm i up to round I. We say the attack is successful after T rounds (T) T (T) in expectation or with high probability, while the cumulative attack cost C(T) > == lrz oT)).
3.2 Attack Algorithm against UCB
For better illustration of the attack strategy, we first define the following auxiliary notations. Let (t) := {s S t. a = i} be the set of rounds up to f when arm played. We denote the pre-attack average reward of arm up round & by (t) (t) - EeEr( r Lastly, let (t) == (N(t)=1 ExET((t) Ts be the post-attack average reward of arm up to round t.
As in we consider attacks against the (a, -UCB algorithm from 12 where a = 4.5 and d 2 /8 since Bernoulli random variables are 1
The original attack algorithm
in calculates an attack value Og for round such that
Pa. (t) S at - 1) - 23(NN -o:
where 3(N) = 2N log T2IN2 A. > 0 and 8 0 are the parameters of the attack algorithm. The r back to the player. The main idea of the attack algorithm in [9] to compute the attack value so that the post-attack empirical estimates of the non-target armss are always less than those of the target arm.
attacker then gives the post-attack reward
However, this attack design only works when the reward space is unbounded and continuous, while in the threat model with binary feedback, the Bernoulli rewards are discrete and bounded. There are two issues raised by the discrete and bounded requirements. First, the calculated attack value ag is real number, which may not make the post-attack reward feedback r, to be valid (binary). Second, in order ensure that Eq. (1) is true, the calculated a might be larger than which is higher than the maximum attack value in our threat model. In other words, it is impossible to let Eq. (T) hold for all rounds, while such guarantee was essential for the theoretical analysis in (9. To overcome these issues, we propose new attack algorithm against UCB on L-armed bandits with binary feedback. It described in Algorithm The algorithm maintains timestamp (a for each arm a. In round the arm pulled by the player, a,, is not the target arm L, it first checks the condition % < r (Line 6), with 7/ computed as
(1-1) (t) (t) Ao) [
7t No. (t) (t) E ExEro
where [z]+ max(0, 2) and , (t,(t)= (t) 23(N In fact, condition N/t S. r is equivalent to checking whether there exists a feasible at to ensure Eq. ( holds: if r with or set to be [rel (Line 7), Eq. (1) will hold in round L. Using similar analysis as in [9. we can derive an upper bound of No, (t) and prove the success of the attack up to round L. The algorithm also updates the timestamp hag (t) for a (line 7). If 7 > rQ. it indicates that there is no feasible a that can

---

ensure Eq. I Instead, the algorithm sets [7/] with % computed as
(1 1)) (t-1)) Ao [0].]
9 No. (O)), (t) ES (t- No, (t) [4,
(Ma, (ha,
(3)
where hag (t 1) records the last round that Eq. ①I was satisfied. We can prove such ds is always
feasible (og - r and it can ensure that
Pa. (1) S (ha, (L 1)) 23. (L 1))) Do-
This new inequality always holds for all rounds, which helps guarantee the success of the attack.
more conservative lower bound of (LL, Hy (ha, (t- 1)), instead of Hr (t), on the right-hand side of the inequality. We refer to this as conservative estimation for the target arm L with respect arm de, where the estimated lower bound of L will only be updated when there exists feasible O to ensure Eq. ( Intuitively, it makes the attack algorithm more conservative and less likely use small attack value that may result in an invalid large attack value in later rounds. We use an inductive proof to show that there always exists a such that Eq. (4) holds while keeping It valid (binary). Therefore, conservative estimation addresses the problems posed by binary feedback. This forms the foundation for the attack algorithms tailored for OLTR with click feedback.
Remark. Compared with Eq. (1. Eq. (4)
3.3 Analysis
We first show that our attack algorithm always returns valid binary feedback to the player. Lemma 1. The post-attack feedback of Algorithm always valid, i.e., rr E {0, 1] for any
The proof of Lemma 1 which uses an inductive analysis Yt, St, can be found in the appendix.
Define A. Pa - ptz We give the following theorem to show the successful attack of Algorithm
Theorem 1. Suppose T 2 L and d 1/2. With probability at least 1 6. Algorithm missuides the UCB algorithm to choose the target arm L at least T (L- 1) [ cumulative attack cost at most
3 log T rounds, using
C(T) S (1 (1+
3. log T Eacl (Aa + Du +43 (1+
3 log ha (T))
A3
Ag
As T goes infinity, we have
C(T) T-0 log T
lim
50
Σ \B<K
A Ao
Compared with Theorem 2 in [9, the 3 term in our cost bound depends on log h (T) instead of log Since 3 is a decreasing function and (T)) < T, our finite-time cost bound can be larger than that in (9. However, our asymptotic analysis of the cost suggests that when T is large, such difference becomes negligible. Notice that the attack algorithm in [9] does not have any theoretical guarantee in the binary feedback setting, this comparison is only meant to show the additional cost potentially caused by the conservative estimation.
Attacks on Online Learning to Rank
We now move developing effective attack algorithms for more complicated OLTR settings. Since attacking OLTR also faces the challenges caused by binary click feedback, the attack algorithms in this section rely attack design for stochastic bandits with binary feedback in Section 3
4.1 Position-Based Click Model
Threat Model. We introduce the threat model for online stochastic ranking with position click feedback. In each round t, the player chooses a list of K item, a, (a1,1, .ak.)) to recommend.
The environment generates the pre-attack click feedback r! (rf...".- .kke) {0, 13 where r
5

---

Algorithm 2 Attack against the PBM-UCB algorithm
1: Initialization: Randomly select K items with L to build a"; (0) = 1 vA [4] Va Ea'
2: for t= 1, .... do
3: Observe 0,, rf. set Ox, (01,t:" ; = (0,-.. ,0,
4: for E [K] do
5: if d a" then
6:
diit CAL BAL_AALPHA(;;4) (i,,, r2,,- a")
7:
else
8:
Oiit
9:
end if
10: end for
11: Return T3 = r ayi update h4 (t) h1 - 1) for all
a, a E a'
12:
end for
Algorithm CAL_
1: Input: item I, click feedback r", item set a"
2: for a* do
3: Calculate a)(,,a), fel1, a) according to Eqs. 6 and
4: end for
5: Timax max.Ea 71(1, a), Ymax = max.ca 71(,aa
6: if Tmax S then
7: a [//max 1. hu (1) for Corallas E
8: else
9: a [imaax] (t) ht,a(t 11 for all a E a
10: end if
11: Return
is sampled from a Bernoulli distribution with mean KePas, The attacker then observes and rf. and decides the post- post-attack click feedback T. f0, 1}K The player only receives
the feedback and uses it to decide the next list to recommend, a,+1 for round t +- 1. Without loss of generality, we
assume item L is sub-optimal target item. Similar to Section 3.] say the attack is successful after T rounds if the number target item recommendations is N7 =T (T) in expectation
or with high probability, while the cumulative attack cost C(T) > |[, rflli o(T).
Attack against PBM-UCB, We consider the PBM-UCB algorithm in the online ranking algorithm of the player, which computes the UCB index of each item a as
(1) = iaall - 1) (1 = (1-111) 1)
(5)
(t-
where (o) = = Σ kip {a;,s = a} is the position bias-corrected counter, (a(()) is the empirical mean of item and is parameter of the algorithm. The algorithm then chooses the corresponding first K items with the highest UCB indices as the recommendation list.
We propose our attack algorithm against PBM-UCB in Algorithm 2 It works by first randomly taking K items and making them set with the target item L, denoted as a {af - L.- Then, based the conservative estimation idea from Algorithm 1 it maintains timestamp h[l, a) for each item / with respect to each E a*. The intuition is that, to ensure a similar inequality as (4 for all rounds, we need to make conservative estimation the lower bounds of μ. for all E a This is handled by Algorithm which maintains the timestamps h (t) for the input item / and outputs the appropriate attack value a on that can always ensure the required inequality. The value of parameters y (1, a) and (e, a) in Algorithm| 3 are computed as
Eq.
71(1,a) = [N(()R(()) - an(s) - Ni(1) (L((1) - -20]]]
(6)
()) (((E))P(()) - EvEr(e-1) - (n(s)= - Ni(t) (hi,attttt11 1)) -20

---

Algorithm 4 Attack against the CascadeUCB algorithm
1: Initialization: Randomly select K - items with L to build a"; (0) - vA E [4] Va Ea'
2: for (= 1,,3 .... do
3: Observe 0,, rf. C₁; set O2 (01,1) OK.)) = (0, (0,
4: if C, S K and ac,,t & a* then
5: oc,,, = _AL_ALPHH ALAAAALHHAAC,,,, "C,,,, a²)
6: if oc. 1 and Di > C2 S.t. 0i a* then
7:
0i = -1
8: end if
9:
end if'
Return r; = rb - ac; update hr,a()) h4,a (t - 1) for all + ac,,t a E
11:
end for
Notice that Algorithm could also work when there are more than one but less than K 1 target arms (the goal of the attacker becomes misguiding the player to recommend target arms very often with sublinear cost). The only modification required is to put all of these target arms into a",
Analysis. The following theorem shows the attack against PBM-UCB successful.
Theorem 2. Suppose T 2 L and 1/2. With probability least 1 6, Algorithm misguides the PBM-UCB algorithm to recommend the target item I. at least T (T. K) 2n
I+c log T) rounds,
AB
using a cumulative attack cost at most
C(T) S <( (1e log Easl (Au Do 43
Ite log ta 2n
When T goes infinity, have
C(T) logT
(1+c)(A, + Ao)
lim
50
x
Proof sketch. Whenever art a is chosen by the player, there must exist E a" such that Ro... (t) 2 (t). The output as of Algorithm would ensure (a),,() S Paahaacaat 1)) 2,3(N (BNNaaha,, (aar,,. (t- 1))) Ag. owing to the conservative estimations in (e(a,,,,)) and 5e (a a). Combining these inequalities, we can get Ba,,, (1) (1) Do. With a careful calculation on
this inequality and the involved bias-corrected counters, we have Na.,, (t) S
1tc
logt). This
2x
result holds for any ai,z $ a*. Thus, we immediately get the bound of (1). The remaining proof for the cost bound will be similar to that of Theorem
Compared with Theorem I the asymptotic cost of Algorithm 2 has an additional dependency 1/ 1/k2.. which suggests may require more cost to achieve a successful attack in the PBM model, though the cost dependency on T is still logarithmic.
4.2 Cascade Click Model
Threat Model. We introduce the threat model for OLTR with cascade click feedback. In each round the player chooses a list of K items,
(a1,,) aK..) to recommend. The environment (C,
generates the pre-attack click feedback rf (r (1, 7 E 10, ||r!|| S 1. Let C, denote
if no item was clicked). The attacker observes at r C., and decides the post-attack click feedback r. E {0, ||re|]i S 1. The player only receives F. as the feedback and uses it to decide the next list recommend, a,+1, for round t ++1. The goal of the attacker in this setting is the same as that in the PBM model.
the position of the clicked item, i.e., rC..
Attack against CascadeUCBB, We propose an attack algorithm against CascadeUCB in Algo- rithm Similar to the attack against PBM-UCB, first randomly generates a set items T .1 I.). It also follows the idea of conservative estimation: when the clicked item ac does not belong to a", calls Algorithm maintain Aoc,.. for all a E a* and compute the attack value ac.,: based on the conservative estimations. If the output ac, = 1, which means
7

---

Algorithm 5 Attack against arbitrary algorithm
1: Initialization: Randomly select K - items with target L to build at
2: for [- 1,2, 3, do
3: Observe ag, ri
4: for E [K] do
5: Oi,t = 0
6:
air $ a" and fit = then
po.. (t)+ (0) (0)) Ra, (0,B(N;;
7:
Pi. max
8:
With prob. Pi.c, set at, =1 end if
9:
10: end for
Return r; = r Ctt
12:
end for
the algorithm sets the clicked position to be zero, the player will keep checking the positions after C. Since the pre-attack feedback of all items after position C, is zero, we need to find the first item ai,t E a" after position C, and set Oiiz -1 (ri.e = 1). The empirical means of the items between position C, and that are not in a decreases, and the empirical mean of a, E a increases. Thus, does not affect the success of the attack while still making the post-attack feedback valid.
Analysis. First, note that there a mismatch between recommendation and observation in the cascade model: for all i such that C, < <is K, ai,t is recommended but not observed, i.e., there is no new click sample for item a,2t for estimation. We can still follow a similar proof of Theorem 2 to get the upper bound of the number of observations (samples) for a;,t & a", but it is less than the number of recommendations and thus cannot ensure the success of the attack. To tackle this problem, we use new regret-based analysis on the expected number of recommendations. We can also prove that the post-attack feedback of Algorithm 4 always valid. Define p" - p4:- We give the following theorem of the successful attack against CascadeUCB.
Theorem 3. Suppose 2 L and S 1/2. With probability at least Algorithm misguides the CascadeUCB algorithm to choose the target arm at least T (T. K) expectation. Its cumulative attack cost is at most
12
log T
rounds in
p"
C(T) & [++
3 logT)
Eack (Aa Do + 43 (1+
3 log ho ho. (T)))
23
ag
As T goes infinity, have
C(T) T-000 log T
A +
lim
0
Σ LOCK
A
Proof sketch. As mentioned above, we use a new regret-based analysis. The intuition is that the regret caused by any suboptimal item is the product of its reward gap with respect to the optimal list and its expected number of recommendations. If we know the regret upper bound and the reward gap lower bound,
derive the upper bound of the expected number of recommendations. To do so, we first show that the post-attack problem can be viewed as a problem with a known reward gap lower bound. This can be obtained by (a,,(t)) S. frz. (hL,,,,, (t 1)) (3 (ha 1))) Do for any a; & a", which indicates the post-attack expected reward gap between dj,t and L is always larger than An- Then, the lower bound of the reward gap of 0; with respect to the optimal list is p" Do Based the regret upper bound 12 log T An given in (5). we can get the upper bound of the 12 expected number of recommendations 2² log T. For the remaining cost analysis, since the attack
cost only depends on the observed items, we can still follow the proof of Theorem 2
4.3 General Attacks OLTR with General Click Model
We have provided attack strategies against UCB-based OLTR algorithms under two specific click models. A natural follow-up question is whether there exists an attack strategy that can attack any

---

OLTR algorithm under the general click model. To answer this question in what follows, we design an attack strategy that can misguide any OLTR algorithm without knowing the underlying algorithm. However, it may pay more cost (still sublinear) than the others since it cannot take advantage of the details of the algorithm to make fine-tuned adjustments.
Threat Model. We consider the threat model for OLTR with general click feedback. In each round the player chooses a list of K items, at (01,2,. (k,)) to recommend. The environment generates the pre-attack click feedback ri = (ri,,,.. feasible feedback space of click model c. The attacker observes az, r2, and decides the post-attack click feedback r. E {0, 1] Tr E R.. The attack should be aware of Re; otherwise, ensuring valid post-attack feedback is impossible. The player only receives r; as the feedback and uses it to decide the next list to recommend, as+1 The goal of the attacker is the same that in the PBM model.
K E (0,1) r R.. where R, is the
General Attack against Arbitrary OLTR Algorithm. We propose an attack algorithm against arbitrary OLTR algorithms in Algorithm 5 Similar to the attack against PBM-UCB, it first randomly
generates set of items a* = (ai ................................ " -x=--:1 l.). In each round, for each clicked item ai & a', the algorithm calculates an attack probability Pi, and uses that to decide whether its feedback needs to be changed to unclicked (ri.t 0). We prove that pi, actually an estimated upper bound of A./4i thus by such probabilistic feedback perturbations, the algorithm makes all items outside a" be worse than the items inside a', which guarantees the success of the attack. We consider a general assumption for the OLTR algorithm to be attacked.
Assumption 1. The OLTR algorithm chooses suboptimal items no more than R(T) = T(T) times for T rounds,
Notice that both PBM-UCB and CascadeUCB satisfy the assumption with R(T) = Ollg T). We give the following theorem to show the success of our general attack algorithm.
Theorem 4. Suppose T 2 L and 8 < 1/2. With probability at least 1 8, Algorithm 5 misguides arbitrary OLTR algorithm that satisfies Assumption to choose the target item at least T R(T) rounds in expectation. Its cumulative attack cost is at most
C(T) S (Encc + ((()))
Compared with the results in the PBM and cascade models, the 3() term in the cumulative cost of Algorithm is B(1). which can be much larger than the others. Also, the asymptotic costs of Algorithm 2 and Algorithm 4 is independent of B, while the asymptotic cost of Algorithm depends on B, showing that Algorithm is more costly than attack strategies specific OLTR algorithms.
5 Experiments
We conduct experiments using both synthetic and real data (MovieLens 20M dataset (26)). Due
to space limitations, we report only the results of OLTR using the position-based based model. We use = 0.1 for the PBM-UCB algorithm. For the synthetic data, we take L = 16, K 8, T 100, 000: {ui are sampled from uniform distribution UO, 1) for Figure la and from (O, x)) for Figure 1b
For the real data, we take L = 100, K 10, = 100, 000; { are extracted according to 2
Using synthetic data, we first study how the algorithm's performance is influenced by the algorithmic and problem parameters. As shown in Figure Ia the cost decreases with an increase in Ag. aligning with our observations in Theorem 2 Figure Ib shows that the cost increases as æ increases, which suggests that our algorithm pays more costs when A, is large. We then compare our algorithm with two baselines: Trivial,. attacks all arms except the target arm as long as the attack is valid; Trivialge first randomly takes K arms out to generate set and then attacks all arms outside the set as long as the attack is valid. ssows that Trivialal algorithm cannot successfully attack PBM-UCB even with linear costs. Our algorithm and Trivial.,, have similar performance on the chosen ratio of the target arm as shown in Figures 2a and 2c which is the chosen time of the target arm divided by the current round. However, our algorithm pays 50% and 40% less cost than Trivia wiillg in Figures 2b and 2d respectively, which validates the necessity of our attack design.

---

20
X-11
X-00
15
0pm05
0.75
X:005
1.0
0.50
0.00
0.0
0.2
0.4
0.6
0.8
1.0
05
0.2
0.4
0.5
0.8
1.0
(a) Cost as Ao varies
(b) Cost as a varies
Figure Impact of algorithmic and problem parameters on PBM-UCH
1.00
Triiae Thiake
0.8
0.75
3.0
0.6
0.50
0.22
0.5
Trsiale
Our attact
0.00
0.0
Tivile
1.9
0.8
0.0
0.8
1.0
(a) Chosen ratio (syn.)
(b) Cost (syn.)
(c) Chosen ratio (real)
(d) Cost (real)
Figure 2: Companion with baseline algorithms.
Concluding Remarks
This paper presents the first study adversarial attacks against OLTR with click feedback. We propose attack strategies that can successfully mislead various OLTR algorithms across multiple click models. One limitation of our work is that cannot be applied feedback models without clicks, such as the top-K feedback [33. Although we provide theoretical results for all these strategies, as discussed in Section 3.3 the finite-time
results might be further improved by more fine- fneeggained analysis on ha (t). Additionally, there no known lower bound for the cumulative attack cost, even for the stochastic bandit setting in the literature, making it unclear whether our attack strategies (asymptotically) order-optimal. This study opens up several future directions. One is to design attack strategies for other OLTR algorithms and feedback models. Lastly, our study on the vulnerability of existing OLTR algorithms inspires the design of robust OLTR algorithms against adversarial attacks.
Acknowledgments and Disclosure of Funding
Shuai Li is supported by National Key Research and Development Program of China (2022ZD01 14804) and National Natural Science Foundation of China (62376154, 62006151, 62076161). M. Hajiesmaili's work is supported by CAREER-2045641, CNS-2102963, CNS- 2106299, and CPS-2136199, Wierman is supported by NSF grants CNS-2146814, CPS-2136197, CNS-2106403, NGSDI-2105648.
References
[1] Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari. and Zheng Wen. Online learning to rank in stochastic click models. In International conference on machine learning, pages 4199 4208. PMLR, 2017.
[2] Shuai Li, Tor Lattimore, and Csaba Szepesvári. Online learning rank with features. In International Conference on Machine Learning, pages 3856-3865. PMLR, 2019.
[3] Tor Lattimore, Branislav Kveton, Shuai Li. and Csaba Szepesvari. Toprank: A practical algorithm for online stochastic ranking. Advances in Neural Information Processing Systems, 31, 2018.
[4] Paul Lagrée, Claire Vernade, and Olivier Cappe. Multiple-play bandits in the position-bases model. Advances in Neural Information Processing Systems, 29, 2016.
10

---

[5] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank the cascade model. In International conference on machine learning, pages 767-776. PMLR, 2015.
[6] Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129-136, 2007.
[7] Tie- Yan Liu et al. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, ((3):225-331, 2009.
[8] Fatih Cakir, Kun He, Xide Xia, Brian Kulis, and Stan Sclaroff. Deep metric learning to rank. In Proceedings of the IEEE/CVF conference on computer vision and paltern recognition, pages 1861-1870, 2019.
[9] Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. Advances in Neural Information Processing Systems, 31, 2018.
[10] Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pages 4042-4050. PMLR, 2019.
[11] Yinglun Xu, Bhuvesh Kumar, and Jacob D Abernethy, Observation-free attacks on stochastic bandits, Advances in Neural Information Processing Systems, 34:22550-22561, 2021.
[12] Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[13] Sougata Chaudhuri and Ambuj Tewari. Online learning to rank with top-k feedback. The Journal of Machine Learning Research, 18(1):3599-3648, 2017.
[14] Junpei Komiyama, Junya Honda, and Akiko Takeda. Position-basee multiple-play bandit problem with unknown position bias. Advances in Neural Information Processing Systems, 30, 2017.
[15] Beyza Ermis, Patrick Ernst, Yannik Stein, and Giovanni Zappella. Learning to rank in the position based model with bandit feedback. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, pages 2405-2412, 2020.
[16] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015.
[17] Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascad- ing bandits for large-scale recommendation problems. Thirty-Second Conference on Uncertainty in Artificial Intelligence, 2016.
[18] Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference machine learning, pages 1245-1253. PMLR, 2016.
[19] Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. Advances in Neural Information Processing Systems, 2022.
[20] Xutong Liu, Jinhang Zuo, Siwei Wang. John CS Lui, Mohammad Hajiesmaili, Adam Wierman, and Wei Chen. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning, pages 22559-22599 PMLR, 2023.
[21] Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Dem bandits: Learning to rank with multiple clicks. In International Conference Machine Learning, pages 1215- 1224. PMLR, 2016.
[22] Weiwen Liu, Shuai Li, and Shengyu Zhang. Contextual dependent click bandit algorithm for web recommendation. Computing and Combinatorics: 24th International Conference, COCOON 2018, Proceedings 24, pages 39-50. Springer, 2018.
11

---

[23] Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems, 33:14362-14373, 2020.
[24] Yuzhe Ma and Zhijin Zhou. Adversarial attacks on adversarial bandits. International Conference on Learning Representations, 2023.
[25] Huazheng Wang, Haifeng Xu, and Hongning Wang. When are linear stochastic bandits attackable? In International Conference on Machine Learning, pages 23254 23273. PMLR, 2022.
[26] Movielens 20m dataset. http::///ggaoo.oooooo///attttttp
[Online].
12

---

Appendix
A Proofs
A.1 Proof of Lemma
Proof. When 7 Sre, it is easy check ot [xe] S r thus r (0,1).
When 7t > re. if 9t S rt. we will have ar = [%,] - rg and r. [0,1), Since % depends on as goal is show % rg for any de Consider any arm K. We denote taj the j-th time that the UCB algorithm played a. Since the UCB algorithm would play each arm one time in the beginning, we have
Ma. S
[
S rl...
(8)
Next, want show that if Feos S Sraaw Menst S consider two cases:
r "aasst Since 5n also depends on ba, (t
1),
1) Ttus S rhuss In this case, we have Haa (la.stt1 1) la.j. We can bound Taai using Me.s
Otais [l (Has)) 20] S Sra (oatt1
Majti S Maas ftast1
where the second inequality is due to Wan I OCtais"
0 2) Maus > raas" In this case, we have hallaat1 - 1) = bollos 1). We can bound M...ia using
Ptas
Na.st S Ma.s + +ro ata.s [4, (haltas 11) - S S toats
(10)
where the second inequality is due to Hto. I rra., and Htom S Ot..ss
Since Na. I ro. by induction, we have Meo.s S rla, for any a. which concludes the proof.
A.2 Proof of Theorem 1
Proof. We use the following two lemmas to prove Theorem [ The proof is similar to those of Lemma and Lemma in (9), while as discussed in Section 3] the algorithm in 99 relies on Eq. (T) that may hold due to the binary feedback, and our proof mainly based on Eq. (4) that can be ensured by the conservative estimations. Define event E == (Vi, 4I > L: 17 (t)
< ((N,()))) With
Hoeffding's 's inequality, easy to prove for (0, 1), (F)) > 8.
Lemma 2. Assume event E holds and 5 S 1/2. For any + L and any t 2 L, we have
Na(1) < min (N.
log 1}
(11)
A
Proof. Fix some t 2 L. We consider a, previous round that a was pulled. Since arm a should be pulled at least once by the UCB algorithm, we have t' 2 1, and the attack in round t' would ensure
L and denote t' maxfs < t a, a} as the
(aa(t)) & 1 (haa(t)) Ag-
(12)
Since arm a was pulled in round t, we know its UCB value must be greater than that of target arm L:
3 log(1)
3
log(t)
Paatt - 1)+ 2 Na -) 2 fin
1) (t 2
(13)
Nu(t 1))
Considering that I' and are consecutive rounds when was pulled, have fia
(ta)t) and Na(t 1) = Na(t'). Rearranging Eq. (13 we get
3
log(t)
log(t) 2 At 1) (t)) 2 (t - 1)- (4, (ha(t')) - -o) 2 Ao. (14)
2
Na(t)) 2
Nt
13

---

where the second inequality comes from Equation 12
Since Ao > O, we have
(a(t) Na(t))+1 N2 - 1) = (t)...
(15)
Also, since
log(() O, we have //
log(t1 Na)
Ao, which implies
(t-1-1)
3
= Na())
log(t).
(16)
D
Lemma 3. Assume event E holds and 1/22.
1) For any I. 2 L, the cumulative attack cost to any fixed arm + L can be bounded as:
Σ S. (a(0 + Ao + (M) ((N(())) +1
(17)
(1)
2) When goes infinity, we have
Exera(t) Cg
3 (Aa + Ao)
lim
S
(18)
logt
A
Proof. Fix any arm a * L. By the definitions 7 and 7t it follows that:
Σ (ETa(1)
a, <
Σ a, 11
(19)
(ETx(t-1)
S (a(1)2((1) Na(t) L (ha(t - 1)) - Ao] +1
(20)
S (a)t) A. + 33(N (t))) + ((N, + 1,
(21)
where the last inequality is due to the decrease of B. For the asymptotic result, combining Lemma with Equation
7
we have
EvET.( ax+
No 1 log(()
lim 1000
lim
[ + 38((N. + ((N. + log(t)
(22)
logt
3
lim
[A. +
((N) + log(!)
(23)
log(t)
Ao 2
easy to check that lim, B(1) = 0. Hence, to get the asymptotic cost bound the lemma, we need to prove lim,, ((N, ((,,,(h.(()) other words, ha (4) should be always updated when goes to infinity. To obtain this, we consider two cases of 76-
O. We find li ha) = / is a sufficient condition for it;
1) H, (t) Do 2 O, we have
lim 7 = lim (t)
Σ a, (t( 23(N2(()) -o))
1100
(ETa(t-1)
lim (t) - (N(t)) (3())(h Ao) + av
+000
(100)00.00.()))-0000((((0.)0 -o) - (.(()((nn() 23(Nr(()) -Ao) lim (r] ar + (a(tt) (300)((((()))) -A)) (PL 23(NN(t)) -Ao))
<r lim (ha - (t) (h (Pc(t) -o))
5
The first inequality due to the attack at round L' The last inequality is due to the confidence radius based on (ha (t'))) and 3 is decreasing.
14

---

If If , (t) - -o < 0, we have (t) < (t) and PL (2
lim 7t re + lim (Na(t')A((t)
Σ a²)
SETalt-1)
r + lim (a(t')aa(t)
S r + lim (ha())) (3(NN(haat))) -a)
1000
S r + lim
No (N(())
t0o
Since in both cases, 7/ rf. we have ha (t) when goes to infinity.
With Lemma 2 and Lemma 3. the proof is completed by summing the corresponding upper bounds all non-target arms
A.3 Proof of Theorem 2
Proof. As for Algorithm I we first need to prove the post-attack feedback of Algorithm i always valid. It is equivalent to showing that the output of Algorithm iis valid attack value on the input pre-attack feedback r0, i.e. a S r Similar to the proof of Lemma I we consider two cases: when Tmax < r0,
the same inductive proof of Lemma | to show that a = [max S 70. Thus, the post-attack feedback rd a is always valid.
Ymax| S r0; when Ymax <>", we
Fix some t 2 such that di.t & a'. We denote t' = max(s < t: di,t E a.} as the previous round that 0z was chosen. With the conservative estimations in 7/e (e, a) and 9e (as,,, a), the output og of Algorithm could ensure
(ha,,.a (t), S Pa Wa 1)) 2 1))) - Ao:
(24)
for any a". Since ag is chosen by the PBM-UCB algorithm, there must exist a" with its UCB value less than that of az,t:
Pa 1) Ba(t) S (t- 1) Ba,..
(25)
Since t' and are two consecutive rounds when item at,z was chosen, we have Poo, (t 1) Par, (t),, Nas, 1) Na.,, (t'). Rearranging Eq. (25), have
Bor. (t) (t) 2 At 1) - Paa.. (t') 2 Do.
(26)
where the last inequality is due to Eq. 24h. Since B (1) 2 Do. with the definition of Bag, (4) in Eq. (5), we have
1 logl,
No., (1)
(27)
2n A3
for any ase & a". Thus, for the target item L,
1+c log T
NL 2 T Σ N((T) M(T)
(28)
Ax
Iga"
which guarantees the chosen time of the target item.
For the cumulative attack cost analysis, we consider any arm ai,t & a", Since Eq. (2 holds for any E a", we take L and get
Olagass S Na., (1) Aaas + Do + ( (1)) 3(N.,, (1)
(29)
RETaLe()) (t)
S Na.. (t) D + Ao + 43(N (
(30)
where the second line is due to No.. (1) < hos, S Na,, . (l), and 3 is decreasing. Based on this inequality, we can follow the same steps in the proof of Lemma to derive the upper bound of the cumulative attack cost for Algorithm
15

---

A.4 Proof of Theorem 3
we can use the same proof in Appendix A.3 to show its post-attack feedback is always valid. Also, the output as,t of Algorithm would still ensure Eq. (24) for any at. a", va E a'. Based on this, we can consider the post-altack problem cascading bandit problem with known expected reward gaps, where the expected reward of any item 1 E a" is less than that of the target item by least Åg. Since is the worst item in a", with the regret analysis of CascadeUCB in [5]. we know the regret caused by any list containing / & a is bounded by
Proof. Since Algorithm also calls Algorithm 3
12
RT(T)= I
log T.
(31)
An
We also know the lower bound of the one-round instantaneous regret caused by any list containing ( I 14:- can then write the lower bound of (T) as
y" Do, where p²
RT( 2 p" Ao ([N)
(32)
Combinining Eq. 31 and Eq. dations of item
32
we obtain the upper bound of the expected number of recommen-
12
E[N((T)] S P²A
log T.
(33)
Thus, for the target item L.
E[N Σ 2T K)
A log T
(34)
Iga"
For the remaining cost analysis, since the attack cost only depends on the observed items. we can we need change the confidence radius (t in Eq. (5) the
still follow the proof of Theorem [
typical form
logt N. 1j.
then derive the corresponding cost upper bound.
A.5 Proof of Theorem
Proof. Since Algorithm only attacks when r. = 1. it is easy to verify its post-attack feedback valid. The key step for proving its successful attack to show that Pi,: an upper bound of Doce/ Dole/Moz.. if it is true, by the probabilistic attack with probability Pi,t, Algorithm 5 makes a post- attack bandit problem where the expected reward of any item & a* is worse than that of target item L, which guarantees the number of target arm pulls is T R(T). Actually, we have
A as.
Pas,
PL
(35)
Maza
Paia
which increases as Pa,,, increases. Replacing Moi, with pay, (1) + 3NNo.N (t)),
[a (1) (N, (1)) p. (t) (((())+BNN(())) pa_. (t) (t)..
Dani < paa. (1) B(N,,, (1)) - pr. pa. (t) + 3(Na,, (t))
(36)
Pac.
where pa,, (t) + 3(N.,, (t)) 2 Mar, and (t) + (t) 2 Hr. under event E. Since the last term is the definition of Pt,t, we have proved it is high--robabilliy upper bound of Du,./ / For the cost analysis, we have
C(T) <
pa., (t)+ (B) (1) + Hare $ a'}
(37)
S Σ [Mar. + +2,(Na,, (1)) pr. + 28(N &a))
(38)
0 Σ (An + 43(1)) ((T))
(39)
which concludes the proof.
16

---

B Additional Experiments
B.1 Synthetic Data
We first consider adversarial attacks on 2-armed stochastic bandits with binary feedback. The rewards of arms and follow Bernoulli distributions with means μn and μ2 (/1 > (22). We designate
as the target arm. We take I" = 10, 000, 8 = 0.1, Ao = 0.1. We set μ사 = 0.85 and sample the value of P2 from uniform distribution (0.055, 0.15). We compare Algorithm [ with modified algorithm from 19], which attacks every non-target arm whenever the calculated
0 and the pre-attack feedback is one. Note that this modified algorithm lacks theoretical guarantee. We show the costs and target arm chosen times relative to trivial baseline, which sets the post-attack feedback of all non-target arms to zero as long as the pre-attack feedback is one. Figure 3 demonstrates that our algorithm is more efficient than the modified one, incurring fewer costs for greater number of target arm selections.
We also conduct experiments under the cascade model with synthetic data. We take L = 16, K = 100, 000, and {ui are sampled from uniform distribution U(0, We compare 4 with the same baselines introduced in Section 5 Figure 4 shows that Trivialal Algorithm algorithm suffers an extremely high cumulative cost, while cannot misguide the agent recommend the target arm very often. On the other hand, our algorithm and Trivialgs algorithm can successfully attack CascadeUCB and perform similarly on the chosen ratio of the target arm. However, our algorithm pays about 30% less cost than Trivialye-
B.2 Real Data
As discussed in Section have shown results under the position-based model with real data. We now show the experimental results with real data (MovieLens 20M dataset) under the cascade model. We take
100, K 10, T 100, 000; { are extracted according to [2. Similarly, we compare the chosen ratio and cumulative cost of our algorithm with Trivialal and Trivialgt- Figure [ shows that Trivialal cannot successfully attack CascadeUCB as the chosen ratio of the target arm is very low and it suffers linear cost. Algorithm 4 and Trivialye have similar performance on the chosen ratio of the target arm. However, our algorithm dramatically decreases the cost by more than 50%, which indicates that it is more effective than Trivialget
17

---

0.25
1.5
Our attack
Chosen times
0.00
1.0
Cast
0.25
0.5
-0.50
0.0
-0.75
Our attack
-1.08 0.25
0.50
0.75
1.00
1:25
1,50
0.25
0.50
0.75
1.00
1.25
1.50
μ2
U2
(a) Relative Cost
(b) Relative chosen times
Figure 3: Attacks against UCB 2-armed bandits with binary feedback.
0.8
Chosen ratio
Our attack
35
Triviali
0.4
Triviale
0.6
Triviala
0.0
0.0
0.2
1.0
0.2
0.4
0.6
(a) Cost
(b) Chosen times
Figure Attacks against CascadeUCB with synthetic data.
1.00
1.25
1.00
Chosen rabio
0.75
0.75
0.50
triviaa
0.50
0.25
0.25
triviala triviahe
0.00
0.00
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(a) Cost
(b) Chosen times
Figure 5: Attacks against CascadeUCB with real data.
18


Reviews:
[{"review_id": "g6qgTcVFIq", "reviewer": "Reviewer_7TEH", "summary": "This paper studies attack strategies against UCB-based OLTR algorithms for position-based click model and cascade click model. Compared with prior works in adversarial attacks, OLTR problem leads to the additional challenge that the rewards are discrete and bounded, which requires different attack method design, i.e., to ensure the post-attack reward is valid. The authors further propose attack strategy that works for OLTR algorithms with general click models, at the expense of additional attack cost compared with the strategies designed for specific click models.", "questions": "Can the authors provide more explanation on why constructing the set $a^{\\star}$ by randomly selecting $K-1$ items, in addition to the target item $L$? Since the goal is to make target item $L$ appear in the recommended set $a_{t}$, why do we want to spend cost on making the learner recommend the $K-1$ randomly sampled items as well? Is it possible to simply making sure L replaces the last item in $a_{t}$?\n\nThe reason the current design (for single target item) seems to be sub-optimal is that, this algorithm can be directly applied to the case where there are more than 1 but less than K+1 target items, without incurring additional cost, i.e., the algorithm will need to spend cost in making the learner pull $K-1$ randomly selected items anyway.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is well-written and seems to be technically sound.\n\nTo the best of my knowledge, this is the first work that provides rigorous solutions and analysis for attacking OLTR algorithms.\n\nThe designed attack strategy for discrete and bounded reward might be of independent interest, e.g., it may be applied to other problem settings with discrete reward.", "weaknesses": "I think a more intuitive (and self-contained) explanation, on why the use of conservative estimation can address the challenge caused by bounded reward, would be helpful. The current writing of Section 3.2 requires some knowledge of of [9] to fully understand the intuition and appreciate its novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. *Intuitive explanation of conservative estimation.*\n\n**A1**. The main idea of the attack algorithm in [9] is to calculate the attack value per round such that the post-attack empirical estimates of the non-target arms are always less than that of the target arm (i.e., Eq. (1)). However, with binary feedback, if we follow their original design, the calculated attack value can be greater than one, thus it is an invalid attack value and Eq. (1) required by their theoretical analysis can not hold.\nWe resolve this issue by using the conservative estimation of the target arm: a conservative lower bound of the target arm's mean is used in Eq. (2) and Eq. (3) to determine the attack value. Intuitively, it makes the attacker more conservative to use a small attack value (that may result in an invalid large attack value in later rounds). It ensures the calculated attack value is always valid and Eq. (4) holds for all rounds (required by our new theoretical analysis). We will revise the explanation of the conservative estimation in the updated version.\n\n\n**Q2**. *Explanation on why constructing the set by randomly selecting items. Is it possible to simply making sure $L$ replaces the last item in ${a}_t$?*\n\n**A2**. Different from the simple $L$-armed bandit setting where only a single item will be checked by the player, in OLTR, all items in the recommended list can be checked by the player (depending on the click model). Thus, in addition to putting the target item in the recommended list, we also need to ensure that the attacker does not have to attack the other items in the list too often. By randomly selecting $K-1$ items to build a set with the target item, our attack algorithm will only attack those items outside the set, and the recommended list will gradually only contain the items in the set. This is a simple solution to control the attack costs on the other items in the recommended list and we prove in Theorems 2, 3, 4 that it only requires sublinear costs.\n\n**Q3**. *The current design (for single target item) seems to be sub-optimal.*\n\n**A3**. For the single target item case, if we know the best $K-1$ items in advance, a better solution might be attacking the remaining items except for the target item (i.e., using the best $K-1$ items to build the set with the target item). However, we consider the setting without prior knowledge of all items; learning the best $K-1$ items while doing attacks can be complicated since the attacker's observation depends on the player's action and the player's action is affected by the attacks. Although a better solution might be possible with a more carefully design of the joint learning and attacking, our idea of randomly sampling $K-1$ items can be directly applied in attacking most OLTR algorithms with different click models, while learning the best $K-1$ items needs to be algorithm/model-specific. We will add this discussion in the updated version."}, {"review_id": "Kkfgg0Ky02", "reviewer": "Reviewer_i6fi", "summary": "This paper studies adversarial attack to online learning to rank, where a successful attack to an OLTR algorithm is such that a suboptimal item is recommended for linear in T times while with log T cost. This paper approaches this attack problem by studying attack to discrete MAB as warmup and then moves on to attack UCB based OLTR algorithms under position and cascade models. Lastly, it ends up with an attack strategy for general algorithms and click models, both theoretical and simulation results are provided to justify the attacks being successful.", "questions": "Major question please refer to weakness 1.", "limitations": "Identified Limitations are listed in Weakness and Question.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Adversarial attack to online learning to rank makes up the foundation for studying robust/trustworthy recommendation systems. I agree some research into this topic is a must-do.\n2. This paper is well written and easy to read. It appears to have a thoughtful path to break down the OLTR attack problem in a few pieces and tackle it step by step, which is good. However, I doubt, which is also my major concern for this paper, that are some of the steps necessary to derive a successful attack? See details in weakness I list below.", "weaknesses": "**Possibly overcomplicates the problem**\n\nThere’s another work [1]https://arxiv.org/pdf/2305.19218.pdf on arxiv that seems to study the same problem as this paper. This paper retains novelty as these two can be considered as concurrent works according to the arxiv one’s submission date. But interestingly, [1] seems to have conflicted results from this paper:\n\nThe major tension lies in this paper proposes to alter clicks of unwanted arms with a sophisticated probability (e.g. in Alg.5), while [1] simply set 1 to 0 when an unwanted arm has a click. Moreover, this paper tests in simulation a baseline attack Trivial_1, which is close to the attack proposed by [1] (except for  [1] has a cutoff time for attack), and this paper claims Trivial_1 fails to attack according to the plot. And not surprisingly, theorem and simulation results in [1] supports their attack. \n\nSo this finding casts some doubt on this paper whether it overcomplicates the problem, as the attack proposed in [1] is way simpler with no need to compute a sophisticated probability to attack. Here are some clues in this paper that I think questionable:\n\n1. In Section 3.2, it claims that the challenge in applying previous MAB attack to discret MAB is $\\alpha_t$ in (1) can be invalid (>=1) when the altered reward should keep binary, which leads to all the effort in finding a new  $\\alpha_t$ with care. But simply setting all returns for unwanted arms to be 0 may also get the job done.\n2. Simulation section shows that Trivial_1 fails while Trivial_{k-1} succeeds,I don’t think Trivial_{k-1} has essential difference than Trivial_1 as in the special case k=2 they are identical. So maybe there’s something going wrong with the plots or interpretation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. *Comparison with the other work [1].*\n\n**A1**. We thank the reviewer for pointing us to this related work. We kindly remind that the submission date of this arXiv paper is after the NeurIPS deadline. We would like to make some clarifications on the difference between our work and theirs.\n\n1) Attack objective. Our attack objective is to manipulate the learning agent to put the target item into the recommended list, while their goal is to place the target item on top of the list. These objectives are related but different: their objective requires additional assumptions about the candidate items and the prior knowledge available to the attacker, while our model does not make any assumption about the items and our algorithms do not need any prior knowledge.\n\n2) Algorithm and assumption. The click poisoning attack strategy attack-then-quit (ATQ) in [1] can only be applied to elimination-based rankers BatchRank and TopRank: it not only sets the clicks of the non-target items to be zero but also sets the clicks of the target item to be one, thus will incur linear attack costs for any non-elimination-based ranker (e.g., PBM-UCB, CascadeUCB) without a cutoff time. Our attack algorithms are more relevant to their generalized list poisoning attack strategy GA against PBM-UCB and CascadeUCB. For their GA algorithm, they assume that there exist $2K-1$ low attractiveness items, and the algorithm needs to know them in advance; this is due to their objective of placing the target item on top of the list. However, with our objective of placing the target item in the list, we do not make any assumption about the items. Also, their theoretical analysis of GA mainly holds for rankers with a unique optimal list (from their Definition 2), while our Algorithm 5 can successfully attack arbitrary OLTR rankers.\n\n3) Attack cost. We focus on fine-grained attack design against OLTR with click feedback and provide problem-dependent attack costs adaptive to the difficulty of the problem ($\\Delta_a$ in Table 1), while they mainly consider the order of the attack cost in $T$ to be sublinear, i.e., $o(T)$. Such problem-dependent cost analyses are also highlighted in previous works [9, 10].\n\nTo sum up, with our objective of manipulating the learning agent into choosing the target item, we propose attack algorithms without additional assumptions and prior knowledge about the candidate items. Our attack design and analyses are more involved as our goal is to derive fine-grained problem-dependent attack costs adaptive to the problem difficulty, which cannot be achieved by simple attack design and play an essential role in understanding the vulnerability of OLTR under adversarial attacks.\n\n**Q2**. *Conflicted results about the Trivial$_1$ baseline.*\n\n**A2**. As mentioned in A1 (2), the GA algorithm in [1] uses the known low attractiveness items to build a list with the target item, and then sets the clicks of all items outside the list to be zero. Our Trivial$_1$ is actually different from GA since it does not build any list and just sets the clicks of all items except the target item to be zero. Trivial$_1$ fails because it always needs to attack the other clicked items in the recommended list and incurs linear attack costs (see A2 to Reviewer 7TEH for more details). Thus, our experimental results do not conflict with those in [1].\n\n**Q3**. *Why not simply setting all returns for unwanted arms to be 0?*\n\n**A3**. As discussed in A1 (3), we would like to design attack algorithms with fine-grained problem-dependent attack costs adaptive to the problem difficulty, since non-adaptive attack strategies need to pay unnecessarily large attack costs. Notice that the problem-dependent cost analysis would be much more challenging than the analysis of the cost order in time horizon $T$, which is one of our technical contributions.\nFor the $L$-armed bandit problem with binary feedback, simply setting all returns of non-target arms to be $0$ can indeed succeed, but its attack cost will depend on $\\mu_a$ instead of $\\Delta_a$, which is undesirable compared to previous results in [9, 10]. For OLTR with click feedback, Trivial$\\_{K-1}$ has the same issue that the problem-dependent parameters in the attack cost can be much worse than those of our proposed algorithms. This is validated by our experiments on both synthetic and real data: Figures 1 and 5 show that our algorithm pays around $40\\\\%$ less costs than Trivial$\\_{K-1}$ for both PBM-UCB and CascadeUCB.\n\n**Q4**. *Trivial$\\_1$ and Trivial$\\_{K-1}$ when $K=2$.*\n\n**A4**. Trivial$\\_{K-1}$ means taking $K-1$ items out to build a set with the target item, so when $K=2$, it will still take $1$ item out to build a set with the target item and is different from our Trivial$\\_{1}$ that does not build any set. As mentioned in Q2, Trivial$\\_1$ needs to attack all clicked non-target items in the recommended list, while Trivial$\\_{K-1}$ only attacks the non-target items outside the built set. The performance of Trivial$\\_{K-1}$ is still better than Trivial$\\_{1}$ when $K=2$. Thanks for capturing this naming issue and we will change these names to Trivial$\\_{\\text{all}}$ and Trivial$\\_{\\text{set}}$ and in the updated version."}, {"review_id": "kWLuPC9wsr", "reviewer": "Reviewer_carj", "summary": "The paper introduces adversarial attack on online learning to rank. The attacker aims to fool the online learning to rank algorithm to choose the target item. The paper studied three victim models: stochastic L-armed bandit, OLTR with position-based model and OLTR with cascade model. Authors proposed three attack algorithm respectively for three victim models and a general attack strategy to attack arbitrary OLTR algorithms without knowing the details of the algorithm. Their theoretical analysis and experimental results show that the proposed attack strategies can manipulates the learning agent into choosing the target attack item in linear time but incurring a sublinear cost.", "questions": "See in weakness 2.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studied adversarial attacks on online learning to rank with click feedback, which as far as I know is the first work in this field. The paper provides some theoretical guarantees on their proposed algorithms. The results show that the attack strategies can successfully attack OLTR algorithms with sublinear cost. The paper is well-written and well-organized. The attack strategy on the UCB algorithm clearly shows that the differences between this work and previous work about reward attack on bandits.", "weaknesses": "Overall, the paper is well-written and has good technical content, but I have the following concerns:\n\n1. An intuitive attack method is that the attacker first chooses an action (list) $a$ including the target items and sets the reward out of this list to 0. The authors name this as $Trivial_{k-1}$. The authors empirically compared the proposed methods with $Trivial_{k-1}$, which is good. However,  $Trivial_{k-1}$ seems to keep the same cost scaling on time as the proposed attack strategies, which weakens the contribution of this work.\n\n2. There is no lower bound about the attack cost and any information. Compared with $Trivial_{k-1}$, The proposed attack algorithms improve the attack cost by a constant ratio. How far is the proposed attack strategies to the optimal?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. *Trivial$\\_{K-1}$ seems to keep the same cost scaling on time as the proposed attack strategies.*\n\n**A1**. We admit that the attack cost of Trivial$\\_{K-1}$ is in the same order of $O(\\log T)$ as our proposed algorithms. \nHowever, our algorithms achieve problem-dependent attack costs adaptive to the problem difficulty, which have better problem-dependent parameters than those for Trivial$\\_{K-1}$ (see A3 to Reviewer i6fi). \nTrivial$\\_{K-1}$ needs to pay unnecessarily large costs as it attacks all items outside the built set using the most aggressive attack values thus is not adaptive to the problem difficulty. \nOur experimental results in Figures 1 and 5 also validate our theoretical findings.\nWe would like to highlight that we are the first to propose the attack algorithms with problem-dependent attack costs against OLTR with click feedback, which requires more involved fine-grained cost analyses than the analysis of the cost order in time horizon $T$. \nSuch problem-dependent cost analyses are also the main focus of previous works on $L$-armed stochastic bandits [9, 10], which is essential to understanding the vulnerability of bandit algorithms under adversarial attacks.\n\n**Q2**. *There is no lower bound about the attack cost.*\n\n**A2**. The lower bound of the attack cost is hard to derive since the attacks will change the stochastic environment to a non-stochastic environment in which the behaviors of the stochastic bandit algorithms are unclear. The only known lower bound result [A] is for attacks against adversarial bandits where the pre-attack and post-attack environments are both adversarial. \nSuch lower-bound analysis in the adversarial setting is a tractable question since the performance of the adversarial bandit algorithms under both the pre-attack and the post-attack environments is measurable.\nHowever, in the stochastic setting, this is not the case since the performance of the stochastic bandit algorithms under the post-attack adversarial environments is unclear. Hence, all previous works on attacks against stochastic bandits [9, 10, 11] do not have lower-bound results. \nAlthough the lower bound of the attack cost against stochastic bandits is still an open problem, our proposed algorithms for OLTR with click feedback achieve the same dependency on problem-dependent parameters $\\Delta_a$ in the asymptotic costs as that for stochastic bandits with continuous and unbounded feedback [9, 10].\n\n[A] Yuzhe Ma, and Zhijin Zhou. Adversarial Attacks on Adversarial Bandits. In ICLR, 2023."}, {"review_id": "f4i3siYpRg", "reviewer": "Reviewer_E7da", "summary": "This paper presented a study of reward poisoning attacks on UCB bandit algorithms with binary feedback and applies the designed attack to the online-learning-to-rank (OLTR) problem. The binary reward structure poses unique challenges to reward poisoning attacks, since the attacker needs to ensure the perturbed reward is still binary. The authors proposed an attack algorithm that achieves that. Based on that, the paper studied reward poisoning attacks in OLTR. The attacker is limited to change the click feedback, which is required to be binary before and after attack. Two threat models are considered - in the position-based click feedback scenario, the authors proposed attack strategy targeting the PBM-UCB algorithm; and in the cascade-click model, attack strategy against CascadeUCB is proposed. Both achieve T-O(log T) target item selections with only O(log T) attack cost. The paper also designed a general attack strategy for arbitrary click models that achieve O(log T) sub-optimal item selections. Finally, the paper performed empirical evaluations of the attacks.", "questions": "(1). Can the author make the assumption in Theorem 4 more prominent?\n\n(2). Is O(log T) sub-optimal item selections a critical assumption in Theorem 4? Can the authors extend the result to arbitrary no-regret ranking algorithms that guarantee o(T) suboptimal item selections?", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1). The paper first studied data poisoning attacks on ranking algorithms, which is timely topic following prior works that study reward poisoning attacks on multi-armed bandit. Although the idea behind the design of the attack algorithm is similar in nature, poisoning ranking algorithms poses unique challenges compared to bandits - the attack needs to ensure the poisoned reward is still binary. \n\n(2). The theoretical analysis of this paper is solid. First, an efficient attack targeting the UCB bandit algorithm is proposed, which guarantees that the poisoned reward is still binary. Then two theoretical results are presented to show that UCB-style ranking algorithms are susceptible to poisoning attacks in both position-click and cascade-click scenarios. Finally, the paper also provided a general attack for general click model ranking algorithms.\n\n(3). The paper performed extensive empirical evaluations of the proposed attack strategies. The results are convincing.", "weaknesses": "(1). The assumption made in section 4.3 is hidden in Theorem 4 - the ranking algorithm needs to guarantee O(log T) sub-optimal item selections. This assumption is critical and should not be hidden inside the theorem. Instead, the authors should consider carefully defining the assumption.\n\n(2). The Theorem 4 is not intriguing enough. In particular, it needs to assume that the ranking algorithm guarantees O(log T) sub-optimal item selections. Is O(log T) critical? Can it be O(sqrt(T))? The problem is that O(log T) seems too specific. Instead, it makes more sense to assume the ranking algorithm is no-regret, i.e., it selects suboptimal items in o(T) rounds. In that case, does Theorem 4 still hold?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**. *Can the author make the assumption in Theorem 4 more prominent?*\n\n**A1**. Thanks for the suggestion. We agree it is better to define the assumption that the ranking algorithm would choose suboptimal items sublinear times more explicitly. We will make it as a separate assumption in the updated version.\n\n\n**Q2**. *Is $O(\\log T)$ sub-optimal item selections a critical assumption in Theorem 4? Can the authors extend the result to arbitrary no-regret ranking algorithms that guarantee $o(T)$ suboptimal item selections?*\n\n**A2**. Thanks for raising this excellent point. We can indeed extend Theorem 4 to arbitrary ranking algorithm with $R(T) = o(T)$ suboptimal item selections. The chosen time of the target item will become at least $T-R(T)$ in expectation, and the cumulative attack cost is at most $C(T) \\le O\\left(\\sum_{a<L}(\\Delta_a + 4\\beta(1)) R(T) \\right)$. \nThe changes in the proof will be line 473 and Eq. (39) in the Appendix. For line 473, since Algorithm 5 still makes the expected reward of any item $l \\notin {a}^*$ be worse than that of the target item in the post-attack problem, the number of target item pulls determined by the ranking algorithm directly becomes $T-R(T)$. For Eq. (39), the replacement of $\\mathbb{I}\\\\{a_{i,t} \\notin a^*\\\\}$ in Eq. (38) is only affected by the ranking algorithm, thus we can use $R(T)$ to replace $\\log T$ in Eq. (39).\nNotice that Algorithm 5 does not have to know $R(T)$ beforehand, so it works without knowing the details of the ranking algorithms. We will include this extension in the updated version."}]

Author rebuttal:

Meta-review: This paper studies reward poisoning attacks against online learning to rank (OLTR) where the rewards are discrete and bounded.  Attack strategies are proposed against UCB-based algorithms for position-based click model and cascade click model, and both achieve T-O(log T) target item selections with only O(log T) attack cost. The paper also designed a general attack strategy for arbitrary click models that achieve O(log T) sub-optimal item selections. 

Overall, the reviewers are all positive to the paper.  The reviewers appreciate that the problem is well-motivated and the theoretical results are sound. There are concerns regarding the attack target and advantages against baselines, and the authors' responses resolved the concerns. I am happy to recommend acceptance. The authors are suggested to incorporate the response and discussion into the final version.
Decision: Accept (poster)