SOURCE-LINKED INTELLIGENCE

A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret

arXiv · AI, language, vision and robotics · article · Sep 5, 2026 · UTC

We study a finite-horizon online resource allocation problem with initial resource capacities proportional to the horizon. In each period, a request type is observed and one action is chosen from a finite menu. Each action earns a reward and consumes a vector of resources. The arrival types are independent and identically distributed, but their probabilities are unknown. We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with the current request type. The policy achieves $O(1)$ expected additive regret

Read original source ↗ Open in workspace

recordType

paper

region

Global