Lemma 2, p. 14 — for
ProvedPrimalDualPricing.Regret.lemma_2learning-algorithmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and let satisfy . Then the total length of the phases before the last phase satisfies
The last phase therefore takes at least half of the season.
Formalization Note The page states the threshold only. The condition is added because is defined only for .
Preamble
import Mathlib import Definitions.Def_PrimalDualPricing_Regret_Params
Formal statement
namespace PrimalDualPricing.Regret
/-- Lemma 2 (Chen–Gallego, arXiv:1812.09234v3, p. 14). For `ε > 0`, `T > 0` and `n ≥ 3` with
`n ≥ exp((8/T)^{1/ε})`, the total length of the phases before phase `K` satisfies
`∑_{k=1}^{K−1} τ^{(k)} ≤ T/2`. (`n ≥ 3` is added: below it `K` is undefined.) -/
theorem lemma_2 (eps T : ℝ) (heps : 0 < eps) (hT : 0 < T) (n : ℕ) (hn : 3 ≤ n)
(hn' : Real.exp ((8 / T) ^ (1 / eps)) ≤ n) :
∑ k ∈ Finset.Ico 1 (numPhases eps n), tau eps n k ≤ T / 2 := by sorry
end PrimalDualPricing.Regret
Source
Chen, Gallego, A Primal-dual Learning Algorithm for Personalized Dynamic Pricing with an Inventory Constraint, arXiv:1812.09234v3, p. 14, Lemma 2 (parameters p. 13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.