Lemma 12 — Σ_{k≤L} ρ^{⌈k^β⌉} ≤ Σ_{k≤L} ρ^{k^β} ≤ Γ(1/β)(1/β)/(ln(1/ρ))^{1/β}
ProvedAdaptiveBaseStock.Regret.geometric_ceil_sumgamma-functionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysis
For every , and ,
where is the Gamma function.
The bound is uniform in ; it sums the geometrically decaying bias of the gradient estimates over cycles of length .
Preamble
import Mathlib import Definitions.Def_AdaptiveBaseStock_Regret_Algorithm
Formal statement
namespace AdaptiveBaseStock.Regret
/-- Lemma 12, p. 25: for `ρ, β ∈ (0, 1)` and `L ≥ 1`,
`Σ_{k=1}^L ρ^{⌈k^β⌉} ≤ Σ_{k=1}^L ρ^{k^β} ≤ Γ(1/β)(1/β) / (ln(1/ρ))^{1/β}`. -/
theorem geometric_ceil_sum (ρ β : ℝ) (hρ0 : 0 < ρ) (hρ1 : ρ < 1) (hβ0 : 0 < β) (hβ1 : β < 1)
(L : ℕ) (hL : 1 ≤ L) :
∑ k ∈ Finset.Icc 1 L, ρ ^ cycleLen β k ≤ ∑ k ∈ Finset.Icc 1 L, ρ ^ ((k : ℝ) ^ β) ∧
∑ k ∈ Finset.Icc 1 L, ρ ^ ((k : ℝ) ^ β)
≤ Real.Gamma (1 / β) * (1 / β) / (Real.log (1 / ρ)) ^ (1 / β) := by sorry
end AdaptiveBaseStock.Regret
Source
Huh, Janakiraman, Muckstadt, Rusmevichientong, An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand, working paper, February 8, 2007 (published version: Math. Oper. Res., 2009, DOI 10.1287/moor.1080.0367), Lemma 12, p. 25 (proof in Appendix A, p. 32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.