App. A.1, p.36 — for
ProvedContAssortLogit.harmonic_boundassortment-optimizationmultinomial-logitp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1regretrevenue-managementstochastic-approximation
For every and every integer ,
This closes the regret bound: summing the rate of Lemma 5 over the horizon costs a logarithmic factor.
Differences from the source:
- generalization: (the policy's parameter) → every ; reason: the bound uses only ; the paper's is a special case
- reading: → the natural logarithm ; reason: the paper gives no base; the natural logarithm is the convention of the paper's analysis and the strongest of the usual readings
Preamble
import Mathlib open MeasureTheory Set
Formal statement
namespace ContAssortLogit
/-- **The harmonic bound** (Peeters, den Boer & Mandjes, arXiv:1807.06497v4, App. A.1, p.36):
`Σ_{t=1}^T (t + β)⁻¹ ≤ 3 log T` for all `T ≥ 2`, for every `β ≥ 0`. -/
theorem harmonic_bound (β : ℝ) (hβ : 0 ≤ β) (T : ℕ) (hT : 2 ≤ T) :
∑ t ∈ Finset.Icc 1 T, 1 / ((t : ℝ) + β) ≤ 3 * Real.log T := by sorry
end ContAssortLogit
Source
Peeters, den Boer, Mandjes, Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information, arXiv:1807.06497v4, App. A.1, p.36, "by ∑_{t=1}^T (t + β)⁻¹ ⩽ 3 log T for all T ⩾ 2"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.