App. A.1, p.35 — the SAP iterates stay in
ProvedContAssortLogit.rho_mem_Iccassortment-optimizationmultinomial-logitp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1regretrevenue-managementstochastic-approximation
Let be a revenue function, , and . Then the iterates of SAP satisfy
The choice makes every step size at most , so each update is a convex combination of and the observed revenue .
Differences from the source:
- encoding: and are functions on → with every hypothesis stated on (or ); reason: values outside never enter any quantity; same instances
- reading: , an empty set for → for ; reason: the minimum is undefined there, and is allowed; is the continuous, monotone extension, and the offered assortment is a null set
- encoding: periods → indices (so is index and ); reason: Lean's natural numbers start at 0; same sequence
- encoding: for the iterates of SAP → for the SAP iterates along every sequence of (no-)purchases; reason: the iterate is a deterministic function of the purchases, so this is the same as holding on every realization
- generalization: SAP with (the standing choice in the proof of Theorem 1) → any (the range of §4.2); reason: the claim uses only and ; every is such an
Preamble
import Mathlib import Definitions.Def_ContAssortLogit_Model import Definitions.Def_ContAssortLogit_Policy open MeasureTheory Set
Formal statement
namespace ContAssortLogit
/-- **The SAP iterates stay in `[0, 1]`** (Peeters, den Boer & Mandjes, arXiv:1807.06497v4,
App. A.1, p.35): "by our choice of `β ≥ max{0, α − 1}` it follows that `ϱ_t ∈ [0, 1]` for all
`t ∈ ℕ`". This holds for every sequence of (no-)purchases.
**Formalization Note.** Index `n` is the paper's period `n + 1`. -/
theorem rho_mem_Icc (w : ℝ → ℝ) (hw : IsRevenueFn w) (α β ϱ₁ : ℝ) (hα : 0 < α)
(hβ : max 0 (α - 1) ≤ β) (hϱ₁ : ϱ₁ ∈ Icc (0 : ℝ) 1) :
∀ (X : ℕ → PurchaseSpace) (n : ℕ), sapRho w α β ϱ₁ X n ∈ Icc (0 : ℝ) 1 := 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.35, "by our choice of β ⩾ max{0, α − 1} it follows that ϱt ∈ [0, 1] for all t ∈ N"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.