Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — AIM's average expected cost is within (γ+1/γ)ȳ max{b,h}/√T (perishable) and C/√T (non-perishable) of Q(y^NV)

Proved
AIMInventory.Known.theorem_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

censored-demandinventoryonline-convex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let demands D1,D2,⋯≥0D_1, D_2, \dots \ge 0D1​,D2​,⋯≥0 be i.i.d. with finite positive mean, let h,b>0h, b > 0h,b>0, and let Q(y)=h E[y−D]++b E[D−y]+Q(y) = h\,E[y-D]^+ + b\,E[D-y]^+Q(y)=hE[y−D]++bE[D−y]+ with newsvendor quantity

yNV=inf⁡{y≥0∣F(y)≥b/(b+h)},y^{NV} = \inf\{y \ge 0 \mid F(y) \ge b/(b+h)\},yNV=inf{y≥0∣F(y)≥b/(b+h)},

FFF the distribution function of D1D_1D1​. Under Assumption 1 the manager knows yˉ>0\bar y > 0yˉ​>0 with yNV≤yˉy^{NV} \le \bar yyNV≤yˉ​. Run the AIM algorithm with scale γ>0\gamma > 0γ>0 and any starting level y^1∈[0,yˉ]\hat y_1 \in [0,\bar y]y^​1​∈[0,yˉ​], and let (yt:t≥1)(y_t : t \ge 1)(yt​:t≥1) be its order-up-to levels. Then:

  1. Perishable inventory. For every T≥1T \ge 1T≥1,
E[1T∑t=1TQ(yt)]−Q(yNV)≤(γ+1γ)yˉmax⁡{b,h}T.E\Big[\frac1T\sum_{t=1}^T Q(y_t)\Big] - Q(y^{NV}) \le \Big(\gamma + \frac1\gamma\Big)\frac{\bar y\max\{b,h\}}{\sqrt T}.E[T1​t=1∑T​Q(yt​)]−Q(yNV)≤(γ+γ1​)T​yˉ​max{b,h}​.
  1. Non-perishable inventory. Suppose moreover that 0<ρ<E[D1]0 < \rho < E[D_1]0<ρ<E[D1​] (the second half of Assumption 1), E[D16]<∞E[D_1^6] < \inftyE[D16​]<∞ and γ≤ρmax⁡{b,h}/(hyˉ)\gamma \le \rho\max\{b,h\}/(h\bar y)γ≤ρmax{b,h}/(hyˉ​). Then there is a constant CCC such that for every T≥1T \ge 1T≥1,
E[1T∑t=1TQ(yt)]−Q(yNV)≤CT.E\Big[\frac1T\sum_{t=1}^T Q(y_t)\Big] - Q(y^{NV}) \le \frac{C}{\sqrt T}.E[T1​t=1∑T​Q(yt​)]−Q(yNV)≤T​C​.

The algorithm sees only censored sales and does not know the demand distribution, yet its long-run average cost approaches the newsvendor cost, which is the optimal cost of a manager who knows the distribution, at rate 1/T1/\sqrt T1/T​.

The constant CCC may depend on everything except TTT. The paper's explicit formula (9) for CCC rests on Proposition 4 (i), which is false as printed; with the corrected Proposition 4 (i) the same proof gives

C=(γ+1γ)yˉmax⁡{b,h}+2hρ(1+21π22⋅E[(D1−ED1)6](ED1−ρ)6).C = \Big(\gamma + \frac1\gamma\Big)\bar y\max\{b,h\} + 2h\rho\Big(1 + \frac{21\pi^2}{2}\cdot\frac{E[(D_1-E D_1)^6]}{(E D_1 - \rho)^6}\Big).C=(γ+γ1​)yˉ​max{b,h}+2hρ(1+221π2​⋅(ED1​−ρ)6E[(D1​−ED1​)6]​).

This formula is not part of the statement.

Formalization Note The AIM run is defined from the demand path, and the expectation is the integral over the i.i.d. path law; the integrand is bounded on the run (all levels lie in [0,yˉ][0,\bar y][0,yˉ​]), so the integral is a genuine expectation. h,b,yˉ>0h, b, \bar y > 0h,b,yˉ​>0 are implicit in the paper (they appear in denominators), and the positive mean of D1D_1D1​ is part of the reused demand-law structure (in the non-perishable case it already follows from 0<ρ<E[D1]0 < \rho < E[D_1]0<ρ<E[D1​]). In the non-perishable case the constant is chosen after ρ\rhoρ and all other data, before TTT.

Preamble
import Mathlib
import Definitions.Def_AIMInventory_Known_AIM
open MeasureTheory
open scoped NNReal
Formal statement
namespace AIMInventory.Known

/-- Theorem 2, p. 7: under Assumption 1 (`y^NV ≤ ȳ`), the AIM run satisfies, for every `T ≥ 1`,
`E[(1/T) Σ_{t=1}^T Q(y_t)] − Q(y^NV) ≤ (γ + 1/γ) ȳ max{b, h} / √T` in the perishable case; and
in the non-perishable case, if moreover `0 < ρ < E[D_1]`, `E[D_1^6] < ∞` and
`γ ≤ ρ max{b, h}/(hȳ)`, there is a constant `C` with
`E[(1/T) Σ_{t=1}^T Q(y_t)] − Q(y^NV) ≤ C / √T` for every `T ≥ 1`. -/
theorem theorem_2 (P : CappedBaseStock.DemandLaw) (h b γ ybar yhat1 : ℝ)
    (hh : 0 < h) (hb : 0 < b) (hγ : 0 < γ) (hybar : 0 < ybar)
    (hyhat1 : yhat1 ∈ Set.Icc 0 ybar)
    (hNV : ((LostSalesOrderUpTo.Asymptotic.newsvendorLevel P.law h b : ℝ≥0) : ℝ) ≤ ybar) :
    (∀ T : ℕ, 1 ≤ T →
      avgExpectedCost P .perishable ybar γ b h yhat1 T
          - Q P h b (LostSalesOrderUpTo.Asymptotic.newsvendorLevel P.law h b : ℝ)
        ≤ (γ + 1 / γ) * (ybar * max b h / Real.sqrt T)) ∧
    (∀ ρ : ℝ, 0 < ρ → ρ < CappedBaseStock.mean P →
      Integrable (fun x : ℝ≥0 => (x : ℝ) ^ 6) P.law →
      γ ≤ ρ * max b h / (h * ybar) →
      ∃ C : ℝ, ∀ T : ℕ, 1 ≤ T →
        avgExpectedCost P .nonPerishable ybar γ b h yhat1 T
            - Q P h b (LostSalesOrderUpTo.Asymptotic.newsvendorLevel P.law h b : ℝ)
          ≤ C / Real.sqrt T) := by sorry

end AIMInventory.Known
Source
Huh & Rusmevichientong, A Non-Parametric Asymptotic Analysis of Inventory Planning with Censored Demand, Math. Oper. Res. (2009), author's manuscript, p. 7, Theorem 2 (with Assumption 1, p. 7; proof in §2.4, p. 10)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me