PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiameng Lyu

arXiv:2608.14096v1cs.LGmath.OC

TL;DR

In one-warehouse multi-store inventory systems, fixed-target learning cannot adapt allocations after realized sales change remaining resources. The paper introduces a resource-adaptive primal-dual framework using censored demand and proves logarithmic expected regret, improving on square-root-order guarantees.

  • Problem

    OWMS allocation requires dynamically balancing service across stores with different demand distributions and economic margins, while fixed-target learning cannot re-center as resources change.

  • Method

    RAPDL tracks the endogenous primal-dual resolving path using remaining-resource rates and censored-demand gradient estimates.

  • Results

    O(log T) regret improves on square-root-order guarantees, while experiments report lower mean total cost across homogeneous and heterogeneous regimes.

  • Takeaways & Limitations

    The framework and analysis may inform online learning problems involving depleting shared resources.

  • Takeaways & Limitations

    The analysis assumes demand vectors are i.i.d. over time and requires existence and regularity of the selected smallest resource multiplier.

Abstract

from arXiv · show

The one-warehouse multi-store (OWMS) system is a fundamental inventory network in which a nonreplenishable warehouse allocates shared stock across multiple stores over time. Existing OWMS learning policies are built around a fixed target calibrated to the initial average resource rate, but such a fixed-target architecture cannot re-center after realized sales change the remaining resource available per future period. We develop Resource-Adaptive Primal-Dual Learning, a new learning framework that tracks the primal-dual resolving path with censored demand as the remaining-resource state evolves. In each period, the current resource rate indexes the target store allocations and dual variable, while censored sales provide gradient estimates for updating both. The analysis combines expected-sales geometry with a moving-target argument to yield logarithmic expected regret, improving on the state-of-the-art square-root-order guarantees of existing OWMS learning policies. The underlying design and analytical ideas may inform other online learning problems with depleting shared resources. Numerical experiments further demonstrate good finite-horizon performance of a practical variant across different horizon lengths and inventory regimes.

1. Introduction

The paper addresses learning in finite-stock OWMS systems, where allocations compete for shared inventory under unknown demand and censored feedback. It introduces RAPDL to track and re-center the resource-indexed Primal-Dual path, establishing logarithmic regret and favorable short-horizon numerical performance.

  • Motivation: Finite warehouse inventory creates dynamic competition across stores and periods, while unknown demand and censored feedback make learning difficult.Each allocation changes future inventory and the opportunity cost of later units.
  • Related work: Existing finite-stock censored-demand OWMS policies learn fixed targets and have square-root-order regret guarantees.This contrasts with the paper’s resource-indexed re-solving approach.
  • Method: RAPDL replaces the initial-rate fixed target with online tracking of the endogenous Primal-Dual path generated by resource-state re-solving.Remaining inventory per remaining period re-indexes store allocation targets and their common scarcity price, while censored sales update both the target and resource state.
  • Theory: O(log T) regret follows because value-function smoothness, expected-sales geometry with moving-target analysis, and inventory dynamics each control a logarithmic regret component.The framework avoids estimating demand distributions or repeatedly solving a fluid program.
  • Numerical evaluation: 24 paired comparisons show RAPDL has lower mean total cost than Double Binary Search across homogeneous and heterogeneous inventory regimes.The experiments provide short-horizon evidence for the algorithm.

2. Problem Formulation

The paper formulates a one-warehouse multi-store inventory system with nonreplenishable stock, censored demand observations, lost sales, and state-dependent inventory dynamics. It compares admissible policies through a constrained fluid benchmark and resource-rate-specific primal-dual optimizers.

  • System dynamics: The system has N stores and T periods, begins with nonreplenishable warehouse stock B_1 = W = γT, and starts every store empty.The warehouse allocates post-shipment store stocks while warehouse and store inventories evolve through sales.
  • System dynamics: Each period, the manager observes the current state and past sales, chooses shipments before demand, observes only censored sales, and updates inventories; unmet demand is lost.Sales satisfy S_i,t = D_i,t ∧ Y_i,t, with next-period store inventory and warehouse stock determined by realized sales and shipments.
  • Demand assumptions: Demand vectors are i.i.d. over time, coordinates may be arbitrarily dependent within a period, and each store’s marginal demand law F_i is absolutely continuous on [0, ¯d_i].The model imposes continuous-density bounds on each marginal distribution.
  • Benchmarks and regret: The one-period fluid relaxation retains the expected-sales budget, defines a value that lower-bounds the exact dynamic benchmark, and motivates regret relative to the constrained fluid benchmark.The fluid-benchmark gap is nonnegative and upper-bounds the performance gap relative to the exact dynamic oracle.
  • Benchmarks and regret: For each resource rate r, y∗(r) is the unique optimizer of the one-period fluid program, while λ∗(r) is its selected smallest resource multiplier.The existence and regularity of these resource-rate-specific quantities are established in the formulation.

