Search papers, labs, and topics across Lattice.
This paper investigates online resource allocation in scenarios where both rewards and consumption sizes are continuously distributed, focusing on the implications of degeneracy in the model. The authors establish that the additive regret is influenced by the size-weighted mass of requests near acceptance cutoffs, introducing an active weighted-mass exponent \( p \) that characterizes the difficulty of the problem. Notably, they demonstrate that a sample-path marginal policy can achieve \( O((\log T)^2) \) regret when \( p = 1 \), contrasting with a lower bound of \( T^{1/2 - 1/(2p)} \) for \( p > 1 \).
Achieving sub-linear regret in online resource allocation is possible even under challenging degeneracy conditions, challenging conventional wisdom about regret bounds.
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.
