Pith. sign in

REVIEW 4 minor 45 references

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

T0 review · 0 major / 4 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read When rewards and consumption sizes are both continuous, online allocation regret is set by how much size-weighted ratio mass sits near active cutoffs, not by fluid non-degeneracy.

desk verdict Matching rates under continuous size+reward and fluid degeneracy, pinned to one mass exponent p—clean theory that drops the usual non-degeneracy assumptions. read the letter →

arxiv 2607.02196 v2 pith:OMO4KSZE submitted 2026-07-02 cs.LG

Jiawei Zhang This is my paper · ORCID
classification cs.LG MSC 90C1590B0568W2760G40
keywords onlineresourceallocationadditiveregretcontinuousrandomconsumptionfluiddegeneracyvalue-to-sizeratioactiveweighted-massexponentsample-pathmarginalpolicynetworkrevenuemanagement
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies irrevocable accept/reject decisions for scarce resources when each request has a continuous random reward and a continuous random size that scales a fixed type-specific consumption vector. It shows that additive regret against the fractional hindsight optimum is controlled by a single distributional quantity: the size-weighted mass of value-to-size ratios near the active acceptance cutoffs, measured by an active weighted-mass exponent p. When that mass grows linearly (p = 1), a sample-path marginal policy that prices capacity by the expected hindsight drop along a capacity sweep attains O((log T)^2) regret; when the mass is thinner (p > 1), every online policy must suffer order T^{1/2-1/(2p)} regret, and the same policy matches that polynomial rate up to logs. The result holds even when the fluid LP is primal-degenerate or dual-nonunique, so continuous random consumption can create a genuine polynomial price of degeneracy at critical capacities while non-critical capacities remain polylogarithmic for the same primitives.

What carries the argument

The active weighted-mass exponent p (how fast size-weighted ratio mass accumulates near cutoffs) together with the sample-path marginal (SPM) policy, which prices each request by the average of pathwise offline bid-price cutoffs along the capacity segment it would consume; regret reduces to a stable product of cutoff width and borderline mass, closed by p.

What would settle it

Build a one-resource instance whose size-weighted ratio mass near the critical cutoff grows like width^p for a chosen p > 1 (e.g., independent uniform value and Beta size), run any online policy at capacity equal to mean total demand, and check whether regret stays o(T^{1/2-1/(2p)}) as T grows; the paper claims it cannot.

Watch

Extended reading notes

Core claim

Additive regret in continuous-reward, continuous-size online resource allocation is governed by the active weighted-mass exponent p of the size-weighted ratio measures near acceptance cutoffs: the sample-path marginal policy achieves O((log T)^2) when p = 1 and O(T^{1/2-1/(2p)} polylog T) when p > 1, and for every p > 1 there exist instances on which every online policy incurs Ω(T^{1/2-1/(2p)}) regret, all without any fluid non-degeneracy assumption.

Load-bearing premise

The size-weighted ratio mass near cutoffs must grow at least like a power of the band width, and conditional-on-size curvature can concentrate only in a limited power-law corner form that integrates after averaging over size.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies online accept/reject resource allocation with continuous rewards and continuous scalar sizes that scale fixed type-specific consumption vectors, allowing fluid degeneracy. It introduces an active weighted-mass exponent p that measures size-weighted value-to-size ratio mass near active cutoffs (Assumption 1). Under this regularity, the sample-path marginal policy (SPM) attains O((log T)^2) regret when p=1 and O(T^{1/2-1/(2p)} polylog T) when p>1 (Theorem 2.5); a matching lower bound of order T^{1/2-1/(2p)} holds for every p>1 on one-resource endpoint-contact families (Theorem 4.2). The analysis reduces regret to Jensen gaps of pathwise marginals, averages cutoffs along capacity sweeps, controls the product of cutoff width and borderline mass via Hoffman-type stability plus Young absorption, and handles non-dominated corners by an endpoint Hardy estimate. Corollaries recover polylog rates for independent size/ratio with bounded density and T^{1/4} for independent uniform reward and size.