3. Resource-Adaptive Primal-Dual Learning · Appendix B.5 discusses this two-rate variant and sketches its theoretical guarantee.

RAPDL adapts store thresholds and a common shadow price to the evolving remaining-resource rate, using censored sales to update the moving primal-dual target. Its executable recursion combines feasibility projection, censored-feedback gradient estimation, resource updates, dual stabilization, safeguards, and a two-sided step-size schedule.

  • 3. Resource-Adaptive Primal-Dual Learning: RAPDL uses the remaining-resource rate to index preferred thresholds and a common shadow price, replacing the fixed target indexed by γ.Each sales observation both provides censored feedback and changes the next resource index.
  • 3. Resource-Adaptive Primal-Dual Learning: Each period projects preferred thresholds onto the feasible inventory set, observes censored sales, updates the resource rate, and takes a projected stochastic step.The rate rt moves the fluid target after every sales realization.
  • 3.1. The Executable RAPDL Recursion: The executable recursion projects the learning state Xt onto the physically feasible set before implementing actions, using a Euclidean projection with a water-filling representation.The preferred threshold need not itself be a feasible post-shipment inventory.
  • 3.1. The Executable RAPDL Recursion: After observing Si,t := Di,t ∧ Yi,t, RAPDL forms the censored-sales gradient estimate bGi,t and uses it in the projected primal-dual update.The estimator combines stockout indicators, cost terms, and the current dual variable.
  • 3.2. Gradient Estimation and Dual Stabilization: The anchor correction stabilizes the dual direction because the joint Lagrangian has zero dual curvature, while its observable form requires no additional sample.The correction borrows curvature from a maximum-margin primal coordinate without moving the selected target path.
  • 3.3. Safeguards and Step-Size Design: Resource capping, safe clipping, and a two-sided step-size schedule control sample magnitude, preserve survival-probability geometry, and adjust responsiveness across the horizon.The cap rc := min{r,D} removes endpoint explosion, while the schedule supports faster learning initially and faster resource adjustment near the end.

4. Main Result and Regret Analysis

Theorem 4.1 establishes a horizon-independent, logarithmic regret guarantee for RAPDL under the stated model assumptions. The analysis decomposes regret into re-solving, learning, and implementation gaps, each controlled at logarithmic order.

  • Main theorem: Theorem 4.1 gives RAPDL horizon-independent tuning under Assumption 2.1 for every T ≥2, 0 ≤γ ≤D, and admissible within-period joint demand law.The constant C depends only on fixed model primitives and the selected tuning, not on T or γ.
  • Regret decomposition: O(log T) cumulative gap arises from movements along the resource-indexed fluid re-solving path relative to the fluid benchmark.This is the intrinsic re-solving component, even if the policy could follow the path exactly.
  • Regret decomposition: O(log T) cumulative tracking gap results from learning the unobserved Primal-Dual re-solving path using censored sales.Unknown demand laws prevent direct computation of the path, so RAPDL tracks it from censored observations.
  • Regret decomposition: O(log T) cumulative discrepancy arises from implementing preferred actions subject to current warehouse and store inventories.Adding the re-solving, learning, and implementation gaps yields the overall O(log T) regret bound.
  • Fluid-path analysis: The transformed fluid program has a unique primal optimizer s∗(r) and selected smallest optimal multiplier λ∗(r), including when stores have identical margins.The resource-clearing branches satisfy λ∗(r) = 0 for r ≥r0, supporting the path properties used in the regret analysis.

5. Numerical Experiments

Numerical experiments compare RAPDL with DBS across homogeneous and heterogeneous inventory settings, horizons, and resource levels. RAPDL achieves lower mean Total Cost in every paired comparison, while endpoint-envelope substitution has only a small effect.

  • Experimental design: The study compares RAPDL with DBS across different horizon lengths and inventory regimes using matched demand paths, initialization, tuning budgets, and feasibility constraints.S1 uses a homogeneous setting, whereas S2 is heterogeneous and includes cross-store dependence.
  • Performance metrics and results: At T = 100, RAPDL’s bootstrap median Relative Regret ranges from 0.30% to 12.38%, narrowing to 0.15%–6.58% by T = 200.Both methods remain close to the fluid benchmark at practical horizons.
  • Sensitivity to endpoint information: Across four resource levels, the absolute Total Cost difference between exact endpoint information and a rough envelope is at most 1.24%.Replacing the exact endpoint with a conservative upper bound therefore has only a small numerical effect in these finite-horizon comparisons.

