PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhaohua Chen

arXiv:2610.09577v1cs.LG

TL;DR

The paper studies online resource allocation where actions control a Markov state affecting future rewards and resource use. It develops fluid-LP benchmarks and re-solving policies, reporting constant regret under nondegeneracy in the known-prior setting and showing that re-solving frequency matters. For unknown priors, it proposes UIR-UP and identifies knowledge of the optimal target state class as a boundary for sublinear regret.

  • Problem

    Classical online resource allocation does not capture settings where actions change a state that affects later rewards and resource consumption.

    Source: §1 · p. 2

  • Method

    The paper extends fluid-LP benchmarking to a controlled Markov state and proposes a three-phase, U-shaped infrequent re-solving policy for unknown request priors.

    Source: §1 · p. 2, §1.1 · pp. 3, 5

  • Results

    Under a unique nondegenerate optimum and an irreducible optimal induced kernel, both known-prior re-solving algorithms achieve O(1) regret; performance improves as re-solving probability decreases in the nondegenerate experiments.

    Source: §1.1 · p. 6, §8 · p. 28

  • Takeaways & Limitations

    The comparison between frequent and infrequent re-solving can reverse in the Markov-state setting, and infrequent re-solving can use O(log log T) LP solves.

    Source: §1.1 · p. 5

    Without the optimal target state class, sublinear regret is impossible when the class depends on the unknown prior and entry is irreversible before enough requests are observed.

    Source: §6.3 · p. 21

Abstract

from arXiv · show

We study finite-horizon online resource allocation with i.i.d. requests and an endogenous Markov state on a finite state space: each action affects the transition of the state that governs future rewards and resource consumption. In this problem, a transient fluid LP benchmark upper bounds the expected reward of every nonanticipating policy, while a stationary LP supplies randomized state-dependent controls. We assume that the stationary LP has a unique optimum and identify primal nondegeneracy and irreducibility of the optimal induced kernel as important regularity conditions in this framework. With a known request prior, we show that, under nondegeneracy and irreducibility, both frequent and infrequent re-solving attain $O(1)$ regret. However, under a degenerate optimum, irreducibility yields the sharp worst-case $\Theta(\sqrt{T})$ rate for infrequent re-solving, while frequent re-solving can incur $\Omega(T)$ regret. Thus, more frequent optimization can perform asymptotically worse. With an unknown request prior, we develop a three-phase U-shaped infrequent re-solving policy that coordinates learning and inventory correction with $O(\log\log T)$ LP solves. When the optimal induced kernel is irreducible and the algorithm is given the optimal target state class and a constant-cost entrance policy, it attains $O(1)$ regret under nondegeneracy and $O(\sqrt{T})$ regret under degeneracy. Without the target-class information, linear minimax regret is unavoidable. Numerical experiments further illustrate the instability of round-by-round re-solving relative to epoch-wise infrequent re-solving, show that thresholding greatly mitigates its loss, and find that infrequent schemes remain dominant under both known and estimated priors.

1 Introduction

The paper extends online resource allocation to settings where actions shape a Markov state that affects later rewards and resource use. It develops fluid-LP benchmarks and re-solving policies, finding that less frequent optimization can outperform round-by-round re-solving in this setting.

1 Introduction

  • The model captures resource allocation in which actions affect a Markov state that in turn changes future rewards and resource consumption, as in the cluster-load and RAG examples.The stationary LP yields randomized state-dependent controls, while the transient fluid LP upper-bounds expected reward for every nonanticipating policy.Source: §1 · p. 2, §1.1 · p. 3

1.1 Main contributions

  • With a known request prior, both frequent and infrequent re-solving achieve O(1) regret under nondegeneracy, while under degeneracy infrequent re-solving has worst-case Θ(√T) regret and frequent re-solving Θ(T).The comparison can reverse the state-free pattern: maintaining a policy within an epoch preserves the sequence of decisions that can make an initial action worthwhile.Source: §1.1 · pp. 4–5
  • For unknown request priors, UIR-UP uses three phases and O(log log T) LP re-solves; its regret is O(1) under nondegeneracy and O(√T) under degeneracy when the optimal target state class is known.The phases address early prior-estimate correction, learning versus inventory consumption, and increasingly frequent updates near the horizon’s end.Source: §1.1 · pp. 5–6
  • Without knowledge of the optimal target state class, linear regret is unavoidable in the unknown-prior setting.The lower bound uses request distributions with different optimal target classes that cannot be distinguished sufficiently early.Source: §1.1 · p. 6

