Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7 — expanding-projection AIM regret without a known newsvendor bound

Proved
AIMInventory.UnknownBound.theorem_7

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

censored-demandinventoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-gradient

Consider the perishable inventory system with i.i.d. nonnegative demand, holding cost h>0h>0h>0 and shortage cost b>0b>0b>0. Let QQQ be the single-period expected newsvendor cost and yNVy^{NV}yNV the newsvendor quantity. For any 0<δ<1/20<\delta<1/20<δ<1/2, run modified AIM from an initial target y^1δ∈[0,1]\hat y^\delta_1\in[0,1]y^​1δ​∈[0,1]: after period ttt, it uses the observable signal Ht=hH_t=hHt​=h if demand is below its current target and Ht=−bH_t=-bHt​=−b otherwise, takes step size 1/(max⁡{b,h}t)1/(\max\{b,h\}\sqrt t)1/(max{b,h}t​), and projects the next target onto [0,tδ/2][0,t^{\delta/2}][0,tδ/2]. For every T≥1T\ge1T≥1,

E ⁣[1T∑t=1TQ(y^tδ)]−Q(yNV)≤max⁡{b,h}(1T1/2−δ+1T1/2+(yNV)1+2/δT).\mathbb E\!\left[\frac1T\sum_{t=1}^T Q(\hat y^\delta_t)\right]-Q(y^{NV})\le\max\{b,h\}\left(\frac1{T^{1/2-\delta}}+\frac1{T^{1/2}}+\frac{(y^{NV})^{1+2/\delta}}{T}\right).E[T1​t=1∑T​Q(y^​tδ​)]−Q(yNV)≤max{b,h}(T1/2−δ1​+T1/21​+T(yNV)1+2/δ​).

The explicit bound shows that the average expected cost approaches the newsvendor benchmark even though the policy uses no upper bound on the benchmark level.

Formalization Note The paper leaves the modified run's first target unspecified; [0,1][0,1][0,1] is the initial interval needed for the stated T=1T=1T=1 guarantee. The demand-law structure additionally assumes strictly positive finite mean; the positive-mean part is not used by this perishable result. The policy is a deterministic function of an i.i.d. demand path with paper period ttt at path coordinate t−1t-1t−1; its decisions depend only on earlier coordinates. Real powers are used for the projection radius and bound.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Definitions.Def_AIMInventory_UnknownBound_AIM

open MeasureTheory
Formal statement
namespace AIMInventory.UnknownBound

/-- Theorem 7: average expected newsvendor regret of expanding-projection
AIM in the perishable inventory case, without a known upper bound. -/
theorem theorem_7 (P : CappedBaseStock.DemandLaw) (δ b h y₁ : ℝ) (T : ℕ)
    (hδ : δ ∈ Set.Ioo (0 : ℝ) (1 / 2)) (hb : 0 < b) (hh : 0 < h)
    (hy₁ : y₁ ∈ Set.Icc (0 : ℝ) 1) (hT : 1 ≤ T) :
    (∫ d : CappedBaseStock.DemandPath,
        ((∑ t ∈ Finset.Icc 1 T, cost P h b (modAimTarget δ b h y₁ d t)) / (T : ℝ))
          ∂CappedBaseStock.demandPathLaw P) - cost P h b (newsvendor P h b) ≤
      max b h *
        (1 / Real.rpow (T : ℝ) ((1 / 2 : ℝ) - δ) +
         1 / Real.rpow (T : ℝ) (1 / 2 : ℝ) +
         Real.rpow (newsvendor P h b) (1 + 2 / δ) / (T : ℝ)) := by sorry

end AIMInventory.UnknownBound
Source
Huh & Rusmevichientong, A Non-Parametric Asymptotic Analysis of Inventory Planning with Censored Demand, Math. Oper. Res. (2009), author's manuscript, p. 11, Theorem 7; https://doi.org/10.1287/moor.1080.0355
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