{"id":"045d5340-260a-40a4-9ae7-0944d77eb5d9","arxiv_id":"2608.11873","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new multiplayer formulation of Dependent Click Model bandits with action and reward asymmetry, three decentralized algorithms, and sublinear regret guarantees.","lead":"This paper extends click-model bandit learning to a multiplayer setting where several agents share a ranked list, see different feedback, and cannot always see each other's actions. It proposes three algorithms with sublinear regret bounds and small simulations showing coordinated learning beats independent learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Multi-slot observation probability is algebraically inverted: Lemma 5 and Theorems 6/8 use (1-w)+wv instead of 1-wv, so the stated multi-slot regret bounds do not follow as written.","rationale":"The reader's weakest assumption concerned whether players can correctly attribute observed click feedback to joint items in Problems A and C. That is a legitimate ambiguity. However, the more decisive problem is a concrete mathematical error in the DCM observation model: the paper's p_k formula is inverted, so the multi-slot observation-count analysis is wrong independent of any coordination or attribution question. This directly undermines Lemma 5 and the quantitative statements of Theorems 6 and 8, which are central to the paper's multi-click contribution. I do not think the paper must be rejected outright: the algorithms could still have sublinear regret after correcting p_k to \\prod(1 - w_j v_j), and the first-slot theorems (Theorems 2, 4, and 7) do not rely on this formula. But the stated bounds should not be accepted as written, so the appropriate verdict remains conditional, as the reader already concluded. I marked agreement_with_reader as 'disagree' because the reader's identified weakest assumption is not the same as the load-bearing flaw I found.","tokens_in":11518,"tokens_out":12789,"duration_ms":140685,"concrete_test":"Simulate the DCM with K=2, v_1=1, and w(e_1)=0.5 over many rounds, recording how often slot 2 is observed. The paper's p_2 formula gives 1, while the correct continuation probability is 0.5; the simulation will match 0.5, falsifying Lemma 5 as written. Then recompute Theorem 8's alpha with p_min defined as min \\prod_{j<k}(1 - w(e_j) v_j) instead of the current product; if the regret bound's exponential factor changes, the stated multi-slot guarantee depends on the erroneous formula.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is the formula for the probability that a slot-k item is observed, defined in Section III.B before Lemma 5 as p_k(e) = \\prod_{j<k} [(1-w(e_j)) + w(e_j) v_j]. Under the paper's own DCM definition in Section II.C, a user who clicks at slot j continues with probability 1-v_j, and a user who does not click continues with probability 1; so the probability of reaching slot k is \\prod_{j<k} (1 - w(e_j) v_j). The paper's factor, (1-w) + wv = 1 - w(1-v), is the probability that the user does not click-and-continue, which is not the continuation probability. The error is visible at the extremes: for v=1, the paper's factor equals 1, predicting that a slot-2 item is always observed after a click at slot 1, whereas the true continuation probability is 1-w(e_1); for v=0, the paper's factor equals 1-w, predicting continuation only when there is no click, whereas the true continuation probability is 1. Because Lemma 5's observation-count lower bound, the definition of p_min, and the alpha = 1 + (K-1)p_min factor in Theorems 6 and 8 all inherit this formula, the quantitative multi-slot regret guarantees are not established as stated. The qualitative sublinear-regret claim may survive with a corrected p_min, but the paper's stated bounds and the abstract's claim about small termination probabilities rest on this algebraic error.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a multiplayer information-asymmetric extension of Dependent Click Model (DCM) bandits, in which several players jointly form a ranked list, each controlling one coordinate of each joint item, and users may click multiple times according to slot-dependent termination probabilities. Three information structures are considered: action asymmetry (Problem A), reward asymmetry (Problem B), and both (Problem C). For each, the paper proposes a decentralized algorithm—mCascadeUCB-A, mCascadeUCB-Intervals-Ranking(-multiple), and mMDSEE-TopK—and claims sublinear regret guarantees in Theorems 2, 4, 6, 7, and 8. Experiments on a small synthetic instance (L=3, K=2, M=3) compare the methods under low and high termination probabilities. The paper also claims that for small termination probabilities, knowing the termination ranking is unnecessary.","tokens_in":11850,"tokens_out":8339,"duration_ms":84212,"significance":"If the guarantees were correct, this would be a useful first systematic treatment of decentralized multi-click cascading bandits, and the proposed coordination mechanisms would be of interest to the online-learning-to-rank community. The paper is also honest about its limitations, explicitly leaving lower bounds and factored-structure improvements open, and its experimental comparison includes a sensible per-player UCB baseline. However, the current version contains load-bearing proof gaps and an algebraic error in the multi-slot observation probability, so the theoretical claims are not yet established as stated.","major_comments":[{"comment":"Theorem 2, the main regret guarantee for Problem A, is stated without a proof. The appendix contains proofs for Theorems 4, 6, 7, and 8, but no proof for Theorem 2. Because the mCascadeUCB-A coordination argument depends on showing that all players share identical statistics and select identical joint rankings, the absence of a proof leaves the central claim of the action-asymmetry setting unverified.","section":"Section III.A, Theorem 2"},{"comment":"The observation probability p_k(e) is algebraically incorrect. The paper defines p_k(e) = \\prod_{j<k} [(1-w(e_j)) + w(e_j) v_j]. Under the DCM described in Section II.C, the probability that the cascade reaches slot k is \\prod_{j<k} (1 - w(e_j) v_j), because the user continues after slot j either by not clicking (probability 1-w(e_j)) or by clicking and not terminating (probability w(e_j)(1-v_j)). The paper's factor equals 1 - w(e_j)(1-v_j), which is the probability that the user does not click-and-continue, not the continuation probability. The error is visible at the extremes: for v_j=1, the paper's factor is 1, predicting that slot k is always reached after a click at slot j, whereas the true continuation probability after a click is 0; for v_j=0, the paper's factor is 1-w(e_j), whereas the true continuation probability is 1. Because p_min, Lemma 5's observation lower bound, and the constants A, c, and alpha in Theorems 6 and 8 all inherit this factor, the quantitative multi-slot regret bounds are not established as stated. The qualitative sublinear-regret claim may survive with a corrected p_min, but the analysis must be redone.","section":"Section III.B, Lemma 5 and Theorems 6 and 8"},{"comment":"The exploration regret in Theorem 7 is inconsistent with the proof. The theorem states the first term as O(L^M log T log log T), but the appendix proof bounds R_{T,E} \\le L^M F(\\lfloor \\log_2 T \\rfloor) \\lceil \\log_2 T \\rceil = O(L^M \\log^2 T) when F(\\lambda)=\\lambda. The stated log log T factor is not derived anywhere in the proof, and the actual calculation gives a quadratic logarithm.","section":"Section III.C, Theorem 7 and appendix proof"},{"comment":"The derivation of the multi-slot effective observation count is not rigorous. The proof writes \\tilde n_t(e) = n_t(e) + (K-1)(1 - \\sqrt{\\log T/(2 p_min^2 n_t(e))}) n_t(e) p_min and then drops lower-order terms to conclude \\tilde n_t(e) = \\Theta(F_0(t) \\log t [1+(K-1)p_min]). This step is not justified for all t appearing in the subsequent sum, and it depends on the incorrect p_min definition from Lemma 5. Consequently the alpha-scaling claim and the reported regret bound for Theorem 8 are unsupported.","section":"Section III.C, Theorem 8 and appendix proof"}],"minor_comments":[{"comment":"The notation K_max = K_1 \\cdots K_M is undefined; presumably it should be L^M, and the exploration phase that visits all joint items should last at least ceil(L^M / K) rounds, since K joint items are displayed per round.","section":"Section III.A"},{"comment":"The appendix proof labels are scrambled: the 'Proof.' immediately following Lemma 9 proves Lemma 5, not Lemma 9, and the proof of Theorem 4 starts only later. This makes the appendix difficult to follow.","section":"Appendix"},{"comment":"The claim that 'for small termination probabilities, the termination ranking need not be known' is stated in the abstract and conclusion but is never formulated as a theorem with explicit assumptions. Please identify which result establishes this and state the condition on the termination probabilities.","section":"Abstract and Section VI"},{"comment":"The domination condition in line 7, UCB_t(e) < \\max_{e'\\in D} LCB_t(e'), triggers sabotage, but it is not specified how the player who detects the condition coordinates the deviation when the player with the low UCB is different from the detecting player. A clearer description of the implicit-signaling protocol would help.","section":"Algorithm 2"},{"comment":"Figures 1 and 2 appear in the manuscript only as captions without the actual plots, so the experimental claims cannot be visually verified from the submitted text.","section":"Section IV"},{"comment":"Equation (5) invokes a 'good event' without defining it; please spell out the high-probability event and the exact concentration constants used in the confidence intervals.","section":"Appendix, proof of Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The Problem C algorithm is a direct extension of the authors' own prior work [16,17], which is not circular but should be presented more carefully as an extension. More importantly, the missing proof of Theorem 2, the unsupported exploration bound in Theorem 7, and the algebraic error in the multi-slot observation probability are load-bearing for the paper's main claims. These issues are fixable in principle, but they require substantial re-derivation, so the current version should not be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short version: this paper opens a genuinely new area—multiplayer cascading bandits with multi-click feedback under information asymmetry—and the three problem settings are worth thinking about. But as written, the main theoretical guarantees do not stand. The biggest issue is a wrong formula for the observation probability in Section III.B, and it infects Lemma 5 and Theorems 6 and 8. In the DCM, after a click at slot j, the user continues with probability 1-v_j and stops with probability v_j; if there is no click, the user continues. So the probability that slot k is reached is \\prod_{j<k}(1 - w(e_j) v_j). The paper writes p_k(e)=\\prod_{j<k}[(1-w(e_j))+w(e_j)v_j], which equals \\prod_{j<k}(1 - w(e_j)(1-v_j)). That is not the continuation probability. Check the edges: at v=1, the paper's factor is 1, so a slot-2 item is always observed after a click at slot 1, but the true continuation probability is 1-w(e_1). At v=0, the paper's factor is 1-w, but the true continuation probability is 1. Since p_min and the alpha factor in Theorems 6 and 8 derive from this formula, those bounds are not established. The qualitative sublinear-regret claim may survive with a corrected p_min, but you can't take the stated rates as proven.\n\nThere are also smaller gaps. Theorem 2 is stated without proof; the appendix has proofs for Theorems 4, 6, 7, and 8, but not for the first main result. The abstract says \"for small termination probabilities, the termination ranking need not be known,\" but I don't find a formal statement that actually proves that in the text. And the observability model in Problem A is under-specified: after the initial joint schedule, do players really know which joint item occupied each slot if they cannot see each other's actions? The proof seems to rely on identical UCB statistics plus a deterministic tie-breaking rule, but that only works if the click feedback tells every player which joint item was clicked, which is not obvious when they only observe a click position and know their own action but not the others'.\n\nOn the positive side, the coordination mechanisms are clever. The sabotage signaling in Problem B is a neat idea, and the MDSEE extension for Problem C is a reasonable adaptation of prior work (including the authors' own). The experiments are small but they sanity-check the qualitative claims. The novelty is real: nobody has combined multi-click DCM feedback with multiplayer information asymmetry in this way.\n\nWho is this for? Members of the bandits/online learning community who care about decentralized ranking. It deserves a serious referee, but the referee will need to verify the probability algebra and the missing proof before the results can be accepted. My recommendation: engage, but with a heavy revision request.\n\nBest,\n[You]","headline":"Novel settings and some clever coordination tricks, but the multi-slot analysis has a load-bearing probability error and Theorem 2 is unproved.","tokens_in":12363,"tokens_out":4480,"would_cite":false,"duration_ms":42716,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Decentralized players with asymmetric access to actions and rewards can still learn near-optimal ranked lists in the Dependent Click Model, and with small termination probabilities they do not even need the termination ranking.","keywords":["multi-armed bandits","cascading bandits","multiplayer learning","information asymmetry","dependent click model","online learning","regret bounds","decentralized coordination"],"falsifier":"Run mCascadeUCB-A (Problem A) in a simulator where the click feedback reports only the slot index of the first click, not the identity of the full joint item in that slot, while players cannot see each other's actions; if players' statistics diverge and cumulative regret grows linearly with $T$, the attribution assumption that carries the proof is violated.","tokens_in":11311,"feed_emoji":"🎯","tokens_out":15520,"duration_ms":140155,"temperature":0.7,"pith_summary":"Multiplayer recommendation is harder than running $M$ independent bandits: several players jointly compose one ranked list, each controls only their own part of every entry, and each may see a different slice of the click feedback. This paper claims that despite those information asymmetries, sublinear regret is achievable in all three combinations—hidden actions, private rewards, or both—using algorithms that coordinate through shared statistics, deterministic schedules, and observable deviations rather than messages. It also claims that when user sessions rarely continue after a click, the algorithms no longer need to know the termination probabilities that govern how many clicks occur, a relaxation relative to earlier single-agent DCM bandits. If these claims hold, multi-stakeholder recommender systems can learn jointly from click feedback without a central controller or inter-player communication; the main open question is whether the exponential dependence on $L^M$ in the regret bounds is an artifact of the algorithms or an intrinsic price.","feed_headline":"No-communication cascade bandits get sublinear regret","feed_subtitle":"For action, reward, or both asymmetries, decentralized players match single-agent regret order without talking.","key_machinery":"The argument runs on joint items—$M$-tuples $a_k=(a_k^1,\\dots,a_k^M)$, one coordinate per player—which turn the shared ranking problem into a combinatorial bandit over the product set $E=E_1\\times\\cdots\\times E_M$ of size $L^M$. Three coordination devices carry the proofs: (1) shared UCB statistics over joint items with a fixed lexicographic tie-break, so every player computes the same top-$K$ list without seeing the others' actions; (2) lower and upper confidence intervals combined with an implicit sabotage signal, where a player leaves the deterministic round-robin schedule to announce that a candidate is dominated; (3) an MDSEE-style phased explore-then-commit routine with schedule $F(\\lambda)=\\lambda$, after which exploitation rankings come from empirical means and exploitation-round feedback is deliberately ignored because attribution to joint items would be unreliable. The multi-click DCM structure enters through slot termination probabilities $v_j$ and through $p_{\\min}$, the minimum probability that a user reaches a slot past the first; the factor $\\alpha=1+(K-1)p_{\\min}$ measures how many extra effective observations per round deeper slots provide.","core_discovery":"The paper's central claim is that the Dependent Click Model stays learnable when the single agent is replaced by $M$ players who jointly select a $K$-item ranked list, provided each form of asymmetry is met with the right coordination device. For action asymmetry (Problem A), a pre-agreed exploration schedule followed by identical UCB indices over joint items lets every player reconstruct the same top-$K$ list despite not observing the others' actions, giving regret $O(\\sum_e \\frac{12}{\\Delta_{e,K}}\\log T + \\frac{\\pi^2}{3}L^M)$. For reward asymmetry (Problem B), lower-upper confidence intervals plus an implicit sabotage signal—departing from the common round-robin schedule—eliminate dominated items with $O(\\log T)$ gap-dependent regret, and with multi-slot feedback the bound approaches the classical $O(\\log T/\\Delta^2)$ when $p_{\\min}\\approx 1$. For both asymmetries (Problem C), a phased explore-then-commit algorithm (mMDSEE-TopK) obtains sublinear regret using either first-slot or multi-slot feedback, with a mis-commitment term governed by the concentration of empirical means. The paper further claims that for small termination probabilities the termination ranking need not be known, and that multi-slot feedback is beneficial only in that regime, matching the effective-observation factor $\\alpha=1+(K-1)p_{\\min}$.","pith_inferences":["A matching lower bound would likely show whether the $L^M$ dependence is intrinsic; a concrete route the authors point to is assuming a generalized linear link function over per-player features, which should bring regret down to polynomial in $L$.","The sabotage-signaling idea suggests a general protocol: in cooperative learning with private rewards, deterministic schedules can carry information through deliberate deviations, so 'no communication' does not mean 'no information exchange.'","For deployed multi-stakeholder recommender systems, the results imply that joint ranking can be tuned online from click feedback alone, without a central module or cross-party messaging, provided slot-to-item attribution is reliable; this is a testable engineering claim the paper does not run at scale.","The high-termination experiment warns that naively using all observed clicks can hurt; a practical rule of thumb would be to disable multi-slot updates when the estimated $p_{\\min}$ falls below a threshold, which is beyond the paper's stated algorithm."],"forward_implications":["In the action-asymmetry setting, players who cannot see one another's choices still match the regret order of a centralized single-agent cascading UCB algorithm (Theorem 2).","In the reward-asymmetry setting, players who share actions but hold independent click streams identify the top-$K$ ranking with gap-dependent $O(\\log T)$ regret, and the bound approaches the classical $O(\\log T/\\Delta^2)$ when termination probabilities are small (Theorems 4 and 6).","When both actions and rewards are asymmetric, the no-communication phased algorithm still achieves sublinear regret under both first-slot and multi-slot feedback (Theorems 7 and 8).","For small termination probabilities, learning no longer requires knowing the termination ranking, a relaxation of the single-agent DCM requirement.","Which feedback structure is better depends on the termination regime: full multi-slot feedback helps when $p_{\\min}$ is large, while first-slot-only feedback wins when users terminate early, as the experiments show."],"supporting_citations":[{"why":"Supplies the cascade model and the single-agent cascading UCB regret analysis that all multi-agent bounds are measured against.","marker":"[1]"},{"why":"Introduces the multiple-click dependent-click model that the paper extends from one agent to several.","marker":"[2]"},{"why":"The closest single-agent DCM bandit algorithm; its termination-ranking requirement is the one the paper relaxes for small termination probabilities.","marker":"[3]"},{"why":"Analyzes cascading bandits over factored action sets, motivating why the un-factored product model carries an L^M dependence.","marker":"[7]"},{"why":"Provides the cooperative multiplayer bandit framework, the MDSEE phased exploration scheme, and the lexicographic tie-break used for no-communication coordination.","marker":"[16]"},{"why":"Supplies the noisy-reward no-communication multiplayer analysis that the multi-slot cascade extension builds on.","marker":"[17]"}],"fun_headline_variants":["Multiplayer DCM bandits handle information asymmetry","Sublinear regret for multiplayer cascading bandits","Shared list, multiple clicks, no talk: sublinear regret","No-talk multiplayer cascade bandits match single-agent regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"In the no-communication settings, every player must be able to determine, from the pre-agreed schedule and local feedback alone, exactly which full joint item occupied each observed slot; if click feedback is ever ambiguous about that attribution, shared statistics diverge and the regret bounds stop applying.","fun_headline_variants_meta":{"raw":{"variants":["Multiplayer DCM bandits handle information asymmetry","Sublinear regret for multiplayer cascading bandits","Shared list, multiple clicks, no talk: sublinear regret","No-talk multiplayer cascade bandits match single-agent regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001271,"raw_usage":{"total_tokens":5213,"prompt_tokens":968,"completion_tokens":4245,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":584,"completion_tokens_details":{"reasoning_tokens":4182}},"tokens_in":584,"tokens_out":4245,"duration_ms":28872,"temperature":1.0,"reasoning_tokens":4182,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:25:07.703088+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run mCascadeUCB-A (Problem A) in a simulator where the click feedback reports only the slot index of the first click, not the identity of the full joint item in that slot, while players cannot see each other's actions; if players' statistics diverge and cumulative regret grows linearly with $T$, the attribution assumption that carries the proof is violated.","supporting_citations":[{"cited_title":"Cascading bandits: Learning to rank in the cascade model,","cited_arxiv_id":null,"evidence_quote":"Supplies the cascade model and the single-agent cascading UCB regret analysis that all multi-agent bounds are measured against."},{"cited_title":"Efficient multiple-click models in web search,","cited_arxiv_id":null,"evidence_quote":"Introduces the multiple-click dependent-click model that the paper extends from one agent to several."},{"cited_title":"Dcm bandits: Learning to rank with multiple clicks,","cited_arxiv_id":null,"evidence_quote":"The closest single-agent DCM bandit algorithm; its termination-ranking requirement is the one the paper relaxes for small termination probabilities."},{"cited_title":"Online learning for coop- erative multi-player multi-armed bandits,","cited_arxiv_id":null,"evidence_quote":"Provides the cooperative multiplayer bandit framework, the MDSEE phased exploration scheme, and the lexicographic tie-break used for no-communication coordination."}],"review_version":1}