Resource-Adaptive Primal-Dual Learning for One-Warehouse Multi-Store Systems with Censored Demand

1. Introduction

• In finite-stock OWMS, allocations compete for shared inventory, so each sale reduces future resources; unknown demand distributions and censored feedback make learning while preserving inventory difficult.Even with known demand laws, the exact dynamic program is high dimensional and strongly state dependent.Source: §1 · pp. 1–2

1.1. Contributions

• RAPDL replaces a fixed initial-resource target with a remaining-inventory-per-period-indexed KKT target, using censored sales to update store allocations and their common scarcity price without estimating demand distributions or repeatedly solving a fluid program.The resource state re-centers the next target as the system evolves.Source: §1.1 · p. 2
• The analysis establishes O(log T) regret by bounding the re-solving path’s intrinsic gap, the learning gap, and the feasible-action implementation gap, improving on square-root-order guarantees.Expected-sales geometry and a moving-target argument control the learning gap.Source: §1.1 · p. 2
• RAPDL has lower mean total cost than the Double Binary Search policy of Bekci et al. (2023) in all 24 paired comparisons across homogeneous and heterogeneous experiments.The comparisons span different inventory regimes and provide short-horizon evidence.Source: §1.1 · p. 2

2. Problem Formulation

• The manager observes warehouse and store inventories and past sales, ships before demand, then observes only censored sales; unmet demand is lost.The warehouse starts with W = γT units and stores start empty.Source: §2 · p. 4
• Demand vectors are i.i.d. over time, store demands may be dependent within a period, and the policy does not know each complete marginal distribution Fi.Source: §2 · p. 4
• The objective accounts for shipment and store-holding costs, lost-sales penalties, terminal warehouse holding cost, and a sell-back credit for terminal store inventory.Source: §2 · p. 5
• The one-period fluid relaxation retains an expected-sales budget, lower-bounds the exact known-distribution dynamic benchmark, and its nonnegative gap upper-bounds the performance gap to that oracle.Source: §2 · pp. 5–6
• Regret is defined relative to the constrained fluid benchmark, whose optimizer y*(r) is unique and whose selected smallest resource multiplier is λ*(r).Source: §2 · p. 6

3. Resource-Adaptive Primal-Dual Learning

• Each sales observation supplies censored feedback and changes the next resource index, so RAPDL tracks a moving target (y*(r_t), λ*(r_t)) instead of the fixed target indexed by γ.The moving target consists of preferred thresholds and a common shadow price.Source: §3 · p. 6
• Each period projects preferred thresholds onto the physically feasible inventory set, observes censored sales, updates the resource rate, and takes a projected stochastic step.The rate moves the fluid target after each sales realization.Source: §3 · p. 6

3.1. The Executable RAPDL Recursion

• The preferred threshold is a learning state that may be infeasible as post-shipment inventory, so the implemented action is its Euclidean projection onto the feasible set.The projection has a water-filling representation.Source: §3.1 · p. 7

3.2. Gradient Estimation and Dual Stabilization

• Censored sales make the gradient sample observable at the implemented action, while an anchor correction borrows primal curvature to stabilize the dual coordinate without moving the target.The maximum-margin anchor’s KKT residual vanishes along the selected target path, including at zero resource, and the observable correction needs no additional sample.Source: §3.2 · pp. 8–9

3.3. Safeguards and Step-Size Design

• Capping the resource rate at D bounds the dual sample and removes endpoint explosion, while fixed caps keep preferred thresholds in a uniformly positive-survival region without excluding the fluid target.The projection box also contracts with remaining resource.Source: §3.3 · pp. 9–10
• The two-sided step-size schedule allows faster learning initially and faster resource adjustment near the end, with smaller updates in the middle.A horizon-independent constructive parameter choice certifies the regret guarantee; parameters may also be selected offline for the intended instance.Source: §3.3 · p. 10
• Remark 3.2 also considers a two-rate stepsize variant.The provided passage identifies the variant but does not specify its theoretical guarantee.Source: §3.3 · p. 10

4. Main Result and Regret Analysis

• Under Assumption 2.1, RAPDL with Algorithm 1 initialization and horizon-independent, primitive-based tuning has O(log T) regret for T≥2 and 0≤γ≤D, with C independent of T and γ.Source: §4 · p. 10, §4.1 · p. 11

4.1. High-Level Idea of Regret Analysis

• The O(log T) total comprises re-solving, learning, and implementation gaps, each O(log T).Source: §4.1 · p. 11

4.4. Step 2: Bounding the Learning Gap

• Tracking the re-solving path from censored sales yields an O(log T) cumulative learning gap.Source: §4.1 · p. 11, §4.4 · p. 15

4.2. Analytical Setup in Expected-Sales Space

• In expected-sales variables s_i=m_i(y_i), the affine resource term preserves primal curvature, while the executable policy remains in threshold space.Source: §4.2 · p. 11
• The transformed fluid program has a unique primal optimizer and selected smallest multiplier; its resource-clearing path has λ*(r)=0 for r≥r0.Source: §4.2 · p. 12

4.3. Step 1: Bounding the Re-Solving Gap

• Step 1 bounds the cumulative discrepancy from movements along the resource-indexed re-solving path by C log T, then separates learning and implementation gaps.Source: §4.3 · pp. 14–15

4.5. Step 3: Bounding the Implementation Gap

• Because implemented actions must obey store and warehouse inventory feasibility unlike preferred actions, implementation adds O(log T) discrepancy.Source: §4.1 · p. 11, §4.5 · p. 16

Experimental design

• The experiments compare RAPDL with DBS using matched demand paths, initialization, tuning budgets, and feasibility constraints across horizon lengths and inventory regimes.DBS is the closest directly comparable learning benchmark identified in the study.Source: §5 · p. 16

S2: heterogeneous setting

• The heterogeneous six-store setting uses positively correlated demands, with a shared within-period shock, and its specification is admissible under Assumption 2.1.Demand vectors remain independent and identically distributed over time.Source: §5 · p. 17

Performance metrics and results

• RAPDL has lower mean Total Cost in all 24 paired finite-horizon comparisons.The comparisons use 2,000 paired production paths for each reported cell.Source: Table 1 · p. 18, §5 · pp. 18, 20
• RAPDL's bootstrap median Relative Regret ranges from 0.30% to 12.38% at T = 100 and 0.15% to 6.58% at T = 200.Both methods are close to the fluid benchmark at practical horizons.Source: §5 · pp. 18, 20, Figure 1 · p. 19, Figure 2 · p. 19
• At T = 60 and T = 100, RAPDL's bootstrap median Relative Regret is below DBS's in all eight panels, while T = 20 and T = 40 comparisons are mixed.The earliest comparisons are retained in the figures.Source: Figure 1 · p. 19, Figure 2 · p. 19, §5 · p. 20

Sensitivity to endpoint information

• Across four resource levels at T = 200, the absolute Total Cost difference between exact endpoint information and the rough envelope is at most 1.24%.These are separately calibrated end-to-end implementations, not a fixed-parameter isolation of endpoint input.Source: Table 2 · p. 20, §5 · p. 20

6. Conclusion

• RAPDL tracks the endogenous primal-dual re-solving path using censored-sales updates to store thresholds and the warehouse scarcity price, with water-filling mapping learned states to feasible actions.The conclusion presents the framework as replacing fixed-target learning with online adaptation as shared inventory depletes.Source: §6 · p. 20

Online Appendix for “Resource-Adaptive Primal-Dual Learning for One-Warehouse

• The accompanying online appendix includes a technical bound for the learning gap, whose supporting proofs and local verifications are collected in Appendix A.5.Source: Online Appendix for “Resource-Adaptive… · p. 23, Appendix A · p. 23

Appendix A: Technical Bound for the Learning Gap

• The learning-gap analysis bounds cumulative primal-dual tracking and the unweighted first-order residual using a shared one-step mirror recursion.Its proof constructs an exact-target potential, smooths the moving KKT path, establishes one-step drift, and sums the recursion.Source: Appendix A · p. 23

A.1. Step 1: Construct the Exact-Target Potential

• The exact-target potential measures sales-space error while the algorithm updates in threshold space, and capping preserves the KKT target and feasibility.A tailored potential aligns the mean threshold step with the sales-error field and remains compatible with projection.Source: §A.1 · pp. 23–24

A.2. Step 2: Construct the Smoothed Comparator

• To handle corners in the exact target’s path, the analysis averages backward over a window of width η, balancing approximation and motion errors with η_t = √α_t.The smoothed comparator stays O(η) from the target, has Taylor remainder O(|∆r|^2/η), and remains feasible because it uses no more resource than r.Source: §A.2 · p. 25

A.3. Step 3: Establish the One-Step Drift

• The one-step drift argument combines a projected moving-comparator bound with state-update contraction and comparator-motion control.Censored-sales gradient estimates have conditional mean equal to the expected-sales field at the estimated state, with error controlled by the discrepancy between estimated and actual states.Source: §A.3 · pp. 26–27

