{"id":"40e189af-4ef3-476c-ab3b-a832c87d0c0b","arxiv_id":"2508.00523","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"DBGD-NF and its blocking variant achieve regret bounds of O(n average-delay^{1/3} T^{2/3}) and O(n(T^{2/3} + sqrt(dT))) for online nonsubmodular optimization with delayed bandit feedback.","lead":"This paper introduces two algorithms for online optimization problems where feedback is delayed and only partially informative. The new methods achieve better worst-case performance than previous approaches, and for small delays they match systems without delay.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Both regret bounds rest on differentiability/Lipschitz and bounded-variance conditions for the one-point bandit estimator, and the available text never states them; the abstract's weak DR assumptions alone do not supply them.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing condition: the one-point estimator's unbiasedness and bounded variance are not guaranteed by the abstract's weak DR assumptions alone. A stress test should not manufacture a different concern when the reader has already located the decisive soft spot. I read the abstract as claiming a genuine improvement: average delay replaces maximum delay in the first bound, and delay and bandit error are additively decoupled in the second. That structural claim is internally coherent and the comparison d = o(\\bar d^{2/3} T^{1/3}) is consistent with the two bounds. The remaining risk is not internal inconsistency but a missing hypothesis: without differentiability/Lipschitz conditions, the one-point estimator cannot be controlled, and neither bound follows. The supplied full text is blank, so no proof can be checked; this is why the reader's CONDITIONAL verdict is appropriate. My recommendation is UNCHANGED because the concern does not move the verdict: the paper remains conditionally acceptable pending verification of the regularity assumptions and concentration arguments. If the full text turns out to omit those assumptions, the verdict should move to REJECT; if it includes them and the proofs are correct, it should move to ACCEPT. The concrete test above settles which branch applies.","tokens_in":949,"tokens_out":5110,"duration_ms":56663,"concrete_test":"Inspect Section 2 and the theorem statements of the full manuscript for explicit regularity assumptions: (A1) for every t, f_t is differentiable and L-Lipschitz on a bounded convex set K; (A2) the one-point sampling distribution is supported on K with density bounded below; (A3) delays d_t are bounded by d. If A1 is absent, run a scalar counterexample f(x)=√x on K=[0,1], which is weakly DR-submodular but not Lipschitz at 0; the estimator's bias/variance diverge as δ→0, so the claimed O(T^{2/3}) exponent cannot be obtained. If A1 is present, verify the variance lemma that bounds the estimator variance by O(n^2/δ^2) and that the choice δ∝T^{-1/3} converts this into the stated regret terms, including the average-delay coupling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims are the O(n \\bar d^{1/3} T^{2/3}) bound for DBGD-NF and the O(n(T^{2/3} + sqrt(dT))) bound for its blocking variant. Both derivations must use a one-point bandit gradient estimator of the form g_t = (n/δ) f_t(x_t + δ u_t) u_t. For this estimator to be unbiased with bounded variance, the losses must be differentiable and L-Lipschitz on a bounded convex feasible set, and the sampling distribution must have density bounded away from zero. The abstract only assumes α-weak DR-submodularity and β-weak DR-supermodularity; these are order-theoretic curvature conditions and do not imply differentiability, Lipschitzness, or any gradient regularity. If the full text does not explicitly impose such regularity assumptions, the bias and variance of the estimator can diverge, and the concentration arguments behind both bounds collapse. A related second risk is that DBGD-NF uses all available delayed gradients in each round, creating dependence between the current decision and past gradients; the average-delay bound requires a concentration inequality for this dependent, delayed sequence. The supplied full text is empty, so these conditions cannot be checked from the available material.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online nonsubmodular optimization with delayed feedback in the bandit setting, assuming the loss functions are α-weakly DR-submodular and β-weakly DR-supermodular. The abstract proposes DBGD-NF, a one-point gradient estimator method that uses all available delayed gradients in each round and claims a regret bound of O(n\\bar{d}^{1/3}T^{2/3}) in terms of the average delay \\bar{d}, improving on the previous O(nd^{1/3}T^{2/3}) bound that depended on the maximum delay d. A second algorithm uses a blocking update mechanism and claims an O(n(T^{2/3}+\\sqrt{dT})) regret bound, which additively decouples the effects of delays and bandit feedback and matches the no-delay bound when d=O(T^{1/3}). The abstract also reports experiments on structured sparse learning. The supplied manuscript contains only the abstract; no full-text proofs or derivations are provided.","tokens_in":1230,"tokens_out":3768,"duration_ms":36016,"significance":"If the claimed bounds are correct, the paper makes a meaningful theoretical contribution: it replaces the maximum delay with the average delay in the first bound and additively decouples delay effects from bandit estimation error in the second, improving known results. The internal arithmetic is consistent: the second bound reduces to the no-delay O(nT^{2/3}) bound when d=O(T^{1/3}), and the comparison condition d=o(\\bar{d}^{2/3}T^{1/3}) is arithmetically correct. However, because only the abstract is available, the decisive proof details—especially the concentration arguments and the regularity conditions for the one-point estimator—cannot be checked, so the significance is conditional.","major_comments":[{"comment":"The abstract assumes only α-weak DR-submodularity and β-weak DR-supermodularity, but the one-point gradient estimator used by both algorithms requires differentiability and L-Lipschitz continuity of the losses on a bounded convex feasible set with a sampling density bounded away from zero. These conditions are not stated, and weak DR conditions do not imply them; the full text must explicitly impose these regularity assumptions and prove the unbiasedness and bounded variance of the estimator, otherwise the concentration arguments behind both regret bounds are unsupported.","section":"Abstract"},{"comment":"The claim that using all available delayed gradients in each round yields an O(n\\bar{d}^{1/3}T^{2/3}) bound relies on a concentration inequality for a sequence in which the current decision depends on past gradients. The abstract gives no indication of how this dependent, delayed sequence is handled; without a proof of such an inequality, the average-delay bound is not established by the available material.","section":"Abstract (DBGD-NF description)"}],"minor_comments":[{"comment":"The notation \\bar{d} is defined as the average delay, but the definition would be clearer if placed in a displayed equation in the full text.","section":"Abstract"},{"comment":"The final sentence mentions experiments on structured sparse learning without naming baselines or metrics; the full text should specify the experimental setup and comparisons.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"The review is based solely on the abstract because the full text was not provided. This makes verification of the central claims impossible. The abstract's bounds are internally consistent and the comparison between the two regret bounds is correct, but the two technical risks I identified—missing regularity conditions for the one-point estimator and the dependence in the delayed gradient sequence—are load-bearing. I recommend that the editor obtain the full text and have the referees check these points before making a decision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, quick take on arXiv:2508.00523. I only have the abstract; the full text is empty in our pipeline, so this is all based on what's visible.\n\nWhat's new: the paper claims an average-delay-dependent regret bound O(n \\bar{d}^{1/3} T^{2/3}) for DBGD-NF and an additive, decoupled bound O(n(T^{2/3} + \\sqrt{dT})) for its blocking variant. The prior bound O(n d^{1/3} T^{2/3}) depends on maximum delay and multiplies delay cost with bandit cost. Replacing max with average delay and separating the two sources is a genuine conceptual step. The bounds are internally consistent—when d = O(T^{1/3}) the second collapses to the no-delay O(nT^{2/3}), and the comparison between the two is arithmetically sound. The algorithmic ideas (using all available gradients each round, and a blocking update) are plausible. Experiments on structured sparse learning are mentioned, though no results are shown.\n\nWhere I'm cautious: the proofs matter enormously, and we can't see them. The stress-test note nails the specific worry: the one-point gradient estimator needs the loss to be differentiable and Lipschitz, the feasible set bounded with a sampling density bounded away from zero, and the estimator's variance bounded. The abstract's assumptions (alpha-weak DR-submodular, beta-weak DR-supermodular) are order-theoretic; they don't imply those analytic conditions. If the full text doesn't state them, the bias/variance argument collapses. A second concern is the dependence between delayed gradients and current decision in DBGD-NF; the concentration inequality for that dependent sequence isn't visible from the abstract.\n\nNone of this is a reason to kill the paper. It's a reason to send it to a referee who will check the assumptions carefully. The claims are significant if true, and the approach appears coherent. My recommendation: accept for peer review, and require the referee to verify the regularity conditions and the proof of the average-delay bound.\n\nFor myself: I wouldn't cite it until the proofs are public and checked; the potential is there but the current evidence is an abstract. Reading group: maybe, if someone wants to work through the technique.\n\nBest.","headline":"Promising theoretical bounds that improve on prior work, but with only the abstract available the proofs—and the missing analytic assumptions for the one-point estimator—are what a referee must check.","tokens_in":1704,"tokens_out":2624,"would_cite":false,"duration_ms":24234,"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":"The paper establishes that delayed bandit feedback in nonsubmodular optimization can be priced by average delay rather than maximum delay, and gives a blocking variant whose regret adds the delay cost to the bandit cost.","keywords":["online learning","nonsubmodular optimization","bandit feedback","delayed feedback","regret bound","DR-submodular","one-point gradient estimator","blocking update"],"falsifier":"Take a problem instance that satisfies the paper's regularity conditions, keep the average delay $\\bar{d}$ fixed, and shift all delay into a single round so that the maximum delay $d$ grows; if the empirical regret of DBGD-NF grows with $d$ rather than staying tied to $\\bar{d}$, the average-delay bound is false. For the blocking variant, run it under delay patterns with the same $d$ but different block boundaries and check whether the regret separates into an $nT^{2/3}$ bandit term plus an $n\\sqrt{dT}$ delay term.","tokens_in":790,"feed_emoji":"📉","tokens_out":8344,"duration_ms":68772,"temperature":0.7,"pith_summary":"This paper studies online optimization over losses that are not convex but are only approximately submodular, in the bandit setting where the learner sees only the value of the point it chose and feedback arrives after a delay. The first algorithm, DBGD-NF, uses a one-point gradient estimator and exploits every estimated gradient that has arrived in a round, achieving an $(\\alpha,\\beta)$-regret bound of $\\mathcal{O}(n\\bar{d}^{1/3}T^{2/3})$, where $\\bar{d}$ is the average delay. The second adds a blocking update mechanism and attains $\\mathcal{O}(n(T^{2/3}+\\sqrt{dT}))$, separating the delay contribution from the bandit contribution. If these bounds are correct, the price of delayed feedback depends on the typical delay, not the worst spike, and when the maximum delay is small the algorithm recovers the no-delay bandit regret.","feed_headline":"Delay cost now scales with average delay, not worst-case delay","feed_subtitle":"Regret tracks the mean delay, and a blocking variant recovers no-delay performance when maximum delay is small.","key_machinery":"Two mechanisms carry the argument. First, the one-point gradient estimator: the algorithm queries a single function value per round and constructs an unbiased gradient estimate from it, and by using all delayed estimates that have arrived by the current round it accumulates information faster than a method that waits on the latest sample. Second, the blocking update: decisions are held fixed for blocks of rounds, so the randomness from bandit feedback and the randomness from delay can be controlled in separate terms; this is what turns a product of delay and bandit regret into a sum.","core_discovery":"The central claim is that delayed feedback in bandit online optimization over $\\alpha$-weakly DR-submodular and $\\beta$-weakly DR-supermodular losses—continuous functions whose diminishing-returns property holds only approximately—is less costly than earlier bounds suggested. Previous work bounded regret by $\\mathcal{O}(nd^{1/3}T^{2/3})$ using the maximum delay $d$ and multiplied the delay penalty with the no-delay bandit regret. DBGD-NF instead averages over all available gradient estimates each round, turning the delay dependence into $\\bar{d}^{1/3}$, where $\\bar{d}=\\frac{1}{T}\\sum_{t=1}^T d_t$ is the mean delay. The blocking variant updates the decision only at block boundaries, which changes the joint effect of delay and bandit feedback from a product into a sum, yielding $\\mathcal{O}(n(T^{2/3}+\\sqrt{dT}))$; for $d=\\mathcal{O}(T^{1/3})$ this matches the $\\mathcal{O}(nT^{2/3})$ regret achievable without delay.","pith_inferences":["A general lesson the paper does not state: for delayed bandit online optimization, the first moment of the delay distribution is often the right object, not the worst case, which suggests other delayed-feedback algorithms could be made delay-robust by averaging over all available queries.","The additive decoupling in the blocking variant may transfer to other bandit problems, predicting that any bandit algorithm whose regret is known without delay can be converted to a delayed setting by paying at most an added $\\sqrt{dT}$ term.","A testable extension would compare DBGD-NF against the previous method under delay distributions with the same maximum delay but different means; if mean-delay dependence is real, the advantage should grow as the mean shrinks.","The one-point estimator plus all-available-gradients rule suggests a cheap modification for many online algorithms: keep a queue of delayed gradient estimates and update with all of them, not just the freshest one."],"forward_implications":["Regret degrades with the average delay $\\bar{d}$ rather than the maximum delay $d$, so rare long delays become nearly harmless under DBGD-NF.","The blocking variant achieves an additive $\\mathcal{O}(n(T^{2/3}+\\sqrt{dT}))$ bound, meaning bandit error and delay error no longer multiply against each other.","When $d=\\mathcal{O}(T^{1/3})$, the blocking variant reproduces the $\\mathcal{O}(nT^{2/3})$ regret bound of the bandit setting without delayed feedback.","Comparing the two new bounds, the blocking variant is preferable when the maximum delay satisfies $d=o(\\bar{d}^{2/3}T^{1/3})$.","Experiments on structured sparse learning illustrate that both methods improve over the previous worst-case-delay algorithm."],"supporting_citations":[],"fun_headline_variants":["Regret tracks mean delay, not worst-case delay","Blocking update separates delay and bandit regret","Average delay replaces max in bandit regret bound","New algorithms cut delayed bandit regret","Small max delay gives no-delay regret rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bounds rely on the one-point gradient estimator being unbiased with bounded variance, which requires the loss functions to be differentiable and Lipschitz on a bounded convex feasible set; if these regularity conditions fail, the concentration arguments behind the regret bounds collapse.","fun_headline_variants_meta":{"raw":{"variants":["Regret tracks mean delay, not worst-case delay","Blocking update separates delay and bandit regret","Average delay replaces max in bandit regret bound","New algorithms cut delayed bandit regret","Small max delay gives no-delay regret rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000472,"raw_usage":{"total_tokens":2456,"prompt_tokens":1163,"completion_tokens":1293,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":779,"completion_tokens_details":{"reasoning_tokens":1223}},"tokens_in":779,"tokens_out":1293,"duration_ms":11477,"temperature":1.0,"reasoning_tokens":1223,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T10:05:45.627720+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a problem instance that satisfies the paper's regularity conditions, keep the average delay $\\bar{d}$ fixed, and shift all delay into a single round so that the maximum delay $d$ grows; if the empirical regret of DBGD-NF grows with $d$ rather than staying tied to $\\bar{d}$, the average-delay bound is false. For the blocking variant, run it under delay patterns with the same $d$ but different block boundaries and check whether the regret separates into an $nT^{2/3}$ bandit term plus an $n\\sqrt{dT}$ delay term.","supporting_citations":[],"review_version":1}