Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

Zhaohua Chen

cs.LGOct 7, 2026

Online Resource Allocation with an Endogenous Markov State: Fewer LP Solves Earn More

Authors: Zhaohua Chen

Organizations: Taobao & Tmall Group of Alibaba, Renmin University of China

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 $Θ(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $Ω(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.

Figures & tables

Policy	Optimal induced kernel irreducible		Optimal induced kernel reducible
	unique, non-degen.	unique, degen.	unique, non-degen.
FR	${O}(1)$	${\Theta}({T})$	${\Theta}({T})$
IR	${O}(1)$	${\Theta}(\sqrt{{T}})$	${\Theta}({T})$
Best policy	${O}(1)$	${\Theta}(\sqrt{{T}})$	${\Theta}({T})$

Table 1 : Known-prior regret relative to the transient fluid benchmark.

Policy	Known optimal target state class		Unknown optimal target state class
	unique, non-degen.	unique, degen.	unique, degen.
UIR-UP	${O}(1)$	${\Theta}(\sqrt{{T}})$	—
Best policy	${O}(1)$	${\Theta}(\sqrt{{T}})$	${\Theta}({T})$

Table 2 : Unknown-prior regret relative to the transient fluid benchmark.

Algorithm	Prior	Re-solving	Description
FR	known	${\Theta}({T})$	Algorithm 1 .
IR	known	${\Theta}(\log\log{T})$	Algorithm 2 .
FRT	known	${\Theta}({T})$	FR with thresholding.
IRT	known	${\Theta}(\log\log{T})$	IR with thresholding.
FR-UP	unknown	${\Theta}({T})$	FR with the request prior replaced by ${\widehat{p}^{{n}}}$ .
UIR-UP	unknown	${\Theta}(\log\log{T})$ , three phases	Algorithm 3 .

Table 3: Algorithms used in the experiments.

State	Action	Outcome for request ${j}$
${A}$	$0$	$({B};0;(0,0))$
${A}$	${u}$	$({B};1;(3/2,1/2))$
${A}$	${v}$	$({B};1+{b_{{j}}};(5/2,3/2))$
${B}$	$0$	$({A};0;(0,0))$
${B}$	${u}$	$({A};1;(1/2,3/2))$
${B}$	${v}$	$({C};1-{d_{{j}}};(1/2,3/2))$

Table 4: Primitive data of the experimental environment. Each entry in the last column is

(\text{next state};\text{reward};\text{resource-consumption vector})

Panel of Figure 1 — Figure 1 : Mean regret against the transient fluid LP with a known request prior.

Panel of Figure 2 — Figure 2 : Mean regret against the transient fluid LP with an unknown request prior.

	Known prior		Unknown prior
${\rho_{1}}$	FR (200)	IR (1,000)	FR-UP (200)	UIR-UP (1,000)
$0.995$	$100.725$	$5.535$	$87.568$	$1.947$
$1$	$15{,}285.072$	$1.704$	$15{,}266.652$	$1.000$
	FRT (200)	IRT (1,000)	FRT-UP (200)	UIRT-UP (1,000)
$0.995$	$6.854$	$6.009$	$6.303$	$8.001$
$1$	$7.230$	$2.351$	$6.250$	$1.000$

Table 5: Mean regret against the transient fluid LP at

{T}=32{,}000

. Parentheses give the number of trials.

Panel of Figure 3 — Figure 3 : Mean regret against the transient fluid LP, with $95\%$ confidence intervals, as a function of the first resource’s capacity ratio ${\rho_{1}}$ at ${T}=2000$ . All other model primitives are unchanged.

	Known prior				Unknown prior
${\rho_{1}}$	FR	IR	FRT	IRT	FR-UP	UIR-UP	FRT-UP	UIRT-UP
$0.998$	$203.055$	$2.467$	$6.794$	$2.209$	$207.775$	$1.485$	$5.971$	$1.512$
$0.999$	$318.835$	$2.623$	$6.901$	$1.934$	$307.075$	$1.457$	$5.734$	$1.278$
$1.000$	$1{,}016.932$	$2.090$	$6.860$	$2.219$	$1{,}011.322$	$1.000$	$6.360$	$1.000$
$1.001$	$1.000$	$1.090$	$1.000$	$1.000$	$1.000$	$1.081$	$1.000$	$1.000$
$1.002$	$1.000$	$1.102$	$1.000$	$1.000$	$1.000$	$1.087$	$1.000$	$1.000$

Table 6: Mean regret against the transient fluid LP near the capacity-ratio boundary at

{T}=2000

Panel of Figure 4 — Figure 4 : Mean regret for constant-frequency re-solving.

Explore similar work

Infrequent Resolving Algorithm for Online Linear Programming
Aug 1, 2024Guokai Li, Zizhuo Wang, Jingwei ZhangLinear Programming \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China
Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy
Jul 2, 2026Jiawei Zhang\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret
Stern School of Business New York University
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
Sep 23, 2026Jiameng LyuLinear Programming Learning-Augmented Algorithms
Department of Management Science, School of Management, Fudan University, Shanghai 200433, China

Aug 1, 2024, cs.DSJ/K move · Enter open · S save

Infrequent Resolving Algorithm for Online Linear Programming

Guokai Li, Zizhuo Wang, Jingwei Zhang

School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China

Linear Programming \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Free

Open paper AskPDF arXiv

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications such as online auctions, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former typically guarantees better performance but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithms only require first-order computations but induce a worse performance. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard "degenerate" case) while solving LPs only

O(\log\log T)

times over the time horizon

T

. Moreover, when we are allowed to solve LPs only

M

times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly

O\left(T^{(1/2)^{M-1}}\right)

regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

Abstract

Explore similar work

Infrequent Resolving Algorithm for Online Linear Programming

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving