Towards Optimal Inventory Control under Censored Demand: A Biased Sample-Average Approximation Approach

1. Introduction

• Censored observations reveal demand only below their stocking level, so offline learning depends on whether the observed levels cover decision-relevant demand, while online collection must balance information against inventory cost.The introduction asks whether this coverage suffices for consistent learning and whether one adaptive policy can create it while achieving low regret; Qin et al. (2023) gives a worst-case impossibility result but does not identify an instance-dependent condition.Source: §1 · pp. 2–3

1.1. Contributions

• A derivative-based cost decomposition for base-stock policies localizes policy-gap errors to decision-relevant parts of the demand model and also yields a uniform-CDF-error reduction.The decomposition tracks marginal values through demand-induced inventory dynamics rather than reducing policy learning to policy evaluation error.Source: §1.1 · p. 3
• Offline DP-UCB uses an upper-biased demand CDF and achieves the stated learning guarantee when its instance-dependent effective sample size covers coordinates relevant to the optimal policy.The coverage measure counts trajectories with stocking levels above each demand coordinate; upward CDF bias pushes base-stock levels lower, toward better-covered coordinates. Under stationary demand, observations can also be aggregated across periods for an improved rate.Source: §1.1 · pp. 5–6
• For stationary demand, offline observations can be pooled across periods, while online observations can be pooled across periods and episodes, yielding sharper rates than the non-stationary guarantees.The introduction reports a factor-T improvement in the stationary online regret rate.Source: §1.1 · pp. 6, 8, §1.2 · p. 8
• The paper establishes minimax lower bounds over coverage classes, including the uncensored case, and describes these as the first tight lower bounds for multi-period inventory policy learning.The coverage classes are parameterized by a coverage fraction p.Source: §1.1 · p. 6
• Online DP-LCB uses a shrinking lower-biased CDF to raise early base-stock levels, generate coverage of the optimal policy, and achieve optimal regret with a matching lower bound.Its collected data have effective sample size on the order of the episode count, up to logarithmic and burn-in terms; under stationary demand, aggregation across periods and episodes yields a factor-T improvement in regret rate.Source: §1.1 · pp. 7–8

1.2. Other Related Works

• Related work on non-stationary multi-period inventory does not provide consistent learning guarantees under censored demand, while censored newsvendor settings use one-stage quantiles rather than multi-period dynamic programming.The paper distinguishes its setting from both repeated newsvendor problems and multi-period problems with stationary demand and costs.Source: §1.2 · p. 8
• The cost decomposition recovers the sharper inventory policy-learning rate, with stationary demand further sharpening its horizon dependence.This contrasts with generic MDP analyses and complements work on exploiting stationary transitions.Source: §1.2 · p. 9
• For structured base-stock policies, policy learning can be strictly easier than evaluating the optimal cost (Ren et al. 2021).The passage contrasts this with general MDPs, where reducing policy learning to policy evaluation is sharp (Li et al. 2024a,b, Xiong et al. 2022).Source: §1.2 · p. 9
• DP-LCB uses a lower-biased CDF to explore through higher base-stock levels and achieves the optimal online regret.The discussion relates this mechanism to optimism in episodic reinforcement learning.Source: §1.2 · p. 9

• For positive integers n, [n] denotes {1,...,n}, while [n]+ includes 0; integer intervals use inclusive [a,b] or half-open [a,b).Source: §2 · p. 9
• Vectors and matrices are indexed from 0 unless stated otherwise, and an M-dimensional vector uses indices 0 through M−1.Source: §2 · p. 9
• High-probability statements use confidence level δ ∈ (0,1/2), and the conventions define positive-over-zero as +∞ and zero-over-zero as 1.Source: §2 · p. 9

