{"id":"502c4547-c297-4609-8737-92744683f806","arxiv_id":"2606.31449","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Limited-adaptivity slate GLM bandit algorithms achieve the same regret as a fully adaptive algorithm, up to constants, under a diversity assumption.","lead":"The paper presents two algorithms for slate bandits—one that updates its policy once per few batches and one that rarely switches—and proves both match the regret of a fully adaptive algorithm. If the guarantees hold, online recommendation and ad systems can cut update frequency and parallelize rounds with little loss.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Key eigenvalue lower bound relies on a false generalized martingale lemma and on applying the diversity assumption to scaled, non-adapted vectors.","rationale":"The paper's central claim is that both limited-adaptivity algorithms achieve κ-free regret under Assumption 2.1. The proof chain depends on the design matrices' eigenvalues growing linearly at rate ρ (Lemmas A.12, C.9, D.1). I identified a concrete internal inconsistency in that chain: the generalized matrix martingale lemma D.1 drops the α factor from the covariance lower bound, and Lemma A.12 applies the diversity assumption to scaled vectors whose scaling factor is not adapted to the filtration. The reader's weakest assumption correctly flags Assumption 2.1 as unenforced, but the more load-bearing issue is that even granting Assumption 2.1, the proof does not establish the eigenvalue lower bound it relies on. This is not merely a disagreement with prior work or a missing empirical detail; it is a mathematical gap in the central argument. The algorithms and experiments are plausible and the paper is clearly written, but the stated regret guarantees are not supported by the provided proofs. A revision that corrects Lemma D.1 and either proves the scaled-vector covariance bound or states a stronger assumption could change this verdict; as written, the central claim should not be accepted.","tokens_in":49508,"tokens_out":10494,"duration_ms":95839,"concrete_test":"Re-derive Lemma D.1 for α=1/2 with x_s = ±(1/√2)e_1: the stated bound λ_min(Q_t) ≥ γ + cρt fails; the correct bound is γ + cαρt. Then trace this α through Lemma A.12: replace the claimed lower bound E[\\bar{x}_t^i(\\bar{x}_t^i)^T | F_{t-1}] ⪰ ρ κ^{-1} β_t^{-1} I by the only justified bound (using β_t ≤ e^{2S}) ρ κ^{-1} e^{-2S} I, and recompute the threshold T(H) and Lemma A.9. If the resulting regret acquires a κ e^{2S} factor or a slower eigenvalue growth rate, the claimed κ-free O(Nd^{3/2}√T) bound is not supported.","verdict_should_be":"REJECT","load_bearing_attack":"Assumption 2.1 is stated for the algorithm's original selected items x_t^i, but the proof of the central eigenvalue lower bound applies it to the scaled vectors \\bar{x}_t^i = sqrt( ˙µ(b_t^T θ0)/β_t) x_t^i. In Lemma A.12 (and C.9) the authors write E[\\bar{x}_t^i \\bar{x}_t^i^T | F_{t-1}] = E[ ˙µ(b_t^T θ0) β_t^{-1} x_t^i x_t^i^T | F_{t-1}] ⪰ ρ κ^{-1} β_t^{-1} I. The equality is definitional, but the inequality requires controlling a random, non-F_{t-1}-measurable scaling factor inside the conditional expectation. Since b_t is chosen from the current, not yet observed item set X_t^i, β_t is not F_{t-1}-measurable; the diversity assumption on x_t^i alone does not give the claimed lower bound. More seriously, the generalized Lemma D.1 is false as stated: from E[x_s x_s^T | F_{s-1}] ⪰ αρ I with α∈(0,1], its proof concludes λ_min(Q_t) ≥ γ + cρt, but the correct conclusion is γ + cαρt (already for x_s = ±√α e_1). Thus the linear eigenvalue growth used in Lemmas A.12, C.9, and D.1 is not established. Without it, the multiplicative equivalence diag(H^i) ≃ H and the regret bounds in Theorems 3.1 and 4.1 collapse, and the claimed κ-independence is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies contextual slate bandits with generalized linear model (GLM) rewards under two limited-adaptivity regimes. It proposes B-SlateGLinCB, which operates in O(log log T) batches, and RS-SlateGLinCB, which makes only O(Nd log T) parameter updates. Under a diversity assumption on the selected items (Assumption 2.1), the paper claims regret bounds of tilde-O(N d^{3/2} sqrt(T E[\\dot{\\mu}(x_*^T \\theta_*)])) for the batched algorithm and tilde-O(R sqrt(T) + R S^{1/2} N d sqrt(sum_t \\dot{\\mu}(x_{t,*}^T \\theta_*))) for the rarely-switching algorithm, both with leading terms independent of the nonlinearity parameter kappa. The algorithms select slotted items independently to avoid exponential slate enumeration, and the paper includes synthetic experiments, a prompt-tuning application, and an empirical check of eigenvalue growth.","tokens_in":49878,"tokens_out":11083,"duration_ms":99392,"significance":"If the theoretical results were correct, they would be a valuable advance: they would bring the limited-adaptivity toolkit to slate bandits with GLM feedback, achieve computationally efficient poly(N) per-round selection, and match the regret of the fully adaptive Slate-GLM-OFU while removing the kappa-dependence that afflicts many GLM bandit bounds. The algorithmic ideas are reasonable and the empirical comparisons are suggestive. However, the central proof mechanism—linear growth of eigenvalues of the scaled design matrices—rests on a false generalization of a martingale lemma, and the diversity assumption is not shown to hold for the algorithms' own selection rules. The main theoretical claims are therefore not established in this version.","major_comments":[{"comment":"Lemma D.1 is false as stated. In the proof, after obtaining |sum x_s x_s^T - t Sigma_C| <= (1-c)rho t, the text concludes lambda_min(sum x_s x_s^T) >= t lambda_min(Sigma_C) - (1-c)rho t >= alpha rho t - (1-c)rho t >= c rho t. The last inequality would require alpha >= 1, but the lemma allows alpha in (0,1]. The correct conclusion is lambda_min >= gamma + (alpha+c-1)rho t, which may be negative and is at best gamma + c' alpha rho t. This is not a minor slip: Lemmas A.12, A.13, C.9, and C.10 apply this lemma with alpha = kappa^{-1} beta_t^{-1} (or kappa^{-1} e^{-1}) and rely on the claimed linear rate lambda + rho |T|/2. Without that rate, the multiplicative equivalence and the norm bound ||x||_{H^{-1}} <= 2 sum ||x^i||_{(H^i)^{-1}} fail, and with them the regret bounds in Theorems 3.1 and 4.1.","section":"Appendix D, Lemma D.1"},{"comment":"Assumption 2.1 is stated as though the algorithm guarantees diversity of the selected items, but no such guarantee is proved. In B-SlateGLinCB (Algorithm 1, Step 22) the item x_t^i is sampled from a G-optimal design on X_t^i; the distribution pi_G(X_t^i) generally has nonzero mean, so E[x_t^i | F_{t-1}] = 0 need not hold. In RS-SlateGLinCB (Algorithm 2, Step 5/17) the selection is deterministic given X_t^i and the current matrices, again with no reason to be conditionally zero-mean. Since the regret proofs invoke Assumption 2.1 for the algorithm's own sequence, the results apply only to a special class of environment selections that is not characterized. The paper should either prove the assumption for its algorithms under explicit conditions on D^i, or restate it as a separate structural condition and check it for the item-set distributions used in the experiments.","section":"Section 2.5, Assumption 2.1"},{"comment":"The application of the diversity assumption to the scaled vectors is not justified. The scaled vector is \\bar{x}_t^i = sqrt(\\dot{\\mu}(b_t^T \\hat{\\theta}_0)/\\beta_t) x_t^i, where b_t and \\beta_t depend on the current item set X_t^i and are not measurable with respect to F_{t-1}. The displayed inequality E[\\bar{x}_t^i \\bar{x}_t^i^T | F_{t-1}] = E[\\dot{\\mu}(b_t^T \\hat{\\theta}_0)\\beta_t^{-1} x_t^i x_t^i^T | F_{t-1}] \\succeq \\rho \\kappa^{-1} \\beta_t^{-1} I treats \\beta_t as a fixed constant; in reality the best deterministic bound is \\beta_t \\le e^{2S}, yielding an exponentially small \\alpha = \\kappa^{-1} e^{-2S}. Combined with the error in Lemma D.1, this reintroduces the kappa-dependence that the paper claims to eliminate, so the kappa-free statement is unsupported.","section":"Appendix A.5, Lemma A.12"}],"minor_comments":[{"comment":"The experimental figures report averages over 25 seeds but no error bars or confidence intervals, making it hard to assess the statistical significance of the comparisons, especially when the claimed advantage over baselines is modest.","section":"Section 5"},{"comment":"The notation section defines lambda = O(R sqrt(NdS log(ST/delta^-1))), while Algorithm 2 initializes lambda = O(NdR^2 S^{-1} log(T delta^-1)). These are inconsistent; the correct value used in the proofs should be stated clearly.","section":"Appendix C.1 vs Algorithm 2"},{"comment":"Several small presentation issues: 'Kiefer-Wolfowitz' is misspelled 'Keifer-Wolfowitz' in Section 2.7; 'Cauchy-Schwartz' appears in Appendix B instead of 'Cauchy-Schwarz'; reference [KRS] lacks a venue/year; and the proof of Lemma A.8 relies on 'Claim A.8 from [SDBS24]' without restating it, which hinders verification.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The paper's main claims are interesting and the algorithmic framework is appealing, but the central technical lemma (D.1) is demonstrably false for the parameter range it is used in, and the diversity assumption is not shown to hold for the algorithms' selections. These are load-bearing errors: patching them would either require a substantially different proof strategy or would reintroduce kappa-dependence, changing the paper's main selling point. The manuscript also leans heavily on lemmas from co-authored prior work [GS25, SDBS24]; that reliance is not itself disqualifying, but it makes independent verification of the imported lemmas especially important, and the generalization of the eigenvalue lemma in Appendix D is where the proof breaks."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Both algorithms are new and the scaling-slate construction is a genuinely clever move: it controls the ratio μdot(b_t^T θ0)/μdot(x_t^T θ0) without paying a κ factor, and the slot-level elimination keeps the per-round time polynomial in N. The distributional-design variant in Appendix B is also new, and the prompt-tuning application is a nice bonus. So there is real content here.\n\nThe soft spot is in the proofs of linear eigenvalue growth. Lemma D.1 claims that from E[x_s x_s^T | F_{s-1}] ⪰ αρ I (α∈(0,1]) one gets λ_min(Q_t) ≥ γ + cρt. That is algebraically false. Weyl's inequality gives λ_min(Q_t) ≥ γ + αρt − (1−c)ρt = γ + (α−1+c)ρt, so the slope is essentially αρ, not ρ. The paper simply drops α at the last step. This is load-bearing: Lemma D.1 is used in Lemmas A.12 and C.9 to show the slot design matrices have eigenvalues growing as λ + ρt/2, and that is the basis for the multiplicative equivalence between diag(H^i) and H. Without the ρ growth, the cross-block norm bounds fail, and the κ-free regret guarantees in Theorems 3.1 and 4.1 are unsupported.\n\nThere is also a measurability issue in the same place. The scaled vectors x̄_t^i = sqrt(μdot(b_t^T θ0)/β_t) x_t^i are used with Assumption 2.1, but the scaling factor depends on b_t, which is chosen from the current item sets and is not F_{t-1}-measurable. So the step E[x̄_t^i x̄_t^i^T | F_{t-1}] = ... is not justified. And even the diversity assumption itself is stated as something the algorithm must ensure, but neither algorithm enforces it. The reader is right to flag that.\n\nThe experiments lack error bars and code, but the regret curves are plausible and the empirical comparison to the fully adaptive baseline is useful. None of this is a takedown of the algorithms themselves; the scaling-slate idea may be salvageable with a different proof technique. But as written, the main theorems are not proved.\n\nThis paper is for researchers working on slate bandits with limited adaptivity and on GLM bandits generally. They would benefit from seeing the algorithm design, but they should not cite the regret bounds yet.\n\nI would engage with this as a referee: the topic is important, the flaw is specific, and a serious referee report could help the authors either fix Lemma D.1 and the measurability gap or substantially weaken their claims. Send it to peer review, but expect major revision.","headline":"New algorithms and a clever scaling-slate trick, but the central eigenvalue-growth lemma is false and the κ-free regret bounds are not established as written.","tokens_in":50347,"tokens_out":8790,"would_cite":false,"duration_ms":70408,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Contextual slate bandits with GLM rewards can match fully adaptive regret using only O(log log T) or O(Nd log T) policy updates, under a diversity condition.","keywords":["slate bandits","generalized linear bandits","limited adaptivity","batched bandits","rarely-switching bandits","regret bounds","G-optimal design","bandit feedback"],"falsifier":"Run B-SlateGLinCB or RS-SlateGLinCB on item distributions with zero conditional mean but rank-deficient or anisotropic conditional covariance—for example, every item in one slot lies in a fixed low-dimensional subspace—and record the minimum eigenvalue of each slot's H_i at every batch or update. The proof requires λ_min(H_i) ≥ λ + (ρ/2)t after t rounds; if growth flattens below that slope, the diversity assumption is violated and the regret bounds no longer apply. A simpler check: construct a distribution with nonzero conditional mean, which already breaks the zero-mean half of Assumption 2.1","tokens_in":49407,"feed_emoji":"🎯","tokens_out":8786,"duration_ms":87555,"temperature":0.7,"pith_summary":"The paper studies the contextual slate bandit problem with generalized linear rewards—at each round the learner picks one item per slot to form a slate and sees a single scalar reward—under two forms of limited adaptivity. The main claim is that the usual price of limited adaptivity largely disappears: a batched algorithm that changes policy only O(log log T) times achieves regret Õ(RS N d^{3/2} sqrt(T E[μ'(x_*^T θ*)])), and a rarely-switching algorithm that refits parameters only O(Nd log T) times achieves regret Õ(R sqrt(T) + R S^{1/2} N d sqrt(Σ_t μ'(x_{t,*}^T θ*))). Both match, up to constants, the regret of a fully adaptive algorithm, and neither has the non-linearity parameter κ in its leading term. Because items are selected slot-by-slot via G-optimal designs, per-round computation is polynomial in N even though the slate space is exponential. If these results hold, practitioners can parallelize rounds and reduce parameter refits without sacrificing asymptotic regret.","feed_headline":"Fewer updates match fully adaptive regret for slate GLM bandits","feed_subtitle":"Only O(log log T) batches or O(Nd log T) parameter refits keep regret at Õ(√T), with no non-linearity penalty.","key_machinery":"The load-bearing construction is the slot-level scaled design matrix H_i = λI + Σ_t ˙μ(b_t^T θ̂_0) β_t^{-1} x_t^i (x_t^i)^T, where b_t is the 'scaling slate'—the item in each slot with largest norm under the warm-up inverse design matrix—and β_t is an exponential self-concordance normalizer. This matrix plays two roles: it upper and lower bounds the full slate-level design and the Hessian of the GLM log-likelihood, so the MLE confidence ellipsoid transfers from Nd dimensions to per-slot d dimensions; and the scaling-slate ratio ˙μ(b_t^T θ̂_0)/˙μ(x_t^T θ̂_0) is O(1), which cancels the κ factor that normally appears in GLM regret. Around this, the algorithms use G-optimal designs—probability d","core_discovery":"The central claim is that in the slate GLM bandit setting, limited adaptivity is compatible with state-of-the-art regret. Under a diversity assumption on the item sequences, B-SlateGLinCB partitions the horizon into O(log log T) batches and attains regret Õ(RS N d^{3/2} sqrt(T E_{X~D} μ'(x_*^T θ*))), while RS-SlateGLinCB makes only O(Nd log T) adaptive parameter updates and attains regret Õ(R sqrt(T) + R S^{1/2} N d sqrt(Σ_t μ'(x_{t,*}^T θ*))). Both bounds match the rate of the fully adaptive slate GLM algorithm and, crucially, have leading terms free of κ—the instance-dependent non-linearity parameter that can be exponential in the parameter norm in ordinary GLM bandit bounds. The authors e","pith_inferences":["One testable extension is to replace the diversity assumption with a forced-exploration mechanism: if the algorithm actively samples items covering low-eigenvalue directions, the eigenvalue-growth lemmas could be proven rather than assumed, broadening applicability.","The same scaling-slate trick—using a worst-case normalizing item to bound the link-function ratio—may transfer to other structured bandits with GLM rewards, such as multi-slot ranking or assortment problems, and would likely remove κ from their leading regret terms.","The empirical advantage of pruning only against the most recent batch (B-SlateGLinCB+) suggests that multi-batch elimination is conservative; a regret proof for that variant could yield both faster algorithms and tighter constants.","Because the bounds depend on E[μ'(x_*^T θ*)] at the optimal slate, the algorithms may adapt to easy instances automatically; an experiment varying the separability of the optimal slate could test whether this instance-dependence is real or an artifact of the analysis."],"forward_implications":["Batched deployment becomes practical: only O(log log T) policy updates give regret Õ(N d^{3/2} sqrt(T)), and rounds within a batch can run in parallel.","Rarely-switching deployment cuts optimization cost: O(Nd log T) parameter refits give regret Õ(N d sqrt(T)), matching a fully adaptive policy that updates every round.","The κ-free leading term removes an exponential-in-S penalty that typically appears in GLM bandit bounds, so the guarantees remain meaningful for strongly nonlinear reward links.","Slot-wise G-optimal sampling keeps per-round time polynomial in N despite an action space of size 2^{Ω(N)} slates.","The paper's heuristic variant B-SlateGLinCB+ matches the fully adaptive baseline empirically on prompt exemplar selection; proving its bounds would give the practical version a theorem as well."],"fun_headline_variants":["O(log log T) batches match fully adaptive slate GLM regret","Slate GLM bandits: limited adaptivity, no κ regret penalty","Rarely-switching slate GLM bandits match fully adaptive regret","No κ penalty: slate GLM bandits with rare updates hit √T regret"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is the diversity assumption (Assumption 2.1): for each slot, the item actually selected, conditioned on past rounds, must have zero mean and covariance at least ρI in every direction; the paper does not prove that G-optimal sampling enforces this. If the environment violates it, the linear-eigenvalue-growth lemmas fail and both regret bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["O(log log T) batches match fully adaptive slate GLM regret","Slate GLM bandits: limited adaptivity, no κ regret penalty","Rarely-switching slate GLM bandits match fully adaptive regret","No κ penalty: slate GLM bandits with rare updates hit √T regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001392,"raw_usage":{"total_tokens":5557,"prompt_tokens":919,"completion_tokens":4638,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":663,"completion_tokens_details":{"reasoning_tokens":4557}},"tokens_in":663,"tokens_out":4638,"duration_ms":32374,"temperature":1.0,"reasoning_tokens":4557,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T04:32:07.182340+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run B-SlateGLinCB or RS-SlateGLinCB on item distributions with zero conditional mean but rank-deficient or anisotropic conditional covariance—for example, every item in one slot lies in a fixed low-dimensional subspace—and record the minimum eigenvalue of each slot's H_i at every batch or update. The proof requires λ_min(H_i) ≥ λ + (ρ/2)t after t rounds; if growth flattens below that slope, the diversity assumption is violated and the regret bounds no longer apply. A simpler check: construct a distribution with nonzero conditional mean, which already breaks the zero-mean half of Assumption 2.1","supporting_citations":[],"review_version":2}