A.4. Step 4: Sum the Recursion

• Summing the recursion in two ways controls the tracking potential and residual, then returns from the smoothed comparator to the exact target.The summation uses a reciprocal-step telescope and bounds the final residuals.Source: §A.4 · pp. 28–30

Proof of Lemma A.2

• The selected KKT path preserves capped complementarity and yields thresholds and a dual variable in the moving clipping box.The proof uses the binding and nonbinding branches to establish target preservation, then verifies coordinatewise primal bounds and the dual bound.Source: §A.5 · p. 30

Proof of Lemma A.3

• Lemma A.3 establishes metric comparison and gradient control on the safe box, converting the gradient bound into the stated metric bound.The proof compares the primal summands under a change of variables, then combines the lower metric bound with gradient estimates.Source: §A.5 · p. 31

Proof of Lemma A.4

• Lemma A.4 shows that smoothing preserves coordinatewise monotonicity and the multiplier range, becomes constant beyond the transition region, and has controlled derivatives.Its regularity argument uses translation continuity in L1 and an integral Taylor bound.Source: §A.5 · pp. 31–32

Proof of Lemma A.6

• Lemma A.6 proves state-update contraction by transferring a fixed-target restoring inequality to the smoothed comparator and then to the executable stochastic update.The transfer uses the ideal pairing and bounds the discrepancy between the ideal field and executable update.Source: §A.5 · pp. 32, 34
• Lemma A.6 also bounds comparator motion by controlling smoothing and resource changes, Taylor remainders, and radius motion.The proof combines these bounds to establish the comparator-motion estimate without same-period noise factorization.Source: §A.5 · pp. 35–36

Details for the one-step verification

• The one-step verification establishes joint-gradient regularity and verifies executable bounds, safe-box preservation, projection compatibility, and the conditional mean identities.Conditionally on the history, demand independence yields the stated probabilities for censored-sales events and the expected censored demand.Source: §A.5 · pp. 38–39

• The executable bounds place both X_t and Y_t in the fixed safe rectangle Q_i[0, ¯X_i].Source: §A.5 · p. 39
• On [0, ¯X_i], F_i is K_i-Lipschitz and m_i is one-Lipschitz.Source: §A.5 · p. 39
• The stabilized field is uniformly Lipschitz on that rectangle, and comparing Y_t with X_t proves the bias bound.Source: §A.5 · p. 39

Appendix B: Fluid Geometry and Remaining Proofs

• The appendix proves the remaining fluid-geometry, implementation-gap, and tuning claims.Its constants depend only on fixed primitives and horizon-independent tuning.Source: Appendix B · p. 39
• It sketches an extension to endpoint envelopes.Source: Appendix B · p. 39

Proof of Proposition 2.3

• Because Y_t is chosen before demand, the conditional expected store-period term equals ℓ_i(Y_i,t), proving (2.6).Source: Proof of Proposition 2.3 · p. 40
• Summing the inventory recursion shows that shipments only relocate inventory, while sales deplete it.This aggregate identity is used to establish (2.7).Source: Proof of Proposition 2.3 · p. 40
• The expected-sales transformation makes g_i convex.The passage also introduces the resulting representation, but its formula is incomplete in the supplied excerpt.Source: Proof of Proposition 2.3 · p. 40
• The fluid value v is convex under mixing feasible allocations and nonincreasing as the feasible set expands with resource rate r.Source: Proof of Proposition 2.3 · p. 40
• Clipping an allocation above the demand cap d̄_i preserves expected sales m_i(y_i) and weakly decreases expected loss ℓ_i(y_i).Source: Proof of Proposition 2.3 · p. 40

B.1. Fluid Benchmark and Re-Solving-Path Geometry

• The admissible-policy objective is bounded below by wW + T v(γ), yielding the stated oracle bound.The proof takes the infimum over admissible policies after establishing the bound.Source: Proof of Proposition 2.3 · p. 40

Derivation of sales-space curvature

• The sales-space curvature calculation gives h_i f_i(y) / (1 − F_i(y))^3.Source: Derivation of sales-space curvature · p. 41

