Metraipolis › archive › dc_b5210ea7919f
A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret — arXiv:2609.05895
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05895
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:56:25.525Z
- SHA-256 of the archived text
868711bf12bef4f4882378891f73c681a81633071bfd48f17971f153bef67ee9- Stable URL of this page
https://metraipolis.com/documento/dc_b5210ea7919f
How to cite
A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret — arXiv:2609.05895 — arXiv (en), https://arxiv.org/abs/2609.05895 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b5210ea7919f (Metraipolis archive dc_b5210ea7919f, sha256 868711bf12bef4f4882378891f73c681a81633071bfd48f17971f153bef67ee9)
BibTeX
@misc{dcb5210ea7919f,
title = {A First-Order Learning Algorithm for Online Resource Allocation with Constant Regret — arXiv:2609.05895},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05895},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b5210ea7919f; sha256 868711bf12bef4f4882378891f73c681a81633071bfd48f17971f153bef67ee9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05895. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG). Categorie arXiv: Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2609.05895 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T13:39:42.821Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).