(24), p. 58 — union bound: with probability ≥ 1 − δ every rank of π̃ satisfies (23)
ProvedRankAssort.SimpleLearn.eq_24Let and , and consider a run of the Simple Learning Algorithm (Algorithm 2) driven by an -PAC black box, in the prefix-conditional sense of the definition SimpleLearningRun. Let be the event that the product placed at rank is -approximately best among the products not ranked before it, i.e. that (23) holds at rank . Then
The page bounds each by and applies the union bound. The per-rank bound is obtained here by summing the prefix-conditional guarantee over the possible prefixes.
Formalization Note Ranks are 0-based in Lean: the paper's rank is index , a ranking is a duplicate-free list of the products (Fin n), and is the list entry at index . The probability is the measure of the learning randomness; enters as ENNReal.ofReal (1 - delta). The theorem is stated for an arbitrary tolerance ; Theorem 3 uses .
Differences from the source:
- generalization: ϵ′ = 2ϵ/n → any real tolerance epsP; reason: Theorem 3 uses the instance epsP = 2ϵ/n
- generalization: D a distribution of customer types → any measure D on the type space; reason: the statement concerns only the learning probability P; a probability measure D is one instance
- reading: Pr(B_r = 0) ≤ δ/n for every r, from the (ϵ′, δ/n)-PAC guarantee → the prefix-conditional PAC guarantee of SimpleLearningRun, summed over prefixes; reason: p. 58: "(23) holds for any particular instantiation of [π̃]ᵣ₋₁ with probability 1 − δ/n"; summing over prefixes gives the page's per-rank bound
- encoding: Pr over the algorithm's randomness, value 1 − δ → measure P of the learning randomness Ω, ENNReal.ofReal (1 − delta); reason: Lean convention; same values for δ ≤ 1, and both sides trivial for δ > 1
- encoding: ranks 1..n, a ranking is a permutation π of [n], π⁻¹(j) the product at rank j → 0-based indices, a ranking is a duplicate-free List (Fin n) of length n, π⁻¹(j) is the entry at index j − 1; reason: Lean convention; the same rankings
import Mathlib import Definitions.Def_RankAssort_SimpleLearn_Model import Definitions.Def_RankAssort_SimpleLearn_Algorithm
namespace RankAssort.SimpleLearn
open MeasureTheory
theorem eq_24 {n : ℕ} {Θ : Type*} [MeasurableSpace Θ] (D : Measure Θ) (τ : Θ → CustomerType n)
(epsP delta : ℝ) (hdelta : 0 < delta)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(run : SimpleLearningRun D τ epsP (delta / n) P) :
ENNReal.ofReal (1 - delta) ≤
P {ω | ∀ r < n, ∃ i, (run.out ω)[r]? = some i ∧
IsApproxBest D τ ((run.out ω).take r) i epsP} := by sorry
end RankAssort.SimpleLearn
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.