Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(A19) — squared estimation error of the greedy deviation

Proved
KeskinZeevi.IncumbentSufficient.sq_estimation_error_bound_A19

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

concentrationdynamic-pricingleast-squaresp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider the incumbent price model with light-tailed shocks of variance σ2\sigma^2σ2, a slope β∈B\beta \in \mathfrak Bβ∈B with ψ(β)≠0\psi(\beta) \ne 0ψ(β)=0, a constant κ1>0\kappa_1 > 0κ1​>0 and a start time t0≥1t_0 \ge 1t0​≥1. Set

K0=D^24bmax⁡4,K1=512 K0 σ2(u−l)2(ψ(β))−4,K2=4(u−l)2.K_0 = \frac{\hat D^2}{4 b_{\max}^4}, \qquad K_1 = 512\, K_0\, \sigma^2 (u-l)^2 (\psi(\beta))^{-4}, \qquad K_2 = 4(u-l)^2 .K0​=4bmax4​D^2​,K1​=512K0​σ2(u−l)2(ψ(β))−4,K2​=4(u−l)2.

There is a period NNN such that every pricing policy satisfying condition (ii) of Theorem 4 from t0t_0t0​ on, i.e. almost surely ∑s=1t(ψ(bs)−xs+1)2≤κ1log⁡t\sum_{s=1}^t (\psi(b_s) - x_{s+1})^2 \le \kappa_1 \log t∑s=1t​(ψ(bs​)−xs+1​)2≤κ1​logt for all t≥t0t \ge t_0t≥t0​, obeys for every t≥Nt \ge Nt≥N

Eβπ(ψ(β)−ψ(bt))2≤K1t−1+K2 Pβπ(Atc).\mathbb E^\pi_\beta(\psi(\beta) - \psi(b_t))^2 \le K_1 t^{-1} + K_2\, \mathbb P^\pi_\beta(A_t^c).Eβπ​(ψ(β)−ψ(bt​))2≤K1​t−1+K2​Pβπ​(Atc​).

The estimation error of the greedy deviation thus decays like 1/t1/t1/t, up to the probability that the greedy prices were not already close to optimal.

