Observation-Free Attacks on Online Learning to Rank
Sameep Chattopadhyay, Nikhil Karamchandani, Sharayu Moharir · 2025
Read Observation-Free Attacks on Online Learning to Rank by Sameep Chattopadhyay, Nikhil Karamchandani, Sharayu Moharir (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-22855.txt.
Introduction
Sameep Chattopadhyay, Nikhil Karamchandani, and Sharayu Moharir attack online ranking systems without ever observing their output. Online learning to rank powers search engines and recommenders, which learn from clicks as they serve. Its vulnerability to coordinated attacks was poorly understood. Their framework promotes a set of target items into the top-K list for almost all rounds. At the same time, it forces the learner to suffer regret that grows linearly with time.
Two strategies serve two classic algorithms, CascadeUCB1 and PBM-UCB. Theory shows each needs only a logarithmic number of manipulations to succeed. Experiments on real-world data back the analysis. The observation-free design makes the attacks stealthy: the attacker never needs to see the rankings.
Catalog record
| CREATOR | Sameep Chattopadhyay, Nikhil Karamchandani, Sharayu Moharir |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-22855
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Observation-Free Attacks on Online Learning to Rank Sameep Chattopadhyay, Nikhil Karamchandani, Sharayu Moharir Abstract Online learning to rank (OLTR) plays a critical role in information retrieval and machine learning systems, with a wide range of applications in search engines and content recommenders. However, despite their extensive adoption, the susceptibility of OLTR algorithms to coordinated adversarial attacks remains poorly understood. In this work, we present a novel framework for attacking some of the widely used OLTR algorithms. Our framework is designed to promote a set of target items so that they appear in the list of top- K K recommendations for T − o ( T ) T-o(T) rounds, while simultaneously inducing linear regret in the learning algorithm. We propose two novel attack strategies: 𝙲𝚊𝚜𝚌𝚊𝚍𝚎𝙾𝙵𝙰 {\tt CascadeOFA} for CascadeUCB1 and 𝙿𝙱𝙼𝙾𝙵𝙰 {\tt PBMOFA} for PBM-UCB . We provide theoretical guarantees showing that both strategies require only O ( log T ) O(\log T) manipulations to succeed. Additionally, we supplement our theoretical analysis with empirical results on real-world data. \workshoptitle Workshop on Algorithmic Collective Action (ACA@NeurIPS 2025) 1 Introduction Online Learning to Rank (OLTR) [ 1 ] is a sequential decision-making framework widely used in information retrieval systems [ 2 ] to rank items based on user feedback. In an OLTR setup, the learning agent presents a ranked list of items to the user in each round, and the user provides implicit feedback by interacting with the list in some manner. One of the most widely studied forms of such feedback is click behavior, which the agent seeks to model and optimize in order to improve its recommendations. Over the years, several click feedback models have been studied, with two of the most prominent being the Cascade model [ 3 ] , where the user examines the list sequentially from top to bottom and clicks the first item they find “attractive”, therefore resulting in a single click per round, and the Position-based model [ 4 ] , which allows multiple clicks in a round and assumes that the probability of an item being examined depends on its position in the list. Due to the sequential nature of OLTR, several studies have attempted to reformulate the problem within the framework of Multi-Armed Bandits (MABs) [ 5 ] . Recent works have developed efficient learning algorithms for the Cascade [ 6 , 7 , 8 ] and the Position-based [ 9 ] feedback models. Additionally, more general algorithms that accommodate a broader class of user feedback structures, encompassing both the above models, have also been proposed and analyzed [ 10 , 11 ] . Given the widespread use of online decision-making systems, understanding their response to coordinated attacks is crucial. While extensive research has explored adversarial attack strategies for the MABs, with frameworks like reward manipulation and action manipulation [ 12 , 13 , 14 , 15 , 16 ] , relatively little attention has been given to such attacks in the OLTR setting [ 17 , 18 ] . This work focuses on a specific class of reward manipulation strategies known as observation-free attacks [ 13 ] , where a collective adversary generates (or manipulates) reward signals to promote a set of pre-determined items in a learning algorithm without having access to the algorithm’s feedback. A key feature of these observation-free attacks is that they can be executed in the real world by groups of ordinary individuals who, in spite of lacking access to the feedback from other users, can influence the algorithm to promote unattractive yet socially beneficial content through their own coordinated actions. This makes them a compelling instance of algorithmic collective action [ 19 , 20 ] . Despite their real-world applications and proven success for MABs [ 13 ] , no effective observation-free attack strategy has yet been demonstrated for even the most common OLTR algorithms [ 18 ] . 1.1 Our Contributions In this paper, we present the first study on observation-free attacks against OLTR algorithms with click feedback. Our technical contributions are summarized as follows. In Section 3 , we introduce a general framework for a limited-time observation-free attack strategy to promote a set of target items in OLTR. Based on this framework, we propose two novel attack strategies, namely {\tt CascadeOFA} and {\tt PBMOFA} for the Cascade and the Position-based feedback models, respectively. We prove that both attack strategies require just O(\log T) reward manipulations to successfully promote their target elements for T-o(T) rounds and impose \Omega(T) regret on their respective learning algorithms. Our work also addresses some of the major drawbacks of the earlier attack strategies for OLTR, specifically the need for continuous manipulation of rewards in [ 17 ] and the inability to attack UCB-based OLTR algorithms through reward manipulation in [ 18 ] . We supplement our analysis with empirical evaluation of our strategies using the MovieLens dataset [ 21 ] . 1.2 Related Work Numerous recent studies have explored adversarial attacks on classical multi-armed bandit algorithms [ 12 , 13 , 14 , 15 , 16 ] . However, adversarial attacks on OLTR [ 17 , 18 ] remain relatively unexplored. While most of the attacks on MABs could potentially be extended to OLTR, the combinatorial action space and restricted feedback structure in OLTR make these extensions non-trivial [ 17 ] . To the best of our knowledge, only two studies have investigated adversarial attacks on OLTR algorithms. The first one [ 17 ] , introduced a reward manipulation attack on CascadeUCB1 and PBM-UCB , demonstrating that a target item could be recommended for T-o(T) rounds with only o(T) corruptions. A key limitation of this attack was its reliance on observing rewards and performing costly computations in every round. The second study [ 18 ] proposed an attack-then-quit (ATQ) strategy for OLTR algorithms based on item elimination. The study also discusses the hindrances in applying ATQ-like attacks to UCB-based OLTR algorithms as one of its major drawbacks. 2 Setting In this section, we discuss our problem setting for designing an observation-free attack on OLTR algorithms. For the ease of notation, we define the following quantities. Let the universal set of all available items be \mathcal{A}=\{1,2,\dots,L\} ; at each time-step (round) t , the user is presented with an ordered list \mathcal{L}_{t}=(a_{1,t},\dots,a_{K,t}) of K items selected from \mathcal{A} , where K\leqslant L . Here, a_{i,t} is the item present at the i^{\mathrm{th}} position of \mathcal{L}_{t} , i.e., \mathcal{L}_{t}[i]=a_{i,t} . The user examines \mathcal{L}_{t} and provides feedback to the OLTR algorithm through clicks, following a specified click feedback model. 2.1 Click Feedback Models This work primarily focuses on two of the most common click feedback models for OLTR: the Cascade model [ 3 ] and the Position-based model [ 4 ] . In both models, the items are characterized by attraction probabilities w\in[0,1]^{L} . When a user examines an item a=a_{i,t} located at position i in list \mathcal{L}_{t} during round t , the probability of clicking on it is given by w_{a} , which is independent of previous rounds and the attraction probability of other items. To formally characterize the user feedback, we define the following quantities: – Examination Feedback : \mathrm{X}_{t}\in\{0,1\}^{K} , with \mathrm{X}_{i,t}=1 , if and only if a_{i,t}