6. Conclusion … A.4. Step 4: Sum the Recursion

RAPDL adapts primal-dual learning to censored demand and depleting shared inventory by tracking the endogenous re-solving path, with logarithmic-order analysis and strong finite-horizon empirical performance. The appendix develops the technical bound through an exact-target potential, smoothed moving comparator, one-step drift recursion, and recursive summation.

  • 6. Conclusion: RAPDL replaces fixed-target learning with online tracking of the endogenous Primal-Dual re-solving path under unknown demand and censored sales.Censored sales update preferred store thresholds and the warehouse scarcity price, while water-filling maps the learned state to feasible actions.
  • 6. Conclusion: Logarithmic-order bounds control the re-solving, learning, and implementation gaps, while numerical experiments show strong finite-horizon performance across inventory regimes.The framework also tracks re-solving incrementally under unknown and censored feedback and may inform learning-and-control methods for other systems with depleting shared resources.
  • Appendix A: Technical Bound for the Learning Gap: The technical bound controls squared-tracking and first-order residuals using a one-step mirror recursion.The proof proceeds by constructing an exact-target potential, smoothing the moving KKT path, establishing one-step drift, and summing the recursion.
  • A.1. Step 1: Construct the Exact-Target Potential: Capping preserves the KKT target and feasibility, while a threshold-space potential measures exact sales-space error and remains compatible with projection.The potential uses sales coordinates for the comparator, threshold coordinates for the update state, and endpoint extensions to maintain bounded curvature.
  • A.2. Step 2: Construct the Smoothed Comparator: Smoothing the exact target over a backward resource window removes path corners while preserving feasibility and balancing approximation with motion errors.The construction stays O(η) from the target, has Taylor remainder O(|∆r|2/η), and uses ηt = √αt.
  • A.3. Step 3: Establish the One-Step Drift: The projected moving-comparator argument establishes regularity, executable bounds, admissible projections, state-update contraction, and comparator-motion control for the one-step drift.Censored-gradient estimates satisfy E[ bGt | Ht] = Gθ(Yt,λt;rt), with their deviation controlled by ∥Yt −Xt∥.
  • A.4. Step 4: Sum the Recursion: Summing the one-step recursion yields the required tracking and exact-to-smoothed comparison bounds through harmonic estimates and bounded potential terms.The proof drops nonnegative residuals, handles finite initial terms directly, and uses reciprocal-step telescoping for the residual summation.
  • A.4. Step 4: Sum the Recursion: Residual summation combines resource dissipation, reciprocal-step telescoping, and the previously established potential bound to prove the unweighted first-order residual result.The resource term can be dropped after applying target resource feasibility, while the telescope contributes at most C + (1/χ)PL.

A.5. Auxiliary Proofs and Verifications

This appendix section collects the auxiliary proofs supporting the framework, including target-path feasibility, metric and gradient control, smoothing regularity, state contraction, comparator motion, and one-step verification.

  • Target-path properties: The auxiliary proofs verify target preservation, complementarity, feasibility in the moving clipping box, and threshold–dual membership.The selected KKT path also satisfies 0 ≤ λ∗(r) ≤ λmax and coordinatewise primal bounds.
  • Metric and gradient bounds: The proofs establish the metric comparison and gradient-control inequalities needed to bound the Wasserstein-type field by CW(q,z).These results combine the change-of-variables argument, differentiation on the safe box, and the lower bound in (A.9).
  • Smoothing regularity: The smoothed KKT path preserves coordinatewise monotonicity, remains within the multiplier range, and satisfies regularity bounds through kernel translation continuity and Taylor expansion.For r ≥ r0 + η, the averaged integrands equal the constant nonbinding target.
  • Restoring inequality: The fixed-target restoring calculation uses KKT cancellation, strong convexity, and a maximum-margin anchor to absorb multiplier cross terms and prove the restoring inequality.The anchor pairing separates into a positive multiplier square and a cross term, which is controlled using survival, Lipschitz, and Young bounds.
  • One-step verification: The remaining one-step verification proves the three model-specific conditions in Appendix A.3 and thereby verifies Lemma A.5’s hypotheses.The section explicitly identifies these checks as the final model-specific verification.

