Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 (1), pp. 22–23 — with probability 1 − δ the Simple Learning Algorithm's ranking hooks at least ½ of the optimum minus ϵ

Proved
RankAssort.SimpleLearn.theorem_3_1

by mikedeng1 · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmonline-learningp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pacproduct-ranking

Consider the online assortment ranking problem with nnn products: customers have types (p,f,k)(p, f, k)(p,f,k) drawn from an arbitrary distribution D\mathcal DD (with a measurable type map), click sequentially with bias inside their first impression window, and are hooked if they click at least once. Let ϵ,δ>0\epsilon, \delta > 0ϵ,δ>0, and run the Simple Learning Algorithm (Algorithm 2) with any (ϵ′,δ′)(\epsilon', \delta')(ϵ′,δ′)-PAC algorithm as a black box, where

ϵ′=2ϵn,δ′=δn.\epsilon' = \frac{2\epsilon}{n}, \qquad \delta' = \frac{\delta}{n}.ϵ′=n2ϵ​,δ′=nδ​.

Then with probability at least 1−δ1-\delta1−δ the returned ranking π~\tilde\piπ~ satisfies, simultaneously for every ranking π∗\pi^*π∗ (in particular the optimal one),

E[H(π~)] ≥ 12 E[H(π∗)]−ϵ.\mathbb E[H(\tilde\pi)] \ \ge\ \frac12\,\mathbb E[H(\pi^*)] - \epsilon .E[H(π~)] ≥ 21​E[H(π∗)]−ϵ.

This is part 1 of Theorem 3 (general OnAR): learning with a black-box PAC bandit algorithm recovers, up to an additive ϵ\epsilonϵ and with confidence 1−δ1-\delta1−δ, the factor ½ that the greedy algorithm attains with complete information (Theorem 1).

Formalization Note Ranks are 0-based in Lean: the paper's rank rrr is index r−1r-1r−1, a ranking is a duplicate-free list of the nnn products (Fin n), and π−1(j)\pi^{-1}(j)π−1(j) is the list entry at index j−1j-1j−1. "Any (ϵ′,δ′)(\epsilon',\delta')(ϵ′,δ′)-PAC algorithm as a black box" is a SimpleLearningRun D τ (2 * eps / n) (delta / n) P: a random output ranking π~(ω)\tilde\pi(\omega)π~(ω) whose rank-rrr product, conditionally on every prefix already fixed, fails to be ϵ′\epsilon'ϵ′-approximately best among the unranked products with probability at most δ′\delta'δ′ (Definition 1 applied at each call, p. 58). The sampling of the black box is not modelled. E[H(⋅)]\mathbb E[H(\cdot)]E[H(⋅)] is computed from the sequential click law with bias. "The optimal ranking" is rendered as "every ranking", which is equivalent since the set of rankings is finite. As on the page, only ϵ,δ>0\epsilon, \delta > 0ϵ,δ>0 are assumed; for δ≥1\delta \ge 1δ≥1 the statement is trivially true. Part 2 (Independence, 1−1/e1-1/e1−1/e) is not formalized.

Differences from the source:

  • reading: given any (ϵ′, δ′)-PAC algorithm as a black box (Definition 1) → a SimpleLearningRun: the output π̃(ω) whose rank-r product, conditionally on every prefix already fixed, fails to be ϵ′-best among the unranked products with probability ≤ δ′; the black box's sampling and T̃ are not modelled; reason: Algorithm 2 calls ALG once per rank on the unranked products, and p. 58 uses its guarantee "for any particular instantiation of [π̃]ᵣ₋₁"; T̃ does not enter the conclusion
  • encoding: π∗ the optimal ranking → every ranking π∗, quantified inside the probability event; reason: equivalent: rankings form a finite nonempty set, so the optimum exists and the bound for it implies the bound for every ranking
  • encoding: with probability (1 − δ) → ENNReal.ofReal (1 − delta) ≤ P {ω | …}; reason: Lean convention; same statement for δ ≤ 1, trivial for δ > 1 as on the page
  • encoding: expectation over the type (p, f, k) ∼ D, a random variable → integral over θ ∼ D of a function of τ θ, with TypeMeasurable τ (every coordinate of the type map measurable); reason: the expectations are undefined otherwise (Lean would return the junk value 0); the integrands lie in [0, 1], so measurability is all that is needed
  • 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
Preamble
import Mathlib
import Definitions.Def_RankAssort_SimpleLearn_Model
import Definitions.Def_RankAssort_SimpleLearn_Algorithm
Formal statement
namespace RankAssort.SimpleLearn
open MeasureTheory
theorem theorem_3_1 {n : ℕ} {Θ : Type*} [MeasurableSpace Θ] (D : Measure Θ)
    [IsProbabilityMeasure D] (τ : Θ → CustomerType n) (hτ : TypeMeasurable τ)
    (eps delta : ℝ) (heps : 0 < eps) (hdelta : 0 < delta)
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    (run : SimpleLearningRun D τ (2 * eps / n) (delta / n) P) :
    ENNReal.ofReal (1 - delta) ≤
      P {ω | ∀ piStar : List (Fin n), piStar.Nodup → piStar.length = n →
              (1 / 2 : ℝ) * expHook D τ piStar - eps ≤ expHook D τ (run.out ω)} := by sorry
end RankAssort.SimpleLearn
Source
Ferreira, Parthasarathy, Sekar, Learning to Rank an Assortment of Products, SSRN 3395992 author manuscript, pp. 22–23, Theorem 3 (part 1)
Human review
  • Endorsed by Shuze Chen · Oct 23, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 23, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me