1.2 Related work

  • The paper distinguishes its model from prior Markov-demand extensions because requests are i.i.d. and actions, rather than an exogenous chain, control the state affecting later outcomes.It also contrasts its single persistent controlled state and horizon scaling with prior large-system models of many parallel subproblems.Source: §1.2 · pp. 7–8

2 Model and benchmarks

The model allocates resources over rounds with a state-dependent reward and consumption process whose state transitions are action-controlled. A transient fluid LP upper-bounds policy value, while a stationary LP provides a more convenient benchmark and randomized control; a hindsight benchmark is unsuitable when state evolution depends on request order and actions.

2 Model and benchmarks

  • Each round observes the current state and an i.i.d. request, then selects an action yielding reward and resource consumption while inducing the next-state transition.The initial state is fixed, and a null action yields zero reward and consumes no resources.Source: §2 · pp. 8–9

2.1 The transient fluid LP upper bound

  • The transient fluid LP upper-bounds the expected value of every nonanticipating policy.Its variables track nonterminal state-request-action counts and terminal-round probabilities; terminal actions contribute reward without consuming fluid capacity.Source: §2.1 · pp. 9–10

2.2 The stationary LP

  • An optimal stationary-LP solution induces a randomized state-dependent policy, and the stationary value is within an additive constant of the transient benchmark.This makes the stationary LP a convenient proxy for the transient upper bound.Source: §2.2 · pp. 10–11

2.3 Why not the hindsight optimum?

  • A hindsight benchmark is unsuitable because request order and chosen actions affect state transitions, rewards, and resource consumption; incorporating this randomness can make the benchmark too strong.The cited result says this state-aware hindsight optimum can exceed the optimal nonanticipating value by Θ(T).Source: §2.3 · p. 12

3 Regularity assumptions

The analysis imposes uniqueness, primal nondegeneracy, and irreducibility of the optimal induced kernel. These conditions support local stability, while degeneracy makes entrance into the target state class a separate requirement.

3 Regularity assumptions

  • The stationary LP is assumed to have a unique, primal-nondegenerate optimum; together these conditions imply local stability around the nominal capacity vector.Near that vector, the optimal solution retains its binding-resource, active-state, and active-decision sets, and its coordinates are affine in binding capacities.Source: §3 · pp. 12–13
  • The optimal induced kernel must be irreducible on the optimal target state class, so every state in that class communicates under the optimal policy.Nearby capacity perturbations preserve irreducibility on the class, which remains closed under the perturbed kernel.Source: §3 · pp. 13–14
  • Under nondegeneracy, the optimal target state class is the entire state space, making entrance immediate from the fixed initial state.Under degeneracy, reachability of the target class is not automatic.Source: §3 · p. 14
  • For the degenerate case, the analysis separately assumes a fixed entrance policy that reaches the target class with finite expected time and constant expected resource cost.Entrance-augmented algorithms use this policy until the process first enters the class, unless the process stops first.Source: §3 · p. 14

4 Frequent and infrequent re-solving under regularity

Frequent and infrequent re-solving extend stationary-LP control to the Markov-state setting. Under the stated regularity assumptions, both attain constant regret, while infrequent re-solving schedules policy updates in epochs and requires only O(log log T) LP solves.

4 Frequent and infrequent re-solving under regularity

  • Frequent re-solving updates the stationary LP each round, whereas infrequent re-solving holds each selected policy fixed until its next scheduled update.Both operate after entry into the optimal target state class.Source: §4.1 · p. 15

4.1 Algorithms

  • Infrequent re-solving uses O(log log T) stationary-LP solves, with each epoch governed by the solution selected at its update.A deterministic selector makes the same LP input yield the same selected optimizer, though the resulting action policy may still randomize.Source: §4.1 · pp. 15–16

4.2 Performance under regularity

  • Under Assumptions 3.1, 3.2, and 3.4, both frequent and infrequent re-solving have constant regret.The guarantee applies for any fixed α ∈ (1/2, 1) for infrequent re-solving.Source: §4.2 · p. 16

5 Incomplete regularity

With a unique degenerate stationary-LP optimum, infrequent re-solving has sharp worst-case square-root regret, while frequent re-solving can incur linear regret. The section also shows that irreducibility of the optimal induced kernel is necessary for a universal sublinear-regret guarantee.

5.1 A unique degenerate optimum

  • A single-state lower bound from Bumpensanti and Wang (2020) applies because TG(ρ) equals the transient fluid LP in that setting.The passage relates this result to the lower-bound analysis for the degenerate optimum.Source: §5.1 · p. 17
  • IR achieves O(sqrt T) regret under the stated assumptions, and the matching lower bound makes its worst-case rate Θ(sqrt T).The IR guarantee requires irreducibility of the optimal induced kernel and a constant-cost entrance policy.Source: §5.1 · p. 17
  • FR can incur Ω(T) regret when the stationary LP has a unique but degenerate optimum.The cited construction has one resource and one request type and satisfies Assumptions 3.4 and 3.7.Source: §5.1 · p. 17

5.2 Failure of irreducibility of the optimal induced kernel

  • Irreducibility is necessary for any algorithm to have a universal sublinear-regret guarantee when the optimal induced kernel is reducible.In that case, realized state-action frequencies may fail to match the stationary optimum, or states in the optimal target class may be unreachable.Source: §5.2 · p. 18

6 Unknown request prior

When the request prior is unknown, estimation error affects control through the fluid LP, and degeneracy can make small perturbations change the selected action support. The section presents UIR-UP and shows that knowing the optimal target state class is necessary for sublinear regret.

6 Unknown request prior

  • Unknown-prior estimation matters because the empirical prior enters the fluid LP, and under degeneracy a small perturbation can change the selected action support.The algorithm first uses an entrance policy and then forms a Laplace-smoothed request estimate from observations since entrance.Source: §6 · p. 18, §6.1 · p. 19

6.2 U-shaped infrequent re-solving

  • With the optimal target state class and an entrance policy supplied, UIR-UP uses O(log log T) LP solves and achieves O(1) regret under nondegeneracy and O(√T) under uniqueness alone.The policy’s guarantees also require an irreducible optimal induced kernel and a constant-cost entrance policy.Source: §6 · p. 18, §6.2 · p. 20

6.1 Terminology and preliminaries

  • The algorithm assumes the optimal target state class is known and uses safe actions that keep the process inside that class without knowing the request prior.The projected policy is designed to operate entirely within the supplied class.Source: §6.1 · pp. 18–19

6.3 Unknown optimal target state class R∗: a linear information-theoretic regret lower bound

  • If the optimal target state class is unknown, even sublinear regret is impossible when it depends on the prior and entry must occur before enough requests are observed.The lower-bound instances have unique degenerate optima, irreducible optimal induced kernels, and one-round entrance policies.Source: §6 · p. 18, §6.3 · p. 21

7 Numerical experiments

The experiments compare frequent, infrequent, and thresholded re-solving across known- and unknown-prior settings, including capacity ratios around the degeneracy boundary. Lower re-solving frequency generally improves frequent policies, but infrequent schedules perform better in the reported comparisons.

7.1 Algorithms

  • For unknown-prior infrequent methods, the sparse learning schedule follows a rounded construction, while thresholding prunes small action probabilities and freezes controls within each epoch.Infrequent algorithms use α = 0.7; thresholding is disabled only for the final solve when one round remains.Source: §7.1 · pp. 22–23

7.2 Environment

  • The three-state, three-request, two-resource instance varies only ρ1 across regimes; trials report 95% t confidence intervals for mean regret.The setup includes a nondegenerate optimum at ρ1 = 0.995 and a unique degenerate optimum at ρ1 = 1.Source: §7.2 · pp. 23–24