• The problem assumes bounded holding and lost-sales penalties, demands supported on the finite set [M]+, and an integer initial inventory level.Source: §2 · p. 10
• Under independent demand, the optimal policy is characterized through dynamic programming and can be represented by base-stock levels.The section restricts order-up-to levels to integers without loss of optimality under the stated integer-demand and inventory setting.Source: §2 · pp. 10–11
• Censored observations reveal demand only below the chosen order-up-to level; otherwise they reveal only that demand is at least that level.Thus, data informativeness depends on the demand coordinates covered by the collection levels, not only on the number of trajectories.Source: §2 · p. 11
• Offline learning uses fixed pre-collected data, whereas online learning chooses policies over K episodes and accumulates regret from their deployed costs.In the offline setting, the learner cannot extend the coverage supplied by the behavior policy; online order-up-to choices determine both current costs and future data coverage.Source: §2 · pp. 11–12

• The model-based policy is obtained by running dynamic programming under the estimated demand distributions and taking the resulting base-stock sequence.Source: §3 · p. 12
• The decomposition theorem relates the cost difference between the optimal and model-based policies to discrepancies between the true and estimated demand models.The framework is intended to support later sample-complexity analyses under different demand models and observation protocols.Source: §3 · pp. 12, 14
• The cost gap of the estimated policy is non-increasing in initial inventory, so its maximum over initial inventories is attained at zero.Source: §3 · p. 13
• The decomposition exchanges policy-generated weight vectors, using the trajectory under the optimal policy in place of the one under the model-based policy; the residual from this exchange supports an upper bound.Source: §3 · p. 15

4. Performance Bound with Uniform Convergence of CDF

• The cost-gap decomposition yields a deterministic reduction from policy cost gap to uniform CDF estimation error, independent of how the estimator is obtained.The section notes that this reduction is coarse for censored feedback, the paper’s main focus.Source: §4 · pp. 15–16

4.1. Uncensored Non-Stationary Demand via Period-wise SAA

• ˜O(M²T²/ε²) samples suffice for an ε-accurate policy under uncensored non-stationary demand after burn-in N ≳ T⁴, matching Xie et al. (2024) up to logarithmic factors and improving the Halman (2020), Qin et al. (2023) bound.Source: §4.1 · p. 16

4.2. Uncensored Stationary Demand via Aggregated SAA

• ˜O(M²T/ε²) samples suffice for an ε-accurate policy under stationary uncensored demand after burn-in N ≳ T³.The aggregated estimator pools the NT period-level observations; the section also reports a matching lower bound and a strict separation from optimal-cost estimation.Source: §4.2 · pp. 17–18
• Stationary aggregation gains a factor T because all NT period-level demands share one distribution, unlike trajectory-level VC analyses that do not directly exploit this pooling.Source: §4.2 · p. 17
• The stationary-demand results show that learning a near-optimal base-stock policy can require fewer samples than estimating the optimal cost to the same accuracy.The section states that this separation is specific to the inventory structure and that policy-evaluation reductions are too coarse here.Source: §4.2 · p. 18

5. Offline Policy Learning via Upper-Biased SAA

• Upper-biased CDF estimates induce downward-biased base-stock levels, avoiding poorly covered high-demand coordinates.The resulting coverage condition focuses on coordinates relevant along the optimal-policy trajectory.Source: §5 · p. 18, §5.2 · pp. 20–21

5.1. Biased SAA: Construction and Statistical Properties

• The upper- and lower-biased CDF estimators are constructed sequentially from censored adaptive data, with a bias and closeness guarantee under the stated event.The offline algorithm uses the upper-biased estimator; the lower-biased version is introduced for later online policy design.Source: §5.1 · pp. 19–20

5.2. Sample Complexity under Censored Feedback

• Theorem 5.4 gives an offline sample-complexity guarantee in terms of effective sample size, which weights coordinate-level observation counts by optimal-policy visitation probabilities.Consequently, the data need not cover every demand coordinate uniformly; sufficient coverage is needed on coordinates visited by the optimal policy.Source: §5.2 · p. 21

5.3. Improved Sample Complexity under Stationary Demand

• Under stationary demand, pooling observations across periods increases effective sample size by a factor of T and improves the leading policy-learning error by a factor of T.The demand distributions share a common marginal, although informative observation counts still vary by coordinate under censoring.Source: §5.3 · pp. 22–23

5.4. Sample Complexity Lower Bounds

