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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 5 Sep 2026.

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

- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [A Re-solving Heuristic with Uniformly Bounded Loss for Network Revenue Management](https://mlsanity.com/paper/1802.06192/) (2018)
- [Online Allocation and Pricing: Constant Regret via Bellman Inequalities](https://mlsanity.com/paper/1906.06361/) (2019)
- [The Bayesian Prophet: A Low-Regret Framework for Online Decision Making](https://mlsanity.com/paper/1901.05028/) (2019)
- [Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions](https://mlsanity.com/paper/2210.07996/) (2022)
- [Online Resource Allocation under Horizon Uncertainty](https://mlsanity.com/paper/2206.13606/) (2022)
- [Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations](https://mlsanity.com/paper/1912.08917/) (2019)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Infrequent Resolving Algorithm for Online Linear Programming](https://mlsanity.com/paper/2408.00465/) (2024)
- [Greedy Algorithm for Multiway Matching with Bounded Regret](https://mlsanity.com/paper/2112.04622/) (2021)
- [Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances](https://mlsanity.com/paper/2205.09078/) (2022)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy](https://mlsanity.com/paper/2607.02196/) (2026)

## Abstract (arXiv)

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. We present a primal first-order learning policy that, in each period, performs one gradient ascent update of the action coordinates associated with one request type, for a fluid relaxation in which resource overuse incurs a quadratic penalty. The policy achieves O(1) expected additive regret relative to the hindsight optimum, with a bound independent of the horizon T, under a general arrival model. This model includes independent and identically distributed arrivals with unknown probabilities, independent nonstationary arrivals with known probabilities, independent nonstationary arrivals with unknown probabilities and one historical sample path, and Markov-modulated arrivals with an unknown Markov chain. The policy does not solve any linear program, and the regret bound does not require a nondegeneracy assumption on the fluid linear program.