{"id":"91b812ee-6026-45c4-a0cb-4c34b9a4d662","arxiv_id":"2508.18841","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A contextual dueling bandit algorithm asks users to compare each new item against a past item for free, achieving O(sqrt(T)) regret after a short random exploration phase.","lead":"This paper proposes a new recommender-system model where a user compares each new recommendation with an item they consumed in the past, a comparison that costs no extra regret. The authors prove an O(sqrt(T)) regret bound for their algorithm and show in simulations that reusing old items for comparisons lowers regret versus comparing two fresh items.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's regret proof invokes Lemma 2 to bound Σ||x_t−y_t||_{V_t^{−1}}, but Lemma 2 as printed bounds Σ||x*_t−x_t||_{V_t^{−1}} and is even mis-indexed, leaving the central O(√T) step unproved.","rationale":"The reader's weakest-assumption analysis identified exactly the load-bearing gap: the proof step that controls Σ ||x_t−y_t||_{V_t^{−1}} cites a lemma that instead controls a different quantity and is not usable as written. My reading confirms this. The issue is internal to the proof, not a disagreement with the community consensus: the standard elliptical-potential lemma for the sequence z_t = x_t−y_t would almost certainly repair the proof, and the rest of the argument (regret decomposition, rich-history Lemma 3, confidence Lemma 1) is coherent. Thus the appropriate verdict is conditional, not rejection: the paper's main theorem needs a corrected Lemma 2 and a valid proof of the potential-sum bound before it can be considered established. The experiments are supportive but do not substitute for a complete proof of the stated guarantee. No ad hominem or theatrical framing is warranted; the flaw is a concrete proof gap with an identifiable repair path.","tokens_in":16946,"tokens_out":8701,"duration_ms":86978,"concrete_test":"Independently state and prove the elliptical-potential bound for ROAM's probing vectors: if z_t = x_t−y_t and V_{t+1} = V_t + z_t z_t^T, show Σ_{t=τ+1}^T ||z_t||_{V_t^{−1}} ≤ sqrt(2 d T log((trace(V_{τ+1}) + (T−τ)(2r)^2)/d)) (or the analogous bound with the correct constants). Then re-derive the regret bound of Theorem 1 using this lemma in place of the misstated Lemma 2. If the bound holds and the regret calculation goes through, the theorem is restored; if the bound fails or the indexing in V_t^{−1} is off by one, the central claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.2, the cumulative-regret proof reaches the bound R_T ≤ 2rτ + αβ Σ_{t=τ+1}^T ||x_t−y_t||_{V_t^{−1}} and then says this follows from Lemma 2. However, Lemma 2 as stated bounds Σ_{i=τ+1}^{t+τ} ||x*_t − x_t||_{V_t^{−1}}, not the probing-vector sum Σ ||x_t−y_t||_{V_t^{−1}}. The printed lemma is also internally inconsistent: the sum runs over i, yet the summand uses the outer variable t and the same t appears as the upper limit, so it cannot be applied as written. Since the entire O(√T) claim depends on controlling the sum of probing vectors, the main theorem is currently unverified. The gap is very likely repairable: ROAM updates V_{t+1} = V_t + (x_t−y_t)(x_t−y_t)^T, so the standard elliptical-potential lemma applies to z_t = x_t−y_t and yields Σ ||z_t||_{V_t^{−1}} ≤ √(2dT log(...)). But that standard lemma is neither stated nor proved in the paper, and the cited Lemma 2 does not supply it. This is a genuine missing step, not a matter of convention.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new 'history-constrained' contextual dueling bandit model. At each round the learner recommends one item x_t; after consumption, the user compares it with an item y_t chosen from the history of previously consumed items. Regret is charged only for x_t. The proposed algorithm ROAM first runs a pure exploration phase of length τ, then recommends greedily w.r.t. the current MLE and chooses y_t to maximize the norm ∥x_t−y∥_{V_t^{−1}}. The main theorem claims cumulative regret O((r/(κ√λmin(Σ))) d√T log(T/(dδ))) with probability at least 1−3δ, provided τ = O(r^2/λmin(Σ) log(d/δ)). The proof introduces a 'rich history' condition and proves via matrix concentration that a short exploration phase creates a rich history. Synthetic experiments compare ROAM with CoLSTIM.","tokens_in":17238,"tokens_out":12131,"duration_ms":116439,"significance":"The model is well motivated and the idea of recycling consumed items as comparison arms without extra regret is a genuinely useful twist on concurrent contextual dueling bandits. If the proof is repaired, the O(√T) regret guarantee has the right order, and the absence of an exploration-exploitation hyperparameter is a practical strength. The rich-history lemma and its matrix-concentration proof are the main technical novelty. However, the paper's central theorem is not established as printed: the bound on the probing-vector sum in §3.2 is attributed to a lemma that bounds a different quantity. This is repairable with a standard elliptical-potential bound, but the bound must be stated and proved explicitly.","major_comments":[{"comment":"The cumulative-regret proof reaches R_T ≤ 2rτ + αβ Σ_{t=τ+1}^T ∥x_t−y_t∥_{V_t^{-1}} and then says this follows from Lemma 2. Lemma 2 as printed bounds Σ_{i=τ+1}^{t+τ} ∥x_t^*−x_t∥_{V_t^{-1}}, not the probing-vector sum. The critical-ratio inequality has the form ∥x_t^*−x_t∥ ≤ β∥x_t−y_t∥, so it cannot be used to turn an upper bound on the former into an upper bound on the latter. The O(√T) conclusion therefore currently rests on an unproved bound. I expect the missing bound is the standard elliptical-potential lemma for z_t = x_t−y_t with V_{t+1}=V_t+z_t z_t^T; the authors should state and prove that lemma, or cite a precise statement of it, and use it in step (ii).","section":"Section 3.2, proof of Theorem 1, step (ii)"},{"comment":"Lemma 2 is not a well-formed mathematical statement. The summation is over i from τ+1 to t+τ, but the summand ∥x_t^*−x_t∥_{V_t^{-1}} does not depend on i and reuses the outer t; the right-hand side also depends on t. As printed, the lemma cannot be instantiated. Please restate it with correct indices and, if it is a known result, give a source that actually contains that statement.","section":"Lemma 2"},{"comment":"Lemma 3 asserts that after τ exploration rounds, H_t is 8r/√λmin(Σ)-rich for every t>τ. In the appendix, Lemma 9 proves the inequality for H_{2τ+1} (i.e., after 2τ rounds), using the pairs (x_{2t−1},x_{2t}), and the text says Lemma 3 follows by 'a change of notation from τ to 2τ.' This changes the exploration horizon in the statement of Lemma 3. Please make the correspondence explicit, e.g., by stating Lemma 3 for an exploration horizon 2τ with an adjusted universal constant, or by proving richness for H_{τ+1} directly.","section":"Lemma 3 and Appendix A.3 (Lemma 9)"}],"minor_comments":[{"comment":"The instruction 'Set y_t ← x_{t−1}' is undefined at t=1, since x_0 is not defined. Define an initialization (e.g., start comparisons at t=2) or specify x_0.","section":"Algorithm 1, line 5"},{"comment":"The text says the lemmas can be traced to 'the seminal work on linear bandits [3]', but reference [3] is Saha (2021), not a linear-bandit paper. Presumably [5] (Abbasi-Yadkori et al.) or [9] (Li et al.) is intended.","section":"Section 3, first paragraph after Lemma 2"},{"comment":"The proof states that z_t = x_{2t−1}−x_{2t} satisfies ∥z∥_2 ≤ r. Since each x has norm at most r, the difference has norm at most 2r. This does not change the asymptotic constants (C can be enlarged), but it should be corrected for rigor.","section":"Appendix A.3, proof of Lemma 9"},{"comment":"The sentence 'The default parameters used in the default important parameters' is garbled. Also, the comparison with CoLSTIM should state explicitly why charging ROAM one regret per round and CoLSTIM two regrets per round is fair, given that the models consume different numbers of items per round.","section":"Section 4, first paragraph and Figure 3"},{"comment":"The bound in Lemma 1 is stated with a free variable t in the logarithm; in the final theorem this becomes T. It would be clearer to state 'for all t ≤ T'.","section":"Lemma 1"}],"recommendation":"major_revision","confidential_remarks":"The contribution is incremental relative to [3,4] in terms of proof techniques, but the history-constrained model is new and practically motivated. The main proof gap is very likely fixable with a standard elliptical-potential lemma, so I would not reject. Please ask the authors to supply the missing lemma and to correct the Lemma 3 parameter mapping before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The model is the real contribution. Letting the algorithm recycle consumed items as free comparison arms is a sensible and underexplored idea, and the paper states it cleanly: history-constrained CDB, regret only on the fresh recommendation, and a rich-history condition that the algorithm can certify via a short random exploration phase. The matrix-concentration argument that a few dozen random recommendations suffice to make history rich is new and, as far as I can tell, sound. The simulations are simple but do what they claim: they show ROAM beats CoLSTIM when regret is counted per item presented, and they confirm the critical ratio stays small in practice. The writing is clear and honest about the model's limitations, including the practical cost of free queries.\n\nThe soft spot is exactly where the reader and stress-test put it. Theorem 1's proof needs a bound on the sum of ||x_t - y_t||_{V_t^{-1}}, but Lemma 2 as printed bounds the sum of ||x*_t - x_t||_{V_t^{-1}}, and it is also mis-indexed (sum over i, summand uses t). So the central step that yields the O(sqrt(T)) regret is unverified. This is a genuine gap in the proof as written, not a matter of convention. It is also very likely repairable: since V_t updates with (x_t-y_t)(x_t-y_t)^T, the standard elliptical-potential lemma directly bounds the probing-vector sum. I would bet the theorem is true and the fix is a few lines. But the paper as submitted does not contain those lines, so the main result is not yet established.\n\nOther issues are minor by comparison. There are small typos (Lemma 2 indexing, a stray \"t\" in the final bound). The extra 1/sqrt(lambda_min(Sigma)) factor is stated honestly as the cost of the asymmetric model. The experiments use only synthetic data, but for a theory paper that is fine. The related-work discussion is accurate: the concurrent CDB papers do not consider free reuse of history.\n\nThe right reader is a bandit theorist working on preference-based feedback or on exploration costs. I would bring this to a reading group despite the gap, because the model framing is worth discussing and the proof repair is a good exercise. If the authors fix Lemma 2 and the step around it, the paper becomes a solid extension of the CDB literature.\n\nRecommendation: send it to peer review, not a desk reject. A competent referee will catch the gap, and the contribution is strong enough to justify a revision round.","headline":"A genuinely new model for post-consumption preference elicitation with a likely-correct but not-yet-proven regret bound; the proof has a repairable gap in the key lemma application.","tokens_in":17814,"tokens_out":1532,"would_cite":true,"duration_ms":18164,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes a history-constrained dueling bandit model in which each new recommendation is compared against an item the user has already consumed, and proves that a greedy algorithm with a short random warm-up achieves O(√T) regret.","keywords":["contextual dueling bandits","recommender systems","regret bounds","explicit preference feedback","linear stochastic transitivity","matrix concentration","rich history","exploration-exploitation"],"falsifier":"Re-run the paper's simulation (d = 5, τ = 50, T = 1000) and record, for t > τ, the cumulative sum of the probing-vector norms ∥x_t − y_t∥_{V_t^{-1}}; if it grows faster than the Lemma 2 bound √(2dT log((4r²τ + T)/d)), or if the per-step inequality r_t ≤ αβ∥x_t − y_t∥_{V_t^{-1}} fails on a sizable fraction of steps, the O(√T) claim would be falsified. A direct mathematical check is to prove or disprove that ∑_{t>τ} ∥x_t − y_t∥_{V_t^{-1}} ≤ √(2dT log((4r²τ + T)/d)) under the rich-history and concentration conditions.","tokens_in":16757,"feed_emoji":"🔁","tokens_out":16288,"duration_ms":140358,"temperature":0.7,"pith_summary":"This paper proposes a new bandit model for recommender systems: each round the algorithm recommends one item, and after the user has consumed it, asks the user to compare it with an item already consumed in the past. Because the regret for the past item was already paid when it was consumed, the algorithm can use that comparison purely to learn, at no additional regret. The central claim is that a short random exploration phase—only Õ(d) rounds—suffices to accumulate a 'rich' history of consumed items, after which a simple greedy algorithm (ROAM) achieves O(√T) cumulative regret with high probability. If correct, this shows recommenders can exploit the explicit comparisons users give after consumption—generally more reliable feedback than implicit choices—while matching the regret order of the best simultaneous-comparison algorithms. Simulations on synthetic data confirm the effect, with ROAM outperforming the concurrent-dueling baseline across its tuned hyperparameters.","feed_headline":"Recycling past picks keeps recommender regret at O(√T)","feed_subtitle":"A short random warm-up fills the history with diverse items, so ROAM can query them as free comparison probes.","key_machinery":"The load-bearing object is the rich-history condition (Definition 1): a history H_t is β-rich if for every pair of items x, x′ and every positive definite matrix A, ∥x − x′∥_A ≤ β max_{y∈H_t} ∥x − y∥_A. This condition bounds the critical ratio — ∥x_t − x*_t∥_{V_t^{-1}} / ∥x_t − y_t∥_{V_t^{-1}} — by a constant, so the instantaneous regret at step t is dominated by β times the norm of the probing vector z_t = x_t − y_t, and the cumulative regret becomes a sum of probing-vector norms. Richness is established during the initial random exploration phase: the even-indexed differences x_{2t} − x_{2t−1} are i.i.d. and concentrate around Σ by a matrix concentration inequality, which yields both the β","core_discovery":"Central claim: comparing a new recommendation against an already-consumed item is provably efficient at no extra regret. The proof hinges on a condition called rich history: after O(r²/λ_min(Σ)·log(d/δ)) rounds of random recommendation, history items are diverse enough that any candidate pair is probed by some history item within a constant factor β = 8r/√λ_min(Σ). Once history is rich, ROAM recommends greedily against the current estimate θ̂_t and picks comparison item y_t maximizing ∥x_t − y∥_{V_t^{-1}}, a pure exploration query that costs no regret. Theorem 1 bounds cumulative regret by O((r/(κ√λ_min(Σ))) d√T log(T/(dδ))) with probability at least 1 − 3δ — the same √T order as simultaneou","pith_inferences":["The rich-history condition is a general separation principle: once past recommendations maintain directional diversity, the exploitation choice and the exploration query can be decoupled. The same idea should transfer to logistic-bandit and preference-alignment setups where comparisons against a fixed reference item are standard—a direction the paper only notes in passing.","The theory's β and τ are visibly conservative: simulations show the critical ratio sits far below 8r/√λ_min(Σ), and exploration beyond τ ≈ 10d only increases regret. A sharper analysis of the probing-vector sum would likely shrink both the stated τ and the final constant.","The free-comparison assumption is an idealization; a natural testable extension is to cap the number of comparisons per recommendation or restrict y_t to a sliding window of recent items, then measure how regret degrades as querying is rationed."],"forward_implications":["History-constrained comparisons reach cumulative regret of order O(√T) with high probability—the same order as the concurrent model—and the comparison item contributes nothing to the regret.","After the short exploration phase (τ ≈ O(d log(d/δ)) under standard parameter scaling), ROAM needs no exploration-exploitation hyperparameter: x_t is chosen greedily and y_t is chosen purely for exploration.","Reusing consumed items for comparisons can yield materially lower regret than comparing two fresh items per round, as the ROAM-versus-CoLSTIM simulations show for all tested hyperparameter values.","The O(√T) guarantee is achieved while placing the comparison query after consumption, matching how explicit feedback is actually elicited in recommender systems."],"supporting_citations":[{"why":"Defines the concurrent contextual dueling bandit model and contributes the proof skeleton ROAM follows, including the summation bound on recommendation-error norms that anchors the regret analysis.","marker":"[3]"},{"why":"Supplies the linear stochastic transitivity choice model used for the user's comparisons and the CoLSTIM algorithm that serves as the empirical baseline.","marker":"[4]"},{"why":"Provides the generalized linear bandit concentration bound (Lemma 1) that the proof uses to control the estimation error in the V_t norm.","marker":"[9]"},{"why":"Provides the matrix concentration inequality (Theorem 5.41) behind Lemma 4, from which the rich-history guarantee and the λ_min(V_{τ+1}) ≥ 1 condition are derived.","marker":"[23]"}],"fun_headline_variants":["Recycling history: free probes give O(√T) regret","Consumed items become free comparison probes regret O(√T)","Random warm-up builds rich history for regret-free probes","Past picks double as free probes to hold O(√T) regret","History diversity from random start makes probes costless"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The O(√T) guarantee rests on the assumption that the comparison vectors, summed over time, obey the same bound that is proven only for the recommendation-error vectors — the proof of Theorem 1 applies Lemma 2 to ∑∥x_t − y_t∥_{V_t^{-1}} although the lemma is stated for ∑∥x*_t − x_t∥_{V_t^{-1}}, without supplying the missing argument.","fun_headline_variants_meta":{"raw":{"variants":["Recycling history: free probes give O(√T) regret","Consumed items become free comparison probes regret O(√T)","Random warm-up builds rich history for regret-free probes","Past picks double as free probes to hold O(√T) regret","History diversity from random start makes probes costless"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001748,"raw_usage":{"total_tokens":6770,"prompt_tokens":800,"completion_tokens":5970,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":544,"completion_tokens_details":{"reasoning_tokens":5886}},"tokens_in":544,"tokens_out":5970,"duration_ms":46031,"temperature":1.0,"reasoning_tokens":5886,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T16:10:08.825205+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the paper's simulation (d = 5, τ = 50, T = 1000) and record, for t > τ, the cumulative sum of the probing-vector norms ∥x_t − y_t∥_{V_t^{-1}}; if it grows faster than the Lemma 2 bound √(2dT log((4r²τ + T)/d)), or if the per-step inequality r_t ≤ αβ∥x_t − y_t∥_{V_t^{-1}} fails on a sizable fraction of steps, the O(√T) claim would be falsified. A direct mathematical check is to prove or disprove that ∑_{t>τ} ∥x_t − y_t∥_{V_t^{-1}} ≤ √(2dT log((4r²τ + T)/d)) under the rich-history and concentration conditions.","supporting_citations":[{"cited_title":"Optimal algorithms for stochastic contextual preference bandits","cited_arxiv_id":null,"evidence_quote":"Defines the concurrent contextual dueling bandit model and contributes the proof skeleton ROAM follows, including the summation bound on recommendation-error norms that anchors the regret analysis."},{"cited_title":"Stochastic contextual dueling bandits under linear stochastic transitivity models","cited_arxiv_id":null,"evidence_quote":"Supplies the linear stochastic transitivity choice model used for the user's comparisons and the CoLSTIM algorithm that serves as the empirical baseline."},{"cited_title":"Provably optimal algorithms for generalized linear contextual bandits","cited_arxiv_id":null,"evidence_quote":"Provides the generalized linear bandit concentration bound (Lemma 1) that the proof uses to control the estimation error in the V_t norm."},{"cited_title":"Introduction to the non-asymptotic analysis of random matrices","cited_arxiv_id":null,"evidence_quote":"Provides the matrix concentration inequality (Theorem 5.41) behind Lemma 4, from which the rich-history guarantee and the λ_min(V_{τ+1}) ≥ 1 condition are derived."}],"review_version":1}