Metraipolis › archive › dc_4e9509af26f0
Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More — arXiv:2610.09577
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.09577
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T11:56:46.324Z
- SHA-256 of the archived text
086787b52761b7c3aac1542f73755d89a4fe6ca4d5ff317080f48d9c7b4404e4- Stable URL of this page
https://metraipolis.com/documento/dc_4e9509af26f0
How to cite
Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More — arXiv:2610.09577 — arXiv (en), https://arxiv.org/abs/2610.09577 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e9509af26f0 (Metraipolis archive dc_4e9509af26f0, sha256 086787b52761b7c3aac1542f73755d89a4fe6ca4d5ff317080f48d9c7b4404e4)
BibTeX
@misc{dc4e9509af26f0,
title = {Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More — arXiv:2610.09577},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.09577},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e9509af26f0; sha256 086787b52761b7c3aac1542f73755d89a4fe6ca4d5ff317080f48d9c7b4404e4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.09577. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $\Theta(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $\Omega(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.09577 — 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-08T10:50:37.696Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).