arXiv：cs.LG· Zhaohua Chen·· 4 小时前AI 评分29
内生的 Markov 状态下的在线资源分配：更少的 LP 求解反而收获更多
Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More
AI 导读
研究带 i.i.d. 请求与内生 Markov 状态的有限期在线资源分配，证明在不频繁重求解下，非退化最优可达 O(1) regret，而退化最优时频繁重求解可能招致 Ω(T) 的 regret。针对未知请求先验，提出三阶段 U 型不频繁重求解策略，仅需 O(log log T) 次 LP 求解，在不可约性与目标状态类信息下分别取得 O(1) 和 O(sqrt(T)) regret。
正文
Abstract: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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.09577 [cs.LG] |
| (or arXiv:2610.09577v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.09577 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Zhaohua Chen [view email]
[v1]
Wed, 7 Oct 2026 07:21:03 UTC (152 KB)
来源：arXiv：cs.LG · arxiv.org