{"id":"64724ebf-a8f1-489d-b1ed-6ca03f8de5fe","arxiv_id":"2607.02150","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Establishes Ω((log T)^2) lower bound on regret for multi-secretary problem with gapped distributions via Bellman certificates, showing prior O((log T)^2) upper bounds are tight.","lead":"This paper proves that the additive regret in the multi-secretary problem is at least Ω((log T)^2) for mixtures of separated uniform distributions with support gaps. A smart generalist might read it to understand fundamental limits on how well online policies can approximate offline optimal rewards in resource allocation.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's UNVERDICTED status stems from abstract-only access; the full manuscript supplies an explicit certificate construction whose validity can be checked directly. The modeling assumptions (bounded densities, support gaps, additive regret vs. offline prophet) are standard and match the setting in which the O((log T)^2) upper bounds were previously proved, so they do not constitute a load-bearing weakness for the lower-bound claim.","tokens_in":1678,"tokens_out":297,"duration_ms":17285,"concrete_test":"Extract the explicit Bellman certificate (value-function approximation and dual variables) constructed for the two-uniform mixture in the main theorem; substitute into the relaxed Bellman inequalities and verify that feasibility holds while the implied regret gap is at least c (log T)^2 for some c>0 and all large T.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a matching lower bound of Ω((log T)^2) for the specific instance of two separated uniform distributions at critical capacity, obtained via an explicit Bellman certificate that is feasible for the relaxation of the exact recursion. The framework is presented as directly converting such a certificate into a regret lower bound, with the construction specialized to bounded-density gapped supports. No internal inconsistency appears in the argument structure or in the stated relationship between the certificate and the additive regret relative to the offline prophet.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves that the optimal additive regret in the multi-secretary problem is Ω((log T)^2) for a mixture of two separated uniform distributions at critical capacity. This is obtained by constructing an explicit Bellman certificate that is feasible for a relaxation of the exact Bellman recursion; the same framework yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges (appendix). The result shows that existing O((log T)^2) upper bounds for bounded-density gapped instances are tight even in the one-resource case.","tokens_in":1777,"tokens_out":348,"duration_ms":23695,"significance":"If the certificate construction is valid, the result is significant: it closes the gap between upper and lower bounds for the gapped case, confirming that support gaps force the extra logarithmic factor relative to connected-support distributions. The Bellman-certificate framework is a clear strength—it converts the lower-bound argument into an explicit, verifiable object rather than an information-theoretic or minimax argument—and the paper directly matches the cited upper bounds for this canonical instance.","major_comments":[],"minor_comments":[{"comment":"The abstract states that the certificate 'converts lower bounds into explicit certificate constructions'; a short paragraph in the introduction summarizing the key algebraic steps of the construction (without full proof) would help readers assess feasibility before reaching the technical sections.","section":null},{"comment":"Notation for the 'critical capacity' parameter should be introduced with an explicit formula (e.g., as a function of the two uniform supports) the first time it appears, rather than only in the instance definition.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and positive assessment of the paper. The report accurately summarizes our contribution in establishing matching Ω((log T)^2) lower bounds for the multi-secretary problem under gapped distributions using explicit Bellman certificates, confirming the tightness of existing upper bounds even in the single-resource case.","responses":[],"tokens_in":1253,"tokens_out":82,"duration_ms":15824,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The key point here is that the paper settles an open question by proving a matching lower bound of Ω((log T)^2) regret for the multi-secretary problem under bounded-density distributions with support gaps. It does this for the concrete case of a mixture of two separated uniform distributions at critical capacity, and the same certificate method also covers a companion case where densities vanish near the edges.\n\nThe new element is the explicit construction of a feasible solution to the relaxed Bellman recursion that directly translates into the regret lower bound. This framework avoids circularity with the existing upper bounds and explains why gaps permit the larger regret while connected supports stay at O(log T). The abstract and stress-test description indicate the argument is self-contained and the certificate is built independently of the cited O((log T)^2) upper bounds.\n\nThe work is solid on its own terms for this specialization. It cleanly converts the certificate into an additive regret statement relative to the offline prophet, and the choice of the two-uniform mixture at the critical point looks deliberate to hit the threshold where the extra log appears. The appendix extension broadens the result without changing the core technique.\n\nThe main limitation is that the tight bound is shown for specific gapped instances rather than all gapped distributions at once. That is not a flaw given the claim, but it means the result is a sharp clarification for the simplest case rather than a sweeping characterization. No load-bearing gaps or fitting issues are visible in the stated argument structure.\n\nThis is aimed at people working on online algorithms and dynamic programming for resource allocation. Anyone tracking regret bounds in prophet inequalities or network revenue management will find the tightness result useful. The paper deserves a serious referee because the question it answers was explicitly open and the certificate approach looks reproducible enough to check.","headline":"The paper gives the first explicit Ω((log T)^2) lower bound for gapped multi-secretary instances via Bellman certificates, showing the extra log factor in prior upper bounds is necessary.","tokens_in":2204,"tokens_out":444,"would_cite":true,"duration_ms":13544,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"For mixtures of two separated uniforms at critical capacity, the multi-secretary problem requires Omega((log T)^2) additive regret.","keywords":["multi-secretary problem","additive regret","support gaps","Bellman certificates","lower bounds","online algorithms","prophet inequalities"],"falsifier":"An explicit computation of the optimal online policy's expected regret for the two-uniform mixture instance at sufficiently large T that yields o((log T)^2) would disprove the lower bound.","tokens_in":2581,"feed_emoji":"","tokens_out":430,"duration_ms":13688,"temperature":0.7,"pith_summary":"The paper shows that the extra logarithmic factor in regret upper bounds for the multi-secretary problem is necessary when value distributions have gaps in their support. It constructs an explicit lower bound of order (log T)^2 for the optimal online policy versus the offline prophet benchmark, using a mixture of two separated uniform distributions at the critical capacity. This matches known O((log T)^2) upper bounds and proves them tight even in the one-resource case. The argument relies on Bellman certificates as feasible solutions to a relaxed version of the dynamic programming recursion.","feed_headline":"Multi-secretary regret lower bound hits (log T)^2 for gapped uniforms","feed_subtitle":"Mixture of two separated distributions at critical capacity forces quadratic-log gap to offline optimum.","key_machinery":"Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion that convert lower bounds into explicit constructions and identify why support gaps permit larger regret.","core_discovery":"For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of (log T)^2. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Multi-secretary requires (log T)^2 regret lower bound for gapped uniforms","Bellman certificates prove (log T)^2 multi-secretary regret lower bound","(log T)^2 regret lower bound for gapped multi-secretary problem","Gapped distributions require (log T)^2 regret in multi-secretary"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The model uses bounded-density distributions with support gaps and measures additive regret relative to the offline prophet reward in the standard multi-secretary setting.","fun_headline_variants_meta":{"raw":{"variants":["Multi-secretary requires (log T)^2 regret lower bound for gapped uniforms","Bellman certificates prove (log T)^2 multi-secretary regret lower bound","(log T)^2 regret lower bound for gapped multi-secretary problem","Gapped distributions require (log T)^2 regret in multi-secretary"]},"model":"grok-4.3","cost_usd":0.005234,"raw_usage":{"total_tokens":2517,"prompt_tokens":632,"num_sources_used":0,"completion_tokens":80,"cost_in_usd_ticks":52337000,"prompt_tokens_details":{"text_tokens":632,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1805,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":632,"tokens_out":80,"duration_ms":14678,"temperature":1.0,"reasoning_tokens":1805,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-03T03:56:17.474206+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit computation of the optimal online policy's expected regret for the two-uniform mixture instance at sufficiently large T that yields o((log T)^2) would disprove the lower bound.","supporting_citations":[],"review_version":1}