7.3 Known request prior

  • At ρ1 = 1, FR mean regret rises from 233.852 at T = 500 to 15,285.072 at T = 32,000, while IR remains between 1.704 and 2.706.Thresholded FRT remains between 6.920 and 7.391; at ρ1 = 0.995, FR ranges from 75.185 to 107.435 while FRT remains between 6.136 and 6.982.Source: §7.3 · pp. 24–25, Figure 1 · p. 25

7 Numerical experiments

  • Thresholding keeps frequent-policy regret bounded across the reported sweeps, but infrequent re-solving retains lower regret in the degenerate known-prior comparison.Source: §7.3 · pp. 24–25, Figure 1 · p. 25

7.4 Unknown request prior

  • At ρ1 = 1, FR-UP reaches mean regret 15,266.652 at T = 32,000, while thresholded FRT-UP remains between 5.999 and 6.320 and both infrequent variants have zero empirical variance.At ρ1 = 0.995, FR-UP ranges from 75.704 to 102.245; at T = 32,000, UIR-UP has mean regret 1.947 and UIRT-UP 8.001.Source: §7.4 · pp. 25–26, Figure 2 · p. 26

7.5 Perturbing the capacity ratio across the degeneracy boundary

  • At T = 2000, known-prior FR regret jumps from 318.835 at ρ1 = 0.999 to 1,016.932 at 1, then drops to 1.000 at 1.001; FR-UP follows the same pattern.Thresholding attenuates the boundary spike, and infrequent-policy regret remains low for ρ1 ∈ [0.995, 1.005].Source: §7.5 · pp. 26–27, Figure 3 · p. 27

7.6 Lowering the re-solving frequency

  • At the nondegenerate point, lowering the re-solving probability improves sample-mean regret, but frequent variants remain worse than IR or UIR-UP; at degeneracy, their loss still grows on the horizon scale.At T = 32,000, known-prior regret is 2,540.116 for p = 0.2 versus 1.704 for IR; unknown-prior regret is 1,809.039 for p = 0.2 versus 1.000 for UIR-UP.Source: §7.6 · pp. 27–28, Figure 4 · p. 28

8 Conclusion

The paper extends online resource allocation to action-dependent Markov states and analyzes frequent and infrequent LP re-solving. Its conclusions distinguish regular and degenerate optima, and show that an unknown-prior infrequent schedule can achieve order-optimal regret under stated information and regularity conditions.

8 Conclusion

  • The proposed model makes the persistent state action-controlled, so transitions shape future rewards and resource use.Source: §8 · p. 28
  • With a unique primal-nondegenerate optimum and irreducible optimal induced kernel, frequent and infrequent re-solving achieve O(1) regret; under degeneracy, infrequent re-solving achieves O(√T) while frequent re-solving can incur Θ(T).Source: §8 · pp. 28–29
  • For unknown priors, a three-phase infrequent schedule solves the LP O(log log T) times and guarantees order-optimal regret under the stated regularity conditions.Source: §8 · pp. 28–29

A.1 Proof of Lemma 2.1

The appendix establishes the LP benchmark comparison and supports sensitivity results for the stationary LP solution. Its proofs connect policy-generated counts to transient-LP feasibility and use fixed-basis arguments for local parameter changes.

A.1 Proof of Lemma 2.1

  • Expected state-request-action and state-visit counts from any nonanticipating policy form a feasible transient-LP solution with the same objective, proving the benchmark upper bound.Source: §A.1 · p. 35

A.2 Proof of Lemma 2.2

  • Shifting the dual variables yields a feasible transient-LP dual solution, so weak duality proves the stationary-versus-transient benchmark comparison.Source: §A.2 · pp. 35–36

B.1 Proof of Proposition 3.3

  • Under uniqueness and nondegeneracy, nearby right-hand sides preserve the optimal LP basis, and state-decision coordinates are unaffected by capacities of resources outside the active set.Source: §B.1 · pp. 37–38

B.2 Proof of Proposition 3.5

The appendix proves local properties of the optimal induced kernel and establishes proof-only guarded comparisons for frequent and infrequent policies. These arguments support closure and regularity claims within a target state class.

B.2 Proof of Proposition 3.5

  • Locally induced kernels keep the optimal target class closed, vary Lipschitz-continuously with the capacity parameter, and preserve irreducibility within that class.Source: §B.2 · p. 38

