PaperlayerView exact revision on arXiv

Source-linked AI summary

Information Limits of Multistage Inventory Control: Learning, Valuation, and Censoring

Hanzhang Qin, David Simchi-Levi, Ruihao Zhu

arXiv:2609.37380v1math.OCcs.SYeess.SY

TL;DR

Learning replenishment policies and estimating their costs can require different information, especially with inherited inventory or censored sales. The paper develops lower bounds and a carry-safe reduction for offline multistage inventory control, finding cubic worst-case policy-learning needs and cases where valuation remains harder or unidentified.

  • Problem

    The same demand data may support an optimal replenishment policy without revealing shortage costs, so policy learning and financial evaluation need not require the same information.

    Source: §1 · p. 1

  • Method

    The paper proves information-theoretic lower bounds for offline multistage inventory control and uses carry-safe caps to reduce censored observations while preserving transitions and policy gaps.

    Source: §1 · pp. 1–2

  • Results

    Policy learning requires cubically many observations in the nonstationary worst case, while stationarity allows quadratic policy learning and inherited-stock valuation can remain cubically difficult.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Under the stated logging protocol, policy learning and valuation have distinct information limits, and censoring can leave absolute costs unidentified despite attainability of the policy-learning limit.

    Source: §1 · p. 2, §6 · p. 20

    The coverage test is sufficient but not necessary for identification, and using the same observations to check coverage and fit the policy requires the stated protocol.

    Source: §5.5 · p. 20

Abstract

from arXiv · show

Learning how to replenish inventory and estimating the cost of doing so require different information. We establish information-theoretic lower bounds for offline multistage inventory control with independent bounded demand. For fixed additive error in total expected cost, policy learning requires cubically many scalar observations in the horizon in the worst case, even under full observation and adaptive sample allocation. This matches the known empirical-risk upper order. Stationarity permits a quadratic policy-learning guarantee, yet valuation with inherited stock can remain cubically difficult even when the optimal policy is known. Censoring sharpens this distinction: optimal decisions can be learnable while absolute costs remain unidentified. We give a carrysafe coverage condition under which truncation preserves inventory transitions and policy gaps exactly. Combining this reduction with a matching lower bound yields the sharp censored-learning rate, with raw sample requirements inversely proportional to the usable fraction of sales logs. The same qualified observations can check coverage and fit the policy under a joint error guarantee. The results isolate information limits for decisions and valuation under an explicit conditionally independent logging protocol.

1. Introduction

The paper distinguishes the information needed to learn replenishment decisions from that needed to value them in multistage inventory control. It establishes lower bounds and censored-data conditions for these tasks, including when carryover and stationarity change their difficulty.

1. Introduction

  • Policy learning needs cubically many scalar observations in the horizon in the worst case, even with full observation and adaptive allocation.The lower bound matches the known empirical-risk upper order.Source: §1 · p. 1
  • Stationarity permits a quadratic policy-learning guarantee, yet valuation with inherited stock can remain cubically difficult even when the optimal rule is known.A rare demand can determine how long inherited inventory accumulates holding costs; starting empty restores a quadratic valuation guarantee.Source: §1 · pp. 1–2
  • For censored lost-sales data, carry-safe caps preserve inventory transitions and cap-feasible policy gaps exactly, supporting a matching policy-learning limit.Raw sample requirements scale inversely with the usable fraction of logs reaching the caps, while absolute costs may remain unidentified.Source: §1 · p. 2
  • Prior work covers inventory sample guarantees and censored single-period settings; this paper focuses on additive total-cost error with nonstationarity, adaptive allocation, and carryover.Its censored contribution is a finite-horizon carryover reduction with a matching policy-learning lower bound.Source: §1 · p. 2

2. Model and Observation Protocols

The model separates inventory decisions and values from the demand observations available to learn them. It specifies full-demand and censored-sales protocols, then frames policy learning and value estimation as distinct sample-complexity tasks.

2.1. Inventory Decisions and Values

  • Backlog reveals demand, whereas lost-sales observations reveal only sales; the backlog cost equivalence relies on zero ordering cost and lead time.The stated setting allows randomized feasible policies and assumes independent bounded demands.Source: §2.1 · p. 3
  • With zero ordering cost, lead time, and terminal salvage value, optimal decisions in both models use period-specific base-stock levels bounded by the demand support.For initial inventory in [0, D̄], optimal states lie in [−D̄, D̄] under backlog and [0, D̄] under lost sales.Source: §2.1 · p. 3