• Lower bounds show that the sample-complexity dependence in the offline results is minimax optimal over coverage classes, up to logarithmic and burn-in terms.The stationary-demand lower bound also supports optimality of the aggregated result up to logarithmic factors.Source: §5.4 · pp. 23–24

6. Online Policy Design via Lower-Biased SAA

• DP-LCB’s lower-biased CDF estimates optimism and prescribes larger base-stock levels, so higher inventory reveals demand at more coordinates.This couples low-cost policy selection with actively generating coverage for subsequent learning.Source: §6 · p. 25

6.1. Regret Analysis Through Self-Coverage Property

• The algorithm’s generated data achieve self-coverage growing at least linearly with prior episodes, supporting its regret guarantee.Episode estimation errors are weighted by visitation probabilities of the policy actually executed, rather than optimal-policy visitation probabilities.Source: §6.1 · pp. 27–28

6.2. Stationary Demand: Aggregated DP-LCB

• Under stationary demand, aggregating observations across periods increases effective sample size by a factor of T and sharpens the regret bound.The aggregated lower-biased model preserves the optimistic, non-increasing policy sequence.Source: §6.2 · pp. 28–29

6.3. Regret Lower Bounds

• The online regret bounds are near-optimal up to logarithmic factors and higher-order terms.The lower-bound results cover both non-stationary and stationary demand settings.Source: §6.3 · p. 29

7.1. Discretized Environments and Rounded Policies

• For η-grid policies, the original problem’s sub-optimality is at most the discretized problem’s gap plus 4(h∞ + b∞)T^2η.The guarantee is uniform over initial inventory levels.Source: §7.1 · p. 31
• For uncensored demand, smaller η sharpens the error bound but increases the computational cost of solving the finer-grid dynamic program.The learning rates of the cited SAA estimators do not depend on η.Source: §7.1 · p. 31
• The discretization reduction also applies to other CDF estimators, including tree-based, log-spline, and kernel-density methods.The cited examples include Ban et al. (2019), Ganggang and Shi (2024), and Fan et al. (2024a).Source: §7.1 · p. 31

7.2. Extension of Offline Policy Learning Results

• For offline censored learning, the general-demand guarantee replaces the rounded-data effective sample size with an integral-form effective sample size and adds a discretization term.The integral form generalizes the discrete effective sample size by replacing a sum over demand levels with an integral.Source: §7.2 · p. 32
• For offline learning, η ≍ 1/(NT)^3 is a safe choice that preserves the discrete-setting convergence rate up to polylog(NT) factors.In censored settings, decreasing η may increase a logarithmic term.Source: §7.2 · p. 32

7.3. Extension of Online Policy Learning Results

• For online learning, η ≍ 1/K yields the discrete-setting regret result up to additional log K factors.The extension also covers stationary demand, where the leading-order regret improves, although the supplied passage does not give the full rate.Source: §7.3 · p. 33

8.1. Offline Policy Learning

• Offline gaps decrease with more data when coverage is finite, remain flat when needed coordinates are never revealed, and are smaller for lower coverage ratios.Across behavior policies, gaps show similar dependence on effective sample size N ⋆.Source: §8.1 · p. 34, Figure 1 · p. 34
• DP-UCB avoids a large, nearly flat gap in the tested thin-coverage instance by biasing the CDF upward and keeping the learned stock level in the covered region.Vanilla DP and SAIL may underestimate a thinly covered crossing and jump across a dead zone to a higher stock level.Source: §8.1 · p. 34, Figure 2 · p. 35

8.2. Online Policy Learning

• DP-LCB achieves much smaller online regret than vanilla DP and SAIL-CE in the tested instance by lowering its CDF estimate, raising stock levels, and generating needed coverage.Vanilla DP and SAIL-CE remain at low stock levels and suffer nearly linear regret because they miss the high-demand spike.Source: §8.2 · p. 35, Figure 3 · p. 35

