Adversarial Attacks on Online Learning to Rank with Stochastic Click Models
Authors: Zichen Wang
Rishab Balasubramanian
Hui Yuan
chenyu song
Mengdi Wang
Huazheng Wang
Venue: Accepted by TMLR ()

Abstract: We propose the first study of adversarial attacks on online learning to rank. The goal of the attacker it to misguide the online learning to rank algorithm to place the target item on top of the ranking list linear times to time horizon $T$ with a sublinear attack cost. We propose generalized list poisoning attacks that perturb the ranking list presented to the user. This strategy can efficiently attack any no-regret ranker in general stochastic click models. Furthermore, we propose a click poisoning-based strategy named attack-then-quit that can efficiently attack two representative OLTR algorithms for stochastic click models. We theoretically analyze the success and cost upper bound of the two proposed methods. Experimental results based on synthetic and real-world data further validate the effectiveness and cost-efficiency of the proposed attack strategies.

Published in Transactions on Machine Learning Research (09/2024)
Adversarial Attacks on Online Learning to Rank with Stochas- tic Click Models
Zichen Wang
zichenu6@rilinois..hh
Deportment of Electrical Computer Engineering & Coordinated Science Laboratory University of Mlinois Urbena- Champaain
Rishab Balasubramanian
bullesuri@orrgoossttt....
Department of Computer Science Oregon State University
Yuan Hui
hudyuann@princeton..el
Department of Electricol Computer Engineering Princeton University
Chenyu Song
songchen @oregonstate.cdo
Deportment of Computer Science Oregon State University
Mengdi Wang
mengglind@prinneton..cd
Department of Electrical Computer Engineering Princeton University
Huazheng Wang
huazheeng wang Boregnoreoossltte.com edu
Deportment of Computer Science Oregon State University
Reviewed on OpenReview: https: openreview. net/ forum? id= BKuGowROBt
Abstract
We propose the first study of adversarial attacks on online learning to rank. The goal of the attacker is to misguide the online learning to rank algorithm to place the target item on top of the ranking list linear times to time horizon with a sublinear attack cost. We propose generalized list poisoning attacks that perturb the ranking list presented to the user. This strategy can efficiently attack any no-regret. ranker in general stochastic click models. Furthermore, we propose click poisoning- based strategy named attack-then-gue that can efficiently attack two representative OLTR algorithms for stochastic click models. We theoretically analyze the success and cost upper bound of the two proposed met hods. Experimental results based on synthetic and real-world data further validate the effectiveness and cost-efficiency the proposed attack strategies.
1 Introduction
Ouline learning to rank (OLTR) (Grotov and de Rijke, 2016) formulates learning to rank (Liu et al., 2009), the core problem in information retrieval, as a sequential decision-making problem. OLTR is a family of online learning solutions that exploit implicit feedback from users (e.g,, clicks) to directly optimize parameterized rankers on the fly. has drawn increasing attention in recent years (Kveton et al., 2015a; Zoghi et al., 2017; Lattimore al., 2018; Oosterhuis and de Rijke, 2018; Wang al., 2019; Jia al., 2021: Wang et al., 2018; et al., 2021) due to its advantages over traditional offline learning- based solutions and numerous applications in web search and recommender systems (Liu et al., 2009).

---

Published in Transactions on Machine Learning Research (09/2024)
To effectively utilize users' click feedback to improve the quality of ranked lists, one line of OLTR studied bandit-based algorithms under different click models. In each iteration, the algorithm presents ranked list of K items selected from L candidates based on its estimation of the user's interests. The ranker observes the user's click feedback and updates these estimates accordingly. Different users may examine and click on the ranking list differently, and how the user interacts with the item list is called the click model. Many works have been dedicated to establishing OLTR algorithms the cascade model (Kveton et al., 20;;;; Zong et al., 2016; Li et al., 2016; Vial et al., 2022), the position-base based model (Lagrée and Vernade, 2016) and the dependent click model (Katariya et al., 2016; Liu al., 2018). However, these algorithms are ineffective when employed under a different click model. To overcome this bottleneck, Zoghi et al. (2017); Lattimore et al. (2018); Li et al. (2019) proposed OLTR algorithms with general stochastic click models that cover the aforementiones click models.
There has been a huge interest in developing robust and trustworthy information retrieval systems (Golrezaci et al., 2021; Ouni et al., 2022: Sun and Jafar, 2016), and understanding the vulnerability of OLTR algorithms to adversarial attacks is an essential step towards the goal. Recently, several works explored adversarial attacks multi-armed bandits (Jun et al., 2018; Liu and Shroff, 2019) and linear bandits (Garcelon et al., 2020; Wang et al., 2022) where the system recommends one item to the user in each round. The idea of the poisoning attack is to lower the rewards of the non-target item to misguide the bandit algorithm to recommend the target item using cost sublinear to time horizon T. In online ranking, we consider the goal of the adversary as misguiding the algorithm to rank the target item on top of the ranking list linear times (T (T)) with sublinear attack cost (o(T)). However, it is hard to directly extend the attack strategy on multi-armed bandits to OLTR since the click model is a black box to the adversary.
In this paper, we propose the first study of adversarial attacks on OLTR to misguide the rankers to place the target item on top of the ranking list. We study two threat models: click poisoning attacks where the adversary manipulates the rewards the user sends back to the ranking algorithm, and list poisoning attacks where the adversary perturbs the ranking list that are presented to the user. We first propose a generalized list poisoning allack strategy (GA) that can efficiently allack any no-regrel ranker for stochastic click models. The adversary perturbs the ranking list presented to the user and pretends the click feedback represents the user's interests in the original ranking list. This guarantees the feedback always follows the unknown click model, making the attack stealthy. Furthermore, propose click poisoning- based strategy named attack-then-qun thin-quit strategy (ATQ) that can efficiently attack two representative OLTR algorithms for stochastic click models, i.e., BatchRank (Zoghi et al., 2017) and TopRank (Lattimore et al., 2018). Our theoretical analysis guarantees that the proposed mothods succeed with sublincar attack cost. We empirically evaluate the proposed mothods against several OLTR algorithms on synthetic data and a real-world dataset under different click models. Our experimental results validated the theoretical analysis of the effectiveness and cost-efficiency of the two proposed attack algorithms. Our code and data can be accessed publicly for reproducibility...
2 Related Works
Online learning to rank. OLTR is first studied as ranked bandits (Radlinski et al., 2008; Slivkins et al., 2013), where each position in the list is modeled as an individual multi-armed bandits problem (Auer et al., 2002). Such a problem can be settled down by bandit algorithms which can maximize the expected click number in each round. Recently studied of OLTR focused on different click models (Craswell et al., 2008; Chuklin et al., 2015), including the cascade model (Kveton et al., 2015a;b; Zong et al., 2016; Li et al., 2016; Vial et al., 2022), the position-based model (Lagrée and Vernade, 2016) and the dependent click model (Katariya et al., 2016; Liu et al., 2018). OLTR with general stochastic click models is studied in (Zoghi et al., 2017; Lattimore et al., 2018; Li et al., 2018; 2019; Gauthier et al., 2022).
Adversarial attack against bandits. Adversarial reward poisoning attacks against multi-armed bandits have been recently studied in stochastic bandits (Jun et al., 2018; Liu and Shroff, 2019; Zuo, 2020; Xu et al., 2021; Lu et al., 2021), linear bandits (Wang et al., 2022; Garcelon et al., 2020), Gaussian process bandits (Han and Scarlett, 2021), adversarial bandits (Ma and Zhou, 2023), and combinatorial bandits (Balasubramanian
hhttpe://github wwt/
ine iaw.aaaannn--neeeeeeneee----- to- Rank- Stochastichciceeeee fank--fr-Sttccastiie
Mlick-Madeel.
2

---

Published in Transactions on Machine Learning Research (09/2024)
et al., 2023). These works share a similar attack idea, where the attacker holds the reward of the target arm, meanwhile lowers the reward of the non-target arm. Besides reward poisoning attacks, other threat models such as action poisoning attacks (Liu and Lai, 2020a; 2021) were also being studied.
Recently, Zuo et al. (2023) studied adversarial attacks on OLTR. The paper considered an eosier attack goal: ensuring that the target item appears on the displayed length-K ranking list R, for T o(T) times, without regard for the specific position of the target item. They introduced two click poisoning attack algorithms specifically designed for CascadeUCB and PBMUCB. These algorithms rely the knowledge of the target rankers and the underlying click model (i.e., Cascade model and position- position-based model). Additionally, they proposed a general attack algorithm based on click poisoning, operating under the assumption that the attacker is aware of the feasible feedback space of the victim's click model (refer to the last paragraph of page of Zuo et al. (2023) for details). The authors acknowledged that 'without this knowledge, ensuring valid post-attack feedback becomes impossible." Moreover, we illustrate through Example that click poisoning attacks are poorly adapted to different click models. This discussion highlights the ineffectiveness of their attack algorithms (wwo single-target altack algorithms and a general attack algorithm) when information about the underlying click model is absent.
In this paper, we focus on fooling the victim ranker into placing the target item at the top of the list R2 for T - o(T) times. To overcome the strong assumption that the attakker knows the underlying click model, we propose the list poisoning-base based GA algorithm, which achieves our attack objective without relying on any knowledge of the underlying click model. We also introduce a new click poisoning- attack strategy named ATQ to boost the target item the top of the list. This strategy leverages the phase elimination property of general rankers like TopRank and BatchRank. We observe that these algorithms tend to 'assume' the most attractive item is the best during certain exploratory phases, consistently placing it at the top. Consequently, our ATQ aims to fool TopRank and BatchRank into believing that the target item possesses the highest attractiveness within a short period.
3 Preliminaries
3.1 Online Learning to Rank
We denote the total item set with L items as D {ai, (a,,,.,,r))) Let [xx C DK stands for all K- tuples with different elements from D. At each round t, the ranker would present length- K ordered list R, = axx) E (D) to the user, where a is the item placed at the k-th position of RR Generally, K is a constant much smaller than L. When the user observes the provided list, he/she returns click feedback C. - -Ci ( to the ranker where C₁ = stands for user click on item a₁ Note that a & R2 can not be observed by the user, thus its click feedback in round is C = O. The attractiveness score represents the probability that the user is interested in item ag, and is defined as a(a)) [0, 1], which is unknown to the ranker. Without loss of generality, we suppose a(ai) >,... > a(ar.) where an is the most attractive item and az is the least attractive item.
3.2 Stochastic Click Models
In this paper, we consider the general stochastic click models studied by Zoghi et al. (2017); Lattimore et al. (2018), where the conditional probability that the user clicks on position in round t is only related to R. This implies there exists an unknown function that satisfies
P(C, 1 R. R, af. =a.) vRR, at k):
(1)
where R = R2 denote the list presented in round t, and a, = of denote that the s-th most attractive item (where a₂ can be any arbitrary item in D) is placed in the k-th position of R, (also the k-th position of R). The key problem of OLTR is to present the optimal list R = (d1,..,,ap to the user for per-round click number maximization. The optimal list is unique due to the attractiveness of items is unique.
3

---

Published in Transactions on Machine Learning Research (09/2024)
Assumption 1. Since the user does not observe items in position R2, we assume that the ranker con achieve marinam expected namber of clicks in round I. if and only if RR R², i.e.
K
maX (D)
(R, a
Σ
(R al. k).
(2)
Definition 1 (Cumulative regret). The performance of ranker be evaluated by the cunvulative regret, defined as
R(T) = E uRR' k) - u(R,, aj. k))
1=1
Nole that if Assumplion 1 holds, R can uniquely mazimize E v v(Ri, a ki), and every Rr & RR leads to non-zero regret.
We present two classic click models (Chuklin et al., 2015; Richardson et al., 2007; Craswell et al., 2008) that are special instances of the stochastic click models.
Position-based model. The position-based model (Richardson et al., 2007) assumes the examination probability of the k-th position in list R₂ constant x(k) E [0, 1]. In each round, the user receives the ordered list R2, He/she would examine position & with probability x(k). position k is examined then the user would click item a with probability a(at). Hence, the probability of item af is clicked by the user is
v v(R, alg - x(k)a((a)).
Note that the examination probability of items not in R2 is Hence, the expected number of clicks round is
K
K
Σ
o (R,, a k:) = (x()))(aa).
(4)
k=1
The examination probabilities of the first K positions are assumed to follow x(1) > > x(K) (Chuklin et al., 2015). The maximum number of clicks in each round is K.
Cascade model. In the cascade model (Craswell et al., 2008), the user examines the items in R2 sequentially from af. The user continues examining items until they find an item af, attractive or they reach the end of the list. If the user finds at attractive, they would click on it and stop examining further.
According to the above description, the examination probability of position k equals the probability of none of the items in the first h positions in R₁ can attract the user, and can be represented as
k-1 a1-
X(R,, k)
The maximum number of clicks is at most 1, and the expected number of clicks in each round can be written as
K
K (R,, at, k) Σ (Ri,, =1 II o(a))) k=1
Σ
(6)
Similar to the position-basee model, x(Re,1))>. 1)> X(R,, K) is hold in the cascade model.
Definition (No-regret ranker). We define the no-regret ranker as a ranker that achieves a sublinear (o(T)) regret in its click model under Assumption By Definition 1, we can see that ranker is no-regret if and only if it presents RD to the user for T o(T) times.
4

