# Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

arXiv: https://arxiv.org/abs/2607.02196 · HTML: https://mlsanity.com/paper/2607.02196/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 45 references that are in the map.
- First posted on arXiv 2 Jul 2026.

## Builds on (most cited first, 5 of 5)

- [Online Resource Allocation with Stochastic Resource Consumption](https://mlsanity.com/paper/2012.07933/) (2020)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Beyond Non-Degeneracy: Revisiting Certainty Equivalent Heuristic for Online Linear Programming](https://mlsanity.com/paper/2501.01716/) (2025)
- [Hoffman constant of the argmin mapping in linear optimization](https://mlsanity.com/paper/2307.01034/) (2023)

## Built on by (most cited first, 1 of 1)

- [A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret](https://mlsanity.com/paper/2609.05895/) (2026)

## Abstract (arXiv)

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 T1/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(√T) regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.