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

Aug 1, 2024cs.DS

Infrequent Resolving Algorithm for Online Linear Programming

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.

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

Ask PDF

Jul 2, 2026cs.LG

Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy

We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on an observable request type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose value-to-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least

T^{1/2 - 1/(2p)}

, and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains

O((\log T)^2)

regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves

o(\sqrt{T})

regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.

Jiawei Zhang

Stern School of Business New York University

\Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Regret Queue Control Minimax Rate Slow Relaxation Modes

Ask PDF

Sep 23, 2026cs.LG

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

The growth of large language model (LLM) inference and search services increases the scale of online linear programming problems, motivating computationally efficient algorithms. We develop resource-adaptive stochastic gradient descent (RASGD) for stochastic online linear programming. The algorithm uses one request and current inventory to update resource prices, requiring O(m) operations for m resources and memory per arrival and no LP or sample-average optimization. The central idea is to express the current-resource pricing logic of re-solving through a first-order SGD update: each arrival refreshes the remaining-inventory allowance in the dual objective, while the stepsize decreases for early learning and increases later to match the speed of inventory adjustment. Under standard non-degeneracy conditions, our algorithm is feasible on every sample path and achieves O(\log T) expected regret against the realized fractional hindsight optimum, which matches the lower bound, even for policies that know the distribution and have unrestricted computation. The analysis converts curvature around the fixed reference price into inventory stability without tracking optimal prices at changing resource levels. Numerical experiments show that RASGD achieves regret competitive with per-arrival LP re-solving and improves upon the tested first-order baselines, while retaining the computational efficiency of first-order methods. These results establish RASGD as a computationally efficient approach to achieving high allocation quality in large-scale OLP.

Jiameng Lyu

Department of Management Science, School of Management, Fudan University, Shanghai 200433, China

Linear Programming Learning-Augmented Algorithms Stochastic Optimization

Ask PDF