Significance. If correct, the work cleanly separates dual non-uniqueness from the true price of continuous random consumption: the latter is the thinness of size-weighted ratio mass near cutoffs, quantified by a single exponent p. Matching upper and lower bounds without fluid non-degeneracy fill a genuine gap left by Jiang et al. (2025a), Besbes et al. (2025), Lueker (1998), and related CE/resolving analyses that either assume non-degeneracy or rule out continuous sizes. The technical toolkit (sweep averaging, active-mass product stability, endpoint Hardy) is reusable, and the capacity-local refinement (Appendix B) correctly isolates polynomial regret as a critical-capacity phenomenon. Full proofs are supplied end-to-end; the contribution is therefore a sharp, self-contained theory result of clear interest to online allocation and revenue management.

minor comments (4)
  1. The single-type sharpening remark after Examples 1–2 (that O((log T)^2) can be improved to O(log T) when there is only one scalar cutoff) is left as an informal note; a short formal statement or pointer would help readers who specialize to the classical knapsack.
  2. Notation for the capacity-sweep parameter θ (Section 3) collides with the local contact exponent θ of Definitions 2.2–2.4; a one-line reminder at first use in each appendix would reduce cognitive load.
  3. Appendix C.1’s dual calculations for the two running examples are useful; a brief cross-reference from the introduction examples to C.1 would make the dual-interval claim easier to verify on a first reading.
  4. A few long sentences in Section 1.3 (roadmap) and the proof of Lemma 3.9 could be broken for readability; the logic is sound but dense.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: p is a distributional regularity parameter, and matching upper/lower bounds are proved self-contained from Assumption 1.

full rationale

This is a pure minimax theory paper. The active weighted-mass exponent p is defined from the arrival law via the size-weighted ratio measures μ_k (Assumption 1: c ℓ_k(I)^p ≤ μ_k(I) ≤ C ℓ_k(I), plus dominated/endpoint-contact structure). Theorem 2.5 then proves that SPM attains rates governed by that same p, via an explicit chain (Bellman reduction Prop. 3.1 → marginal-to-cutoff Lem. 3.3 → projected-hull Jensen Lem. 3.4–3.5 → pre-Young stability Prop. 3.6 + Young absorption Lem. 3.7 → Prop. 3.8 → concentration and endpoint Hardy Lem. A.7 / Lem. 3.9). Theorem 4.2 constructs one-resource endpoint-contact families realizing every p>1 and proves a matching Ω(T^{1/2-1/(2p)}) lower bound by a two-point dilemma; the construction uses only the same mass estimates (Lem. 4.1) that define p. Nothing is fitted to data; no equation equates the claimed regret to a quantity defined by the regret itself. Self-citations (Zhang 2026a on (log T)^2 tightness in a related discrete-consumption setting; Zhang 2026b companion on unknown distributions) are complementary and not used as black-box inputs that force the present rates. Defining a regularity exponent and proving matching rates in terms of it is standard non-circular theory.

Assumptions & free parameters 0 free parameters · 5 assumptions · 3 invented entities

The paper is pure theory. Load-bearing ingredients are standard probability/LP facts plus the modeling and regularity assumptions that define the class of instances. No free parameters are fitted; the exponent p is a property of the given distribution. The sample-path marginal policy and the contact-branch representation are definitional devices, not new physical entities.