• The appendix states an equivalence result between lost-sales and backlogging dynamics for the inventory setting.It denotes corresponding quantities with superscripts B and LS, respectively.Source: A. Equivalence Between Backlogging and… · p. 36
• The proposition considers any initial inventory x ∈ [M]+ and relates inventory levels under lost-sales and backlogging dynamics.The proof establishes the relation inductively from the initial condition using the two transition equations.Source: A. Equivalence Between Backlogging and… · p. 36
• The proof proceeds by backward induction, using the Bellman equation for the backlogging system.It restricts minimization to y ≥ max{z,0} because feasible negative y is weakly dominated by zero when demand is nonnegative.Source: A. Equivalence Between Backlogging and… · p. 36

• The proof couples each demand realization d_t to η-rounded demand ˜d_t satisfying d_t ≤ ˜d_t < d_t + η.The rounded demand follows the distribution used in the η-discretized problem.Source: §B.1 · p. 37
• Each period’s newsvendor cost is (h∞ + b∞)-Lipschitz, allowing the proof to bound expected total-cost changes under rounded demand.The argument compares the original base-stock policy’s cost with cost under the rounded demand distribution.Source: §B.1 · p. 37
• For an η-grid policy, the discretized cost matches its rounded-environment cost; rounding any inventory level to a nearby grid point incurs a bound proportional to η.The stated bound is 2T^2(h∞ + b∞)η.Source: §B.1 · p. 37

B.2. Proof of Equation (7.4)

• The proof defines η-rounded demand ˜d_t so that d_t ≤ ˜d_t < d_t + η, then uses its induced dataset to compare effective sample sizes.The rounded coordinate counts are linked to counts in the original data at threshold jη.Source: §B.2 · p. 38
• The reciprocal effective-sample-size difference between the η-discretized and rounded datasets is bounded by Tη.The passage gives |1/N^η,⋆ − 1/˜N⋆| ≤ Tη/B ≤ Tη.Source: §B.2 · p. 38
• The proof controls the base-stock policy gap and visiting-probability gap to establish the comparison used in Equation (7.4).Its argument defines λ_t(u) from the coordinate count N_t(u) and bounds it between zero and one.Source: §B.2 · pp. 38–39

C. Details of the Numerical Experiments

• All experiments use seasonal, non-stationary demand on discrete support [M]+ with M = 30 and costs h = 1, b = 3; reported sub-optimality gaps are computed exactly by evaluating the learned policy under the true model via DP.Source: C. Details of the Numerical Experiments · p. 40
• For the pessimism experiment, the logging policy targets ℓt with probability 0.95 and M with probability 0.05; online methods begin uninformed, so their first episode orders to M and observes uncensored demand.The described pessimism setup therefore gives only thin coverage at ℓt and higher coordinates.Source: C. Details of the Numerical Experiments · p. 40
• SAIL is run on the same logged trajectories and evaluated by exact dynamic programming; its online variant, SAIL-CE, repeatedly resolves the offline procedure and acts greedily without extra exploration.SAIL returns a policy table that need not be a base-stock policy.Source: C. Details of the Numerical Experiments · p. 40

EC.1.1. Technical Lemmas and Notations.

• A time-reversed random walk provides a probabilistic interpretation of At, and under a base-stock policy the post-order inventory is max{st, xt}.The appendix also introduces events and interval indicator vectors for later use.Source: EC.1.1. Technical Lemmas and Notations · pp. 45–46

EC.1.2. Proof of Proposition 3.2

• The trajectory-visiting-probability matrix representation supports the result that Mk:t−1Et is non-negative and non-increasing.The proof section also states that Proposition 3.2’s monotonicity claim is covered by this matrix property.Source: EC.1.2. Proof of Proposition 3.2 · pp. 46–47

EC.2.1. Proof of Corollary 4.1

• The Corollary 4.1 proof bounds the propagation term by order M(h∞ + b∞)(Tε + T^3ε^2), using summation by parts and a bulk-tail decomposition; the optimal-policy expected overshooting gap is bounded by O(1).The stated naive bound on the propagation term would give O(MT^2ε), motivating the more careful decomposition.Source: EC.2.1. Proof of Corollary 4.1 · pp. 53–54
• The Corollary 4.1 proof combines an adjoint relation with a recursion and uses the terminal condition gT+1 = 0 and g1 ≥ 0 in its final inequality.The passage states that these conditions give ⟨1,gT+1 − g1⟩ ≤ 0.Source: EC.2.1. Proof of Corollary 4.1 · p. 57