B.3 Proof of Proposition 3.6

  • The nondegeneracy basis argument rules out a state with zero optimal mass, since its state-request equality would create an all-zero basis row.Source: §B.3 · pp. 38–39

C.1 Analytical setup

  • Guarded FR and IR comparisons terminate after specified locality, entrance, depletion, or horizon checks; upper bounds for guarded FR transfer to FR.The null-completion convention is essential to the frequent-re-solving lower-bound construction for a unique degenerate optimum.Source: §C.1 · pp. 40–41

C.2.1 The dual Bellman potential

This proof section develops Bellman-potential, Poisson-equation, and optimizer-continuity tools to analyze infrequent re-solving, including stability of its ratios and control of escapes from the target state class. It uses stopped-potential and stopping-control arguments to bound error terms, entrance errors, schedule length, and horizon and inventory exposure.

C.2.1 The dual Bellman potential

  • Under Assumption 3.7, entrance imbalance affects every performance bound by at most a constant, and the expectation of the right-hand side in Lemma C.2 is O(1).Source: §C.2.1 · p. 42

C.3 Common resource averages and Poisson equations

  • The centered Poisson equation has a unique solution, and its solutions are uniformly bounded and Lipschitz over the stated parameter neighborhood.The construction uses a nonsingular stationary-projector-adjusted matrix; the bounds hold across the full one-sided neighborhood, including inactive coordinates.Source: §C.3 · pp. 44–45

C.4.1 Time-varying martingale decomposition and exact ratio recursion

  • For regular frequent-re-solving rounds, the Poisson equation yields an exact ratio recursion with bounded martingale differences and keeps the next ratio in N2δ.The recursion also yields the stated lower bound βt+1,i > ρi − 2δ for every resource.Source: §C.4.1 · pp. 45–46

C.4.2 An exponential exit bound

  • Lemma C.6 establishes an exponential exit bound for frequent re-solving while the remaining horizon is at least h.Its martingale increments and accumulated quadratic variation are O(h^-1), with the accumulated remainder also controlled.Source: §C.4.2 · p. 47

C.4.3 Finishing the proof for frequent re-solving

  • Potential telescoping and an integrable bound on cutoff or exit costs finish the frequent-re-solving proof, and the resulting upper bound transfers from FRg to FR.The implemented FR policy dominates the stopped policy pathwise.Source: §C.4 · p. 45, §C.4.3 · pp. 48–49

C.5.1 Uniform concentration within a frozen epoch

  • Within a frozen epoch, the Poisson equation converts centered-cost deviations into martingale deviations, to which maximal Azuma–Hoeffding concentration applies.For deviations x ≥ 4V, the associated martingale deviation is at least x/2.Source: §C.5.1 · p. 50

C.5.2 Stability of infrequent resolving points

  • The infrequent-re-solving analysis uses a pre-action near-depletion check, which fires before actual depletion because one-period consumption is bounded.The entrance policy is not invoked when the stationary LP has a unique nondegenerate optimum; the guard-free IR policy inherits the stopped policy’s upper bounds.Source: §C.5 · p. 49, §C.5.2 · p. 50
  • If the initial resolving ratio lies in Nδ/4 and none of the epoch bad events occurs, every later resolving ratio remains in Nδ.On the complement of those events, binding coordinates move by at most dk per epoch, and the cumulative movement is bounded.Source: §C.5.2 · pp. 52–53

C.5.3 Finishing the proof for infrequent re-solving

  • The proof of infrequent re-solving telescopes reward-plus-potential increments up to truncation and bounds the resulting tail sum uniformly in T.Before the cutoff, the epoch lengths form a strictly decreasing sequence of distinct integers larger than the cutoff threshold.Source: §C.5.3 · pp. 53–54

D.1 Proof of Theorem 5.2

  • Theorem 5.2’s proof combines optimizer continuity, rare visits outside the target class, accumulated-gap control, and inventory-deviation propagation in a stopped dual-potential identity.Nominal uniqueness supplies a selector-uniform upper-Lipschitz estimate, while stationary domination controls visits outside the optimal target state class.Source: §D.1 · p. 55