Appendix B: Fluid Geometry and Remaining Proofs

Appendix B establishes the remaining fluid-geometry, implementation-gap, and tuning claims, while sketching an endpoint-envelope extension with constants independent of the horizon.

  • The appendix proves the remaining fluid-geometry claims.
  • It also proves the remaining implementation-gap and tuning claims.
  • The appendix sketches an endpoint-envelope extension.
  • Constants depend only on fixed primitives and are horizon-independent.

B.1. Fluid Benchmark and Re-Solving-Path Geometry Proof of Proposition 2.3

The section proves the fluid benchmark’s expected-sales identities and establishes the geometry of the value function through feasibility, clipping, convexity, and monotonicity arguments. Jensen-based aggregation then yields the oracle bound.

  • Direct calculations: Conditional on pre-demand actions, the expected bracketed store–period term equals ℓ_i(Y_i,t), proving (2.6).The proof uses that Y_t is chosen before current demand.
  • Direct calculations: Because shipments relocate inventory while sales deplete it, summing aggregate inventory recursions establishes the sales-based identity (2.7).The argument explicitly distinguishes inventory relocation from depletion.
  • Re-solving-path geometry: The value function v is convex by mixing feasible allocations and nonincreasing because its feasible set expands with r.These properties support the subsequent benchmark comparison.
  • Re-solving-path geometry: Clipping any allocation y_i above the demand cap ¯d_i preserves m_i(y_i) while weakly decreasing ℓ_i(y_i), maintaining feasibility for the fluid program.The proof separately notes feasibility when 0 ≤ y_i ≤ ¯d_i.
  • Oracle bound: Applying the benchmark inequality to random actions, then Jensen across actions and periods, produces the oracle lower bound.The final step takes the infimum over all admissible policies.

Derivation of sales-space curvature

The section derives sales-space curvature by applying equations (2.4) and (2.5), differentiating once more, and obtaining an expression involving h_i, f_i(y), and (1−F_i(y))^3.

  • Derivation of sales-space curvature: Equations (2.4) and (2.5) provide the starting expression for the sales-space curvature derivation.The supplied passage identifies these equations as the basis of the derivation.
  • Derivation of sales-space curvature: Differentiating the preceding expression once more advances the curvature calculation.The passage explicitly states that a further differentiation is performed.
  • Derivation of sales-space curvature: The resulting expression is h_i f_i(y) (1−F_i(y))^3.This is the displayed terminal form in the supplied derivation fragment.

Proof of Lemma 4.3

The proof characterizes the fixed-price response and shows that the aggregate allocation map Φ is continuous, strictly decreasing, and invertible. It then establishes the optimizer’s explicit primal-dual representation, endpoint multiplier selection, monotonicity, Lipschitz regularity, and value sensitivity.

  • Fixed-price response: Strict convexity yields a unique coordinate minimizer: zero allocation when λ ≥ b_i − c_i and an interior stationary solution otherwise.The response formula ϕ_i(λ) is continuous across breakpoints because the interior solution decreases to zero as λ approaches b_i − c_i.
  • Aggregate allocation map: Φ is Lipschitz and strictly decreasing from r_0 to 0, so its inverse is well defined on the positive resource interval.The proof obtains positivity of the derivative almost everywhere and integrates across the finitely many breakpoint intervals.
  • Primal-dual representation: The optimizer is (ϕ(Φ^-1(r)), Φ^-1(r)) for 0 < r < r_0, with zero primal allocation at r = 0 and a selected multiplier λ*(0) = λ_max.At r = 0, admissible multipliers form [λ_max,∞); selecting the smallest multiplier makes the dual target continuous at the endpoint.
  • Regularity and monotonicity: The optimal allocations s*_i(r) are nondecreasing in r, while q* is globally Lipschitz and the selected dual multiplier is nonincreasing in r.These properties follow from the monotonicity of ϕ_i and λ*(r), together with integration across tied breakpoints.
  • Value sensitivity: The proof derives P_i(r) = min{r,r_0}, verifies the endpoint claims and KKT residuals, and establishes v′(r) = −λ*(r) with a Lipschitz derivative.Continuity of the selected multiplier implies that v is continuously differentiable, while the multiplier Lipschitz bound transfers to v′.

B.2. Implementation Gap Proof of Lemma 4.4 · B.3. Tuning Construction Verification of Remark 4.2

