Wait-Less Offline Tuning and Re-solving for Online Decision Making
Authors: Jingruo Sun
Wenzhi Gao
Ellen Vitercik
Yinyu Ye
Venue: ICML 2025 poster (2025)
Keywords: Online Linear Programming
Sequential Decision Making
Resource Allocation
Primary area: general_machine_learning->online_learning_active_learning_and_bandits

Abstract: Online linear programming (OLP) has found broad applications in revenue management and resource allocation. State-of-the-art OLP algorithms achieve low regret by repeatedly solving linear programming (LP) subproblems that incorporate updated resource information. However, LP-based methods are computationally expensive and often inefficient for large-scale applications. By contrast, recent first-order OLP algorithms are more computationally efficient but typically suffer from weaker regret guarantees. To address these shortcomings, we propose a new algorithm that combines the strengths of LP-based and first-order OLP algorithms. Our algorithm re-solves the LP subproblems periodically at a predefined frequency $f$ and uses the latest dual prices to guide online decision-making. In parallel, a first-order method runs during each interval between LP re-solves and smooths resource consumption. Our algorithm achieves $\mathcal{O}(\log (T/f) + \sqrt{f})$ regret and delivers a "wait-less" online decision-making process that balances computational efficiency and regret guarantees. Extensive experiments demonstrate at least $10$-fold improvements in regret over first-order methods and $100$-fold improvements in runtime over LP-based methods.

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Jingruo Sun
Wenzhi Gao
Ellen Vitercik Yinyu Ye 145
Abstract
tem continuously accumulates and evolves. Online Linear Programming (OLP) (Agrawal et al., 2014) offers a power- ful framework that encapsulates the core principles of se- quential decision maaking and has been extensively applied to different domains, including resource allocation (Bal- seiro et al., 2022a), online advertising (Mehta et al., 2007), and inventory management (Talluri et al., 2004).
Online linear programming (OLP) has found broad applications in revenue management and resource allocation. State-of-the-art OLP algo- rithms achieve low regret by repeatedly solving linear programming (LP) subproblems that in- corporate updated resource information. How- ever, L.--baed methods are computationally pensive and often inefficient for large-scale ap- plications. By contrast, recent first-order OLP al- gorithms are more computationally efficient but typically suffer from weaker regret guarantees. To address these shortcomings, we propose a new algorithm that combines the strengths of LP- based and first-order OLP algorithms. Our algo- rithm ro-solves the LP subproblems periodically at a predefined frequency / and uses the latest dual prices to guide online decision-making In parallel, a first-order method runs during each interval between LP re-solves and smooths re- source consumption. Our algorithm achieves (log(T/f) vT) regret and delivers a "wait- less" online decision packiign-making process that bal- ances computational efficiency and regret guar- antees. Extensive experiments demonstrate at least 10-fold improvements in regret over first- order methods and 100-fold improvements in runtime over LP-based methods.
We study OLP problem where eustomers arrive sequen- tially, each requesting combination of resources and of- fering a bidding price. The objective is to determine which resource requests to fulfill to maximize revenue while re- specting resource constraints. The challenge is that deci- sions must made immediately and irrevocably, relying solely on historical data without knowledge of future ar- rivals. The goal is to minimize regret with respect to the optimal hindsight linear programming (LP) solution.
To guide real-time gecision-making state-of-the-ar OLP algorithms estimate optimal dual prices and use them to make decisions. These algorithms fall into two main cat- egories: L.Pbased and first-order methods. Specifically, LP-based methods update dual prices by repeatedly solv- ing linear programs each time step with all available in- formation so far. However, the substantial computational demands limit their application in time-sensitive settings. First-order methods offer quick, incremental updates to dual prices using gradient information, but generally fall short of achieving the strong regret guarantee of LP-based methods. These trade-offs motivate an open question the intersection of online learning and decision-making:
1. Introduction
Can we simultaneously achieve low regret and computational efficiency?
Sequential decision-making has garnered significant atten- tion for its utility in guiding optimal strategies in dynamic environments. The goal to identify effective decisions and policies in environments where knowledge of the sys-
Our contributions. We answer this question in the affir- mative. We summarize our contributions follows:
DDpaarteent of Management Science & Engineering, Stanford University 'Institute for Computational and Mathematical Engi- neering, Stanford University Deppartment of Computer Science, Stanford University "Chinese University of Hong Kong (Shen Zhen) ' 'Hon Kong University Science and Technology. Cor- respondence to: Jingruo Sun <jingruo @ stanford.edu>.
Parallel Multi-Stage Framework: We separate online learning and decision-making into distinct processes that interact via feedback loop. We re-solve the LP sub- problems periodically at fixed frequency and feed the updated dual price to guide decision-making until the next time that the LP re-solved. To further enhance ef- ficiency, we apply a first-order method during the initial and final stages, restarting with the most recent learn-
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
ing outcomes. By integrating the LP-based and first- order techniques, our approach leverages their respective strengths and achieves balance between regret perfor- mance and computational costs.
naively combined. We overcome this challenge by intro- ducing unified performance metric that decomposes re- gret into three components: dual convergence, constraint violation, and leftover resources. This approach yields the first integrated analysis of LP-based and first-order OLP, culminating in our (log((Tf)) + vf) regret bound.
Regret Analysis: We unify the analysis of L.P-ased and first-order methods by deriving new performance met- ric to account for their inter-dependency. Our analysis yields a "spectrum theorem" " that bounds regret for any feasible choice of the re-solving frequency:
1.1. Related Literature
Online resource allocation and OLP problems have been widely studied under two predominant models: the stochastic input (Goel & Mehta, 2008; Devanur et al., 2019) and stochastic permutation models (Agrawal et al., 2014; Gupta & Molinaro, 2016). We study the former, where each customer's 's resource request and bidding price are drawn i.i.d. from an unknown distribution. We use ex- pected regret and constraint violation as the performance metric. We summarize some recent works in Table 1.
Theorem 1.1 (Informal version of Theorem 3.2). If we re-solve the LPs every f time steps within horizon T and apply first-order method in the initial and final J steps, we achieve worst-case regret of O (log(()))) + vf).
In particular, f = 1 yields pure LP-based method with Ollog 7') regret, while f ' reduces to pure first- order method with (VVT) regret. By choosing an "op- timal" f. one can achieve the best possible regret based on available computational resources and enable a "wait- less" Decision-making system across all time steps.
LP-based Methods. These methods solve the OLP dual repeatedly to update dual prices and make decisions. Early approaches enforced fixed average resource constraint (Agrawal et al., 2014), whereas recent work dynamically tracks remaining resources and enables LP-based methods to achieve Oloo T') regret under continuous support and non-degeneracy assumptions (Li & Ye, 2022). Variants in- clude multi-secretary problems (Bray, 2022), regularized resource constraints (Ma et al., 2024), and finite-support distributions yielding constant regret (Chen et al., 2024).
Experiments: Through experiments across diverse dis- tributions, we demonstrate that our algorithm achieves over a 10-fold improvement in regret compared to first- order methods and over a 100-fold improvement in run- time with comparable regret to LP-based methods.
Key Challenges. OLP methods face a fundamental chal- lenge in balancing efficient real-time decision decision-making and accurate dual-price learning. Specifically, LP-based meth- ods ensure high-quality decisions with (log T) regret, but their computational costs increase quadratically with prob- lem size. A natural anternative-batthie solving the LP once every f arrivals-reduces reduces this cost, but leaves customers waiting until the batch concludes. In contrast, first-order methods update dual prices via gradi- ent information, allowing for faster computation. However, these methods require small step sizes to maintain decision quality, which slows their adaptation to new data. Even using different step sizes for learning and decision-making only achieves (T11)) regret when the distribution of cus- tomers has continuous support. Our parallel framework addresses these issues: an L.-based method periodically refines dual prices, while a first-order method immediately processes arriving customers using the most recent dual up- dates, thereby eliminating delays.
First-order Methods. These methods generate decisions using gradient updates without solving LPs, enabling effi- cient computation. They achieve ((vT) regret with mirror descent (Li et al., 2020; Balseiro et al., 2022a) and (733)5 under finite support and non-degeneracy assumptions (Sun et al., 2020). Variants include proximal updates (Gao et al., 2023), momentum-bart based mirror descent (Balseiro et al., 2022b), resource adjustments (Ma et al., 2024), and restart strategies yielding (33 regret (Gao et al., 2024).
customers and
Delay in Decision-making. Delays arise from the time- consuming process of solving the large-scale, up-to-date LP subproblems for each customer. Golrezaei & Yao (2021) study a mix of impatient and partially patient cus- tomers, while Xie et al. (2023) show that batching re- quests can reduce regret. Concurrent work (Xu et al., 2024) reduces delay by solving LPs in batches but as- sumes a lower bound on resource requests and still re- quires waiting in initial and final batches. To achieve delay- free decisions, we shift the re-solving process offline and only fine-tune the solution online. Compared with previ- ous works, our framework imposes standard assumptions, achieves (log(T/f)++)) regret, and ensures "wait-less" decision-making throughout the entire horizon.
A second challenge emerges when analyzing the regret of this hybrid approach. I.P-based methods rely on a stopping-time analysis (halting when resources are de- pleted), whereas first-order methods track constraint viola- tions as part of the regret. Since these two formulations are fundamentally different, existing regret bounds cannot be
2

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Table 1: Performances of Dual Algorithms in Recent OLP Literature
Paper
Setting
Algorithm
Regret
Decision-Makinn
(Li & Yc, 2022)
Bounded, continuous support, non-degeneracy
L.Pbased
O T' logglog
Delay
(Bray, 2022)
Bounded, continuous support, non-degeneracy
LP-based
(log T')
Delay
(Chen et al., 2024)
Bounded, finite support, non-degeneracy
L.Phased
O(1)
Delay
(Li ul., 2024)
Bounded, finite support, non-degeneracy
LP-based
O(1)
Delay
(Xu et al., 2024)
Bounded, continuous support, non-degeneracy
LP-based
(log(I//))
Delay
This paper
Bounded, continuous support, non-degeneracy
LP-based & First-order
O(log(T/S) + vT)
No Delay
al. 2020)
Bounded
First-order
O(vT)
No Delay
(Balseiro et al., 2022a)
Bounded
First-order
O(vT)
No Delay
(Gao al., 2023)
Bounded
First-order
O(VT)
No Delay
(Sun 2020)
Bounded, finite support, non-degeneracy
First-order
O(7%/8
No Delay
(Gao al., 2024)
Bounded, continuous support, non-degeneracy
First-order
O(T4/8)
Delay
Paper organization. The rest of the paper is organized as follows. Section 2 introduces the problem formulation and assumptions. Section 3 proposes our algorithms and main theoretical guarantee: O(log(T/)) (T/) + vf) regret bound. Section 4 presents experiments validate our theory.
et al., 2020), (DLP) can be written as
min fr()) = + E p20
(d. + (re (ar (a..p))))
(1)
This formulation can be written as a -sample approxima- tion of the following stochastic program:
2. Problem Setup
min f(p) = E[fr(p)] d E[(r - a Tap)) p)*1 (2) P20
We use || to denote the Euclidean norm and (.) to de- note Euclidean inner product. Bold letters A and a de- note matrices and vectors, respectively. Subscript (+)a de- notes the index for resource type i time t. The notation (+) max (-axx-;00) 0) denotes the element-wise positive part function, and ([()) denotes the 0-1 indicator function.
where the expectation is taken with respect to (r: a) ~ P.
We define optimal solutions to the -ssmple approximation problem (1) and stochastic program (2) respectively
Pr = arg min
fT(P) and p arg min s(p). p20
p20
2.1. OLP Formulation
The decision variable x; can be established from the com- plementary slackness condition
We study online resource allocation problem over the time horizon 7' under a stochastic input model. Initially, we have an inventory vector E RTm representing m resource types. At each time step 6, a customer arrives with request sampled i.i.d. as (1:)aa) ~ P, where IRT is the offered payment (bid), A (a),..., ar) R is the matrix of customers' resource demands, and P is a fixed, unknown distribution. We must decide whether to accept or reject each request, represented by the decision variables æ = (II,..., E {0, 1)". The goal is to maximize the cumulative reward. This problem can be formulated as the following OLP, re- ferred the primal linear program (PLP):
{
O. Pi < a Pj
2/
1. Pt a Pj
and 21 [0, a, Př-
r (Fi....,
This connection between primal and dual solutions inspires OLP algorithms that make decisions based on dual prices:
Zt I(r: 2 a, p.).
(4)
2.2. Algorithms for OLP
We summarize two main dual-based OLP algorithms.
LP-based Method. The LP-based method (Li & Ye, 2022) calculates dual prices by re-solving the online LP problem at each time step. Specifically. define du = ba/(T - 6) as the average remaining resource for type at time t. The resulting optimization problem can be viewed as a t-sample approximation to the stochastic pro- gram specified by d, = (dse. ..., ...,,de)" as
max (r. S.I. A s
(PLP)
05#51
The dual problem of (PLP) is given by
min (b.p) + (1 s.t. (2.0)20
Ap-yyr
(DLP)
where p is the vector of dual prices. Let - b/T e mM denote the initial average resource. As demonstrated by (Li
min fa, (p) = d3 p + E[(r a +) p20
(5)
3

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
By updating de this method incorporates past decisions when computing Pt- If resources are over-utilized in ear- lier periods, the supply decreases, prompting us to raise the dual price and be more selective with future orders. We outline this method in Algorithm 3 of Appendix A.2.
2.4. Assumptions and Auxiliary Results
We adopt the following assumptions regarding the stochas- tic inputs. These assumptions are standard in the online learning literature (Li & Ye, 2022; Jiang et al., 2022; Xu et al., 2024). In particular, we require the input data to be bounded, follow a linear growth, and be non-degenerate.
First-order Method. The first-order method (Li et al., 2020) calculates dual prices via online subgradient updates. We maintain static average resource d b/T, compute Iy per (4), and update the dual price
Assumption 2.1 (Boundedness). We assume
(a) The order inputs {(ri, a+) )== are generated i.i.d from an unknown distribution P.
P++1 = (P: a,(d axz+))+
(b) There exist constants r, a, > 0 such that Ine| S F and | (o S almost surely for L..., T.
where the subgradient term evaluated at pt is
d - OtTt E 3p-p. p. (d' p- + (r+- - a. +)
(c) The average resource capacity d = satisfies d, E d d for some d > d d> 0 for any i = 1...., m.
This process can be interpreted as a projected stochastic subgradient method for solving (I). It reduces computa- tional cost by requiring only a single pass through the data and eliminates solving LPs explicitly. A restart strategy improves the first-order method to have O(T)/3) regret (Gao et al., 2024). Algorithm 4 and Algorithm in Ap- pendix A.3 summarizes this method.
In this assumption, (a) states that {(r,, a.)) are inde- pendent of each other, but we allow dependencies between their components. Part (b) introduces the bounds r, a solely for analytical purposes. This is a minimal requirement on (re, a.) compared to previous work (Agrawal et al., 2014; Li & Ye, 2022; Xu et al., 2024). Part (c) requires the aver- age resource to grow linearly with T, ensuring that a con- stant fraction of z, values can be set to 1. Consequently, the number of fulfillable orders is proportional to T, facili- tating a stable service level over time.
2.3. Performance Metries
We aim to design algorithms that optimize a bi-objective performance measure involving regret and constraint vio- lation. The regret measures the difference between the ob- jective value of the algorithm's 's output and that of the true optimal solution, while the constraint violation measures the degree to which the algorithm's 's output fails to meet the given constraints. We denote the offline optimal solution to (PLP) by x² = (zf..... 27), and the online algorithm output by x = (z1,..., )r)) Then, we define the regret r(x)) and resource violation v(x) as
Assumption 2.2 (Uniform Non-degeneracy). We assume
(a) The second-moment matrix Blaa" "] is positive defi- nite with minimum eigenvalue X.
(b) There are constants μt, V such that for any (r, a) ~ P.
vla T (p p¹)
r(w)= x²) (),
(6)
< |r 2 a T p p|a)= - Prr 2 a p' aa)
v(x) = |1 b)+
(7)
S s T (p p')l
Therefore, we define the following bi-objectives for evalu- ating an algorithm's worst-case performance:
holds for all
DE VoP = PE
Rm : P> 0, 1pl S 1
AT = sup Ep (r() + u(x)]
(8)
PEE
and d E Va = ldl m
where E denotes a family of distributions satisfying regu- larity assumptions specified later.
(c) The optimal p" satisfies p. = 0 if and only if d:- Ela,I(r > a "=)) > 0 for all d E Va and i E [m].
This metric is commonly used for first-order OLP algo- rithms (Gao et al., 2023; Li al., 2020) and is also aligned with the literature on online convex optimization with con- straints (Mahdavi et al., 2012; Yu et al., 2017). Integrating r(æ) and v(x) into a single performance measure promotes balanced resource consumption over the decision horizon. In Section 3, we derive a decomposition of (8) that unifies the regret analysis for all OLP methods.
In this assumption, part (b) ensures that the cumulative dis- tribution of the reward given the resource consumption re- quest r| a is continuous and exhibits a stable growth rate. Part (c) requires strict complementarity for the optimal so- lutions of the stochastic program in (2), which is a non- degeneracy condition for both the primal and dual LPs.
4

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
According to stochastic program (2), we define the binding and non-binding index sets as:
Algorithm 1 Parallel Multi-Phase OLP Algorithm
Input: total resource b, time horizon T, average resource d b/T. initial dual price p1 = 0. re-solving fre-
1B- = {i: : d4 - Bl > a aap'' p²)] - 0},
quency f. and number of batches k [T/S]
IN - (i: d. - Ela,,(( > a p²) > 0}.
(9)
for t = 1 to T do
Observe (re, at) and make decision D2 as rule (4) Update constraint for i = I....,
By Assumption 2.2(c), these sets are complements, as I IN 0 and Ip U IN {l,...mm m).
remaining resource byt = bi,t-1 Ost bie average remaining resource die T-1
3. Parallel Multi-Phase OLP Algorithm
if S f or 1 2 kf then
(11 IS (11/f2/8
We now present our algorithm for parallel multi-phase on- line learning and deciisonnmmaingg Our approach is mo- tivated by the challenges of existing methods. Specifi- cally, the LP-based method has strong worst-case re- gret bound of Oloo 7', but its high computational costs lead to decision-making delays. Meanwhile, the first-order method updates decisions efficiently but suffers a high re- gret of OVVT). By combining the strengths of these two methods, our new framework balances decision-making quality and computational efficiency.
Update learning rate Or
t t2 kf Compute subgradient and update dual price Pt+1:
Pi+1 (p. az(d axz1))
end if t mod f= 0 and constraints are not violated then Solve OLP and update dual price P++1:
P++1 = argmin d, p + + - a. p) p20
end
else
3.1. Algorithm Design
Update dual price pr+1 to be the most recent solu- tion Pt-1 = Pt.
We establish our framework with the following design:
end
end
1. We maintain two parallel paths of online learning and online decision-making The online learning results are periodically sent to the decision-making path as a re-start point to guide subsequent updates.
of the previous batch. The algorithm restarts the subgradi- ent updates only in the final batch to guide the remaining decisions. Algorithm summarizes this approach.
2. In the online learning path, we employ a streamlined I.P- based method, which only re-solves the updated OLP problem according predefined frequency, reducing the computational overhead.
Algorithm 1 balances online learning and efficient decision-making It is responsive to dynamic environ- ments, adapts to the latest information, and reduces com- putational cost by periodic re-solving. We thus establish a "wait-less" online decision-making framework where each customer's order is processed immediately without delays from earlier requests or large-scale LP computations.
3. In the online decision-making path, we apply the first- order method during the initial and final batches. The learning rate is optimally tuned for these two intervals.
Figure/ 1 illustrates our framework, which generates two parallel sequences of dual prices: {rp))__ from the first- order method and {pf yr from the LP-based method. The algorithm proceeds in batches of length f. In the first batch, it uses the first-order method to iteratively update the dual prices, thereby guiding decision maaiin.. At the end of this batch, applies the L.-based method to obtain a refined dual price and passes it the decision making path. The LP re-solving occurs only once per batch, making the ap- proach computationally efficient. Formally, we re-solve the OLP at every time i. satisfying t < kf and i mod f 0, where A = [T/f] is the number of batches.
3.2. Algorithm Analysis
We decompose the performance metric of Algorithm I into three key components. All proofs (including essential prop- erties of the dual price p:) are in Appendix B and C.
Theorem 3.1 (Performance Metric). Under Assumptions 2. and 2.2, the performance AT of Algorithm satisfies
AT S "paa Et E [lpp -2*1 + E [I] [Ax - b)+
+ +11p"11 E [ Ar) B+
(10)
where (-)B+ indicates the projection of binding terms onto the positive orthant.
During intermediate batches, decisions are made based on the most recent dual prices computed from the IP at the end
Based on the definition of Ar (8), we derive the perfor-
5

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
LP-aolving methhdd
L.Psolving method
LP-solving method
First-arder method
Decision making
Decision making
Finstorder method
2
kff
T
Decision Path:
pf p
pf
p
Pj41
P2f
Pkr
PRy-1 - Pkf+2
pf
Collect sumples, Solve LP to get pl.
Collect new samples, Solve LP to get ply
Collect new samples, Resolve for Ply 1 Reesovee pky No learning in final batch
Learning Path:
Figure 1: Algorithm 1 illustration of parallel paths and the interactions between online learning and decision decision-making. Decisions are generated based on 1) the LP-based method (blue) with frequency f. 2) the first-order method (red) for the initial and final phases (with a warm start), and 3) employing the latest dual price (yellow) during intermediate phases.
mance metric the sum of three key components: dual convergence, remaining resources, and binding constraint violation. This bound demonstrates that our algorithm en- courages 1) smooth and balanced resource utilization, and 2) full resource consumption by the end of the time hori- zon. Building on Theorem 3.1, we provide a "spectrum theorem" for the algorithm's performance.
ysis for the final batch leads the choice a, 1/ as shown in Theorem B.9.
Technical Intuitions. Theorem 3.1 decomposes the per- formance metrics to make the regret analysis compatible between the LP-based and first-order methods.
LP-based Method: As Theorem 3.1 suggests, achiev- ing small regret requires Ax b to be close to zero. To enforce this, we impose a stronger condition to track the average remaining resource-if d, exceeds the allowed limit, we manually set the dual prices to zero to accept all subsequent orders. This approach enables to elimi- nate the "stopping time" argument and make the analysis compatible with our new framework.
Theorem 3.2. Under Assumptions 2.1 and 2.2, the worst- case performance Ar of Algorithm 1 is bounded by
AT E OOOlog (7) vV)+
(11)
where f represents the number of re-solving batches and f is the length of each batch.
Remark 3.3 (Spectrum Theorem). We elucidate the trade- offs in total regret induced by using LP-based methods with Olog T) regret and first-order methods with ((VT) regret. Our algorithm introduces a re-solving frequency E [1, and achieves Olog(T//)) vT) regret, which recovers previous results with extreme
The regret improvement comes from the final batch since it starts with the I.P-derived learning result pay, which lies within
First-order Method:
(Ll//kk)-size neighborhood around p". Using the subgradient method, we bound the three components in Theorem 3.1 in terms of [p: p" and express them in terms of f. k. T, and ag. Optimizing the learning rate to a = 2-2 yields an improved regret of Off (1/) /3) in the final batch.
of f 1 and = T. Specifically, the first-order method gives us the re- gret of vʃ for the first batch and f1/3 for the last batch, and the LP-based method contributes the regret of log(T/J1 (ff)).
Remark 3.4 (Warm Start). We can obtain a tighter regret bound of (log(T/f)) + f1/3) given a warm start of the initial dual price satisfying Ilpo (IPo-pll pI S 113 or if we use the ba-ddded method at each time step for the first batch.
3.3. Algorithm Extension
We propose an enhanced version of Algorithm 1 that em- ploys the first-order method for speision-mmking between two consecutive LP resolves. Rather than making decisions solely with the most recently solved dual price from the learning path, Algorithm 2 treats it for each re-solving interval and adopts a smaller step size for subgradient updates to avoid deviating too far from the LP- -P-guided solutions. Figure/ 2 illustrates this framework. Specifically, for each interval [jf. (j + 1)f]. we attain the new start P; from the learning path time jf and con-
Remark 3.5 (Learning Rate Selection). We select the best learning rate minimize the regret upper bound consist- ing of (6) and (7). For the first batch, the regret grows lin- early with while the constraint violation is inversely pro- portional to ay- To achieve the tightest bound, we balance this trade-off by selecting the learning rate that minimizes the overall expression, which yields the optimal choice or 1/v/ as derived in Theorem B.7. similar anal-
starting point
6

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
LP-solving method
LP-solving method
LP-solving method
First-order mothod
First-order method
First-order method
First-order mothod
0
2f
kf
T
Decision Path:
pp p2-
p--
P5+2
Par
P2f+1
Per
pBJ+1
Pk142"
Collect new samples, Solve LP at to get pf-
Collect samples, Solve I.P 2 to Pis
Collect samples, Resolve for plg Resolve pkj
Learning Path:
learning batch
Figure 2: Algorithm 2 illustration of parallel paths with multi-time restart. Decisions are generated based on 1) the LP- based method (blue) with frequency f and 2) the first-order method (red) during ro-solving intervals with warm start.
Algorithm Enhanced Multi-Starl OLP Algorithm
Building on the Spectrum Theorem 3.2, this section aims to translate our theoretical results into practical applications.
Input: total resource b, horizon T, average resource d = b/T, initial dual = 0, re-solving frequency / for f = to do
We formulate a new optimization problem find the opti- mal re-solving frequency that minimizes the regret in Theo- rem 3.2, taking into account computational resource capac- ities. Denote C1 (-), c2(-) as computational cost functions for LP-based and first-order methods, and R as the total computational resource capacity. The optimal value f is determined by solving the following optimization problem:
Observe (r,,a,) and make decision 2, rule (4) Update constraint for i 1,... m: remaining resource constraint bis = bis-1 CaTi
average resource capacity die- = bar if / mod| + then
T-1
Update learning rate a, = O(L/t) Compute subgradient and update dual price p++1:
min (E(I....TT) log ff) + f
P++1 = (p: - a, axx:))
s.t. (k) + 202(1) S R.
(12)
end
if t mod| f = 0 and constraints are not violated then Solve OLP and update dual price 1:
Specifically, we use the interior-point method or the sim- plex method as the LP solver, the computational cost m² + t) for any time t. The first-order method updates gradients in constant time. The following proposition pro- vides concrete example in practice.
P++1 argmin di p + EE=z1r (r, ag p)+ p20
end
Proposition 3.6 (Optimal Re-solving Frequency). Given a fixed computation resource capacity R, if we use the interior-point or simplex method as the LP solver in Al- gorithm I. we can instantiate Constraint (12)
end
tinue to fine-tune the dual price {pt)e-// order method with learning rate 0; O(1tt). Algorithm 2 summarizes this approach.
(++1ff using the first-
(m² +jf)) 2mf < R.
This proposition enables users to determine the optimal re- solving frequency that balances regret and computational cost based on available computational resources.
As illustrate in experiments (Section 4), the in- corporation of an intermediate first-order method improves the algorithm's 's stability and ensures smooth resource con- sumption. Therefore, the multi-restart mechanism results in better performance during the final batch and improves the algorithm's 's total performance.
4. Numerical Experiments
We conduct extensive experiments to evaluate algo- rithm's performance and validate our theoretical results. This section is divided into two parts. In the first part (Sec- tion 4. 1), we evaluate Algorithms and across different choices of re-solving frequency. In the second part (Sec- tion 4.2), we compare our algorithm with L.--aaed and
3.4. Algorithm Application
Our motivation in designing Algorithm is to effectively balance computational efficiency and decision optimality.
7

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Table 3: Algorithms comparison.
Figure 4: Regret for various algorithms.
T'
Regret
Algorithm
Compute Time
115.32
((14/2)
First-Order
0.008
60.39
O(T1/)) First-Order
0.013
10
3,50
LP-based
123.497
10a
9.12
Algorithm 1
1.8
5.09
Algorithm 2
Regret
203.20
O(T First-Order
0.118
73.07
((T First-Order
0.108
10
3.88
LP-based
3600
9.41
Algorithm 1
56.9
164
6.36
Algorithm 2
56.8
351.91
O(T First-Order
1.211
115.39
O(T4/1) First-Order
1.577
10c
LP-based
100000
10
10'
10a
10'
10
11.65
Algorithm
2155.9
Horizon
7.09
Algorithm
2242.1
01728) Fint-Onder
otP Fint-onkr
1.-luaed
Algonitm
Algorittm
first-order methods in temms of regret and running time. All implementations can be found at GitHub Link.
4.2. Comparative Analysis with Baseline Methods
We next compare our algorithm's 's regret and computation time with classic LP-based (Li & Ye, 2022) and two first- order methods with ((T (Li et al., 2020) and O(31/3) regrets (Gao et al., 2024). We generate {(r,, at) from uniform distribution (Input D). We set the resource types to m = 5, time 7 to range evenly over [102, 10%) average re- source d: Uniform[1/3 2/3]. and re-solving frequency to fof= 1/3 T3 from Section 4.1. Each result is averaged over 100 trial runs. We summarize the findings in Table 3 and Figure 4, and we include more comparisons with an infre- quent re-solving method (Li et al., 2024) in Appendix E.2. We observe the effectiveness of Algorithm and
We consider the following distributions:
Input l: Ogt ~ 0, 2). r2 ~ Unif(0, 10)
Input II: axt ~ N (0.5, 1), ~ (0.5mm m)
Learning rates are selected as specified Section
1(//2/)) IS
Algorithm 1: au
011/f13) t2kf kf
Algorithm 2: az = 0(1(1)
4.1. Regret under Varying Re-solving Frequencies
We choose = 1 and generate the sequence {(re, {(r,,,))) randomly from the uniform (Input I) and normal (Input II) distributions, and include more complex distributions in Appendix 1. The time horizon T spans evenly over [10?, 10%), the initial average resource is sampled as de ~ Uniform [ffform[133,// /1/3, 2/3). and / 1/2 T2/3} represent- ing high, medium, and low re-solving frequencies. We port the average result 100 trials for each experiment. We use the classic first-order method with (TT2/2) regret (Li et al., 2020) Table 2 and Figure 3 on logarithmic scale.
1. Our algorithms exhibit strong performance in terms of decision optimality. They achieve over a 20-fold and 10-fold improvement regret compared the (TT1/2) first-order method and the ((1)/3) first-order method respectively. These numerical results also corroborate the theoretical bounds in Theorem 3.2.
2. Our algorithms are computationally efficient. Their run- times exhibit over 100-fold improvement compared to the I.P-based method with only a minimal increase (less than 2-fold) in regret.
baseline. Results are summarized in
We analyze the absolute value regret and its growth rate over time. We observe that regret decreases as the re- solving frequency increases. This trend holds consistently across both algorithms and input types. In addition, while regret accumulates over longer time horizons, the increas- ing rate remains stable for algorithms employing higher re- solving frequencies. These findings are consistent with the guarantees of Theorem 3.2, as more frequent updates en- able better adaptation to dynamic environments.
Therefore, we achieve balance between effective decision-making and efficient computation. Our algo- rithms demonstrate better regret than the first-order method and obtain substantial computational speed-ups compared to the LP-based method. They exhibit strong scalability and adaptability across various re-solving frequencies and stochastic input models, consistently delivering superior performance as the problem size grows.
8

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Table 2: Regret of algorithms with various re-solving frequencies.
T'
First-Order
Low freq
Mid freq
High freq
Finst-Order
Low freq
Mid freq
High freq
10a
12.13
7.76
5.77
4.86
10a
12.13
6.78
5.20
4.50
104
38.50
10.96
7.55
5.67
10*
38.50
8.03
5.99
Input I
Input
10a
122.44
23.90
9.92
8.36
10a
122.44
22.33
11.57
6.36
10
404.59
56.70
21.90
8.99
10"
404.59
48.21
22.44
7.09
10a
11.44
6,28
4.86
3.95
10a
11.44
3.20
2.56
1.75
104
36,50
10.21
7.34
3.81
104
36.50
5.48
4.30
2.52
Input II
Input
10a
115.57
14.61
11.78
4.66
10a
115.57
12.35
4.48
3.86
106
365.99
35.20
15.68
6.26
10a
365.99
30.48
13.20
4.77
(a) Algorithm
(b) Algorithm 2
Inpur
Input
Input
Input 11
10a
Regret
10a
10a
10a
207
20"
10a
10
10a
10'
10
10
10
10
10
10"
107
10a
10
10'
10
Horizon
Horizon
Horizon
First-Order
Algorithm
Algorithm 2
Low freq
Mid freq
High freq
Figure 3: Evaluations of Algorithm and 2 across various horizons, re-solving frequencies, and stochastic inputs, validating the positive relationship between regret and frequency stated Theorem 3.2.
5. Conclusion and Discussion
framework to broader classes of online optimization prob- lems. Overall, our results underscore the potential of hy- brid algorithms in high-dimensional, large-scale environ- ments, offering practical insights for applications in opera- tions research, machine learning, and beyond.
This paper presents a new approach online linear pro- gramming for dynamic resource allocation, addressing the inherent trade-offs between decision-making optimality and computational efficiency. Recognizing the limitations of existing methods, we propose a parallel framework that decouples online learning and decision -akiing into inde- pendent yet complementary processes. By integrating LP- based and first-order methods, our framework effectively balances total regret and computational cost.
Discussion of Unknown Horizon
In this paper, we consider decision- makiing under a fi- nite horizon, since the average resource Assumption (c) widely used in OLP literature relies on fixed horizon be well-defined. When the horizon unknown, this assump- tion becomes ill-posed, and prior work (Balseiro et al., 2023) shows that it may not be possible to achieve sub- linear regret. Addressing these challenges would likely re- quire first adapting LP-based and first-order OLP methods to uncertain horizons before tackling a hybrid approach.
We establish rigorous theoretical guarantees, proving that our algorithm achieves a worst-case regret bound of Olog(T/S) + vT) under continuous support. This re- sult highlights our method's ability to interpolate between bP-based and first-order methods based on computational capability. Furthermore, extensive experiments validate the effectiveness of our approach, demonstrating improve- ments in both regret minimization and runtime efficiency over competitive baselines.
In practice, often possible make prior prediction of the horizon using data-driven approaches or based on the resources available. For example, in online advertising, the number of customers can be predicted from historical statistics. Besides, in retail or event-based sales, the selling horizon may be externally decided by upper-level decision- makers. These practical applications suggest a reasonable modeling choice for finite time horizons.
Beyond these contributions, our work opens avenues for further research adaptive online decision-making. Future directions include refining the re-solving frequency based on real-time computational constraints and extending our

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Impact Statement
Goel, G. and Mehta, A. Online budgeted matching in random input models with applications to adwords. In SODA, volume 8, pp. 982-991, 2008.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences our work, none of which feel must be specifically highlighted here.
Golrezaei, N. and Yao, E. Upfront commitment in on- line resource allocation with patient customers. arXiv preprint arXiv: 208.0:000 2021.
Acknowledgments
Gupta, A. and Molinaro, M. How the experts algorithm can help solve Ips online. Mathematics of Operations Research, 41(4):1404- 1431, 2016.
This work was supported in part by NSF grant CCF- 2338226.
Jiang, J., Ma. W., and Zhang, Degeneracy is ok: Loga- rithmic regret for network revenue management with in- discrete distributions. arXiv preprint arXiv:22 2022.
References
Agrawal, S., Wang, Z., and Ye, A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4):876-890, 2014.
Li, G., Wang, Z., and Zhang, J. Infrequent resolving al- gorithm for online linear programming. arXiv preprint 2400:2408800465, 2024.
Balseiro, S.. Kroer, C., and Kumar, R. Online resource allocation under horizon uncertainty. In Abstract Pro- ceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pp. 63-64, 2023.
Li, X. and Ye, Y. Online linear programming: Dual conver- gence, new algorithms, and regret bounds. Operations Research, 7065):2988-2666, 2022.
Balseiro, S. R., Lu, H., and Mirrokni, V. The best of many worlds: Dual mirror descent for online allocation prob- lems. Operations Research, 2022a.
Li, X., Sun, C., and Ye, Y. Simple and fast algorithm for bi- nary integer and online linear programming. Advances in Neural Information Processing Systems, 33:9412-944 -921,, 2020.
Balseiro, S. R., Lu, H., Mirrokni, V., and Sivan, B. From online optimization to PID controllers: Mirror descent with momentum. arXiv preprint arXiv:2002.06152, 2022b.
Ma, W., Cao, Y., Tsang, D. H., and Xia, D. Optimal regu- larized online allocation by adaptive re-solving. Opera- tions Research, 2024.
Bray, R. L. Logarithmic regret in multisecretary and on- line linear programming problems with continuous val- uations. arXiv preprint arXiv:1912.089) 2022.
Mahdavi, M., Jin, R., and Yang, Trading regret for effi- ciency: Online convex optimization with long term straints. Journal of Machine Learning Research, 13(81): 2012.
Chen, G., Li, X., and Ye, Y. An improved analysis of lp- based control for revenue management. Operations Re- search, 72(3):1 124-1138, 2024.
Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. Ad- words and generalized online matching. Journal of the ACM (JACM), 54(5):22-es, 2007.
Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66(1):1-4) 2019.
Sun, R., Wang, X., and Zhou, Z. Near-optimal primal-dual algorithms for quantity- based network revenue manage- ment. arXiv preprint arXiv:2011.06327.. 2020.
Gao, W., Ge, D., Sun, C., and Ye, Y. Solving linear pro- grams with fast online learning algorithms. In Inter- national Conference on Machine Learning, pp. 10649- 10675, PMLR, 2023.
Talluri, K. T. Van Ryzin, G., and Van Ryzin, G. The theory and practice of revenue management, volume 1. Springer, 2004.
Xie, Y., Ma, W., and Xin, L. The benefits of delay to online decision-making, Available at SSRN 4248326, 2023.
Gao, W. Sun, C., Xue, C., and Ye, Y. Decoupling learn- ing and decision making:: Breaking the O(VT) barrier in online resource allocation with first-order methods. In International Conference on Machine Learning, pp. 11859-14883 PMLR, 2024.
Xu, H., Glynn, P. W., and Ye, Y. Online linear program- ming with batching. arXiv preprint arXiv:2408.0033 003100 2024.
10

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Yu, H., Neely, M., and Wei, X. Online convex optimization with stochastic constraints. Advances in Neural Infor- mation Processing Systems, 30, 2017.

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Appendix
Table of Contents
Primary Results and Properties
13
A.1 Preliminary results
13
A.2 LP-hased analysis
13
A.3 First-order Analysis
14
B Algorithm Design and Analysis
17
B.I. Regret Analysis
17
B.2 Total Performance Analysis
18
B.3 Regret for LP-based Method
19
B.4 Regret for First-Order Method
21
C. Main Results
25
C.I Proof of Theorem 3.1.
25
C.2 Proof of Theorem 3.2.
25
D Auxiliary Results
26
Technical Support for L.P-haeed Analysis
D.2 Technical Support for First-order Analysis
29
E Supplementary Experiments
E.1 New Distribution
30
More Comparison
Structure of the Appendix We organize the appendix as follows. In Section A, we present some primary results for the OLP problem and the foundation analysis for LP-based and first-order methods; Section B characterizes the unique properties from our parallel multi-phase structure, and presents the cohesive mathematical framework which decomposes the performance metrics to unify all the OLP methods; Section C demonstrates the outline of Algorithm 2, combines all the previous results and proves the main results in our paper; Section provides auxiliary results and technical support for the previous three sections; Section E includes supplementary experiments of more general input distributions and comparisons with recent algorithms.
12

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
A. Primary Results and Properties
In this section, we present some primary results for the problem and OLP dual algorithms which will help present our main results. We also include basic properties and convergence of the LP-based and first-order methods. All the analyses are stated under Assumption 2.1 and 2.2.
A.1. Preliminary results
We propose the following lemma as directed results from Assumptions. Let denote the family of distributions satisfying Assumption 2.1 and 2.2. We propose the following lemma.
Lemma A.1 (Dimension Stability). Under Assumptions 2.1 and 2.2, there exists a constant ó > 0 such that
Ap E D = dd - 6, d, + 6)mh, stochastic programs (5) specified by de share the same LB and IN sets.
This lemma is consequence of Lemmas 12 and 13 in (Li & Ye, 2022). The existence of 8 comes from the continuity of fa, (p). Thus, 8 is only associated with stochastic program (5), and it is independent of T. Note that D C Va. We will analyze our feasible dual solutions derived from the online algorithm with de E D.
Lemma A.2 (Quadratic Regularity, Proposition 2 in (Li & Ye, 2022)). Under Assumptions 2. and 2.2, for any E Vp.
ua² 2
f(p) S V (p-p")
p" p'1,,
V\
f()) 2 V/'p') (p- - p²)
2 1p p 1111
Moreover, p' is the unique optimal solution to (2).
This lemma establishes a local form of semi-strong convexity and smoothness at p", which guaranteed by our assump- tions on the distribution P E. By focusing on these local properties rather than insisting on strong convexity and global smoothness, we relax the classical requirements typically imposed in such settings. In later sections, we will leverage this result derive our regret bound.
A.2. LP-based analysis
We state the LP-based method Algorithm and its properties of boundedness and dual convergence results.
Algorithm LPP-aaeed method
Input: total resource b, time horizon T, average resource d b/T, and initial dual price p 0.
for f = 1 to I' do
Observe (re, at) and make decision oe based on rule (4) constraints are not violated.
Update constraint for i 1,... m.
remaining resource constraint bis bi, ag.T average resource capacity du byr T-7
Solve the updated dual problem and obtain dual price P.+1:
1 1
Pc+
argmin d'p+ p20
p +
Σ (rj a. p)*
==1
end
LP-based method incorporates the past decisions into the optimization of p:- resources were over-utilized in earlier periods, the remaining supply decreases, prompting the algorithm to raise the dual price and become more selective with future orders. Conversely, if ample resources remain, the future dual price will be lowered, allowing more consumer requests to be accepted. This adaptive mechanism accounts for past actions by adjusting the available resource capacity. Lemma A.3 (Boundedness of LP result). The online dual price Pt. from Algorithm and the optimal dual price pº of stochastic program (2) are bounded as
F
F
|p"
|| < d 8
d'
13

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Lemma A.4 (Dual Convergence of LP-based algorithm). Under Assumptions 2.1 and 2.2, Pt represents the online solution from L.--bsed method, there exists constant Ctp depending on a. m, v, and X such that
pill Cip t
E
(13)
In addition, the difference between pž and p' satisfies
p p"1 22 ||d dlp
(14)
This lemma establishes that the LP-based online AHDL algorithm (Jiang et al., 2022) produces dual solutions Ps that converge to p;- This convergence highlights the stability of the online dual variables during the intermediate stages of decision-making and ensures warm start for the first-order method in the last re-solving batch. Moreover, we bound the distance between p; and p" by relating their respective average resource capacities, d, and d, in the associated stochastic programs (Li Ye, 2022). These results provide the foundation for analyzing ||pe p' in our final result.
Proof of Lemma A.3. By the optimality of p" and boundedness of d, have
d d> - d' s
This holds because if otherwise, p" not be the optimal solution due f(p") f(0). Given the non-negativeness of p" and p" Va. we obtain ||p"|| < |pp" l| and thus |p" S 4
Similarly, by the optimality of pž and its associated d, E DD in Lemma A.I, we know
(d-8))lplll- di Pa S E I 7.
so we get the bound as |pel <
F 8-8"
Proof of Lemma A.4.
According to the latest results in (Jiang et al., 2022), the online dual price Pt achieves a sublinear
convergence O Vi to p; Since
p' E arg min f(p) = d p+ + [(r - p) p20
p. E arg min fa, (p:) == d, p. + E [(r a T p1)
P.20
By Lemma 12 in (Li & Ye, 2022), we have ||pt p" 1 v
0وga || d: - d
1
A.3. First-order Analysis
We present the classic first-order method (Li et al., 2020) in Algorithm 4 and the first-order method with restart strategy (Gao et al., 2024) in Algorithm 5. We also show their properties of boundedness and dual convergence results.
Algorithm First-Order Online algorithm
Input: total resource b, time horizon T, average resource d = b/T, and initial dual price pl 0.
for f = 1 to T do
Observe (rr, at) and make decision z, based on rule (3).
Update learning rate a, = (I)VTT. Compute subgradient and obtain dual price P++1:
Pi+1 argmin (d a,2,) Tp ++ 1p -pell
2a,
p20
end
14

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Algorithm 5 First-Order Restart algorithm
Input: total resource b, time horizon T, average resource d b/T, and initial dual price p 0. 00, for f = 1 to I" do
Observe (rz, ar) and make decision 2t based on rule (4)
(1//T//)) L 7
Update learning rate oz
(1//2//3) t> T2/3
Compute subgradient and obtain dual price P++1:
PG1 = argmin (d - a(,)))
+ (pp 1pp -pell
p20
204
Run subgradient method with stepsize a = O(1/t) and update {pf}. Att T2/3, restart Pr2/3 = D/ra/3.
end
Lemma A.5 (Boundedness of first-order result). The online dual price Pt from Algorithm 4 is bounded as
p 2F + mla d)2
m(ā + d).
Lemma A.6 (Dual convergence of First-order algorithm). Under Assumptions 2.1 and 2.2, Pe represents the online solution from first-order method, if 04 vλ, the subgradient updates satisfy the following recursion rule:
E [[p++1 - p p11 < (1 - a.VA))p: p'1l² + af + dj2.
(15)
Case af a < Dx then there exists a constant Ojo +m 22
such that
E [llp: p'113] < Cso +
(16)
Case if = vx(+tT. then there exists a constant Cfo
4mm d)+ x2
such that
Cjo
[lpp - ---111
(17)
This lemma shows that the first-order method (Gao et al., 2024) guarantees the convergence of p. to p'. It also highlights a key trade-off choosing the learning rate a₁ an aspect that will be central to our later optimality analysis. It also highlights a key trade-off in choosing the learning rate ag, an aspect that will be central to our later optimality analysis. With this groundwork in place, we now move on to bounding the total regret of our algorithm.
Proof of Lemma A.5. As our initial choice p1 according Lemma I in (Li et al., 2020), get the above result. In addition, by Lemma B.l in (Gao et al., 2024), we have
m(ā + d)
Ip S d
+
+ a m + d).
2d
Proof of Lemma A.6. Based on the updated rule in Algorithm 4, we derive:
|Pt1 2 < pp an(d a:T+)) p=1
lp: p²12 -2a,(d a. Pt -p)) a (d a
< pp - p²1 22r(d - a. Pt - p²) + a,m(a d)2
1) With convexity of and E(d - ax31 E (p:),, we have:
f(p") 2 (p.) + (d a.34 Pc p")
15

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
2) With quadratic regularity of in Lemma A.2, we have:
Vt
f(pi) 2 f(p") V (p: -p")
2 Pp p" p=11?
2 V\ 2 Ip: p*11²
which indicates f(p:) - f(p')
Combine the above results and take expectation conditioned on history information ajj S 1), obtain:
E P1+1 - p²11 < Pp: p"1 2a, (d 0,3r, Pt p3) + a + a)²
Σ Pp p" 1| -2ar(f (p:()(p)))))) - f(p")) + a, + d)²
I |p: p²12 aLuilpp: - p'11 + amaa + dd)²
(1 apdi)lpp p' 1| azm(aa + d)²
This proves (15) with the general case of learning rate dy.
Case 1. When dz 0 ex is constant, we take recursion of (15), Note that (1 vdaa)' < 1/vdad, we get:
t-1
P+t1 pp11 s (1 - aVA)"Ipii- -p"122
Σ
a amm + -
(d) avvA
5=0
|p
m(a d)2 1²1
vdol
vd
tm((+a)) Dd
Since all feasible E Vp is bounded, let Cfo-
we are able to obtain (16).
Case 2. When 0r DX(++1J for any S Lemma A.6 gives us
j+1 Pj -p"12+ 4m + d)2 u2ii(j +1)
j 1
E Fl|p - -
Re-arranging the above inequality, we have
p²11 s (j² 11)1p; - 2 4m(( + d)²
(j + 1) P5+1
v²
4m(a + d)2
then (j + 1) PJ+1
- -p'112
x2
Then by telescoping from j = 2 to t, we have
4mn(a + d))a x²
Σ G + 1) Pj+ - - =p112 (t+ 1 (p+1 -21 [p: 2
which then gives us
[p - p21
+ 4m(a + dy't
E E| 2p'
(t + 1)2
+ +1
|| p' 121
4m(ā + d)²
thus E Pr
22112=
t2
x²
As pı and p" is bounded, taking Cfa 2m(a+d)² 02
completes the proof for (17).
16

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
B. Algorithm Design and Analysis
In this section, we present cohesive mathematical framework to integrate LP-based method and first-order method by developing new performance metric. We also provide some unique properties for our algorithm design of parallel multi-phase structure.
As stated in Algorithm 1, we construct independent paths for online learning and online decision-making conducted si- multaneously. Specifically, for the online learning path, we use the LP-based method to resolve updated linear programs at fixed frequency and send this result to the decision-making path; For the online decision-making path, we apply the first-order method the initial and final batches, and use the latest dual price for decision decision-making in the intermediate resolving intervals. This process is illustrated in Figure
B.1. Regret Analysis
First, we construct an upper bound for the offline optimal objective value. The challenge comes from the intractable dependeney of constraints on objective value under online setting. tackle this issue by introducing a Lagrangian function integrate constraints into the objective and balance revenue maximization with constraint satisfaction. The formulation stated as follows.
Lemma B.1 (Lagrangian Upper Bound). Under Assumptions (2.1) and (2.2), define the deterministic Lagrangian dual function as
{(p) =B a pp)) + (d at(r > a p)) p"].
Then for any feasible Vp, we have:
(a) E Σ Teili
S &T((p"),
(b) A(p')
{(p) S أقē lpp - p" p'11
(18)
Lemma B.2 (Dual Price Boundedness). Under Assumption 2.1, the online and offline optimal dual prices are bounded respectively by ||p'|| < and
2F + m(ā + d)² F 1 d-6
+ ma +d)) d))
|prll sp:= max
d
This lemma establishes that the optimal dual prices remain bounded. Our algorithm maintains these bounds because if p: grows large, the algorithm responds by accepting more orders, which in turn reduces Pt+1- This self-correcting mechanism keeps the dual prices within these limits. With this groundwork place, we now move on to derive the upper bound for the total performance of Algorithm
Theorem B.3 (Decomposition of Regret). Under Assumptions (2.1) and (2.2), let C, max vAs }. derive
upper bound for the regret r(x) as:
r(x)= S Cr
[B]((b
Σ t=1
axtt
B+
Σ
T -p"12
E
(19)
t=1
Proof of Lemma B.1.
This lemma is proved as Lemma 3 in (Li & Ye, 2022) by strong duality and optimality of pi-
Proof of Lemma B.2. By the boundedness results in Lemma A.3 and Lemma A.5, define
2F + m(a + d)²
m( + a1
max 5- d
then we complete the proof.
17

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Proof of Theorem B.3. By the definition of {(p). derive the online objective as
T
T
E
E ( |p:]]
Bll(pi) - -(d aaxi)"
Then by Lemma B.1, we derive the upper bound for the regret r(x) defined in (6) to be:
T
r(x) = E
1=1
$ T((p'')
Σ E(e(p:) - ) Tp' p"]
[[(d a, T 'p1 + Σ El((p") [(pp)]
T
T
T
< E
Σ
a134
p
+
pt
p'11
2
mm/
< ||p"|
E
(b
T
B
n
T
E
lp:
-p112
2
1=1
where (.)++ denotes the positive part only for binding constraints.
As |pp"| is bounded, taking the constant C, max 2:
ua² 2
completes the proof.
B.2. Total Performance Analysis
We consider the constraint violation as v(x) = |1(Ax - b)+ in (7). Then the total performance is the combination of regret and constraint violation. Since Theorem B.3 holds for any unknown distribution P E E, we have:
AT = sup Ep(r(x) + v(x)] PEE
c
E
b
a&Tt
B+
+
T
E p:
p'11
E (2
a b) $1
t=1
1=1
T
CC,
E Pt
p²112
B|(
|| + +E Az)
b)+1|
(20)
This new framework is adaptive to all OLP methods. We proceed with this structure to analyze various OLP methods. Theorem B.4 (Horizon Division). Based on the change of methods, we separate the horizon into three intervals Tí, T2. and Ts. and reorganize the total performance for analysis to be
AT S [r + +T, + ATr]
(21)
where ATy, ATy and Arg are the performances for each interval.
Proof of Theorem B.4. We split the total horizon into three intervals of initial batch T, = [0, fl. intermediate process T2 = [f, kf], and final batch T3- = [kf, We use the first-order method for the first and final batches and the LP-based method for intermediate processes. Notice that for the initial resolving batch, we maintain the classical analysis for the
18

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
first-order method since it has not reached the mixture with the LP-based method. Then based on (20), we define
AT, Biraa - -1 + B
Σ a, - fd)
I
TTg-
k
Bllp: -==111
1 + ( 1)fd
k
ag
B+
+B
Σ
kf
0,3r (b: 13-11111 1)sdd) "I
(22)
t=
1=/
D =
Bllp: - p²11 + B (
Σ
T
B
+ E
Σ
T
ag - (T - k)) +1
t=
t-
t=
Then have
Dr S Cr +1z + Aral
since (I(a + 1)+1| < ||+||| + ||b+|| for any a,
B.3. Regret for LP-based Method
In this section, we are going to bound Ar; for the regret from LP-based method. To provide a tighter analysis, we examine the real-time average resource capacity d, instead of the original process b, Specifically, by Lemma A.I, we constraint d, within feasible range D. If d, & D. we set the dual price to zero to accept all subsequent orders. We analyze the remaining resources and constraint violation due this strategy. Note that this is required solely for rigor analysis purposes and is not necessary when running the algorithm.
Lemma B.5 (Dynamics of Resource Usage). Under Assumption 2.1 and 2.2, there exists a constant C depending on d, a. m, v, A1, us and Cip such that
kf Σ
B((dr, d,)²] < Colog(k).
(23)
Theorem B.6 (Regret of Intermediate Process). Under Assumption 2.1 and 2.2, following the result in (22), we prove the regret satisfies
{ ( (llg((+))
Ar, S log
(24)
Proof of Lemma B.5. During the re-solving process, we denote each interval to be Lif, (j + 1)fl where 1, 2, ..., k. As the resource usage follows b b, a141I(re41 af PP+1). normalizing both sides, we derive the update of average resource consumption be:
(++1)S 2tzjst da.js a(, > at P(++1)))
d = dris +
-i(++
Subtracting d; on both sides, it becomes
Li=isti diis - a.ellrr > af P(+n))
(j+1}8
d1.134135 - de = =di.s d; +
T T T-(i+1)f
Li=jsti di.s - ai,e at p.p'))
diiss - d, +
T (i+++1)f
Li=jft1 ar.el(r > a p arel(re > at p(+D))
T 1)f
19

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Taking expectations of squares, have
G+1) DEjjtt diss - a a 1) ( 1)5}²
B(duu+1) - d,)² -B(da,s - dd,² IE
(i+1)S -= ane anee((r > at Pit - an.el(re > at P(+1))))
+E
(T-()+1))
(j+1)s
au,lle a pir))
Ltslt+
+2E
(d.ss - di)
T -
(J+1) Lt=jlt1 ar. > a[p;)) an > af P(stDr))
+2E
(d di)
T T- --(i+
(++1) P-jf+1 doss - a0, > of PTj)) (ttiss are > p( aree > at P(+t)))
+2E
--
T (-+ 1)f
(25)
By Lemma D.I, we obtain the recursion relation as
E(d,()+Ds- - d:)² < E(d.,i - 2 + (k-j 112 (k (k-j 1) 1)f /Elidaas -d)
Cree
4ua² VCp
+
(26)
where Cree > is a constant defined in Lemma D.1.
Then according Lemma D.2, take C max Cree: 16p)2 we solve recursion (26) and obtain the upper bound of total deviation from original d; in the re-solving process to be:
k
C
E 1oias-dy77 log(k).
(27)
Therefore, we sum the whole re-solving process and obtain:
kf
k
G+1)f
E((de, - d;) = Σ
E[(d,, d,)²)
1=1 t=1/
f C
f log(k) (by result in (27)
- C'log(k).
(28)
This completes the proof.
Proof of Theorem B.6. We analyze the three terms in (22) respectively.
1. For dual convergence, by Lemma A.4, we have
k
(+11)
Σ
E -
Σ llp - 1
t=
f E |Potts- - pp'13]
f E |PPttis - Pirlla + |p0, p01
1=1
20

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Ctp jf
B[(d, d)²]] (by Lemma A.4)
22X²
mC ==1
ip
log(k)
log(k). (by Lemma B.5).
(29)
2. For the constraint violation, by Chebyshev's inequality, we bound the probability as
kf
Bidr, d
P((di, 5 2
82
C
log(k). (by Lemma B.5)
(30)
82
Since our strategy to automatically set p: = 0 once de & D, we will accept all the subsequent orders according to our decision condition (3). Denote the total number of orders processed specifically due to this rule, then we have:
kf P(ida dil S 5) S 82
C
log(k)
(31)
which indicates that the resource violation is most
Σ a,s, (k- -k-1) 71
Cā 82
TE
ElaR]
log(k).
(32)
3. For the remaining resource, we derive its upper bound by considering the opposite extreme case of our strategy. If we reject all those R orders, then no resource is used on them. Thus, by (31), the positive projection of remaining resource at l = kf is at most:
E
(kk-1)) 1)fd
Σ axrr)
"|
[[d +8)
<
C(d+ 8)
(k).
(33)
82
Combining the results of (29), (32), and (33), we derive the final result as
mC
Ar, S (Cip + u2\2 + (a + d + 8) 82 log(k).
(34)
This completes the proof.
B.4. Regret for First-Order Method
In this section, we are going to bound År, and ÅT; for the regret from the first-order method. The key point is to analyze the connection between dual prices based on the gradient-updater rule. Here pt p.." Theorem B.7 (Regret of Initial Batch). Under Assumption 2. and 2.2, we have
m(ā + d)² 2F m(a + d)² m(a + a)) VF.
AT:
(35)
d
Lemma B.8 (Constraint Violation). Under Assumption 2.1 and 2.2, take the learning rate at = a, we bound the constraint violation for the last batch as
T Σ t=
(T- 17-kjy (-kffdd
Cip
Cs
C. 1
Cb
E
a.30
+
(36)
/k
T
a
/T- ava
Va
21

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Theorem B.9 (Regret of Final Batch). Under Assumption 2.1 and 2.2, we have
m(ā + d)²
2Cip Vk
Clplog(f)
4Cb
Ta S
+
+ 2C,)
fa/3.
(37)
vAk:
Vk
Lemma B.10 (Warm-Start First-Order Regret), Assume that we have a warm start for the initial dual price po the first batch, which satisfies |oP p"ll I f-1/3, Then the regret of the first batch follows
A warm I (m(a + d)² + #4Cw)
fa/s + log(f).
(38)
Proof of Theorem B.7. We analyze An, (22) by parts. By Lemma B.3, B.4 in (Gao et al., 2024), we have
m(ā + d)2
E Elra rgae]
2 05,
a - fd) |
2F + m(a + d)²
+ m(a + a)
d
To achieve the tight upper bound, we select the optimal step size
- which then gives the desired result.
Proof of Lemma B.8. With the update rule of first-order method in Algorithm 4, we have
P++1 = (p: -a(d - axx:)]+ 2 p: - -add - arTz), a(d-a;v)).
1 - (pi+1 - Pp). which gives us a,3, S a
Summarizing on both sides and applying the telescoping, we derive
T
T
a1 - d) S Σ
(p:+1 - p.) - - Pkj).
k=
t=
By Lemma D.3, take C₁ = max
Cia
m(a+d) VoA
... we have
1 + Va 1 -fT- Va 72 ]
E
P p'
C.
(39)
Thus, according to Lemma A.4 and (39), the expectation of constraint violation satisfies
T
T
Σ
a - d) )
<
Σ
(a
-d)
t=
t=kf
B| Pirll
< E |ipks p"ll + ||pp+++-"""]
Cip + +Ob
-T- Va + Va 11
72 )
Vif
Opp 1 +
V ava +G, 1 G 1
Co
<
(40)
vkf
Va r
This completes the proof.
22

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Proof of Theorem B.9. We decompose Ang into three parts according (22) and analyze each term respectively. Since the first-order method re-starts from pkf. by Lemma A.4, we have:
Pkf -p'1
m(a + d)²
E D'11 v
vdod
t=kf
|ky - p²11
log(T- -kf) + m(a + d)²
(T - kf)a
vda
VA
p p²11 log(s) m(a + d)2
fa
vλa
vd
Op log(f)
1
m(a d)²
+
fa.
(41)
vAkf
v\
Since E [J, by Proposition 3.3 in (Gao et al., 2024), the dual price is far from the origin and thus the positive projection still equals itself. This indicates that:
PG+1 [p: - a(d axxi)=== p. a(d axx;),
1
which then gives us d - a,3; (p: P(+1).
Summarizing on both sides and applying the telescoping, we derive
Ed- ax) (dda
Σ
(p: p(+1)= (pxs P1+1).
1
r=
t=
Then for the positive binding terms, by Lemma A.4 and (39), we have
T
B*
T
Σ
(d - a.z,))
S Σ (d a.
t=
- Ellpas - PT+
E lipas - p"11+ +++l|p++100 - p'll -P'll
Cip + VfT- ava + Va
Co
1 1
C. 1
+
(42)
VkJ a
T a
Combining the results of (41), Lemma B.8, and (42) together, we obtain the final result as:
(a aa - d)²
20
20,
Cip (oplog(1)) 1 +
2C,
2
2Cp
ATa
Dλ fa
Vkf
T
vAkf
(T-kfM
avo
+
Va
(43)
We select the optimal learning rate a = f-2/3 to minimize Ar, in (43). We prove this result in cases.
1. If - kf S f 1/3, the regret must be smaller than the length of the batch, so Ar, IT - =
2. IfT - kf > f1/3, then we use this property to bound the term
2C,
2
We derive
V(T-Kf)
ava
ATg < m(a + d)²
12
2Cb
Ciplog(f))
4Cb
5 5 +
+
22/
- /
D\
vkf
T2
viks
VpL/3. kf
m(ā + d)²
201p
20,
liplog(f)
4Cb Vi
1/3 +
1/ +
f/13
11/3 + 2C' 1/3
Vk
T
vAk
m(a + dj²
2Cip
Cip log()
4Cb
+ +2C)) .1/3.
(44)
VT:
vik
Vi.
This completes the proof.
23

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Proof of Lemma B.10.
According Lemma D.3, with |po- p'll S 1/3 and
have
2x
Po P - p²112 am + d)2
Blllp=+1 - -p"11 pol
udas
Blpps+1 -p'll fi/s/udf Va
1
m(@ d)
v a + T
p
(45)
Vvd
Then according to Lemma B.8, take C max m(a+d) Vot
.P, we derive the constraint violation follows
E Σ
a, d)
) Σ
+
<
asti d))
t=0
t=
E
Ps+1 Poll
Po
p'1l
+ +1plp+11 - p''|
1
f1 Ta v 1
1
Cvv
f1/3
T
1
C fo/6
1
C 7
+
+ C
va
(46)
f1/
ava
Similar to (41) in Theorem B.9, we derive the dual distance as
+ m(a + d)2 p²11
Σ
E
Elpp
p=11²
a
Ddae
< lpPo 1²112
m(a d)2
log(S)
fa
vλa
vd
log(f)
m(a + d)2
+
so.
(47)
vAf2/3
Di
Similar to (42) in Theorem B.9, we derive the positive projection for binding terms
8+
E
Σ d
a.2:))
E
Σ d
a
t=0
t=
Ep P/+1ll
0
Po - pp +²11+ ||ps+1 - p'1]
a
1 1 Cw 1
1 C
S
n/ ava CC
(48)
fa/
a
Va
T
a
Therefore,
Therefore,combiniii combining the results (46), (47), and (48) together, we have
AT; log(f)
1
m(a d)2
fa
vxf2/3
a
vd
2
1
2Cn
1
1
20
1
2C
f1/3
a
F/
a
Va
T
a
māā + d)²
log(s)
2
2C
1
2C
1
fa
(uxp2/3
+
2C,
(49)
2d
J1/3
T
a
ava
Va
Thus, taking the optimal learning rate = /22/3,
obtain the regret for the first batch with start as:
m(ā + 2)²
log(f)
2
20
20
Ar.wam
f +
+
22/3 +
f 2C,, //3
DX/2/3
f1/3
T
24

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
m(a + d)² p2/3 +
log(s) +2/2/3 +
20 20w + 2Cn f2/s
vd
vd
T
m(ā + d)² + 4Cio) .113+ + +log(s).
(50)
This completes the proof.
C. Main Results
In this section, we demonstrate the proof for all theoretical results that we proposed in the main body of the paper. We instate Assumption 2.1 and 2.2 are satisfied.
C.1. Proof of Theorem 3.1.
By Theorem B.3, we obtain
Ar = ([((())) + v(x))]
|p'll 1 Σ a1
p
E
Pt p"1l + + axt b)
2
Ip' E (b Ax) B+
|+||
|||
+ μā
+E [ll(Az b) llp: - pp p²113]
This completes the proof.
C.2. Proof of Theorem 3.2.
Combining the results of Theorem B.6, Theorem B.7, and Theorem B.9, for some constant Creg > 0, we obtain:
AT = An An + Ars
m(ā + d)²
2F + m(a + d)²
+ mm(a mm(a+dd) VF
+
d
mC
Cip + x2
+ (ā (ā+d+
82 log(k)
m(a + d)²
20
Coplog(J)
4Cb
+0O) 1//3.
(51)
Vk
vk
Therefore, achieve the worst-case regret of:
AT Olog((k) + /s 113).
(52)
For special cases,
1. If we LP-based method the first batch, then will have Ar, log(f). Total performance follows
Ar < lo) + f1/3) s log(v + 22/3 E O(lo((T) + f2/3).
(53)
2. If we have a warm start for the first batch, with the initialization Iipo achieves Ar; E 1/ /3 + log(f)) by Lemma B.10. Thus, total performance follows
p'll < 1-/3,, then the first batch regret
Ar s (f k)) + 2 e O(log(T) + +f 1/3).
(54)
This completes our proof.
25

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
D. Auxiliary Results
In this section, we provide auxiliary results to support the proof the previous three sections, These lemmas focus on pure mathematical derivations.
D.I. Technical Support for LP-based Analysis
Lemma D.1. Denote d1,(j+1)f, diis as the average consumption of i-th type resource at time ( + 1)f and if. There
exists a constant Cree depending on d, a, m, v, A, us, and Cip such that:
Cree
4pa² Cip
E(d,,i+i)s -d)² = E(d di)² (k (k-j- (k-j --ji-WW(+Y
El d;)²l.
Lemma D.2. With the recursion relation in (26), there exists a constant
> depending on a, m, Us X, ph and Cip such
that the summation of the total deviation of de with the original d satisfies:
C
E [diss - d:) log(k).
Proof of Lemma D.1. We analyze each term in (25). The key technique we is to take conditional expectations and simplify the double summations.
(a) Term 1.
G++Dif 2i=jf+1 diss- - az arr 1)
E
(T (j+
Gf1)ff (+1))
E
Σ Σ
E
> at p) an.l(rs > (.D) dir
7 1)1)
(=)++ #fi
G-11)f
E
Σ
E (diss ai,e > at 2 dzf]
[T - 1)
(=1/+1
(+1))
E
Σ
B((dess - -
af o. an any > ()]r;))) d,s]
dda
E
(+11ff
- aiellree > a pT5 dis
- > a.Drir)
(T- (1+1)f)
(T- (j 1)f)²
d)²
(since 16 doist ar > af pir)
0 for binding terms)
(T (j -1++1//7
(a d)2
(since [T] k- k-
(k - 1)2
(b) Term 2.
[ Dt=jft1 arre > a. aTp;,) aiel(re > at P(tn))))?
E
(i+
Sk+1is E (a, aTr;,) - I(re a. (()4))))) (Ir, a.r;)) I(r, a. afp d11]
E
(T- (1-(+++) 111)
26

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
When f= 8,
E { pir) I(re > al P dis S sa²
When l + 8, by Assumption 2.2,
(ar,e(((re ( - I(re > at PoHnn))aaall(( a. pzs) [(r > a Po+ny))) dy]
B
E
E
- I(re > at Potny))aa > a. p}r) I(r, > a P(+1)))) a; a. ddj
E
[(re a
> p1) I(r > a P(+))) a at [ [(r, > a pjr) I(r > a, ( as) dgs
E
(ie(P(re > at pis ar) - P(re > a P(+1)) as)) ( > a, Pjj Dis a.) - P(r, > a Pisttis as))) | d3s
< E
aa (P(+1)) - p}j)) a (PU+1)) - -P}s) dis (using Assumption here)
< uLa" [((((+))) )² |js]-
Combining these two cases together and by the convergence of LP-based method, we obtain the bound for Term 2 as
--jff4 arlel(r > a. - anee > at P(+1))))
G+1)$
E
(T (J+++11) 1)f)
(++1)
(+1)f
(T (j 1)5 E
Σ d +
Σ
aaa B[(pG-1)5 P dis
[-1f+1
1
(Fa² + f " - (dp)l))))))
$ (T' - (j 1)f)2
1
(SaP+ + 12 Cip) if
(by Lemma A.4)
(T
2² + 3
1
(c) Term 3.
Lisjst di.s aiee > at (iss) ) +j+
(++1)f
2E
(drss - di)
(++1)f
E
Σ
E
artl(r aul p(r))) dis] (diis - de)
T (j 1)f
(=1/+1
0. (by the definition of binding terms)
(d) Term 4.
(i-1is Disifti anel(re aTP;,) agell(ee > at (PPHH)))
2E
(diis - di)
T-(++1)/
(j+1))
2 T (j + 1)f
Σ
(digf d.)a, E [(ree > at aTri.)) I(re > at po+ns) at)
E=iff1
27

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
(+1))
$ T (j 1)f
2
Σ
E
(digs-djaay
P(re > at Pjs as) P(re at Pu+ns ai)
f-ff+1
(+1))
2
$ T (j + 1)f
Σ
E
-dass-di)pan (pG+1)s - -P}})
(by Assumption 2.2)
t=
(++)))
2ua
$ T (j+1)$
Σ
Bi(diss- dd]3] VE(PU+H> -P1,)3] (by Cauchy's 's inequality)
8-$f+1
2p
V Ctp
$ T 1)f
B[(dess- d4)
Vif
Apa² UCip
|E(dd.s-- -.
(k j- 1)v( (0(++1)), 1)f
Term 5.
(++1)f
> (rr pjr) T T
Eiijfti are > at pi)) aneel at po+ni)) TéiS <r)
Imjffi -
21E
T T T-(++1))
Ltiit doss aellre > a Pjs)
(j+1)8
2
Zi=isti a,e a P.p) - > af P(+1)f)) 2
(i+l)s
< 2
E
T --+++1]
(-(++1))
(a + d)2
722 J1paatipp
< 21
V
(h: j - 1)25 V (k-j- 1)25
(by results of Term and Term 2)
2a(a + d) + 11P02Cpp
jk-j 1)
Combining all the terms, we obtain the upper bound as:
E [di - d.) E(di.j d:)2+ + (ā+
8² + 1
(k jk-j 1)2f
(k- -
2α(a + d) / + 112
4nā² TTp
jk-j-10 1i + 1)f V B((dess - d.)
(k - j - f
Taking Cree = (ā + d)² + d² + Ci + 2a(a + d) / CiaaCrp completes the proof.
Proof of Lemma D.2. We consider a general sequence {2, with
R
VR
2j+1 S 2j +
jk-j-1 1)25
where R > 0 is a constant.
Taking sum on both sides of the inequality and re-arranging, we have
Σ
(k j - 1)(2+11 - 21)5 5
16R
+
16R
Σ
Vzj
(k: +
1)f
f
+I
5=1
j=1
16R
16R
<
log (k) +
f
Vj
+1
j=1
28

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Noticing that Σソ= (k- j 12(4+11 - 2z) = Σi=z Jg. we have
2
k
k
16R
16R
k
4K
3j
f
log
log(A:)
We treat Σj=1 2j as the variable, then solve and get
12R log(k))
2j S
j=1
With this result, consider our recursion in (26), take the constant C = 12 max 16 > 0, we obtain:
k E ((diss-d))) S f log(k).
C
j=1
D.2. Technical Support for First-order Analysis
Lemma D.3. Following the updated rule of furs-order method, we derive the last dual price satisfies:
Cip
Va + m(a + d)
Va P
Blpp++I HMPT+1-p'l1 -p'll
Vu>(T-kfjk) - kfjks
VuX
T
Proof of Lemma D.3. According to Lemma A.6, take ar = a < vx
we derive the conditional expectation as
E PT+1 - 2211|1 pusl= s (1 - (l))BlI1TTT -p" 1=11?
pks + am²m(a + d)²
T-
< (1 - -Aa)T-kflppp -p"11+ +
Σ
a am + d)²(1 vda)
j=0
kf - 1112 + a² a²m(a (a + d)²
< (1 - (a))T-billpx>-
v\a
vxa(T k.f) lpas p'112 am ( + d)²
1
(55)
v1
where we use the technique of 2j=0 T- a² a²m(ā + d)2(1 - vda) <
1-(1-DAa}~
and (1 - Vdxa)T-K T-K VAo
vλa
I+ -Aa(T-Kf)
By LP-convergence result in Lemma A.4, we know Blips p-'l S Cyp By Proposition 3.3 in (Gao et al., 2024), we
know the event E = ||pa]
p=1l <
with probability P> 1 - 7④. By Lemma B.2, we know |p:l| < p. vky
Cip
Thus, we have
E pTT1
p²1 < |rr+ -p"11" P(E) + E PT+1 P'11-1] PPE)
Cip
1 +
maa + d)²
P
S
a T
(56)
vX(T kf)kf
a
29

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Thus, va+bs va vb for any b> O, by (56), we have
Cip va +
.va+ + m(a + p T22
-1prt1-p'11 VVAIT -AlT-kfoo kf)kf
Ved
This completes the proof.
E. Supplementary Experiments
In this section, we provide more experiments to further evaluate the performance of our algorithms. We consider a more general and complex input distribution and include additional comparisons with recent methods.
E.1. New Distribution
As an extension of Section 4.1, our goal is to evaluate the main algorithms with different choices of re-solving frequency E (T\/3, T1/2, 21/2, We consider a more complex distribution for reward and resource consumption requests and guarantee that Assumptions 2.1 and 2.2 are still satisfied.
Consider
Input III: ag ~ min(1, max(0, 2)), re Unif(0, 1]
where z ~ ((1) Student's t-distribution with degree of freedom.
We generate (re, a; )T= from Input III and keep other parameters T E 100) and d, Uniform [1/3, 2/3] the same in Section 4.1. We report the average result over 100 trials for each experiment and use the classic first-order method with /3 regret (Algorithm 4) as a baseline.
Table 4: Algorithms under New Distribution.
Figure 5: Regret for various re-solving frequencies.
Algoridim
Algocithm
T
First-Order
Low freg
Mid freq
High freq
10a 3.78
1.68
1.26
1.20
10
10.69
2,60
2.10
1.54
10"-
Algorithm
10"
36.79
4.79
3.67
2.54
Regret
10a
117.13
10.45
6.17
3.56
10a
377.84
34.54
14.30
5.48
10a
10a
3.78
1.24
1.17
1.13
10s
Algorithm
10
36.79
2.99
2.15
10a
10a
117.13
9.78
4.88
3,05
102
107
10a
10a
10a
16a
107
10f
10"
10
Horizon
Horizon
10a
377.84
25.96
8.90
4.86
Fist-Order
Algorithm Mid freq
Algoritum 2
flog
High froq
Under the new distribution, our algorithms still exhibit a strong regret performance. shown Table and Figure 5, we observe that regret decreases as the re-solving frequency increases. This trend holds consistently across both algorithms and is consistent with the guarantees of Theorem 3.2.
E.2. More Comparison
Building on the comparison baseline methods Section 4.2, we evaluate our algorithms against recent works. As reminder, algorithms employ frequent LP-solving learn online dual price under continuous support. Li et al. (2024) considers similar problem using infrequent LP-solving to update the dual variable but under finite support.
To compare them, we adapt our algorithms to finite support and take the re-solving frequency f = T from Section 4.1; We take the best-performed parameters for the infrequent method where the number of customer types n = 50 and = 3 = 0.95 which control the solving times near start and end. We take the horizon over T e [10?, 10 and report the average result over 100 trials for each experiment. We still use the first-order method in Algorithm 4 as baseline.
30

---

Wait-Less Offline Tuning and Re-solving for Online Decision Making
Table Algorithms comparison.
Figure 6: Regret for various algorithms.
Y'
Regret
Algorithm
Compute Time (8)
11.92
First-Order
0.002
10a
11.12
Infrequent L.Phased
0.724
3,77
Algorithm
0.790
3.69
Algorithm
0.782
10
36.37
First-Order
0.01
10
14,20
Infrequent LP-based
Regret
Algorithm
3.015
6.35
Algorithm
3.112
110.22
First-Order
0.109
10t
10
20.90
Infrequent L.Phhsed
1.028
16.41
Algoritum
52.95
10.84
Algorithm
52.39
312.26
First-Order
1.106
10
28.80
Infrequent LP-based
4,929
20.58
Algorithm
1261.0
Horizon
14.30
Algorithm
1305.4
Fom--Ode Order
Infresent
Alaurimn
Alaunibe
Table 5 and Figure 6 demonstrate the algorithm regret and computation time across different horizons. While the infre- quent LP-based method has faster computation, our algorithms show a competitive performance decision optimality and achieve lower regret under finite support.
31


Reviews:
[{"review_id": "O1xz8dyhNa", "reviewer": "Reviewer_LeBH", "summary": "This paper studies online linear programming and proposes an algorithm based on switching between a first-order method and a linear programming method proposed in previous literature to achieve both better computational efficiency and smaller regret by properly choosing the switching frequency f. There are also simulation results provided to demonstrate the improvements in computation time and regret performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer LeBH**\n\nThank you for the valuable feedback on our paper.\n\n**Other Strengths And Weaknesses**\n\n1. Unknown horizon $T$\n\n   This is a very good point. To our knowledge, in the OLP setting, an unknown horizon length $T$ can make the problem much more complicated: it is shown in [1] that it may not be possible to achieve sublinear regret with horizon uncertainty. In particular, the average resource assumption **A2.1 (c)** widely used in OLP literature is no longer well-defined, and an algorithm would also have to adapt to horizon uncertainty. Addressing this challenge would likely require first adapting LP-based and first-order OLP methods to uncertain horizons before tackling a hybrid approach.\n\n   Despite the theoretical challenge, in practice, it is often possible to make some prior prediction of $T$ using data-driven approaches or based on the resources available in hand. For example, in online advertising, the number of customers can be predicted from historical statistics. Besides, in practice, the selling horizon is sometimes decided by upper-level decision-makers. e.g., a company selling products before festival events. In this case, $T$ is available to the decision-maker as a problem parameter.\n\n2. Determine $f$ based on the remaining resource\n\n   Thank you for the insightful comment. Since $f$ determines both the LP resolving frequency and the switching time to the first-order method, the analysis would be challenging if the LP resolving frequency is dynamically adjusted.\n\n   However, we believe it's a good idea to determine the switching time based on the remaining resources:\n\n   -  One way is to define a new stopping time based on some pre-specified resource level (e.g., $f \\cdot d$ when there's only one resource), after which the algorithm switches to the first-order method. The regret accumulated by the first-order method would be of order $O(\\sqrt{\\tau_f})$. A rough estimate of $\\tau_f =O(\\max\\\\{\\log f + \\log T, f\\\\})$ can be obtained from the analysis of the constraint consumption process [1], where $\\log f + \\log T$ arises from the deviation of $d_t$ (average remaining resource at time $t$) from $d$.\n   - The other way (more heuristic) is to determine the switching frequency based on the stability of the dual price $\\{p_t\\}$ obtained by LP. Suppose $\\{p_t\\}$ remains stable near the end of the horizon, then it suggests the resource consumption is smooth, and solving LP frequently is less necessary--switching to first-order methods would be ideal in this case.\n\n   We are glad to add a discussion in the revision but will leave a more rigorous regret analysis for future work.\n\n3. More discussions on technical novelty\n\n   Thanks for the comment. To our knowledge, our paper is the first result combining LP-based and first-order OLP algorithms, achieving the best-of-both-worlds guarantee: achieving efficient decision-making with regret that interpolates the performance of two algorithms. Technically, our contributions include\n\n   - We develop a regret analysis framework that unifies both LP-based and first-order methods. In the current OLP literature, there are two types of analyses, one based on stopping time [2] and the other based on a joint metric of regret and resource violation [3]. Although intuitively, these two analyses should yield similar guarantees, it is non-trivial to combine them when two algorithms need to switch to each other. In particular, we need to carefully handle the evolution of the dual price $p_t$ when switching between two algorithms. Since first-order methods are known to be less stable, it is important to also take care of the stepsize of the algorithm (see our discussion in B.2 and B.9).\n   - In addition, our work addresses a technical limitation of a previous work [4], where the authors also consider solving LPs periodically but require customers to wait at the beginning/end. Our analysis removes the need of waiting.\n\n   From a high-level point of view, our method resembles the pre-training (LP) and fine-tuning (first-order methods) of large-language models. \"Pre-training\" provides baseline regret guarantee $\\log (T/f)$ and \"fine-tuning\" performs minor refinement with improved efficiency.\n   \n   We will add more discussion about the technical intuitions in the paper in the revision.\n\n**Questions**\n\n1. Discussion of technical novelty.\n\n    Please see our response to \"Other Strengths And Weaknesses\".\n\nWe hope our response addresses your concerns and thank you again for your efforts in the review process!\n\n**References**\n\n[1] Balseiro, Kroer, & Kumar (2023). Online resource allocation under uncertain horizons. *ACM SIGMETRICS Abstract Proceedings*.\n\n[2] Li & Ye (2022). Online linear programming with new algorithms and regret bounds. *Operations Research*, 70(5), 2948–2966.\n\n[3] Li, Sun, & Ye (2020). Fast algorithm for binary integer and online LP. *NeurIPS*, 33, 9412–9421.\n\n[4] Xu, Glynn, & Ye (2024). Online LP with batching. *arXiv:2408.00310*.", "claims_and_evidence": "Most of the technical claims are clearly supported by convincing evidence.", "methods_and_evaluation_criteria": "Yes. The proposed method is evaluated by both regret and constraint violation, which makes sense for the OLP problem and its relevant applications.", "theoretical_claims": "The theoretical claims seem correct after a quick read. More comments on the technical results are listed in later boxes on strengths and weaknesses.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This paper is related to online decision making under constraints.", "essential_references_not_discussed": "I didn't find any.", "other_strengths_and_weaknesses": "Strengths: This paper proposes a very interesting question in online decision making: how to achieve both efficiency and low regret at the same time. The paper designs a novel algorithm based on switching between two previously designed algorithms to achieve the best of both worlds. By tuning the switching frequency, the proposed algorithm include LP and the first-order method as special cases. \n\nThe illustration figure in Fig 1 is very clear and helpful for understanding the algorithm.\n\nHowever, I have some questions.\n\n1.This algorithm relies on switching back to the first-order method in the last f steps. But what if T is unknown? How to determine when to switch?\n\n2. Relying on a pre-determined f can be conservative. Is there any idea to determine the switching time adaptively based on the remaining demand?\n\n3. The algorithm heavily relies on two algorithms previously developed. The paper could benefit from more discussion on the technical novelty, otherwise the paper may seem to have marginal contribution compared to the previous literature, e.g. (Li etal 2020) and (Li Ye 2022)", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please provide more technical discussions on the technical novelty to highlight the challenges and novelty compared to (Li et al. 2020) and (Li Ye 2022).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oJyrL5GqUS", "reviewer": "Reviewer_GkFi", "summary": "This paper studies online linear programming (OLP) under stochastic inputs. Algorithmic approaches to this problem can be broadly categorized into two types: (i) the LP-based approach, which repeatedly solves an LP using the entire history of observations and decisions, and (ii) the first-order approach, which employs a general dual mirror descent to update dual prices and makes online decisions based on the updated prices. It is known that the LP-based approach can achieve $O(log(T))$ (or even $O(1)$ in the case with discrete support) regret but suffers from high computational complexity. but suffers from high computational complexity. In contrast, the first-order approach can only achieve $O(\\sqrt{T})$ regret but  but is computationally efficient.\n\nThis paper proposes an algorithm that integrates the key ideas of both existing approaches. Specifically, the algorithm solves the LP at a frequency $f$ (i.e., for each batch of arrivals of size $T/f$) and applies the first-order approach only to the first and last batches. The final regret is $O(\\log(T/f) + \\sqrt{f})$, which smoothly interpolates between the performances of the two existing approaches.\nTo achieve this, the paper unifies the regret analysis of the two approaches by decomposing the regret into three components.\n\nThe paper also presents an enhanced version of the algorithm that applies the first-order approach to each batch while using the dual price from the LP-based approach as the initial point. Although this enhanced algorithm shows performance advantages over the original algorithm, no performance guarantees are provided.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer GkFi**\n\nThank you for your positive evaluation of our paper!\n\n**Experimental Designs Or Analyses**\n\n1. Computational efficiency.\n\n    We kindly refer the reviewer to Table 3 (Page 7 top) for a running time comparison between different methods, and in the revision we'll add a more comprehensive experiment to compare the computational aspects of different algorithms.\n \n2. Parameter setting.\n\n    Thank you for your comments. In Algorithm 1, we take the learning rate as $\\mathcal{O}(1/f^{1/2})$ when $t \\leq f$ and $\\mathcal{O}(1/f^{2/3})$ when $t \\geq kf$. In Algorithm 2, we take the learning rate as $\\mathcal{O}(1/t)$. We'll add a more detailed experiment setup section in the revision to cover the parameter settings (frequency/learning rate) of different algorithms.\n\n3. $T^{1/3}$ solving frequency.\n\n    Thank you for pointing this out. We have experiments across different re-solving frequencies $f \\in \\\\{ T^{1/3}, T^{1/2}, T^{2/3} \\\\}$ in Section 4.1 to evaluate the performance of our main algorithms. A smaller $f$ leads to lower regret but higher computational cost, while a larger $f$ improves the decision efficiency at the expense of decision optimality. Section 4.2 is designed to compare the performances among different algorithms, and the choice of $T^{1/3}$ for Section 4.2 is simply one of the candidate frequencies. \n\n\n\n**Other Strengths And Weaknesses**\n\n1. Insights of Algorithm 2.\n\n   Thank you for pointing this out. Algorithm 1 has a solid theoretical guarantee, but it does not update the dual price between two consecutive LP resolves. Algorithm 2 is proposed to alleviate this issue: between two LP resolves, the dual price is also updated using the first-order method. We adopt a smaller step size for first-order updates between LP resolves in Algorithm 2 to avoid deviating too far from the LP-guided solutions. We leave a more rigorous analysis of Algorithm 2 to future work. \n\n3. Discussion on the frequency of resolving and comparison with [1].\n\n   Thank you for the comment. Indeed, in [1], the LPs are solved at geometric intervals. However, this type of resolving only guarantees regret of order $O(\\sqrt{T})$, and to achieve $o(\\sqrt{T})$ regret under our setting, the only two ways we are aware of are \n\n   - solving the LPs at every time interval with an action-history dependent algorithm (adjusting $d_t$). This achieves $O(\\log T)$ regret [2].\n\n   - using an $o(\\sqrt{T})$ stepsize for the first-order method starting from a good initial guess of $p^\\star$. This achieves $O(T^{1/3})$ regret [3].\n\n   Our algorithm essentially interpolates between these two $o(\\sqrt{T})$ regret bounds, and our LP-based algorithm also requires periodic re-solving. Otherwise, only $O(\\sqrt{T})$ regret can be guaranteed.\n\n**Questions For Authors**\n\n1. Insights on the performance enhancement from Algorithm 2.\n\n   Please see our response to \"Other Strengths And Weaknesses\".\n\n2. Frequency $T^{1/3}$.\n\n    Please see our response to **Experiment Designs or Analyses**.\n\n\nThank you again for your efforts in the review process!\n\n**References**\n\n[1] Agrawal, S., Wang, Z., & Ye, Y. (2014). A dynamic near-optimal algorithm for online linear programming. *Operations Research*, *62*(4), 876-890.\n\n[2] Li, X., & Ye, Y. (2022). Online linear programming: Dual convergence, new algorithms, and regret bounds. *Operations Research*, *70*(5), 2948-2966.\n\n[3] Gao, W., Sun, C., Xue, C., Ge, D., & Ye, Y. (2024). Decoupling Learning and Decision-Making: Breaking the $\\mathcal {O}(\\sqrt {T}) $ Barrier in Online Resource Allocation with First-Order Methods. *arXiv preprint arXiv:2402.07108*.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I checked the proofs of the main Theorems 3.1 and 3.2. To the best of my knowledge, the proofs are correct, and the unified regret analysis is interesting and could potentially be applied to more general settings.", "experimental_designs_or_analyses": "Yes, I reviewed the numerics in Section 4. Although all experiments are conducted using synthetic data, they effectively demonstrate the regret of the proposed algorithms under varying frequencies. However, there are two issues with the experiments: (i) although the paper discusses computational efficiency, no detailed experiments are provided in this section; (ii) there is a lack of discussion on parameter settings. First, in Section 4.2, the frequency is fixed to be $T^{1/3}$ without explanation. Does this relate to Proposition 3.5, which computes the optimal re-solving frequency? Second, the learning rates used in the experiments are not specified for either Algorithm 1 or Algorithm 2.", "relation_to_broader_scientific_literature": "The combined algorithms for OLP in this paper bridge the algorithms and results from LP-based approaches and first-order methods. They elegantly demonstrate the trade-off between performance and computational complexity in online decision-making literature.", "essential_references_not_discussed": "I am not aware of any missing references.", "other_strengths_and_weaknesses": "- There are still no performance statements on the enhanced algorithm (Algorithm 2). Some additional discussion is needed to clarify the insights and limitations of this algorithm to help better understand it. For example, the learning rates for the first-order updates in Algorithm 1 and Algorithm 2 are set differently. What is the reason for this setup, and is there any potential for improvement?\n- It is not very clear why the LP approach is re-solved at very $T/f$ intervals. The re-solving idea was proposed in the very first OLP paper [Agrawal2014], where the LP is solved at geometric time intervals. In fact, it might make more sense to reduce the frequency of re-solving the LPs as time goes on under stochastic inputs (since the dual prices are gradually learned). There is a lack of discussion on the choice of re-solving frequency at the beginning.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Can you give any insights on the performance of the enhanced algorithm (Algorithm 2)? \n\n- In Section 4.2, why is the re-solving frequency fixed to $T^{1/3}$? Can we use the optimal frequency suggested in Section 3.4? What are the pros and cons?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TYSOrA3q2L", "reviewer": "Reviewer_QGM5", "summary": "This paper introduces a hybrid algorithm for Online Linear Programming (OLP) that combines LP-based and first-order methods. By periodically re-solving LPs at frequency \\( f \\) and using first-order updates in between, the method achieves a regret bound of $\\mathcal{O}(\\log(T/f) + \\sqrt{f}) $, balancing computational efficiency and decision quality. Experiments demonstrate significant improvements: 20x lower regret than pure first-order methods and 100x faster runtime than pure LP-based methods. The theoretical analysis is rigorous, and the parallel framework addresses key challenges in unifying LP-based and first-order regret formulations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer QGM5**\n\nWe appreciate your valuable feedback.\n\n**Claims And Evidence**\n\n1. Claims on the assumptions (non-degeneracy)\n\n   Thank you for pointing this out. We will add a more detailed discussion to clarify the assumptions in the paper. To achieve $\\mathcal{O}(\\sqrt{T})$ regret, we agree that these assumptions are not minimal. But we also want to note that without non-degeneracy (or its variant), [3] has shown that $\\Omega(\\sqrt{T})$ is a lower bound for OLP, and most of the literature in this line assumes non-degeneracy (or similar assumptions). \n\n**Experimental Designs Or Analyses**\n\n1. Experiments are only on uniform and normal distributions\n\n   We have added additional experiments on more problem distributions and tested performance under different re-solving frequencies. Our algorithms continue to demonstrate strong performance, consistent with the result in Theorem 3.2. We kindly refer the reviewer to the anonymous link [https://anonymous.4open.science/r/icml_2025_olp-6C17/](https://anonymous.4open.science/r/icml_2025_olp-6C17/) for more details.\n\n**Other Strengths And Weaknesses**\n\n1. Requirement on non-degeneracy\n\n   Please see our response to **Claims And Evidence**.\n\n2. Lack of direct comparison with existing literature\n\n   Thank you for pointing this out. [1] studies a similar problem under the finite support setting. We adapted our algorithms to finite support and added experiments to compare with [1] in [https://anonymous.4open.science/r/icml_2025_olp-6C17/](https://anonymous.4open.science/r/icml_2025_olp-6C17/). In the finite-support setting, we find that our algorithm achieves lower regret while [1] is often faster. We will add additional experiments and discussions in the revision.\n\n**Questions**\n\n1. Stopping time analysis\n\n   We believe that a stopping time analysis is possible. This paper adapts the analysis of the LP-based method to the metric of first-order methods, and we can do the other way around by properly defining a stopping time for first-order methods [3]. Another simple way is to \"subtract\" $O(f + \\log T)$ resource from the initial inventory and run OLP on this new problem, and in expectation, the resource violation from the original problem can be removed.\n\n2. Unknown time horizon\n\n   To our knowledge, in the OLP setting, not knowing the horizon $T$ makes the problem harder. In [1], it is shown that only a competitive ratio result is achievable when $T$ has uncertainty. The most challenging part is that the average resource assumption **A2.1 (c)** is no longer well-defined. Since both LP-based and first-order methods require some estimate of average resources to work, a lack of this knowledge makes the problem more difficult. \n\n    Although the problem is theoretically challenging, in practice, it is often possible to make some prior prediction using data-driven approaches or based on the resources available at hand. For example, in online advertising, the number of customers can be predicted from historical statistics. Besides, in practice, the selling horizon is sometimes decided by some upper-level decision-makers. e.g., a company selling products before festival events. In this case, it is available to the decision-maker as a problem parameter.\n\n3. $O(1)$ regret bound under finite support setting\n\n   This is also a very good question. To our knowledge, $O(1)$ regret is achievable in the finite-support setting with the same LP-based algorithm and a non-degeneracy assumption [4]. Since our analysis interpolates between the regret guarantee of first-order and LP-based methods, we believe the analysis in [4] can be adapted to give a similar result, which we leave to future work.\n\nThank you for your time in the review process!\n\n**References**\n\n[1] Li, G., Wang, Z., & Zhang, J. (2024). Infrequent resolving algorithm for online linear programming. *arXiv preprint arXiv:2408.00465*.\n\n[2] Balseiro, S., Kroer, C., & Kumar, R. (2023, June). Online resource allocation under horizon uncertainty. In *Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems* (pp. 63-64).\n\n[3] Balseiro, S., Lu, H., & Mirrokni, V. (2020, November). Dual mirror descent for online allocation problems. In *International Conference on Machine Learning* (pp. 613-628). PMLR.\n\n[4] Chen, G., Li, X., & Ye, Y. (2024). An improved analysis of LP-based control for revenue management. *Operations Research*, *72*(3), 1124-1138.", "claims_and_evidence": "**Supported Claims**:  \n1. **\"Balanced Regret and Runtime\"**: The claim of achieving $\\mathcal{O}(\\log(T/f) + \\sqrt{f})$ regret with reduced computational cost is well-supported by:  \n   - **Theoretical proofs** (Theorems 3.1–3.2, Appendix B–C).  \n   - **Empirical results** (Tables 2–3, Figures 2–3) showing 20x lower regret than first-order methods and 100x faster runtime than LP-based methods.  \n2. **\"Wait-Less Decision-Making\"**: The absence of decision delays is validated by comparisons with literature in Table 1 and Section 4.2.  \n\n**Potentially Problematic Claims**:  \n- **\"Minimal Assumptions\"**: The paper states that Assumptions 2.1–2.2 are \"minimal,\" but these include strict non-degeneracy assumption (Assumption 2.2(b)) . These may not hold in real-world scenarios.", "methods_and_evaluation_criteria": "The performance metrics based on regret and constraint violations are commonly used in the literature.  Empirical comparisons against LP-based (Algorithm 3) and first-order (Algorithm 4) baselines are also appropriate.", "theoretical_claims": "I have not fully checked the proof details. The decomposition into dual convergence, constraint violation, and leftover resources is logically sound. The final bound $ \\mathcal{O}(\\log(T/f) + \\sqrt{f}) $ relies on Lemma B.5 (dynamics of resource usage) and Lemma B.10 (warm-start regret). These assume non-degeneracy, but no critical gaps were found.", "experimental_designs_or_analyses": "It is nice that results are averaged over 100 trials (Section 4.1), which reduces variance.  However, the experiments were conducted solely on uniform and normal distributions, which may limit the general validity of the results.", "relation_to_broader_scientific_literature": "The paper extends two key lines of work:  \n\n(a) **LP-Based OLP**. Builds on Agrawal et al. (2014) and Li & Ye (2022) by reducing computation via periodic re-solving.  \n\n(b) **First-Order OLP**. Improves upon Gao et al. (2023) and Balseiro et al. (2022a) by integrating LP-guided dual prices for lower regret. \n \nThe \"wait-less\" framework addresses limitations in Xu et al. (2024), which requires batch-level delays.", "essential_references_not_discussed": "I did not realize that there was an omission of closely relevant literature.", "other_strengths_and_weaknesses": "**Strengths**\n\n(a) The parallel framework effectively leverages the strengths of LP-based and first-order methods, addressing a notable gap in existing OLP literature. \n\n(b) The regret decomposition and \"spectrum theorem\" provide a unified analysis of LP-based and first-order methods, overcoming incompatibilities in prior work. The derived regret bound interpolates between $\\mathcal{O}(\\log T) $ (pure LP) and $ \\mathcal{O}(\\sqrt{T}) $ (pure first-order), allowing practitioners to tune \\( f \\) based on computational budgets.\n\n(c) The experiments validate the framework’s superiority, with orders-of-magnitude improvements in both runtime and regret across synthetic datasets.\n\n**Weaknesses**\n\n(a) The analysis relies heavily on non-degeneracy (Assumption 2.2). The impact of relaxing these assumptions (e.g., degenerate) is unclear.\n\n(b) The experimental evaluation lacks a direct comparison with existing literature. For instance, [Li et al. 2024] also studies a similar problem, and it would be beneficial to include a comparative analysis to better highlight the advantages of the proposed approach.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "(a) Can the proposed algorithm and analysis be extended to the hard-stop setting, where the decision-making process terminates as soon as any one of the resources is exhausted? Additionally, how can the approach be adapted to handle scenarios where the time horizon is unknown?\n\n(b) It appears that in certain cases, LP-based methods can achieve $\\mathcal{O}(1)$ regret. Could the proposed algorithm attain this bound as well? If not, what are the key limitations preventing it from doing so?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of online resource allocation over a horizon of T steps under an unknown iid arrival model. Existing results show that resolving an planning problem at each time t gives a log T regret. While attractive in terms of regret, this requires too  much computational effort. The authors show that why carefully solving the planning optimization problem every f time steps, and using SGD for learning the duals in the first f and the last f steps, they can get a regret of O( log(T/f) + sqrt(f)) offering a tradeoff between computational cost and regret. Once caveat is that authors study a setting where they are allowed to violate the resource constraints, and therefore the objective is to maximize regret minus a penalty for resource overconsumption (which simplifies the analysis since the authors just need to study in some sense the dual function).

The reviews are mixed, with some concerns about technical novelty and comparison with prior work. Reviewer GkFi asks for comparison with Agrawal et al (2014) [who do not assume resource capacity scales with T, and also do not make the dual non-degeneracy assumption made in this paper]. I also found the description of Li et al. (2024) in Table 1 a bit misleading since the authors call their decision making delayed and that the paper required non-degeneracy -- my interpretation is that the decision is made at the time of arrival of a customer, so it is not delayed, and further from the abstract of tha paper "the proposed algorithm achieves a constant regret (even for the hard “degenerate” case) while solving LPs only O(log log T) times." The algorithm in Li et al. (2024) is primal based while in the current paper it is dual based (and requires dual to be non-degenerate), so there is sufficient gap in the methodology.

The review team is leaning towards weak accept decision as a result.
Decision: Accept (poster)