D.1.1 Lipschitz continuity of optimizers

  • Every optimizer of a sufficiently nearby perturbed LP, and its induced policy on the optimal recurrent class, differs from the nominal solution by O(∆(β)), uniformly over optimizer selection.The proof establishes a nominal-problem-dependent Lipschitz bound even when the perturbed LP has multiple optimizers.Source: §D.1.1 · pp. 55, 58

D.1.2 Rare opportunity to escape the optimal target state class

  • Under a nearby frozen policy starting in the optimal target class, stationary domination bounds the probability of being outside that class at every time.The lemma’s result also bounds the sum of these outside-class probabilities.Source: §D.1.2 · p. 59

D.1.3 Bounding the accumulated gap

  • Lemma D.3 provides a maximal bound for accumulated one-period gaps under a frozen policy when the epoch starts in the optimal recurrent class.Its assumptions cover uniformly bounded, full-history measurable quantities such as current-round reward and resource consumption.Source: Set f · p. 59, §D.1.3 · p. 59

Set f

  • The accumulated-gap argument uses a bounded Poisson-equation corrector for the nominal chain to isolate a bounded-increment martingale.Doob’s square-integrable maximal inequality then bounds the martingale maximum.Source: Set f · p. 60
  • Both dual-potential error terms are O(∆(β)), and taking expectations with (D.10) and (D.13) establishes (D.12).Source: Set f · p. 60

D.1.4 Stopping control

  • A successful entrance leaves at least one round and a strictly positive amount of every resource, and the restarted schedule has at most a constant number of epochs depending only on α.Source: §D.1.4 · pp. 61–62
  • The stopping-control analysis bounds both the expected remaining horizon and the total binding-resource inventory at the analytical stop.Source: §D.1.4 · p. 62

D.1.5 Finishing the proof

The proof bounds accumulated dual slack and uses a stopped comparison to establish the stationary-benchmark gap.

D.1.5 Finishing the proof

  • The stopped comparison follows IR until analytical truncation, then takes null actions; IR dominates it pathwise because later rewards are nonnegative.A resource near-depletion check before each action ensures depletion cannot precede the analytical stop.Source: §D.1.5 · pp. 65–66
  • Complementary slackness makes the state and nominal-action slacks zero in the target class, while slacks outside it are bounded.The proof combines these cases into a pointwise bound on the slack.Source: §D.1.5 · p. 66
  • Conditional finite-horizon telescoping from entrance bounds the stopped comparison’s post-entry reward, using the terminal-potential estimate.The proof then combines the stopped comparison with entrance-event bounds to obtain the final estimates.Source: §D.1.5 · pp. 67–68
  • The passage states that T ≤ Φ_T(Tρ, s1) is used to obtain (14) and (15).Source: §D.1.5 · p. 68

D.2 Proof of Proposition 5.3

This proof constructs an example with a unique degenerate stationary optimum and an irreducible optimal induced kernel. Frequent re-solving can nevertheless lose linearly because it drops a recovery action after reaching a state assigned zero probability by the new optimizer.

D.2 Proof of Proposition 5.3

  • The nominal stationary optimum is unique but degenerate: three state-action masses are zero at d=0 and positive for every d>0.The proof uses this support change to establish degeneracy.Source: §D.2 · pp. 69–70
  • The optimal induced kernel is irreducible, though periodic, and the initial state already lies in the optimal target class.Thus the example satisfies both dynamic assumptions stated in the proof.Source: §D.2 · p. 70
  • After action e moves the process to C, the ratio-one optimizer assigns C zero stationary probability, so frequent re-solving selects the null action there forever.The action e is selected during a B-round; the null-action convention applies when the current state has zero probability under the selected solution.Source: §D.2 · p. 71
  • An excursion occurs with constant probability by round T/2, leaving at least T/2 rounds in the trap and producing linear regret for frequent re-solving.A comparison policy instead takes recovery action r and then resumes baseline actions, remaining admissible and earning more on the trapped suffix.Source: §D.2 · pp. 71–72
  • The harmful effect is not caused by a large capacity-ratio deviation; it is the newly solved optimizer's omission of a state reached under a nearby optimal policy.Holding decisions fixed within an epoch preserves the recovery sequence that made the initial action worthwhile.Source: §D.2 · pp. 72–73