assumptions (5)
  • domain assumption Requests arrive i.i.d.; type probabilities π_k>0 fixed; capacity scales linearly b_T=Θ(T).
    Standard fluid scaling for additive-regret analysis in online allocation (Sec. 2.1).
  • domain assumption Conditional on type, size and reward have compact supports bounded away from zero; value-to-size ratios lie in [0,y].
    Boundedness used for Lipschitz constants, dual clipping, and concentration envelopes (Sec. 2.2).
  • ad hoc to paper Assumption 1: single-interval support of μ_k, active-mass sandwich cℓ^p ≤ μ ≤ Cℓ, finite cover by dominated or endpoint-contact neighborhoods with power-law branch densities.
    The precise regularity class that makes the product bound and Hardy estimate close; without it the rates need not hold (Def. 2.2–2.4, Ass. 1).
  • standard math Hoffman (1952) stability for linear inequality systems and classical LP sensitivity (Boyd-Vandenberghe).
    Used for projected comparison of nearby empirical fluid solutions (Lem. A.2–A.4).
  • standard math Fractional hindsight OPT differs from binary hindsight by at most d·v (basic solutions have ≤ d fractionals).
    Justifies using the fractional benchmark for the same asymptotic rates (Sec. 2.1).
invented entities (3)
  • active weighted-mass exponent p independent evidence
    purpose: Single scalar that interpolates between polylog and polynomial regret regimes via the lower growth rate of size-weighted ratio mass near active cutoffs.
    Defined from the arrival distribution (Ass. 1); not postulated independently of the data-generating process. Independent evidence is the matching lower-bound construction for every p>1.
  • sample-path marginal policy (SPM) independent evidence
    purpose: Accept if realized reward exceeds the expected drop in future fractional hindsight value caused by reserving the consumed capacity.
    Algorithmic object realizing the RAMS principle; well-defined without dual selection. Independent evidence is the matching upper bound proved for it.
  • endpoint-contact branch / contact submeasure independent evidence
    purpose: Local representation of ratio mass that accumulates only as size moves away from a corner of the joint support, enabling the Hardy integral estimate.
    Technical device inside Ass. 1 for the continuous-consumption case; falsifiable by checking whether a given density admits such a power-law edge map.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy." pith.science (2026). https://pith.science/paper/OMO4KSZE

@misc{pith2026260702196,
  author       = {Pith},
  title        = {Pith review of: Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OMO4KSZE}},
  note         = {Machine review of arXiv:2607.02196}
}
abstract

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least $T^{1/2 - 1/(2p)}$, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains $O((\log T)^2)$ regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves $o(\sqrt{T})$ regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 4 linked inside Pith

  1. [1]

    A dynamic near-optimal algorithm for online linear programming

    Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62 0 (4): 0 876--890, 2014

    2014

  2. [2]

    Uniformly bounded regret in the multisecretary problem

    Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisecretary problem. Stochastic Systems, 9 0 (3): 0 231--260, 2019

    2019

  3. [3]

    Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards

    Alessandro Arlotto and Xinchang Xie. Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards. Stochastic Systems, 10 0 (2): 0 170--191, 2020

    2020

  4. [4]

    Online resource allocation with limited flexibility

    Arash Asadpour, Xuan Wang, and Jiawei Zhang. Online resource allocation with limited flexibility. Management Science, 66 0 (2): 0 642--666, 2020

    2020

  5. [5]

    Balseiro, Omar Besbes, and Dana Pizarro

    Santiago R. Balseiro, Omar Besbes, and Dana Pizarro. Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research, 72 0 (5): 0 2168--2189, 2024

    2024

  6. [6]

    Balseiro, Haihao Lu, and Vahab Mirrokni

    Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 71 0 (1): 0 101--119, 2023

    2023

  7. [7]

    Good prophets know when the end is near

    Siddhartha Banerjee and Daniel Freund. Good prophets know when the end is near. Management Science, 71 0 (6): 0 4877--4894, 2025

    2025

  8. [8]

    Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances

    Omar Besbes, Yash Kanoria, and Akshit Kumar. Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances. Operations Research, 73 0 (3): 0 1273--1288, 2025

    2025

