Online Resource Allocation with Continuous Random Consumption: Regret under Degeneracy
arXiv:2607.02196v1 [cs.LG] 2 Jul 2026
Jiawei Zhang Stern School of Business New York University July 3, 2026
Abstract We study online resource allocation when both rewards and consumption sizes may be continuously distributed. Requests arrive sequentially and must be accepted or rejected irrevocably under fixed resource capacities. Each request belongs to one of finitely many observable types; conditional on the type, both the reward and the scalar size are random, and the realized size scales a fixed type-specific resource-consumption vector. The model allows the deterministic fluid relaxation to be degenerate. We show that additive regret is governed by the size-weighted mass of requests whose valueto-size ratios lie near the active acceptance cutoffs. We formalize this quantity through an active weighted-mass exponent p. When p > 1, this cutoff mass is thin, and the problem is genuinely hard: every online policy must incur regret of order at least T 1/2−1/(2p) , and this holds for every p > 1. A sample-path marginal policy matches this lower bound up to polylogarithmic factors; and when p = 1, so that the mass grows linearly near the cutoff, it attains O((log T )2 ) regret. For example, if the size and the value-to-size ratio are independent and uniformly distributed, then p = 1; if instead the size and√the reward are independent and uniformly distributed, then p = 2. Thus the policy achieves o( T ) regret throughout this regularity class without any fluid non-degeneracy assumption, allowing both primal degeneracy and dual non-uniqueness.
1
Introduction
Online resource allocation asks how scarce resources should be allocated before the future is known. Requests arrive over time, reveal rewards and resource requirements, and require immediate decisions. Accepted or assigned requests consume resources irreversibly, while future requests remain uncertain. Network revenue management, online advertising, and online order fulfillment fit this broad template. A central question is how much value is lost because decisions are made online. We measure this loss by additive regret relative to a hindsight benchmark: the offline fractional allocation that observes the entire arrival sequence before choosing which requests to serve. This benchmark isolates the cost of the information gap between online and offline decision making. The goal is to understand how regret grows with the horizon T . This paper studies a stochastic online allocation model with accept/reject decisions in which both rewards and resource consumptions may be continuously distributed. Requests belong to finitely many observable types. Each arriving request reveals its reward and its size; conditional on the type, both variables may be continuous. The per-unit resource-consumption vector is deterministic conditional on the type, so accepting a request consumes its realized size times this vector. 1
When the size is deterministic conditional on type, the model specializes to the semi-discrete model of Jiang et al. (2025a). In the one-resource, one-type case, it contains the classical stochastic knapsack model with random profits and weights studied by Lueker (1998). Our main finding is that allowing continuous random consumption can change the worst-case regret exponent: there are bounded-density instances on which every online policy incurs polynomial regret. We also prove that a sample-path marginal policy attains the matching polynomial exponent, up to logarithmic factors.
1.1
Literature review
Our model is most closely related to the network revenue management literature (Gallego and van Ryzin, 1994; Talluri and van Ryzin, 2004). Most algorithms and analyses are built around the deterministic fluid relaxation of the online problem and the dual prices of that relaxation. A standard approach is to solve a fluid relaxation and periodically re-solve it as time and remaining capacity evolve. These dual prices, however, need not be well behaved: when the fluid relaxation is degenerate, the optimal dual price is not unique, and the acceptance threshold it induces can jump under an arbitrarily small change in remaining capacity, so a re-solving policy chases a moving target. √ When rewards and resource consumptions have finite support, this approach yields o( T ) regret (Reiman and Wang, 2008). Under a non-degeneracy assumption on the fluid relaxation, Jasin and Kumar (2012) obtain an O(1) regret bound. Without such a non-degeneracy assumption, Arlotto and Gurvich (2019) establish an O(1) bound for the multisecretary problem. Subsequent work obtains O(1) bounds for the more general network revenue management model (Bumpensanti and Wang, 2020; Vera and Banerjee, 2021; Vera et al., 2021; Li et al., 2024). For more general reward distributions, logarithmic regret is achievable under suitable distributional regularity (Lueker, 1998), but existing analyses typically also impose non-degeneracy or stability conditions on the deterministic fluid relaxation (Li and Ye, 2022; Bray, 2025; Balseiro et al., 2024). These conditions appear in several forms, including strict complementarity, uniqueness of the optimal primal basis, uniqueness of the optimal dual solution, and second-order growth of the dual objective. However, the non-degeneracy condition may fail, and degeneracy is not a pathological corner case. As highlighted by Bumpensanti and Wang (2020), it is likely to occur in practice. In capacity planning, when the expected demand√for a resource is of order T , the square-root law of inventory suggests a safety-stock scale of order T . When demand fluctuates, different resources may become bottlenecks at different times. In the associated linear program, the set of binding constraints may therefore change as capacity is depleted. Thus degeneracy is often the natural operating regime, not an exception. See Bray (2025) and Jiang et al. (2025a) for related discussions. Recent work clarifies which form of non-degeneracy is most relevant for certainty-equivalent (CE) resolving policies. Chen and Wang (2025) separate dual uniqueness from primal non-degeneracy and show that CE’s performance is governed by stability of the fluid dual price, rather than by primal non-degeneracy itself. When the √ optimal dual price, and hence the acceptance threshold it induces, is stable, CE can attain o( T ) regret, and in some distributional settings logarithmiclevel regret, even if the primal fluid solution is degenerate. The fluid dual price, however, need not be stable. √ Besbes et al. (2025) show that the CE algorithm can lose logarithmic guarantees and incur T -scale regret for the multisecretary problem with multiple types, each with a uniformly distributed reward. They design a different policy and obtain (log T )2 regret. Jiang et al. (2025a) obtain a (log T )2 bound for a special case of our model when the size of each type is deterministic. Zhang (2026a) shows that this (log T )2 rate is tight. Thus, even when consumption has finite support and reward densities are continuous and bounded below near the relevant cutoffs, degeneracy 2
has a price. But the price is mild: logarithmic regret becomes (log T )2 .
1.2
Main results
We show that the classical logarithmic picture changes once consumption is continuously distributed. The change is already visible in one-type, one-resource stochastic knapsack instances. We use the following three examples throughout the paper. Example 1. The reward and the size are independent and uniform on [0, 1]. Example 2. The reward and the size are independent and uniform on [1, 2]. Example 3. The size is uniform on [1, 2], and the value-to-size ratio is uniform on [1/2, 2] and independent of the size. A request of size β consumes β units of the resource, so the quantity that matters is the reward per unit consumed, the value-to-size ratio V /β; the offline optimum accepts requests in decreasing order of this ratio. We take Examples 2 and 3 at the fluid capacity 32 T , which is their expected total demand. Example 1 is the classical instance of Lueker (1998), at the capacities studied there.1 All three examples have bounded marginal densities on compact supports, but their regret orders differ. Example 2 has regret of order T 1/4 (Theorem 4.2 and Corollary 2.8), whereas Examples 1 and 3 have logarithmic regret.2 Two contrasts among these examples separate the roles of fluid degeneracy and cutoff mass. The first contrast, between Example 1 and Example 2, isolates the role of fluid degeneracy. Appendix B.1 computes the three fluid duals. Shifting the reward and size supports from [0, 1] to [1, 2] preserves the marginal shapes up to translation, but it turns a unique fluid dual price into a degenerate interval of prices, and it changes the regret order from logarithmic to T 1/4 . In Example 1 the fluid dual price is unique at every capacity; in Example 2, at capacity 32 T , every price in [0, 1/2] is optimal. The T 1/4 rate of Example 2 thus lies outside Lueker’s [0, 1]-uniform analysis, where the dual price is unique. The second contrast, between Example 2 and Example 3, isolates the mechanism behind the polynomial rate. These two examples have the same fluid capacity 32 T and the same degenerate fluid dual, yet their regret orders differ. In both, the operative acceptance cutoff is pinned at the lower edge of the ratio support; what differs is the size-weighted ratio mass just above that edge. In Example 3 this mass grows linearly with the distance from the edge. In Example 2 the edge is a corner of the joint support: a ratio near 1/2 requires the reward and the size to be simultaneously √ near their extremes, so the nearby mass grows quadratically. This thinness turns ordinary T -scale demand fluctuations into T 1/4 -scale regret. We formalize this mechanism through a distributional exponent p ≥ 1. The exponent measures how fast the weighted cutoff mass accumulates near an active acceptance cutoff. The linear case of Example 3 has p = 1. The corner case of Example 2 has p = 2. Slower mass growth corresponds to larger values of p. Our main result shows that a sample-path marginal policy attains O((log T )2 ) regret when 1
Lueker (1998) takes the capacity proportional to the horizon, with proportionality constant strictly below the mean consumption. At every such capacity, the fluid dual price of the [0, 1]-uniform instance is unique and positive. 2 Corollary 2.6 gives O((log T )2 ) for Example 3. In the single-resource, single-type case, the extra logarithmic factor can be removed. It comes from a uniform bound over all cutoffs, which is unnecessary when there is only one scalar cutoff. This recovers the O(log T ) order of the classical single-resource analysis of Lueker (1998); we do not carry out that refinement here.
3
p = 1, and O T 1/2−1/(2p) polylog T
regret when p > 1. We also prove√matching lower bounds for the polynomial exponent for every p > 1. Thus the policy achieves o( √T ) regret throughout this class. We emphasize that existing o( T ) additive-regret bounds for models with continuously distributed rewards and continuously distributed resource consumption are obtained under conditions that rule out the degeneracies studied here. Some papers, such as Li and Ye (2022) and Bray (2025), impose non-degeneracy assumptions explicitly. Others, such as Lueker (1998) and Chen and Wang (2025), impose primitive distributional assumptions under which the relevant fluid dual price is unique or stable. By contrast, our model and bounds allow both primal degeneracy and dual non-uniqueness.
1.3
Overview of the analysis
The policy prices each accepted request by the marginal value of the capacity it consumes in the expected offline problem—that is, by the drop in the average hindsight value over future arrivals caused by reserving that capacity. This is the RAMS principle of Besbes et al. (2025): charge this marginal loss as the price of capacity, so that minimizing the resulting per-step loss controls total regret. The reduction of regret to a sum of per-step losses goes back to Vera and Banerjee (2021), and is also used by Bray (2025) and Jiang et al. (2025a). Our contribution is to bound the perstep loss for our model—with continuously distributed consumption and without a non-degeneracy assumption. Proving this bound rests on three ideas. The first explains how the policy prices capacity without selecting a dual price. The second identifies the quantity that remains stable under degeneracy. The third handles the new difficulty created by random consumption. Price by an average of cutoffs, not by a selected dual price. Consider a request of type k with realized size z, arriving when the remaining capacity is b. Accepting it moves the capacity from b to b − zak . A classical analysis would price this capacity change by selecting a dual price at one of these capacities. This is unstable under degeneracy: many prices may be optimal at the same capacity, and a selected price can jump after an arbitrarily small perturbation. We avoid selecting a price. Instead, we traverse the segment from b to b − zak . Along this segment, the hindsight value is a concave function of one scalar. Such a function is differentiable almost everywhere, and at each differentiability point its slope is unambiguous. That slope acts as an acceptance cutoff for value-to-size ratios: it is the threshold q above which a request with ratio V /β is worth accepting and below which it is not. The marginal value charged by the policy is the average of these cutoffs along the segment. The kinks where dual prices are ambiguous form a null set, and the average passes through them. This averaging makes the policy well defined without a non-degeneracy assumption. It does not, by itself, prove a regret bound. The loss still depends on how far the cutoffs generated by different future sample paths can spread, and degeneracy is precisely the case in which cutoff movement need not be stable. Measure losses by borderline mass, and prove the product is stable. For a feasible request of fixed type and size, changing the cutoff can change the decision only when the valueto-size ratio lies between the two cutoffs. Thus the one-period loss is controlled by two quantities:
4
the width of the band between the cutoffs, and the resource carried by requests whose ratios fall inside that band. We call these requests borderline. The key point is that the product of these two quantities is stable, even when the cutoff width itself is not. Under degeneracy, two future sample paths can produce cutoffs that are far apart. But if little ratio mass lies between those cutoffs, the movement is mostly harmless. The analysis therefore controls cutoff width × borderline resource mass, rather than cutoff movement alone. We prove this product bound by comparing two typical future sample paths directly. Their empirical type totals and capacities are close. If their cutoffs differ, the difference in the resource they accept is carried entirely by requests whose ratios lie between the two cutoffs. A classical stability estimate for linear programs, due to Hoffman (1952) and requiring no uniqueness of the optimal solution, makes the resource each path accepts close whenever the two paths themselves are close. Combining these two facts nearly closes the product bound. The remaining term is proportional to the cutoff width alone. It corresponds to degenerate stretches where a cutoff moves while sweeping little or no mass. The distributional exponent p closes this gap: a ratio band of width ℓ near an active cutoff must carry weighted mass at least of order ℓp . This converts leftover width back into mass. Thus a smaller p means more mass near the cutoff and less regret, while a larger p means thinner mass and a larger price for degeneracy. p With n arrivals remaining, empirical fluctuations are of order log n/n. After the active-mass closure, the one-period bounds sum to O((log T )2 ) when p = 1, and to O(T 1/2−1/(2p) polylog T ) when p > 1. The stable object is therefore not a dual price. It is the product of cutoff width and borderline resource mass. Random consumption: different sizes see different bands. The product bound just described aggregates over sizes. The loss from a specific arriving request, however, is conditional on that request’s realized size. A request of size z is borderline when its ratio lies in the cutoff band, and this event depends on the ratio distribution conditional on size z. When consumption is deterministic conditional on the type, the conditional and aggregate distributions coincide, and the product bound finishes the one-period analysis. With continuously distributed consumption, they can differ sharply. The difficulty is most visible near a corner of the joint reward-size support. For each size z, the attainable ratios may begin at a size-dependent lower edge; as z changes, that edge can move into or out of the cutoff band. A short band can then contain little aggregate mass but still capture a large share of the conditional mass for sizes whose edge falls inside the band. A pointwise comparison between conditional and aggregate mass is therefore false. We show that an averaged comparison is enough. We integrate the conditional band mass over the size distribution. Sizes whose moving edge lies inside the band and sizes whose moving edge lies outside the band balance each other after integration. This recovers the aggregate product bound, up to one logarithmic factor. This size-integration step is the technical price of continuously distributed consumption. The lower bound isolates the same quantity from the other side. At the corner of Example 2, a band√of width ε carries resource of order εp T . Such a band cannot be reliably distinguished from the T -scale fluctuation of total demand until ε ≍ T −1/(2p) . Misclassifying requests in that band costs order ε per unit of resource, which forces regret of order √ ε T ≍ T 1/2−1/(2p) .
5
Section 2.4 turns this outline into a step-by-step roadmap with pointers to the formal statements. Sections 3 and 4 then prove the upper and lower bounds.
1.4
Further related work
Classical dynamic stochastic knapsack models with sequential arrivals and admission control were studied by Kleywegt and Papastavrou (1998, 2001). Marchetti-Spaccamela and Vercellis (1995) prove a (log T )3/2 regret bound for the online stochastic knapsack problem. Arlotto and Xie (2020) prove logarithmic regret for an equal-reward stochastic knapsack with random item sizes. Jiang and Zhang (2020) generalize this result to the multi-resource case. A separate literature studies stochastic knapsack and online packing through multiplicative approximation guarantees. One line compares algorithms with the optimal adaptive policy for stochastic knapsack or stochastic packing (Dean et al., 2005, 2008; Bhalgat et al., 2011; Ma, 2018). Another line studies prophet or LP benchmarks for online stochastic knapsack and obtains constant competitive ratios (Dütting et al., 2020; Jiang et al., 2025b). In random-order online packing and online linear programming, large-capacity assumptions lead to 1 − o(1) competitive ratios relative to the offline optimum (Kesselheim et al., 2018; Agrawal et al., 2014). Other finite-type online allocation models also admit constant or uniformly bounded additive regret. Examples include online packing, matching, and pricing (Vera and Banerjee, 2021; Vera et al., 2021), overbooking (Freund and Zhao, 2023), online decision-making with an uncertain horizon (Banerjee and Freund, 2025), dynamic matching (Asadpour et al., 2020; Gupta, 2024; Wei et al., 2023), and online resource allocation via primal-dual policies (He et al., 2025). A related line develops computationally efficient primal-dual, first-order, and re-solving √ methods for broader distributional settings. Classical first-order and primal-dual methods attain O( T )√regret (Balseiro et al., 2023; Li et al., 2023; Jiang et al., 2025), while recent refinements obtain sub- T regret under additional regularity or non-degeneracy conditions (Gao et al., 2025; Ma et al., 2025). The rest of the paper is organized as follows. Section 2 states the model, the distributional regularity condition, and the main regret theorem. Section 3 defines the sample-path marginal policy and proves the upper bound. Section 4 proves matching lower bounds for the polynomial exponent. Section 5 concludes.
2
Model, Assumptions, and Main Results
This section gives the formal setup and states the main regret bounds. We first define the online allocation model and the fractional hindsight benchmark. We then introduce the sample-path marginal policy. Finally, we define the weighted-ratio distribution, state the standing distributional assumption, and state the main theorem.
2.1
Model and the Sample-Path Marginal Policy
There are d resources and K request types. Type k has a fixed consumption direction ak ∈ Rd+ , with ak ̸= 0. Over a horizon of T periods, requests arrive i.i.d. The period-t request is Zt = (Jt , βt , Vt ), where P(Jt = k) = πk > 0, βt > 0 is the size, and Vt ≥ 0 is the reward. The decision maker Jt from a observes Zt and irrevocably accepts or rejects it. An accepted request consumes β ta P d budget bT ∈ R+ . Writing xt ∈ {0, 1} for the online decision, the realized reward is t Vt xt , and feasibility requires X βt aJt xt ≤ bT . t
6
We measure performance of an online algorithm against the fractional hindsight (offline) optimum. For a length-n arrival sequence Wn = (Z1 , . . . , Zn ) and a capacity b ∈ Rd+ , define the n-period fractional hindsight optimum ( n ) n X X OPTn (b; Wn ) = max Vi xi : βi aJi xi ≤ b . 0≤xi ≤1
i=1
i=1
The additive regret of an online algorithm ALG is T i hX Vt xALG . RegT (ALG; bT ) = E OPTT (bT ; WT ) − E t
t=1
The fractional optimum OPTT (bT ; WT ) upper bounds the binary hindsight optimum, and the two differ by at most dv: a basic optimal solution of the fractional LP has at most d fractional variables (the rest are pinned at 0 or 1 by the box constraints 0 ≤ xi ≤ 1), and rounding these down preserves feasibility while losing at most dv of reward. The fractional benchmark therefore yields the same regret rates as long as the reward has a bounded support. The instances are indexed by T . We assume the capacity grows linearly in the horizon, bT = Θ(T ), the standard fluid scaling in this literature. The sample-path marginal policy prices the capacity consumed by the current request through the expected fractional hindsight value of the remaining periods. For n ≥ 0, set Φn (b) = E[OPTn (b; Wn )], the expected fractional hindsight value of a length-n i.i.d. sequence, with Φ0 ≡ 0. We use the convention that OPTn (b; Wn ) = −∞ and Φn (b) = −∞ when b ∈ / Rd+ , where the feasible set is d empty; thus Φn is evaluated only at capacities in R+ . In the Bellman expansions below, every term Φs−1 (Bs − βs aJs ) carries the feasibility indicator 1{βs aJs ≤ Bs }, and the product is read as 0 when that indicator vanishes. At a decision epoch with s periods remaining and remaining capacity b, suppose that the current arrival is (J, β, V ) = (k, z, v). Define the marginal value of the capacity consumed by this request as ( Φs−1 (b) − Φs−1 (b − zak ), zak ≤ b, ∆s (b, k, z) = (2.1) +∞, otherwise. The sample-path marginal policy SPM accepts the request if and only if v ≥ ∆s (b, k, z).
(2.2)
The rule (2.2) is the sample-path instance of the RAMS principle of Besbes et al. (2025), which prices each action by the marginal value of the capacity it consumes in the hindsight problem. As with RAMS, implementing SPM requires simulation: the expected hindsight value Φs−1 has no closed form and is estimated by sampling future arrivals. Remark 2.1. Notice that the threshold in (2.2) is the marginal value of the expected hindsight relaxation Φs−1 . It is not a dual price of a deterministic fluid program. When the fluid relaxation is degenerate, the bid-price control algorithm with thresholds computed from fluid dual prices can be highly sensitive to small changes in capacity. In contrast, the function Φs−1 is Lipschitz in the remaining capacity through the kinks at which a fluid dual price would jump, so the marginal value in (2.1) varies continuously where a certainty-equivalent threshold does not. This distinction is what lets SPM handle degenerate instances. 7
2.2
A primitive distributional assumption
We now state the distributional regularity condition used in the regret analysis. The primitive ranges are bounded. Conditional on type k, the size satisfies β ∈ [β k , β k ], with β k > 0, and the reward satisfies V ∈ [0, v]. Put β = mink β k and β = maxk β k . The value-to-size ratio is R = Vβ . Since β ≥ β k > 0 conditional on type k, this also gives E[β | J = k] > 0 and mk = πk E[β | J = k] > 0, so every expression of the form β k /(πk E[β | J = k]) is well defined. Every resource is consumed by at least one type; unused coordinates are dropped. For each resource j, define αj = min{akj : akj > 0},
Mj =
v , βαj
yk =
d X
Mj akj ,
y = max yk . k
j=1
Then every realized ratio satisfies R ∈ [0, y]. The main regularity condition is imposed on a type-wise weighted ratio measure. For each type k and Borel set B ⊆ [0, y], define µk (B) = πk E[β 1{R ∈ B} | J = k] . In words, µk (B) is the expected type-k resource carried by requests whose value-to-size ratio lies in B. All hypotheses below are conditions on the arrival distribution through the measures µk and the conditional curvature measures defined next. For each size z, define Λk,z (B) = z P(R ∈ B | J = k, β = z),
B ⊆ [0, y].
This is a finite Borel measure on ratio space. The kernel Λk,z is the size-conditioned counterpart of µk : it records how ratio mass is distributed among type-k requests of size z. Let Pkβ denote the conditional law of β given J = k, and denote Bk = [β k , β k ]. Define the finite kernel measure Mk ( dz, dr) := πk Pkβ ( dz)Λk,z ( dr). Equivalently, for every nonnegative measurable g, Z Z Z g(z, r) Mk ( dz, dr) = πk g(z, r)Λk,z ( dr) Pkβ ( dz). Bk
The ratio marginal of Mk is the weighted-ratio measure: Z Mk (Bk × B) = πk Λk,z (B) Pkβ ( dz) = µk (B),
B ⊆ [0, y].
Bk
Endpoint-contact assumptions below are imposed on submeasures of Mk , not on the law conditioned on R ∈ U . Definition 2.2 (Contact branch). Fix a type k and a one-sided endpoint neighborhood U . Let x denote the oriented distance into the support, so that x = R − r at a lower endpoint and x = r − R at an upper endpoint. After this orientation, identify U with a local interval [0, x0 ]. A contact branch with exponent θ > 0 is a branch submeasure Mbr k ≤ Mk |Bk ×U represented 1 by a size coordinate ω ∈ (0, ω0 ). It consists of an injective C size map βk (ω), whose Jacobian is bounded above and below by primitive constants, a weight w with c ≤ w(ω) ≤ C, a size density 8
f (ω), an edge function e(ω), and exponents α, τ > 0 and γ ≥ 1 with θ = γ + α/τ, such that, with br Λbr k,ω denoting a finite branch curvature measure supported on [e(ω), x0 ] and having density λk,ω , f (ω) ≍ ω α−1 ,
γ−1 e(ω) ≍ ω τ , λbr , k,ω (x) ≍ (x − e(ω)) Z Z Z ω0 w(ω) g(βk (ω), x) Λbr g(z, x) Mbr k,ω ( dx) f (ω) dω k ( dz, dx) =
(2.3)
0
for every nonnegative measurable g. Equivalently, the branch ratio marginal is Z ω0 br br w(ω) Λbr µk (I) := Mk (Bk × I) = k,ω (I) f (ω) dω,
I ⊆ U.
0
The submeasure µbr k is the branch’s contact submeasure. All constants are primitive. The exponents α, τ, γ and the contact exponent θ = γ + α/τ are local to the endpoint-contact machinery; they are not to be confused with the capacity-sweep parameter θ of Section 3, the resource constants αj , or the capacity tolerance τ of Proposition 3.6. Informally, an endpoint-contact representation captures the case in which the feasible ratio support begins at a size-dependent boundary, so that type-k ratio mass accumulates only as the size moves away from that boundary. Definition 2.3 (Endpoint-contact representation). Fix a type k. A one-sided endpoint neighborhood U admits a single-branch endpoint-contact representation with exponent θ if there exist β br measurable finite subkernels ΛD k,z and Λk,z on U such that, for Pk -a.e. z, br Λk,z |U = ΛD k,z + Λk,z .
(2.4)
Define the corresponding kernel submeasures by β D MD k ( dz, dr) := πk Pk ( dz)Λk,z ( dr),
β br Mbr k ( dz, dr) := πk Pk ( dz)Λk,z ( dr).
The branch submeasure Mbr k is required to be a single contact branch with exponent θ in the sense of Definition 2.2. The ratio marginals are br µbr k (I) := Mk (Bk × I).
D µD k (I) := Mk (Bk × I),
(2.5)
They satisfy, modulo null sets, br µk |U = µD k + µk .
The dominated part satisfies, in the local endpoint coordinate, θ µD k ([0, x]) ≤ Cx ,
ΛD k,z (I) ≤ Cµk (I)
for every interval I ⊆ U and for Pkβ -a.e. z.
(2.6)
All constants are primitive and uniform over U . Definition 2.4 (Local endpoint mass exponent). Let ν be a finite Borel measure on R with interval support Sν . For r ∈ Sν , a right local exponent is a number θ > 0, when it exists, such that ν([r, r + x]) ≍ xθ
as x ↓ 0.
A left local exponent is defined by the reflected relation ν([r − x, r]) ≍ xθ
as x ↓ 0.
If r is an endpoint of Sν , the one-sided local exponent from within the support is called the endpoint exponent of ν at r. For the weighted ratio measure ν = µk , we write pk,r for this endpoint exponent when it exists. 9
Informally, Assumption 1 controls how the size-weighted ratio mass behaves near an active acceptance cutoff. Part (a) says this mass is at least ℓp and at most ℓ over a window of width ℓ, with the exponent p governing the lower bound; part (b) says that conditioning on a request’s realized size creates no additional concentration of mass, except possibly at a corner of the support, which is handled separately; and part (c) says such corners cannot arise in the benign regime p = 1. Assumption 1 (Weighted-ratio regularity). In addition to the boundedness assumptions above, the arrival distribution satisfies the following conditions for some exponent p ≥ 1 and primitive constants 0 < c ≤ C < ∞. (a) (single-interval support and active mass) For each type k, the weighted ratio measure has compact single-interval support Sk = supp µk = [rk− , rk+ ] ⊆ [0, y]. For every interval I ⊆ [0, y], write ℓk (I) = Leb(I ∩ Sk ). The active-mass bounds are c ℓk (I)p ≤ µk (I) ≤ C ℓk (I).
(2.7)
(b) (finite conditional-curvature cover) For each type k, the support Sk admits a finite cover by neighborhoods of the following two kinds, each relatively open in Sk and possibly overlapping, so that the cover has a positive Lebesgue number. Dominated neighborhoods. On a dominated neighborhood, for a.e. z and every interval I contained in that neighborhood, Λk,z (I) ≤ C µk (I). This simultaneous-in-I requirement is equivalent to the per-interval bound—that for each fixed I the inequality holds for a.e. z—by applying the latter to the countable family of rationalendpoint intervals, intersecting the corresponding full-measure sets of z, and extending to all intervals by continuity of the finite measures. Endpoint-contact neighborhoods. An endpoint-contact neighborhood is a one-sided neighborhood of an endpoint of Sk that admits the endpoint-contact representation of Definition 2.3. (c) (regular case) When p = 1, the finite cover consists only of dominated neighborhoods. Endpointcontact neighborhoods may appear only when p > 1. All constants in the active-mass bounds, finite cover, dominated-neighborhood comparison, and endpoint-contact representation are primitive and independent of T . The single-interval support condition in Assumption 1 is a modeling convention rather than a substantive restriction when support components are observable. A type whose ratio distribution has several observable support components can be split into several observable types, one for each component. This convention keeps the projection and normal-cone arguments below free of internal gaps. No rectangular or product support for (β, R) is assumed, except inside the endpoint-contact neighborhoods of Definition 2.3. For later use, define the type-wise projection onto the active ratio support by Πk (q) = min{rk+ , max{rk− , q}}, q ∈ [0, y]. 10
For a general compact interval B = [B− , B+ ], we use the analogous notation ΠB (q) = min{B+ , max{B− , q}}. The projection collapses only the two value-flat rays outside a single support interval; it does not cross internal gaps. The two local structures in Assumption 1 have different roles. On a dominated neighborhood, the size-conditioned curvature is comparable to the weighted ratio measure. Thus conditioning on the realized size does not create an additional singularity. Endpoint-contact neighborhoods are the only places where this domination may fail. There, conditional on size, the feasible ratio interval can start at a size-dependent edge e(ω). The contact conditions in Definition 2.2 provide exactly the extra structure needed for the endpoint Hardy estimate, a weighted integral inequality used in Section 3. The fully dominated requirement when p = 1 rules out such non-dominated contact in the regular regime. The exponent p in Assumption 1 is the active weighted-mass exponent that determines the regret rate in Theorem 2.5. It is a property of the arrival distribution, not of the policy or the capacity ratio. If several values of p satisfy the active-mass condition (2.7), the sharpest bound is obtained by taking the smallest admissible one. In the structured classes below, this exponent can be computed explicitly from the endpoint growth of the weighted ratio measure.
2.3
Main Regret Bounds
We now state the regret guarantee for the sample-path marginal policy. The theorem gives a distribution-dependent rate through the active weighted-mass exponent p, and the corollaries translate this exponent into primitive conditions for several common model classes. Theorem 2.5 (Regret bound for the sample-path marginal policy). Under the model assumptions of Section 2.1, the linear capacity scaling bT = Θ(T ), and Assumption 1 with active weightedmass exponent p, the sample-path marginal policy defined with the exact expected hindsight value Φn = E[OPTn ] satisfies RegT (SPM; bT ) ≤
( C (log(eT ))2 , C T 1/2−1/(2p) (log(eT ))(p+1)/(2p)+1 + C,
p = 1, p > 1.
Here the constant C depends only on the model primitives (including the direction matrix) and the constants in Assumption 1; it depends neither on T nor on the capacity bT . In fact the bound holds for every capacity bT ∈ Rd+ ; the linear scaling bT = Θ(T ) is the regime of interest and enters only through the matching lower bound of Section 4. The proof of Theorem 2.5 is presented in Section 3. Concentration bounds the empirical cutoff error; the active weighted-mass condition (2.7) then governs how that error becomes lost mass, and the dominated-neighborhood comparison and endpoint-contact structure convert this into a bound on the one-step loss. The next corollaries translate Assumption 1 into more primitive distributional conditions. They are grouped by the source of nonregularity: first the ratio distribution itself, then the joint distribution of value and consumption, and finally the shape of the consumption distribution. Each proof identifies the corresponding value of p and then applies Theorem 2.5; the proofs are collected in Appendix B.
11
Corollary 2.6 (Independent size and ratio, bounded density). In the setting of Theorem 2.5, for each type k, let (βk , Vk , Rk ) have the conditional distribution of (β, V, R) given J = k. Suppose that βk and Rk are independent, and that Rk has a density bounded above and below by positive constants on its single-interval support. Then RegT (SPM; bT ) ≤ C (log(eT ))2 . This regular regime extends the O((log(eT ))2 ) guarantee of Jiang et al. (2025a) from deterministic consumption with continuous reward to random consumption that is independent of the ratio. The bounded ratio density keeps the active weighted-mass exponent equal to one. When the ratio density vanishes at an endpoint of its support, the exponent becomes larger than one, and the regret turns polynomial at a rate determined by the order of vanishing. Corollary 2.7 (Independent size and ratio). In the setting of Theorem 2.5, for each type k, let (βk , Vk , Rk ) have the conditional distribution of (β, V, R) given J = k. Suppose that βk and Rk are independent. Suppose also that Rk has single-interval support, is regular in the interior of that support—meaning c|I| ≤ P(Rk ∈ I) ≤ C|I| for every compact interval I in the interior—and at each endpoint r satisfies the one-sided interval bound c |I|θk,r ≤ P(Rk ∈ I) ≤ C |I| for every interval I in a one-sided endpoint neighborhood, with endpoint intervals of order xθk,r . With θ = max θk,r > 1, k,r
the sample-path marginal policy satisfies RegT (SPM; bT ) ≤ C T 1/2−1/(2θ) (log(eT ))(θ+1)/(2θ)+1 + C. This bound matches, up to logarithmic factors, the polynomial regret rate obtained by Besbes et al. (2025) for the multisecretary problem. Corollary 2.7 extends the same polynomial exponent to multi-resource allocation with random consumption; the deterministic-consumption case βk ≡ 1 is included as a special case. The additional loss is logarithmic under the stated independence and endpoint mass conditions. The two preceding corollaries take the endpoint behavior of the ratio distribution as primitive. This behavior can also arise from simpler primitives. When value and consumption are independent, the ratio support can acquire a corner at an endpoint even if both marginal densities are bounded above and below. In that case the active weighted-mass exponent is two. Corollary 2.8 (Bounded independent densities). In the setting of Theorem 2.5, for each type k, let (βk , Vk , Rk ) have the conditional distribution of (β, V, R) given J = k. Suppose that Vk and βk are independent, have compact supports bounded away from zero, and have densities bounded above and below by positive constants on their supports. Then RegT (SPM; bT ) ≤ C T 1/4 (log(eT ))7/4 . The exponent two in Corollary 2.8 is not special. Holding the value distribution fixed and allowing the consumption density to vanish at an endpoint gives a continuum of active weightedmass exponents.
12
Corollary 2.9 (Beta consumption and uniform value). In the setting of Theorem 2.5, for each type k, let (βk , Vk , Rk ) have the conditional distribution of (β, V, R) given J = k. Suppose that Vk ∼ Unif[vk− , vk+ ], with 0 < vk− < vk+ , is independent of βk = β k + (β k − β k )Yk , where Yk ∼ Beta(ak , bk ) with ak , bk > 0. Then, writing q = maxk {ak , bk }, RegT (SPM; bT ) ≤ C T 1/2−1/(2(1+q)) (log(eT ))(q+2)/(2(1+q))+1 + C. Across the four corollaries the single exponent p interpolates between the polylogarithmic regime and the T 1/2 barrier.
2.4
Proof roadmap
We give the proof of Theorem 2.5 in Section 3. Before turning to the details, we summarize the four steps of the argument. Step 1: Regret reduces to one-period Jensen losses. The first step is to show that a Bellman comparison along the SPM trajectory bounds regret by a sum of one-period Jensen losses: X C RegT ≤ C + E[EW [H(YW )] − H(EW [YW ])] + . s s P The harmonic term s C/s = O(log T ) comes from rounding the offline solution’s decision on the current arrival to a binary value; it is dominated by the Jensen losses in every regime below. Here H(r) = E[(V − zr)+ | J = k, β = z] is the expected acceptance surplus of a type-k request of size z at per-unit-size price r, convex in r. For a future path W of length n = s − 1, YW (b, k, z) =
OPTn (b; W ) − OPTn (b − zak ; W ) z
(2.8)
is the per-unit-size drop in the offline value when the future path W is forced to reserve zak units of capacity for the current request. Thus the dynamic regret analysis reduces to bounding the Jensen gap generated by the random pathwise marginal YW . Step 2: The marginal is an average of bid prices. The marginal in (2.8) is a capacity difference, and we analyze it by sweeping continuously between the two capacities. For θ ∈ [0, 1], set g(θ) = OPTn (b − θzak ; W ). The function g is concave and Lipschitz, so it is differentiable for a.e. θ. At such points, define 1 qθ,W = − g ′ (θ). z This is the per-unit-size offline bid price at the intermediate capacity b − θzak . It is also the acceptance cutoff at that capacity: the offline fractional optimum accepts the request when its value-to-size ratio exceeds qθ,W . Therefore, YW =
g(0) − g(1) = z 13
Z 1 qθ,W dθ. 0
This representation is the first of the ideas described in Section 1.3: it makes the price well defined under degeneracy, while Steps 3–4 below supply the stability estimate that bounds the resulting loss. Under degeneracy, the dual price jumps with capacity, already under deterministic consumption, as the marginal accepted type switches. SPM never commits to a bid price at a single such capacity; it acts on the averaged marginal YW , using only the a.e.-defined derivative along the sweep, so the analysis integrates through the degenerate capacities rather than selecting a dual price at one of j them. Along the sweep, a dual price pθ,W assigns each type j a cutoff qθ,W = aj · pθ,W . The scalar qθ,W is the component corresponding to the arriving type. The later stability argument compares two such cutoff vectors from two independent future paths. Step 3: Convexity converts cutoff variation into swept active mass. The acceptancesurplus function H is convex in the cutoff. Therefore the Jensen gap from Step 1 can be bounded by comparing two cutoff vectors generated by two independent future paths. For type k, let qk and q̄k be the two empirical cutoffs. Only ratios between these two cutoffs can contribute to the loss. The relevant active interval is Ika (q, q̄) = [qk ∧ q̄k , qk ∨ q̄k ] ∩ Sk . Let ℓk (q, q̄) be the length of this interval, and let Mk (q, q̄) be its weighted ratio mass. The one-period loss is bounded by an active-mass product of the form X ℓk (q, q̄)Mk (q, q̄). k
The length measures how far the two empirical cutoffs move. The mass measures how much type-k demand lies where the two cutoffs disagree. The probabilistic Jensen loss is therefore reduced to a deterministic stability question: how large can this active-mass product be for empirical cutoffs generated by two nearby future paths? Step 4: Stability controls the swept active mass. It remains to bound the active-mass product from Step 3. The two cutoff vectors come from two independent future paths. Their empirical type masses and empirical capacities concentrate around the same population quantities. The deterministic stability argument then shows that, when these empirical inputs are close, the projected cutoffs cannot sweep much active weighted mass: X ℓk (q, q̄)Mk (q, q̄) ≤ C τ + ε1+1/p , k
where ε is the empirical type-mass error and τ is the empirical capacity error. The exponent p enters through the active-mass condition (2.7). It determines how much weighted mass an interval must contain relative to its length, and therefore determines p the scale ε1+1/p . Finally, concentration gives per-stage errors of order δs = log(es)/s, and summing the resulting per-stage bounds over s yields the rates of Theorem 2.5: polylogarithmic when p = 1, and of order T 1/2−1/(2p) (up to logarithmic factors) when p > 1.
3
Proof of the Main Regret Bound
We now turn the roadmap of Section 2.4 into the proof of Theorem 2.5. Assumption 1 is in force throughout this section. The constant C may change from line to line, but it depends only on the 14
primitive constants, the direction matrix, and the regularity constants. It never depends on T or on the initial capacity. The analysis works directly with the expected hindsight value Φn . The only ordering principle needed is the finite-path fractional-knapsack fact that, within each type, an optimal fractional allocation accepts requests in decreasing order of the value-to-size ratio R = V /β. We first record the Bellman reduction. The expected acceptance surplus of a type-k request of size z at per-unit-size cutoff r is Hk,z (r) = E[(V − zr)+ | J = k, β = z], which is convex in r with curvature measure Λk,z ; see Section 2.2. Recall the future-path marginal YW from (2.8). For s ≥ 3, capacity b, and an independent future path W of length s − 1, define h i Ξs (b) = EJ,β EW [HJ,β (YW )] − HJ,β (EW [YW ]) 1{βaJ ≤ b} , where YW = YW (b, J, β). The quantity Ξs (b) is the one-period Jensen loss at capacity b when s periods remain. For s ≤ 2 we set Ξs ≡ 0: the future path of length s − 1 ≤ 1 is too short for the per-stage analysis, and the two corresponding one-step gaps are O(1) and absorbed into the constant of (3.1). The next proposition combines the one-step Bellman comparison with telescoping along the SPM trajectory. The argument follows the Bellman comparison in Jiang et al. (2025a, Sec. 3.1); related reductions from regret to per-stage loss appear in Vera and Banerjee (2021), Bray (2025), and Besbes et al. (2025). We give the details in Appendix A.1. Proposition 3.1 (Bellman comparison and telescoping). Under SPM, T X C E[Ξs (Bs )] + RegT (SPM; bT ) ≤ C + , s
(3.1)
s=1
where Bs is the remaining capacity when s periods remain. The remainder of this section is to bound Ξs (b) uniformly over feasible capacities b.
3.1
The per-stage loss is an active-mass product
This subsection starts from the per-stage Jensen loss Ξs (b) and reduces it to a product of two active quantities: the length of a swept ratio interval and the weighted ratio mass inside that interval. The first step is to replace the future-path marginal YW by finite-path cutoffs. Fix a future path W of length n and a feasible arriving request of type k and size z, that is, with zak ≤ b. For θ ∈ [0, 1], set bθ = b − θzak ,
ρθ =
bθ . n
Thus b0 = b and b1 = b − zak . Define g(θ) = OPTn (bθ ; W ). The function g is concave and Lipschitz, and hence differentiable for a.e. θ. For the future path W = (Ji , βi , Vi )ni=1 , write Ri = Vi /βi . We work on the probability-one event that each realized ratio Ri lies in the support SJi = [rJ−i , rJ+i ] of its type; this holds almost surely,
15
since µℓ (Sℓc ) = 0 and β ≥ β ℓ > 0 give P(R ∈ Sℓ | J = ℓ) = 1. The empirical tail functions are normalized by the future-path length n: bk,W (r) = 1 C n
n X
βi 1{Ji = k, Ri ≥ r},
i=1
bk,W (r+) = 1 C n
n X
βi 1{Ji = k, Ri > r}.
(3.2)
i=1
Let bk,W (0), m b k,W = C
k = 1, . . . , K.
d For m ∈ RK + and ρ ∈ R+ , define the finite-path fluid feasible set
Km (ρ) = {u ∈ RK + : 0 ≤ u ≤ m, Au ≤ ρ}.
(3.3)
The next lemma extracts bounded scalar cutoffs from the finite-path linear program. These cutoffs encode feasibility through the empirical tails and optimality through a projected normal inequality. The proof is given in Appendix A.2. Lemma 3.2 (Bounded cutoff selection). For almost every θ ∈ [0, 1], there exist uθ,W ∈ RK + and K qθ,W ∈ [0, y] such that
(ii)
g ′ (θ) , z bℓ,W (qθ,W,ℓ +) ≤ uθ,W,ℓ ≤ C bℓ,W (qθ,W,ℓ ), C
(iii)
uθ,W ∈ Km b W (ρθ ),
(i)
(iv)
qθ,W,k = −
K X
(3.4) ℓ = 1, . . . , K,
(3.5) (3.6)
Πℓ (qθ,W,ℓ )(u′ℓ − uθ,W,ℓ ) ≤ 0,
u′ ∈ Km b W (ρθ ).
(3.7)
ℓ=1
The next lemma is what makes the scalar cutoffs sufficient. It shows that the Jensen gap for the future-path marginal is no larger than the Jensen gap for the selected cutoff coordinate along the sweep. After this reduction, the proof only has to control empirical cutoffs. Lemma 3.3 (Marginal-to-cutoff reduction). Fix a feasible current request of type k and size z, a capacity b, and a future horizon n. Let W be an independent future path of length n, and let qθ,W,k be the cutoff coordinate selected in Lemma 3.2 for the sweep from b to b − zak . Then h i (3.8) EW [Hk,z (YW )] − Hk,z (EW [YW ]) ≤ EW,θ̃ Hk,z (qθ̃,W,k ) − Hk,z EW,θ̃ [qθ̃,W,k ] , where YW = YW (b, k, z) and θ̃ ∼ Unif[0, 1] is independent of W . Proof. Fix a future path W . Define g(θ) = OPTn (b − θzak ; W ),
0 ≤ θ ≤ 1.
The function g is concave and Lipschitz, and hence it is absolutely continuous and differentiable for a.e. θ. At differentiability points, set qθ,W,k = −
g ′ (θ) . z
By Lemma 3.2, this representative agrees a.e. with the selected cutoff coordinate. Absolute continuity gives Z Z 1 g(0) − g(1) 1 1 ′ YW (b, k, z) = =− g (θ) dθ = qθ,W,k dθ. z z 0 0 16
Equivalently, h i YW (b, k, z) = Eθ̃ qθ̃,W,k | W . Taking expectation over W yields EW [YW ] = EW,θ̃ [qθ̃,W,k ]. Since Hk,z is convex, Jensen’s inequality gives i h Hk,z (YW ) ≤ Eθ̃ Hk,z (qθ̃,W,k ) | W . Taking expectation over W and using the preceding identity for EW [YW ] proves (3.8). For scalar cutoffs q, q̄ ∈ [0, y], define the active swept interval Ika (q, q̄) = [q ∧ q̄, q ∨ q̄] ∩ Sk , together with its length and weighted mass Mk (q, q̄) = µk (Ika (q, q̄)).
ℓk (q, q̄) = Leb(Ika (q, q̄)),
This is the two-cutoff form of the single-interval length ℓk (I) = Leb(I ∩Sk ) of Assumption 1, applied to the interval Ika (q, q̄). Jensen under a pairwise active cap. The right-hand side of (3.8) is a Jensen gap for the convex function Hk,z . We use the following general bound. Let h be a convex function on [0, y], and let µh be the measure generated by the right derivative of h. Thus, for B = [B− , B+ ] ⊂ [0, y], µh (B) = h′+ (B+ ) − h′+ (B− ). In the applications below, µh is finite, atomless, and supported on the active ratio support Sk : µh ([0, y] \ Sk ) = 0. We first record a general convex-analysis bound: the Jensen gap of a convex function is controlled by the length and the curvature mass of the projected hull of the cutoff set. Lemma 3.4 (Projected-hull Jensen gap). Let J = [a, b] be a compact interval with |J| > 0, and let ν be a finite, atomless Borel measure supported on J. Let h be convex with curvature measure ν, so that Z h(x) = α + βx + (x − t)+ ν( dt) J
for some α, β ∈ R. Let Q be nonempty with Q ∪ J contained in an interval of length D, let Q be a random variable taking values in Q, and let ΠJ be the projection onto J. With u = inf{ΠJ (q) : q ∈ Q},
v = sup{ΠJ (q) : q ∈ Q},
so that [u, v] ⊆ J, D Eh(Q) − h(EQ) ≤ 1 + (v − u) ν([u, v]). |J|
17
Proof. By the curvature representation, Z GQ (t) ν( dt), Eh(Q) − h(EQ) =
GQ (t) = E(Q − t)+ − (EQ − t)+ ,
J
and GQ ≥ 0 by convexity of x 7→ (x − t)+ . If t ∈ J and t < u, then ΠJ (Q) ≥ u > t almost surely; since t ∈ J, this forces Q > t almost surely, so GQ (t) = 0. Likewise t > v gives Q < t almost surely and GQ (t) = 0. Hence Z Eh(Q) − h(EQ) =
GQ (t) ν( dt). [u,v]
Fix t ∈ [u, v]. If {ΠJ (q) : q ∈ Q} does not contain both endpoints of J, then at most one clamp side of J is used. If the upper side is unused, then (q − t)+ ≤ v − t ≤ v − u for every q ∈ Q, so GQ (t) ≤ E(Q − t)+ ≤ v − u; if instead the lower side is unused, then Q ≥ u almost surely and GQ (t) ≤ E(Q − t)+ − (EQ − t) = E(t − Q)+ ≤ v − u. If both endpoints of J are attained, then [u, v] = J, and since Q ∪ J lies in an interval of length D we have (Q − t)+ ≤ D, so GQ (t) ≤ E(Q − t)+ ≤ D = (D/|J|)(v − u). In every case GQ (t) ≤ (1 + D/|J|)(v − u), and therefore D Eh(Q) − h(EQ) ≤ 1 + (v − u) ν([u, v]). |J|
Specializing Lemma 3.4 to the active ratio support converts a pairwise active cap on the swept curvature into a bound on the Jensen gap. Lemma 3.5 (Jensen bound under a pairwise active cap). Fix a type k. Let h be convex on [0, y], and suppose that the measure µh defined above is finite, atomless, and supported on Sk . Let Q ⊂ [0, y] be nonempty, and let Q be a random variable taking values in Q. Then y Eh(Q) − h(EQ) ≤ 1 + sup ℓk (q, q̄) µh Ika (q, q̄) . |Sk | q,q̄∈Q Proof. The curvature measure µh is finite, atomless, and supported on Sk , so Lemma 3.4 applies with J = Sk , ν = µh , and ambient length D = y (since Q∪Sk ⊆ [0, y]). With u = inf{Πk (q) : q ∈ Q} and v = sup{Πk (q) : q ∈ Q}, it gives y Eh(Q) − h(EQ) ≤ 1 + (v − u) µh ([u, v]). |Sk | By the active-hull closure lemma, Lemma A.1, applied with B = Sk and ν = µh , (v − u) µh ([u, v]) ≤ sup ℓk (q, q̄) µh Ika (q, q̄) . q,q̄∈Q
Combining this with the previous display proves the lemma.
18
Remainder of the proof. Lemma 3.5 reduces the per-stage loss to a pairwise active cap. For good pathwise cutoffs q, q̄, we need to show that ℓk (q, q̄) Λk,z (Ika (q, q̄)) ≤ Cr. On a dominated neighborhood, Assumption 1 gives Λk,z (I) ≤ Cµk (I) for every active interval I contained in that neighborhood and for almost every size z. Thus, in the dominated case, it is enough to bound ℓk (q, q̄) µk (Ika (q, q̄)) uniformly over good cutoff pairs. The next subsection proves this deterministic active-mass bound. At a contact endpoint, domination by µk may fail; there we use the endpoint Hardy estimate instead.
3.2
Projected active-mass product stability
We now prove the deterministic stability estimate that controls the active-mass product swept by two empirical cutoff vectors. The estimate is deterministic: concentration will later supply the required closeness of the empirical inputs. Recall the finite-path fluid feasible set Km (ρ) from (3.3); it is the feasible region of the type-level finite-path fluid problem with type masses m and normalized capacity ρ. The cutoffs enter only through their projected values on the active supports. Recall from Section 3.1 the active interval Ika (q, q̄), its length ℓk (q, q̄), and its weighted mass Mk (q, q̄); the product ℓk (q, q̄)Mk (q, q̄) is the active-mass product for type k. We also use the normal cone notation NK (x) = {z : z ⊤ (v − x) ≤ 0 for all v ∈ K},
x ∈ K.
For each type k, define the population tail masses Ck (r) = πk E[β1{R ≥ r} | J = k],
Ck (r+) = πk E[β1{R > r} | J = k],
and m0k = Ck (0) = πk E[β | J = k], with m0 = (m01 , . . . , m0K ). Proposition 3.6 shows that if two feasible type-level solutions have nearby empirical tail data, nearby capacities, and compatible projected normal directions, then their active-mass product is small. Proposition 3.6 (Active-mass product stability). Assume the active mass bound (2.7), and assume that each active support set Sk is a single interval. Fix compact ranges for m and ρ on which Lemma A.4 applies. For every Cm < ∞, there are constants ε0 , C < ∞ such that the following holds. Let u e ∈ Km e m̄, ρ, ρ̄ lie in the fixed compact ranges. Let qe, q̄ ∈ e (ρ) and ū ∈ Km̄ (ρ̄), where m, K [0, y] . Suppose that 0 < ε ≤ ε0 , Ck (e qk +) − ε ≤ u ek ≤ Ck (e qk ) + ε,
Ck (q̄k +) − ε ≤ ūk ≤ Ck (q̄k ) + ε,
that Π(e q ) ∈ NKme (ρ) (e u),
Π(q̄) ∈ NKm̄ (ρ̄) (ū),
and that ∥m e − m̄∥∞ ≤ Cm ε, 19
∥ρ − ρ̄∥∞ ≤ τ.
k = 1, . . . , K,
Then
K X
ℓk (e qk , q̄k )Mk (e qk , q̄k ) ≤ C τ + ε1+1/p ,
k=1
where Mk (a, b) := µk (Ika (a, b)). Proof. For each k, write Ik := Ika (e qk , q̄k ) = [e qk ∧ q̄k , qek ∨ q̄k ] ∩ Sk ,
ℓk := Leb(Ik ),
Mk := µk (Ik ).
Set p := Π(e q ) and p̄ := Π(q̄), so that pk = Πk (e qk ) and p̄k = Πk (q̄k ). Since Sk is a single interval and Πk is projection onto Sk , ℓk = |Πk (e qk ) − Πk (q̄k )| = |pk − p̄k |.
(3.9)
We first record the tail identities used below. The upper bound in (2.7) implies that µk is atomless: for every point a, µk ({a}) ≤ C Leb({a} ∩ Sk ) = 0. By definition of the closed and strict tails, Ck (a) = µk ([a, ∞)),
Ck (a+) = µk ((a, ∞)).
Therefore, if a > b, then Ck (a) − Ck (b+) = −µk ([b, a] ∩ Sk ),
(3.10)
Ck (a+) − Ck (b) = µk ([a, b] ∩ Sk ).
(3.11)
and if a < b, then We now prove the coordinatewise active-mass product estimate. Fix k. If pk = p̄k , then ℓk = 0 by (3.9), and hence (pk − p̄k )(e uk − ūk ) = 0 = −ℓk Mk + 2εℓk . Suppose next that pk > p̄k . Since Πk is monotone, this implies qek > q̄k . Using the graph relations assumed in the proposition, u ek − ūk ≤ Ck (e qk ) + ε − Ck (q̄k +) − ε = Ck (e qk ) − Ck (q̄k +) + 2ε. Applying (3.10) with a = qek and b = q̄k gives Ck (e qk ) − Ck (q̄k +) = −Mk . Thus u ek − ūk ≤ −Mk + 2ε. Multiplying by pk − p̄k = ℓk > 0, we obtain (pk − p̄k )(e uk − ūk ) ≤ −ℓk Mk + 2εℓk . Finally suppose that pk < p̄k . Monotonicity of Πk gives qek < q̄k . Again using the graph relations, u ek − ūk ≥ Ck (e qk +) − ε − Ck (q̄k ) + ε = Ck (e qk +) − Ck (q̄k ) − 2ε. Applying (3.11) with a = qek and b = q̄k gives Ck (e qk +) − Ck (q̄k ) = Mk . Hence u ek − ūk ≥ Mk − 2ε. Since pk − p̄k < 0, (pk − p̄k )(e uk − ūk ) ≤ (pk − p̄k )(Mk − 2ε) = −|pk − p̄k |Mk + 2ε|pk − p̄k | = −ℓk Mk + 2εℓk .
20
Combining the three cases, for every k, (pk − p̄k )(e uk − ūk ) ≤ −ℓk Mk + 2εℓk . Summing over k gives (p − p̄)⊤ (e u − ū) ≤ −
K X
ℓk Mk + 2ε
k=1
K X
ℓk .
(3.12)
k=1
On the other hand, Lemma A.4 applies by hypothesis. Hence, for some constant Cpc < ∞, (p − p̄)⊤ (e u − ū) ≥ −Cpc τ − Cpc ε
K X
ℓk .
(3.13)
k=1
Combining (3.12) and (3.13), and increasing the constant if necessary, gives K X
ℓk Mk ≤ C1 τ + C1 ε
k=1
K X
ℓk .
(3.14)
k=1
It remains to absorb the linear active-length term. By the lower bound in (2.7), applied to the interval Ik , (3.15) ℓk Mk ≥ c ℓp+1 Mk = µk (Ik ) ≥ c ℓpk , k . Young’s inequality with conjugate exponents p + 1 and (p + 1)/p gives, for every ℓ ≥ 0, c C1 ε ℓ ≤ ℓp+1 + C2 ε1+1/p , 2 where C2 depends only on C1 , c, p. Applying this with ℓ = ℓk and using (3.15), C1 ε ℓk ≤
1 ℓk Mk + C2 ε1+1/p . 2
Summing over the fixed number of types gives C1 ε
K X k=1
K
1X ℓk ≤ ℓk Mk + C3 ε1+1/p . 2
(3.16)
k=1
Substituting (3.16) into (3.14) yields K X k=1
K
1X ℓk Mk ≤ C1 τ + ℓk Mk + C3 ε1+1/p . 2 k=1
Moving the half-product term to the left and increasing the constant gives K X
ℓk Mk ≤ C τ + ε1+1/p .
k=1
The three-case coordinatewise bound, the projected-comparison estimate, and the Young absorption all hold for any ε > 0; the smallness ε ≤ ε0 in the statement is not used, and the estimate holds for every ε > 0. This proves the proposition. This P is the only active-mass product stability estimate used below. It controls the active-mass product k ℓk Mk swept by the projected cutoffs. The projection discards inactive flat parts of the sweep, which carry neither weighted-resource mass nor conditional curvature. 21
3.3
Concentration, summation, and the bound at p = 1
It remains to combine the pathwise active-mass product cap of Proposition 3.6 with the Jensen bound in Lemma 3.5, and then to sum the resulting per-stage losses. The concentration step below compares the empirical analogues of these tails across two finite future paths to their population values. Normalization reminder. Recall from (3.2) that, for a future path W = (Ji , βi , Vi )ni=1 , the empirical tail systems are normalized by the future-path length n: bk,W (r) = 1 C n
n X
bk,W (r+) = 1 C n
βi 1{Ji = k, Ri ≥ r},
i=1
n X
βi 1{Ji = k, Ri > r},
i=1
where Ri = Vi /βi . Thus bk,W (0) m b k,W := C is the normalized empirical type total. Likewise, along the capacity path bθ = b − θzak , the normalized right-hand side used in the deterministic systems is ρθ :=
bθ . n
The finite-path primal allocation selected in Lemma 3.2 is divided by n, so it lies in Km b W (ρθ ), or eff ) introduced below. (ρ equivalently in the clipped system Km bW θ Concentration. The empirical closed and strict tails are generated by the weighted-threshold classes (J, β, V ) 7→ β1{J = k, V /β ≥ r}, (J, β, V ) 7→ β1{J = k, V /β > r}. These are bounded VC-subgraph classes with envelope β. Hence, after increasing constants if necessary, there is an event En (W ) such that P(En ) ≥ 1 − n−6 and, on En (W ), r n o log(en) bk,W (r) − Ck (r)|, |C bk,W (r+) − Ck (r+)| ≤ δn , max sup max |C δn := C . (3.17) k r∈[0,y] n Taking r = 0 in (3.17) gives ∥m b W − m0 ∥∞ ≤ δn .
(3.18)
On En (W ), every empirical closed/right cutoff relation is a population closed/right relation with perturbation δn . Indeed, if bk,W (qk +) ≤ uk ≤ C bk,W (qk ), C then (3.17) implies Ck (qk +) − δn ≤ uk ≤ Ck (qk ) + δn .
(3.19)
The upper bound in (2.7) implies that µk is atomless, since µk ({r}) ≤ C Leb({r} ∩ Sk ) = 0. Thus Ck (qk +) = Ck (qk ), although the two-sided form (3.19) is the form used below.
22
Global domination when p = 1. When p = 1, Assumption 1 requires the finite active cover of each Sk to consist only of dominated neighborhoods. Thus, for each cover element U , for a.e. feasible size z, Λk,z (I) ≤ CU µk (I) for every interval I ⊂ U. Since the cover is finite, we may intersect the corresponding full-measure sets of z’s and work on one full-measure set where all local domination bounds hold simultaneously. Choose a finite partition rk− = ak,0 < ak,1 < · · · < ak,Nk = rk+ such that every cell [ak,h−1 , ak,h ] is contained in one dominated neighborhood. This is possible by compactness of Sk and the finite active cover. If I ⊆ Sk is an interval, then, up to endpoints, I=
Nk [
I ∩ [ak,h−1 , ak,h ] .
h=1
Endpoints do not matter for µk , since µk is atomless. They also do not matter for Λk,z on the full-measure size set, because local domination gives Λk,z ({a}) ≤ CU µk ({a}) = 0 whenever a lies in a dominated neighborhood U . Therefore, summing the local domination bounds over the finitely many cells gives Λk,z (I) ≤ C µk (I)
for every interval I ⊆ Sk , for a.e. z.
(3.20)
Moreover, since πk Eβ [Λk,β (B) | J = k] = µk (B) for every Borel set B, and since µk ([0, y] \ Sk ) = 0, we also have Λk,z ([0, y] \ Sk ) = 0
for a.e. z.
Thus, on the same full-measure size set, Λk,z is finite, atomless, and supported on Sk . These are precisely the support and atomlessness conditions needed to apply Lemma 3.5 with curvature measure Λk,z . Per-stage bound.
Fix s ≥ 3, set n = s − 1, and define 1 1+1/p rn := C δn + . n
In the case p = 1, the concentration scale (3.17) satisfies δn2 ≤ C log(en) n , so 1 log(en) rn = C δn2 + ≤C . n n
(3.21)
The deterministic active-mass product estimate, Proposition 3.6, requires δn ≤ ε0 . This holds for all sufficiently large n. For the finitely many smaller values of n, we enlarge the final constant in the regret bound. Hence, in the rest of this paragraph, assume δn ≤ ε0 . Fix a feasible current pair (k, z), so zak ≤ b, and define bθ := b − θzak ,
ρθ := 23
bθ , n
θ ∈ [0, 1].
Clipping the resource vector. We first place the empirical type masses and resource vectors in the compact ranges required by Proposition 3.6. Choose mmax ∈ RK b W ≤ mmax for + such that m every normalized empirical vector m b W , and set ρmax := Ammax ,
max ρeff . θ := ρθ ∧ ρ
Here the minimum is taken coordinatewise. Because 0 ≤ u ≤ m b W ≤ mmax implies Au ≤ Ammax = max ρ , clipping nonbinding resource coordinates does not change the feasible set: eff Km b W (ρθ ) = Km b W (ρθ ).
(3.22)
eff Consequently, the normalized empirical primal allocation selected in Lemma 3.2 lies in Km b W (ρθ ), and the same projected normality condition holds for this clipped feasible set. Since m b W ≤ mmax eff max and 0 ≤ ρθ ≤ ρ , both arguments lie in the fixed compact ranges on which Proposition 3.6 applies. The clipping map is coordinatewise 1-Lipschitz. Thus, for any θ, θ′ ∈ [0, 1], eff ∥ρeff θ − ρθ′ ∥∞ ≤ ∥ρθ − ρθ′ ∥∞ ≤
C z∥ak ∥∞ ≤ . n n
(3.23)
Let W, W ′ ∈ En , and let θ, θ′ be differentiability points for the corresponding pathwise value functions. By (3.19), both empirical cutoff systems satisfy the population closed/right graph relations with perturbation δn . By (3.18), the vectors m b W and m b W ′ are within δn of m0 , and hence within 2δn of each other. By (3.23), their clipped right-hand sides differ by at most C/n. Lemma 3.2 supplies projected normality. Therefore Proposition 3.6, applied with Cm = 2, ε = δn , and τ = C/n, gives K X ℓj (qj,θ,W , qj,θ′ ,W ′ ) µj Ija (qj,θ,W , qj,θ′ ,W ′ ) ≤ rn . j=1
Each summand is nonnegative, so in particular, for the current type k, ℓk (qk,θ,W , qk,θ′ ,W ′ ) µk Ika (qk,θ,W , qk,θ′ ,W ′ ) ≤ rn .
(3.24)
Let QΩ := qk,Θ,W ,
Ω = (Θ, W ),
Θ ∼ Unif[0, 1],
with Θ independent of W . By Lemma 3.3, EW [Hk,z (YW )] − Hk,z (EW [YW ]) ≤ EΩ Hk,z (QΩ ) − Hk,z (EΩ QΩ ) .
(3.25)
Now condition on the good event G := En (W ). Since QΩ ∈ [0, y], and since Hk,z is uniformly bounded and uniformly Lipschitz on [0, y], for n large enough that P(G) ≥ 1/2, EHk,z (QΩ ) − Hk,z (EQΩ ) − E[Hk,z (QΩ ) | G] − Hk,z (E[QΩ | G]) ≤ CP(Gc ) ≤ Cn−6 . (3.26) Indeed, boundedness gives |EHk,z (QΩ ) − E[Hk,z (QΩ ) | G]| ≤ CP(Gc ), after increasing C, and QΩ ∈ [0, y] gives |EQΩ − E[QΩ | G]| ≤ CP(Gc ). 24
The Lipschitz property of Hk,z then controls the difference between the two Hk,z -of-mean terms. Let DW ⊆ [0, 1] be the full-measure set of differentiability points for the path W , and define QG := {qk,θ,W : W ∈ En , θ ∈ DW } . Changing QΩ on a null set if necessary, the conditional random variable QΩ | G takes values in QG . Moreover, for any two values q, q̄ ∈ QG , generated by good futures and differentiability points, (3.24) gives ℓk (q, q̄) µk (Ika (q, q̄)) ≤ rn . (3.27) Using the global domination bound (3.20), we get, for a.e. feasible size z, ℓk (q, q̄) Λk,z (Ika (q, q̄)) ≤ Crn
for all q, q̄ ∈ QG .
(3.28)
The cap (3.28) is the pairwise active-cap hypothesis of Lemma 3.5, with r = Crn . It follows from (3.27) and the global domination bound (3.20). Applying that lemma conditionally on G with h = Hk,z ,
µh = Λk,z ,
Q = QG ,
gives E[Hk,z (QΩ ) | G] − Hk,z (E[QΩ | G]) ≤ Crn .
(3.29)
Combining (3.25), (3.26), and (3.29), we obtain EW [Hk,z (YW )] − Hk,z (EW [YW ]) ≤ Crn + Cn−6 . This bound holds for every feasible current pair (k, z) with z in the full-measure size set described above. Since the exceptional set has zero arrival probability, averaging over the current type and size in the definition of Ξs (b) gives Ξs (b) ≤ Crn + Cn−6 . When p = 1, using (3.21) yields Ξs (b) ≤ C
log(e(s − 1)) . s−1
Summation. The preceding per-stage bound is uniform over feasible capacities b. Since n = s−1, Proposition 3.1 gives RegT (SPM; bT ) ≤ C + C
T X log(e(s − 1)) s=3
s−1
The harmonic term is bounded by C log(eT ), and T X log(e(s − 1)) s=3
s−1
≤ C(log(eT ))2 .
Therefore, RegT (SPM; bT ) ≤ C(log(eT ))2 . This proves the p = 1 part of Theorem 2.5.
25
+
1 s
.
3.4
Endpoint-contact verification when p > 1
For p > 1, the proof follows the same reductions as in the case p = 1, but the last curvature step changes. On dominated neighborhoods, the conditional curvature is controlled pointwise by the weighted ratio measure. Near an endpoint-contact neighborhood, this domination can fail because the conditional ratio support has a moving endpoint. The replacement is a Hardy-type estimate that integrates the conditional curvature over the endpoint branch. The next lemma is the per-stage estimate needed to complete the proof. It uses the same active-mass product cap from Proposition 3.6, followed by the endpoint Hardy estimate. The proof is deferred to Appendix A.4. Lemma 3.7 (Per-stage loss under endpoint contact). Assume Assumption 1 with p > 1. There exist s0 < ∞ and C < ∞ such that, for all s ≥ s0 and every capacity b, with n = s − 1, h i Ξs (b) = EJ,β EW [HJ,β (YW )] − HJ,β (EW [YW ]) 1{βaJ ≤ b} ≤ C rs log(e/rs ), where rs =
log(es) s
(p+1)/(2p)
1 + . s
Completion of the proof of Theorem 2.5. The case p = 1 was proved in Section 3.3. It remains to consider p > 1. By Proposition 3.1 and Lemma 3.7, the finitely many stages s < s0 can be absorbed into the constant, and T X 1 rs log(e/rs ) + RegT (SPM; bT ) ≤ C + C , s s=s 0
where rs =
log(es) s
(p+1)/(2p)
1 + . s
Since p > 1, the first term in rs dominates 1/s up to constants for large s. Hence rs log(e/rs ) ≤ Cs−(p+1)/(2p) (log(es))(p+1)/(2p)+1 + C
log(es) . s
Therefore, T X s=s0
rs log(e/rs ) ≤ C
T X
s−(p+1)/(2p) (log(es))(p+1)/(2p)+1 + C(log(eT ))2
s=s0
≤ CT 1/2−1/(2p) (log(eT ))(p+1)/(2p)+1 + C(log(eT ))2 . The polynomial term dominates the polylogarithmic term when p > 1, after increasing C if necessary. Combining this estimate with the telescoping bound gives RegT (SPM; bT ) ≤ CT 1/2−1/(2p) (log(eT ))(p+1)/(2p)+1 + C. This proves the p > 1 part of Theorem 2.5, and completes the proof.
26
4
Lower bound
The polynomial exponent in the SPM upper bound is sharp in the worst case over the endpointcontact families constructed below. We show that, for every prescribed active weighted-mass exponent p > 1, no online policy can achieve regret smaller than order T 1/2−1/(2p) . The construction uses one resource and one arrival type. Its weighted ratio measure has endpoint exponent exactly p at both endpoints of its support, so the smallest exponent satisfying the active-mass condition (2.7) is p itself. The construction isolates the mechanism behind the lower bound. The operative ratio cutoff lies at the lower edge of the ratio support. That edge is a corner: it is reached only when consumption and value simultaneously approach their extreme values. As a result, the resource mass just above the cutoff is governed by the product of the value density and the size density near the boundary. We choose the size density symmetrically at its two endpoints, so the same contact exponent appears at both ratio endpoints. Thus the active weighted-mass exponent used in the upper bound is exactly the exponent used in the lower-bound construction.
4.1
A one-resource endpoint-contact family
Fix p > 1. The lower-bound instance has one resource, one arrival type, and unit consumption direction. The size is β = 2 − Y , where Y ∼ Beta(p − 1, p − 1) has density fY (y) =
1 y p−2 (1 − y)p−2 , B(p − 1, p − 1)
0 ≤ y ≤ 1.
The reward is V = 1 + S, where S ∼ Unif[0, 1], and S and Y are independent. Thus β ∈ [1, 2] and V ∈ [1, 2], and the mean size is µ := E[β] = 32 . We set the capacity at the fluid scale 3 bT = T µ = T. 2 The value-to-size ratio is R=
V 1+S = ∈ [1/2, 2]. β 2−Y
Let r0 = 1/2 denote the lower endpoint of the ratio support. This endpoint is reached only in the joint limit S ↓ 0 and Y ↓ 0. The upper endpoint 2 is reached only in the joint limit S ↑ 1 and Y ↑ 1. This family is the independent value-and-size class of Proposition B.2 (the case behind Corol± lary 2.9), with uniform value (a± V = 1) and β = 2 − Y , Y ∼ Beta(p − 1, p − 1) (aβ = p − 1). By that + + − proposition both ratio-endpoint exponents equal a− V + aβ = aV + aβ = p, so the weighted ratio measure satisfies the active-mass condition (2.7) with exponent p; and since the endpoint mass is of order xp , no smaller exponent is admissible. Hence p is exactly the smallest admissible active-mass exponent of this family. The lower-bound proof uses only the following two endpoint estimates. Lemma 4.1 (Endpoint mass). For all sufficiently small x > 0, E[β 1{R ≤ r0 + x}] ≍ xp ,
E[β(R − r0 ) 1{R ≤ r0 + x}] ≍ xp+1 .
The constants depend only on p.
27
Proof. This family is the independent value-and-size class of Proposition B.2, with uniform value ± (a± V = 1) and β = 2 − Y , Y ∼ Beta(p − 1, p − 1) (aβ = p − 1). Its lower ratio endpoint exponent + is therefore a− V + aβ = p, and the verification there, through Lemma A.6, gives the weighted ratio measure E[β 1{R ∈ ·}] the endpoint density m(r0 + t) ≍ tp−1 Hence
as t ↓ 0.
Z x E[β 1{R ≤ r0 + x}] =
m(r0 + t) dt ≍ xp ,
0
and, integrating the same density against the ratio premium r − r0 = t, Z x E[β(R − r0 ) 1{R ≤ r0 + x}] = t m(r0 + t) dt ≍ xp+1 . 0
4.2
The matching lower bound
The lower bound is a two-point dilemma at the lower ratio endpoint. An endpoint layer of width p εT carries √ Θ(εT T ) weighted resource (Lemma 4.1), which √an online policy cannot distinguish from the Θ( T ) fluctuation of total demand exactly when εpT T ≍ 1, i.e. εT ≍ T −1/(2p) . Since the √ perunit regret for misjudging the layer is the ratio premium εT , the unavoidable regret is εT · T ≍ T 1/2−1/(2p) , larger for a thinner endpoint (larger p). Theorem 4.2 (Endpoint-contact lower bound). For the family above, there is a constant cp > 0 such that, for all sufficiently large even T , inf RegT (π; bT ) ≥ cp T 1/2−1/(2p) . π
Proof. Write T = 2n and split the horizon into two halves of length n. Fix a small constant η > 0, to be chosen below, and set εT = ηT −1/(2p) . Define the two low-ratio layers Lε = {R ≤ r0 + εT },
L2ε = {R ≤ r0 + 2εT },
and, for the first half, W =
n X t=1
βt 1{(βt , Vt ) ∈ Lε },
U1 =
n X t=1
βt 1{(βt , Vt ) ∈ L2ε },
S1 =
n X
βt .
t=1
Thus W and U1 are the first-half resource in the thinner and thicker endpoint layers, and S1 is the total first-half resource. √ Step 1: Construct a favorable first-half event. By Lemma 4.1, EW = n Θ(εpT ) = Θ(η p T ), and the summands of W√are bounded, so Var(W ) ≤ CEW . Chebyshev’s inequality then gives P{W < √ p cW η T } ≤ C/(η p T ) for a sufficiently small constant cW > 0, and choosing cW small enough also gives h √ i √ E W 1{W ≥ cW η p T } ≥ c η p T . (4.1) 28
√ Since Var(S1 ) = Θ(T ), Chebyshev’s inequality gives P{|S1 − nµ| ≤ K T } ≥ 34 for a fixed large √ constant K. Lemma 4.1 also gives EU1 ≤ Cη p T , so after fixing √ K and then choosing η small enough that Cη p ≤ K/16, Markov’s inequality gives P{U1 ≤ K T } ≥ 15 16 . Let F = A0 ∩ B0 ∩ C0 be the intersection of the first-half events √ √ √ B0 = {|S1 − nµ| ≤ K T }, C0 = {U1 ≤ K T }. A0 = {W ≥ cW η p T }, We now show that intersecting with B0 and C0 does not destroy too much W -mass. By Cauchy– Schwarz, E[W 1B0c ] ≤ (EW 2 )1/2 P(B0c )1/2 . Since EW 2 = (EW )2 + Var(W ) ≤ (EW )2 + CEW and P(B0c ) ≤ C/K 2 , choosing K large enough gives √ E[W 1B0c ] ≤ 41 c η p T (4.2) for√all large T , where c is the constant in (4.1). Second, since W ≤ U1 and P(C0c ) = P{U1 > K T } ≤ Cη p /K, the bound EU12 ≤ (EU1 )2 + CEU1 and Cauchy–Schwarz give √ p 1/2 √ E[W 1C0c ] ≤ E[U1 1C0c ] ≤ (EU12 )1/2 P(C0c )1/2 ≤ Cη p T ηK + o(η p T ). After fixing K, choosing η small enough and then T large gives √ E[W 1C0c ] ≤ 14 c η p T . Combining (4.1), (4.2), and (4.3),
√ E[W 1F ] ≥ cF η p T
for a primitive constant cF > 0; and on F one has W ≥ cW η √ U1 ≤ K T .
(4.3)
(4.4) √ p
√
T , |S1 − nµ| ≤ K T , and
Step 2: The second half forces a dilemma. Fix an arbitrary first-half history in F (and, for a randomized policy, its internal randomization through the first half). Let Yrej ∈ [0, W ] be the amount of first-half P Lε -resource rejected by online policy, and set L = W − Yrej for the accepted Pthe 2n amount. Let S2 = 2n β and U = t 2 t=n+1 t=n+1 βt 1{(βt , Vt ) ∈ L2ε } be the second-half analogues of S1 and U1 ; the second half is independent of the first-half history and policy decisions. Since β is bounded and nondegenerate, the central limit theorem gives a constant p− > 0 such √ − ) ≥ p for all large T . Similarly P{S − nµ ≥ that√E − = {S2 − nµ ≤ −2K T } satisfies P(E√ − 2 p p /K ≤ q /2 4K T } ≥ q+ for√some q+ > 0; since EU2 ≤ Cη T , choosing η small enough that Cη + √ √ gives P{U2 > K T } ≤ q+ /2 by Markov, so E + = {S2 − nµ ≥ 4K T , U2 ≤ K T } satisfies P(E + ) ≥ p+ := q+ /2 > 0 for all large T . √ Resource-poor second √ half. On F ∩ E − the bounds on S1 and S2 give S1 + S2 ≤ nµ + K T + √ nµ − 2K T = bT − K T < bT , so accepting every arrival is feasible; as all values are nonnegative, the hindsight optimum accepts every arrival. Every unit of first-half Lε -resource the online policy rejects is then lost relative to hindsight, and on Lε each such unit has ratio R ≥ r0 . Hence regret ≥ r0 Yrej
on F ∩ E − .
(4.5)
√ √ √ Resource-rich √ second half. On F ∩E + we have S1 +S2 ≥ nµ−K T +nµ+4K T = bT +3K √ T . Also U1 +U2 ≤ 2K T , so the total resource outside L2ε is at least S1 +S2 −(U1 +U2 ) ≥ bT +K T > bT ; thus there is a feasible hindsight solution of total resource bT using only arrivals outside L2ε , every unit of which has ratio at least r0 + 2εT . 29
Let X be the online accepted fractional resource measure, with total mass M = |X| ≤ bT . Its first-half Lε part has mass L = W − Yrej and ratio at most r0 + εT ; let Xhi be the remaining online resource, so |Xhi | = M − L. After removing Xhi , at least bT − (M − L) units of resource outside L2ε remain, so the solution consisting of Xhi together with bT − M + L such units is feasible (its total mass is bT ). Comparing it to the online solution, the common Xhi cancels: the comparison gains bT − M + L units of ratio at least r0 + 2εT , while the online solution has L units of ratio at most r0 + εT and possibly unused capacity bT − M . Hence, using L = W − Yrej , regret ≥ (r0 + 2εT )(bT − M + L) − (r0 + εT )L = (r0 + 2εT )(bT − M ) + εT L ≥ εT (W − Yrej )
on F ∩ E + .
(4.6)
Step 3: Optimize over the policy’s first-half choice. Conditioning on the first-half history in F and using P(E − ) ≥ p− , P(E + ) ≥ p+ , (4.5), and (4.6), E[regret | first half] ≥ p− r0 Yrej + p+ εT (W − Yrej ) = p+ εT W + (p− r0 − p+ εT )Yrej . Since εT → 0, for all large T we have p+ εT ≤ p− r0 , so the right side is nondecreasing in Yrej and minimized at Yrej = 0; hence E[regret | first half] ≥ p+ εT W on F . Taking expectations and using (4.4), √ E[regret] ≥ p+ εT E[W 1F ] ≥ c ηT −1/(2p) · η p T = c η p+1 T 1/2−1/(2p) . Absorbing the fixed η p+1 into the constant gives E[regret] ≥ cp T 1/2−1/(2p) . The online policy was arbitrary, including randomized policies, so the same bound holds after taking the infimum over all online policies. When the reward and size are independent and both uniform on [1, 2] — the construction above at p = 2, where Y ∼ Unif[0, 1] — with capacity bT = 32 T , the active weighted-mass exponent is p = 2, and Theorem 4.2 gives inf RegT (π; bT ) ≥ c T 1/4 . π
This theorem isolates how joint reward-size randomness can create a thin ratio-support endpoint and force polynomial regret. When consumption is deterministic (β ≡ 1), the ratio is a onedimensional function of the value alone, its support has no corner, the relevant endpoint is regular (p = 1), and polylogarithmic regret is achievable; the same holds when the value is deterministic and the size has a regular distribution. It is the joint randomness of consumption and value that turns the ratio-support edge into a corner, raises the active weighted-mass exponent to p = 2, and makes T 1/4 the exact polynomial exponent for this instance. Together with the SPM upper bound of Section 3—which matches T 1/2−1/(2p) up to a logarithmic factor for every p ≥ 1 and gives polylogarithmic regret at p = 1—the two results pin down the polynomial exponent as a function of the single active weighted-mass exponent p.
5
Concluding remarks
This paper studies online allocation with random rewards and random consumption sizes. Under the paper’s weighted-ratio regularity conditions, the main conclusion is that regret is controlled by the size-weighted value-to-size ratio measure near active acceptance cutoffs. When this size-weighted resource mass grows linearly, the sample-path marginal policy attains O((log T )2 ) regret. When the mass vanishes faster than linearly, the problem becomes polynomially harder: for exponent 30
p > 1, the policy attains the rate T 1/2−1/(2p) up to logarithmic factors, and the lower bound shows that the polynomial exponent is unavoidable. The mechanism is distributional. Jointly random rewards and consumptions can make the critical value-to-size ratio occur only on a thin part of the joint support, such as a corner, even when the marginal reward and consumption distributions have bounded densities on compact supports. This is one price of degeneracy: continuous random consumption can create thin cutoff mass. A companion note Zhang (2026b) studies the unknown-distribution setting. When the arrival distribution is unknown but all arrivals are observed, and the endpoint shape parameters—the local endpoint mass exponents of Definition 2.4—are known, a smoothed empirical version of the expected-hindsight marginal rule is analyzed there through the same swept active-mass stability estimate. The companion note shows that this plug-in rule preserves the rates of Theorem 2.5: (log T )2 when p = 1, and T 1/2−1/(2p) up to logarithmic factors when p > 1. Several questions remain open. One is algorithmic: the sample-path marginal policy uses the marginal value of the expected hindsight problem, while much of the online allocation literature works with policies that periodically re-solve fluid or empirical relaxations. It would be useful to understand whether the same rates can be achieved with substantially fewer re-solves, or with simpler approximations to the marginal value rule. A second question is structural. In this paper, a type has one random scalar size that scales a fixed resource bundle. A natural next step is to allow a request to have a genuinely random consumption vector, with different random size distributions across resources. Such a model would allow several resources to become critical simultaneously and would require controlling multidimensional cutoff structure without imposing fluid non-degeneracy assumptions such as unique dual prices or strict complementarity.
References Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4):876–890, 2014. Alessandro Arlotto and Itai Gurvich. Uniformly bounded regret in the multisecretary problem. Stochastic Systems, 9(3):231–260, 2019. Alessandro Arlotto and Xinchang Xie. Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards. Stochastic Systems, 10(2):170–191, 2020. Arash Asadpour, Xuan Wang, and Jiawei Zhang. Online resource allocation with limited flexibility. Management Science, 66(2):642–666, 2020. Santiago R. Balseiro, Omar Besbes, and Dana Pizarro. Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research, 72(5):2168–2189, 2024. Santiago R. Balseiro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 71(1):101–119, 2023. Siddhartha Banerjee and Daniel Freund. Good prophets know when the end is near. Management Science, 71(6):4877–4894, 2025. Omar Besbes, Yash Kanoria, and Akshit Kumar. Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances. Operations Research, 73(3):1273–1288, 2025.
31
Anand Bhalgat, Ashish Goel, and Sanjeev Khanna. Improved approximation results for stochastic knapsack problems. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1647–1665, 2011. Boyd, Stephen, Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. Robert L. Bray. Logarithmic regret in multisecretary and online linear programs with continuous valuations. Operations Research, 73(4):2188–2203, 2025. Pornpawee Bumpensanti and He Wang. A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66(7):2993–3009, 2020. J. Camacho, M. J. Cánovas, H. Gfrerer, and J. Parra. Hoffman constant of the argmin mapping in linear optimization. arXiv preprint arXiv:2307.01034, version 2, 2026. Yilun Chen and Wenjia Wang. Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming. arXiv preprint arXiv:2501.01716, 2025. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Adaptivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 395–404, 2005. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research, 33(4):945–964, 2008. Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs. SIAM Journal on Computing, 49(3):540–582, 2020. Daniel Freund and Jiayu Zhao. Overbooking with bounded loss. Mathematics of Operations Research, 48(3):1344–1363, 2023. Guillermo Gallego and Garrett van Ryzin. Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Science, 40(8):999–1020, 1994. √ Wenzhi Gao, Dongdong Ge, Chenyu Xue, Chunlin Sun, and Yinyu Ye. Beyond O( T ) regret. arXiv preprint arXiv:2501.02761, 2025. Varun Gupta. Greedy algorithm for multiway matching with bounded regret. Operations Research, 72(3):1139–1155, 2024. Shuangchi He, Yifan Wei, Jinzhi Xu, and Shuanghao Yu. Online resource allocation without resolving: The effectiveness of primal-dual policies. Working paper, SSRN 5133857, 2025. Alan J. Hoffman. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 49(4):263–265, 1952. Stefanus Jasin and Sunil Kumar. A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37(2):313–345, 2012. Jiashuo Jiang, Xiaocheng Li, and Jiawei Zhang. Online stochastic optimization with Wassersteinbased nonstationarity. Management Science, 71(11):9104–9122, 2025. 32
Jiashuo Jiang, Will Ma, and Jiawei Zhang. Degeneracy is OK: Logarithmic regret for network revenue management with indiscrete distributions. Operations Research, 73(6):3405–3420, 2025. Jiashuo Jiang, Will Ma, and Jiawei Zhang. Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Operations Research, 73(3):1703–1721, 2025. Jiashuo Jiang and Jiawei Zhang. Online resource allocation with stochastic resource consumption. arXiv preprint arXiv:2012.07933, 2020. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing LPs in the random-order model. SIAM Journal on Computing, 47(5):1939–1964, 2018. Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem. Operations Research, 46(1):17–35, 1998. Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem with random sized items. Operations Research, 49(1):26–41, 2001. Xiaocheng Li and Yinyu Ye. Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research, 70(5):2948–2966, 2022. Xiaocheng Li, Chunlin Sun, and Yinyu Ye. Simple and fast algorithm for binary integer and online linear programming. Mathematical Programming, 200:831–875, 2023. Guokai Li, Zizhuo Wang, and Jingwei Zhang. Infrequent resolving algorithm for online linear programming. arXiv preprint arXiv:2408.00465, 2024. George S. Lueker. Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms, 29(2):277–305, 1998. Will Ma. Improvements and generalizations of stochastic knapsack and Markovian bandit approximation algorithms. Mathematics of Operations Research, 43(3):789–812, 2018. Wanteng Ma, Ying Cao, Danny H. K. Tsang, and Dong Xia. Optimal regularized online allocation by adaptive re-solving. Operations Research, 73(4):2079–2096, 2025. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Mathematical Programming, 68:73–104, 1995. Martin I. Reiman and Qiong Wang. An asymptotically optimal policy for a quantity-based network revenue management problem. Mathematics of Operations Research, 33(2):257–282, 2008. Kalyan T. Talluri and Garrett J. van Ryzin. The Theory and Practice of Revenue Management. Springer, 2004. Alberto Vera and Siddhartha Banerjee. The Bayesian prophet: A low-regret framework for online decision making. Management Science, 67(3):1368–1391, 2021. Alberto Vera, Siddhartha Banerjee, and Itai Gurvich. Online allocation and pricing: Constant regret via Bellman inequalities. Operations Research, 69(3):821–840, 2021. Yifan Wei, Jinzhi Xu, and Shuanghao Yu. Constant regret primal-dual policy for multi-way dynamic matching. Working paper, SSRN 4357216, 2023. 33
Jiawei Zhang. Tight lower bounds for the multi-secretary problem via Bellman certificates. SSRN working paper, abstract no. 6772762, posted May 22, 2026, revised June 3, 2026. Available at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=6772762. Jiawei Zhang. Online resource allocation with continuously distributed reward and consumption: unknown distributions case. Working paper, 2026.
A
Auxiliary proofs for Section 3
A.1
Proof of Proposition 3.1
Proof of Proposition 3.1. To analyze the total reward collected by the SPM algorithm, we denote, at the decision epoch with s periods remaining, the current arrival as Zs = (Js , βs , Vs ) and Xs ∈ {0, 1} as the SPM decision. Recall that BT = bT . We have RegT (SPM; bT ) " T # X = ΦT (bT ) − E Vs Xs s=1
" = E ΦT (BT ) − Φ0 (B0 ) −
T X
# Vs Xs
s=1
" T # T X X =E Φs (Bs ) − Φs−1 (Bs−1 ) − Vs Xs s=1
(A.1)
s=1
" T # X =E Φs (Bs ) − Vs Xs − Φs−1 (Bs−1 ) s=1
" T # X Φs (Bs ) − Vs Xs − Φs−1 (Bs − βs aJs Xs ) =E s=1
#!# " T " X max{Φs−1 (Bs ), Vs + Φs−1 (Bs − βs aJs )}1{βs aJs ≤ Bs } Bs . Φs (Bs ) − E =E + Φs−1 (Bs )1{βs aJs ̸≤ Bs } s=1 The inner expectation is over the current arrival Zs , conditionally on the realized remaining capacity Bs . The last equality uses that SPM is the one-step greedy rule. By (2.2), on the feasible event {βs aJs ≤ Bs } the policy accepts (Xs = 1) exactly when Vs + Φs−1 (Bs − βs aJs ) ≥ Φs−1 (Bs ), so Vs Xs + Φs−1 (Bs − βs aJs Xs ) equals the displayed maximum; on the infeasible event Xs = 0, so this quantity equals Φs−1 (Bs ). We now upper-bound the first term in the one-step gap, Φs (Bs ). Recall that Φs (Bs ) is the expected value of the s-period offline fractional hindsight LP with initial capacity Bs . The offline LP allows fractional decisions. We first show that, for the current arrival Zs = (Js , βs , Vs ), any fractional use can be removed at expected cost O(1/s). For each realized s-tuple of arrivals and capacity Bs , choose a basic optimal solution by a permutation-equivariant measurable rule. One way to obtain such a rule is to attach independent continuous auxiliary labels to the s arrivals, order the arrivals by these labels, and choose the first basic optimum in the resulting finite, label-ordered list of bases. The labels are used only to select among optimal basic solutions and do not change the offline value. 34
A basic optimum of a d-resource fractional knapsack LP has at most d fractional variables. Since the selected basic optimum is permutation-equivariant and the s arrivals are exchangeable, the distinguished current arrival is fractional with probability " s # 1X d ∗ E 1{0 < Xi < 1} ≤ . s s i=1
Rounding down the fractional use of this one arrival loses at most v̄. Let OPTbs (Bs ; Zs , W ) be the s-period offline optimum in which the current arrival Zs is restricted to a binary decision, while the remaining s − 1 arrivals W stay fractional. Rounding the distinguished arrival in the selected basic optimum gives the pathwise bound OPTs (Bs ; Zs , W ) − OPTbs (Bs ; Zs , W ) ≤ v̄ 1{0 < Xs∗ < 1}, so, taking expectations and using the fractional-probability bound above, h i dv̄ Φs (Bs ) ≤ E OPTbs (Bs ; Zs , W ) + . s It therefore suffices to bound E[OPTbs (Bs ; Zs , W )], at the cost of the additive C/s. Now separate the two cases for the binary offline decision on Zs . Let W be any sample path of the remaining s − 1 arrivals. If βs aJs ̸≤ Bs , then accepting Zs is infeasible, so the current arrival must be rejected and the future value is at most OPTs−1 (Bs ; W ). If βs aJs ≤ Bs , then the offline solution may either reject Zs , leaving capacity Bs , or accept it, leaving capacity Bs − βs aJs . Thus, with the current arrival restricted to a binary decision, OPTbs (Bs ; Zs , W ) = max{OPTs−1 (Bs ; W ), Vs + OPTs−1 (Bs − βs aJs ; W )}1{βs aJs ≤ Bs } + OPTs−1 (Bs ; W )1{βs aJs ̸≤ Bs }. It remains to rewrite the feasible-acceptance term. On the event {βs aJs ≤ Bs }, define YW = YW (Bs , Js , βs ) =
OPTs−1 (Bs ; W ) − OPTs−1 (Bs − βs aJs ; W ) . βs
Then, conditional on Bs , Js , βs , W , max{OPTs−1 (Bs ; W ), Vs + OPTs−1 (Bs − βs aJs ; W )} = OPTs−1 (Bs ; W ) + Vs − βs YW
+
.
Averaging this pathwise identity first over Vs and then over W gives EW EVs max{OPTs−1 (Bs ; W ), Vs + OPTs−1 (Bs − βs aJs ; W )} | Bs , Js , βs , W h h ii + = EW OPTs−1 (Bs ; W ) + EVs Vs − βs YW | Js , βs = EW [OPTs−1 (Bs ; W ) + HJs ,βs (YW )] = Φs−1 (Bs ) + EW [HJs ,βs (YW )] h i = Φs−1 (Bs ) + HJs ,βs (EW [YW ]) + EW [HJs ,βs (YW )] − HJs ,βs (EW [YW ]) i h Js = E max{Φs−1 (Bs ), Vs + Φs−1 (Bs − βs a )} Bs , Js , βs + EW [HJs ,βs (YW )] − HJs ,βs (EW [YW ]) 35
where the last equality follows from the definition of HJs ,βs and the identity βs EW [YW ] = Φs−1 (Bs ) − Φs−1 (Bs − βs aJs ) . The bracketed term is the Jensen loss from replacing the random future-path marginal YW by its expectation. Averaging this Jensen loss over the feasible current type and size gives Ξs (Bs ). Therefore Φs (Bs ) ≤ E max{Φs−1 (Bs ), Vs + Φs−1 (Bs − βs aJs )}1{βs aJs ≤ Bs } Bs (A.2) C + Φs−1 (Bs )P(βs aJs ̸≤ Bs | Bs ) + Ξs (Bs ) + . s The first two terms on the right-hand side of (A.2) are precisely the one-step expression already subtracted in (A.1). Hence, for every s ≥ 3, C E Φs (Bs ) − Vs Xs − Φs−1 (Bs − βs aJs Xs ) ≤ E[Ξs (Bs )] + . s Substituting this bound into (A.1) and summing over s = 1, . . . , T — with Ξs ≡ 0 for s ≤ 2, whose one-step gaps are O(1) and at most C/s after enlarging C — gives T X C . RegT (SPM; bT ) ≤ C + E[Ξs (Bs )] + s s=1
This proves the proposition.
A.2
Cutoff selection and active-hull closure
This appendix supplies two technical ingredients deferred from Section 3.1. The first is the bounded cutoff selection lemma. The second is the active-hull closure lemma, which turns a pairwise active cap into a cap on the full projected hull. Proof of Lemma 3.2. The function g(θ) is concave and Lipschitz, because OPTn (·; W ) is the optimal value of a finite-dimensional linear program as a function of its right-hand side. Hence g is differentiable for almost every θ ∈ [0, 1]. Fix such a value of θ. We first bound the derivative of g along this capacity path by the reward-ratio support. For 0 < ε ≤ 1 − θ, 0 ≤ g(θ) − g(θ + ε) ≤ εzy. The lower bound follows from monotonicity of the offline value in capacity. To prove the upper bound, we pass to the dual of the box-constrained offline LP. Its upper-bound constraints xi ≤ 1 carry nonnegative multipliers ηi , and the dual is min
λ≥0, η≥0
b⊤ θ+ε λ +
n X
ηi
subject to
βi (aJi )⊤ λ + ηi ≥ Vi ,
i = 1, . . . , n.
i=1
Let (λ, η) be an optimal dual solution, and set Mj := v/(βαj ). We claim that clipping λ to λ ∧ M , while keeping η fixed, gives another optimal dual solution. Feasibility is preserved item by item. Fix i. If every coordinate j with aJj i > 0 has λj ≤ Mj , then (aJi )⊤ (λ ∧ M ) = (aJi )⊤ λ on those
36
coordinates and the i-th constraint is unchanged. Otherwise some such coordinate has λj > Mj , and since aJi ̸= 0 gives aJj i ≥ αj , βi (aJi )⊤ (λ ∧ M ) ≥ βi aJj i Mj ≥ β αj ·
v = v ≥ Vi , βαj
k so the i-th constraint holds even with ηi = P0. Because bθ+ε ≥ 0, which holds since za ≤ b, and ⊤ λ ∧ M ≤ λ, the objective bθ+ε (λ ∧ M ) + i ηi does not increase, so (λ ∧ M, η) is again optimal. Therefore the offline LP at bθ+ε has an optimal resource-dual vector λ with λj ≤ Mj for all j. Since the offline value is concave in the right-hand side, this dual vector is a supergradient at bθ+ε . Taking bθ = bθ+ε + εzak , we obtain
g(θ) = OPTn (bθ ; W ) ≤ OPTn (bθ+ε ; W ) + λ⊤ (bθ − bθ+ε ) = g(θ + ε) + εz λ⊤ ak . The coordinatewise bound on λ gives λ⊤ ak ≤
d X
Mj akj = yk ≤ y.
j=1
Hence 0 ≤ g(θ) − g(θ + ε) ≤ εzy. Dividing by εz and letting ε ↓ 0 gives 0≤−
g ′ (θ) ≤ y. z
(A.3)
Let xθ be an optimal solution of the pathwise fractional problem with capacity bθ . Define the normalized type allocation by uθ,W,ℓ =
1 X βi xθi , n
ℓ = 1, . . . , K.
i:Ji =ℓ
Then 0 ≤ uθ,W ≤ m bW,
Auθ,W ≤ ρθ .
Thus uθ,W ∈ Km b W (ρθ ). Let λθ be an optimal dual vector for the resource constraints at capacity bθ such that g ′ (θ) = −z(ak )⊤ λθ . Such a choice exists by standard LP sensitivity analysis; see Boyd and Vandenberghe (2004, Sec. 5.6.3, Eq. (5.58)). We construct qθ,W from this dual vector. Complementary slackness gives, for every item i with Ji = ℓ, Vi /βi > (aℓ )⊤ λθ ⇒ xθi = 1,
Vi /βi < (aℓ )⊤ λθ ⇒ xθi = 0.
Consequently, whenever (aℓ )⊤ λθ ≤ y, bℓ,W ((aℓ )⊤ λθ )+ ≤ uθ,W,ℓ ≤ C bℓ,W ((aℓ )⊤ λθ ). C Set qθ,W,ℓ = min{(aℓ )⊤ λθ , y},
37
ℓ = 1, . . . , K.
Then qθ,W ∈ [0, y]K . Since (ak )⊤ λθ = −g ′ (θ)/z, the bound (A.3) gives qθ,W,k = −
g ′ (θ) , z
which proves (3.4). It remains to verify the tail condition. If (aℓ )⊤ λθ ≤ y, then (3.5) follows from the preceding display. If (aℓ )⊤ λθ > y, then Vi /βi < (aℓ )⊤ λθ for every item i with Ji = ℓ. Complementary slackness therefore gives xθi = 0 for all such items, and hence uθ,W,ℓ = 0. Since qθ,W,ℓ = y, bℓ,W (qθ,W,ℓ +) = C bℓ,W (y+) = 0 ≤ uθ,W,ℓ ≤ C bℓ,W (y) = C bℓ,W (qθ,W,ℓ ). C This proves (3.5) for every ℓ. We next prove (3.7). Let Uθ,W,ℓ :=
X
βi xθi = nuθ,W,ℓ .
i:Ji =ℓ ′ For every u′ ∈ Km b W (ρθ ), feasibility of u and nonnegativity of λθ imply ⊤ ′ ⊤ λ⊤ θ A(u − uθ,W ) ≤ λθ ρθ − λθ Auθ,W =
1 ⊤ λ (bθ − AUθ,W ). n θ
The last term is zero by complementary slackness in the unnormalized pathwise LP. Equivalently, K X
((aℓ )⊤ λθ )(u′ℓ − uθ,W,ℓ ) ≤ 0.
(A.4)
ℓ=1
By definition, qθ,W,ℓ = min{(aℓ )⊤ λθ , y},
ℓ = 1, . . . , K.
Thus qθ,W,ℓ ≤ (aℓ )⊤ λθ for every ℓ. Strict inequality can occur only when (aℓ )⊤ λθ > y. In that case every type-ℓ item has negative reduced cost, so uθ,W,ℓ = 0. Therefore, for every feasible u′ and every ℓ, qθ,W,ℓ (u′ℓ − uθ,W,ℓ ) ≤ ((aℓ )⊤ λθ )(u′ℓ − uθ,W,ℓ ). Combining this inequality with (A.4) yields K X
qθ,W,ℓ (u′ℓ − uθ,W,ℓ ) ≤ 0,
u′ ∈ Km b W (ρθ ).
(A.5)
ℓ=1
Finally, we replace each coordinate of qθ,W by its projection onto the corresponding active support. Fix ℓ. If qθ,W,ℓ > rℓ+ , then (aℓ )⊤ λθ ≥ qθ,W,ℓ > rℓ+ ; since every realized type-ℓ ratio lies in [rℓ− , rℓ+ ], each type-ℓ item has Vi /βi ≤ rℓ+ < (aℓ )⊤ λθ , so complementary slackness gives xθi = 0 and uθ,W,ℓ = 0. Hence u′ℓ − uθ,W,ℓ ≥ 0 for every feasible u′ , and since Πℓ (qθ,W,ℓ ) ≤ qθ,W,ℓ , Πℓ (qθ,W,ℓ )(u′ℓ − uθ,W,ℓ ) ≤ qθ,W,ℓ (u′ℓ − uθ,W,ℓ ). If qθ,W,ℓ < rℓ− , then (aℓ )⊤ λθ = qθ,W,ℓ < rℓ− ; since every realized type-ℓ ratio lies in [rℓ− , rℓ+ ], each typeℓ item has Vi /βi ≥ rℓ− > (aℓ )⊤ λθ , so complementary slackness gives xθi = 1 and uθ,W,ℓ = m b ℓ,W = − ′ ′ b Cℓ,W (rℓ ). Every feasible u then satisfies uℓ ≤ m b ℓ,W = uθ,W,ℓ , and since Πℓ (qθ,W,ℓ ) ≥ qθ,W,ℓ , Πℓ (qθ,W,ℓ )(u′ℓ − uθ,W,ℓ ) ≤ qθ,W,ℓ (u′ℓ − uθ,W,ℓ ). If qθ,W,ℓ ∈ Sℓ , the two sides are equal. Summing over ℓ and using (A.5) proves (3.7). 38
We now prove the active-hull closure lemma used in Lemma 3.5. For q, q̄ ∈ [0, y] and a closed interval B ⊂ [0, y], define IB (q, q̄) := [q ∧ q̄, q ∨ q̄] ∩ B and dB (q, q̄) := Leb(IB (q, q̄)). Lemma A.1 (Active-hull closure of a pairwise cap). Let ν be a finite atomless measure on a closed interval B ⊂ [0, y], and let Q ⊂ [0, y]. Suppose that, for some r > 0, dB (q, q̄)ν(IB (q, q̄)) ≤ r,
q, q̄ ∈ Q.
(A.6)
Let u := inf{ΠB (q) : q ∈ Q},
v := sup{ΠB (q) : q ∈ Q}.
Then (v − u)ν([u, v]) ≤ r.
(A.7)
Proof. If u = v, the claim is immediate. Suppose that u < v. First consider the case in which both extremes are attained. Thus there exist q − , q + ∈ Q such that ΠB (q − ) = u, ΠB (q + ) = v. Then IB (q − , q + ) = [u, v],
dB (q − , q + ) = v − u.
The pairwise cap (A.6) gives (v − u)ν([u, v]) = dB (q − , q + )ν(IB (q − , q + )) ≤ r. It remains to handle the case in which at least one extreme is not attained. For every 0 < η < (v − u)/2, the definitions of u and v give qη , q̄η ∈ Q such that ΠB (qη ) ≤ u + η,
ΠB (q̄η ) ≥ v − η.
Therefore [u + η, v − η] ⊆ IB (qη , q̄η ). It follows that dB (qη , q̄η ) ≥ v − u − 2η and ν(IB (qη , q̄η )) ≥ ν([u + η, v − η]). Using (A.6), we obtain (v − u − 2η)ν([u + η, v − η]) ≤ r. Letting η ↓ 0, and using that ν is finite and atomless, gives (v − u)ν([u, v]) ≤ r. This proves (A.7).
39
A.3
Projected stability estimates
This appendix proves the three fixed-polytope estimates used in the proof of Proposition 3.6: a uniform optimal-face Hoffman bound, an optimal value and solution sensitivity estimate, and the projected comparison for single-interval systems. Credit. The finite-switching path idea used below is inspired by the well-connected polyhedral mapping viewpoint of Camacho et al. (2026) for right-hand-side perturbations of linear-program argmin maps. Their paper develops such perturbations through finite unions of convex polyhedral graph pieces; the argument below uses only the classical Hoffman bound. Lemma A.2 (Uniform optimal-face Hoffman bound). Let B be an m × n matrix, and let C ⊂ Rm and S ⊂ Rn be compact. Assume that, for every a ∈ conv(C), P (a) := {v ∈ Rn : Bv ≤ a} is nonempty, and that the family {P (a) : a ∈ conv(C)} is uniformly bounded. Then there is a constant C < ∞ such that the following holds. If c, c′ ∈ C, s ∈ S, ∥c − c′ ∥∞ ≤ ∆, and x′ ∈ arg max{s⊤ v : v ∈ P (c′ )}, then there exists x ∈ arg max{s⊤ v : v ∈ P (c)} such that ∥x − x′ ∥1 ≤ C∆. Proof. We apply Hoffman’s bound to the optimal face induced by the price vector s. The main point is that the resulting constant can be chosen independently of s. We use the classical Hoffman error bound for systems of linear inequalities and equalities; see Hoffman (1952). Write Bi for the i-th row of B. For each subset D ⊆ {1, . . . , m}, define PD (a) := {v : Bv ≤ a, BD v = aD }, where the equality constraints are vacuous when D = ∅. Hoffman’s bound gives a constant HD < ∞, depending only on B and D, such that, whenever PD (a) ̸= ∅, n o dist1 (y, PD (a)) ≤ HD max ∥(By − a)+ ∥∞ , ∥BD y − aD ∥∞ . (A.8) Let H :=
max D⊆{1,...,m}
HD < ∞.
Fix s ∈ S. For a ∈ conv(C), write Φ(a, s) := arg max{s⊤ v : v ∈ P (a)}. The defining linear program and its dual are max{s⊤ v : Bv ≤ a}
min{a⊤ λ : B ⊤ λ = s, λ ≥ 0}.
and
Let D(s) be the finite family of subsets D ⊆ {1, . . . , m} for which there exist coefficients λi > 0, i ∈ D, satisfying X s= λi Bi⊤ . i∈D
40
These coefficients depend on s and B, but not on the right-hand side a. When s = 0, the empty set belongs to D(s). We claim that, for every D ∈ D(s) and every a ∈ conv(C) such that PD (a) ̸= ∅, PD (a) = Φ(a, s).
(A.9)
Fix such D and a, and let λ be the nonnegative vector supported on D with B ⊤ λ = s. Then λ is feasible for the dual problem. If z ∈ PD (a), then s⊤ z = λ⊤ Bz = λ⊤ a. By weak duality, z and λ are primal and dual optimal. Hence PD (a) ⊆ Φ(a, s). Conversely, let v ∈ Φ(a, s). Since λ is dual optimal, X 0 = λ ⊤ a − s⊤ v = λi (ai − Bi v). i∈D
Each term in the final sum is nonnegative, and each coefficient λi , i ∈ D, is strictly positive. Therefore Bi v = ai for every i ∈ D, so v ∈ PD (a). This proves (A.9). Now fix c, c′ ∈ C, and define δ := ∥c − c′ ∥∞ ,
γ(t) := c′ + t(c − c′ ),
t ∈ [0, 1].
The sets P (γ(t)), 0 ≤ t ≤ 1, are nonempty and lie in a common compact set. Indeed, γ(t) ∈ conv(C) for every t ∈ [0, 1], and the family P (a) is uniformly bounded over conv(C). For each D ∈ D(s), define ID := {t ∈ [0, 1] : PD (γ(t)) ̸= ∅}. We claim that each nonempty ID is a closed interval. Convexity follows by taking convex combinations of feasible witnesses. If v0 ∈ PD (γ(t0 )) and v1 ∈ PD (γ(t1 )), then, for θ ∈ [0, 1], the point (1 − θ)v0 + θv1 lies in PD (γ((1 − θ)t0 + θt1 )). This is because both the inequalities Bv ≤ γ(t) and the equalities BD v = γD (t) are preserved under convex combination, while γ(t) varies affinely in t. To prove closedness, take tr ∈ ID with tr → t, and choose vr ∈ PD (γ(tr )). The points vr lie in the common compact set, so a subsequence converges to some v. Passing to the limit in the inequalities and equalities gives v ∈ PD (γ(t)). Hence t ∈ ID . The finitely many intervals {ID : D ∈ D(s)} cover [0, 1]. To see this, fix t ∈ [0, 1], and choose vt ∈ Φ(γ(t), s). By strong linear-program duality, there is a dual optimal solution λ(t) ≥ 0 such that B ⊤ λ(t) = s, λi (t) γi (t) − Bi vt = 0 for all i. Let D(t) := {i : λi (t) > 0}. Then D(t) ∈ D(s). Complementary slackness gives Bi vt = γi (t) for every i ∈ D(t), and therefore vt ∈ PD(t) (γ(t)). Thus t ∈ ID(t) . 41
Since a finite family of closed intervals covers [0, 1], we may choose points 0 = t0 < t1 < · · · < tN = 1 and subsets D1 , . . . , DN ∈ D(s) such that [tj−1 , tj ] ⊆ IDj ,
j = 1, . . . , N.
Set x0 := x′ . We construct points xj ∈ Φ(γ(tj ), s) inductively. Suppose that xj−1 ∈ Φ(γ(tj−1 ), s). Since [tj−1 , tj ] ⊆ IDj , (A.9) gives PDj (γ(tj−1 )) = Φ(γ(tj−1 ), s),
PDj (γ(tj )) ̸= ∅.
Thus xj−1 ∈ PDj (γ(tj−1 )). Applying (A.8) to the nonempty target set PDj (γ(tj )), we obtain a point xj ∈ PDj (γ(tj )) such that ∥xj − xj−1 ∥1 ≤ H∥γ(tj ) − γ(tj−1 )∥∞ = H(tj − tj−1 )δ. Because tj ∈ IDj , this point also satisfies xj ∈ Φ(γ(tj ), s) by (A.9). Summing over j = 1, . . . , N , we get ∥xN − x′ ∥1 ≤ Hδ
N X
(tj − tj−1 ) = Hδ.
j=1
Since γ(1) = c, the point x := xN belongs to Φ(c, s). Taking C := H yields ∥x − x′ ∥1 ≤ C∥c − c′ ∥∞ ≤ C∆, which completes the proof. Lemma A.3 (Optimal value and solution sensitivity estimate). Fix compact coordinatewise ranges for m and ρ such that Km (ρ) ̸= ∅ for every (m, ρ) in these ranges. For r ∈ [0, y]K , define hm,ρ (r) := max{r⊤ v : v ∈ Km (ρ)}. Then there is a constant C < ∞ such that, for all admissible m, m̄, ρ, ρ̄ and all r, r̄ ∈ [0, y]K , hm,ρ (r) + hm̄,ρ̄ (r̄) − hm̄,ρ̄ (r) − hm,ρ (r̄) ≥ −C∥ρ − ρ̄∥∞ − C∥m − m̄∥∞ ∥r − r̄∥1 . Consequently, if u maximizes r⊤ v over Km (ρ) and ū maximizes r̄⊤ v over Km̄ (ρ̄), then (r − r̄)⊤ (u − ū) ≥ −C∥ρ − ρ̄∥∞ − C∥m − m̄∥∞ ∥r − r̄∥1 . Proof. Let
I B0 := −I , A
m c(m, ρ) := 0 . ρ
Then Km (ρ) = {v : B0 v ≤ c(m, ρ)}. Applying Lemma A.2 to the fixed matrix B0 and to the compact ranges under consideration gives a constant L < ∞ with the following property. If ∥c(m, ρ) − c(m′ , ρ′ )∥∞ ≤ ∆, and if z ′ maximizes s⊤ x over Km′ (ρ′ ) for some s ∈ [0, y]K , then there is a maximizer z of s⊤ x over Km (ρ) such that ∥z − z ′ ∥1 ≤ L∆. 42
(A.10)
We first vary only the resource right-hand side. Fix m and s ∈ [0, y]K . If w′ ∈ arg maxKm (ρ′ ) s⊤ x, then (A.10) gives w ∈ arg maxKm (ρ) s⊤ x with ∥w − w′ ∥1 ≤ L∥ρ − ρ′ ∥∞ . Therefore hm,ρ (s) = s⊤ w ≥ s⊤ w′ − ∥s∥∞ ∥w − w′ ∥1 ≥ hm,ρ′ (s) − yL∥ρ − ρ′ ∥∞ . Interchanging ρ and ρ′ yields |hm,ρ (s) − hm,ρ′ (s)| ≤ yL∥ρ − ρ′ ∥∞ .
(A.11)
Define F (m, ρ; m̄, ρ̄; r, r̄) := hm,ρ (r) + hm̄,ρ̄ (r̄) − hm̄,ρ̄ (r) − hm,ρ (r̄). Applying (A.11) twice gives F (m, ρ; m̄, ρ̄; r, r̄) ≥ F (m, ρ; m̄, ρ; r, r̄) − 2yL∥ρ − ρ̄∥∞ .
(A.12)
It remains to bound F (m, ρ; m̄, ρ; r, r̄). Consider first a one-coordinate change in m. Suppose that m+ = m + ηej , where η ≥ 0, and set Gj (s) := hm+ ,ρ (s) − hm,ρ (s). We claim that |Gj (r) − Gj (r̄)| ≤ Lη∥r − r̄∥1 .
(A.13)
Let d := r − r̄ and st := r̄ + td, 0 ≤ t ≤ 1. The functions g + (t) := hm+ ,ρ (st ) and g(t) := hm,ρ (st ) are Lipschitz in t, and hence are differentiable for almost every t. We use the standard derivative formula for support functions. If hK (s) = maxv∈K s⊤ v and XK (s) is its optimizer set, then, at every t where hK (st ) is differentiable, d hK (st ) = d⊤ x dt
for every x ∈ XK (st ).
(A.14)
Indeed, the right derivative is maxx∈XK (st ) d⊤ x, the left derivative is minx∈XK (st ) d⊤ x, and these two values coincide at points of differentiability. Fix a point t at which both g + and g are differentiable, and choose x+ (t) ∈ arg maxv∈Km+ (ρ) s⊤ t v. + The right-hand sides c(m , ρ) and c(m, ρ) differ only in the j-th upper-bound coordinate, by η. + Thus (A.10) gives a point x(t) ∈ arg maxv∈Km (ρ) s⊤ t v with ∥x (t) − x(t)∥1 ≤ Lη. Using (A.14), we obtain, for almost every t, d + {g (t) − g(t)} = |d⊤ (x+ (t) − x(t))| ≤ ∥d∥∞ ∥x+ (t) − x(t)∥1 ≤ Lη∥d∥1 . dt Integrating over t ∈ [0, 1] proves (A.13). For this one-coordinate increase, hm,ρ (r) + hm+ ,ρ (r̄) − hm+ ,ρ (r) − hm,ρ (r̄) = Gj (r̄) − Gj (r) ≥ −Lη∥r − r̄∥1 . The same bound holds for a coordinate decrease, after interchanging the two vectors. Now connect m to m̄ one coordinate at a time. Let m0 = m and mK = m̄, where ( m̄i , i ≤ j, j mi = j = 1, . . . , K. mi , i > j, 43
The vectors mj−1 and mj differ only in coordinate j, by ηj := |m̄j − mj |. Summing the onecoordinate estimate gives hm,ρ (r) + hm̄,ρ (r̄) − hm̄,ρ (r) − hm,ρ (r̄) ≥ −L∥r − r̄∥1
K X
|m̄j − mj | ≥ −LK∥m − m̄∥∞ ∥r − r̄∥1 .
j=1
Combining this estimate with (A.12), and absorbing 2yL and LK into a single constant C, gives the desired four-point estimate. It remains to prove the final displayed inequality in the lemma. By the definitions of u and ū, we have r⊤ u = hm,ρ (r) and r̄⊤ ū = hm̄,ρ̄ (r̄). Since ū ∈ Km̄ (ρ̄) and u ∈ Km (ρ), r⊤ ū ≤ hm̄,ρ̄ (r), Therefore
r̄⊤ u ≤ hm,ρ (r̄).
(r − r̄)⊤ (u − ū) = r⊤ u + r̄⊤ ū − r⊤ ū − r̄⊤ u ≥ hm,ρ (r) + hm̄,ρ̄ (r̄) − hm̄,ρ̄ (r) − hm,ρ (r̄).
The four-point estimate gives the claimed bound. Lemma A.4 (Projected comparison for single-interval systems). Assume that each active support set Sk is a single interval in [0, y]. For every Cm < ∞, there is a constant C < ∞ such that the following holds. Let m, m̄, ρ, ρ̄ lie in the compact ranges of Lemma A.3. Let u ∈ Km (ρ), ū ∈ Km̄ (ρ̄), and let q, q̄ ∈ [0, y]K . Set pk = Πk (qk ) and p̄k = Πk (q̄k ) for k = 1, . . . , K. If p ∈ NKm (ρ) (u),
p̄ ∈ NKm̄ (ρ̄) (ū),
and ∥m − m̄∥∞ ≤ Cm ε,
∥ρ − ρ̄∥∞ ≤ τ,
then (p − p̄)⊤ (u − ū) ≥ −Cτ − Cε
K X
ℓk (qk , q̄k ),
k=1
where ℓk (a, b) := Leb [a ∧ b, a ∨ b] ∩ Sk . Proof. For a convex set K and a point x ∈ K, write NK (x) := {z : z ⊤ (v − x) ≤ 0 for all v ∈ K}. Thus p ∈ NKm (ρ) (u) means that u maximizes p⊤ v over Km (ρ). Similarly, ū maximizes p̄⊤ v over Km̄ (ρ̄). Since each projection Πk maps into Sk ⊆ [0, y], both p and p̄ belong to [0, y]K . Apply Lemma A.3 with r = p and r̄ = p̄. If C4 is the constant in that lemma, then (p − p̄)⊤ (u − ū) ≥ −C4 ∥ρ − ρ̄∥∞ − C4 ∥m − m̄∥∞ ∥p − p̄∥1 . Using the assumed bounds on m − m̄ and ρ − ρ̄, we get (p − p̄)⊤ (u − ū) ≥ −C4 τ − C4 Cm ε∥p − p̄∥1 .
(A.15)
It remains to express ∥p − p̄∥1 in terms of the portions of the intervals between qk and q̄k + − that lie inside Sk . Write Sk = [s− k , sk ]. For a ≤ b, the projection Πk is constant on (−∞, sk ]
44
− + and on [s+ k , ∞), and it equals the identity on [sk , sk ]. Therefore its variation over [a, b] is exactly Leb([a, b] ∩ Sk ). By symmetry, for all a, b ∈ [0, y], |Πk (a) − Πk (b)| = Leb [a ∧ b, a ∨ b] ∩ Sk = ℓk (a, b). (A.16)
Applying (A.16) with a = qk and b = q̄k , and summing over k, gives ∥p − p̄∥1 =
K X
ℓk (qk , q̄k ).
k=1
Substituting this identity into (A.15), and then renaming constants, proves the claim.
A.4
Endpoint-contact verification
This part completes the proof of the main bound when p > 1. The argument for p = 1 reduced the per-stage marginal loss to an active conditional-curvature product. On a dominated neighborhood, pointwise domination turns that product into the active weighted-resource product controlled by Proposition 3.6. On an endpoint-contact neighborhood, pointwise domination can fail: for sizes near the size boundary, the conditional curvature Λk,z may concentrate near a receding edge e(ω) ≍ ω τ . A short ratio interval can then have conditional curvature of lower order than its size-averaged mass. The active-mass product cap is still available, because Proposition 3.6 is deterministic and uses only projected active intervals. The remaining task is to integrate the conditional curvature along the endpoint branch. The Hardy estimate below does this. Under the active-mass product cap, the size-integrated curvature is at most Crs log(e/rs ), so the endpoint branch costs only a logarithmic factor relative to the dominated case. Assumption 1 is in force throughout this subsection. The deterministic active-mass estimate has already used only the active mass bound (2.7) and the single-interval active supports. The endpoint step below uses the endpoint-contact neighborhoods in Assumption 1. On an endpoint-contact neighborhood, the branch has local exponent θ = γ + α/τ . Lemma A.6 gives the corresponding local branch mass growth. The dominated remainder has, by (2.6), no larger endpoint growth than this branch. Thus the full weighted-ratio measure has local endpoint exponent θ at that contact endpoint. The global active-mass exponent p in (2.7) need not equal this particular θ. Any admissible global exponent must satisfy θ ≤ p, and equality holds only at endpoints that realize the worst local exponent when p is chosen as the smallest admissible exponent. The Hardy bound below is stated for a general θ, so the proof does not require the identification θ = p. Throughout this subsection, C denotes a constant that depends only on the primitive endpoint constants, the number of types, the direction matrix, and the boundedness constants. It never depends on T , s, or the current capacity. A. The endpoint Hardy bound We now convert the active-mass product cap into a bound on the size-integrated conditional curvature. First we isolate the branch disintegration supplied by the endpoint-contact assumption. Then we record the two one-branch estimates used in the Hardy step: the mass contributed to µk , and the Jensen estimate for the branchwise surplus. Lemma A.5 (Kernel branch disintegration). Fix a type k and one endpoint-contact R neighborhood U from Assumption 1. For every nonnegative measurable functional A(z, Λ) = U a(z, r) Λ( dr) 45
that is linear in the curvature measure Λ, there are constants 0 < c ≤ C < ∞, depending only on the primitive bounds on the branch weight w, such that Z ω0 Z Z ω0 β br br c A βk (ω), Λk,ω f (ω) dω ≤ πk A z, Λk,z Pk ( dz) ≤ C A βk (ω), Λbr k,ω f (ω) dω. Bk
0
0
Proof. The endpoint-contact representation decomposes the kernel measure on Bk ×U as Mk |Bk ×U = br D br MD k + Mk , with subkernels Λk,z and Λk,z as in (2.4). Applying the branch identity (2.3) to the nonnegative kernel g(z, r) = a(z, r) gives the exact disintegration Z Z ω0 β πk A z, Λbr P ( dz) = w(ω) A βk (ω), Λbr k,z k,ω f (ω) dω, k Bk
0
and the comparison follows from the primitive upper and lower bounds on w. Lemma A.6 (Endpoint-contact mass bounds). For the endpoint branch of type k, recall θ = γ+α/τ from Definition 2.2. Orient the local ratio coordinate into the support: x = R − rk,0 at a lower endpoint and x = rk,0 − R at an upper endpoint. Then the branch contribution µbr k has Lebesgue θ−1 on (0, x ). Hence, for every interval [a, b] ⊆ [0, x ], (x) ≍ x density mbr 0 0 k θ−1 , c(b − a)bθ−1 ≤ µbr k ({a ≤ x ≤ b}) ≤ C(b − a)b
θ µbr k ({0 ≤ x ≤ x1 }) ≍ x1 .
Proof. By the branch formula in Definition 2.2, Z ω0 (I) = w(ω)Λbr µbr k,ω (I)f (ω) dω. k 0
Since w is bounded above and below by primitive constants, it can be absorbed into the comparability constants. Thus the Lebesgue density of µbr k satisfies Z ω0 f (ω) ≍ ω α−1 . λbr mbr k,ω (x)f (ω) dω, k (x) ≍ 0
The integrand is zero unless e(ω) ≤ x. Since e(ω) ≍ ω τ , the relevant range is 0 ≤ ω ≤ Cx1/τ . The upper density bound therefore gives Z Cx1/τ γ−1 ω α−1 dω ≤ Cxθ−1 . (x) ≤ Cx mbr k 0
For the lower bound, restrict to ω ≤ c x1/τ .
Since e(ω) ≤ Ce ω τ for a primitive constant Ce , and x0 , ω0 are primitive, the constant c may be chosen depending only on the primitive constants— small enough that e(ω) ≤ x/2 and c x1/τ ≤ ω0 for every x ∈ (0, x0 ]. Since γ ≥ 1, λbr k,ω (x) ≥ γ−1 γ−1 br θ−1 c(x − e(ω)) ≥ cx . The same integration gives mk (x) ≥ cx . Rb Integrating the density over [a, b] gives the interval bound. Indeed, since θ ≥ 1, a xθ−1 dx ≍ θ (b − a)bθ−1 . Taking a = 0 and b = x1 gives µbr k ({0 ≤ x ≤ x1 }) ≍ x1 . Lemma A.7 (Endpoint Hardy bound under an active-mass product cap). For the endpoint branch of type k, recall that θ = γ + α/τ . There are constants r0′ > 0 and C < ∞, depending only on the primitive endpoint constants, such that the following holds. Fix 0 < r ≤ r0′ . For each size coordinate ω, let Iω be a local-coordinate ratio interval, and write dω := Leb(Iω ∩ [e(ω), x0 ]), br Λω (Iω ) := Λbr k,ω (Iω ), and µ(Iω ) := µk (Iω ). If the active-mass product cap dω µ(Iω ) ≤ r holds, then
for a.e. ω ∈ [0, ω0 ]
(A.17)
dω Λω (Iω )f (ω) dω ≤ Cr log(e/r).
(A.18)
Z ω0 0
46
Proof. Work in the oriented local coordinate, so the moving active interval is [e(ω), x0 ], with e(ω) ≍ ω τ . If Iω ∩ [e(ω), x0 ] = ∅, then dω = 0, and the corresponding integrand is zero. Hence we may restrict to ω’s for which this intersection is nonempty. For such an ω, set Bω := sup(Iω ∩ [e(ω), x0 ]). Since Iω is an interval, the active intersection is, up to endpoints, an interval [aω , Bω ]. Endpoint conventions do not matter because the branch measures have densities. Thus dω = Bω − aω , so dω ≤ Bω . Also, because Bω ≥ e(ω) and e(ω) ≍ ω τ , Bω ≥ c ω τ .
(A.19)
θ−1 Lemma A.6, applied to [aω , Bω ], gives µbr k ([aω , Bω ]) ≥ c dω Bω . Since [aω , Bω ] ⊆ Iω and θ−1 µ = µbr k is positive, we also have µ(Iω ) ≥ c dω Bω . Combining this lower bound with (A.17) yields
d2ω Bωθ−1 ≤ Cr.
(A.20)
We next bound the conditional curvature term. By the endpoint-branch density assumption, br γ−1 for x ≥ e(ω). Since γ ≥ 1, we have the density of Λbr k,ω satisfies λk,ω (x) ≤ C(x − e(ω)) (x − e(ω))γ−1 ≤ Bωγ−1 for x ∈ [aω , Bω ]. Therefore Λω (Iω ) ≤ Cdω Bωγ−1 . Multiplying by dω and using (A.20), we get dω Λω (Iω ) ≤ Cd2ω Bωγ−1 = Cd2ω Bωθ−1 Bωγ−θ ≤ CrBωγ−θ . Since θ = γ + α/τ , this becomes dω Λω (Iω ) ≤ CrBω−α/τ .
(A.21)
We also need a crude increasing bound. Since dω ≤ Bω , dω Λω (Iω ) ≤ Cd2ω Bωγ−1 ≤ CBωγ+1 .
(A.22)
Combining (A.21) and (A.22), and then using (A.19), gives the pointwise bound dω Λω (Iω ) ≤ C sup min{B γ+1 , rB −α/τ }.
(A.23)
B≥cω τ
−α/τ
Let B∗ := r1/(θ+1) . This is the balancing scale, since B∗γ+1 = rB∗ enough that B∗ ≤ x0 whenever 0 < r ≤ r0′ . Define
. Choose r0′ > 0 small
1/τ
ω∗ := c∗ B∗ ,
(A.24)
where c∗ > 0 is a sufficiently small primitive constant. Reducing r0′ again if necessary, we may assume that ω∗ ≤ ω0 . First consider 0 ≤ ω ≤ ω∗ . By the choice of c∗ , we have cω τ ≤ B∗ . Since B 7→ B γ+1 is increasing and B 7→ rB −α/τ is decreasing, the supremum in (A.23) is attained, up to primitive constants, at the balancing scale B∗ . Thus dω Λω (Iω ) ≤ CB∗γ+1 for 0 ≤ ω ≤ ω∗ . Using f (ω) ≤ Cω α−1 , we obtain Z ω∗ Z ω∗ γ+1 dω Λω (Iω )f (ω) dω ≤ CB∗ ω α−1 dω ≤ CB∗γ+1 ω∗α . 0
0
α/τ
By (A.24), ω∗α ≤ CB∗
. Hence
Z ω∗
γ+1+α/τ
dω Λω (Iω )f (ω) dω ≤ CB∗ 0
47
= CB∗θ+1 = Cr.
(A.25)
Now consider ω > ω∗ . Then cω τ ≥ c′ B∗ , after adjusting primitive constants. The supremum in (A.23) is therefore bounded by the decreasing branch: sup min{B γ+1 , rB −α/τ } ≤ Cr(cω τ )−α/τ ≤ Crω −α . B≥cω τ
Together with (A.23), this gives dω Λω (Iω ) ≤ Crω −α for ω∗ < ω ≤ ω0 . Since f (ω) ≤ Cω α−1 , Z ω0 Z ω0 ω −1 dω ≤ Cr log(e/ω∗ ). dω Λω (Iω )f (ω) dω ≤ Cr ω∗
ω∗ 1/τ
Because ω∗ = c∗ B∗
= c∗ r1/(τ (θ+1)) , we have log(e/ω∗ ) ≤ C log(e/r). Therefore Z ω0 dω Λω (Iω )f (ω) dω ≤ Cr log(e/r).
(A.26)
ω∗
Combining (A.25) and (A.26) yields (A.18), because 0 < r ≤ r0′ and r0′ is fixed. The scale B∗ = r1/(θ+1) balances the increasing and decreasing branches of the size integral. The boundary term log(e/ω∗ ) ≍ log(e/r) is the only logarithmic loss; it is the price of integrating the conditional curvature against the size distribution rather than dominating it pointwise. Proof of Lemma 3.7 Proof of Lemma 3.7. We prove the bound in four steps. First, Proposition 3.6 gives a pathwise active-mass product cap for all good future paths. Second, the cap is extended from pairs of cutoffs to the active hull of the good cutoff support. Third, dominated neighborhoods and endpointcontact neighborhoods are treated separately. Finally, we average over the current size and remove the conditioning on the good futurep event. Let n = s − 1, and set δn := C log(en)/n, as in the concentration event (3.17). Define the deterministic cap scale 1 r̄s := Ccap δn1+1/p + , n where Ccap is large enough to dominate the constant obtained when Proposition 3.6 is applied 1+1/p below. Since δn = C(log(en)/n)(p+1)/(2p) , after increasing constants we have r̄s ≤ Crs .
(A.27)
Let λch > 0 be a Lebesgue number for the finite cover of the active supports Sk by dominated neighborhoods and endpoint-contact neighborhoods, chosen uniformly over all types and cover elements. By the lower active-mass bound in (2.7), every active interval I with active length at least λch satisfies Leb(I ∩ Sk ) µk (I) ≥ c λp+1 (A.28) ch . Let rH > 0 be the minimum of the small-radius constants in Lemma A.7 over the finitely many endpoint-contact neighborhoods. If there are no endpoint-contact neighborhoods, set rH := 1; then the contact-branch part of the proof is vacuous. Reduce rH , if needed, so that 1 . rH ≤ c λp+1 2 ch
(A.29)
Choose s0 so large that, for all s ≥ s0 , we have δn ≤ ε0 , r̄s ≤ rH , and P(En ) ≥ 1/2, where ε0 is the smallness threshold in Proposition 3.6. 48
Fix a current type and size pair (k, z) with zak ≤ b. For θ ∈ [0, 1], set bθ := b − θzak and ρθ := bθ /n. Let mmax dominate every normalized empirical vector m b W , and set ρmax := Ammax eff max and ρθ := ρθ ∧ ρ . As in (3.22), clipping nonbinding resource coordinates does not change the feasible set: eff Km (A.30) b W (ρθ ) = Km b W (ρθ ). The clipping map is coordinatewise 1-Lipschitz. Hence, uniformly over θ, θ′ ∈ [0, 1], eff ∥ρeff θ − ρθ′ ∥∞ ≤ ∥ρθ − ρθ′ ∥∞ ≤
C z∥ak ∥∞ ≤ . n n
(A.31)
By Lemma 3.2, for a.e. θ and almost every future path W , we may choose a normalized (z) (z) (z) eff empirical primal–cutoff pair (b uθ,W , qθ,W ). It satisfies u bθ,W ∈ Km b W (ρθ ), the empirical closed/right tail relations, and (z) (z) Π(qθ,W ) ∈ NKmb (ρeff ) (b uθ,W ). W
θ
Here (A.30) transfers feasibility and projected normality to the clipped feasible set. The superscript (z) records that the capacity path depends on the current size z. We choose jointly measurable representatives on the full-measure differentiability sets; null sets in (θ, z, W ) are irrelevant by Fubini. Take W, W ′ ∈ En , and let θ, θ′ be differentiability points for the corresponding pathwise value functions. On En , the empirical closed/right graph relations imply the population relaxed graph relations with tolerance δn , as in (3.19). Also, ∥m b W − m0 ∥∞ ≤ δn and ∥m b W ′ − m0 ∥∞ ≤ δn , so the two empirical mass vectors are within 2δn of each other. Together with (A.31), these are exactly the operative hypotheses needed for Proposition 3.6: feasibility, projected normality, relaxed closed/right graph relations, closeness of m, right-hand-side closeness, and containment of swept active intervals in the active supports. Applying Proposition 3.6 with ε = δn and τ = C/n gives a sum bound over all types. Since every summand is nonnegative, the current type k satisfies (z) (z) (z) (z) (A.32) ℓk qk,θ,W , qk,θ′ ,W ′ µk Ika qk,θ,W , qk,θ′ ,W ′ ≤ r̄s . (z)
(z)
Let Ω = (Θ, W ), where Θ ∼ Unif[0, 1] is independent of W , and set QΩ := qk,Θ,W . The marginal-to-cutoff reduction, Lemma 3.3, gives (z)
(z)
EW [Hk,z (YW )] − Hk,z (EW [YW ]) ≤ EΩ Hk,z (QΩ ) − Hk,z (EΩ QΩ ).
(A.33)
(z)
We now condition on the good future event G := En (W ). Since QΩ ∈ [0, y], and Hk,z is uniformly bounded and uniformly Lipschitz on [0, y], (3.26) gives (z) (z) (z) (z) EHk,z (QΩ ) − Hk,z (EQΩ ) − E[Hk,z (QΩ ) | G] − Hk,z (E[QΩ | G]) (A.34) ≤ CP(Gc ) ≤ Cn−6 . For each good future W , let DW,z ⊆ [0, 1] be the full-measure set of differentiability points, (z) and let QG,z be the essential range of the cutoff qk,Θ,W under the conditional law of (Θ, W ) given (z)
G—the smallest closed subset of [0, y] that QΩ enters with conditional probability one. After (z) (z) changing QΩ on a null set, QΩ | G takes values in QG,z . Each point of QG,z is a limit of cutoffs (z) qk,θ,W with W ∈ En and θ ∈ DW,z ; since (A.32) caps every pair of such cutoffs, and both ℓk and 49
the atomless measure µk vary continuously under convergence of interval endpoints, the cap passes to the limit. Hence every pair q, q̄ ∈ QG,z satisfies ℓk (q, q̄) µk (Ika (q, q̄)) ≤ r̄s .
(A.35)
Let Jz be the closed active hull of QG,z in Sk , namely Jz :=
[
[q ∧ q̄, q ∨ q̄] ∩ Sk .
q,q̄∈QG,z
If Jz has zero active length, then the good cutoff distribution straddles no curvature of Hk,z , and the good-support Jensen gap is zero. We therefore assume below that Jz has positive active length. By Lemma A.1, applied with B = Sk and ν = µk , the pairwise cap (A.35) extends to the closed active hull: Leb(Jz ) µk (Jz ) ≤ r̄s . (A.36) Because r̄s ≤ rH , (A.28) and (A.29) imply that Jz is contained in a single member of the finite active cover. Otherwise the Lebesgue-number property would force Leb(Jz ) ≥ λch , contradicting (A.36). We next choose this cover element measurably. Write the finite active cover for type k as Uk = {Uk,1 , . . . , Uk,Nk }. Using the jointly measurable cutoff representatives, define (z)
(z)
Lz := ess inf Πk (qk,θ,W ),
Rz := ess sup Πk (qk,θ,W ).
(θ,W )∈G
(θ,W )∈G
Because QG,z is the essential range, its projected infimum and supremum are Lz and Rz , so Jz = [Lz , Rz ] ∩ Sk . Since each Uk,i is an interval neighborhood, the event {Jz ⊂ Uk,i } is measurable in z. The first-index rule ik (z) := min{i : Jz ⊂ Uk,i } is therefore measurable on the set where Jz has positive active length. On the zero-active-length set, set ik (z) = 0. This decomposes the size space into measurable sets Ak,i := {z : ik (z) = i}, i = 1, . . . , Nk , plus a zero-contribution set Ak,0 . On each Ak,i , all good active hulls lie in the fixed cover element Uk,i . We now bound the good-support Jensen contribution on each cover element. Dominated neighborhoods. Suppose that Jz ⊂ U , where U is dominated. Every active interval generated by two good cutoffs lies in Jz ⊂ U . Hence the local domination assumption gives Λk,z (Ika (q, q̄)) ≤ Cµk (Ika (q, q̄)) for Pkβ -a.e. z and all q, q̄ ∈ QG,z . Combining this with (A.35), we get ℓk (q, q̄) Λk,z (Ika (q, q̄)) ≤ C r̄s , q, q̄ ∈ QG,z . We verify the measure hypotheses needed R for Lemma 3.5. The measure µk is atomless, because µk ({t}) ≤ C Leb({t} ∩ Sk ) = 0. Also, πk Λk,z ([0, y] \ Sk ) Pkβ ( dz) = µk ([0, y] \ Sk ) = 0, so Λk,z is supported on Sk for Pkβ -a.e. z. Since Jz ⊂ U , only curvature inside U can contribute to the U whose good-support Jensen gap. We may therefore replace Hk,z by a convex representative Hk,z curvature measure is Λk,z |U . This restricted measure is finite, because z ≤ β k , and atomless by local domination. U , µ = Λ | , and Q = Q Lemma 3.5, applied conditionally on G with h = Hk,z G,z , yields h k,z U (z)
(z)
E[Hk,z (QΩ ) | G] − Hk,z (E[QΩ | G]) ≤ C r̄s ≤ C r̄s log(e/r̄s ). U equals that of H , because the gap kernel vanishes outside the projected The Jensen gap of Hk,z k,z hull Jz : outside Jz , all good cutoffs lie on one side of the curvature point, as in the proof of Lemma 3.4.
50
Endpoint-contact neighborhoods. Now suppose that U = Uk,i is an endpoint-contact cover element, with assigned size set Ak,i . For a size z and a curvature measure Λ, define the goodsupport Jensen functional, after subtracting affine parts, by Z n (z) + o (z) + ∆U (Λ) := 1{z ∈ A } E (Q − t) | G − E[Q | G] − t Λ( dt). k,i z,i Ω Ω U
The integrand is nonnegative and independent of Λ, so Λ 7→ ∆U z,i (Λ) is a nonnegative curvatureβ U D U br linear functional. The kernel split (2.4) gives ∆U z,i (Λk,z |U ) = ∆z,i (Λk,z ) + ∆z,i (Λk,z ) for Pk -a.e. z. The dominated component is handled exactly as in the dominated-neighborhood case, using ΛD k,z (I) ≤ Cµk (I) from (2.6). Its good-support contribution is therefore at most C r̄s , and hence at most C r̄s log(e/r̄s ). It remains to control the contact branch after averaging over size. By Lemma A.5, applied to the functional ∆U z,i , the branch contribution is bounded, up to a primitive constant, by
Z ω0 0
br ∆U βk (ω),i Λk,ω f (ω) dω.
(A.37)
Use the local endpoint coordinate ζ, oriented into the support as in Lemma A.6. This affine change of variables has slope 1 or −1, so it preserves lengths and Jensen gaps after the branch surplus is written in local coordinates. If the current item is infeasible, or if the good local cutoff set is empty, set Iω = ∅ and dω = 0, and define the branchwise contribution to be zero. Otherwise, for z = βk (ω), define n o (βk (ω)) Qω := ζ qk,θ,W : W ∈ En , θ ∈ DW,βk (ω) . Let Iω be the closed active hull of Qω inside the moving branch support Bω = [e(ω), x0 ], and set dω := Leb(Iω ). For two local cutoffs q, q̄ ∈ Qω , write I ω (q, q̄) := [q ∧ q̄, q ∨ q̄] ∩ Bω . If q̃ = ζ −1 (q) and q̄˜ = ζ −1 (q̄), then the local coordinate map preserves active lengths and sends I ω (q, q̄) into the original active interval Ika (q̃, q̄˜). Hence ω a ˜ ˜ Leb(I ω (q, q̄)) µbr k (I (q, q̄)) ≤ ℓk (q̃, q̄ ) µk (Ik (q̃, q̄ )) ≤ r̄s .
Since Lemma A.6 implies that µbr k is atomless, Lemma A.1 extends this pairwise cap to the branch active hull: dω µbr for a.e. ω. (A.38) k (Iω ) ≤ r̄s The passage from Pkβ -a.e. size z to a.e. branch coordinate ω uses the injectivity of βk (ω) and the lower Jacobian bound in Definition 2.2. The branch contribution (A.37) is estimated through Lemma 3.4, whose geometric factor 1 + y/|J| is governed by the length of the ambient interval J. The branch support Bω = [e(ω), x0 ] has length x0 − e(ω), which may be arbitrarily small, so we split the branch coordinates according to ΩL = {ω : e(ω) ≤ x0 /2},
ΩT = {ω : e(ω) > x0 /2},
and bound the two contributions separately. Fix first a feasible coordinate ω ∈ ΩL with Qω ̸= ∅ and βk (ω) ∈ Ak,i . The branchwise goodsupport Jensen gap is the Jensen gap of the branch surplus, whose curvature measure Λbr k,ω is
51
atomless and supported on Bω . Because |Bω | = x0 − e(ω) ≥ x0 /2, the factor 1 + y/|Bω | is at most 1 + 2y/x0 , and Lemma 3.4, applied with J = Bω , ν = Λbr k,ω , and ambient length at most y, gives br br ∆U βk (ω),i Λk,ω ≤ C dω Λk,ω (Iω ).
(A.39)
Since r̄s ≤ rH , the cap (A.38) lies in the range of Lemma A.7. Applying that lemma, and bounding the integrand over ΩL by (A.39) and elsewhere by its nonnegativity, we obtain Z Z ω0 br ∆U Λ f (ω) dω ≤ C dω Λbr (A.40) k,ω k,ω (Iω ) f (ω) dω ≤ C r̄s log(e/r̄s ). βk (ω),i ΩL
0
Fix next a feasible coordinate ω ∈ ΩT , so that e(ω) > x0 /2 and Bω ⊆ [x0 /2, x0 ] is bounded away from the contact point; on this region the conditional curvature is dominated by µk , and the branch is treated as a dominated neighborhood. Since γ ≥ 1, the branch density satisfies γ−1 ≤ C for x ∈ B , so λbr ω k,ω (x) ≤ C(x − e(ω)) br Λbr k,ω (I) = Λk,ω (I ∩ Bω ) ≤ C Leb(I ∩ Bω )
for every interval I.
θ−1 , which is bounded below By Lemma A.6, the branch marginal µbr k has density comparable to x by a positive constant on [x0 /2, x0 ]; since µk ≥ µbr k and Bω ⊆ [x0 /2, x0 ],
µk (I) ≥ µbr k (I ∩ Bω ) ≥ c Leb(I ∩ Bω )
for every interval I.
Combining the two estimates, a a Λbr k,ω Ik (q, q̄) ≤ C µk Ik (q, q̄)
for all q, q̄ ∈ QG,z ,
which is the domination hypothesis of the dominated-neighborhood case. Hence, exactly as for the dominated component above, the pairwise cap (A.35) and Lemma 3.5, applied on the full active U br support Sk with curvature measure µh = Λbr k,ω , give ∆βk (ω),i (Λk,ω ) ≤ C r̄s ; the factor 1 + y/|Sk | from that lemma is bounded, and the interval [x0 /2, x0 ] enters only through the density domination just established. Because f is integrable, Z ω0 Z U br f (ω) dω ≤ C r̄s . (A.41) ∆βk (ω),i Λk,ω f (ω) dω ≤ C r̄s ΩT
0
Adding (A.40) and (A.41), and using r̄s ≤ 1 in the latter, the branch part of (A.37) is at most C r̄s log(e/r̄s ). Adding the dominated component gives the same bound for endpoint-contact neighborhoods. We have now bounded the good-support contribution on every measurable set Ak,i . Summing over the finite cover and over the finitely many types absorbs only primitive constants, so the total good-support contribution to Ξs (b) is at most C r̄s log(e/r̄s ). Using the cutoff reduction (A.33) and the conditioning estimate (A.34), we get Ξs (b) ≤ C r̄s log(e/r̄s ) + Cn−6 . Finally, (A.27) and r̄s , rs ∈ (0, 1) imply r̄s log(e/r̄s ) ≤ Crs log(e/rs ). After increasing s0 , we also have n−6 ≤ Crs log(e/rs ) for all s ≥ s0 . Hence Ξs (b) ≤ Crs log(e/rs ), as claimed.
52
B
Regularity verification and the regret corollaries
This appendix verifies Assumption 1 for the structured distribution classes in Section 2.3 and then proves the regret corollaries. In these classes, endpoint behavior is determined by two primitive mechanisms: the mass of the ratio distribution itself, and the way conditional ratio supports recede as the size approaches a boundary. The propositions below compute a per-type exponent pk for each type k. The global exponent used in Theorem 2.5 is p = maxk pk . Proposition B.1 (Independent size and ratio). Fix a type k. Suppose that, conditional on J = k, the size β and the ratio R = V /β are independent, that β ∈ [β k , β k ], and that R has single-interval support [rk− , rk+ ]. Suppose also that R is regular in the interior—c|I| ≤ P(R ∈ I | J = k) ≤ C|I| for every compact interval I in the interior of the support—and that, at each endpoint r, its distribution satisfies the one-sided interval bound c|I|θk,r ≤ P(R ∈ I | J = k) ≤ C|I| for some θk,r ≥ 1 and every interval I in a one-sided endpoint neighborhood, with endpoint intervals having mass of order xθk,r . Then the type-k distribution satisfies Assumption 1. Its local endpoint exponents are pk,r = θk,r , and its active mass condition holds with per-type exponent pk = max{1, θk,r− , θk,r+ }. k
k
Proof. For every interval I, µk (I) = πk E[β | J = k] P(R ∈ I | J = k). Thus µk has exactly the same local endpoint exponents and interval bounds as the ratio distribution. Cover the compact support Sk by the two endpoint neighborhoods and finitely many interior neighborhoods, taken relatively open in Sk and overlapping, and let λ0 be a Lebesgue number of this cover. These local bounds patch to (2.7) with exponent pk = max{1, θk,r− , θk,r+ }. The upper bound k k follows by summing the local upper bounds. For the lower bound, if ℓk (I) ≤ λ0 , then the active part of I lies in one cover element, so the corresponding local lower bound applies. If ℓk (I) > λ0 , then I ∩ Sk contains an active subinterval of length λ0 , and hence µk (I) ≥ cλp0k ≥ c′ ℓk (I)pk , since ℓk (I) ≤ |Sk |. Independence gives, for almost every z, Λk,z (I) = z P(R ∈ I | J = k) ≤
βk µk (I). πk E[β | J = k]
Interior regularity of R gives dominated neighborhoods away from the endpoints. At each endpoint, the displayed domination gives a dominated one-sided neighborhood. Therefore the finite local cover in Assumption 1 is fully dominated. Proposition B.2 (Independent value and size). Fix a type k. Suppose that, conditional on J = k, the reward V and the size β are independent and have compact interval supports bounded away from zero. Suppose that their densities are locally bounded above and below in the interiors, that the density of V is bounded above on its support, and that both densities are comparable near each endpoint to a power of the distance to that endpoint. Then the type-k distribution satisfies ± Assumption 1. If a± V and aβ denote the endpoint exponents of the distributions of V and β, then the local endpoint exponents of µk are + pk,r− = a− V + aβ ,
− pk,r+ = a+ V + aβ .
k
k
The active mass condition holds with per-type exponent + + − pk = max{a− V + aβ , aV + aβ }.
53
Proof. Write the supports of V and β as [v − , v + ] and [β k , β k ], with v − > 0. The ratio support is # − v+ v . [rk− , rk+ ] = , βk βk "
Let fV and fβ be the conditional densities. The weighted ratio measure has density Z βk mk (r) = πk
z 2 fβ (z)fV (rz)1{v − ≤ rz ≤ v + } dz.
βk
Since fV is bounded above and fβ is integrable, mk is bounded above. Hence the upper inequality in (2.7) holds locally, and then globally after compact patching. Now let r be an interior point of [rk− , rk+ ]. Then there is z0 ∈ (β k , β k ) such that rz0 ∈ (v − , v + ). On small neighborhoods of z0 and r, both densities are bounded below, so mk is bounded below. Thus µk (I) ≍ |I| locally at every interior point. Moreover, on each such local neighborhood, Λk,z (I) = z P(V /z ∈ I | J = k) ≤ C|I| ≤ Cµk (I), so the interior neighborhoods are dominated. It remains to verify the endpoint neighborhoods. Since V and β are independent conditional on J = k, the conditional curvature for a fixed size z is Λk,z ( dr) = z P(V /z ∈ dr | J = k) = z 2 fV (zr) 1{v − ≤ zr ≤ v + } dr. Thus the kernel measure in Definition 2.3 has product density Mk ( dz, dr) = πk fβ (z) z 2 fV (zr) 1{v − ≤ zr ≤ v + } dz dr.
(B.1)
We use the endpoint power comparisons −
fV (v − + s) ≍ saV −1 ,
+
fV (v + − s) ≍ saV −1 ,
−
fβ (β k + s) ≍ saβ −1 ,
+
fβ (β k − s) ≍ saβ −1 .
+ The bounded-above assumption on fV implies a− V , aV ≥ 1; otherwise the corresponding endpoint density would blow up. Therefore the branch curvature exponents below satisfy the requirement γ ≥ 1 in Definition 2.2. The endpoint exponents of β may be any positive numbers, and they enter through the size-coordinate exponent α. Lower endpoint. The lower ratio endpoint is rk− = v − /β k . Use the local coordinates ω = β k − z and x = r − rk− , so that z = β k − ω. The conditional lower edge of the ratio support recedes from rk− by v− v− e(ω) = − ≍ ω. βk − ω βk
For r = rk− + x, we have zr = (β k − ω)(rk− + x) = v − + (β k − ω) x − e(ω) . Hence, on a sufficiently small lower endpoint neighborhood, the branch curvature is 2 − Λbr k,ω ( dx) = (β k − ω) fV v + (β k − ω)(x − e(ω)) 1{x ≥ e(ω)} dx. −
Its density is comparable to (x − e(ω))aV −1 . 54
Substituting z = β k − ω and r = rk− + x in (B.1) gives the exact local disintegration Z Z Z ω0 πk fβ (β k − ω) g(β k − ω, rk− + x)Λbr g(z, r) Mk ( dz, dr) = k,ω ( dx) dω. 0
+
This is the branch identity (2.3) with βk (ω) = β k −ω, w ≡ 1, and f (ω) = πk fβ (β k −ω) ≍ ω aβ −1 . Fix the neighborhood width by x0 = e(ω0 ); since e is increasing, e(ω) > x0 for ω > ω0 , so Λk,z |U = 0 for every size z ≤ β k − ω0 . The disintegration over ω ∈ (0, ω0 ) therefore captures all of Mk on Bk × U , and the whole lower endpoint kernel is one branch with no dominated remainder, so ΛD k,z = 0 and br Λk,z = Λk,z |U . Therefore the lower endpoint has an endpoint-contact representation with γ = a− V,
α = a+ β,
τ = 1,
+ pk,r− = a− V + aβ . k
Lemma A.6 gives the lower endpoint mass order. Together with the dominated interior cover and the global upper density bound, this verifies (2.7) near rk− . Upper endpoint. The upper ratio endpoint is rk+ = v + /β k . Use the local coordinates ω = z − β k and x = rk+ − r. The conditional upper edge v + /(β k + ω) recedes from rk+ by e(ω) ≍ ω. For r = rk+ − x, zr = (β k + ω)(rk+ − x) = v + − (β k + ω) x − e(ω) . The same computation, again with x0 = e(ω0 ), applied to (B.1) yields a single branch with no + dominated remainder. Its branch curvature density is comparable to (x − e(ω))aV −1 , and its size − density is f (ω) = πk fβ (β k + ω) ≍ ω aβ −1 . Thus the upper endpoint has an endpoint-contact representation with γ = a+ V,
α = a− β,
τ = 1,
− pk,r+ = a+ V + aβ . k
Patching the two endpoint neighborhoods with the dominated interior neighborhoods, all taken + + − relatively open in Sk and overlapping, gives (2.7) with exponent max{a− V + aβ , aV + aβ }, by the same finite-cover argument used in Proposition B.1. We now prove the regret corollaries. By Theorem 2.5, it suffices in each case to verify Assumption 1 and identify the active weighted-mass exponent p. Proof of Corollary 2.6. A density bounded above and below gives the active mass condition with p = 1, and Proposition B.1 gives a fully dominated cover. The result is the p = 1 case of Theorem 2.5. Proof of Corollary 2.7. By Proposition B.1, the active mass exponent is p = θ, and the finite cover is dominated. Substituting this exponent into Theorem 2.5 gives the bound. Proof of Corollary 2.8. Densities bounded above and below have endpoint exponent 1. Therefore Proposition B.2 verifies the active mass condition with p = 2. The result is Theorem 2.5 at p = 2, for which the logarithmic exponent is (p+1)/(2p)+1 = 7/4. Uniform, truncated normal, and truncated exponential distributions on compact intervals bounded away from zero are instances. + Proof of Corollary 2.9. The uniform value distribution has endpoint exponents a− V = aV = 1. The affine Beta(ak , bk ) distribution has endpoint exponent ak at β k and bk at β k . By Proposition B.2, the weighted ratio measure has endpoint exponents 1 + bk and 1 + ak . Hence the active mass exponent is p = 1 + maxk {ak , bk } = 1 + q. Substituting this exponent into Theorem 2.5 gives the bound.
55
B.1
Fluid duals in three one-resource examples
This subsection compares three one-resource examples. Each has one request type, horizon-T capacity bT = cT , scalar size β, reward V , and ratio R = V /β. The fluid relaxation is max 0≤x(V,β)≤1
E[V x(V, β)]
s.t.
E[βx(V, β)] ≤ c.
Its Lagrange dual is min D(λ), λ≥0
D(λ) := cλ + E[(V − λβ)+ ].
Equivalently, since V = βR, we have D(λ) = cλ + E[β(R − λ)+ ]. The optimal fluid policy accepts requests whose ratio R exceeds an optimal dual price λ, with arbitrary tie-breaking at R = λ. The examples below show that dual degeneracy and the mass exponent p are distinct phenomena. Independent V, β ∼ U [0, 1] and 0 < c < 1/2. Let V and β be independent and uniformly distributed on [0, 1]. Take 0 < c < E[β] = 1/2, so the fluid relaxation cannot accept all requests. The dual objective is D(λ) = cλ + E[(V − λβ)+ ]. For 0 < λ < ∞, its derivative, at points of differentiability, is D′ (λ) = c − E[β 1{V > λβ}]. An optimal dual price λ∗ therefore satisfies E[β 1{V /β > λ∗ }] = c. The left-hand side is continuous and strictly decreasing on the relevant range. For 0 ≤ λ ≤ 1, Z 1 1 λ E[β 1{V > λβ}] = b(1 − λb) db = − . 2 3 0 Thus the solution is λ∗ = 3(1/2 − c) whenever c ∈ [1/6, 1/2]. For c < 1/6, the solution lies above 1, and the same strict monotonicity gives a unique solution. Hence the fluid dual price is unique for every 0 < c < 1/2. This is the classical nondegenerate stochastic knapsack case. The cutoff is pinned down by the capacity equation: the optimal policy rejects a positive fraction of low-ratio requests and accepts a positive fraction of high-ratio requests. Under the usual regularity condition, the regret is logarithmic (Lueker, 1998). (Because the size can be arbitrarily close to 0, this instance lies outside the standing assumptions of Section 2; we include it only for the dual comparison.) Independent V, β ∼ U [1, 2] and c = 3/2. Let V and β be independent and uniformly distributed on [1, 2], and set c = E[β] = 3/2. Since V > 0 almost surely, the accept-all solution x ≡ 1 is optimal whenever it is feasible. It is feasible here because E[β] = c. Thus the fluid relaxation accepts all requests. The dual objective is D(λ) = (3/2)λ + E[(V − λβ)+ ]. If 0 ≤ λ ≤ 1/2, then V − λβ ≥ 0 for all (V, β) ∈ [1, 2]2 . Hence 3 3 D(λ) = λ + E[V − λβ] = E[V ] + λ(c − E[β]) = . 2 2 Thus every λ ∈ [0, 1/2] is dual optimal, since D(λ) ≥ E[V ] by weak duality while the accept-all primal solution already attains value E[V ] = 3/2. For λ > 1/2, on the other hand, D′ (λ) = 56
3/2 − E[β 1{R > λ}] > 0 because P(R < λ) > 0; so D is strictly increasing beyond 1/2, and the dual optimal set is exactly Λ∗ = [0, 1/2]. The fluid dual is not unique. In this example, the active cutoff is at the lower edge of the ratio support. The ratio R = V /β reaches its minimum 1/2 only at the corner (V, β) = (1, 2). Consequently, the size-weighted ratio mass near the active cutoff is thinner than linear. Indeed, for small ε > 0, V E β1 ∈ [1/2, 1/2 + ε] ≍ ε2 . β Thus this example has p = 2. It is dual degenerate and belongs to the polynomial regime; it is the instance of Corollary 2.8. Independent β ∼ U [1, 2], R ∼ U [1/2, 2], and c = 3/2. Finally, let β ∼ U [1, 2], let R ∼ U [1/2, 2], assume independence, and set V = βR. Again take c = E[β] = 3/2. Since R > 0, the accept-all solution is optimal and feasible. The dual objective is 3 3 λ + E[(R − λ)+ ] , D(λ) = λ + E[β(R − λ)+ ] = 2 2 where the last equality uses independence and E[β] = 3/2. If 0 ≤ λ ≤ 1/2, then R − λ ≥ 0 almost surely, and therefore 5 λ + E[(R − λ)+ ] = λ + E[R − λ] = E[R] = . 4 Thus D(λ) = 15/8 for all λ ∈ [0, 1/2]. For λ ∈ [1/2, 2], Z 2 1 (2 − λ)2 + E[(R − λ) ] = (r − λ) dr = . 2 − 1/2 λ 3 Hence λ + E[(R − λ)+ ] = λ + (2 − λ)2 /3, whose derivative is (2λ − 1)/3. This derivative is nonnegative on [1/2, 2] and strictly positive for λ > 1/2. For λ > 2, the positive-part term vanishes and D(λ) = (3/2)λ. Therefore the dual optimal set is again Λ∗ = [0, 1/2]. The fluid dual is not unique. This example is dual degenerate, but it is not in the polynomial regime. For a Borel set B ⊂ [1/2, 2], the size-weighted ratio measure is 3 µ(B) = E[β 1{R ∈ B}] = E[β]P(R ∈ B) = P(R ∈ B), 2 by independence. Since R has a density bounded above and below on [1/2, 2], we have µ([1/2, 1/2+ ε]) ≍ ε. Thus p = 1. The instance is dual degenerate, but the size-weighted ratio mass near the active cutoff is linear, so it belongs to the logarithmic-type regime; it is the instance of Corollary 2.6. These three examples separate the roles of dual degeneracy and cutoff mass. The [0, 1]-uniform example has a unique dual price. The two accept-all examples are dual degenerate. Among them, independent V, β ∼ U [1, 2] has thin cutoff mass and p = 2, while independent β ∼ U [1, 2] and R ∼ U [1/2, 2] has linear cutoff mass and p = 1. Thus the polynomial regret mechanism is not dual degeneracy alone; it is dual degeneracy together with insufficient size-weighted ratio mass near the active cutoff.
57