D.3 Proof of Proposition 5.4

The proof gives a reducible-kernel example where both fluid benchmarks exceed achievable policy value by a linear amount. The unknown-prior analysis assumes access to the optimal target class and an entrance policy, and develops concentration and sparse-balanced scheduling results for its re-solving phase.

D.3 Proof of Proposition 5.4

  • In the two-state example, the optimal induced kernel is reducible, while the process starting in state 1 cannot earn more than 3/2 per round despite capacity sufficient for that reward.The stationary benchmark is 7T/4, and the proof constructs a transient-feasible solution with the same linear obstruction.Source: §D.3 · p. 74
  • The transient relaxation admits a source-free stationary circulation in an unreachable absorbing class because its state-flow constraints aggregate over time.This yields the transient-fluid inequality in the example as well as the stationary-benchmark inequality.Source: §D.3 · p. 74

E Analysis of the unknown request prior

  • The unknown-prior analysis assumes UIR-UP is given the true optimal target state class and a fixed entrance policy satisfying the entrance assumption.The proof conditions on the realized entrance history for its subsequent analysis.Source: E Analysis of the unknown request prior · p. 75

E.1.1 Estimation concentration

  • The estimator has concentration bounds with constants depending only on the number of request types.The proposition states these bounds conditional on any realized entrance history and for every integer sample count n≥1.Source: §E.1.1 · p. 75

E.1.2 Sparse-balanced scheduling

  • Sparse-balanced scheduling limits the phase-2 re-solves to O(log log T), balancing the accumulated statistical contribution of frozen empirical policies.Under degeneracy, the stated per-round first-order estimation error can make an epoch of length Λ contribute order Λ/√n after n observations.Source: §E.1.2 · p. 76

E.1.3 Local sensitivity with an estimated request prior

This section analyzes the stability of empirical LP solutions and projected policies under capacity and prior perturbations, and develops inventory-control and comparison bounds for stopped epochs across early and late phases. It also controls epoch-to-epoch movement and, under uniqueness and nondegeneracy, strengthens locality and depletion guarantees, yielding a horizon-uniform bound via a fixed cutoff.

E.1.3 Local sensitivity with an estimated request prior

  • Near the nominal parameters, every empirical LP optimum stays within O(∆) of the nominal optimum, and its core-projected action probabilities and induced kernel vary by O(∆).The result requires a sufficiently small joint perturbation; it also ensures uniformly positive state masses on the target class so the projection is well defined.Source: §E.1.3 · pp. 78, 80
  • Under Assumption 3.2, sufficiently small joint perturbations preserve the nominal LP basis, positive supports, unique optimality, and nominal-dual tightness; the restricted protective-phase LP has the same stability.The core projection is unchanged, and inactive resources retain uniformly positive slack.Source: §E.1.3 · pp. 80–81
  • Frozen core-projected epochs admit uniform deviation bounds under the true prior, using the nominal Poisson equation and bounded-increment martingale control.The local policy and true transition kernel differ from their nominal counterparts by O(∆), which bounds the residual term in the epoch analysis.Source: §E.1.3 · pp. 82–83

