Proof of Theorem 3, first display on p. 1159 — worst-case regret as the supremum of −β times the cumulative squared pricing error, and its lower bound
ProvedKeskinZeevi.IncumbentLowerBound.regret_eq_neg_beta_sum_sqErrConsider the incumbent price model with i.i.d. demand shocks. There exist finite positive constants and , depending only on the model, with the following property. For every pricing policy and every horizon ,
The paper writes the right side as ; the summand does not depend on , so the supremum is the sum itself.
The equality holds because is a quadratic with leading coefficient that is maximized at , so . The inequality follows from for and the previous display. It turns the lower bound on cumulative pricing error into a lower bound on regret.
Formalization Note. Lean period is the paper's period . The paper's is the Lean sum over Finset.range T, and the paper's with the term is the Lean sum over with the term . The constants are chosen before the probability space, the noise, the policy and the horizon, as in Lemma 4, of which they are the constants on the page.
import Mathlib import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Model import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Policy import Definitions.Def_RobustBooking_Shared_GaussianNoise import Definitions.Def_KeskinZeevi_IncumbentLowerBound_Regret open RobustBooking.Shared open MeasureTheory
namespace KeskinZeevi.IncumbentLowerBound
/-- Proof of Theorem 3, first display on p. 1159: because `β ∈ [b_min, b_max]`,
`Δ^π(T) = sup_{β∈𝔅, ψ(β)≠0} {−β Σ_{t=1}^T E^π_β(x_t − ψ(β))²}
≥ |b_max| sup_{β∈𝔅, ψ(β)≠0} Σ_{t=2}^T c₀ / (c₁ + (u − l)²(t − 1))`,
with `c₀, c₁` the constants of Lemma 4 (the summand does not depend on `β`, so the second
supremum is the sum itself). Lean period `t` is the paper's period `t + 1`: the paper's
`Σ_{t=1}^T` is `Finset.range T`, and the paper's `Σ_{t=2}^T` with `t − 1` is `Finset.Ico 1 T`
with the Lean index `t`. The constants depend only on the model `M`. -/
theorem regret_eq_neg_beta_sum_sqErr (M : Model) :
∃ c₀ : ℝ, 0 < c₀ ∧ ∃ c₁ : ℝ, 0 < c₁ ∧
∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(ε : ℕ → Ω → ℝ), GaussianNoise M.σ P ε →
∀ (π : Policy M.l M.u) (T : ℕ),
worstRegret M P ε π T
= ⨆ β : M.Bexcl, -(β : ℝ) * ∑ t ∈ Finset.range T, sqErr M P ε π (β : ℝ) t ∧
|M.bMax| * ∑ t ∈ Finset.Ico 1 T, c₀ / (c₁ + (M.u - M.l) ^ 2 * (t : ℝ))
≤ worstRegret M P ε π T := by sorry
end KeskinZeevi.IncumbentLowerBound
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This statement uses several definitions whose code is not shown here: Model, Policy, GaussianNoise, worstRegret, sqErr, and the model fields , , , and . This read-back names them but cannot unfold them. It describes only what the statement says about them. The only thing visible about is that its elements can be turned into real numbers. Below, denotes that real number.
Fix a model . It has real parameters , , and , and an index collection . The statement claims that there exist real constants and that depend only on , with the following property.
Take any measurable space , any probability measure on , and any real-valued process of functions that satisfies the predicate . Then for every policy of the type and every horizon , both of the following hold.
- Identity. The quantity equals a supremum over the index set:
The supremum is the real-valued supremum over all elements of . The sum runs over the periods .
- Lower bound. With the same and :
The sum runs over . The summand does not involve , , or .
The order of the quantifiers matters here. The constants and are chosen once for , before , , , and . So the same pair must work for every probability space, every admissible noise process, every policy and every horizon. Nothing further is assumed about : there is no sign condition on , no requirement that , and no requirement that is nonempty.
Degenerate cases.
- : Both sums are empty, so each expression inside the supremum is . The identity then claims , and the lower bound reduces to .
- : The lower-bound sum is empty, so the bound only says . The identity still involves the single period .
- : Every summand is the constant . The denominator is always at least , so no division by zero can occur.
- : The lower bound is .
- The supremum: It uses the convention for real suprema. If is empty, or the set of values is not bounded above, the supremum is by convention . In that situation the identity claims the worst regret is . The lower bound then requires . With , that can only hold if or .
- Vacuous cases: If no process satisfies for any probability space, or if has no elements, the part after the choice of constants holds vacuously. The statement then only asserts that some positive and exist.
- Hidden conventions: and may involve expectations. An expectation of a non-integrable function would silently take the default value , but that cannot be seen from this code.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.