2.2. Demand Samples, Censored Sales, and the Usable Fraction

  • Periodwise samples allow demand laws to vary by period, while pooled IID samples reuse draws from a common law under time-homogeneous costs.The periodwise adaptive protocol may choose the next sampled period using preceding observations.Source: §2.2 · p. 4
  • Censored logs count as usable when their boundaries reach a cap; converting a usable-sample requirement to a raw budget costs a factor of 1/r.The protocol assumes conditional noninformative censoring; boundaries are fixed or determined before their own demand, excluding some adaptive sales logs.Source: §2.2 · p. 4

2.3. Learning Tasks and Summary of Results

  • The paper defines policy learning and optimal-value estimation as separate high-probability accuracy tasks and summarizes their sample-complexity results in Table 1.The table notes specify additive total-cost error, success probability, and conditions for the reported lower bounds and censored rates.Source: §2.3 · p. 5, Table 1 · p. 5

3. Information-Theoretic Lower Bounds

This section establishes information-theoretic lower bounds for policy learning and value estimation, distinguishing full-demand learning, censored archives, inherited-inventory valuation, and value nonidentification.

3.1. Policy Learning with Full Demand Observations

  • Θ(T^3 eps^-2) scalar observations are necessary for fixed-confidence policy learning with full demand observations, matching the Product ERM upper order.The lower bound allows adaptive sample allocation and arbitrary feasible randomized policies.Source: §3.1 · pp. 6–7

3.2. Policy Learning with Censored Observations

  • M_cov(T, eps, r) > T^3/(46137344 r eps^2) for censored policy learning, so the required raw archive grows inversely with the revealing-log fraction r.Logs reaching boundary 7/8 reveal the unknown demands, whereas low-boundary logs carry no information.Source: §3.2 · pp. 8–9

3.3. Optimal-Value Estimation with Inherited Inventory

  • For η≤1/4, Ω(T^3 ε^-2 log(1/η)) pooled IID demand observations can be necessary to estimate the value of a known, optimal base-stock-zero policy in instances with h_t=p_t=1 and D_t∈{0,1}.Source: §3.3 · pp. 9–10

3.4. Optimal-Value Nonidentification under Censoring

  • For 0 < eps < T/32, no finite censored-sales archive can estimate optimal value with the required accuracy, even under strict coverage and when the optimal policy is identified.The two demand laws yield identical sales distributions and the same optimal policy, but have different missing-tail constants.Source: §3.4 · pp. 10–11

4. A Full-Observation Benchmark

The section develops a full-observation benchmark for policy learning and valuation, then shows how stationarity changes policy-learning sample requirements. It also distinguishes empty-start valuation from valuation with inherited inventory.

4.1. Product ERM and the Empirical-DP Guarantee

  • Product ERM uses independent periodwise demand samples, and one uniform estimation event controls both policy regret and optimal-value error.Replacing demand laws in the Bellman recursion by empirical marginals implements the minimization through empirical dynamic programming.Source: §4.1 · p. 11

4.2. Horizon-Free Uniform Convergence and Product Transfer

  • The horizon-free uniform-convergence bound transfers to product empirical laws, with independence needed separately for that product transfer.The cited scope includes independent nonidentical demands and a bound without dependence on d, log d, or log N.Source: §4.2 · pp. 12–13
  • With probability at least 1 − δ, all starting periods and states have value error at most b_t and policy gap at most 2b_t; log T supports the simultaneous guarantee.The extension applies the bound to each tail and uses a union bound across starting periods.Source: §4.2 · p. 14

4.3. Stationary Policy Learning

  • For stationary demand, pooling observations reduces the policy-learning upper order from cubic to quadratic in the horizon.The section establishes this through a newsvendor reduction and a pooled empirical policy.Source: §4.3 · pp. 14–15
  • M ≥ 2max{h, p}^2 D̄^2 T^2 ε^-2 log(2/η) pooled observations suffice for ε-optimal stationary policy learning.The guarantee assumes IID bounded demand, time-constant holding and shortage costs, and zero ordering cost and lead time.Source: §4.3 · pp. 14–15

4.4. Optimal-Value Estimation and the Stationary Separation

  • Empty-start optimal-value estimation uses O(T^2 ε^-2 log(1/η)) pooled observations, while inherited inventory creates a separation from policy learning.The stated valuation order applies at bounded cost and demand scales.Source: §4.4 · p. 16

5. Learning from Censored Sales