Formalization Note. The paper states (A19) "for any time period t≥N(β)t \ge N(\beta)t≥N(β)" with N(β)=max⁡{N0(β),5}N(\beta) = \max\{N_0(\beta), 5\}N(β)=max{N0​(β),5} and N0(β)N_0(\beta)N0​(β) an unspecified threshold. Here NNN is existential and chosen before the policy, so it is uniform in π\piπ, as in the paper, where N0(β)N_0(\beta)N0​(β) depends only on ψ(β)\psi(\beta)ψ(β) and κ1\kappa_1κ1​. It may also depend on t0t_0t0​. K0K_0K0​, K1K_1K1​, K2K_2K2​ are the explicit constants of p. 1160. K0=max⁡b∈B(ψ′(b))2=D^2/(4bmax⁡4)K_0 = \max_{b \in \mathfrak B} (\psi'(b))^2 = \hat D^2/(4 b_{\max}^4)K0​=maxb∈B​(ψ′(b))2=D^2/(4bmax4​). The start time t0t_0t0​ is the same convention as in the goal theorem. P(Atc)\mathbb P(A_t^c)P(Atc​) enters as a real number (toReal).

Preamble
import Mathlib
import Definitions.Def_RobustBooking_Shared_Noise
import Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares
open RobustBooking.Shared

open MeasureTheory ProbabilityTheory
Formal statement
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
Source
Keskin and Zeevi, Dynamic Pricing with an Unknown Demand Model, Operations Research 62(5), 2014, p. 1160, Appendix A.3, proof of Theorem 4, Eq. (A19) (constants K_0, K_1, K_2, N(β) on pp. 1159-1160)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Fix:

  • a model MMM with bounds l<ul < ul<u, incumbent demand D^\hat DD^ and bmax⁡<0b_{\max} < 0bmax​<0;
  • a measurable space Ω\OmegaΩ with a probability measure PPP;
  • noise functions εs:Ω→R\varepsilon_s : \Omega \to \mathbb Rεs​:Ω→R;
  • a real σ\sigmaσ;
  • a slope β∈[bmin⁡,bmax⁡]\beta \in [b_{\min}, b_{\max}]β∈[bmin​,bmax​] with ψ(β)≠0\psi(\beta) \ne 0ψ(β)=0, where ψ(b)=−p^/2−D^/(2b)\psi(b) = -\hat p/2 - \hat D/(2b)ψ(b)=−p^​/2−D^/(2b);
  • a real κ1>0\kappa_1 > 0κ1​>0;
  • a natural number t0≥1t_0 \ge 1t0​≥1.

Hypothesis. Assume LightTailedNoise(P,ε,σ)\mathrm{LightTailedNoise}(P, \varepsilon, \sigma)LightTailedNoise(P,ε,σ) holds. This predicate is defined in an external file whose content is not shown.

Conclusion. There exists a natural number NNN such that the following holds for every policy π\piπ for MMM. Suppose that for PPP-almost every ω\omegaω, for every natural t≥t0t \ge t_0t≥t0​:

∑s=1t(ψ(bs(ω))−xs+1(ω))2≤κ1log⁡t.\sum_{s=1}^t \bigl(\psi(b_s(\omega)) - x_{s+1}(\omega)\bigr)^2 \le \kappa_1 \log t.s=1∑t​(ψ(bs​(ω))−xs+1​(ω))2≤κ1​logt.

Then for every natural t≥Nt \ge Nt≥N:

∫Ω(ψ(β)−ψ(bt))2 dP≤512 K0 σ2(u−l)2ψ(β)4 t+4(u−l)2 P(Atc),K0=D^24 bmax⁡4.\int_\Omega \bigl(\psi(\beta) - \psi(b_t)\bigr)^2\, dP \le \frac{512\, K_0\, \sigma^2 (u-l)^2}{\psi(\beta)^4\, t} + 4(u-l)^2\, P(A_t^{c}), \qquad K_0 = \frac{\hat D^2}{4\, b_{\max}^4}.∫Ω​(ψ(β)−ψ(bt​))2dP≤ψ(β)4t512K0​σ2(u−l)2​+4(u−l)2P(Atc​),K0​=4bmax4​D^2​.

The ingredients, all for the process that π\piπ generates under slope β\betaβ and noise ε\varepsilonε, are:

  • xsx_sxs​ are the price deviations ps−p^p_s - \hat pps​−p^​;
  • bs=max⁡(bmin⁡,min⁡(β^s,bmax⁡))b_s = \max(b_{\min}, \min(\hat\beta_s, b_{\max}))bs​=max(bmin​,min(β^​s​,bmax​)) is the truncated least-squares estimate, with β^s=0\hat\beta_s = 0β^​s​=0 when ∑r≤sxr2=0\sum_{r \le s} x_r^2 = 0∑r≤s​xr2​=0;
  • AtA_tAt​ is the set of ω\omegaω with (ψ(β)−ψ(bs))2≤ψ(β)2/12(\psi(\beta) - \psi(b_s))^2 \le \psi(\beta)^2/12(ψ(β)−ψ(bs​))2≤ψ(β)2/12 for all natural sss in [⌊(t−1)/2⌋,t−1][\lfloor (t-1)/2 \rfloor, t-1][⌊(t−1)/2⌋,t−1];
  • P(Atc)P(A_t^c)P(Atc​) is used as a real number in [0,1][0, 1][0,1];
  • the integral is a Lebesgue (Bochner) integral.

Dependence of NNN. NNN is chosen before π\piπ. It may depend on MMM, PPP, ε\varepsilonε, σ\sigmaσ, β\betaβ, κ1\kappa_1κ1​ and t0t_0t0​, but not on the policy.

Degenerate cases.

  • t=0t = 0t=0 (relevant only if N=0N = 0N=0): the first term has division by zero and is taken to be 000. The bound then reads ∫(ψ(β)−ψ(b0))2≤4(u−l)2P(A0c)\int (\psi(\beta) - \psi(b_0))^2 \le 4(u-l)^2 P(A_0^c)∫(ψ(β)−ψ(b0​))2≤4(u−l)2P(A0c​), where b0=bmax⁡b_0 = b_{\max}b0​=bmax​ and A0A_0A0​ constrains only s=0s = 0s=0. So A0A_0A0​ is either all of Ω\OmegaΩ or empty, and does not depend on ω\omegaω.
  • t=1t = 1t=1 in the assumption (possible because t0≥1t_0 \ge 1t0​≥1): the right side is κ1log⁡1=0\kappa_1 \log 1 = 0κ1​log1=0. The assumption then forces ψ(b1)=x2\psi(b_1) = x_2ψ(b1​)=x2​ almost surely.
  • σ\sigmaσ: it enters only through σ2\sigma^2σ2, 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 K0K_0K0​ or by ψ(β)\psi(\beta)ψ(β), because bmax⁡≠0b_{\max} \ne 0bmax​=0 and ψ(β)≠0\psi(\beta) \ne 0ψ(β)=0.
  • Non-integrable integrand: if the left-hand integrand is not integrable, the integral is 000.
  • Non-measurable AtcA_t^cAtc​: its PPP-value is the outer measure.
  • Policies that fail the almost-sure assumption: the conclusion says nothing about them.
  • Empty Ω\OmegaΩ: no probability measure exists, so the statement is vacuous.
  • Unsatisfiable noise hypothesis: if LightTailedNoise\mathrm{LightTailedNoise}LightTailedNoise is unsatisfiable for the given σ\sigmaσ, the statement is vacuous.
Human review
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 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