---

Published in Transactions on Machine Learning Research (09/2024)
ranker
ranker
C
R₂
R₁
attacker
attacker
Ce
Ce
R
useT
user
(a) Click poisoning attack.
(b) List poisoning attack.
Figure 1:
Threat models on online learning to rank.
Remark 1. We now briefly discuss relationship between click models and no-regrel runkers. Recall the definition of the position-bused model, the optimal list R uniquely marimize (4). Thus, every ranker that achieves regret R(T) = =TT) in the position-based model falls into the category of no-regret ranker (such as PBM-UCB (Lagrée and Vernade, 2016)). Besides, algorilums (i.e., BatchRonk and TopRank) for general click models (Zoghi et al., 2017; Lattimore et al., 2018) present the optimal list R for T ((T) times owing their elimination and divide-and conturr nature. Therefore, they can achieve a sublinear regret under Assumption and state-of tfate-of-the-art the-art online ranking methods BatchRank (Zoghi et al., 2017) and TopRank (Taltimore et al., 2018) fall into the calegory of no-regret rankers. However, every permodation of the first K K-most attractive items can mazimize Eq equation 6 in the cascade model. The item with the highest allractiveness may not be placed at the first position for T o(T)) limes by un online slochastic runker with R(T) = =(T).. Thus not all rankers that achieve R(T) = o()) in the cascade model are no-regret rankers.
3.3 Threat Models
Let (ox))= (ai = } denote the total rounds item an placed at the first position of R., until time T. The adversary aims to fool the ranker to place a target item à at the first position of Rr for T - oTT) rounds. We consider two poisoning attack models.
Click poisoning attacks. We illustrate click poisoning attacks in Figure 1(a). This similar to the reward poisoning attacks studied on multi-armed bandits (Jun et al., 2018; Liu and Shroff, 2019). In each round, the attacker obtains the user's feedback C, and modifies it to perturbed clicks C. (C) ..., Ct). Naturally, the attacker needs to attain its attack goal with minimum attack cost defined as C(T) ΣI Σl 12 C.--
List poisoning attack. Instead of directly manipulating the click feedback, the list poisoning attacks manipulate the presented ranking list from R2 to R2 illustrated in Figure 1(b). This is similar to the action poisoning atlack proposed by Liu and Lai (2020a; 2021) against. multi-armed bandits. We assume the attacker can access items with low attractiveness denoted as {nk]2K- 22K-1 D and for convenience, a<n) >,..., > a1) The low attractiveness items satisfy a(n) < a(rr). We suppose the attacker does not know the actual attractiveness of these items, but only their relative utilitics, i.c., the attractiveness of items K-1 is larger than items in {mH 12K-1 The attacker uploads these items the candidate action )
set before exploration and we denote D = D U {me 1 -2K-1 In each round, the attacker can replace items in original ranking R, with items in {T 1 2K
]=] This modified list R₂ = (āf....āff is then sent to the user. The cost. of the atlack is C(T) = Σt_ Ek 1 ( A a Note that the click feedback C, in list poisoning attacks is generated by R₂ instead of R., but the ranker assumes that the feedback for R.-
The click poisoning attack has been studied in WSJ (2018); BuzzFeed (2019); Golrezaei et al. (2021). In practice, the click feedback manipulation can be executed through malware installed as a browser extension, which manipulates the elick feedback signal locally before uploading it to the server (e.g., the OLTR algorithm). We also provide an example to explain the practicability of the list poisoning attack.
Example (Motivated example of list poisoning attack). Consider the OLTR of an e-commerce search engine (e.g., Amazon) where the attacker is a seller who wants to promote its target item (e.g., good) to the top (WSJ, 2018; BuzzFeed, 2019). The ilem set of the e-commerce consists of items uploaded by sellers.
5

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm Generalized List Poisoning Attack (GA)
Inputs: List T (ā, m, .... []-1) and {nH ]= -
1 to the candidate action set 2: Upload [m
for = 1: do
Observe R2 = (af
-. ak)
if R. ( * then
6:
for k- = 1: K do
7:
if a & T then
8:
Set a = 1]
9:
else
10:
Set a a
11:
Return R2 (äf..... ak) to the user
12: else
13:
Do not allack
The attacker can find 2K - items with low attractiveness (e.g., unpopular aduertisements low-qualitty products) and derive their relative utilities (the relative utilities of n between E [1. - 1] and i [K, (K,2K- based on offtine learning to rank techniques. Due to low-attractiveness items being much more common in weal-world applications compared to attractive ones and being much smaller than the total item number L, we believe finding 2K lou-attractiveness items is applicable. As a seller, the attacker could uploud both low- atttaattactie items and the target item to the item set (e.g., a seller listing products on the Amazon platform). Additionally, list manipulation can be executed through malware installed as a browser extension, which locally allers the ranking list on the web page. When the e-commerce platform interacts with the user, the attacker can implement list poisoning attack strategy using the uploaded items and the malware.
We define the efficient attack strategies as follows.
Definition 3 (Efficient attack). We say an attack strategy is efficient if
1. It misguides an online stochastic ranker to place the target item à at the first position of Rr for T - oT) times in expectation with cost C(T)= o(T).
2. To keep the click poisoning allack slealthy, the relurned tolal clicks Eks C% in the cascade model is at most 1 and in the position-buse baatid model is at most K.
We conclude the preliminary with the difference between poisoning attacks on stochastic bandits (Jun et al., 2018; Liu and Shroff, 2019; Xu el al., 2021) and online learning rankers. Data poisoning altack on stochastic bandits aims to fool the bandit algorithm to pull the target arm T o(T) times with o(T) cost. The main idea of this class of attack strategics is to hold the expected reward of the target item and reduce the expected reward of the non-target items. However, in the OLTR setting, 1) the ranker would interact with length K list R2 instead of a single arm; 2) the user would generate click feedback under different click models that depend on ezamination probability. Recall from the definition click models, that in the position-based model the user would return at most K clicks in one round, while the cascade model, the user would return at most click. Thus, if the attacker returns more than one click in the cascade model, its attack is unstealthy and inefficient.
4 Generalized List Poisoning Attack Strategy
In this section, we would propose generalized list poisoning attack (GA) that misguides any no-regret ranker to place the target item the first position of R, for T oTT) times in expectation with o(T) cost.
against no-regret rankers. We briefly illustrate the process of GA. The strategy is summarized in A Algorithm 1. The attacker first needs to design list. T, where T (ā, m, m dK- 9--1)- Intuitively, items

---

Published in Transactions on Machine Learning Research (09/2024)
71.... 7K - are utilized to fill in the rest of the positions when ā is in R2. The attacker would not manipulate item ai E 'T. If items a) E D/T are placed in the position k, the attacker would replace it with + (lines 5-9 in Algorithm 1). This manipulation strategy can mislead the ranker to believe the attractiveness of items in D/T are smaller equal than a(πk). Hence, list T would be doemed as the optimal list and is the item with the highest attractiveness. According to the definition of the no-regrel, no-regret algorithms will present T for T- (T) times and the attacker can achieve its attack goal. Theorem demonstrates that GA can efficiently attack any no-regret ranker.
Theorem 1. GA can efficiently attack any no-regret ranker, i.e., E[Nr((a) 2 T- --R(T)/ min and C(T) S /R((T)/mii, where R(TT) - TE K I ifdo not attack, Ek (Ro, kb.,b)3) is the regret upper bound of the victim algorithm, A Amin = (i ( af R) - -E "RR af, k)) > 0 and A consists of T and L ++R K attractiveness smaller equals then a(πk).
(T, k) k) - -i atttakk Σ (e,, al kt} +
- items with
Remark 2. According to the Algorithm 1, R(T) con represent the regrel of the victim algorithom when it explores an environment that consists of an optimal list T and L + K-1 items with attractiveness smaller equal than a(πk). According to the definition of the no-regrel, the victim algorithm will present T for T (T)) times and achieve a sublinear regret, which implies R(T) = =TT). Accondingly, we have E[Nr(a)] = T - o(T) and C(T) = o(T), which satisfies the definition of the efficient attack.
Remark 3 (Gap dependency). If the regret upper bound of the victim ranker satisfies R((T) =
OLL (oL()))) min) for ezample Kveton et al. (2015a), then GA has E[Nr(a)] = T -LLL log(T)) /A min) and C(T) O(2 (oLL) Amn)) This is similar to the torget arm triggered rate and attack cost of the action poisoning attack on MAB in Liu and Lai (2020b).
Remark 4. We note that Zoghi et al. (2017); Lattimore et al. (2018) suppose the position based model satisfies x(1) 2 x(2) 2,..., (K). This is because they are primarily concerned with achieving sublinear regrets rather than the specific position of an item in list R4 Similarly, Zuo et al. (2023) also disregard the position of the target item in R2, as their setting assumes the ā E Rt is an efficient attack. We make this assumption on the fact that if x(1 = x(2), both (a1, a2 as....,gg) ..) and (a2, a1 os...., can achieve zero regret in the posilion-base basedd model. This contradicls the assumplion of our slochastic click model, which slates that only R- = (a1,ag a2, a3....aak] can achieve zero regret. More specifically, if x(1) = x(2), then an algorithm con present (a2, a1 o3...., for oo) to achieve o(T) regret, and GA can not achieve its attack goal due to à has the highest attractiveness and it will be placed on the second position. Besides, it's important note that we can alleviate the assumption to x(1) > x(2) 2 .... 2 x(K) and our GA can also achieve its otlack goal in the position- based model. This is becouse we only focus the position of the target item and disregard the positions of non- con-attractive items {Tk real-world scenarios, it is impossible for this phenomenon to occur, as users inherently exhibit bisses towards distinct positions.
Im K-1
Furthermore, suppose x(k) > x(k)) is highly plausible because in
Although we do not include all rankers with o(T)) regret in the cascade model as no-regret rankers from Remark 1, we can still show that cascade ranking algorithms such as CascadeUCB1 (Kveton et al., 2015a) can be efficiently attacked by Algorithm 1.
Theorem 2. Consider the ranker applies UCBt and is attacked by Algorithm 1. The expected number of à be placed at the first position till round T satisfies E[]r(āa] TT =T-o(T) and the cost is C(T) = o(T). Remark 5. We notice that most existing cascade runkers for OLTR problems are UCB-based algorithmms CCscadeUUBII, CascadeKL UCB (Kveton et al., 2015a), and Cascade UCBV (Vial et al., 2022)). Hence, we believe GA can efficiently attack these algorithms and we can analyze the theorefical results similar to Theorem 2. We have also provided empérical results in our experiment section and Appendir that GA con efficienlly atlack CascadeUCB1,, CascadeKT.UGR and the SOTA algorithm CasondeUCB-V
After the above observation, one may wonder why we don't utilize click poisoning strategy achieve the same goal of GA, we here propose motivated example.
Example 2 (Limitation of click poisoning attack). Suppose the environment includes an item set A = (a1,a2, 02, 0g) with attracliveness a(a1) > a(22) > a(az) and as is the larget item. Besides, we suppose the
7

