{"id":"6673b13c-cbed-4b01-b462-fff2db5d2794","arxiv_id":"2505.23720","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"COBRA combines contextual bandits with a VCG-inspired leave-one-out detection mechanism so that truthful reporting becomes an approximate equilibrium while regret stays sub-linear.","lead":"This paper proposes COBRA, an algorithm for contextual bandit problems where self-interested sellers or providers can lie about their quality to get chosen more often. It uses a leave-one-out detection rule to make lying unprofitable without payments, and claims sub-linear regret and approximate truthfulness guarantees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's NE proof drops an instance-dependent 1/Δmin factor when bounding suboptimal selections, so the claimed Õ(d√T)-NE is not established even in the all-truthful profile.","rationale":"The paper's central claim is that COBRA provides incentive compatibility without money. The reader rejected the paper on Assumption 1 and the unproven transfer of the all-truthful suboptimal-selection bound to the deviating case. My reading found a more basic gap: even in the all-truthful profile used to establish the approximate Nash equilibrium, the proof bounds the number of suboptimal rounds by a term containing 1/Δmin and then silently treats it as a constant. Under the stated assumptions nothing prevents Δmin from being tiny, so the bound is not Õ(d√T). Since the number of selections an agent can gain by deviating is bounded by the same flawed count, the incentive-compatibility guarantee fails at its foundation. This is not a disagreement with the consensus; it is an internal inconsistency in the derivation. A simple simulation with a small gap would reveal whether the count scales linearly; the analytic issue is clear from the inequality chain. I therefore agree with the REJECT verdict, though my weakest-assumption diagnosis differs from the reader's.","tokens_in":30031,"tokens_out":11769,"duration_ms":121166,"concrete_test":"Run COBRA on a two-agent truthful linear instance with a deliberately small gap: e.g., d=2, x1=(1,0), x2=(0,1), θ*=(0.5, 0.5+1/√T), for T=10^5. Record the total number of suboptimal selections Σ 1(a_t≠a*_t). If it scales roughly as T (or even T/log T) rather than Õ(√T), the bound in the proof of Theorem 2 fails. An analytic alternative: redo the derivation without dropping the explicit 1/Δmin; if the final inequality cannot be made uniform in the instance, the theorem statement must be revised to include a gap-dependent term.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing problem is in the proof of Theorem 2 (Appendix A.2.1). The proof bounds the number of suboptimal rounds by (2/Δmin)·α_T·√T·√(2d log(λ+TL/d)) and then equates this to Õ(d√T). But Δmin = min_{a_t≠a*_t}(θ⊤_* x*_{t,a*} − θ⊤_* x*_{t,a}) is an instance-dependent gap that can be as small as T^{-1/2} or smaller under the paper's own assumptions (bounded features, arbitrary θ*). The notation Õ cannot absorb 1/Δmin. Hence the derived inequality does not give a uniform sublinear bound on suboptimal selections; for small-gap instances the count of suboptimal rounds can be linear in T, so the guarantee S_T(a) ≥ S*_T(a) − Õ(d√T) is not proven. The same unsound count bound is then reused in the deviation step (Eq. 18 of the proof) to upper-bound the utility of a misreporting agent, so the unilateral-deviation NE claim inherits the flaw. This issue is independent of Assumption 1 and strikes at the paper's central incentive-compatibility result.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a linear (and, in appendices, non-linear) contextual bandit setting in which arms are strategic agents who may misreport their feature vectors to increase their probability of being selected. The authors propose LOOM, a VCG-inspired statistical test that compares a leave-one-out pessimistic reward estimate against an optimistic reward estimate, and COBRA, a UCB/TS-based algorithm that uses LOOM to eliminate detected over-reporters. The main theoretical claims are that when all agents report truthfully, COBRA has regret O~(d sqrt(T)) and truthfulness is an O~(d sqrt(T))-approximate Nash equilibrium (Theorem 2), and that under Assumption 1 every Nash equilibrium has strategic regret O~(d sqrt(T) + sqrt(NT)) (Theorem 3). The paper also reports simulations comparing COBRA with Lin-UCB, Lin-TS, and OptGTM on synthetic problem instances.","tokens_in":30226,"tokens_out":2654,"duration_ms":27995,"significance":"If the main claims were correct, the paper would make a meaningful contribution: it proposes a payment-free incentive-compatible mechanism for strategic contextual bandits, gives a VCG-inspired detection rule that uses other agents' reports rather than agent-specific baselines, and extends the analysis to LOOM-compatible non-linear bandit algorithms. The regret analysis under fully truthful reports follows a standard Lin-UCB argument, and the experimental section is careful about confidence intervals and varying problem instances. However, the central incentive-compatibility claim is not justified by the proof, and the flaw is not a presentation issue: it appears in the derivation of the approximate-NE guarantee, which is the paper's headline contribution. The paper also explicitly concedes in Appendix C that its own Assumption 1 may fail when multiple agents over-report, which further limits the scope of Theorem 3.","major_comments":[{"comment":"The proof of Theorem 2 bounds the number of suboptimal selections by (2/Delta_min) * alpha_T * sqrt(T) * sqrt(2d log(lambda + TL/d)) and then concludes that this is O~(d sqrt(T)). This step is invalid because Delta_min = min_{a_t != a*_t} (theta*^T x*_{t,a*} - theta*^T x*_{t,a}) is an instance-dependent gap that can be arbitrarily small under the paper's own assumptions of bounded features and arbitrary theta*. The notation O~ cannot absorb 1/Delta_min, and for small-gap instances the displayed bound is not sublinear in T. Since this bound is used to derive Eq. (16), the claimed lower bound S_T(a) >= S*_T(a) - O~(d sqrt(T)) in Eq. (17) is not established.","section":"Appendix A.2.1, Eq. (16)"},{"comment":"The unilateral-deviation step of Theorem 2 applies the all-truthful suboptimal-selection bound of Eq. (16) to an agent who misreports, without accounting for the fact that a deviating agent changes the selected arms, the covariance matrices V_t, the UCB values, and the LOOM elimination dynamics. The quantity sum_{t} 1(a_t != a*_t) is not invariant under a unilateral deviation, and no argument is given that the all-truthful bound controls it in the deviating profile. Consequently the upper bound S_T(a) <= S*_T(a) + O~(d sqrt(T)) in Eq. (19), and with it the approximate-NE claim of Theorem 2, is not proven.","section":"Appendix A.2.1, Eqs. (18)-(19)"},{"comment":"The proof of the NE part of Theorem 3 repeats the same Delta_min problem: after dividing by Delta_min, the bound on sum_t 1(a_t != a*_t) is stated as O~(d sqrt(T) + sqrt(NT)) without justifying that 1/Delta_min is a constant independent of the instance. Under the stated assumptions Delta_min can be as small as T^{-1/2} or smaller, so the displayed bound does not imply a sublinear approximate-NE guarantee. Since this is the only proof of the equilibrium claim for the general case, the conclusion that every sigma in NE(COBRA) satisfies the stated guarantee is not supported.","section":"Appendix A.2.2, Eq. (25)"},{"comment":"The paper states that when multiple agents over-report, all estimators used by COBRA become biased and theoretical guarantees are impossible without additional assumptions. Theorem 3, however, is asserted for every sigma in NE(COBRA), including profiles in which several agents over-report. Assumption 1 is stated as a sufficient condition, but the paper provides no evidence that Assumption 1 holds at any such equilibrium; indeed the appendix's own discussion suggests it may fail exactly there. This leaves the scope of Theorem 3 unclear and weakens the paper's claim that strategic regret is controlled under every Nash equilibrium.","section":"Appendix C, Case 3"}],"minor_comments":[{"comment":"The notation is inconsistent: A is used both for the set of arms and for the set of agents in Definition 2, and N is used for both the set of agents and its cardinality. Please disambiguate.","section":"Section 2, Definitions 1-3"},{"comment":"The pseudocode places the arm selection at Line 4, but the surrounding text refers to Line 5 for the same operation. Please align the text with the pseudocode numbering.","section":"Section 4, Algorithm 1"},{"comment":"The sentence introducing the Thompson Sampling variant says 'we also propose a TS-based variant, COBRA(UCB)', which appears to be a typo for COBRA(TS). Please correct it.","section":"Section 4, TS-based algorithm"},{"comment":"The description of the OptGTM baseline is very brief; please provide a short explanation of its parameters and how it is adapted to the reported setting, so that the experimental comparison is reproducible.","section":"Section 5"},{"comment":"The proof of Theorem 4 repeats the same Delta_min division as Theorem 2, so the non-linear NE claim inherits the same issue; even if the appendix is considered supplementary, this should be flagged in the main text.","section":"Appendix B, Theorem 4"}],"recommendation":"reject","confidential_remarks":"The paper addresses an interesting question and contains a standard Lin-UCB-type regret proof under truthful reporting, but the central approximate-NE claim rests on a specific algebraic error (dropping 1/Delta_min) and on an unjustified transfer of the all-truthful bound to unilateral deviators. These are load-bearing for the main contribution, so in my view the manuscript cannot be accepted in its current form. The Delta_min issue might be repaiable with a more careful instance-dependent analysis, but the deviation step would need a genuinely new argument, and the scope of Theorem 3 would need to be reconciled with the appendix's admission that multiple over-reporters break the estimators. I would not recommend a major revision unless the authors can supply those missing arguments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: COBRA's LOOM mechanism is a genuinely new detection principle for strategic misreporting in linear contextual bandits, and the honest-case regret analysis is standard but fine. The main claim that truthfulness is an Õ(d√T)-NE is not established as written. The proof bounds the number of suboptimal pulls by (2/Δmin)·Õ(d√T), then casually drops the 1/Δmin. Since Δmin can be as small as 1/√T or smaller under the paper's own assumptions, the bound does not give a uniform sublinear guarantee. The same flawed count is reused in Eq. (18) to bound a deviator's utility, so the unilateral-deviation claim inherits the problem. This is the load-bearing result, and the abstract's promise—incentive compatibility with sublinear regret and no money—is unsupported.\n\nCredit where due: the leave-one-out estimator built on other agents' reports is a VCG-style idea that is clearly different from Kleine Buening et al.'s agent-specific estimators and Hu-Duan's LP mechanism. The extension to non-linear rewards is a real addition, and the all-truthful regret bound in Theorem 2 is a textbook Lin-UCB argument that appears correct. The authors are also honest about limits: they state that under-reporting is not detected, and Appendix C concedes that when multiple agents over-report, all estimators become biased and Assumption 1 can fail. That last point undercuts Theorem 3, which holds only under an assumption the paper itself says is fragile. The deviation step in Theorem 2 also applies an all-truthful suboptimal-selection bound to a misreporting agent without accounting for the bias that misreporting introduces, so the transfer is not justified. Experiments are synthetic, run 20 times, with no code released; they are indicative but not decisive.\n\nWho is this for? Researchers working on strategic bandits and mechanism design without transfers will find the LOOM idea worth engaging. The paper deserves a serious referee—the mechanism is novel enough that the proof gap may be repairable, for instance by stating a gap-dependent approximate-NE guarantee or repairing the deviation argument. As it stands, the central theorem is not proven, so I would not accept the current version. But it is not a desk-reject; it is the kind of paper that should go to review with a clear request to fix the Δmin issue and the Assumption 1 burden.","headline":"A genuinely different leave-one-out detection idea for strategic contextual bandits, but the main incentive-compatibility theorem is not proven because the NE analysis drops an instance-dependent 1/Δmin factor.","tokens_in":30785,"tokens_out":2506,"would_cite":false,"duration_ms":24832,"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":"Truthful reporting becomes an approximate Nash equilibrium under a payment-free bandit algorithm, with sublinear regret.","keywords":["contextual bandits","strategic agents","incentive compatibility","approximate Nash equilibrium","misreporting detection","leave-one-out mechanism","UCB","Thompson sampling"],"falsifier":"Run COBRA with two or more agents who all over-report by a positive multiplicative factor on their feature vectors, keep those reports fixed across rounds, and check whether at any time the all-data upper confidence bound for an agent's reported feature falls below that agent's true expected reward; if such a violation occurs before LOOM removes the agents, Assumption 1 is violated and the observed regret can be compared directly against $\\widetilde{O}(d\\sqrt{T}+\\sqrt{NT})$.","tokens_in":29773,"feed_emoji":"🎯","tokens_out":9243,"duration_ms":79826,"temperature":0.7,"pith_summary":"This paper tries to establish that strategic misreporting in contextual bandits can be deterred without payments, using only a statistical test that compares an agent's reported features against everyone else's data. It proposes COBRA, which combines optimism-based arm selection with a leave-one-out check (LOOM) inspired by VCG pricing: an agent whose pessimistic reward estimate from the others' data exceeds the optimistic estimate from its own observed rewards is flagged as over-reporting and removed. The paper claims that when all agents report truthfully, truthfulness is a $\\widetilde{O}(d\\sqrt{T})$-Nash equilibrium and COBRA's regret is at most $\\widetilde{O}(d\\sqrt{T})$; under an additional comparability assumption the regret bound becomes $\\widetilde{O}(d\\sqrt{T}+\\sqrt{NT})$ for every Nash equilibrium. If correct, this gives platforms a way to make truthful product listings a near-best response without charging or paying agents.","feed_headline":"No-payment bandit makes truthful reporting a near-best response","feed_subtitle":"COBRA's leave-one-out checks keep regret sublinear when agents can over-report to win recommendations.","key_machinery":"The load-bearing object is the LOOM condition, $\\mathrm{LCB}^{(x)}_{t,a} > \\mathrm{UCB}^{(y)}_{t,a}$, which compares a pessimistic estimate of the agent's total expected reward, built from a leave-one-out estimate of the reward function using all other agents' data, to an optimistic estimate assembled from the noisy rewards actually observed when the agent was selected. This condition is what detects over-reporting and triggers elimination, and the paper's regret proofs reuse the same UCB and LCB confidence ellipsoids for both arm selection and detection.","core_discovery":"The central claim is that incentive compatibility in this strategic contextual bandit problem does not require transfers: a UCB-style learner can disincentivize over-reporting by making detection depend on the reports of other agents. Concretely, Theorem 2 says that under truthful reports, unilateral deviation cannot raise an agent's expected number of selections by more than $\\widetilde{O}(d\\sqrt{T})$, so truthful reporting is an approximate Nash equilibrium, and the same bound controls regret. Theorem 3 extends the regret guarantee to all Nash equilibria under Assumption 1, at the price of an extra $\\sqrt{NT}$ term that comes from agents exploiting the learner's early uncertainty. The paper also generalizes the argument to nonlinear reward functions for any LOOM-compatible contextual bandit algorithm, meaning one whose reward estimator admits confidence bounds for both the full data and the leave-one-out data, with the same qualitative guarantees.","pith_inferences":["Because the detector uses other agents' data, an individual agent cannot directly corrupt the baseline that judges it, suggesting protection against unilateral manipulation that per-agent history estimators may lack.","The $\\sqrt{NT}$ term points to many-agent coordination as the main scaling threat; a natural stress test is to run correlated over-reporting across a growing number of agents and watch whether the bound degrades.","The paper leaves under-reporting undetected, so a strategic agent might exploit features that lower true quality while still winning selections; a testable extension is to add a symmetric downward test and see whether the equilibrium and regret guarantees survive."],"forward_implications":["Platforms can deter inflated listings without payments, since the threat of removal from the recommendation pool plays the role that prices play in VCG mechanisms.","The sublinear regret guarantee means recommendations approach the best truthful arm over time even while agents may be gaming the learner.","The same leave-one-out test can wrap any optimistic contextual bandit algorithm, linear or nonlinear, as long as that algorithm supplies valid confidence bounds.","The theorems quantify the price of incentives: truthfulness is only approximate, and the all-equilibria regret bound carries an extra $\\sqrt{NT}$ term."],"supporting_citations":[{"why":"Supplies the confidence-ellipsoid theorem behind both the UCB selection rule and the LOOM leave-one-out bounds.","marker":"Abbasi-Yadkori et al., 2011"},{"why":"Provides the optimism-based linear contextual bandit rule that COBRA(UCB) builds on.","marker":"Li et al., 2010"},{"why":"Supplies the finite-time regret analysis used when all agents report truthfully.","marker":"Chu et al., 2011"},{"why":"Provides the Thompson-sampling estimator used by the COBRA(TS) variant.","marker":"Agrawal and Goyal, 2013"},{"why":"Closest strategic linear contextual bandit baseline; its agent-specific estimator is the contrast for LOOM and is compared in the experiments.","marker":"Kleine Buening et al., 2024"},{"why":"Classical VCG mechanism whose leave-one-out allocation logic motivates using other agents' reports to detect over-reporting.","marker":"Vickrey, 1961; Clarke, 1971; Groves, 1973"}],"fun_headline_variants":["Bandits without cash: truthful agents stay near-optimal","COBRA: no bribes, just sub-linear regret with honest agents","Strategic bandits tamed by peer-based checks, no payments","Truthful reporting emerges in bandit game without incentives","COBRA makes honesty a best response without paying agents"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 1, that in every round and for every agent the true expected reward of the reported features lies below the all-data UCB and the all-data UCB lies below the leave-one-out UCB, a comparability the paper admits can fail once several agents over-report and bias every estimator.","fun_headline_variants_meta":{"raw":{"variants":["Bandits without cash: truthful agents stay near-optimal","COBRA: no bribes, just sub-linear regret with honest agents","Strategic bandits tamed by peer-based checks, no payments","Truthful reporting emerges in bandit game without incentives","COBRA makes honesty a best response without paying agents"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000189,"raw_usage":{"total_tokens":1289,"prompt_tokens":855,"completion_tokens":434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":351}},"tokens_in":471,"tokens_out":434,"duration_ms":4283,"temperature":1.0,"reasoning_tokens":351,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T12:39:21.361309+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run COBRA with two or more agents who all over-report by a positive multiplicative factor on their feature vectors, keep those reports fixed across rounds, and check whether at any time the all-data upper confidence bound for an agent's reported feature falls below that agent's true expected reward; if such a violation occurs before LOOM removes the agents, Assumption 1 is violated and the observed regret can be compared directly against $\\widetilde{O}(d\\sqrt{T}+\\sqrt{NT})$.","supporting_citations":[{"cited_title":"Improved Algorithms for Linear Stochastic Bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the confidence-ellipsoid theorem behind both the UCB selection rule and the LOOM leave-one-out bounds."},{"cited_title":"Contextual Bandits with Linear Payoff Functions","cited_arxiv_id":null,"evidence_quote":"Supplies the finite-time regret analysis used when all agents report truthfully."},{"cited_title":"Thompson Sampling for Contextual Bandits with Linear Payoffs","cited_arxiv_id":null,"evidence_quote":"Provides the Thompson-sampling estimator used by the COBRA(TS) variant."},{"cited_title":"Strategic linear contextual bandits","cited_arxiv_id":null,"evidence_quote":"Closest strategic linear contextual bandit baseline; its agent-specific estimator is the contrast for LOOM and is compared in the experiments."},{"cited_title":"Counterspeculation, auctions, and competitive sealed tenders","cited_arxiv_id":null,"evidence_quote":"Classical VCG mechanism whose leave-one-out allocation logic motivates using other agents' reports to detect over-reporting."}],"review_version":1}