EC.2.2. Proof of Proposition EC.2.2

• The proof of Proposition EC.2.2 obtains the desired O(b∞M) bound after constructing a backward time-index set and bounding a summation by induction.The set starts at t and adds earlier indices when their s⋆ values exceed the current set’s supremum.Source: EC.2.2. Proof of Proposition EC.2.2 · pp. 57–59

EC.2.3. Proof of Lemma EC.2.4

• The Lemma EC.2.4 proof bounds a probability involving threshold-crossing events by decomposing it into two events and applying a union bound.The displayed step gives P(B1 ∪ B2) ≤ P(A1 ∪ A2) ≤ P(A1) + P(A2).Source: EC.2.3. Proof of Lemma EC.2.4 · p. 60

EC.4.1.1. Proof of Lemma EC.3.1

• Lemma EC.3.1 relates the empirical radius ˜C_j to C_j, validating ˜C_j for constructing upper and lower confidence estimators.Its proof bounds the difference between the empirical and true variance-like terms using the estimation error for F(j).Source: EC.3. Proof of Results in Section 5 · pp. 60–61, EC.4.1.1. Proof of Lemma EC.3.1 · p. 69

EC.4.1.2. Proof of Lemma EC.3.2

• If F(j)−F(j_0)≤A C_{j_0} for j_0≤j, Lemma EC.3.2 bounds C_{j_0} by (2+4A)C_j.The proof uses the assumed difference condition and a weighted AM-GM inequality.Source: EC.3. Proof of Results in Section 5 · p. 61, EC.4.1.2. Proof of Lemma EC.3.2 · p. 70

Proof of Lemma EC.3.3.

• Lemma EC.3.3 states a deterministic inequality for 0≤p≤u≤1 and ξ≥0, with d:=u−p, covering any positive constants a,b.It supplies two statements for later use.Source: EC.3. Proof of Results in Section 5 · p. 61

Proof of Proposition 5.2.

• Under event (5.2), induction establishes that the UCB estimate is at least F(j) and the LCB estimate is at most F(j).The proof uses the radius relation C_j ≤ ˜C_j.Source: Proof of Proposition 5.2 · pp. 61–62

EC.3.2. Proof of Lemma 5.3

• The proof of Lemma 5.3 uses induction over time to establish the stated sign condition on ΔD_k.The induction step checks the signs of two terms, including one using summation by parts.Source: EC.3.2. Proof of Lemma 5.3 · pp. 62–63

EC.3.3. Proof of Theorem 5.4 and Theorem 5.6

• Theorem 5.4’s proof combines the cost decomposition with a high-probability concentration bound; the proof of Theorem 5.6 follows by substituting aggregate counts and replacing N with N_T.Theorem 5.4’s proof concludes with the bound stated in that theorem.Source: EC.3.3. Proof of Theorem 5.4 and… · pp. 63, 64, 68

Proof of Lemma EC.3.4.

• The proof of Lemma EC.3.4 partitions its index set into extreme and middle parts, defining the extreme part by p_m(1−p_m)≤a.The lemma’s stated setting assumes a monotone sequence p_m and non-negative sequences p_m,h_m.Source: EC.3.3. Proof of Theorem 5.4 and… · p. 65, Proof of Lemma EC.3.4 · p. 71

EC.4. Proof of Corollary 5.5

• The proof of Corollary 5.5 combines a high-probability dichotomy with Theorem 5.4, applying each at confidence level δ/2 and using a union bound.The dichotomy states that at least one of two alternatives holds for every t,j with probability at least 1−δ.Source: EC.4. Proof of Corollary 5.5 · pp. 68–69

Proof of Lemma EC.3.4.

• For Lemma EC.3.4, the proof partitions middle probabilities into O(log(e/a)) dyadic odds-ratio blocks and combines their bounds with the extreme-part bound.Within-block cross terms are controlled using the kernel pm′(1 − pm).Source: Proof of Lemma EC.3.4 · p. 71

EC.4.1.5. Proof of Lemma EC.3.5