Show all 45 references
  1. [9]

    Improved approximation results for stochastic knapsack problems

    Anand Bhalgat, Ashish Goel, and Sanjeev Khanna. Improved approximation results for stochastic knapsack problems. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1647--1665, 2011

    2011

  2. [10]

    Boyd, Stephen, Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press

    2004

  3. [11]

    Robert L. Bray. Logarithmic regret in multisecretary and online linear programs with continuous valuations. Operations Research, 73 0 (4): 0 2188--2203, 2025

    2025

  4. [12]

    A re-solving heuristic with uniformly bounded loss for network revenue management

    Pornpawee Bumpensanti and He Wang. A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66 0 (7): 0 2993--3009, 2020

    2020

  5. [13]

    Camacho, M

    J. Camacho, M. J. C \'a novas, H. Gfrerer, and J. Parra. Hoffman constant of the argmin mapping in linear optimization. arXiv preprint arXiv:2307.01034, version 2, 2026

    2026 arXiv

  6. [14]

    Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming

    Yilun Chen and Wenjia Wang. Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming. arXiv preprint arXiv:2501.01716, 2025

    2025 arXiv

  7. [15]

    Dean, Michel X

    Brian C. Dean, Michel X. Goemans, and Jan Vondr \'a k. Adaptivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 395--404, 2005

    2005

  8. [16]

    Dean, Michel X

    Brian C. Dean, Michel X. Goemans, and Jan Vondr \'a k. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research, 33 0 (4): 0 945--964, 2008

    2008

  9. [17]

    Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs

    Paul D \"u tting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM Journal on Computing, 49 0 (3): 0 540--582, 2020

    2020

  10. [18]

    Overbooking with bounded loss

    Daniel Freund and Jiayu Zhao. Overbooking with bounded loss. Mathematics of Operations Research, 48 0 (3): 0 1344--1363, 2023

    2023

  11. [19]

    Optimal dynamic pricing of inventories with stochastic demand over finite horizons

    Guillermo Gallego and Garrett van Ryzin. Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Science, 40 0 (8): 0 999--1020, 1994

    1994

  12. [20]

    Beyond O( T) Regret: Decoupling Learning and Decision-making in Online Linear Programming

    Wenzhi Gao, Dongdong Ge, Chenyu Xue, Chunlin Sun, and Yinyu Ye. Beyond O( T) Regret: Decoupling Learning and Decision-making in Online Linear Programming. arXiv preprint arXiv:2501.02761, 2025

    2025 arXiv

  13. [21]

    Greedy algorithm for multiway matching with bounded regret

    Varun Gupta. Greedy algorithm for multiway matching with bounded regret. Operations Research, 72 0 (3): 0 1139--1155, 2024

    2024

  14. [22]

    Siqi He, Yehua Wei, Jiaming Xu, and Sophie H. Yu. Online resource allocation without re-solving: The effectiveness of primal-dual policies. Working paper, SSRN 5133857, 2025

    2025

  15. [23]

    Alan J. Hoffman. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 49 0 (4): 0 263--265, 1952

    1952

  16. [24]

    A re-solving heuristic with bounded revenue loss for network revenue management with customer choice

    Stefanus Jasin and Sunil Kumar. A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37 0 (2): 0 313--345, 2012

    2012

  17. [25]

    Online stochastic optimization with W asserstein-based nonstationarity

    Jiashuo Jiang, Xiaocheng Li, and Jiawei Zhang. Online stochastic optimization with W asserstein-based nonstationarity. Management Science, 71 0 (11): 0 9104--9122, 2025

    2025

  18. [26]

    Degeneracy is OK : Logarithmic regret for network revenue management with indiscrete distributions

    Jiashuo Jiang, Will Ma, and Jiawei Zhang. Degeneracy is OK : Logarithmic regret for network revenue management with indiscrete distributions. Operations Research, 73 0 (6): 0 3405--3420, 2025

    2025

  19. [27]

    Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack

    Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Operations Research, 73 0 (3): 0 1703--1721, 2025

    2025

  20. [28]

    Online resource allocation with stochastic resource consumption

    Jiashuo Jiang and Jiawei Zhang. Online resource allocation with stochastic resource consumption. arXiv preprint arXiv:2012.07933, 2020

    2012 arXiv

  21. [29]

    o nnis, and Berthold V \

    Thomas Kesselheim, Klaus Radke, Andreas T \"o nnis, and Berthold V \"o cking. Primal beats dual on online packing LP s in the random-order model. SIAM Journal on Computing, 47 0 (5): 0 1939--1964, 2018

    1939

  22. [30]

    Kleywegt and Jason D

    Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem. Operations Research, 46 0 (1): 0 17--35, 1998

    1998

  23. [31]

    Kleywegt and Jason D

    Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem with random sized items. Operations Research, 49 0 (1): 0 26--41, 2001

    2001

  24. [32]

    Online linear programming: Dual convergence, new algorithms, and regret bounds

    Xiaocheng Li and Yinyu Ye. Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research, 70 0 (5): 0 2948--2966, 2022

    2022

  25. [33]

    Simple and fast algorithm for binary integer and online linear programming

    Xiaocheng Li, Chunlin Sun, and Yinyu Ye. Simple and fast algorithm for binary integer and online linear programming. Mathematical Programming, 200: 0 831--875, 2023

    2023

  26. [34]

    Infrequent resolving algorithm for online linear programming

    Guokai Li, Zizhuo Wang, and Jingwei Zhang. Infrequent resolving algorithm for online linear programming. arXiv preprint arXiv:2408.00465, 2024

    2024

  27. [35]

    George S. Lueker. Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms, 29 0 (2): 0 277--305, 1998

    1998

  28. [36]

    Improvements and generalizations of stochastic knapsack and M arkovian bandit approximation algorithms

    Will Ma. Improvements and generalizations of stochastic knapsack and M arkovian bandit approximation algorithms. Mathematics of Operations Research, 43 0 (3): 0 789--812, 2018

    2018

  29. [37]

    Wanteng Ma, Ying Cao, Danny H. K. Tsang, and Dong Xia. Optimal regularized online allocation by adaptive re-solving. Operations Research, 73 0 (4): 0 2079--2096, 2025

  30. [38]

    Stochastic on-line knapsack problems

    Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68: 0 73--104, 1995

    1995

  31. [39]

    Reiman and Qiong Wang

    Martin I. Reiman and Qiong Wang. An asymptotically optimal policy for a quantity-based network revenue management problem. Mathematics of Operations Research, 33 0 (2): 0 257--282, 2008

    2008

  32. [40]

    Talluri and Garrett J

    Kalyan T. Talluri and Garrett J. van Ryzin. The Theory and Practice of Revenue Management. Springer, 2004

    2004

  33. [41]

    The Bayesian prophet: A low-regret framework for online decision making

    Alberto Vera and Siddhartha Banerjee. The Bayesian prophet: A low-regret framework for online decision making. Management Science, 67 0 (3): 0 1368--1391, 2021

    2021

  34. [42]

    Online allocation and pricing: Constant regret via B ellman inequalities

    Alberto Vera, Siddhartha Banerjee, and Itai Gurvich. Online allocation and pricing: Constant regret via B ellman inequalities. Operations Research, 69 0 (3): 0 821--840, 2021

    2021

  35. [43]

    Yehua Wei, Jiaming Xu, and Sophie H. Yu. Constant regret primal-dual policy for multi-way dynamic matching. Working paper, SSRN 4357216, 2023

    2023

  36. [44]

    Tight lower bounds for the multi-secretary problem via B ellman certificates

    Jiawei Zhang. Tight lower bounds for the multi-secretary problem via B ellman certificates. SSRN working paper, abstract no. 6772762, posted May 22, 2026, revised June 3, 2026. Available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=6772762

    2026

  37. [45]

    Online resource allocation with continuously distributed reward and consumption: unknown distributions case

    Jiawei Zhang. Online resource allocation with continuously distributed reward and consumption: unknown distributions case. Working paper, 2026

    2026

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.