REVIEW 4 major objections 4 minor 38 references
Cascading Bandits Robust to Adversarial Corruptions
T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read Online learning to rank in the cascade model survives adversarial click corruption: the paper proves two algorithms keep logarithmic regret without attacks and lose only a linear-in-C factor under a bounded adversary.
desk verdict A sensible new problem and plausible algorithms, but Lemma 1's independence assumption lets the adversary concentrate all corruption on the slow instance, so the main claim needs a major fix. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Position-based elimination (PBE) maintains one eliminated set $M^k$ for each of the $K$ list positions instead of one global set, removing item $e$ from position $k$ as soon as the lower confidence bound of $k$ better items beats the upper confidence bound of $e$. The robust wrapper runs two PBE instances: a fast instance $F$ with tight confidence radius $wd_F(a)=\sqrt{\log(8LT/\delta)/T^F(a)}$ and a slow instance $S$ with enlarged radius $wd_S(a)=\sqrt{\log(8LT/\delta)/T^S(a)} + 2\log(8LT/\delta)/T^S(a)$. Instance $S$ is played with probability $1/C$, making the expected corruption on $S$ a constant, and every elimination in $S$ is copied to $F$. This carries the argument because the enlarged radius lets $S$ tolerate up to $O(\log T)$ corrupted observations while the $1/C$ sampling keeps suboptimal items from being played often enough to inflate regret.
What would settle it
Build an adversary that observes the recommended list each round and corrupts feedback only on rounds where the slow instance is active, then measure CascadeRKC's cumulative regret as C grows; if the slow instance's observed corruption exceeds O(log T) with high probability or if regret grows faster than O(C $log^{2}$ T), the independence premise behind Lemma 1 is false for adaptive adversaries that condition on the active instance.
Extended reading notes
Core claim
The paper's central claim is that a total corruption budget C in cascading bandits can be absorbed with only a linear price in C. Concretely, CascadeRKC achieves, with high probability, $R(T) \le O(\sum_{e=K+1}^{L} (1/\Delta_{e,K}) \, K L C \, (\log(LT/\delta))^2)$, and when the corruption level is unknown, CascadeRAC achieves $R(T) \le O(\sum_{e=K+1}^{L} K (L C \log(LT/\delta) + \log T) \log(LT/\delta) / \Delta_{e,K})$. With no corruption both reduce to gap-dependent logarithmic regret. The mechanism is elimination-based: the slow instance is sampled with probability $1/C$, so only a constant amount of corruption reaches it in expectation, and the fast instance inherits its eliminations to stay efficient. When the list size is $K=1$, the bounds coincide with known robust multi-armed bandit guarantees, which the paper reads as tightness of the corruption term.
Load-bearing premise
The proof that the slow instance sees only O(1) corruption assumes the adversary's corruptions hit the fast and slow instances in proportion to how often each is played; the adversary is handed the recommended list, which can reveal which instance is active, so a determined attacker could funnel all C corruptions into the slow instance and break the logarithmic-regret argument.
Editorial extensions
If this is right
- If Theorem 3 holds, a platform that knows its corruption budget $C$ can run CascadeRKC and keep logarithmic regret when no attack is happening, degrading only linearly in $C$.
- If Theorem 4 holds, no prior knowledge of $C$ is needed: CascadeRAC stays within $O(C \log^2 T / \Delta)$ regret, with an extra $\log T$ factor for searching over $\log T$ instance levels.
- Both algorithms eliminate items per position rather than globally, which is what keeps the clean-environment regret logarithmic instead of $\sqrt{T}$.
- At $K=1$ the bounds match the known robust stochastic bandit bounds, indicating the corruption term is tight up to logarithmic factors.
- The experimental comparisons show the two algorithms outperform standard cascading-bandit baselines under periodic, early-phase, and varying-gap corruption on synthetic and real-world data.
Reading between the lines
- A determined adversary could exploit the fact that the recommended list reveals which instance is playing, concentrating all $C$ corruptions on the slow instance and violating the $O(1)$ corruption premise of Lemma 1; randomizing between two behaviorally indistinguishable lists would close that loophole.
- The two-instance PBE construction should transfer to position-based click models or other partial-feedback ranking settings, since PBE only requires per-position confidence intervals.
- A concrete testable extension is to run CascadeRKC against an adversary that always corrupts rounds when the slow instance is active and measure whether regret becomes superlinear in $C$; this would show whether the independence assumption in Lemma 1 is actually needed.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the Cascading Bandits with Adversarial Corruptions (CBAC) problem, in which an adaptive adversary with total corruption budget C can modify click feedback. It proposes two algorithms, CascadeRKC (for known C) and CascadeRAC (for agnostic C), built on a position-based elimination (PBE) subroutine. The paper claims gap-dependent logarithmic regret in corruption-free settings and regret growing linearly in C under corruption, with proofs deferred to an appendix and experiments on synthetic and real-world datasets.
Significance. If the theorems were correct, this would be the first treatment of adversarial corruptions in cascading bandits, and the position-based elimination rule combined with multi-instance sampling is a natural extension of Lykouris et al. The claimed O(C) dependence on the corruption level is also consistent with the known MAB lower bound. However, the central adaptive-corruption guarantee rests on an independence assumption in Lemma 1 that conflicts with the paper's own protocol; the appendix proofs are sketches with typos and unstated steps. The experiments, while suggestive, use only fixed-schedule adversaries and therefore do not exercise the claimed adaptive robustness.
major comments (4)
- [Section 5.1 / Appendix 9] Lemma 1 is not valid under the protocol of Section 3. The proof writes E[G_t(a_{S,t})|H_{t-1}] = C_{a_{S,t}}/C, which presumes that the adversary's corruption decision is independent of whether instance S was sampled in round t. But the protocol explicitly gives the attacker the recommended list A_t before the corruption is chosen, and A_t reveals the sampled instance because the two instances maintain different elimination sets (F eliminates items faster, so M^F is a superset of M^S). An adversary can therefore corrupt only on rounds in which S was active, concentrating all C corruptions on S and making its corruption as large as C rather than O(log(1/delta)). Since Lemma 2 and Theorems 3-4 inherit this bound, the main theoretical claims are unsupported for the stated adaptive adversary.
- [Appendix 10] The proof of Lemma 2 confuses delta1 and delta2 and misstates the Hoeffding radius. After selecting delta2 = delta'/LT, the union bound should give a radius involving log(2LT/delta')/T^S(a), not log(2/delta')/T^S(a); the subsequent step then mixes Cs <= log(1/delta1)+3 with delta2 without a coherent high-probability statement. These errors make Eq. (3) and the claim that optimal items are never eliminated insufficiently specified.
- [Section 4.2 / Algorithm 2] Algorithm 2 samples the slow instance S with probability 1/C, which is undefined when C = 0. Since the paper also claims logarithmic regret in the corruption-free case, the algorithm must handle C = 0 explicitly, for example by running only the fast instance F; as written, the pseudo-code and the subsequent analysis do not cover the no-corruption regime.
- [Appendix 11 / Proof of Theorem 3] The bound on the F-instance regret is not derived. The proof asserts that a sub-optimal item e appears at position k in F at most L*C*T^S(e) times because 'every move in the slow active arm elimination occurs with probability 1/C and, at least 1/L of these moves are plays of e,' but no justification is given for the 1/L factor in the cascade model, where elimination is position-specific and the two instances use different active sets. This step is load-bearing because the factor L appears in Theorem 3's bound.
minor comments (4)
- [Section 2] The section title contains a typo: 'Relatet Works' should be 'Related Works'.
- [Section 6 / Figures] The axis labels and legends in Figures 1-5 appear as unicode artifacts, making the plots difficult to read; the figures should be regenerated with standard text fonts.
- [Table 1] In the Movielens column, the entry '18,6502' for CascadeKL-UCB is likely a typo and should probably read '186,502'.
- [Section 5.1 / Lemma 1] The phrase 'during its exploration phase' is not defined either in the lemma statement or in the proof, which actually bounds corruption over all rounds t; please clarify the intended event.
Circularity Check
No significant circularity: regret bounds are derived from the algorithms' definitions and external concentration lemmas, not from fitted parameters or self-citations.
full rationale
The proof chain is self-contained with respect to the paper's own claims. Theorems 3 and 4 bound regret using the elimination rules of the proposed PBE instances, the confidence radii, and standard external tools (Hoeffding inequalities, Theorem 1 of Kveton et al. 2015a, and Lemma B.1 of Lykouris et al. 2018). No fitted parameter is renamed as a prediction, and no equation is defined in terms of the result it purports to prove. The algorithms are explicitly constructed to control sub-optimal plays, and the resulting bounds are derived rather than assumed. Citations to the authors' prior works (e.g., Wang et al. 2024, Dai et al. 2024, Liu et al. 2021) appear only as related work and are not load-bearing for the main theorems. The proof of Lemma 1 does assume that the adversary's corruption decision is independent of whether the S or F instance is sampled, which is not justified under the stated adaptive-adversary protocol and is a genuine correctness risk; however, that is a soundness gap, not a circular reduction, because the claimed bound is not equivalent to an input by construction. The degeneration check to K=1 matches, rather than repackages, the known MAB-with-corruptions bounds.
Assumptions & free parameters
assumptions (5)
- domain assumption Assumption 1: attraction indicators are independent Bernoulli random variables with means w(a).
- standard math Standard concentration inequalities, including Hoeffding's inequality and the martingale bound Lemma B.1 of Lykouris et al. 2018.
- domain assumption The adversary's per-round corruption is binary: the maximum over positions of |R_t(a_k) - Rtilde_t(a_k)| is either 0 or 1.
- ad hoc to paper Expected corruption in the slow instance S is O(1) because S is sampled with probability 1/C, which presumes the adversary's corruption decision is independent of whether S or F is selected.
- standard math Regret decomposition via Theorem 1 of Kveton et al. 2015a, bounding immediate regret by a sum over suboptimal items and positions.
Cite this review
Pith. "Pith review of Cascading Bandits Robust to Adversarial Corruptions." pith.science (2026). https://pith.science/paper/JWBOXQPS
@misc{pith2026250208077,
author = {Pith},
title = {Pith review of: Cascading Bandits Robust to Adversarial Corruptions},
year = {2026},
howpublished = {\url{https://pith.science/paper/JWBOXQPS}},
note = {Machine review of arXiv:2502.08077}
}
read the original abstract
Online learning to rank sequentially recommends a small list of items to users from a large candidate set and receives the users' click feedback. In many real-world scenarios, users browse the recommended list in order and click the first attractive item without checking the rest. Such behaviors are usually formulated as the cascade model. Many recent works study algorithms for cascading bandits, an online learning to rank framework in the cascade model. However, the performance of existing methods may drop significantly if part of the user feedback is adversarially corrupted (e.g., click fraud). In this work, we study how to resist adversarial corruptions in cascading bandits. We first formulate the ``\textit{Cascading Bandits with Adversarial Corruptions}" (CBAC) problem, which assumes that there is an adaptive adversary that may manipulate the user feedback. Then we propose two robust algorithms for this problem, which assume the corruption level is known and agnostic, respectively. We show that both algorithms can achieve logarithmic regret when the algorithm is not under attack, and the regret increases linearly with the corruption level. The experimental results also verify the robustness of our methods.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Cascading bandits: Learning to rank in the cascade model
Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In International conference on machine learning, pages 767--776. PMLR, 2015 a
work page 2015
-
[2]
Learning to rank: Regret lower bounds and efficient algorithms
Richard Combes, Stefan Magureanu, Alexandre Proutiere, and Cyrille Laroche. Learning to rank: Regret lower bounds and efficient algorithms. In Proceedings of the 2015 ACM SIGMETRICS international conference on measurement and modeling of computer systems, pages 231--244, 2015
work page 2015
-
[3]
Learning to rank: from pairwise approach to listwise approach
Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129--136, 2007
2007
-
[4]
Andrew Trotman. Learning to rank. Information Retrieval, 8: 0 359--381, 2005
work page 2005
-
[5]
Toprank: A practical algorithm for online stochastic ranking
Tor Lattimore, Branislav Kveton, Shuai Li, and Csaba Szepesvari. Toprank: A practical algorithm for online stochastic ranking. Advances in Neural Information Processing Systems, 31, 2018
work page 2018
-
[6]
Thompson sampling algorithms for cascading bandits
Zixin Zhong, Wang Chi Chueng, and Vincent YF Tan. Thompson sampling algorithms for cascading bandits. The Journal of Machine Learning Research, 22 0 (1): 0 9915--9980, 2021
work page 2021
-
[7]
An experimental comparison of click position-bias models
Nick Craswell, Onno Zoeter, Michael Taylor, and Bill Ramsey. An experimental comparison of click position-bias models. In Proceedings of the 2008 international conference on web search and data mining, pages 87--94, 2008
work page 2008
-
[8]
Combinatorial cascading bandits
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Combinatorial cascading bandits. Advances in Neural Information Processing Systems, 28, 2015 b
work page 2015
Show all 38 references
-
[9]
Cascading non-stationary bandits: Online learning to rank in the non-stationary cascade model
Chang Li and Maarten De Rijke. Cascading non-stationary bandits: Online learning to rank in the non-stationary cascade model. arXiv preprint arXiv:1905.12370, 2019
1905 arXiv
-
[10]
Stochastic bandits robust to adversarial corruptions
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, 2018
2018
-
[11]
Better algorithms for stochastic bandits with adversarial corruptions
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562--1578. PMLR, 2019
2019
-
[12]
Learning diverse rankings with multi-armed bandits
Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th international conference on Machine learning, pages 784--791, 2008
2008
-
[13]
Cooperative stochastic multi-agent multi-armed bandits robust to adversarial corruptions
Junyan Liu, Shuai Li, and Dapeng Li. Cooperative stochastic multi-agent multi-armed bandits robust to adversarial corruptions. arXiv preprint arXiv:2106.04207, 2021
2021 arXiv
-
[14]
Stochastic graphical bandits with adversarial corruptions
Shiyin Lu, Guanghui Wang, and Lijun Zhang. Stochastic graphical bandits with adversarial corruptions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8749--8757, 2021
2021
-
[15]
Robust stochastic linear contextual bandits under adversarial attacks
Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 7111--7123. PMLR, 2022
2022
-
[16]
Online corrupted user detection and regret minimization
Zhiyong Wang, Jize Xie, Tong Yu, Shuai Li, and John Lui. Online corrupted user detection and regret minimization. Advances in Neural Information Processing Systems, 36, 2024
2024
-
[17]
Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7 0 (6), 2006
2006
-
[18]
Online learning to rank in stochastic click models
Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Online learning to rank in stochastic click models. In International conference on machine learning, pages 4199--4208. PMLR, 2017
2017
-
[19]
Minimax regret for cascading bandits
Daniel Vial, Sujay Sanghavi, Sanjay Shakkottai, and R Srikant. Minimax regret for cascading bandits. arXiv preprint arXiv:2203.12577, 2022
2022 arXiv
-
[20]
Contextual combinatorial cascading bandits
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In International conference on machine learning, pages 1245--1253. PMLR, 2016
2016
-
[21]
Online clustering of contextual cascading bandits
Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
2018
-
[22]
Cascading bandits for large-scale recommendation problems
Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cascading bandits for large-scale recommendation problems. arXiv preprint arXiv:1603.05359, 2016
2016 arXiv
-
[23]
Online learning to rank with features
Shuai Li, Tor Lattimore, and Csaba Szepesv \'a ri. Online learning to rank with features. In International Conference on Machine Learning, pages 3856--3865. PMLR, 2019 a
2019
-
[24]
Cascading hybrid bandits: Online learning to rank for relevance and diversity
Chang Li, Haoyun Feng, and Maarten de Rijke. Cascading hybrid bandits: Online learning to rank for relevance and diversity. In Proceedings of the 14th ACM Conference on Recommender Systems, pages 33--42, 2020
2020
-
[25]
Corruption-tolerant bandit learning
Sayash Kapoor, Kumar Kshitij Patel, and Purushottam Kar. Corruption-tolerant bandit learning. Machine Learning, 108 0 (4): 0 687--715, 2019
2019
-
[26]
Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22 0 (1): 0 1310--1358, 2021
2021
-
[27]
Stochastic dueling bandits with adversarial corruption
Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil. Stochastic dueling bandits with adversarial corruption. In Algorithmic Learning Theory, pages 217--248. PMLR, 2021
2021
-
[28]
Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm
Mohammad Hajiesmaili, Mohammad Sadegh Talebi, John Lui, Wing Shing Wong, et al. Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. Advances in Neural Information Processing Systems, 33: 0 19943--19952, 2020
2020
-
[29]
Stochastic linear optimization with adversarial corruption
Yingkai Li, Edmund Y Lou, and Liren Shan. Stochastic linear optimization with adversarial corruption. arXiv preprint arXiv:1909.02109, 2019 b
1909 arXiv
-
[30]
Nearly optimal algorithms for linear contextual bandits with adversarial corruptions
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:2205.06811, 2022
2022 arXiv
-
[31]
Online learning and detecting corrupted users for conversational recommendation systems
Xiangxiang Dai, Zhiyong Wang, Jize Xie, Tong Yu, and John CS Lui. Online learning and detecting corrupted users for conversational recommendation systems. IEEE Transactions on Knowledge and Data Engineering, 2024
2024
-
[32]
Stochastic linear bandits robust to adversarial attacks
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991--999. PMLR, 2021
2021
-
[33]
The movielens datasets: History and context
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5 0 (4): 0 1--19, 2015
2015
-
[34]
Federated multi-armed bandits
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9603--9611, 2021
2021
-
[35]
Comparison-based conversational recommender system with relative bandit feedback
Zhihui Xie, Tong Yu, Canzhe Zhao, and Shuai Li. Comparison-based conversational recommender system with relative bandit feedback. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1400--1409, 2021
2021
-
[36]
Bernoulli rank- 1 bandits for click feedback
Sumeet Katariya, Branislav Kveton, Csaba Szepesv \'a ri, Claire Vernade, and Zheng Wen. Bernoulli rank- 1 bandits for click feedback. arXiv preprint arXiv:1703.06513, 2017
2017 arXiv
-
[37]
Clustering of conversational bandits for user preference learning and elicitation
Junda Wu, Canzhe Zhao, Tong Yu, Jingyang Li, and Shuai Li. Clustering of conversational bandits for user preference learning and elicitation. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2129--2139, 2021
2021
-
[38]
Click models for web search
Aleksandr Chuklin, Ilya Markov, and Maarten de Rijke. Click models for web search. Synthesis lectures on information concepts, retrieval, and services, 7 0 (3): 0 1--115, 2015
2015
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.