• The Lemma EC.3.5 proof obtains the variance identity by expanding Zt,j, using nested events for m < m′ and accounting for diagonal terms.Source: EC.4.1.5. Proof of Lemma EC.3.5 · p. 72

EC.5.1. Proof of Lemma 6.1

• If event (5.2) holds for every t, then the lower-confidence-bound base-stock levels satisfy st ≥ s⋆t for all t.The proof establishes this ordering by induction using reversed inequalities.Source: EC.5.1. Proof of Lemma 6.1 · pp. 72–73
• The lower-confidence-bound CDF sequence is non-decreasing, inducing a non-increasing sequence of base-stock levels by DP monotonicity.The proof bounds the iterated CDF estimates using the maximum update in Algorithm 2 and Proposition 5.2.Source: EC.5.1. Proof of Lemma 6.1 · p. 73

EC.5.2. Proof of Proposition 6.2

• The proof of Proposition 6.2 adapts Theorem 5.4 using episode-k quantities from lower-biased CDFs, with optimistic bias reversing the signs induced by pessimism.The proof conditions on the event E(k) and on F_k, and states that its resulting bound is the one in Proposition 6.2.Source: EC.5.2. Proof of Proposition 6.2 · pp. 73, 76

EC.5.3. Proof of Proposition 6.3 and Theorem 6.4

• The proof of Theorem 6.4 combines Propositions 6.2 and 6.3 to bound every episode’s cost gap with probability at least 1 −δ.The proof uses a coverage dichotomy to establish Proposition 6.3.Source: EC.5.3. Proof of Proposition 6.3 and… · pp. 76–77

EC.5.4. Proof of Theorem 6.5

• With probability at least 1 −δ, aggregated coverage satisfies N_agg^(k) ≥ c0(k−1)T log(KMT/δ) for every k, supporting the proof of Theorem 6.5.The proof combines this coverage result with an aggregated per-episode cost-gap bound and sums the gaps.Source: EC.5.4. Proof of Theorem 6.5 · p. 78, Proof of Theorem 6.5 · p. 79

Proof of Theorem 6.5.

• For Theorem 6.5, the proof combines an aggregated per-episode cost-gap bound with self-generated coverage, then sums the episode gaps.The proof separately handles the first episode, which has no historical data, using a trivial bound.Source: Proof of Theorem 6.5 · p. 79

EC.6. Proof of Lower Bound Results

• The lower-bound proofs handle coverage fraction p by setting censoring levels to M on ⌈Np⌉ trajectories and to 0 on the rest, whose observations contribute neither KL divergence nor coverage counts.This reduces the experiment to the fully informative case with N replaced by ⌈Np⌉; the text says Theorem 6.6 follows directly from Theorems 5.7 and 5.8 in the uncensored setting.Source: EC.6. Proof of Lower Bound Results · p. 79
• The lower-bound framework controls the minimax data-driven loss using binary-testing, Assouad, and Bernoulli-distribution lemmas.The minimax criterion takes the minimum over data-driven algorithms and the maximum over problem instances.Source: EC.6. Proof of Lower Bound Results · p. 80

EC.6.1. Proof of Lemma 4.6

• For Lemma 4.6, the proof adapts Ren et al. (2021)’s single-action MDP construction to a two-support demand inventory problem and estimates the optimal policy value.The two instances have different demand distributions, and the loss is absolute error in the optimal cost.Source: EC.6.1. Proof of Lemma 4.6 · p. 80

EC.6.2. Proof of Theorem 5.7

• With ε < 1/(2T) and T ≥ 3T′, the verified separation is Δ_j = c∞Mε/2; for every z ∈ ZT′, D(P_z^⊗N ∥ P_z(k)^⊗N) ≤ 8Nε².Source: EC.6.2. Proof of Theorem 5.7 · pp. 83–84

EC.6.3. Proof of Theorem 5.8

• For Theorem 5.8, the two stationary demand instances yield a separation lower bound L(π,P+) + L(π,P−) ≥ εc∞MT when the stated condition on ε holds.This verifies (EC.6.1) with Δ1 = εc∞MT.Source: EC.6.3. Proof of Theorem 5.8 · p. 85