{"id":"5186b535-7b54-42d2-92bd-a6f4dfbd116f","arxiv_id":"2501.14155","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Claims logarithmic and square-root regret bounds for dynamic pricing with inventory constraints across three information settings; key proof steps in the no-information and informed-price results are invalid as written.","lead":"Researchers propose three pricing algorithms for a seller with limited inventory who must learn how demand responds to prices. The paper claims tight theoretical guarantees, but the proofs as written contain errors that break the main claims.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1 is not proven for Algorithm 2 as written: the proof analyzes the uncensored demand process f(p_t)+ε_t, while Algorithm 2 lines 15-17 reject some types and update inventory with accepted demands; Theorem 4.3 inherits the same gap.","rationale":"The paper proposes a plausible framework, and the full-information result Theorem 2.1 may be repairable, but the no-information and informed-price results are the main claims. The load-bearing gap is not merely a missing detail: the pseudocode and the analysis appear to describe different policies. Because the regression in (6) is the only learning mechanism, and because the proof's single-block decomposition (41) is the basis of the regret bound, the rejection step cannot be ignored. I agree with the reader's REJECT verdict: the main theorems are not established as stated. I set the verdict to UNCHANGED because my stress-test reinforces rather than shifts the reader's decision. The reader correctly identified both Eq. (35) and the rejection/censoring issue; I view the rejection/data mismatch as the more load-bearing problem because it is a mismatch between algorithm and proof, not a typo. Eq. (35) could likely be fixed by using block-specific anchors X_{⌈s/n⌉} from (7), whereas the rejection issue requires either removing the rejection step, explicitly using the observed pre-rejection demand in regression and bounding the revenue loss, or extending the proof to handle censored demand. Until then, the headline no-information and informed-price guarantees remain unsupported.","tokens_in":25144,"tokens_out":15654,"duration_ms":142314,"concrete_test":"Re-derive Eq. (41) in Appendix B using the actual accepted demand vector after Algorithm 2 line 16 instead of the uncensored d_t + ε_t. Take a one-dimensional instance (n=1), fix a block k and a period t with I^t_r nonempty (e.g., estimated demand below ζ((T-t+1)^{-1/4}+t^{-1/4}) but true demand positive), and write the exact one-step difference RT(Hybrid_k,F^T)-RT(Hybrid_{k+1},F^T). If this expression differs from (41) by a term not absorbed by the bounds leading to (50) — for example an omitted revenue loss from rejected demand or a biased regression term — then Theorem 3.1 is not proven for Algorithm 2 as stated. Apply the same check to Algorithm 3 lines 11-14 and Theorem 4.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The no-information result Theorem 3.1 is a headline contribution, but the proof in Appendix B does not analyze the policy defined by Algorithm 2. Algorithm 2 line 16 rejects all types whose estimated demand falls below the rounding threshold and 'updates accepted demands' before the inventory update in line 17. The proof, however, models realized demand as d_t + ε_t with d_t := f(p_t), and uses this vector in the single-block regret decomposition (41), in the inventory recursion, and in the linear regression (6). The set I^t_r never appears in the proof. This creates a dilemma. If d_t used for revenue and inventory is the accepted demand after line 16, then for rejected types d_t is not f(p_t)+ε_t, so the regression estimator (6) is biased and the decomposition of Δ^t via (32)-(40) is invalid. If d_t is the pre-rejection observed demand, then the revenue and inventory updates in (41) do not match the algorithm's execution. In both cases, the O(√T) regret bound is not established for the stated algorithm. Algorithm 3 has the same rejection structure (lines 11-14), so Theorem 4.3 is threatened as well. Separately, Eq. (35) is false as written because it uses the current block's anchor for all past blocks; that is a serious proof error, but the rejection/data mismatch is more fundamental because it changes the policy being analyzed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a T-period dynamic pricing problem with n products and m resource constraints under a linear demand model with sub-Gaussian noise. It proposes three policies: Algorithm 1, a full-information re-solve heuristic with a boundary-attraction threshold claimed to achieve O(ζ²n²‖B^{-1}‖² log T) regret without the non-degeneracy condition; Algorithm 2, a periodic-review re-solve heuristic with linear-regression parameter learning and price perturbations claimed to achieve O((ζ²+‖B^{-1}‖²)√T) regret with no prior information; and Algorithm 3, an estimate-then-select method using an informed price-demand pair with known error bound ε0 claimed to achieve O(min{ρ√T,(ε0)²T}+log T). The paper also reports numerical experiments and sketches proofs based on hybrid-policy regret decompositions, concentration inequalities, and stability of quadratic programs.","tokens_in":25434,"tokens_out":6232,"duration_ms":53373,"significance":"If the results were correct, the full-information logarithmic regret without non-degeneracy would be a meaningful extension of the re-solve heuristic literature, and the no-information √T bound would match the known lower bound. The informed-price interpolation is conceptually attractive and gives a falsifiable prediction about a phase transition in ε0. The paper makes a good-faith effort to connect with previous work and to validate the algorithms numerically. However, the proof of the headline no-information theorem does not analyze the algorithm as written, and the key exploration lower bound is derived by an invalid identity; these are load-bearing issues, so the significance is conditional on a substantial revision.","major_comments":[{"comment":"Theorem 3.1 is not proven for Algorithm 2 as written. In the algorithm, lines 15–17 reject all types i∈I^t_r and update the inventory with the accepted demands, and the regression input for (6) is the observed demand history; in the proof, however, the realized demand is modeled as d_t=f(p_t)+ε_t for every t in the single-block regret decomposition (41), in the inventory recursion, and in the estimation error bound (36). The set I^t_r never appears in the proof. If the algorithm regresses on post-rejection (zeroed or 'accepted') demands, estimator (6) is biased; if it uses the uncensored realized demand, then the revenue and inventory updates in (41) do not match the algorithm's execution. In either case the O(√T) regret bound is not established for the stated algorithm. Algorithm 3 has the same rejection structure (lines 11–14), so Theorem 4.3 inherits the gap.","section":"Section 3, Algorithm 2, and Appendix B"},{"comment":"The lower bound J_k ≥ σ0²√(kn)/(8n) is derived from the identity J_k = n^{-1} Σ_{l=1}^k Σ_{i=1}^n (1−1/(n(l−1)+i)) σ0²(kn+i)^{-1/2}. This identity is false: the term p_s−p_{s−1}−(p̃_k−p_{kn}) equals the perturbation σ0 s^{-1/4} e_{s−kn} only for s in the block near kn; for earlier blocks the anchor is p̃_l−p_{ln}, not p̃_k−p_{kn}. The sum therefore does not reduce to the displayed perturbation sum, and the eigenvalue lower bound used in Lemma B.1 and Eq. (36) is unsupported. Since this bound controls the parameter estimation error, the proof of Theorem 3.1 depends on an invalid step.","section":"Appendix B, Eq. (35)"},{"comment":"Proposition 4.4 is misstated. It says 'without knowledge of the accuracy ε0' and claims regret O(min{ρ√T,(ε0)²T}) on instance (α,B) and Ω(max{ρ√T,(ε0)²T}) on (α′,B′), but this is not the lower-bound statement needed for Theorem 4.3, which assumes the upper bound ε0 is known. The proof in Appendix D merely refers to Proposition 4.1 and chooses ε of order T^{-(1−γ)/2}; it does not construct two instances with a fixed known ε0 and does not establish the claimed min/max trade-off. The proposition needs to be restated and proved.","section":"Proposition 4.4 and Appendix D"},{"comment":"The proof of Theorem 2.1 has a condition mismatch and a tail-bound error. Theorem 2.1 assumes ζ ≥ 4σ², but the derivation of (21) requires ζ ≥ 4σ² log n and concludes P((E^t)^c) ≤ n exp(−2(T−t) log n) = exp(−2(T−t)); the intermediate inequality is dimensionally inconsistent because the sub-Gaussian tail of max_i ε_i^t depends on ζ²/(2σ²), not on ζ(T−t)/(2σ²). Thus the logarithmic regret bound for Algorithm 1 is not established as written.","section":"Appendix A, Eq. (21) and Theorem 2.1"}],"minor_comments":[{"comment":"The concentration inequality is called Lemma A.2 but is cited as Lemma B.1 before Eq. (21); the cross-reference and the exponent in the sub-Gaussian tail should be corrected.","section":"Appendix A, cross-references"},{"comment":"The proof uses the perturbation σ0 t^{-1/2} B e_l for Δ^t_{II}, while Algorithm 3 line 9 defines the price perturbation as σ0 sgn(p̃_t−p0) t^{-1/4} e_l; these two expressions must be reconciled for the proof to describe the algorithm.","section":"Appendix C, Eq. (55) vs Algorithm 3 line 9"},{"comment":"Assumption 1.2 calls B 'negative definite' but states λmin(B+B^⊤)>0, which is a positive-definiteness condition; the later use of λmin(B^{-1}+B^{-⊤}) in Lemma B.3 should be checked for sign consistency.","section":"Assumption 1.2 and Lemma B.3"},{"comment":"Figure 4 has T on the x-axis while the caption describes different ε0 values, and Figure 2 is described as a log-log plot but the axes are not labeled as logarithmic; the figures should be re-labeled or captioned to match the text.","section":"Section 5, Figures"},{"comment":"The Banerjee and Freund (2020) reference contains placeholder text 'sc.', and the reference list has several formatting errors (e.g., 'Wainwright 2019' vs the full entry); these should be cleaned up.","section":"References and formatting"},{"comment":"There are typos such as 'CwK' for 'BwK' and 'ot' for 'to'; a careful proofreading pass is needed.","section":"Section 1.3"}],"recommendation":"reject","confidential_remarks":"The paper addresses a timely problem and has appealing conceptual contributions, but the referee concerns are not merely cosmetic: the analysis of Algorithm 2 does not match the policy as written, Eq. (35) is wrong, and the lower-bound statements are misaligned. If the authors can fix Theorem 3.1 by redefining the algorithm or completing the proof, the paper may be resubmittable; in the current form I cannot recommend publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the full-information result is the real contribution; the no-information theorem is not proven for the algorithm as written.\n\nThe boundary-attracted re-solve method (Algorithm 1) is a genuine step forward. Removing the non-degeneracy condition for logarithmic regret in price-based revenue management is meaningful, and the technique is clearly explained. The informed-price interpolation in Algorithm 3 is a practically useful bridge, and the phase-transition intuition (log regret when eps0 is small, sqrt(T) otherwise) is appealing. The paper is well-written and the numerical experiments are consistent with the claimed behavior.\n\nNow the soft spots. The no-information Theorem 3.1 has a load-bearing gap: the proof models realized demand as f(p_t)+epsilon_t for every type and never uses the index set I^t_r from Algorithm 2's rejection step. But Algorithm 2 line 16 rejects low-demand types before the inventory update. If the d_t in the proof is the post-rejection accepted demand, then the linear regression (6) is biased and the revenue decomposition (41) is invalid. If d_t is the pre-rejection observed demand, then the inventory recursion does not match the algorithm's execution. Either way, the O(sqrt(T)) bound is not established for the stated policy. This is not a typo; it is a mismatch between the algorithm and the analysis.\n\nSeparately, Eq. (35) is false as written. The lower bound on lambda_min(P^t) uses the current block's anchor for all past blocks, but past blocks had different anchors. The variance accumulation argument needs a different proof. This is also serious, though the rejection mismatch is more fundamental because it changes the policy itself.\n\nProposition 4.4 is misstated. It says \"without knowledge of the accuracy eps0\" even though the surrounding section assumes eps0 is known, and the regret bound does not align with Algorithm 3. The statement needs to be reworked.\n\nThe full-information proof has smaller issues: condition mismatches and a tail-bound constant that is not tracked carefully. These look repairable.\n\nBottom line: the full-information contribution is worth refereeing, and the informed-price idea is worth keeping. But the no-information and informed-price theorems are not established for the algorithms as written. I would send this to peer review with a clear request: focus on the data-censoring issue in Algorithms 2 and 3, and require the proof to either match the algorithm or the algorithm to be redefined.","headline":"The full-information boundary-attraction result is a genuine advance, but the no-information theorem is not proven for Algorithm 2 as written: the proof analyzes uncensored demands while the algorithm rejects some of them.","tokens_in":25958,"tokens_out":1922,"would_cite":false,"duration_ms":18023,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B50","91B24","90C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Re-solving the fluid model with boundary attraction (rounding tiny target demands to zero) gives $O(\\log T)$ regret without non-degeneracy; forced exploration matches the optimal $O(\\sqrt{T})$, and informed prices interpolate.","keywords":["online learning","dynamic pricing","resource constraints","informed price","regret bounds","fluid approximation","non-degeneracy","linear demand model"],"falsifier":"Simulate Algorithm 2 on a degenerate two-product instance and record whether the demands zeroed by the rounding rule are stored for regression. If rejected observations are excluded, refit the parameters with and without them; an estimator bias large enough to push the empirical regret past the claimed $O(\\sqrt{T})$ rate would show the proof relies on unstated uncensored-regression access. Separately, compute the minimum eigenvalue of the design matrix $P^t$ over the horizon and compare it with the claimed $\\sigma_0^2\\sqrt{kn}/(8n)$ lower bound; a persistent violation would invalidate inequality (35) and with it the estimation-error argument.","tokens_in":24905,"feed_emoji":"📊","tokens_out":19111,"duration_ms":144092,"temperature":0.7,"pith_summary":"The paper studies a seller who posts prices for $n$ products over $T$ periods, where demand is linear in price, noisy, and each sale consumes limited shared resources. Its central claim is that one algorithmic template—solve the deterministic 'fluid' capacity problem, then round any product whose target demand is tiny down to zero—achieves logarithmic regret under full information even when the optimal fluid solution is degenerate, a case where earlier re-solving methods required a non-degeneracy assumption and could fail. When the demand model is unknown, the same template with deliberate price perturbations learns the parameters online and hits the worst-case $O(\\sqrt{T})$ regret, which is optimal. When a pre-trained informed price-demand pair with known error bound $\\varepsilon_0$ is available, the regret becomes $O(\\min\\{\\rho\\sqrt{T},\\,(\\varepsilon_0)^2 T\\}+\\log T)$, so accurate offline predictions recover the full-information logarithmic rate. The practical point is that a seller can select the right pricing policy based on how much it knows and how good its offline estimates are.","feed_headline":"Dynamic pricing: log regret without the degeneracy assumption","feed_subtitle":"Then forced exploration hits the optimal square-root-T regret, and offline price estimates interpolate.","key_machinery":"The carrying object is the 'boundary attracted re-solve' step: at time $t$, solve the fluid program with remaining capacity $c_t$ and per-period budget $c_t/(T-t+1)$, then threshold the target demand at $\\zeta(T-t+1)^{-1/2}$—coordinates below it are rounded to zero and the price is set to the modified expected demand. The threshold does double duty. It keeps every nonzero demand component large enough that zero-mean sub-Gaussian noise cannot make the realized demand flip the sign of $d^{\\pi,t}_i - \\epsilon_i^t/(T-t)$, and it deliberately parks the solution away from the degenerate face where the optimal basis is not unique. In the learning setting the same threshold is paired with an exploration perturbation $\\sigma_0 t^{-1/4} e_{t-kn}$ around the periodic re-solve anchor, which is what keeps the design matrix in the least-squares problem well conditioned and makes the estimation error shrink. The regret analysis is carried by a hybrid-policy decomposition: compare the policy that follows the algorithm up to time $t$ and then uses noiseless fluid solutions, and bound each single-step gap.","core_discovery":"On its own terms, the discovery is that degeneracy is not an obstacle if the re-solver pushes the fluid solution away from the boundary before noise acts. Algorithm 1 solves the fluid program at each remaining-horizon length, and any demand coordinate below $\\zeta(T-t+1)^{-1/2}$ is set to zero before converting the demand target to a price. Because every surviving demand is large relative to the noise that could cancel it, the one-step loss of the policy relative to a hybrid noiseless benchmark is bounded by a term of order $1/(T-t)$, and these terms sum to $O(\\zeta^2 n^2\\|B^{-1}\\|_2\\log T)$. The no-information variant (Algorithm 2) re-estimates $\\alpha,B$ by least squares every $n$ periods, prices as a momentum term plus a $\\sigma_0 t^{-1/4}$ exploration kick, and rejects estimated low-demand types; its regret is $O((\\zeta^2+\\|B^{-1}\\|_2^2)\\sqrt{T})$, matching the established lower bound. Algorithm 3 uses an informed pair $(p_0,d_0)$ with known error $\\varepsilon_0$ as an anchor, obtaining $O(\\min\\{\\rho\\sqrt{T},(\\varepsilon_0)^2 T\\}+C'\\log T)$ and, when $\\varepsilon_0=0$, recovering Algorithm 1's logarithmic bound.","pith_inferences":["The boundary-attraction threshold behaves like a shrinking confidence interval, so the same rounding idea could transfer to non-linear demand models or to other continuous-action resource-constrained bandits where degenerate faces make estimation unstable.","The estimate-then-select comparison suggests a general meta-principle: trust an offline oracle only when its error cost $(\\varepsilon_0)^2 T$ is smaller than the cost $\\sqrt{T}$ of pure online learning, a rule that could apply to other predict-then-optimize settings.","A natural robustness test is to run Algorithm 2 with and without recording the demands that the algorithm rejects before updating inventory; if the stated $O(\\sqrt{T})$ bound survives both variants the mechanism is stronger than the proof, and if it does not, a record-then-reject modification would repair the gap.","The exploration identity (35) can be checked directly by simulating the price sequence and measuring whether the minimum eigenvalue of the design matrix actually grows like $\\sqrt{kn}$; a violation would locate exactly where the no-information argument needs extra proof."],"forward_implications":["A seller with exact knowledge of a linear demand model can price with only $O(\\log T)$ regret even when the fluid optimal solution is degenerate, so the previously standard non-degeneracy condition is not needed.","With no prior information, $O(\\sqrt{T})$ regret is the best any policy can achieve, so Algorithm 2 is worst-case optimal for the linear-demand knapsack pricing problem.","Knowing an upper bound $\\varepsilon_0$ on the error of a machine-learned informed price pair changes the achievable rate: regret is $O((\\varepsilon_0)^2 T+\\log T)$ when the oracle is accurate and degrades gracefully to $O(\\sqrt{T})$ when it is not.","Without a known bound on the oracle error, no policy can uniformly beat the no-information $\\Omega(\\sqrt{T})$ worst case, so the error bound is what converts offline data into a provable speed-up.","The estimate-then-select switch compares $(\\varepsilon_0)^2 T$ with $\\rho\\sqrt{T}$ at the outset and selects between the learning policy and the informed-pair policy, giving a direct operational rule for when to trust offline estimates."],"supporting_citations":[{"why":"Establishes that the fluid optimal value bounds the expected revenue of any online policy, which defines the regret benchmark.","marker":"Gallego and Van Ryzin (1994)"},{"why":"The re-solving heuristic this paper extends; it obtained logarithmic regret for price-based revenue management under a non-degeneracy condition that Algorithm 1 removes.","marker":"Wang and Wang (2022)"},{"why":"Provides the square-root-T lower bound for dynamic pricing with an unknown demand model and the least-squares exploration technique adapted in Algorithms 2 and 3.","marker":"Keskin and Zeevi (2014)"},{"why":"Supplies the perturbation-analysis lemma (Prop 4.32) that converts parameter estimation error into fluid-solution error in the learning proofs.","marker":"Bonnans and Shapiro (2013)"},{"why":"Documents that degeneracy occurs in practice and motivates dropping the non-degeneracy assumption.","marker":"Bumpensanti and Wang (2020)"},{"why":"Contributes the hybrid single-step difference technique used to sum per-period losses and handle degeneracy.","marker":"Jiang et al. (2022)"},{"why":"Supplies the offline-data lower-bound construction used in Proposition 4.1 to show an error bound is needed to improve over no-information pricing.","marker":"Cheung and Lyu (2024)"},{"why":"Provides the Bretagnolle-Huber inequality used in the lower-bound proof of Proposition 4.1.","marker":"Lattimore and Szepesvari (2020)"},{"why":"Gives the sub-Gaussian concentration inequality used to control bad noise events in the proof of Theorem 2.1.","marker":"Wainwright (2019)"}],"fun_headline_variants":["Log-regret pricing without the degeneracy crutch","Resource constraints tamed: log regret, then sqrt(T)","Pricing with knapsacks: from full info to ML prices","Degeneracy-free log regret in dynamic pricing","Optimal sqrt(T) regret when no prior info exists"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The no-information statements stand on the assumption that the exploration schedule makes the least-squares design matrix grow at the claimed rate, and on the assumption that the regression is fed uncensored realized demands; if either fails, the estimation-error control and the $O(\\sqrt{T})$ regret bound no longer follow.","fun_headline_variants_meta":{"raw":{"variants":["Log-regret pricing without the degeneracy crutch","Resource constraints tamed: log regret, then sqrt(T)","Pricing with knapsacks: from full info to ML prices","Degeneracy-free log regret in dynamic pricing","Optimal sqrt(T) regret when no prior info exists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001169,"raw_usage":{"total_tokens":4857,"prompt_tokens":985,"completion_tokens":3872,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":3792}},"tokens_in":601,"tokens_out":3872,"duration_ms":26860,"temperature":1.0,"reasoning_tokens":3792,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:21:05.888686+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Algorithm 2 on a degenerate two-product instance and record whether the demands zeroed by the rounding rule are stored for regression. If rejected observations are excluded, refit the parameters with and without them; an estimator bias large enough to push the empirical regret past the claimed $O(\\sqrt{T})$ rate would show the proof relies on unstated uncensored-regression access. Separately, compute the minimum eigenvalue of the design matrix $P^t$ over the horizon and compare it with the claimed $\\sigma_0^2\\sqrt{kn}/(8n)$ lower bound; a persistent violation would invalidate inequality (35) and with it the estimation-error argument.","supporting_citations":[{"cited_title":"and Wang, H","cited_arxiv_id":null,"evidence_quote":"The re-solving heuristic this paper extends; it obtained logarithmic regret for price-based revenue management under a non-degeneracy condition that Algorithm 1 removes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the perturbation-analysis lemma (Prop 4.32) that converts parameter estimation error into fluid-solution error in the learning proofs."}],"review_version":1}