---

Published in Transactions on Machine Learning Research (09/2024)
length of ranking list K 2 and the attacker knows the preference between the items. The attacker reduces the click feedback of aı to O when a1 E Ri, otherwise, does not atlack. When allacking posilion- OLTR algorithm, the effectiveness of the attack can be deemed as the attacker reducing the attractiveness of a1 to o and holding the attractiveness of a2 and ag. Note that keeping the true attractiveness of target item ag unchanged is the key idea to achieve sublinear allack cosl.
However, the above analysis for the position bosttion-bused model connot be applied to the Cascade model. Different from the PBM, the click probability of an item in the Cascade model is not only related to this item' 's attractiveness but also related to other items' attractiveness. Suppose item a1 is placed at the first position of RRt and item 02 is placed at the second position. If the user clicks and returns the click feedbock (the click feedback of ai is 1 and the click Seedback of a2 is 0), this implies 02 has not been examined by the user and the ranker does not update 02 's attractiveness estimate. When the attacker reduces the click feedback of a1 from to O, we can not simply deem the attacker reducing the attractiveness of 01 to O and holding the aftractiveness of ag- This is becouse the clicks of two items in the Cascade model are Os means the user ezamines all items and does not click either of them. Hence, the clicks will be interpreted by the viclim algorithm as the attractiveness of a1 and a2 is 0, violating the idea that the attacker should keep true attractiveness of target item for sublinear cost.
The above example shows that the simple click poisoning strategy cannot adapt to different click models, and its theoretical results need to be analyzed differently based on the click model's characteristies. However, GA perturbs the ranking list presented to the user and pretends the click feedback represents the user's interests in the original ranking list. The effectiveness of this strategy can be viewed as the attractiveness of items in the original list is replaced by the attractiveness of items in the perturbed list. This guarantees the click feedback always follows the unknown click model, making the attack casy to analyze and stealthy.
5 Attack-Then-Quit Strategy
In this section, we provide a click poisoning attack strategy that applied to rankers on general click models. We will demonstrate our strategy can efficiently attack some rankers under any click models. Previous reward poisoning altack strategies on multi-armed bandits only manipulate the reward of the non-target item and never perturb the reward of the target item (Jun et al., 2018; Liu and Shroff, 2019; Garcelon et al., 2020; Wang et al., 2022). However, the attack strategy proposed in this section perturbs the click foedback of every item. The at attacker would spend linear cost. in short period Tj o(T) and then stop the allack and quit. Thus, we call our attack strategy the attack-then-uuit (ATQ) strategy. As mentioned in the previous section, the BatchRank and TopRank can work in general stochastic click models, while other UCB-type algorithms can only work in specific click models (c.g.. CascadeUCB1 or PBM-UCB). Hence, the BatchRank and TopRank can be deemed as the superior ranker to those UCB-type algorithms, which are worth more significant consideration.
5.1 Click Kasooing-Basedl ATQ
Algorithm 2 can efficiently attack elimination-based rankers (e-g. BatchRank) and divide-and-cooqqer--aedd rankers (e.g., TopRank). At the initialization stage, the attacker would receive target item ā and threshold Ti. In each round, if click feedback Cj is returned from â and ā E R2, the attacker would set č% 1, otherwise, C₁ = 0. Besides, as we mention in Assumption 1 and Definition 1, the item dg E R2 would not be observed by the user in round f, and would not be clicked either. This implies their click feedback would be 0. In ATQ, the attacker does not (cannot) modify the click feedback of items ag & R2 (line 9~~10 in Algorithm 2). After scanning C,, the attacker would return C. (Ct...,Cy), CL) to the ranker. Note that Σt= C% < 1 (line 4-10 in Algorithm 2), hence Algorithm 2 can work stcalthily and efficiently in different click models. Note that the divide-and-conquer and elimination nature ensures BatchRank and TopRank to quickly estimate the attractiveness of items and rank them accordingly. Our attack Algorithm 2 aims to mislead these rankers to 'believe' the target item the best item with the smallest rounds. Once these rankers make this judgment, they would place the target item at the first position until T. In the following sections, we will demonstrate A Algorithm 2 can efficiently attack BatchRank and TopRank with suitable Ti.
8

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm Sataac-Thhen-Oee (ATQ) Algorithm
1: Inputs: The target item a threshold T₃
2: for / 1: Ti do
Observe C. = (Ci, "ii...,,, Ct) and R, (a), ..., a
for k = 1 L do
if aĄ â and ag R, then
6:
Set C% =1
7:
else if a + ä and E R₂ then
8:
Set c =
9:
else
Set čt C₁
10:
11:
Return C. (Ci, (C Ci. to the ranker
Ba = [az)
Bi [Og Gg Ago]
Bas (1greon
T
T
Figure 2: Process of the Algorithm 2 attacks BatchRand
5.2 Attack on BatchRank
Brief Explanation of BatchRank. The BatchRank falls into the category of elimination-based algorithms (Zoghi et al., 2017). The BatchRank would begin with stage L,, every item would be explored for ny, = 164,, log(T") times and Â = 2 2-, Afterward, BatchRank collects enough information to confirm the attractiveness of every item in group larger than the others, BatchRank then splits the initial batch into two sub-batches B2 and Ba Items that are considered with higher attractiveness (i.e., in sub-batch B2,22) would be always placed before items with lower attractiveness (i.e,, in sub-batch B3,6,) The BatchRank would restart with stage & and la and sub-batches B2 and Bs Batches would recursively split until round T. Intuitively, the action 'split' of BatchRank is similar to the elimination action in the elimination-based bandit algorithms (Even-Dar et al., 2006; Lykouris et al., 2018; Bogunovic et al., 2021). The details of BatchRank are provided in the Appendix.
and the first batch B1,6 In stage
Algorithm can successfully attack BatchRank owing to BatchRank's elimination property. Algorithm 2 maximizes the returned clicks of the target item and minimizes the returned elick of the non-target item in short period o(T). After this period, BatchRank regards the target item owning the highest attractiveness (i.e., split). Then the larget item would be always placed at the first position of the list R, and the al aacker achieves the attack goal. We also provide Example to further illustrate the process of Algorithm 2 attack BatchRank.
Example 3. Consider the item set D = (2,, a2.,a,,...aa anu3 contains 10 items. The target item is â = 01 with arbilrury allractiveness and ilem list R, contains 3 positions. The BatchRank begins with BI, D and recursively explores items. The attacker begins the attack at round and ends at Tú. During Ti rounds, the attacker returns Ō₁ = if à 0g and E R,; otherwise C%2 0. This fraudulent strategy misleads BatchRank to believe the attractiveness of the non-target items a + and the attractiveness of is 1. A After BatchRank finishes the split section, the batch BA,s, split into B2 {a1} and Ba,t, (10)
9

---

Published in Transactions on Machine Learning Research (09/2024)
G = P Ps 9gia))
G2 = ((2 (a).
Przz (4)
a1
Pr,s = (xz]
a2
(2
a1
ag
d3
T
Figure 3: Process of the Algorithm 2 attacks TopRank.
Sub-batch B2,6, contains position (f.e., a and Ba,t, contains position 2 and 3 (i.c., a and an). The process is illustrated in Figure 2. The largel ilem à would always be placed at the first posilion of the Rr in the next T - Ti rounds due to B2,2, only contains à. The attack cost would be o(T) because the attacker only manipulates the click feedback for o(T) rounds.
Theorem 3 (Attack against. BatchRank). Consider the attacker aims to allack BatchRank with stochastic click models (Zoghi et al., 2017). If the attacker runs Algorithm with Ti = 16L log()) we have (r 2 T - Ti and the cost con be bounded by C(T) S KTT.
Besides BatchRank, this attack idea can also be utilized to attack some rankers that do not belong to the iiadiaatio-bassee category, such as TopRank.
5.3 Attack on TopRank
Brief Explanation of TopRank. TopRank is a divile-annd-connuerr-aaeeld ranker (Lattimore et al., 2018). It begins with a blank graph G = 0. In round 1, TopRank would establish blocks P.i, Ped via graph G.. The items in block Pa would be placed at the first |Pal positions and the items in block P:2 would be placed at the next (Pezl positions, and so on. During rounds 1 to T, TopRank would explore items with blocks, collect click information and compare attractiveness between items in the same block. If the collected evidence is enough to let TopRank regards the attractiveness of item a; as larger than the attractiveness of item aj, a directional edge (aj, a;) would be established. This behavior is similar to the 'split' action in BatchRank. Besides, graph G. would not contain cycles with high probability. If the graph contains at least one cycle, we consider TopRank would be out of control. Details of TopRank are provided in the appendix.
Note that if there exist edges from every non-target item to the target item and G, contains no cycle, then the target item would be isolated from the non-target items and would always be placed at the first position of RR, This is because the first block only contains the target item. We also provide Example 4 to specifically explain how Algorithm 2 attacks TopRank.
Example 4. The process of the attack is shown in Figure 3. Consider the total item set D = fai, a2, aa} with 3 items. The length of the list R2 is K = 2 and the target item is à = 01. The TopRank would start with block P and d= 1 because the graph contains no edges at the beginning. In the first T2 rounds, the attacker receives click feedbbck C, and modifies click feedback C+ = if ag = à and ag E Re, otherwise Ct = O. After Tr, the edges @a),a), k= 2,3 are established simultaneously. In the last T Ti rounds, the block Pi would only contain à and à would always be placed at the first position of RR- Due to TopRank would only compare items' attractiveness in the same block, the edges from à to ag + à would never be established and cycle would appear in Gt with very low probabilily (will be exylained in the proof of Theorem 4 in the appendiz).
Theorem 4 (Attack against TopRank). Consider the allacker aims to allack TopRank and TopRank runs in the click model in (Lattimore et al., 2018). If the attacker sets Ti =
$ +111- (-S0-/++ and runs Algorithom 2. The attacker can achieve (a) 2 T Ta with probability at least (1/c+ L2)5. The cost can be bounded by C(T) & KTi
1log(e65)
10

---

Published in Transactions on Machine Learning Research (09/2024)
Tec
Total Cost
le5
Targe: Arm Trigger Rate
1ed
Total Cost
Target Arm Trigger Rate
2.5
1.0
1.0
Sute --
Tarkee oo
Toekea on
1.5
0.6
TEMUCE- CA
0.6
PERUCIIGA
0.5
0.2
0.2
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
3.0
0.0
0.2
0.4
0.5
0.8
1.0
Eanations
105
Rarations
165
Ilerations
le5
Beeraions
165
(a) Cost in CM.
(b) Na(ā) in CM.
(c) Cost in PBM.
(d) Ne(a) in PBM.
Figure Synthetic data experiment: (a) total cost spend in the cascade model, (b) (ā) in the cascade model, (c) the total cost. spend in the cascade model and (d) Nz(ā) in the position-based model. We report. averaged result and variance of 10 runs.
By choosing = 1/T and c= 4/2/T/ erl = 3.43 which is same as in TopRank algorithm, we have Ti = O((L/K) log T). Besides, readers should note that - 6T.2 is the intrinsic probability of TopRank's Gt, Vt E [T] contains cycles.
and Theorem 4 is gap-independenut). The reason the cost upper bound of the ATQ isn't gap-dependent is due to 1) the approach taken during the attack, and 2) the structure of the Rank and Rapk The RopRank and BatchRank algorithms are classified as phose elimination algorithms. the proofs of Theorems and 4, we demonstrate that we can achieve the attack objective by mazimize the click feedback of the largel ilem and minimúze the click feedback of the non-torgel ilems during the first elimination phase (see ATQ pseudo code). Through analysis, we determine that the length of the first elimination phase for BatchRank and TopRank is respectivcly bounded by (L and ( log(T)) (this also implies that ATQ can compromise TopRank Juster than BatchRank due to Batch 's inferior performance compored to Ropkank.), which is unrelated to the allractiveness gop. Besides, due to Top and BatchRank will randomly explore the whole item set in the first phase, we suppose the attack cost per round is K due to the attacker should modify at most K click feedback in each round. Accordingly, the finial cost. upper bound do not depends to the altructiveness gaps.
Remark 6 (Why Theorem 3
Remark 7 (Comparison of ATQ performance with that of attack algorithms in the bandit domain). Although we haven't provided an instance-dependent version of cost upper bound, we notice that when the victim algorithm is BatchRank and TopRank, the ATQ can achieve E[Nr(ā] = T log((T with C(T) = O log(T)). This can match the performance of click poisoning attack on MAB (Theorem and Theorem of Jun et al. (2018)), i.e., ([) = O(L and C(T) log((T))
Remark 8 (Why UCB-based algorithms can not be altacked by ATQ?). The effect of ATQ relies on algorithmss' phosed elimination property. However, CascadeUCB and PBM- UCB belong to UCB- (Cs-b algorithms. When the attacker stops, the true click feedback of other items will be revealed the algorithms over time, leading JCB-based algorithms to realize the targeted item isn't the item with the highest attractiveness.
6 Experiments
In the experiment section, apply the proposed attack methods against the OLTR algorithms listed in Table 1 with their corresponding click models. We compare the effectiveness of attack synthetic data and real-world MovieLens dataset. For all our experiments, we use I, = 50, K = 5 (the set up of Zoghi et al. (2017); Lattimore et al. (2018) is L = 10 and K = 5) and T = 10a. For ATQ, we set the Ti in Algorithm 2 by Theorem 3 and Theorem 4.
6.1 Synthetic Data
First, we verify the effectiveness of our proposed attack strategies on synthetic data. We generate a size- L item set D, in which each item 4₃ is related to a unique attractiveness score a(a)). Each attractiveness score a((a) is drawn from uniform distribution U 1). We randomly select a suboptimal target item à. Figure shows the results and variances of 10 runs.
11

---

Published in Transactions on Machine Learning Research (09/2024)
Te5
Total Cost
1e5
Targe: Arm Trigger Rate
Total Cost
Target Arm Trigger Rate
1.0
1.0
2.0 TechhaaauAo
1.00
Farkee oo
Toekea on
kptce
Ncto a
1.5
0.6
0.75
FAMUEDIGA
0.6
PERUCDIGA
0.5
0.2
0.2
0.0
0.0
0.00
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.25
0.50
0.75
1.00
0.0
0.2
0.4
0.6
0.8
1.0
Ranations
105
Rarations
105
lerations
le5
Berations
165
(a) Cust in CM.
(b) [a(@) in CM.
(c) Cost in PBM.
(d) Ne(a) in PBM.
Figure 5: MovicLens experiment: (a) the total cost spend in the cascade model, (b) (ā) in the cascade
model, (c) the total cost. spend in the cascade model and (d) Na(a) in the position-based model. We report. averaged result and variance of 10 runs.
Table 1: Target ranking algorithms and their applied click models
Algorithm
Click model
BatchRank (Zoghi et al., 2017)
Stochastic click model
TopRank (Lattimore et al., 2018)
Stochastic click model
PBM-UCB (Lagrée and Vernade, 2016)
dastion--base model
CascadeUCB1 (Kveton et al., 2015a)
Cascade model
CascadeKLUCB (Kveton et al., 2015a)
Cascade model
In Figures 4(a) and 4(b), we plot the results of the GA against CascadeUCBI, CascadeKLUCB, BatchRank, and TopRank, and the ATQ against RatchRank and TopRank in the cascade model. Both attack strategies can efficiently misguide the rankers to place the target item at the first position for T o(T) times as shown in Figure 4(b), and the cost of the attack is sublincar as shown in Figure 4(a). The GA is cost-cfficient when allacking all four algorithms. We can observe that when it allacks TopRank and BatchRank, the cost would not increase after some periods (similar to the ATQ's results). This is when the TopRank and BatchRank believe the target item and the auxiliary items have a relatively higher attractiveness than the other items, they would only put the target item and the auxiliary items in R2 Besides, when attacking TopRank and BatchRank, the growth rate of GA's target arm pulls N²(ā) slowly increased from 0.2 per iteration to per iteration. This because the GA does not manipulate the items in T and the TopRank and BatchRank need time to confirm the target item has higher attractiveness than {m k- Hence, the smaller the gap between à and 7/, the larger the confirmed time. Compare with the GA, the ATQ also efficiently attack BatchRank and TopRank with sublinear cost. However, its (r) is almost T, which is relatively larger than GA'S (ā). This is because the ATQ is specifically designed for solied-annd-conuu----beeee like TopRank and BatchRank. The ATQ can maximize the target item's click number and misguide these algorithms to believe the target item is the best in the shortest period.
algorithms
Figures 4(c) and 4(d) report the results in the position-based model. We can observe that the spending cost of the GA on the PBM-UCB is slightly larger than the spending cost on the CascadeKL UCB and CascadeUCBL. Besides, although the GA can let the TopRank believe the target item is the best item in almost 500 iterations, it still needs a large number of iterations (around 6 x 10 iterations) to make the BatchRank make such a decision. From the results of the two models, the ATQ is obviously more effective than the GA when the target algorithms are TopRank and BatchRank.
6.2 Experiments on Real-World Data
We also evaluate the proposed attacks on MovicLens datasct (Harper and Konstan, 2016). We first split the datasel into train and test data subsets. Using the training data, we compute a d-rank SVD approximation, which is used to compute a mapping from movie rating to the probability that a user selected at random would rate the movie with 3 stars or above. We use the learned probability to simulate user's clicks given the ranking list. We refer the reader to the Appendix of (Vial et al., 2022) for further details. Figure 5 shows the attack results of attack strategy averaged over 10 rounds.
12

---

Published in Transactions on Machine Learning Research (09/2024)
We can observe that the trends in Figure 5 are similar to those in Figure 4, and the two attack algorithms are again able to efficiently fool the OLTR algorithms. In the cascade model, we see that successfully attacking CascadeKLUCB, TopRank, and BatchRank with GA only needs a relatively low cost, and the cost is higher when the target is CasCadeUCBI. Besides, the ATQ strategy can still outperform the GA in Nr (ā) when the target algorit his are TopRank and BatchRank. In the position-based model, the results are similar to the results the cascade model, and the cost spent the PBM-UCB is larger than the cost spent in the other algorithms.
7 Conclusion
In this paper, we study adversarial attacks online learning to rank. Different from the poisoning attacks studied in the multi-armed bandits setting where reward or action is manipulated, the attacker manipulates binary click feedback instead of reward and item list instead of a single action in our model. In addition, due to the interference of the click models, it difficult for the attacker to preciscly control the ranker behavior under different unknown click models with simple click manipulation. Based on this insight, we developed the that can efficiently attack any no-regret ranking algorithm. Moreover, we also proposed the ATQ that follows the click poisoning idea, which can efficiently attack BatchRank and TopRank. Finally, we presented experimental results based synthetic data and real-world data that validated the cost-efficient and effectivenese of our attack strategies.
References
Qingyao Ai, Tao Yang, Huazheng Wang, and Jiaxin Mao. Unbiased learning to rank: Online or offline? ACM Transactions on Information Systems (TOIS), 39(2):1-29, 2021.
Peter Auer, Nicolo Cesa- Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem.
Machine learning, (7(23))2335-256 2002.
Rishab Balasubramanian, Jiawei Li, Prasad Tadepalli, Huazheng Wang, Qingyun Wu, and Haoyu Zhao. Adversarial attacks on combinatorial multi-armed bandits. ArXio, abs/2310.05308, 2023. URL https:
//api. semanticscholar org/ ID 263830044.
Iija Bogunovic, Arpan Losalka, Andreas Krauso, and Jonathan Scarlett. Stochastic lincar bandits robust adversarial atlacks. In Internalional Conference on Artificial Intelligence and Slabistics, pages PMLR, 2021.
BuzzFeed. Some amazon sellers are paying 10,000 a month trick their way to the top. 2019.
Alcksandr Chuklin, Ilya Markov, and M. de Rijke. Click models for web search. In Click Models for Web Search, 2015.
Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. An experimental comparison of click position-bias models. In Web Search and Data Mining, 2008
Eyal Even-Dar, Shic Mannor, and Y. Mansour. Action climination and stopping conditions for the multi-armod bandit and reinforcement learning problems. J. Mach. Learn. Res., 7:1079 1105, 2006.
Evrard Garcelon, Baptiste Roziere, Laurent Mcunier, Jean Tarbouricch, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks on linear contextual bandits. Advances in Neural Information Processing Systems, 33, 2020.
Aurélien Garivier and Olivier Cappé. The kl-ucb algorithm for bounded stochastic bandits and beyond. In Annual Conference Computational Learning Theory, 2011.
Camille-Sovanneary Gauthier, R. Gaudel, and Élisa Fromont. Unirank: Unimodal bandit algorithms for online ranking. ArXiu, abs/2200.001155, 2022.
Negin Golrezaci, Vahideh Manshadi, Jon Schneider, and Shreyas Sekar. Learning product rankings robust fake users. Proceedings of the 22nd ACM Conference Economics and Computation, 2021.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Artem Grotov and Maarten de Rijke. Online learning to rank for information retrieval: Sigir 2016 tutorial. In Proceedings of the 39th International ACM SIGTR conference on Research and Development in Information Retrieval, pages 1215 1218. ACM, 2016.
E. Han and Jonathan Scarlett. Adversarial attacks on gaussian process bandits. ArXiv, abs 2bss/210008849, 2021. semantcsscoolar
URL haappp/sapp...eaannccccchhha...r arrgCorrussDD-.. 239016505.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5:19:1-19:19, 2016.
Yiling Jia, Huazheng Wang, Stephen Guo, and Hongning Wang. Pairrank: Online pairwise learning rank by divide-and-oonquer. In Proceedings of the Web Conference 2021, pages 146 157, 2021.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks stochastic bandits. In 2018.
Advances in Neural Information Processing Systems, pages
Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Dem bandits: Learning to rank with multiple clicks. In International Conference on Machine Learning, pages 1215-1224 2016.
Branislav Kvelon, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. International Conference on Machine Learning, 2015a.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. NIPS, 2015b.
Paul Lagrée and Claire Vernade. Multiple-play bandits in the position- basod model. In NIPS, 2016.
Tor Lattimore, Branislav Kveton, Shuai Li, and Csaba Szepesvari. Toprank: A practical algorithm for online stochastic ranking. In NeurIPS, 2018.
Chang Li, Branislav Kveton, Tor Lattimore, Iya Markov, M. de Rijke, Csaba Szepesvari, and Masrour Zoghi. Bubblerank: Safe online learning to re-rank via implicit click feedback. In Conference on Uncerlainly in Artificial Intelligence, 2018.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International Conference on Machine Learning, pages 1253,, 2016.
Shuai Li, Tor Lattimore, and Csaba Szepesvari. Online learning to rank with features. ArXiv, abs abss/810.00550) 2019.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. Tn International Conference on Machine Learning, pages 4042 4050, 2019.
Guanlin Liu and Lifeng Lai. Action-manipulatian attacks on stochastie bandits. ICASSP 2020 2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 3112-3116, 2020a.
Guanlin Liu and Lifeng Lai. Action- manipulation attacks stochastic bandits. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3112-3116. IEEE, 2020b.
Guanlin Liu and Lifeng Lai. Efficient. action poisoning allacks on linear contextual bandits. abs/2112.05367, 2021.
ArXic,
Tie- Yan Liu et al. Learning to rank for information retrieval. Foundations and Trends3 in Information Retrieval, 333)2225-33,, 2009.
Weiwen Liu, Shuai Li, and Shengyu Zhang. Contextual dependent click bandit algorithm for web recommen- dation. In International Compuling and Combinatorics Conference, 2018.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Shiyin Lu, Guanghui Wang, and Lijun Zhang. Stochastic graphical bandits with adversarial corruptions. In A AAAT Conference on Arlificial Intellignnce, 2021. URL atttps://app htttps:/app..ematttcchhoool.. org/ CorpusID:: 235349145.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 114-122. ACM, 2018.
Yuzhe Ma and Zhijin Zhou. Adversarial attacks on adversarial bandits. ArXin, abs/2301.125000 2023. URL https://api.. www.ntaa.ccoaa.....ommm.amaa.... httpaaaiiiaccaaaaoooooooopppooee Cwrg/CorpusDD.... 256389660.
Harrie Oosterhuis and Maarten de Rijke. Differentiable unbiased online learning to rank. Proceedings of the 27th ACM International Conference on Information and Knowledge Management CIKM '18, 2018. doi: 0244445/2269226.2233
URL http://dx: doi. org/10. 1et.111151/32605 /t/.///622....2666666.. 3271686.
Achref Ouni, Eric Royer, Thierry Chateau, Marc Chevaldonné, and Michel Dhome. Deep learning for robust information retrieval system. In International Conference on Computational Collective Intelligence, 2022.
Filip Radlinski, Madhu Kurup, and Thorsten Joachims. How does clickthrough data reflect retricval quality? In CIKM '08, 2008.
Matthew Richardson, Ewa Dominowska, and Robert J. Ragno. Predicting clicks: estimating the click- thck-hh rale for new ads. In The Web Conference, 2007.
Aleksandrs Slivkins, Filip Radlinski, and Sreenivas Gollapudi. Ranked bandits in metric spaces: learning diverse rankings over large document collections. J. Mach. Learn. Res., 14:399-436, 2013.
Hua Sun and Syed Ali Jafar. The capacity of robust private information retrieval with colluding databases. IEEE Transactions Information Theory, 64:2361-2370 2016.
Daniel Vial, S. Sanghavi, Sanjay Shakkottai, and Rayadurgam Srikant. Minimax regret for cascading bandits. ArXiv, abs/2203. 12577, 2022.
Huazheng Wang, Ramsey Langley, Sonwoo Kim, Eric MeCord-Snook, and Hongning Wang. Efficientt exploration of gradient space for online learning to rank. In The 41st International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 145-154. ACM, 2018.
Huazheng Wang, Sonwoo Kim, Eric McCord-Snook, Qingyun WU, and Hongning Wang. Variance reduction in gradient exploration for online learning to rank. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 835 345-844, 2019.
Huazheng Wang, Haifeng Xu, and Hongning Wang. When are linear stochastic bandits attackable? In PMLR, 2022.
International Conference on Machine Learning, pages
WSJ. How sellers trick amazon to boost sales. 2018.
Ying Xu, Bhuvesh Kumar, and Jacob D. Abernethy. Observation-free attacks on stochastic bandits. In NewrIPS, 2021.
Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Online learning to rank in stochastic click modcls. In International Conference on Machine Learning, pages 4199 4208, 2017.
Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for large-scale recommendation problems. ArXiv, abs//160.00359, 2016.
Jinhang Zuo, Zhiyao Zhang, Zhiyong Wang, Shuai Li, Mohammad Hassan Hajiesmaili, and Adam Wierman.
Adversarial attacks on online learning to rank with click foodback. ArXiv, abs/2305.17071, 2023. URL
https://api... semanticacholars h
258944139.
Shiliang Zuo. Near optimal adversarial attack on ueb bandits. ArXiv, abs/2008.09312 2020. URL https:
//api. semantccscoolllrr wwwoollarrrrroo/ooeeo tttp/CorppsDD::2246000.
15

---

Published in Transactions on Machine Learning Research (09/2024)
A
Notations
For clarity, we collect the frequently used notations in this paper.
D
Total item set
R
K-length item list be shown to the user in round t Optimal list
R
R2
Manipulated list in round t
C₁
Click feedback list in round & Manipulated click feedback list in round Ordered list (ă, "i........00 ax)
C₂
T
Target item
a
k-th most attractive item in D k-th most attractive auxiliary item Particular item in the list poisoning attack Attractiveness of item dg Item on the k-th position in R2 Manipulated item on the k-th position in R. Click foedback of item ag in round Manipulated click feedback of the item ag in round Click probability of item the k-th position in round Cumulative regret in T rounds Total cost in T rounds Number of item aş be placed at the first position in t rounds Number of item be examined in t rounds Total number of interaction Input threshold value of the attack thenckk-hen-quit algorithm
a
Th
(ax)
a
a
C
(R2,, ag,
R(T)
C(T)
Ni(ax)
M((a)
T
Ti
BatchRank
b
Batch index Stage index
e
Bo.
b-th batch explored in stage Exploration number of item in batch Br, in stage l Total received click number of item ag during stage l Attractiveness estimator of item aş in stage é Upper confidence bound of item ag in stage & Lower confidence bound of item Os in stage
me
Co,e(a))
Co,((a))
Us.(aax)
In,((a))
TopRank
G
Auxiliary graph in round
(ay.a) a4)
Directional edge from item aj to item o; c-th block in round t.
Pie
Suj
Sum of the Uny from round 1 to
Nuj
Sum of the absolute value of Uuy from round 1 to t
16

---

Published in Transactions on Machine Learning Research (09/2024)
4.0
Total Cost
165
Target Arm Trigger Rate
CaccadeUCBS-track
CascadeUC AS-aduuCBS-Attack
1.75
3.0
1.50
2.5
1.25
1.00
1.0
0.50
0.5
0.25
0.0
0.00
0.50
1.00
1.25
1.50
0.00
0.25
1.00
1.25
1.50
Iterations
Iterations
1e5
(a) CCs Cost
(b) CascadeUCBV, Triggered number
Figure 6: Experimental results of GA attacks CascadeUCBV. We report the average results and variance of 10 rounds.
B Additional Experiments
In the main text, we have shown that GA can efficiently attack CascadeUCB1 and CascadeKLUCB, In this subsection, we show that GA can also efficiently attack the SOTA cascade ranker CascadeUCBV (Vial et al., 2022). The attack results are provided in Figure 6. Apparently, the GA can successfully reach the attack goal. Based on these results, we believe GA can efficiently attack almost every existing UCB-type cascade ranker.
C Proof of Theorem 1
Recall that when the attacker implements Algorithm 1, the optimal list becomes R T (ā, 71 7KK -1) due the attractiveness of items belong D is smaller than aл)-11) (i.c., a(л)) < a(T S aā)). We should also notice that the target item has the highest attractiveness. Now recall
T
T E
(aN
Σ 1(a = a}
Σ (a + aa))
(7)
then based on Definition and Assumption 1, we know that if a o ā. the ranker would suffer from regret in round l. Due to the per step regret is al least Amin (i) v(T a(, Σ v(R, k)) 0, where A consists of T and L + K - items with attractiveness smaller equals then a(nx). Then based on finally derive
the definition of regret,
R(T) Amin
[[N ST
(8)
where R(T)
E E UT, a k)
Σt (Ifattack,
EK a
kf
+
11 do not atlack, Ek RR,, af, k)) })]
is the regret upper bound of the victim ranker.
Besides, according to the line 4 of the Algorithm 1, the cost of Algorithm
be bounded by
K
faf D(TT] < KE Σ 1 # 00
C(T)
Due to the optimal list becomes T during the attack, if R.AT + 0, the per step regret is al least Amin- Thus, the cost can be bounded by
KŘ(T)
C(T) < KE
IRRAT 10]
(10)
A Amia
t=1
17

---

Published in Transactions on Machine Learning Research (09/2024)
Therefore, if the target ranker present the best list T for T - o(T) times in its click model under Assumption (the definition of the no-regret ranker), then R(T) o()) (GA would not attack the victim ranker when it presents T), [[Nr(ā)] = ' - o(") and the cost of Algorithm 1 would be sublinear. According to Definition 3 and our deduction, we can conclude that if ranker belongs to no-regret rankers, can be efficiently altcked by Algorithm Here fiuish the proof of Theorem
D Proof of Theorem 2
D.1 Introduction CascadeUCB1
The pscudo-code of the CascadeUCB1 is provided as follows.
Algorithm CascadeUCBI (Kveton et al., 2015a)
Input: Ttem set D
for = L do
Explore item aş and derive C2
4: Set (o = and (ax) Cg
5: for 1: do
for k = 1:
Compute (CB)((x))
Let aq.....a al be K items with largest UCBs and set R. (af. ....... akk Observe click feedback C.
10:
for k = 1: K do
11:
if a is clicked then
12:
Set s k
13:
for & = 1: do
14:
Set N(aa)) = Mi (as)
15:
for k = 1:8 do
16:
Set N((a(t (( +1
(a )a 1 (x=A)
17:
(N((
We let Na(ax) denotes the number of item ag be examined till round t. The upper confidence bound is defined as (a = (x)=1(a))( + 3/(oo(( - 1))/AN(
D.2 Proof of Theorem 2
The proof of Theorem 2 relies the following lemmas.
Lemma 1 (The Hoeffding inequality). Let X1, X2, ..., X, i.d. drawn from Bernoulli distribution, X 1 + X; and [[ be the mean, then
< -a) S -na211
(11)
Lemma Consider item a₁ is the item with the highest attractiveness and 02 + a₁. When the principal runs the CascodeUCB1, the expected number of az be placed at the first position till round T can be bounded by [(N)(a))) + 81 //2 where A a((a)) a(ax).
18

---

Published in Transactions on Machine Learning Research (09/2024)
Proof of Lemma 2. We first decompose ([N) as follows
T
81 log (T)
}
81 log(T)
E[Nr((a) 21+ + E
1
aj = ak, Nz-1(ax) <
+ E
1 aj = ag. Ni-1(ax) 2
]
4
A
1=1
81 log(T)
81 log(()
1 +
E
aj ok: Ne-1(ax) 2
4
4
11
81 log(T)
Σ
T
p
(CB((a)) 2 UCB((a1), Na=1(ax) 2
81 ITg
4
k
(12)
By union bound, we then decompose and bound probability P(UCB((a)) 2 UCB)(a)), No-1(as) A
81 log(T)/43)
P PUCB((ON) (ADD)UCCHEE UCB((a)), N+-1(ax)= 2
81 log(T)
k
ΣΣ P(UCB((U)) 2 UCB.(()) 2UCB(()) Ne-1(as) Nc =a, (a11 >)
(13)
A=1 02 (e
The inequality holds due to Na-1(ax) 2 Na-1(ax). We further upper bound P(UCBB((N)) 2
(L a, N--((an) A). Consider for S X s t-1 and 81 log(T)/A3 a st-1, we have
P UCBi(as) (L- N2-1(a1)= =>)
log(T)
D+ > (xi=)(a))(ai) +3
log(T)
No Na = a, Na-((a)= 2)
<P (Nv= 31/ N(-1(a4)
N, N,-1(a1)
(N)=)la)(aH)+ 24x 2 (Ni- + 3 (ai)
log(T)
No. Ne-1(ax) =, Ni-1(a1) 21) =2)
<P
A + + + ((a)) (a))
log(T)
No =0, N2-1(ai) 2). (14)
<P âv.. ((v a(ai) - a(ax) 2
((1)(a))
The first inequality relies on the definition of the (az) The second inequality holds because o 2 81 log(T)/A3. The third inequality holds because A = a(a1) - a(ax).
Based on the Hoeffding inequality, we have for any and 2 81 (o))
log(T)
P a((1)) ((1)(())) /
(1-1(a1)=
N1-1((11)
T9/2
(15)
P (( a(ax) >
4 N =0)
1
T9/2 -
3
19

---

Published in Transactions on Machine Learning Research (09/2024)
The last term of (14) can be further bounded by
P
(or + a(a1) - a(ax)) 2
Ak
+ (() + N111((1)) N)-1(a)) = o, Ni-1(a1) = =
log(T)
3
SP
d (()))) - a(ax)= 2
A
N (ax) =0) + +P(((()) ( / (a1) (1-1(a1)= =
log(T)
1
$ T9/2
T9/2
7
(16)
The first incquality holds due to the union bound and the last inoquality holds due to (15).
With the fact that
ΣΣ
Σ
S 2. T
2
S
2 T
(17)
the light of (17), the total expected number of ag been placed the first position can be bounded by
81 log(T))
E| B[Nr(an)) 33+
(18)
A
Here finish the proof of Lemma
Proof of Theorem 2. With Lemma 2, we can bound the total expected number of as # a being placed the first position till round T. Thus, from round to round T, the expected number of CascadeUCBI place item an at the first position satisfies
81 log(T)
Nr(ai) T
Σ
3
(19)
A
Remember when the attacker implements attack Algorithm 1, the target item would become the item with the highest attractiveness. The rest of the items consist of [ and L + K - items with attractiveness at most a(1x). Therefore, when Algorithm 1 attacks the CascadeUCBI, (r(()) can be lower bounded by
3 + 81 log(T)
L+K-1 Σ
3 + 81 log(T") (a<(a) {2
[[Nr(a) T Σ
(20)
(a(ā) aT1))
Besides, according the line 4 of Algorithm the cost of Algorithm 1 attack CascadeUCBI can be bounded by
C(T) S KE Σ (RR + 0)
(21)
It is worth noting that Algorithm only manipulates items in list R,, hence the cost generates in one round is at most K. Recall the definition of regret in the cascade model
K
T
K
R(T) = (T a
k)
d RR, k))
km
(22)
K
K a
E
T 1 - (1))(a))
II
(1 alāx))
Σ t=1
1
[a-
k=1
20

---

Published in Transactions on Machine Learning Research (09/2024)
The total regret is generated by K positions. Algorithm 1 only attacks when R * 0. And situation RA * 0 implies there is at least one item & T be placed in the Rx and its attractiveness is reduced to at most a(π)). Due to when R * 0, the number of items is placed in R₂ and belongs to D)T is at least 1. Then for the cascade model, the regret generates in round is at least
K
0 (T, a k) o(Re, k:)
k=
K-1
K-2
21 (1 a(ā))
- (1--d
II (1 a(T))) k=1
(23)
k=1
K-2
=(a(n)
a(ā))
II (1- (1-)))))) k=1
The first inequality holds due to a(īk-1) has the lowest attractiveness With the above derivation, we can derive when R2 RAT + 0, the regrel generates in each round is at least (a(()) (((x))()-x(((((()))) - (1-())))) With this mind, we can further bound the total cost by
C(T) S KE Σ I(RAT + #0] S (a(m) (( ))(()) a(ā)) [ a(n)))
KR(T)
(24)
Due to the regret of the CascadeUCBI satisfies R(T) = o(T), the cost of Algorithm would be sublinear. We conclude that the CascadeUCB1 can be efficiently attacked by Algorithm 1. Here finish the proof Theorem 2.
E Proof of Theorem 3
E.1 Introduction of BatchRank
We here specifically illustrate details of BatchRank. The pseudo-code of the BatchRank is provided as follows.
Algorithm 4 BatchRank (Zoghi et al., 2017)
1: Initialize: bmax 1, I = (1) = 1, (2) = K), l = 0. BI, = D, {1)
2: for 1-=1 1: do
for f= 0: do
for all d% D do
Ca.e(ax)= 0, (a))(an) =
6: for 1=1:7 do
7: for all 6 e B do
8: DisplayBatch(t.bb) for all b E do Collect for all b E do (pdateBatccht.b)
10:
11:
12:
The BatchRank explores items with batches, which are indexed by The BatchRank would begin with stage
8 0, batch index b = 1, and the first batch Ba,r, D. The first position batch b is indexed by (1) and the last position is indexed by (2), and the number of positions in batch b is len(b) I((1) - (2) + 1. The first batch B, contains all the positions in R,- In stage &,, every item in Ba would be explored for n2 16Â,," log(T') times (DisplayBatch) and A 2 2-4, Afterward, the BatchRank would estimate the attractiveness of item ag as
Co.((a)) Co.e(ax)/mu
(25)
21

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm DisplayBatch
1: Input: batch index b, time
2: Set = 4
Let 01,..., Bls.dl be a random permutation of items in B&, such that ns,e(01)
S ... S (n,e(a
Let E (o)) ([ee(()]) be random permutation of position assignments
5: for h == [=1) (2) do
a (a(()Ic(1)++)
Algorithm CollectClicks
1: Input: batch index b, time
2: Set = l and Mimn = min (s,e(az)
BbE.
3: Receive the click feedback C, = Ct)
4: for A = [,(1 (2) do
if (a))(a))) Mmii then
6: Set (afe = (afe(at) + Ele Ca = =at} and (as)(aa)) = no.e(af)) +
Algorithm UpdateBatch
Input: batch index b, time Sct E=4
3: minareBu, no.e(ak)= ny
4: for all aj E Bb,e do
5: Compute Ub,e(as) and Lo,e(as)
Let a1...., a Bo.l be any permutation of B, such that Lo,e(an) 2 ... 2 Lo.e(a)noa))
for & = 1 len(b) do
8: Set B+ = {a,,.., )x} and B Br,
for k = 1: len(b)- - do
10:
if LL.((x)) max BEB Us.((ax) then
11:
Set = k
12:
if 0 and [Bo.el len(b) then
13:
Set B,,41 = {az E Ba,e : Us,e(ax) 2 Lb.e Ltte((ten(t))) and t= f= ++)
14:
else if s > 0 then
15:
Set (1max + 1, bmax + 2))(,,, B +1,0 = B+, B -2, = B5, bbmaxt1 =
16:
4 +2 = 0, Imma+11 = (1), (1)) + s 1), 1 = (Is(1) + s, Io))), bmax bmax +
22

---

Published in Transactions on Machine Learning Research (09/2024)
After the CollectClicks section, the ranker would compute the KL-upper confidence bound and lower confidence bound (Garivier and Cappé, 2011; Zoghi et al., 2017) for every item in the batch, denote as Ub,e(az) and (ax)
Ub,e(ax)= = arg max {n (n.DkL(Cuc(aw)))) < log(T)) + log log(T)}
(ax)))
(26)
Lo,e(ax)= arg min (n.DkI(Co, < log(T) + 3og log(
re(0,Cs,e(n:))
where DEz represents the Kullacc--Teibler divergence between Bernoulli random variables with means p and g. In the UpdateBatch section, all the items in batch Bo., would be placed by order a1, B, where Lo,e, (a1) 2,... 2 Lo.e, (a) The BatchRank would compare the first ten(b) - item's lower confidence bound to the maximal upper confidence bound in B If Lb,e, (ak) max Ub,4, (ax), the BatchRank would set = k. Ones 8 > 0, the batch would spilt from position s and the ranker derives butche Bb+1,& and 2 Sub-batch Bu+1,& contains items and the first s positions in R₂ and sub-batch 2 contains L- s items and positions from 8 to K. The BatchRank would restarl with stages l2 and la 0 and mub-batches B and B The batches would recursively run and split until round T.
E.2 Proof of Theorem 3
The proof of Theorem 3 relies the following Lemma. 3.
Lemma 3. The attacker utilizes Algorithm to manipulate the returned click feedback of the BatchRonk. After 16T log(T) rounds allack and the BatchRank begins ils first split. The upper confidence bound and lower confidence bound of every non-target item satisfies Lo,e, (ax) - and Ub,e,ass lower confidence bound and the upper confidence bound of the target item are Lo,t, (ā) and Un, (ā) 1.
log(T))) - -1/n6, The
Proof of Lemma 3. According to the introduction of BatchRank, the estimated click probability of an arbitrary
item is written as (25) and Co.e, (ax) is at most 16 log(()) in the first stage (Ei = 0 and Á = 2 1). Recall our attack Algorithm returns Cj = when d * â and ag E RR. Thus, the total collected click number of the non-target item is Co,e, (ax) = O, and the estimated click probability is Cr,e, (ax) = 0.
We first introduce the definition of the KT.-divergence
DKL(P)l9) = p log( () (1 p) log( -
(27)
q
By convenience, we define (lg((0) = 0 log(0/0) = and x log(x/0) = +o0 for x > 0 (Garivier and Cappé, 2011). With this knowledge, we can derive the upper confidence bound of the non-target item in stage 4
Ub,e, (ax)
arg {nc, DKL (Co,e, (ax)lla) s log(T) (og) geldn,,, (aw).1)
arg mnx log 0 rE(o.1) arg max (na, log
llg
log(T)) log log log(
(28)
q
1
S log(T) + 3og log(
qE[U.1]
-
Apparently, when q 4=1 1, log(() + log log & ne, 1og(1/11 - 9) = +00, hence should smaller than 1. When ni, log(11((1 - 4)) = loggTT) + log log( we have
ntg log(
) = log(T ())
= log (Tlog(T))))ume)
log(
(29)
1
(Tlog(T))))/1H,,
1 9
q 1 - (I 1 1/n6,
23

---

Published in Transactions on Machine Learning Research (09/2024)
Due to T log(T)) > 1 and nég > O, can derive 0 (Tlog(T)3))1/MM) < and 0 < (a,((aa)) < 1.
The lower confidence bound of the non- non-target item has
Lo,e, (a+) = arg mingm,, DKLCo (ax))l) S log(T) + 3 log log( = 0.
(30)
nE(0.0)
Remember the attacker returns C% = if an = ā and as E R, Thus, the total collected click number of target item is Co (ā) l6l) and Co (ā) 1. We can further deduce the upper confidence bound of the target item
Ub (ā) = arg (ng, D (KI (g) I log(T) + 3 (o)(()) = 1.
(31)
qE[1.1]
The lower confidence bound of the target item has
Lb,t, (a) = arg min ne, (xz(Cr,e & log(T) + +3 loggog((T)) vE(0.1]
1 + (1 - log ) s log(T) + 3og log(T))
arg min n2, (1 qE[0._]
9
(32)
1
arg min (ne, log- q rE[0.1]
< log( ) + loglog(())
= 1.
Here finish the proof of Lemma 3.
Proof of Theorem 3. Consider the attacker implements attack Algorithm with Tj = log(T. With the knowledge of Lemma we obtain when the BatchRank begins to split the first batch B1, =D, the lower confidence bound of every non-target item satisfies Lo,e, (ax) 0, and the lower confidence bound of the target item satisfies La.e, (ā) 1. Therefore à would be ranked at the first position because it has the highest lower confidence bound (line 6 in UpdateBatch). The BatchRank starts comparing Ls.e, (ax) and max ER Ub,e, (ax) for 1 = 1 to K 1 (line 10 in UpdateBatch). Owing to Lt,e, (ā) = 1 > Us,e, (ax) and Lo,e,(ax) Ub,e, (ag), the split point would derive two sub-batches B2,, {ā} and B3,g, a' Sub-batch B2,6, contains the first position of R2 (i.e., a and B3,, contains the rest of the positions of R. (i.e., a..)..,af)). alc). until round T because it only contains a position and an item. This implies after round 16L log(T"), the target item would always be placed at the first position of R, until round T' is over, i.e., Nr(@) 2 T - 16L log(T). Due to the click number in each round being at most K, the cost in one round is at most K. Hence, the cost. of Algorithm 2 can be bounded by C(T) KT,.
1 (line 11 Updatebatch). After the split action, the BatchRank
Sub-batch B2,,, would not split
Based on the above results, we conclude that Algorithm can efficiently attack BatchRank when Ti 16L log()). Here finish the proof of Theorem 3.
F Proof of Theorem 4
F.1 Introduction of TopRank
We here specifically illustrate details of the TopRank. The pseudo-code of the TopRank is provided.
The TopRank would begin with a blank graph G. S [z]2. A directional edge (aj, a:) E G. denotes the TopRank believes item at's attractiveness is larger than item aj. Let ming, D Pic) {a, e DV 1 (a;, ag) g G, for all a₂ E D U The algorithm would begin from round 1 to round T. In each round, the TopRank would establish blocks P.i,..., Pes via the graph G.. Items in block Pn would be placed randomly at the first |Pall positions in R,, and items Pta would be placod randomly at the next (Pizl positions, and so on. In each round, after deriving click feedback C, the TopRank would compute Unj C -CJ if item o; and item ay are in the same block, otherwise, Ung 0. Afterward, the TopRank would
24

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm The TopRank (Lattimore et al., 2018)
4v//T
1: Input: Graph G = 0, round number T, c=
erf(v2) 2 3.43
for = 1: do
Set d =
while D DU- Pee # 0 do
5: Set d= 1+1
Set. Pid ming, (DIU Ptc)
7:
Choose R2 uniformly at random from P1i, Pid
8:
Observe click feedback C. = .C.......)
for (i.j) [2] do
10:
if Oz, aj Pia for some d then
11:
Set Uns- = C. CCJ
12:
else
13:
Set Uni = 0 Uti and Nus- = =E.=1 U2ay
Set Stk Σ.=
14:
Set G.+1 = Ge U a:) Swi 2 v 2Nrrs log( / and Nus > 0}
15:
compute Suj= = E'=1 Uny and Nuy = |Uayl and establish edge (a,,a) a.) if Suz 2 2N log( (ay) and Nuj > 0. Without the attacker interference, the graph would contain any cycle with probability least 1 - 8L2, if the graph contains at least one cycle the TopRank would behave randomly (Lattimore et al., 2018). Parameter 5 would be set as 8 = 1/T.
F.2 Proof of Theorem
The proof of Theorem 4 relies on the following lemmas.
Lemma 4. Consider the TopRank is under the attack of Algorithm 2. Denotes a, = à as the target item and aj # à as non-target items. When Σ 1fa R2} 4 llg(c/0), then ST, 2 2/2N,, Log(E /NT,is) and NT. > are salisfied and edges from non-larget ilems to largel ilem (i.e., (u), aj # az) are established simultaneously.
Proof of Lemma 4. Note that the TopRank sets Uni = C Cj if a; aj E Pia for some d, otherwise, Uni = 0. According attack Algorithm 2, the TopRank would receive C 1 (C, generates by the target item) if R2 and Cj (C} is generated by non-target items) when t t Ti. Based on this, we can derive
= - 1, t à R2, a, E Pid.
(33)
Thus, when P. = (D), we have
Suy =
Σ
Uni = Naj =
Σ Unl = Σ faa Rc), 1ST.
(34)
1=1
==1
In the light of (34) and
line
15
TopRank, if
El 1fa
E R₂}
2
2 E. lfā E R.} log(E / E' 1 R.)), edges (aj, a;) would establish. Utilizing the knowledge of the
25

---

Published in Transactions on Machine Learning Research (09/2024)
elementary algebra, we have
Σ 1 laā E log (s 6
Σ e R1}2
Σ iāā E Ril)
Σ
2 22 Σ l
log(f) + log
(v
Eua Rel) ((aERR))
s=1
s=1
s=1
(35)
if E Re) R1)- -log
Σ lfā E Rob) 2 log g)
2
Σ i(a Ra) 2 4 1oog( ()
The second inequality holds because of Σ l( R₂) > 0. The fourth inequality holds because of (1/4)æ > (o)(yā) when x O. Thus, when Σ 1 E R.} 2 4log(c/0) and S Ti, edges (aj a;) would establish simultaneously. We here finish the proof of Lemma 4.
Lemma 5. Suppose input Ti ++1 VI-VV1/8///// then with probobility at least - 8/c, the TopRank would
4 log(e/6)
achicve Et1 1(ā E R.} > llog(//)).
Proof of Lemma 5. According to the previons discussion, we can separate Ti into two periods P1 and Pa (i.e., Ti P + P2). In period one G, and in period two G, only contains edges from non-target items to the target item. Based on the TopRank property, in period one P(a E R,lt S P1) K/L and in period two P(a E R2 Pi +1 S 1 Ti) 1. Define Bernoulli distribution X that satisfies X 1 with probability K/L. With the help of the Hoeffding inequality, can derive
P
X₂
T -oTh sc-Tie222
(36)
1=1
Set Ti
4 (c/8)/8))
and a = -(1 v I 8K/L)/4 We can derive
E +(1 -118//44//))/
T
P
X, S log(c/))
S
(37)
Further derivation shows that
Ti
8
P
Σ
X. 1+>4logfo llo((e/0)
(38)
Follows the definition of the TopRank, one has
T. Σ laa E R2) 4log(c/6))
Pr
Σ (a E R,}+ +
= P
Σ
fia E R2 + Ps > 4log(c/6)
t=
(39)
2 P Σ 4logce/0)
where the first equation holds because Σ 1fā E R₂} = Po.
The last inequality holds because
P₂ 2 E Xt. Combining (38) and (39), we can finally get
> 1 5 c
P
1fā R1) 4log(c/0)
(40)
1=1
26