• Strict convexity gives zero store allocation when λ ≥ b_i−c_i and a unique interior response otherwise; the responses are continuous across breakpoints, with Φ(0)=r0 and Φ(λmax)=0.Source: Proof of Lemma 4.3 · p. 41
• A maximum-margin-store argument yields v>0 almost everywhere; integrating the derivative shows Φ is Lipschitz and strictly decreasing from r0 to 0, so its inverse is well defined.Source: Proof of Lemma 4.3 · pp. 41–42
• For 0<r<r0, the inverse resource path gives the unique primal optimizer and its multiplier; at r=0, the multiplier set is [λmax,∞), and the proof selects λmax.Source: Proof of Lemma 4.3 · p. 42
• The representation implies the target q* is globally Lipschitz and each store allocation s_i*(r) is nondecreasing, including when breakpoints tie.The coordinate minimization also establishes the storewise activity rule and KKT residuals; the aggregate allocation is P*(r)=min{r,r0}.Source: Proof of Lemma 4.3 · p. 42
• The value function satisfies v′(r)=−λ*(r), is continuously differentiable, and has a Lipschitz derivative.Source: Proof of Lemma 4.3 · p. 42

B.2. Implementation Gap — Proof of Lemma 4.4

• The proof bounds preferred-path and physical-state movement using projection nonexpansiveness, water-filling target variation, and the state update.The resulting movement bound is |Xi,t+1 − Xi,t| ≤ Giαt + D pi(nt −1).Source: Proof of Lemma 4.4 · p. 43
• The proof telescopes expected inventory drainage using the physical inventory update and the conditional demand law.Conditionally on Ht, ei,t is fixed and Di,t has law Fi.Source: Proof of Lemma 4.4 · p. 44
• A density bound converts expected drainage into cumulative excess inventory throughout the safe box.The argument uses fi ≤ Ki and separate bounds over two ranges of y.Source: Proof of Lemma 4.4 · p. 44
• Water-filling converts cumulative excess into the implementation-gap bound; when it does not bind, the downward discrepancy is zero.The proof handles the binding and nonbinding cases separately and then combines the bounds for periods with nt ≥ H0 with the bound for the earlier periods.Source: Proof of Lemma 4.4 · p. 45

B.3. Tuning Construction — Verification of Remark 4.2

• The verification derives proof envelopes and constants from known primitives, including CW and Csm, rather than adding tuning inputs.The metric calculation validates CW, while the Lipschitz constant and fixed kernel’s total variation yield Csm; field and smoothness envelopes come from safe-box bounds.Source: Verification of Remark 4.2 · pp. 45–46
• When the step-size condition α0G ≤ 1 holds, the state-update argument gives the contraction in (A.22) with modulus µupd.Source: Verification of Remark 4.2 · p. 46
• The explicit choices verify all three inequalities in (A.36), giving computable remainder constants and horizon-independent tuning without demand laws.The verified remainders cover the state update, motion, and Taylor terms in (A.26).Source: Verification of Remark 4.2 · p. 46

B.4. Fixed Support Envelopes: An Extension Sketch

• Replacing r_c by r_c,up changes the fluid target and KKT path only on slack-branch states, so the comparator and several proof arguments remain unchanged.The new issue is that a projected threshold can lie beyond the true support, where the original global survival and mirror-metric bounds are unavailable.Source: §B.4 · p. 47
• A localization mechanism uses barriers and a hinge to recover localized metric and gradient control, a restoring inequality, and an operational-gap charge.On the interior region, existing arguments apply with a localized survival lower bound; the hinge handles the complement, supporting the exact-to-smoothed transfer.Source: §B.4 · pp. 47–48
• The fixed-envelope sketch reuses reciprocal-step summations to control localized potential and residual at logarithmic order, but records an extension route rather than a separate theorem.The Bellman telescope uses D_up in place of D; above the envelope cap, both resource rates lie on the constant slack branch.Source: §B.4 · p. 49

B.5. Two-Rate RAPDL: An Extension Sketch

• The two-rate analysis applies to any fixed κ > 0, with inventory decisions, observations, resource updates, and clipping sets unchanged from Algorithm 1.The subsection records a transfer sketch rather than repeating the proof of Theorem 4.1.Source: §B.5 · pp. 49–50
• For two-rate RAPDL, weighting the potential by the dual weight cancels the factor κ in the dual step, leaving the first-order primal-dual pairing unchanged.This weighted-potential identity allows the common-rate proof to be reused.Source: §B.5 · p. 49
• The two-rate transfer keeps projection compatibility and smoothing unchanged, while metric, gradient, and comparator bounds acquire κ-dependent constants.The exact-to-smoothed comparison, implementation-gap bound, and re-solving reduction then follow the common-rate proof with constants allowed to depend on κ.Source: §B.5 · pp. 49–50