Lemma 1, p. 14 — for the number of phases satisfies
ProvedPrimalDualPricing.Regret.lemma_1learning-algorithmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and . The number of phases of Algorithm 1,
satisfies
The number of phases enters every union bound of the analysis, so this bound keeps them polynomial in .
Preamble
import Mathlib import Definitions.Def_PrimalDualPricing_Regret_Params
Formal statement
namespace PrimalDualPricing.Regret
/-- Lemma 1 (Chen–Gallego, arXiv:1812.09234v3, p. 14). For every `ε > 0` and `n ≥ 3`, the total number of
phases `K = min{k ≥ 1 : (Δ̄^{(k)})² ≤ n^{−1/2}(log n)^{2+16ε}}` of Algorithm 1 satisfies `K ≤ 3 log n + 3`. -/
theorem lemma_1 (eps : ℝ) (heps : 0 < eps) (n : ℕ) (hn : 3 ≤ n) :
(numPhases eps n : ℝ) ≤ 3 * Real.log n + 3 := 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 1 (parameters p. 13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.