{"id":"f3a3fe26-9eb2-4a7e-95a3-59be907c1f52","arxiv_id":"2501.01716","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Certainty Equivalent heuristic achieves near-optimal hindsight regret for online linear programming under mild distributional assumptions, without requiring non-degeneracy or second-order growth conditions.","lead":"This paper proves that the Certainty Equivalent heuristic, a standard algorithm for online resource allocation, achieves near-optimal regret without restrictive non-degeneracy conditions, as long as the request distribution is sufficiently regular. This matters because it overturns a long-held belief that degeneracy forces algorithmic redesign, and it clarifies that dual uniqueness, not non-degeneracy, is the key structural property.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix F proof of Lemma 5.2 under Assumption 2.2 contains an inverted Hölder bound (c_ν^{1/ν} instead of c_ν^{-1/ν}), leaving the Assumption 2.2 branch of Theorem 3.1 unproven as written.","rationale":"The paper's central claim is that the CE heuristic achieves near-optimal hindsight regret under either Assumption 2.1 or Assumption 2.2 without non-degeneracy or second-order growth conditions. The proof hinges on Lemma 5.2, whose Assumption 2.2 proof contains a concrete algebraic error: the inequality 1 ≤ c_ν(r_a-l_a)^ν implies r_a-l_a ≥ c_ν^{-1/ν}, not c_ν^{1/ν}. The correct bound is used to control a ball around a support point and to guarantee that certain dual quantities fall inside the conditional reward support. The failure of this bound for a valid instance (e.g., F_a ~ U[1,2], r|a ~ U[0,2/3]) means the proof of Lemma 5.2 under Assumption 2.2 is incomplete as written. This is directly load-bearing because Theorem 3.1's Assumption 2.2 branch depends on Lemma 5.2. I do not claim the theorem is false; the error appears fixable by replacing c_ν^{1/ν} with c_ν^{-1/ν} and adjusting constants. Therefore the appropriate disposition remains conditional acceptance, as the reader already recommended. The reader's stated weakest assumption was Assumption 2.1(ii) and the necessity of zero-starting reward support; I partially agree that this assumption is important, but the proof-level gap I identify is more central to the submitted argument and was not flagged by the reader.","tokens_in":1187,"tokens_out":2823,"duration_ms":223762,"concrete_test":"Independently re-derive Lemma 5.2 under Assumption 2.2 using the correct lower bound r_a-l_a ≥ c_ν^{-1/ν} and re-verify every occurrence in Appendix F, Lemma I.12, and the constants r_1, c_1, c_2, c_3, c_4 in Remark B.1. If the proof goes through, Theorem 3.1 stands with corrected constants; if any step fails, construct a counterexample to Lemma 5.2 for the valid instance F_a ~ U[1,2], r|a ~ U[0,2/3].","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix F proves Lemma 5.2 under Assumption 2.2 by starting from the Hölder upper bound: 1 = F_r^a(r_a) - F_r^a(l_a) ≤ c_ν(r_a-l_a)^ν. Correct algebra gives r_a-l_a ≥ c_ν^{-1/ν}, but the proof concludes c_ν^{1/ν} ≤ r_a-l_a. This reversed bound is then used to define r_1 and to assert there is a ball B(a,r_1) on which a'^T λ*_t stays inside the support [l_{a'}, r_{a'}]. That inclusion can fail: take m=1, F_a ~ U[1,2], and r|a ~ U[0,2/3] (so c_ν = 3/2, ν=1, β=0). The erroneous bound gives c_ν^{1/ν} = 1.5 > 2/3, so the claimed support inclusion is impossible; the geometric Case 1 argument in Lemma 5.2 is invalid for a valid instance. Since Lemma 5.2 provides the concentration inequality used in Section 5.3 to prove Theorem 3.1, the Assumption 2.2 branch of the central regret bound is not established by the submitted proof. Replacing c_ν^{1/ν} with c_ν^{-1/ν} throughout Appendix F and Remark B.1 appears to repair the argument, but this must be checked line-by-line.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Certainty Equivalent (CE) heuristic for online linear programming with a known i.i.d. demand distribution F. It introduces two distributional assumptions (Assumption 2.1 and Assumption 2.2) that require, roughly, conditional reward CDFs to be gap-free and to satisfy a reverse Hölder condition with parameter β. Under either assumption, the paper claims that CE achieves hindsight regret O((log T)^2) for β = 0 and O(T^{1/2 - 1/(2(1+β))} (log T)^{(2+β)/(2+2β)}) for β > 0, uniformly in the initial inventory b, and that this is near-optimal up to polylogarithmic factors. The proof combines a regret decomposition, uniform concentration estimates for the solutions of empirical dual LPs derived from empirical-process bracketing entropy and peeling, and a case analysis under the two assumptions. The paper also contains a conceptual discussion arguing that dual uniqueness, rather than non-degeneracy, is the key structural property for CE performance in non-discrete settings.","tokens_in":65447,"tokens_out":10563,"duration_ms":96278,"significance":"If the main theorem is established, this is a significant contribution: it provides the first generic low-regret guarantee for CE without non-degeneracy or second-order growth conditions, and it covers arbitrary bounded resource-consumption distributions under Assumption 2.1 and regular continuous distributions under Assumption 2.2. The explicit interpolation between the polylogarithmic and square-root regimes through the Hölder parameter β, together with the matching lower bound from prior work, gives a fairly complete picture. The technical machinery, especially the uniform concentration analysis of SAA dual solutions via bracketing entropy and peeling, is of independent interest. The paper also gives explicit constants and is transparent about the provenance of the lower bound.","major_comments":[{"comment":"The proof of Lemma 5.2 under Assumption 2.2 contains an inverted Hölder bound that invalidates the argument as written. From 1 = F_r^a(r_a) - F_r^a(l_a) ≤ c_ν (r_a - l_a)^ν, the correct conclusion is r_a - l_a ≥ c_ν^{-1/ν}, but the text states c_ν^{1/ν} ≤ r_a - l_a. This reversed inequality is then used to define r1 = (1/8)((c_L + √m \\bar{r}/A)^{-1} ∧ 1) c_ν^{1/ν} and to assert, in the paragraph containing equation (27), that a'^T λ*_t lies in [l_{a'}, r_{a'}] for all a' ∈ B(a, r1). The asserted support inclusion can fail for a valid instance: take m = 1, F_a ~ U[1,2], and r|a ~ U[0,2/3], which satisfies Assumption 2.2 with c_ν = 3/2 and ν = 1; the claimed lower bound c_ν^{1/ν} = 1.5 exceeds the support length 2/3, so the ball argument cannot hold. Since Lemma 5.2 supplies the concentration estimate used in Section 5.3 to prove Theorem 3.1, the Assumption 2.2 branch of the main theorem is not established by the submitted proof. Replacing c_ν^{1/ν} by c_ν^{-1/ν} in r1 and in the related constants is the natural repair, but this is not a purely cosmetic change: Lemma I.12 uses the same quantity to assert (c_L + √m \\bar{r}/A)r1 ≤ (1/8)c_ν^{1/ν}, so the constants in Appendix F, Lemma I.12, and Remark B.1 must be recomputed and checked line by line.","section":"Appendix F, first paragraph"}],"minor_comments":[{"comment":"The statement of Lemma 5.2 writes the conditional reward CDF as F_a in the left-hand side, but the proof and equation (16) use F^r_a, the CDF of the reward given a. Please correct the notation to F^r_a throughout the lemma statement.","section":"Section 5.2, Lemma 5.2"},{"comment":"The symbol \"/BD\" appears in many formulas, apparently as a placeholder for an indicator function (e.g., a_i /BD(r > a^T λ)). It is undefined and should be replaced by a proper indicator notation such as 1{...}.","section":"Throughout (e.g., Assumption 4.2, Proposition 3.2, Section 5.2)"},{"comment":"The proof of Lemma 5.3 uses an auxiliary quantity M1 that is defined as the maximum of two separate square-root expectations, but then the text states \"Note that M1 = \\sqrt{E_{a∼F^a}[(a^T \\tilde λ_t - a^T λ^*_t)^2 max(...)]}\", which is a different, larger quantity. The inequality direction is favorable (the max-of-two is no larger than the sqrt-of-expectation-of-max), so the proof can be repaired, but the equality assertion is inaccurate and should be replaced by an explicit inequality.","section":"Appendix G, after equation (52)"},{"comment":"Lemma 4.4, which is central to the paper's conceptual claim that dual uniqueness and non-degeneracy decouple in non-discrete settings, is stated with the remark \"the proof of which we omit.\" Since the lemma is not used in the proof of Theorem 3.1, this omission does not block the main regret bound, but a published version should either provide a proof or clearly flag the statement as a conjecture.","section":"Section 4.4, Lemma 4.4"},{"comment":"Near the end of Lemma 5.4, the phrase \"and C is a universal constant\" appears twice with a parenthetical reference to Lemma I.5 in between. Please remove the duplication and place the reference cleanly.","section":"Section 5.2, Lemma 5.4"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Appendix F is valid and is the main reason for major revision. The inverted Hölder bound is a genuine algebraic error, and it breaks the Assumption 2.2 branch of the proof of Theorem 3.1 as written. The error appears reparable by recomputing the affected constants, but this requires careful checking of Appendix F and Lemma I.12. I therefore recommend major revision rather than rejection. The conceptual discussion in Section 4 is interesting, though Lemma 4.4 would need a proof before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this one. The main claim is real and important: the Certainty Equivalent heuristic achieves near-optimal regret without non-degeneracy or second-order growth, under distributional assumptions that are checkable from primitives. That overturns a condition widely treated as necessary, and the regret scaling in β is the right generalization of the multisecretary spectrum. The empirical-process concentration argument is genuinely new, and the proof under Assumption 2.1 is detailed and plausible.\n\nBut the Assumption 2.2 branch has a concrete error. In Appendix F, from 1 = F_r^a(r_a) - F_r^a(l_a) ≤ cν(r_a - l_a)^ν, the text concludes cν^{1/ν} ≤ r_a - l_a. The correct bound is cν^{-1/ν} ≤ r_a - l_a. The inverted constant is then used to define r1 and to claim that a'^T λ*_t stays inside the conditional reward support on a ball. It fails on a valid instance: m=1, F_a uniform on [1,2], r|a uniform on [0,2/3], cν=3/2, where the erroneous bound gives 1.5 ≤ 2/3. So Lemma 5.2 is not proven under Assumption 2.2 as written.\n\nThis looks like a slip rather than a fatal flaw. Replacing cν^{1/ν} by cν^{-1/ν} throughout Appendix F and Remark B.1 should repair the geometry, and the rest of the chain goes through with the same scaling. But it has to be checked line by line; the published version needs the corrected constants.\n\nTwo smaller things. Lemma 4.4 is stated without proof; it supports the degeneracy narrative rather than the regret bound, so it is minor, but it should be proved or explicitly downgraded to a remark. The lower bound is adapted from prior work with a brief remark; acceptable, but it deserves a bit more care.\n\nOverall: substantial, novel, honestly written. The central claim is likely correct, with one fixable error in one branch. This paper deserves a serious referee. I would send it out, with a clear request to fix the Hölder constant inversion before acceptance.","headline":"Genuine advance: CE provably beats degeneracy under mild distributional assumptions, but the Assumption 2.2 branch has an inverted Hölder constant in Appendix F that must be fixed before the proof is trusted.","tokens_in":66044,"tokens_out":4027,"would_cite":true,"duration_ms":37520,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C05","90B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that the standard certainty equivalent heuristic achieves hindsight regret $O((\\log T)^2)$ for online linear programs when conditional reward distributions are gap-free, and a matching interpolating bound for distributions…","keywords":["certainty equivalent heuristic","online linear programming","hindsight regret","degeneracy","dual uniqueness","empirical process concentration","network revenue management"],"falsifier":"Run Example 4.3 from the paper: two resource-consumption types $a=1$ and $a=4$ each with probability $1/2$, reward conditional on either type distributed $\\mathrm{Unif}[1,2]$, and initial capacity $b=T/2$. The paper claims CE's hindsight regret is $\\Omega(\\sqrt{T})$ here because the conditional reward supports do not start at zero; observing $o(\\sqrt{T})$ regret in simulation would falsify that claimed necessity, while observing $\\sqrt{T}$ growth would confirm it.","tokens_in":64919,"feed_emoji":"🎯","tokens_out":9865,"duration_ms":90951,"temperature":0.7,"pith_summary":"The paper tries to establish that the classic certainty equivalent (CE) heuristic, which re-solves the average-value fluid problem at every step and accepts a request when its reward clears the current dual price, is uniformly near-optimal for online linear programming under much weaker conditions than previously believed. Specifically, if each request's conditional reward distribution has support that is an interval starting at zero and obeys a mild reverse Hölder condition parameterized by $\\beta$, CE's hindsight regret is $O((\\log T)^2)$ for $\\beta=0$ and $O(T^{1/2-1/(2(1+\\beta))}(\\log T)^{(2+\\beta)/(2+2\\beta)})$ for $\\beta>0$. This removes the need for fluid non-degeneracy and second-order growth conditions, overturning the working assumption that degeneracy forces algorithmic innovation beyond CE. The insight is that what actually protects CE is uniqueness of the dual optimum, which holds automatically for smooth continuous fluid duals, rather than stability of the set of binding constraints. A reader should care because CE is the workhorse algorithm for network revenue management, dynamic bidding, and order fulfillment, and this result says it works in a broad class of realistic non-discrete problem instances.","feed_headline":"CE heuristic beats the curse of degeneracy","feed_subtitle":"Under mild interval-support assumptions it matches lower bounds up to polylog factors for online linear programs.","key_machinery":"The load-bearing object is the dual fluid objective $f_d(\\lambda)=d^\\top\\lambda+\\mathbb{E}[(r-a^\\top\\lambda)_+]$, whose minimizer is the dual price CE uses to accept or reject. Under the paper's assumptions this function is smooth and has a unique minimizer no matter the remaining inventory, even when the set of binding constraints changes. The proof machinery is a regret decomposition (Lemma 5.1) that bounds regret by the expected gap between the conditional reward CDF evaluated at CE's dual price and at the hindsight-optimal dual prices, followed by a concentration analysis (Lemmas 5.2-5.5) of the solutions to the per-step sample-average version of the dual program; empirical-process peeling with bracketing entropy controls these solutions uniformly, which is what removes the need for non-degeneracy and second-order growth conditions. The parameter $\\beta\\in[0,\\infty)$ in the reverse Hölder condition quantifies the minimal rate of probability accumulation of conditional reward distributions and directly governs the concentration rate and hence the regret exponent.","core_discovery":"On the paper's own terms, the central discovery is Theorem 3.1: for any online linear programming instance whose request distribution satisfies Assumption 2.1 or Assumption 2.2, the certainty equivalent heuristic attains hindsight regret at most $C(\\log T)^2$ when $\\beta=0$ and at most $\\tilde{C} T^{\\frac12-\\frac{1}{2(1+\\beta)}}(\\log T)^{\\frac{2+\\beta}{2+2\\beta}}$ when $\\beta>0$, for arbitrary capacity $b$ and all $T>3$, with constants independent of $T$ and $b$. Proposition 3.2 supplies a matching lower bound $\\Omega(T^{\\frac12-\\frac{1}{2(1+\\beta)}})$ for $\\beta>0$ and $\\Omega(\\log T)$ for $\\beta=0$ in multisecretary instances, so CE is near-optimal up to polylog factors. The paper further establishes (Corollary 4.2) that standard non-degeneracy assumptions are not necessary for this guarantee, and argues (Lemmas 4.3-4.5, Proposition 4.6) that the structural property that really protects CE is uniqueness of the fluid dual optimum rather than stability of the set of binding resource constraints.","pith_inferences":["Editorial extension: the same dual-uniqueness reasoning likely extends to price-based network revenue management, where CE-type re-solving is also known to rely on non-degeneracy; a smooth dual objective should protect re-solving policies there as well, but the paper does not analyze that setting.","Editorial extension: the $\\beta$ interpolation is testable with multisecretary reward densities proportional to $(1+\\beta)|1-2x|^{\\beta}$; measuring regret slopes across horizons $T$ should reveal the predicted exponent $\\frac12-\\frac{1}{2(1+\\beta)}$.","Editorial extension: for the irregular gap distributions the paper excludes, Proposition 4.6 shows CE fails, so a natural next step is a hybrid policy that applies CE on gap-free regions and reserves capacity around gaps; the paper does not construct such a policy."],"forward_implications":["In all instances satisfying Assumption 2.1 or 2.2, CE attains $O((\\log T)^2)$ hindsight regret when $\\beta=0$, for example in multisecretary, hyper-cube, and generalized-linear-model settings, without any fluid regularity conditions.","For $\\beta>0$, the regret bound $O(T^{1/2-1/(2(1+\\beta))}(\\log T)^{(2+\\beta)/(2+2\\beta)})$ interpolates toward the worst-case $\\sqrt{T}$ regime as $\\beta\\to\\infty$, and Proposition 3.2 shows this is near-optimal up to polylog factors.","Degeneracy in the sense of unstable binding constraints no longer predicts CE failure once conditional reward distributions are continuous and gap-free; the relevant property is dual uniqueness.","Because the assumptions are on the request distribution rather than on the fluid solution, they can be checked from primitives, and CE can be applied directly in the square-root-inventory regime where degeneracy is most likely to arise.","The new CE bounds can serve as a reference guarantee for simulation-based algorithms that inherit the performance of a reference policy, extending uniform low-regret guarantees to instances previously out of reach."],"supporting_citations":[{"why":"Supplies the multisecretary regret spectrum and lower bound that Theorem 3.1 and Proposition 3.2 generalize, and the gap-distribution examples against which CE is contrasted.","marker":"Besbes et al. (2024)"},{"why":"Establishes the prior semi-discrete CE analysis under a uniform second-order growth condition and supplies the degenerate example used in the proof of Lemma 4.1.","marker":"Jiang et al. (2022a)"},{"why":"Provides the dual fluid formulation and the earlier $O(\\log T\\log\\log T)$ CE guarantee under non-degeneracy that this paper removes.","marker":"Li and Ye (2022)"},{"why":"Establishes the logarithmic-regret benchmark and the $\\beta=0$ multisecretary lower bound that the paper matches.","marker":"Bray (2024)"},{"why":"Proves that in discrete settings degeneracy forces $\\Theta(\\sqrt{T})$ regret for CE, the negative result this paper resolves for non-discrete distributions.","marker":"Bumpensanti and Wang (2020)"},{"why":"Provides the compensated coupling perspective used in the regret decomposition of Lemma 5.1.","marker":"Vera and Banerjee (2021)"},{"why":"Supplies the empirical-process concentration inequalities used in the peeling-based uniform concentration analysis.","marker":"Geer (2000)"}],"fun_headline_variants":["CE heuristic near-optimal without non-degeneracy","CE heuristic beats curse of degeneracy","Online LP: CE optimal up to polylog without fluid regularity","CE heuristic works without non-degeneracy assumptions","Degeneracy no longer a barrier for CE heuristic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that conditional rewards are spread over intervals that start at zero, at least locally for the second assumption class, so the fluid dual objective is smooth with a unique optimum; if reward distributions instead have gaps or lower endpoints above zero, the paper shows CE can suffer $\\Omega(\\sqrt{T})$ regret.","fun_headline_variants_meta":{"raw":{"variants":["CE heuristic near-optimal without non-degeneracy","CE heuristic beats curse of degeneracy","Online LP: CE optimal up to polylog without fluid regularity","CE heuristic works without non-degeneracy assumptions","Degeneracy no longer a barrier for CE heuristic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000537,"raw_usage":{"total_tokens":2647,"prompt_tokens":1081,"completion_tokens":1566,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":697,"completion_tokens_details":{"reasoning_tokens":1491}},"tokens_in":697,"tokens_out":1566,"duration_ms":12141,"temperature":1.0,"reasoning_tokens":1491,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:21:17.620650+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Example 4.3 from the paper: two resource-consumption types $a=1$ and $a=4$ each with probability $1/2$, reward conditional on either type distributed $\\mathrm{Unif}[1,2]$, and initial capacity $b=T/2$. The paper claims CE's hindsight regret is $\\Omega(\\sqrt{T})$ here because the conditional reward supports do not start at zero; observing $o(\\sqrt{T})$ regret in simulation would falsify that claimed necessity, while observing $\\sqrt{T}$ growth would confirm it.","supporting_citations":[],"review_version":1}