B.2 proves the implementation-gap bound through four steps: controlling preferred-path and physical-state variation, telescoping expected drainage, converting drainage to cumulative excess, and bounding the implementation gap. B.3 verifies an explicit, horizon-independent tuning construction using only known primitives and without demand laws.

  • B.2. Implementation Gap Proof of Lemma 4.4: The implementation-gap proof is organized into four steps covering state variation, expected drainage, cumulative excess, and the final implementation-gap conversion.The proof explicitly identifies these four stages before developing the corresponding bounds.
  • B.2. Implementation Gap Proof of Lemma 4.4: Preferred-path and physical-state variation are bounded using the algorithmic update, feasibility projection, projection nonexpansiveness, endpoint bounds, and gradient estimates.The resulting variation terms include Giαt and D pi(nt −1).
  • B.2. Implementation Gap Proof of Lemma 4.4: Expected drainage is telescoped from the water-filling formula and physical inventory update, conditioning on Ht so ei,t is fixed and Di,t has law Fi.The argument uses Yi,t, Ii,t, and Ii,t+1 relations induced by water-filling and demand realization.
  • B.2. Implementation Gap Proof of Lemma 4.4: Cumulative excess is obtained by converting expected drainage through density bounds and separate inequalities for the two ranges of y within the safe box.The proof uses fi ≤Ki and bounds y differently in the first and second ranges.
  • B.2. Implementation Gap Proof of Lemma 4.4: The final conversion bounds the implementation gap by distinguishing whether water-filling binds; when it does not bind, the downward discrepancy is zero.The proof uses Yi,t > Xi,t if and only if Yi,t = Ii,t > Xi,t and handles periods with nt ≥H0 separately from the initial periods.
  • B.3. Tuning Construction Verification of Remark 4.2: The B.3 construction fixes motion-cutoff, smoothness, and update constants explicitly from known primitives, with Csm := 3Lq and µupd := µ0 8CW > 0.The proof states that the resulting envelopes are proof envelopes rather than additional tuning inputs.
  • B.3. Tuning Construction Verification of Remark 4.2: The selected parameters satisfy the required contraction, step-profile, recovery, and remainder inequalities, yielding horizon-independent tuning without using demand laws.The verified conditions include χ ≥χM, µrecχ > 3, χ/α0 ≤τ0 ≤2χ/α0, and µrecα0 ≤1/2.

B.4. Fixed Support Envelopes: An Extension Sketch · B.5. Two-Rate RAPDL: An Extension Sketch

B.4 sketches how fixed certified support envelopes can be incorporated into RAPDL by adding localization while reusing the established proof architecture. B.5 similarly sketches a two-rate extension whose weighted potential preserves the common-rate primal-dual cancellation, with constants depending on the fixed rate ratio.

  • B.4. Fixed Support Envelopes: An Extension Sketch: B.4 adapts Theorem 4.1’s proof architecture to fixed, horizon-independent support envelopes by replacing exact support endpoints with conservative caps and adding localization barriers.The direct safe-box formulation remains the formal guarantee; the fixed-envelope route is recorded as an extension sketch.
  • B.4. Fixed Support Envelopes: An Extension Sketch: B.4 preserves the fluid target, KKT path, backward-smoothed comparator, moving-comparator analysis, reciprocal-step bounds, and Bellman telescope after replacing D with Dup.The altered cap case is harmless above Dup because both resource rates lie on the constant slack branch, making the Taylor remainder zero.
  • B.4. Fixed Support Envelopes: An Extension Sketch: B.4’s localization uses a fixed extended box, a C1,1 hinge, and inward drift to control metric and gradient terms, restore the process, and charge the operational gap.Inside the localized region, the main survival-bound arguments apply; outside it, the hinge offsets the exterior loss.
  • B.4. Fixed Support Envelopes: An Extension Sketch: B.4 retains logarithmic-order control because exact-to-smoothed transfer, reciprocal-step summations, residual bounds, and the Bellman telescope carry over with envelope-dependent constants.The extension identifies the additional ingredients but does not state a separate theorem or provide a formal proof.
  • B.5. Two-Rate RAPDL: An Extension Sketch: B.5 presents the transfer argument as a sketch rather than repeating Theorem 4.1’s proof, while indicating extension to every fixed κ > 0.The tuning construction is reused under the two-rate substitution subject to the stated initialization condition.
  • B.5. Two-Rate RAPDL: An Extension Sketch: B.5 reuses the common-rate moving-comparator, implementation-gap, exact-to-smoothed, and re-solving arguments with constants allowed to depend on κ.The dual rate does not enter the physical excess-inventory recursion, so implementation changes arise only through the primal variation bound.
Loading 2608.14096v1…