---

Published in Transactions on Machine Learning Research (09/2024)
when Ti
+ (0-11-114///)// Here finish the proof of Lemma 5.
4 5
Lemma 6. If the attacker implements attack Algorithm and Ti
E -111-11-8////4 the graph G, would
4log(c/6)
not contain any cycle with probability at least - (L2 + 1/c)o.
Proof of Lemma 6. We here analyze our attack Algorithm 2 would not case G, contains any cycle with high probability if the imput T1 = 1+41-/++8//00
Consider the attacker implementing our attack strategy from round 1 to round Ti. Define 0; à and aj * â. The attacker frauds the TopRank to believe the target item à is clicked Σn 1āa J times and non-target items are clicked time in Tí. After Suj 2 2N log( B Naa) and Nuy > 0 are satisfied, the edges would be established at the same time and à would belong to the first block (line in the TopRank and Lemma and 6). Note that during T₁, the attacker sets C₁ 0. Thus
log(o/5)
T 1ez/ =
T1 Σ -11
T Σ li R.}
NT,
t=1
(=1
[=1
(41)
STi Σ
Unjs
Σ -C) = Σ 1 fā e R
Since Unj and Uej would be 0 after t t> Ti (line 9-13 in TopRank), we can obtain Sr, = - Σ Ifa e R.} and Nr,5 = Σ 1sa e R2} hold when Tí. This implies the directional edges from the target item to non-
target items would never establish, ie., - 1(ā E R1 < < 1fā Re) log(3 ΣT 1fā Re))). Besides, due to the received click number from non-target items being 0 in Ti, the Sr, and Nr, between non-target items would be 0. This implies the manipulation of the attacker would not influence the TopRank judgment of the attractiveness between non-target items. In other words, the TopRank under Algorithm 2 attack can be considered as the TopRank interacts with item set D in T - T1 rounds.
According to the above discussion and Lemma 5, if Ti = $ ++01V145K/D)/4 then Srijj >
4log(c/6)
V ir log(E l (TT would satisfy with probability at least 1 - 8/c. Besides, from round Ti + 1 to T, cycles would occur with probability at most S Thus graph G2 would not contain cycles with probability at least 1 (1, + 1/c)ō until T.
Proof of Theorem 4. Suppose the allacker implements attack Algorithm with input value Ti Then, the TopRank would establish edges from non-target items to â with proba- $ E+(11/144K//D) bility least 1 1-8/c 8/c (According to Lemma and Lemma 5). Based on the analysis in Lemma 6, the cycle would appear with probability at most. (T,2 + 1/cjō and the first block would only contain till T. That is to say, the target item in block Pa would always be placed at the first positions after Ti with probability at least 1 1- (L2 (L2+1) 1/c)6. Following Algorithm 2, the attacker would only manipulate the returned click feedback for Ti times. Thus the attack cost can be bounded by C(T) < KTi.
4log(e/8)
According to the above observation, we summarize that Algorithm 2 can efficiently attack TopRank when 4log(c/6)
Ti (- 8K//1/44 Here finish the proof of Theorem 4.
27


Reviews:
[{"review_id": "LBRB0yK5IS", "reviewer": "Reviewer_yCyz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe introduction of the attacks into the OLTR scenario is interesting.\n\nWeakness:\n\nThe main issues of this paper are (1) the unclear description of the motivation, and (2) imprecise math notations and language.\n\nFor the motivation, while proposing the attacks into OLTR is interesting, besides deepen the understanding on the vulnerability and the sensitivity of OLTR methods, the authors need to provide more concrete description on why they consider these two specific attacks, and why it is essential to consider these attacks. For list poisoning attack, although Example 1 tries to provide a real scenario of the attack, it is not clear that how the attacker is able to insert the attack between the communication of the buyer and the website. The last sentence \"When the e-commerce platform interacts with the user, the attacker can implement based on its uploaded items\" needs more details. For click poisoning attack, the authors also need to suggest one practical scenario on how the attacker is able to conduct the attack.\n\nFor the writing, there are numerous imprecise math notations and grammar which impacts the quality of the paper. For math notations, while the list in the appendix is clear, the description in the main paper is not clear. For example, in equation (1), why we use $a_s$ rather than $a_k$ in the formula? Why $v(\\mathcal{R},\\textbb{a}_k^t,k)$ rather than $v(\\mathcal{R},a_s,k)$? Also, on the line below equation (1), the $a_1,\\ldots,a_L$ in $\\mathcal{R}^*$ seems to represents a different thing compared to how they are introduced in the paragraph above equation (1). \n\nIn terms of the grammar issues, the first sentence of Assumption 1 has grammar (change \"due to\" to \"since\" or \"because\"). Remark 1 \"correlation\" should be \"relationship\" (correlation is a term with some specific math definition). Paragraph \"List poisoning attack\", the sentence \"We suppose the attacker does not need to know the actual...\" is incorrect in its logic: Please replace \"does not need to know\" with \"does not know\". The last sentence of Example 1, there should be a noun following the word \"implement\".", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies two possible attack scenarios in online learning to rank (OLTR): click poisoning attacks and list poisoning attacks. Their derivation demonstrates that the existing OLTR methods are very vulnerable to these attacks: the attacks can efficiently mislead the OLTR method to pick the target unwanted item as a top ranked item.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the issues mentioned in the weakness section.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2MOCkLWSF9", "reviewer": "Reviewer_UXbV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- A decently realistic model, though stylized.\n- The algorithms are simple and it is obviously they could be easily implemented. It seems that costs are “realistic” (i.e. one doesn’t have to completely corrupt the entire signal for the ranker).\n- Formal proofs of manipulability for popular LTR models.\n- There is a clear connection to the types of online LTR models used in the literature. And one should definitely expect attackers to try to manipulate LTR models in the real world.\n\nWeaknesses:\n- As with many adversarial attack papers, it is sort of “obvious” that having strong power to steer rewards or tamper with actions could allow one to steer an algorithm’s behavior to bad places, if it is not designed to defend against this. That said, simplicity and lack of novelty don’t make these results bad or uninteresting — it is good that they have been worked out, and in particular that the costs faced by the attacker trying to run such an attack are clearly understood here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies adversarial attacks in a setting of “online learning to rank”.\n\nBase problem:\n\nThe goal of the ranker in this problem is to present an ordered tuple of some larger set of items to a user to maximize the probability that the user clicks. Their problem setting is fairly general: they only make the assumption that click probability at each round is independent of previous rounds. They consider an online setting where the ranker presents a new ranking at each round, gradually improving over time. To achieve the standard goal of sublinear regret (aka be a no-regret algorithm), in this particular setting, the algorithm must output the unique optimal ranking sufficiently often (i.e. T - o(T) steps). This property winds up being important for making the adversarial attack work.\n\nAttack model:\n\nThe authors then consider attackers who want to manipulate such a no-regret algorithm.\n\nThey present two reasonable models of what an attacker can do — click poisoning attacks (motivated by the realistic problem of click fraud) and list poisoning attacks (motivated by an example where an entity could create a lot of fake items to manipulate outcomes). While stylized these seem relatively reasonable and convincing (the click model more so). Applying both of these attacks imposes a cost per round they have to be done.\n\nThe goal of the attacker is to mislead the no-regret algorithm into ranking some chosen item first, while making sure their own cost grows sublinearly.\n\nConcrete attacks:\n\n- Generalized attack under list poisoning model: the authors present an attack that can work for any no-regret ranker, by essentially deceiving it into thinking that a given list is the top, and so getting it to output that list many times.\n- Attack-then-quit strategy: this is a strategy for the click poisoning attacker model, which can be shown to work on two popular ranking strategies (BatchRank and TopRank).\n\nThe authors run experiments showing these attacks work, both on synthetic data (similar setup to previous literature) and the popular MovieLens dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have no requested changes -- the submission seems adequate as is.", "broader_impact_concerns": "Although the topic of better adversarial attack strategies is one that might seem troubling from a broader impact perspective, this paper is mainly theoretically focused, so describing the algorithms and releasing code is likely not dangerous.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CCStJodQXf", "reviewer": "Reviewer_AunX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written. The stuided problem is very interesting. Though I didn't check all proofs, the theoretical results seems sound and reasonable. \n\nWeakness:\n\n1. My main concern is that the paper does not provide detailed comparison between the proposed methods and the concurrent work (Zuo et al. 2023). Since (Zuo et al. 2023) has been published in NeurIPS 2023 (whose audience highly overlaps with TMLR's audience), the authors need to show that some individuals will be still interested in the findings of this paper even if they have read (Zuo et al. 2023). Specifically, I think the paper needs to answer following questions:\n\n- What's the main technical challenge of fooling the ranker to place the target item on top of the list instead of just in the list?  \n- Notice that (Zuo et al. 2023) studied click poisoning attacks against most popular OLTR methods. However, ATQ seems not suitable for attacking PBM-UCB and CascadeUCB. What is the main challenge of extending ATQ to attack PBM-UCB and CascadeUCB?\n- Notice that BatchRank (Zoghi et al., 2017) and Toprank (Lattimore et al., 2018) only require $\\chi(1)\\ge\\dots\\ge\\chi(K)$, while this paper assumes $\\chi(1)>\\dots>\\chi(K)$. What is the limiting factor of studying the case where two positions have the same examination probability? Actually, methods in (Zuo et al. 2023) can handle this case.\n\n2. ATQ requires to know the time horizon T, which is hard to obtain in real-world applications.\n3. I'm surpurising that the theoretical results of ATQ are gap-independent. Could authors give some explanation for such results?\n4. Why ATQ requires $O(KL\\log(T))$ cost to attack against BatchRank, but only requires $O(L\\log(T))$ cost to attack against TopRank?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies poisoning attacks against online learning to rank (OLTR) . The paper proposes GA and ATQ algorithms for list poisoning attack and click poisoning attack, respectively. The authors verify the effectiveness both theoretically and empirically.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The authors should discuss the relationship between this paper and the concurrent work (Zuo et al. 2023) in the introduction.\n2. The paper may provide more discussions on the points mentioned in the \"Weakness\".", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers originally raised concerns about not enough coverage of the related work, about clarity and notation, but these were all well addressed in the rebuttal and the revision, and they all recommended acceptance.
Decision: Accept (poster)