E.1.4 Inventory control for the universal upper bounds

  • The universal inventory analysis gives stopped square-root control through the midpoint, with locality and resource near-depletion checks stopping the comparison before an unsafe action.Nominal-dual loss is O(∆k) in local projected epochs and zero when basis stability applies; the entrance imbalance contributes O(1) after averaging over regular-entry histories.Source: §E.1.4 · pp. 84–85
  • Stopped-prefix accounting includes a final epoch interrupted by resource near-depletion and charges analytical stops and positive terminal potential in the reward comparison.The reward comparison uses nominal dual slacks to bound per-round loss in each epoch.Source: §E.1.4 · pp. 86–87
  • Lemma E.7 bounds event-weighted inventory deviations, remaining horizon after stops, and nominal-dual loss, including prefixes interrupted by resource near-depletion.Its late comparison uses epoch-wise deviation estimates and the scheduled block length to bound a possibly interrupted terminal epoch.Source: §E.1.4 · pp. 88–89
  • Under Assumptions 3.2 and 3.4, the sparse-balanced phase reaches the midpoint without resource near-depletion and satisfies the stated deviation guarantee except with probability O(T^-Q).The conclusion holds for every prescribed Q > 0 and all sufficiently large T.Source: §E.1.4 · pp. 90–91
  • Before the late comparison stops, every empirical LP remains in the nominal joint basis cell and its core projection is the identity.The late-failure checks and locality conditions are specified for each late epoch.Source: §E.1.4 · p. 93
  • Without an epoch failure, endpoint movement is at most d_k, later capacity ratios stay within the joint basis cell, and empirical error is checked again before the next epoch’s actions.Empirical concentration is used only in the unconditional term; conditioned on F_tk, the empirical error is treated as fixed.Source: §E.1.4 · p. 94
  • The resulting bound is uniform in T because the backward power schedule makes h_k grow faster than geometrically while the exponential factor decays super-polynomially.The final cutoff has bounded horizon; combining (E.33), (E.35), and (E.36) proves (E.34).Source: §E.1.4 · p. 94

E.1.5 Finishing the proof

The proof handles possibly degenerate and nondegenerate optima by comparing stopped policy processes after entrance into a suitable neighborhood. It controls entrance, protective-phase, and terminal-potential losses to establish the stated bounds for the guard-free policy.

Unique, possibly degenerate case

  • The possibly degenerate case charges entrance failure, irregular entry, and entrance-potential discrepancy at O(1) in expectation.After regular entry, inventory protects against near-depletion during the protective phase; bounded remaining horizons contribute O(1).Source: §E.1.5 · p. 95
  • Concatenated stopped comparisons bound accumulated local dual loss and positive terminal potential by O(·), then telescope the comparison from entrance to permanent stop.The supplied proof passage truncates the bound after O( and the subsequent square-root expression, so no complete rate is stated here.Source: §E.1.5 · p. 95

Unique, nondegenerate case

  • For the nondegenerate case, midpoint-success paths have O(1) expected positive terminal potential, including late failures and the cutoff.The first-half failure probability is O(T^-Q); with Q > 2, its expected terminal-potential contribution is O(1).Source: §E.1.5 · p. 95
  • On good protective, sparse, and late epochs, the nominal action support makes the local loss zero; warm-start and bad protective epochs contribute O(1) expected loss.The proof then uses finite-horizon telescoping to prove the stated result for the guard-free policy.Source: §E.1.5 · p. 95

E.2 Proof of Proposition 6.2

The proposition constructs two request priors whose optimal recurrent classes differ, while the first request does not reveal which prior governs. A policy that lacks that prior information therefore has a wrong-class probability bounded away from zero for at least one prior, yielding the stated transient-fluid-gap lower bound.

Proof of Proposition 6.2

  • At state 0, the first action commits the process to A or B; no action can keep it at 0 to collect more requests before that commitment.Both states are absorbing thereafter, and unspecified non-null actions there are dominated by the null action.Source: §E.2 · p. 96
  • Under the two priors, the unique stationary optima target different absorbing classes, A and B, despite each class’s optimal induced kernel being irreducible.Each prior also satisfies the stated entrance-policy assumption: its correct entrance action reaches the target singleton in one round at unit resource cost.Source: §E.2 · pp. 96–97
  • The nominal optimum is degenerate because an arbitrarily small capacity decrease forces positive null-action mass and changes the positive support.The productive action uses the resource at rate exactly one, while request balance requires total stationary state probability one.Source: §E.2 · p. 97
  • For every horizon and prior-ignorant policy, at least one of the two priors has wrong-class probability at least 1/4, and the maximum transient-fluid gap inherits the corresponding lower bound.The maximizing prior may depend on the horizon and policy.Source: §E.2 · pp. 97–98
  • With the correct prior, entering its target class in round one and then using productive actions is feasible at capacity ratio ρ = 1.The entrance consumes one unit, leaving T − 1 units for the remaining productive rounds.Source: §E.2 · pp. 96–97
Loading 2610.09577v1…