Theorem 6 — non-perishable AIM: if γ ≤ ρ max{b,h}/(hȳ), the excess y_t − ŷ_t is at most the queue Z_t(ρ)
ProvedAIMInventory.Known.theorem_6Consider the AIM algorithm with non-perishable inventory, cost parameters , upper bound , scale and starting level , and let . If
then for every demand path and every ,
where and .
The excess of the implemented level over the target is the price of carrying inventory over; this theorem dominates it by the waiting time of a single-server queue whose service times shrink like . It is the paper's link between stochastic gradient descent and queueing.
Formalization Note The paper says "with probability one"; the inequality holds along every demand path and is stated that way. Of Assumption 1, only the constants and enter: the inequality does not use or , so those are not hypotheses. The paper's proof writes for . and are implicit in the paper (they appear in denominators).
import Mathlib import Definitions.Def_AIMInventory_Known_AIM import Definitions.Def_AIMInventory_Known_Queue
namespace AIMInventory.Known
/-- Theorem 6, p. 9: in the non-perishable case, if `γ ≤ ρ max{b, h}/(hȳ)`, then along every
demand path and for every `t ≥ 1` the excess `y_t − ŷ_t` of the AIM run is at most `Z_t(ρ)`. -/
theorem theorem_6 (h b γ ybar ρ yhat1 : ℝ) (hh : 0 < h) (hb : 0 < b) (hγ : 0 < γ)
(hybar : 0 < ybar) (hρ : 0 < ρ) (hyhat1 : yhat1 ∈ Set.Icc 0 ybar)
(hγρ : γ ≤ ρ * max b h / (h * ybar))
(d : CappedBaseStock.DemandPath) (t : ℕ) (ht : 1 ≤ t) :
aimLevel .nonPerishable ybar γ b h yhat1 d t - aimTarget .nonPerishable ybar γ b h yhat1 d t
≤ auxQueue ρ d t := by sorry
end AIMInventory.Known
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.