{"id":"c9780149-21aa-4392-8416-09acab8e7d73","arxiv_id":"2502.08077","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Cascading bandits can be made robust to adversarial click corruption using multi-instance position-based elimination, with regret logarithmic in time and linear in the corruption budget.","lead":"This paper proposes two algorithms that keep online ranking systems from being tricked by fake clicks. Their regret grows linearly with the amount of corruption, and experiments on synthetic and real-world data show lower regret than existing cascading bandits.","discovery_kind":"new_application","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18265,"tokens_out":9098,"duration_ms":80754,"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":[{"comment":"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.","section":"Section 5.1 / Appendix 9"},{"comment":"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":"Appendix 10"},{"comment":"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.","section":"Section 4.2 / Algorithm 2"},{"comment":"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.","section":"Appendix 11 / Proof of Theorem 3"}],"minor_comments":[{"comment":"The section title contains a typo: 'Relatet Works' should be 'Related Works'.","section":"Section 2"},{"comment":"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.","section":"Section 6 / Figures"},{"comment":"In the Movielens column, the entry '18,6502' for CascadeKL-UCB is likely a typo and should probably read '186,502'.","section":"Table 1"},{"comment":"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.","section":"Section 5.1 / Lemma 1"}],"recommendation":"reject","confidential_remarks":"The manuscript is an early version with sketchy appendix proofs and damaged figures, but the decisive problem is in the main theorem: Lemma 1's independence assumption contradicts the stated adaptive-adversary protocol. Because the adversary observes the recommended list A_t, it can infer which of the two instances is active and channel all corruption into the slow instance S. This is not a local fix; it changes the model or the algorithm. If the authors can prove the regret bounds for the adaptive adversarial setting, or explicitly restrict the adversary, the paper could be resubmitted; as it stands the central claim is not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"New problem, plausible algorithms, but the main theorem rests on an independence assumption the adversary can break. That is the headline.\n\nWhat is genuinely new: the CBAC formulation is a fair model of click fraud in cascade ranking, and the position-based elimination scheme—one elimination set per rank position—is a reasonable adaptation of active arm elimination to the cascade setting. The two algorithms, CascadeRKC (known corruption) and CascadeRAC (agnostic), follow the Lykouris et al. template, and the regret bounds degenerate to the MAB bounds when K=1, which is a good sanity check. The experiments are broad: synthetic plus Yelp, Movielens, and Yandex, with multiple corruption levels and mechanisms, and the proposed methods consistently beat the baselines. That empirical part looks real, though there are no error bars and no code.\n\nThe soft spot is Lemma 1. The proof assumes that when the slow instance S is sampled (probability 1/C), the corruption it receives is O(1) because corruption only hits the played instance with that probability. That is only true if the adversary's corruption choice is independent of whether S or F produced the list. But the protocol hands the adversary the recommended list, and the two instances produce identifiably different lists: F eliminates sub-optimal items quickly, while S plays everything for a long time. A budget-C adversary can simply corrupt the list whenever it appears to come from S, pushing C corruptions into S and breaking the constant-corruption bound. The proof does not address this. I don't see a way out without either weakening the adversary model (e.g., adversary cannot see the list before choosing corruptions, which contradicts the stated protocol) or making the instances' outputs indistinguishable, which the current algorithm does not do.\n\nThe appendix also has fixable sloppiness: δ1 and δ2 are conflated, a union bound loses an LT factor in the log, and the high-probability arguments in Theorem 3 are sketches. The experiments lack error bars and code, so I'd take the empirical claims as preliminary.\n\nThe problem is worth studying and the design is promising, but the central guarantee is unsupported as written. This should not be accepted yet. It should, however, be sent to a serious referee: the gap is specific and plausibly closable, and the paper's framing could be useful to the learning-to-rank community even if the current proof fails.\n\nVerdict: send to peer review expecting major revision; bring to reading group for the Lemma 1 discussion.","headline":"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.","tokens_in":18717,"tokens_out":6040,"would_cite":false,"duration_ms":462060,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["cascading bandits","adversarial corruptions","learning to rank","click fraud","regret bounds","elimination algorithms","online learning","robustness"],"falsifier":"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.","tokens_in":18102,"feed_emoji":"🛡️","tokens_out":9361,"duration_ms":69638,"temperature":0.7,"pith_summary":"Online learning to rank in the cascade model—where a user scans a short list and clicks the first attractive item—breaks down if part of the click feedback is adversarially corrupted. This paper claims the damage can be contained: it introduces CascadeRKC and CascadeRAC, for known and unknown corruption budgets C, and proves both keep the clean-environment logarithmic regret while paying only an extra term linear in C under an adaptive adversary. The proofs rest on a position-based elimination rule that keeps a separate eliminated set for each list position, plus a two-instance design in which a slow, corruption-tolerant instance is played rarely so it absorbs most of the attack. If the bounds are right, click fraud in recommender systems no longer forces a choice between logarithmic no-attack regret and robustness.","feed_headline":"Cascading bandits survive click fraud at linear cost","feed_subtitle":"Two elimination algorithms keep logarithmic regret without attacks and degrade only linearly in the corruption budget.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the cascading-bandits problem, the cascade reward decomposition, and the per-item regret-event bound used to turn elimination times into a regret bound.","marker":"Kveton et al. [2015a]"},{"why":"Supplies the multi-instance robust elimination template and the concentration inequality (Lemma B.1) used to bound the corruption that reaches the slow instance.","marker":"Lykouris et al. [2018]"},{"why":"Establishes active arm elimination, the base scheme that position-based elimination extends to K-position lists.","marker":"Even-Dar et al. [2006]"},{"why":"Provides the improved robust multi-armed bandit bounds that the K=1 specialization of CascadeRKC and CascadeRAC is compared against.","marker":"Gupta et al. [2019]"}],"fun_headline_variants":["Cascading bandits: corruption costs only linear regret","Click fraud-proof cascading bandits: pay linearly","Robust cascading bandits: linear price for adversarial clicks","Cascading bandits survive click fraud at linear cost","Adversarial corruptions in cascading bandits: linear toll"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cascading bandits: corruption costs only linear regret","Click fraud-proof cascading bandits: pay linearly","Robust cascading bandits: linear price for adversarial clicks","Cascading bandits survive click fraud at linear cost","Adversarial corruptions in cascading bandits: linear toll"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000228,"raw_usage":{"total_tokens":1485,"prompt_tokens":967,"completion_tokens":518,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":435}},"tokens_in":583,"tokens_out":518,"duration_ms":5102,"temperature":1.0,"reasoning_tokens":435,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T10:32:53.185898+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Stochastic bandits robust to adversarial corruptions","cited_arxiv_id":null,"evidence_quote":"Supplies the multi-instance robust elimination template and the concentration inequality (Lemma B.1) used to bound the corruption that reaches the slow instance."},{"cited_title":"Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems","cited_arxiv_id":null,"evidence_quote":"Establishes active arm elimination, the base scheme that position-based elimination extends to K-position lists."},{"cited_title":"Better algorithms for stochastic bandits with adversarial corruptions","cited_arxiv_id":null,"evidence_quote":"Provides the improved robust multi-armed bandit bounds that the K=1 specialization of CascadeRKC and CascadeRAC is compared against."}],"review_version":1}