The section makes censored policy learning possible under carry-safe coverage: truncation preserves the relevant inventory dynamics and policy gaps. It derives a sharp learning rate and a procedure that uses qualified logs to test coverage and fit a policy.

5.3. Exact Truncation and Decision Equivalence

  • Carry-safe coverage supports policy learning from censored sales by making truncated demands decision-equivalent to the original system.The reduction preserves inventory transitions and policy gaps for cap-feasible policies.Source: §5 · p. 16, §5.3 · p. 18

5.1. Why Coverage Is Necessary

  • Without adequate coverage, censored sales can leave even a single-period optimal replenishment decision unidentified, regardless of sample size.The baseline compares demand laws that produce identical observed sales but have different costs for replenishment choices.Source: §5.1 · p. 16

5.2. Carry-Safe Decision Coverage

  • Carry-safe caps preserve the full-information optimal value for states within the caps, whereas periodwise coverage alone may fail to ensure cap closure.The caps constrain carried inventory as well as replenishment levels.Source: §5.2 · p. 17

5.4. Sharp Learning Rate under Prescribed Archives

  • Under maintained coverage, qualified logs support Product ERM, and the sharp censored-learning rate has raw sample requirements inversely proportional to the usable fraction.The usable fraction counts logs reaching the caps; the prescribed-archive result includes discarded logs in the raw budget.Source: §5.4 · pp. 18–19

5.5. Checking Coverage from the Same Archive

  • The observable coverage test is sufficient but not necessary for identification, and its qualified observations can also fit the policy.The same archive supports coverage checking and policy learning under the stated protocol and joint error guarantee.Source: §5.5 · pp. 19–20

6. Concluding Remarks

The conclusion distinguishes the information limits of policy learning and valuation in multistage inventory control. It identifies inherited inventory and censoring as settings where valuation can be harder than learning decisions.

6. Concluding Remarks

  • Policy learning and valuation face different information limits in multistage stochastic inventory control.The conclusion notes that inherited inventory can make valuation harder and censoring can leave costs unidentified even when carry-safe truncation attains the policy-learning limit.Source: §6 · p. 20
  • Demand-adaptive logging, positive lead times, and necessary multiperiod coverage conditions are identified as directions for future study.Source: §6 · p. 20
  • Censoring can leave absolute costs unidentified even when carry-safe truncation attains the policy-learning limit.Source: §6 · p. 20

Data and Code Accessibility

The supplementary files provide materials for the synthetic experiments and companion figures; the illustrations require no proprietary data.

Data and Code Accessibility

EC.1. Supplementary Illustrations

The supplementary illustrations demonstrate valuation error despite a known optimal policy and examine boundary-qualified learning under exact demand truncation. They illustrate mechanisms and identities rather than provide independent evidence for minimax rates or algorithmic superiority.

EC.1. Supplementary Illustrations

  • The numerical illustrations are implementation and teaching examples, not independent evidence for minimax rates or algorithmic superiority.The authors report that scripts, fixed configurations, seeds, and figure inputs are available in supplementary files.Source: EC.1. Supplementary Illustrations · p. 23

EC.1.1. Valuation When the Optimal Policy Is Known

  • The known-policy valuation illustration still has nonzero value-estimation error; its comparison isolates uncertainty in the value of carried inventory, not an algorithm ranking.Theorem 3, rather than this particular estimator’s error, establishes valuation difficulty.Source: EC.1.1. Valuation When the Optimal… · p. 23

EC.1.2. Exact Truncation and Boundary-Qualified Learning

  • Boundary-qualified learning preserves absolute policy gaps under truncation to the cap, with the reported gap agreement within 1.2 × 10−15.The omitted cost is the policy-independent constant T/64 = 0.3125; percentages agree only with the same denominator.Source: EC.1.2. Exact Truncation and… · p. 24
  • For r = 1/8, the qualified learner’s mean gap falls from about 6.5% to 0.15% across the displayed budgets.The universal 1/r lower bound comes from Theorem 2, not this numerical illustration.Source: EC.1.2. Exact Truncation and… · p. 24
  • The exact plateau for r < 1/2 is a construction effect: the r = 1/4 and r = 1/8 curves overlap, and the relative gap is 435.714%.The policy costs about 5.36 times the optimum.Source: EC.1.2. Exact Truncation and… · p. 25
  • The coverage-check calculation requires 335, 1,337, and 5,348 usable observations per period for margins 0.2, 0.1, and 0.05, respectively.Halving the margin requires about four times as many usable observations.Source: EC.1.2. Exact Truncation and… · p. 25
Loading 2609.37380v1…