# Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach

arXiv: https://arxiv.org/abs/2511.03074 · HTML: https://mlsanity.com/paper/2511.03074/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 43 references that are in the map.
- First posted on arXiv 4 Nov 2025.

## Builds on (most cited first, 24 of 24)

- [Wide & Deep Learning for Recommender Systems](https://mlsanity.com/paper/1606.07792/) (2016)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Reinforcement Learning to Rank in E-Commerce Search Engine: Formalization, Analysis, and Application](https://mlsanity.com/paper/1803.00710/) (2018)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [Online Learning to Rank in Stochastic Click Models](https://mlsanity.com/paper/1703.02527/) (2017)
- [Online Clustering of Contextual Cascading Bandits](https://mlsanity.com/paper/1711.08594/) (2017)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [DCM Bandits: Learning to Rank with Multiple Clicks](https://mlsanity.com/paper/1602.03146/) (2016)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Thompson Sampling Algorithms for Cascading Bandits](https://mlsanity.com/paper/1810.01187/) (2018)
- [Learning Product Rankings Robust to Fake Users](https://mlsanity.com/paper/2009.05138/) (2020)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs](https://mlsanity.com/paper/2110.13876/) (2021)
- [Adversarial Attacks on Online Learning to Rank with Click Feedback](https://mlsanity.com/paper/2305.17071/) (2023)
- [Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations](https://mlsanity.com/paper/2106.06712/) (2021)
- [Cascading Bandits Robust to Adversarial Corruptions](https://mlsanity.com/paper/2502.08077/) (2025)

## Abstract (arXiv)

Online learning to rank (OLTR) studies how to recommend a short ranked list of items from a large pool and improves future rankings based on user clicks. This setting is commonly modeled as cascading bandits, where the objective is to maximize the likelihood that the user clicks on at least one of the presented items across as many timesteps as possible. However, such systems are vulnerable to click fraud and other manipulations (i.e., corruption), where bots or paid click farms inject corrupted feedback that misleads the learning process and degrades user experience. In this paper, we propose MSUCB, a robust algorithm that incorporates a novel mean-of-medians estimator, which to our knowledge is applied to bandits with corruption setting for the first time. This estimator behaves like a standard mean in the absence of corruption, so no cost is paid for robustness. Under corruption, the median step filters out outliers and corrupted samples, keeping the estimate close to its true value. Updating this estimate at every round further accelerates empirical convergence in experiments. Hence, MSUCB achieves optimal logarithmic regret in the absence of corruption and degrades gracefully under corruptions, with regret increasing only by an additive term tied to the total corruption. Comprehensive and extensive experiments on real-world datasets further demonstrate that our approach consistently outperforms prior methods while maintaining strong robustness. In particular, it achieves a (97.35%) and a (91.60%) regret improvement over two state-of-the-art methods.