{"id":"5314834b-6cdf-496f-9558-f441be6897ff","arxiv_id":"2501.18049","paper_version":3,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"An online pricing-and-allocation algorithm with lower-confidence-bound agent selection achieves O~(sqrt(T) mn) regret, but the proof rests on a false convexity lemma.","lead":"This paper designs an online algorithm for a seller who sets a price and warehouse inventory each period, then allocates stock to retailers after random demand arrives. It claims a near-optimal regret bound of order square-root of time, but the proof rests on a false convexity lemma.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The regret bound in Theorem 5.1 depends on piecewise convexity of W(p), which rests on Lemma B.2; that lemma is false, since f(x;θ)=θx with S(x)=[0,1−x] gives Q(x)=x(1−x), a concave function. The proof of Lemma 3.3 is therefore invalid and the claimed O~(√T) regret is unsupported.","rationale":"The reader's weakest assumption identifies exactly the flaw I find most load-bearing: Lemma B.2, used to prove Lemmas 3.3 and 3.4, is false. The counterexample f(x;θ)=θx, S(x)=[0,1−x] shows the claimed epigraph interchange is invalid, and Q(x)=x(1−x) is concave. This is not a matter of consensus or subtle boundary conditions; it is a direct contradiction of the stated lemma. The paper provides no alternative proof of piecewise convexity of W(p) or Qt(I,p), and the OCO-based Algorithms 3–5, the confidence bounds ∆K, and the LCB meta-algorithm all depend on that convexity. Consequently, Theorem 5.1's regret bound is unsupported. I see no independent support (no formal verification, no reproducible code) that would offset this. The rejection is appropriate, though the result might be salvageable with a genuinely correct proof of the needed convexity. My conclusion therefore confirms rather than changes the reader's verdict.","tokens_in":25538,"tokens_out":7911,"duration_ms":87160,"concrete_test":"Analytically verify the counterexample: instantiate Lemma B.2 with f(x;θ)=θx, x∈[0,1], and S(x)=[0,1−x]. All assumptions hold, but Q(x)=x(1−x) is concave, so Lemma B.2 is false; the equality in Eq. (21) fails because LHS is epi(x(1−x)) (non-convex) while RHS is an intersection of convex epigraphs (convex). Since Lemma B.2 is the sole support for Lemma 3.3, this settles that the proof of piecewise convexity is invalid; until a direct proof of Lemma 3.3 from Eq. (18) is supplied, Theorem 5.1 lacks a valid derivation.","verdict_should_be":"REJECT","load_bearing_attack":"The central proof chain is: Theorem 5.1 (regret O~(√(T mn)+mn)) relies on Lemmas 5.2, 5.3, and 5.5, whose agent-level sub-regret and confidence-bound arguments require Corollary B.8 and Lemma B.5, which require W(p) to be convex on each interval [C_{i_k,j_k}, C_{i_{k+1},j_{k+1}}] (Lemmas 3.4 and 3.3). The only proof of Lemma 3.3 is in Appendix B.2 via Lemma B.2, which asserts that if f(x;θ) is convex and Lipschitz in x, and S(x) is a convex, monotonically non-expanding set, then Q(x)=max_{θ∈S(x)} f(x;θ) is convex. This lemma is false. Take f(x;θ)=θx and S(x)=[0,1−x]; all hypotheses hold, but Q(x)=x(1−x), which is concave on [0,1], not convex. The flaw is the epigraph interchange in Eq. (21): ⋃_x ⋂_{θ∈S(x)} epi f(·;θ) does not equal ⋂_{θ∈S(0)} ⋃_{x∈S^{-1}(θ)} epi f(·;θ). For the counterexample, the left side is the epigraph of a concave function, while the right side is an intersection of convex epigraphs and hence convex. Since Lemma 3.3 uses this invalid step, the marginal convexity of Qt(·,p) and W(p) is unproven. The OCO agents in Algorithms 3–5 have no guaranteed convex objective, so the horizontal/vertical convergence argument and the LCB meta-algorithm collapse. Even if the specific transportation LP might be convex in special cases, the paper gives no valid proof, and the claimed near-optimal regret is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies an online joint pricing, inventory, and allocation problem with heterogeneous supply costs and unknown linear demand. It proposes a hierarchical algorithm (OCSAA) that uses a lower-confidence-bound meta-strategy over multiple zeroth-order online convex optimization agents, one per interval between sorted supply costs. The main theoretical claim is that Algorithm 2 achieves O~(sqrt(T mn) + mn) regret with high probability, matching the lower bound in T from Broder and Rusmevichientong (2012). The entire upper-bound analysis rests on structural claims that the per-period cost Q_t(I,p) is marginally convex in p on each cost interval (Lemma 3.3) and that the optimistic cost W(p) is piecewise convex (Lemma 3.4); these are proved in Appendices B.2 and B.3.","tokens_in":25999,"tokens_out":6769,"duration_ms":86303,"significance":"If the result were valid, it would be a notable contribution: a near-optimal online algorithm for joint pricing, inventory, and allocation with heterogeneous fulfillment costs, a problem that is globally nonconvex and nonsmooth. The proposed LCB meta-algorithm over local OCO agents is an interesting design and the claimed regret rate is the right target. However, the central structural lemma used to establish piecewise convexity is false as stated, and the proof of that lemma is the load-bearing step for the regret guarantee. The upper-bound result is therefore not established, and the paper cannot currently be accepted.","major_comments":[{"comment":"Lemma B.2 is false as stated, and the proof's key step is the invalid epigraph interchange in Eq. (21). Take f(x;θ)=θx and S(x)=[0,1−x] for x∈[0,1]; all hypotheses of the lemma hold (f is convex and Lipschitz in x for each θ, and S(x) is a convex set that shrinks monotonically), but Q(x)=max_{θ∈S(x)} θx = x(1−x), which is concave on [0,1]. The equality asserted in Eq. (21), namely ⋃_x ⋂_{θ∈S(x)} epi f(·;θ) = ⋂_{θ∈S(0)} ⋃_{x∈S^{-1}(θ)} epi f(·;θ), does not hold; the left side is the epigraph of a concave function, while the right side is an intersection of convex epigraphs. Since Lemma B.2 is the only proof of Lemma 3.3, the marginal convexity of Q_t(·,p) on each cost interval is unproven.","section":"Appendix B.2, Lemma B.2 and Eq. (21)"},{"comment":"The piecewise convexity of W(p) is load-bearing for the entire regret analysis: Lemma 5.2, Corollary B.8, Lemma 5.5, and Theorem 5.1 all use the convexity of W(p) on each interval [C_{i_k,j_k}, C_{i_{k+1},j_{k+1}}] to justify the quarter-point comparisons in Algorithm 3 and the LCB bounds. The proof of Lemma 3.4 in Appendix B.3 inherits Lemma 3.3 through Lemma B.3 and Lemma B.4, so it collapses as well. Without a valid proof of piecewise convexity, the agents in Algorithms 3–5 are not guaranteed a convex objective, and the O~(sqrt(T mn) + mn) regret bound of Theorem 5.1 is unsupported.","section":"Section 3.2, Lemmas 3.3–3.4 and Appendix B.3"},{"comment":"Even if Lemma 3.3 were repaired, the proof of Lemma 3.4 contains additional unjustified analytic steps: Eq. (22) differentiates through the argmin I*(p) without establishing uniqueness or differentiability; Eq. (26) assumes the second derivative ∂²Q_t(I*(p),p)/∂p² exists and is nonnegative; and Eq. (27) uses Moore-Osgood-type limit interchanges without stating the required uniform convergence. These issues are secondary to the failure of Lemma B.2, but they would also need to be addressed in any revision.","section":"Appendix B.3, Lemmas B.3 and B.4"}],"minor_comments":[{"comment":"The arXiv metadata title and abstract ('Online Pricing and Allocation with Demand Learning and Fulfillment Cost') do not match the full-text title ('Joint Pricing and Resource Allocation: An Optimal Online-Learning Approach'); please align these.","section":"Title and abstract"},{"comment":"The term 'marginal convexity' is used repeatedly but never defined; please define it explicitly, including the domain of the argument that is being varied.","section":"Section 3.1"},{"comment":"The arithmetic in lines such as 'a_{K,1}=3L_{K,1}+U_{K,1}/4' is ambiguous; it should be written as (3L_{K,1}+U_{K,1})/4, and similarly for b and c. Also, in Algorithm 3, line 23, the update 'b_{K,τ+1}←U_{K,τ}' appears to be a typo; it should presumably update the interval endpoint U_{K,τ+1}.","section":"Algorithms 2 and 3"},{"comment":"The regret decomposition uses the notations P*_{K_t} and P* that are not defined; these should be p*_{K_t} and p*, respectively, to match the earlier notation.","section":"Section 5, Eq. (9)"}],"recommendation":"reject","confidential_remarks":"The false Lemma B.2 is a genuine mathematical error in a load-bearing part of the proof, not a presentation issue. The paper's main theorem depends on the piecewise convexity of W(p), and the only supplied proof of that piecewise convexity is invalid. I would suggest that the editor weigh whether the authors should be invited to resubmit a substantially revised version with a correct structural proof; as submitted, the manuscript's central claim is not established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The problem formulation is genuinely new and worth somebody's time: joint pricing, inventory, and allocation decisions with heterogeneous fulfillment costs is a realistic and underexplored setting, and the idea of managing multiple local OCO agents with a lower-confidence-bound meta-algorithm is creative. The paper is also clearly written; the algorithm is described in enough detail that an expert could reimplement it.\n\nBut the central proof is broken. Lemma B.2, which is supposed to establish that a max over a shrinking convex feasible set remains convex, is false. The counterexample in the stress-test note is correct: take f(x;theta)=theta*x and S(x)=[0,1-x]; all conditions of the lemma hold, but Q(x)=x(1-x), which is concave. The error is in the epigraph interchange in Eq. (21): you cannot swap the union over x and the intersection over theta. The left-hand side is the epigraph of a concave function; the right-hand side is an intersection of convex epigraphs. This is a real load-bearing failure because Lemma 3.3, Lemma 3.4, and the convexity that every OCO agent relies on all depend on this false lemma. Without piecewise convexity of W(p), the horizontal/vertical confidence argument and the claimed O~(sqrt(T mn)) regret bound are unsupported.\n\nI checked the rest of the proof chain to see if the convexity might be proved another way within the paper. It is not; the only proof of Lemma 3.3 is through Lemma B.2. The paper also cites the lower bound from Broder and Rusmevichientong rather than proving it, which is fine, though the v1 abstract overstates it as new. The boundedness and concentration arguments look standard and plausible, but they sit on top of the unproved convexity.\n\nVerdict: this deserves a serious referee, but the referee should be asked to focus on whether the piecewise convexity can be established by a different route. As it stands, the main theorem does not follow from the arguments given. This is not a trivial typo; it is a mistaken lemma about convexity of parametric maxima. The authors may be able to repair it by adding assumptions on the demand model or by proving convexity of W(p) directly from the LP structure, but that has to be done in the paper. I would not cite the regret bound as is, and I would not waste a reading group on the current version, though the problem formulation is worth remembering.","headline":"The joint pricing-inventory-allocation formulation is genuinely new, but the central convexity lemma (Lemma B.2) is false, so the claimed regret bound is unproven.","tokens_in":26509,"tokens_out":2913,"would_cite":false,"duration_ms":31793,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90B80"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a lower-confidence-bound meta-algorithm over locally convex price intervals achieves $\\widetilde O(\\sqrt{T mn} + mn)$ regret for joint pricing, inventory, and fulfillment allocation, matching the…","keywords":["dynamic pricing","online resource allocation","inventory control","online convex optimization","lower-confidence bound","regret minimization","linear demand","piecewise convex objectives"],"falsifier":"Evaluate Lemma B.2 on the per-period cost with $f(x;\\theta)=\\theta x$ and $S(x)=[0,1-x]$: if the pointwise maximum $Q(x)=x(1-x)$—a concave function—arises as the actual second-stage value, the epigraph interchange in the lemma cannot be correct, and the interval-convexity premise fails. More generally, simulate the algorithm's regret on a two-warehouse, one-consumer instance with linear demand and compare the empirical regret trajectory to $\\widetilde O(\\sqrt T)$ to see whether the bound holds computationally.","tokens_in":25325,"feed_emoji":"📦","tokens_out":6525,"duration_ms":74973,"temperature":0.7,"pith_summary":"A seller must choose a uniform price and warehouse stock levels each period, then fulfill randomly realized demand through a transportation network with heterogeneous per-unit costs. The paper's central claim is that this joint (price, inventory) decision can be learned online with $\\widetilde O(\\sqrt{T mn} + mn)$ regret, optimal in $T$ up to logarithmic factors. If correct, this is the first near-optimal algorithm for online pricing combined with an allocation LP, and it shows that the globally non-convex, non-smooth objective can still be optimized by decomposing the price line into intervals of local convexity. The seller only needs the demand to be linear-and-noisy; the algorithm learns the unknown demand parameters from bandit price feedback and full-information inventory feedback.","feed_headline":"Joint pricing and inventory learning hits O(√T) regret","feed_subtitle":"A lower-confidence meta-algorithm splits prices into convex intervals and provably matches the lower bound on regret.","key_machinery":"The key machinery is the optimistic cost function $W(p)=\\min_{\\vec I} Q(\\vec I,p)$—the minimal expected net loss over inventory given price—together with the piecewise convexity Lemmas 3.3–3.4. On each interval $[C_{i_k,j_k}, C_{i_{k+1},j_{k+1}}]$ between sorted supply costs, $W(p)$ is convex, which allows local OCO agents to operate. Each agent $A_K$ runs a doubling sub-epoch scheme that estimates $W$ at three quarter-points, compares empirical values against a confidence width $\\Delta_K$, and either narrows the search interval by $3/4$ (horizontal convergence) or updates the error bar (vertical convergence). The lower-confidence-bound rule $LCB_K = \\hat W_K - \\frac34 \\Delta_K$ decides which agent to explore next, and the analysis enforces both $\\Delta_K = \\widetilde O(1/\\sqrt{T_K})$ and per-agent sub-regret $\\widetilde O(\\sqrt{T_K})$.","core_discovery":"The paper's central discovery is that the population cost $Q(\\vec I, p)$—inventory cost plus expected optimal fulfillment loss—is marginally convex in price on each interval between consecutive sorted transportation costs $C_{i_k,j_k}$, even though it is globally non-convex and non-smooth in $p$. This piecewise structure lets the algorithm assign one zeroth-order online convex optimization agent to each of the $mn+1$ intervals and run them under a lower-confidence-bound meta-algorithm. The meta-algorithm selects the agent with the smallest estimated lower bound on its local optimum; each agent simultaneously shrinks its horizontal search interval and tightens its vertical value uncertainty. The regret decomposes into per-agent sub-regrets of order $\\widetilde O(\\sqrt{T_K})$ plus meta-level selection error, yielding the overall $\\widetilde O(\\sqrt{T mn} + mn)$ bound with probability $1-\\epsilon$.","pith_inferences":["The horizontal/vertical confidence machinery is not specific to transportation LPs; the same two-sided shrinkage could apply to any bandit problem whose value function is piecewise convex with known breakpoints, suggesting testable extensions to assortment or network-revenue settings.","If the interval-convexity lemma were to fail for some demand model, the LCB/OCO decomposition would lose its convex objective; checking that lemma is the fastest falsification of the claimed rate.","The uniform-price assumption means the algorithm cannot exploit consumer heterogeneity; a natural extension is to allow per-consumer prices, which would add an $n$-dimensional price search and likely change the metric from $mn$ to a dependence on the price-action geometry."],"forward_implications":["A seller can jointly set price and inventories in a multi-warehouse network without knowing the demand curve, losing only $\\widetilde O(\\sqrt{T mn} + mn)$ cumulative profit relative to the clairvoyant optimum.","The rate matches the information-theoretic lower bound for the single-supplier, single-consumer case, so the $T$-dependence cannot be improved in general.","The algorithm runs in polynomial time for rational-polytope inventory sets, pairing the theoretical guarantee with a computable procedure.","The proof technique—decomposing the non-convex price domain into locally convex intervals and orchestrating local OCO agents with an LCB meta-algorithm—provides a template for other non-convex learning-to-optimize problems with bandit feedback.","Under non-linear demand families the same decomposition would yield $\\widetilde O(T^\\alpha (mn)^{1-\\alpha})$ regret, with $\\alpha \\ge 1/2$ depending on the demand family, interpolating between the current rate and slower continuum-bandit rates."],"supporting_citations":[{"why":"Supplies the information-theoretic lower bound $\\Omega(\\sqrt T)$ that the paper matches in $T$.","marker":"Broder and Rusmevichientong (2012)"},{"why":"Provides the zeroth-order stochastic convex optimization scheme each local agent uses to estimate $W(p)$ at query points.","marker":"Agarwal et al. (2011)"},{"why":"Established the pricing-with-fixed-stock baseline that this work extends to heterogeneous supply and per-period inventory.","marker":"Besbes and Zeevi (2009)"},{"why":"Gives the continuum-armed-bandit $\\Omega(T^{2/3})$ lower bound that motivates the piecewise-convex improvement to $\\sqrt T$.","marker":"Kleinberg (2004)"},{"why":"Shows the $O(T^{(k+1)/(2k+1)})$ rate for $k$-th smooth demand, the baseline that the piecewise-convex structure outperforms.","marker":"Wang et al. (2021a)"},{"why":"Models censored-demand pricing-and-inventory learning, a related setting without heterogeneous fulfillment costs.","marker":"Chen et al. (2021a)"}],"fun_headline_variants":["Optimal regret for joint pricing and inventory with fulfillment costs","New algorithm matches lower bound for pricing-inventory learning","OCSAA achieves O(√T) regret for non-convex pricing and inventory","Tackling non-smooth demand learning: optimal pricing and inventory","O(√T) regret is optimal for pricing and inventory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument hangs on the claim that, for a linear demand model, the per-period expected cost is convex in the price inside each interval between two consecutive transportation costs, so that each local agent has a convex function to optimize.","fun_headline_variants_meta":{"raw":{"variants":["Optimal regret for joint pricing and inventory with fulfillment costs","New algorithm matches lower bound for pricing-inventory learning","OCSAA achieves O(√T) regret for non-convex pricing and inventory","Tackling non-smooth demand learning: optimal pricing and inventory","O(√T) regret is optimal for pricing and inventory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000994,"raw_usage":{"total_tokens":4168,"prompt_tokens":859,"completion_tokens":3309,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":3220}},"tokens_in":475,"tokens_out":3309,"duration_ms":27220,"temperature":1.0,"reasoning_tokens":3220,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T00:54:30.328609+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate Lemma B.2 on the per-period cost with $f(x;\\theta)=\\theta x$ and $S(x)=[0,1-x]$: if the pointwise maximum $Q(x)=x(1-x)$—a concave function—arises as the actual second-stage value, the epigraph interchange in the lemma cannot be correct, and the interval-convexity premise fails. More generally, simulate the algorithm's regret on a two-warehouse, one-consumer instance with linear demand and compare the empirical regret trajectory to $\\widetilde O(\\sqrt T)$ to see whether the bound holds computationally.","supporting_citations":[{"cited_title":"P., Hsu, D","cited_arxiv_id":null,"evidence_quote":"Provides the zeroth-order stochastic convex optimization scheme each local agent uses to estimate $W(p)$ at query points."},{"cited_title":"and Zeevi, A","cited_arxiv_id":null,"evidence_quote":"Established the pricing-with-fixed-stock baseline that this work extends to heterogeneous supply and per-period inventory."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the continuum-armed-bandit $\\Omega(T^{2/3})$ lower bound that motivates the piecewise-convex improvement to $\\sqrt T$."}],"review_version":1}