{"id":"ddc42aac-8657-4bc2-991c-f31be6aa27be","arxiv_id":"2606.20022","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Proposes SME-OFU algorithm for SLCB with bounded noise achieving O(log T) regret via set-membership estimation and OFU.","lead":"The paper proposes SME-OFU, an algorithm for stochastic linear contextual bandits that uses set-membership estimation and optimism under bounded reward noise to achieve O(log T) regret. A generalist might read it to see how tighter noise assumptions can yield substantially better theoretical performance than the standard sqrt(T) scaling.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"O(log T) regret claim contradicts Ω(√ T) lower bounds that apply to bounded noise instances","rationale":"The reader's weakest_assumption correctly flags the bounded-noise premise, but the load-bearing issue is not merely that the premise is stronger; it is that the stronger premise is still compatible with existing Ω(√ T) lower bounds, rendering the claimed O(log T) bound internally inconsistent with standard theory. Because the review was abstract-only, this contradiction was not surfaced.","tokens_in":1680,"tokens_out":410,"duration_ms":24608,"concrete_test":"Derive or locate the regret proof (likely Theorem 1 or 2) and check whether the cumulative regret sum contains a term linear in the number of rounds or only logarithmic; if the proof relies on the uncertainty set collapsing after O(1) samples per context, test the argument on a 1-dimensional instance with two alternating contexts and bounded uniform noise to see whether cumulative regret remains O(log T) or grows as Ω(√ T).","verdict_should_be":"REJECT","load_bearing_attack":"Known lower bounds for stochastic linear contextual bandits (e.g., Ω(√dT) from information-theoretic arguments) hold for sub-Gaussian noise and therefore also for the subclass of bounded noise (such as uniform[-c,c] noise, which remains sub-Gaussian). The set-membership estimation produces a polytope uncertainty set whose diameter shrinks only when sufficiently many distinct contexts have been observed; in the bandit setting this still requires Ω(√ T) exploration in the worst case to control the linear estimation error. The paper's statement that bounded noise is a \"stronger condition\" allowing O(log T) therefore does not evade the lower bound. No finite-action or deterministic-reward assumption is stated in the abstract that would remove the lower-bound obstacle.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes the SME-OFU algorithm for stochastic linear contextual bandits (SLCB) under the assumption of bounded reward noise. It uses set-membership estimation (SME) to form a polytope uncertainty set for the unknown parameter and applies the optimism-in-the-face-of-uncertainty (OFU) principle for action selection. The central claim is that this yields a regret bound of O(log T), which the authors argue does not contradict the standard \tilde{O}(\\sqrt{T}) bound because bounded noise is a strictly stronger assumption than sub-Gaussian noise; simulations are reported to show empirical gains over a sub-Gaussian benchmark.","tokens_in":1841,"tokens_out":480,"duration_ms":20728,"significance":"If the O(log T) regret bound were valid under the stated assumptions, the result would be significant: it would demonstrate that the bounded-noise condition can be leveraged for exponentially better regret than is possible under sub-Gaussian noise alone. The use of set-membership estimation to obtain a shrinking uncertainty set is a technically interesting idea that could have broader applicability if the analysis holds.","major_comments":[{"comment":"Abstract (main regret claim): The asserted O(log T) regret bound is inconsistent with standard information-theoretic lower bounds of \\Omega(\\sqrt{dT}) for stochastic linear contextual bandits. These lower bounds are proved for bounded noise distributions (e.g., uniform or Bernoulli) that remain sub-Gaussian; the manuscript does not state any additional assumption (finite action set, deterministic contexts, or deterministic rewards) that would remove the lower-bound obstacle.","section":"Abstract"},{"comment":"Abstract (set-membership argument): The claim that the SME polytope diameter shrinks sufficiently fast to yield only logarithmic regret requires that sufficiently many distinct contexts are observed; in the worst-case bandit setting this still necessitates \\Omega(\\sqrt{T}) exploration to control linear estimation error in d dimensions, contradicting the stated O(log T) bound.","section":"Abstract"}],"minor_comments":[{"comment":"The abstract states that bounded noise 'has not been leveraged explicitly before,' but does not cite or discuss prior works that already consider bounded rewards in linear bandits.","section":"Abstract"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful and constructive review. We address the two major comments point by point below, indicating the revisions we will make to the manuscript.","responses":[{"response":"We appreciate the referee for identifying this inconsistency. Standard information-theoretic lower bounds of Ω(√(dT)) for stochastic linear contextual bandits do apply to bounded noise distributions (such as uniform or Bernoulli) that are sub-Gaussian. Our O(log T) claim was obtained by leveraging the stronger bounded-noise assumption via set-membership estimation, but the manuscript does not explicitly list additional assumptions (e.g., finite action sets or deterministic contexts) that would evade the lower bound. We will revise the abstract, introduction, and theoretical sections to state the precise conditions required for the O(log T) bound and to discuss its relationship to existing lower bounds. If reconciliation is not possible, the claimed regret rate will be adjusted.","revision_made":"yes","referee_comment":"[Abstract] Abstract (main regret claim): The asserted O(log T) regret bound is inconsistent with standard information-theoretic lower bounds of Ω(√(dT)) for stochastic linear contextual bandits. These lower bounds are proved for bounded noise distributions (e.g., uniform or Bernoulli) that remain sub-Gaussian; the manuscript does not state any additional assumption (finite action set, deterministic contexts, or deterministic rewards) that would remove the lower-bound obstacle."},{"response":"We agree that the SME polytope diameter shrinks at a rate that depends on observing sufficiently many distinct contexts. Our analysis assumes that the realized context sequence permits the uncertainty set to contract sufficiently fast under bounded noise. In the worst-case (adversarial) context setting, Ω(√T) exploration may indeed be required to control estimation error. We will add a dedicated discussion of the required context diversity assumptions and provide a refined analysis of the polytope shrinkage rate. This will constitute a partial revision to the theoretical development and any related claims.","revision_made":"partial","referee_comment":"[Abstract] Abstract (set-membership argument): The claim that the SME polytope diameter shrinks sufficiently fast to yield only logarithmic regret requires that sufficiently many distinct contexts are observed; in the worst-case bandit setting this still necessitates Ω(√T) exploration to control linear estimation error in d dimensions, contradicting the stated O(log T) bound."}],"tokens_in":1383,"tokens_out":508,"duration_ms":29571,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main thing to know is that this paper claims an O(log T) regret bound for stochastic linear contextual bandits when reward noise is bounded, by running set-membership estimation inside an OFU algorithm. The abstract positions bounded noise as a stronger assumption than sub-Gaussian that has not been used explicitly before, and it reports simulation gains over a sub-Gaussian benchmark.\n\nThe new piece is the explicit use of SME to produce a polytope uncertainty set rather than the usual concentration ellipsoid. That is a concrete algorithmic choice tied to the bounded-noise model, and the simulations appear to test the right regime.\n\nThe soft spot is the regret bound itself. Information-theoretic lower bounds of Ω(√dT) for linear contextual bandits are derived from worst-case instances that include bounded noise (uniform on an interval remains sub-Gaussian). The set-membership polytope shrinks only after the algorithm has seen sufficiently diverse contexts; in the bandit setting that diversity still requires Ω(√T) exploration in the worst case to keep the uncertainty diameter small. The abstract's remark that the result does not contradict the sub-Gaussian bound because bounded noise is stronger does not remove the obstacle—the lower bound applies directly to the bounded case. No additional assumption (finite action set, deterministic rewards, or restricted context distribution) is stated that would sidestep this.\n\nThe work is aimed at researchers who design algorithms for contextual bandits under non-standard noise models. Someone already thinking about set-membership methods might find the SME-OFU construction worth looking at even if the rate does not hold. But the central claim has a load-bearing tension with established lower bounds, so the paper does not merit sending out for serious refereeing.","headline":"The O(log T) regret claim for bounded-noise SLCB collides with standard Ω(√T) lower bounds that still apply.","tokens_in":2292,"tokens_out":414,"would_cite":false,"duration_ms":19715,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"For stochastic linear contextual bandits with bounded reward noise, set-membership estimation plus optimism in the face of uncertainty yields an O(log T) regret bound.","keywords":["stochastic linear contextual bandits","bounded noise","set-membership estimation","optimism in the face of uncertainty","regret bounds","logarithmic regret"],"falsifier":"A concrete instance or simulation in which reward noise satisfies the boundedness assumption yet every algorithm, including SME-OFU, still incurs regret that grows faster than O(log T) would falsify the claimed improvement.","tokens_in":2582,"feed_emoji":"📉","tokens_out":639,"duration_ms":13013,"temperature":0.7,"pith_summary":"This paper shows that bounded reward noise, a stronger condition than the usual sub-Gaussian assumption, permits a new algorithm to achieve regret that grows only logarithmically with the horizon T. The approach constructs uncertainty sets for the unknown linear parameter via set-membership estimation and then selects optimistic actions inside those sets. Because the noise bound is used explicitly to shrink the feasible parameter region, the algorithm avoids the sqrt(T) scaling required under weaker noise models. Simulations confirm that the method outperforms standard algorithms designed for sub-Gaussian noise when the stronger bounded-noise condition holds.","feed_headline":"Bounded noise yields O(log T) regret for linear contextual bandits","feed_subtitle":"Set-membership estimation exploits the stronger condition to improve scaling over sub-Gaussian assumptions.","key_machinery":"Set-membership estimation constructs a compact uncertainty set for the unknown parameter that is guaranteed to contain the true value whenever noise remains within fixed bounds; this set supplies the optimistic estimates used for action selection.","core_discovery":"The authors introduce the SME-OFU algorithm that applies set-membership estimation to form a bounded uncertainty set containing the true parameter vector consistent with all past observations under bounded noise. Optimism in the face of uncertainty is then invoked by choosing, at each step, the action that maximizes the reward under the most favorable parameter inside this set, producing a cumulative regret of O(log T).","pith_inferences":["The same set-membership construction may transfer to other sequential decision problems whose disturbances admit hard bounds.","Logarithmic regret opens the possibility of stable performance over much longer time horizons than sqrt(T) scaling would allow.","The result underscores that matching the noise assumption precisely to the problem data can change the fundamental scaling of regret."],"forward_implications":["Regret scales logarithmically rather than as sqrt(T) when the bounded-noise condition holds.","The algorithm can be applied directly in domains where realized rewards are naturally bounded.","Tighter uncertainty quantification from bounded noise produces fewer suboptimal pulls over long horizons.","Empirical results already show lower cumulative regret than sub-Gaussian baselines under the same bounded-noise setting."],"fun_headline_variants":["Set-membership estimation yields O(log T) regret for bounded-noise bandits","SME-OFU secures O(log T) regret in linear contextual bandits with bounded noise","Bounded noise enables O(log T) regret via set-membership in contextual bandits","O(log T) regret for stochastic linear bandits using set-membership estimation","Set-membership approach achieves O(log T) regret under bounded reward noise"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The difference between each observed reward and its conditional expectation is confined within fixed finite bounds for all time steps.","fun_headline_variants_meta":{"raw":{"variants":["Set-membership estimation yields O(log T) regret for bounded-noise bandits","SME-OFU secures O(log T) regret in linear contextual bandits with bounded noise","Bounded noise enables O(log T) regret via set-membership in contextual bandits","O(log T) regret for stochastic linear bandits using set-membership estimation","Set-membership approach achieves O(log T) regret under bounded reward noise"]},"model":"grok-4.3","cost_usd":0.003549,"raw_usage":{"total_tokens":1843,"prompt_tokens":632,"num_sources_used":0,"completion_tokens":91,"cost_in_usd_ticks":35487000,"prompt_tokens_details":{"text_tokens":632,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1120,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":632,"tokens_out":91,"duration_ms":5903,"temperature":1.0,"reasoning_tokens":1120,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T15:40:47.565261+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete instance or simulation in which reward noise satisfies the boundedness assumption yet every algorithm, including SME-OFU, still incurs regret that grows faster than O(log T) would falsify the claimed improvement.","supporting_citations":[],"review_version":1}