(A19) — squared estimation error of the greedy deviation
ProvedKeskinZeevi.IncumbentSufficient.sq_estimation_error_bound_A19Consider the incumbent price model with light-tailed shocks of variance , a slope with , a constant and a start time . Set
There is a period such that every pricing policy satisfying condition (ii) of Theorem 4 from on, i.e. almost surely for all , obeys for every
The estimation error of the greedy deviation thus decays like , up to the probability that the greedy prices were not already close to optimal.
Formalization Note. The paper states (A19) "for any time period " with and an unspecified threshold. Here is existential and chosen before the policy, so it is uniform in , as in the paper, where depends only on and . It may also depend on . , , are the explicit constants of p. 1160. . The start time is the same convention as in the goal theorem. enters as a real number (toReal).
import Mathlib import Definitions.Def_RobustBooking_Shared_Noise import Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares open RobustBooking.Shared open MeasureTheory ProbabilityTheory
namespace KeskinZeevi.IncumbentSufficient
/-- Keskin–Zeevi 2014, p. 1160, (A19): fix `β ∈ 𝔅` with `ψ(β) ≠ 0`, `κ₁ > 0` and a start time
`t₀ ≥ 1`. There is `N` (the paper's `N(β)`) such that for every policy satisfying condition (ii)
of Theorem 4, `Σ_{s=1}^t (ψ(b_s) - x_{s+1})² ≤ κ₁ log t` almost surely for all `t ≥ t₀`, and
every `t ≥ N`,
`E(ψ(β) - ψ(b_t))² ≤ K₁ t⁻¹ + K₂ P(A_tᶜ)` with `K₀ = D̂²/(4 b_max⁴)`,
`K₁ = 512 K₀ σ² (u - l)² ψ(β)⁻⁴` and `K₂ = 4 (u - l)²`. -/
theorem sq_estimation_error_bound_A19 (M : Model) {Ω : Type*} [MeasurableSpace Ω]
(P : Measure Ω) [IsProbabilityMeasure P] (ε : ℕ → Ω → ℝ) (σ : ℝ)
(hε : LightTailedNoise P ε σ) (β : ℝ) (hβ : β ∈ M.B) (hψ : M.psi β ≠ 0)
(κ₁ : ℝ) (hκ₁ : 0 < κ₁) (t₀ : ℕ) (ht₀ : 1 ≤ t₀) :
∃ N : ℕ, ∀ π : Policy M,
(∀ᵐ ω ∂P, ∀ t : ℕ, t₀ ≤ t →
∑ s ∈ Finset.Icc 1 t, (M.psi (truncEst π β ε s ω) - dev π β ε (s + 1) ω) ^ 2 ≤
κ₁ * Real.log t) →
∀ t : ℕ, N ≤ t →
∫ ω, (M.psi β - M.psi (truncEst π β ε t ω)) ^ 2 ∂P ≤
512 * (M.DHat ^ 2 / (4 * M.bMax ^ 4)) * σ ^ 2 * (M.u - M.l) ^ 2 / M.psi β ^ 4 / t +
4 * (M.u - M.l) ^ 2 * (P (goodEvent π β ε t)ᶜ).toReal := by sorry
end KeskinZeevi.IncumbentSufficient
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Fix:
- a model with bounds , incumbent demand and ;
- a measurable space with a probability measure ;
- noise functions ;
- a real ;
- a slope with , where ;
- a real ;
- a natural number .
Hypothesis. Assume holds. This predicate is defined in an external file whose content is not shown.
Conclusion. There exists a natural number such that the following holds for every policy for . Suppose that for -almost every , for every natural :
Then for every natural :
The ingredients, all for the process that generates under slope and noise , are:
- are the price deviations ;
- is the truncated least-squares estimate, with when ;
- is the set of with for all natural in ;
- is used as a real number in ;
- the integral is a Lebesgue (Bochner) integral.
Dependence of . is chosen before . It may depend on , , , , , and , but not on the policy.
Degenerate cases.
- (relevant only if ): the first term has division by zero and is taken to be . The bound then reads , where and constrains only . So is either all of or empty, and does not depend on .
- in the assumption (possible because ): the right side is . The assumption then forces almost surely.
- : it enters only through , so its sign does not matter in the bound. It matters only through the unseen noise hypothesis.
- Well-definedness: there is no division by zero in or by , because and .
- Non-integrable integrand: if the left-hand integrand is not integrable, the integral is .
- Non-measurable : its -value is the outer measure.
- Policies that fail the almost-sure assumption: the conclusion says nothing about them.
- Empty : no probability measure exists, so the statement is vacuous.
- Unsatisfiable noise hypothesis: if is unsatisfiable for the given , the statement is vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.