An inventory policy chooses how much stock to order before demand is observed. Its quality is assessed by the holding and backlogging costs it incurs on future demand. A policy chosen to perform well on historical demand can overfit those observations. A useful statistical guarantee therefore controls the difference between historical and future costs simultaneously over the policies that the procedure may select. Xie, Ma and Xin establish such guarantees for stationary base-stock, , and nonstationary base-stock policy classes.
This formalization covers the principal bound families in that paper. Its first goal is the expected generalization and estimation bound for nonstationary base-stock policies with no fixed ordering cost, Corollary 4.10. Its supporting targets include Theorem 4.9 and the constructive product-sample partition in Lemma 4.12. The other principal bounds remain in the explicit scope below and await their own full Lean declarations. The companion inventory-information project needs these results as proved dependencies; merely citing the paper does not close that project's formal proof obligations.
There are periods, a deterministic lead time , and demand bounded by . The first order arrives in period . Average loss means the sum of holding and backlogging costs in periods , divided by the positive horizon . The initial pipeline is empty, and initial inventory is nonpositive for the base-stock models. Holding and backlogging cost coefficients are . Nonstationary base-stock policies in the first goal have no fixed ordering cost and use levels .
The Lean model indexes the first period by zero. It uses the source's explicit finite-maximum formula for post-replenishment inventory, with the demand interval summed up to, but excluding, the observation period. In mathematical notation the inventory in period is . Cost is evaluated after subtracting the current demand . This is a backlog model; applications to lost sales require a separate equivalence argument.
Data comprise IID demand trajectories from a probability measure on the bounded trajectory space. Different periods of the same trajectory can be dependent. Generalization error is the one-sided supremum , where is expected average loss and is empirical average loss. Estimation error is , for an empirical minimizer and a best-in-class population policy. It is not the error relative to every history-dependent inventory policy. These conventions follow Sections 3 and 4.
The first goal, Corollary 4.10, asserts the existence of one absolute constant such that
The constant is quantified before the horizon, lead time, support, costs, demand distribution, sample size, and policy selections. The first inequality explicitly refers to actual minimizers, with an integrable selected risk. The GE conclusion holds independently of whether a particular selector has been supplied.
Its principal complexity target is Theorem 4.9: for each relevant period and , the normalized inventory class has fat-shattering dimension at most . The Lean statement says directly that every -shattered indexed sample has cardinality at most that number. It uses the source convention of a strict upper label and non-strict lower label.
Lemma 4.12 partitions all product indices into groups of indices. Every coordinate of every group traverses the original row indices exactly once. The formal statement uses a bijection between anchor-offset pairs and complete index tuples, together with a coordinate-permutation assertion. The dimension is positive, and and are included.
The full scope also retains Theorem 4.1 and Corollary 4.2 (stationary policies), Theorem 4.4 and Corollary 4.5 ( upper bounds), Theorem 4.7 and Corollary 4.8 ( fat-shattering and GE lower bounds), and the expected Product ERM comparison in equation (4.7). They are catalogued with their assumptions but are not yet all encoded. The GE lower bound is not asserted to be a minimax policy-regret lower bound.
The nonstationary policy vector grows with the horizon, while the expected average-loss bound has no horizon factor. A verified version supplies a reusable statistical ingredient for finite-horizon inventory learning. Total-cost bounds require multiplication by the horizon. Absolute uniform deviation, period-dependent costs, high-probability statements, initial-state reductions, and censoring require further bridge theorems. They are not attributed to Corollary 4.10 without those proofs.
The cyclic partition has a complete locally checked Lean proof with axiom dependencies only propext and Quot.sound. The two statistical targets remain open. Neither a drafted declaration nor a local proof is described as a server-verified contribution.
Ordinary pseudodimension can grow with the horizon for the nonstationary class, so it does not by itself give the desired horizon-free rate. A full proof needs scale-sensitive complexity, probability, and integration infrastructure. For Product ERM, coordinate independence must be explicit: the groups in the partition need not be independent of each other. The expected comparison transfers upper bounds; it cannot reverse direction to transfer a GE lower bound.
The shared environment is Lean 4.33.1 and Mathlib revision 0df444a360eaa60ab8c11dca51a86af692955474. Demand and policy coordinates are bounded real subtypes with their usual measurable structures. Probability is over IID whole trajectories. Finite maximum indices are nonempty. Positive prevent zero denominators in the targets. General definitions remain total, and their behavior outside these hypotheses is exposed in the independent read-backs.
Complete proofs must establish the boundedness and measurability needed for the real suprema and integrals to have their usual meaning. They may not assume the convergence bound, replace arbitrary probability measures by finite-support distributions, or silently restrict the policy class. The branch additionally needs explicit unbounded-domain conventions when holding or backlogging costs vanish. Reusable contributions include shattering, symmetrization, entropy bounds, selection and integrability facts, and finite-product sampling.
namespace XMX
theorem nonstationary_expected_bound :
∃ C : ℝ, 0 < C ∧ ∀ (T L N : ℕ), 0 < T → 0 < N →
∀ (U h b : ℝ), 0 < U → h ∈ Set.Icc (0 : ℝ) 1 → b ∈ Set.Icc (0 : ℝ) 1 →
∀ (μ : Measure (Demand T L U)) [IsProbabilityMeasure μ],
expectedGE N μ (loss T L U h b) ≤ C * (((L : ℝ) + 1) * U) / Real.sqrt N ∧
∀ (select : (Fin N → Demand T L U) → Levels T L U)
(pstar : Levels T L U),
(∀ data p, empiricalRisk N (loss T L U h b) data (select data) ≤
empiricalRisk N (loss T L U h b) data p) →
(∀ p, risk μ (loss T L U h b) pstar ≤ risk μ (loss T L U h b) p) →
Integrable (fun data => risk μ (loss T L U h b) (select data))
(Measure.pi (fun _ : Fin N => μ)) →
expectedEE N μ (loss T L U h b) select pstar ≤
expectedGE N μ (loss T L U h b) := by sorry
end XMXThere is one absolute C>0 such that for every positive T,N,U, lead time L>=0, h,b in [0,1], and joint demand law, expected one-sided GE is at most C(L+1)U/sqrt(N). Expected ERM excess risk relative to a population minimizer is no larger than expected GE for every empirical selector with integrable selected risk. Loss is the average over the final T periods; K=0. No independence across periods is imposed.