Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — sufficient conditions for logarithmic regret with a known incumbent price

Proved
KeskinZeevi.IncumbentSufficient.regret_log_upper_bound

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

dynamic-pricingleast-squaresp2o-batch-rm-cafterp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Consider the incumbent price model with light-tailed i.i.d. demand shocks, and a true slope β∈B=[bmin⁡,bmax⁡]\beta \in \mathfrak B = [b_{\min}, b_{\max}]β∈B=[bmin​,bmax​] whose optimal deviation from the incumbent price is nonzero, ψ(β)≠0\psi(\beta) \ne 0ψ(β)=0. There is a threshold κ0′>0\kappa_0' > 0κ0′​>0 such that for every κ0≥κ0′\kappa_0 \ge \kappa_0'κ0​≥κ0′​, every κ1>0\kappa_1 > 0κ1​>0 and every start time t0≥1t_0 \ge 1t0​≥1 there is a finite constant C>0C > 0C>0 with the following property. If a pricing policy π\piπ satisfies, almost surely, for all t≥t0t \ge t_0t≥t0​,

(i)  J^t≥κ0log⁡tand(ii)  ∑s=1t(ψ(bs)−xs+1)2≤κ1log⁡t,\text{(i)}\ \ \hat J_t \ge \kappa_0 \log t \qquad\text{and}\qquad \text{(ii)}\ \ \sum_{s=1}^{t} (\psi(b_s) - x_{s+1})^2 \le \kappa_1 \log t,(i)  J^t​≥κ0​logtand(ii)  s=1∑t​(ψ(bs​)−xs+1​)2≤κ1​logt,

then its regret is logarithmic:

Δβπ(T)≤Clog⁡Tfor all T≥3.\Delta^\pi_\beta(T) \le C \log T \qquad \text{for all } T \ge 3 .Δβπ​(T)≤ClogTfor all T≥3.

Condition (i) asks the policy to keep accumulating information at a logarithmic rate, and (ii) asks it to stay close to the greedy (certainty-equivalent) deviation ψ(bs)\psi(b_s)ψ(bs​). By Theorem 3 of the same paper, log⁡T\log TlogT is the best possible order, so policies meeting (i)–(ii) are asymptotically optimal.

Formalization Note. This is a corrected form of the printed theorem, which reads "There exist finite positive constants κ0,κ1\kappa_0, \kappa_1κ0​,κ1​, and CCC such that if π\piπ … satisfies (i) … (ii) ∑s=0t(ψ(bs)−xs+1)2≤κ1log⁡t\sum_{s=0}^t (\psi(b_s) - x_{s+1})^2 \le \kappa_1 \log t∑s=0t​(ψ(bs​)−xs+1​)2≤κ1​logt almost surely for all ttt, then …". Read literally, the existential κ0,κ1\kappa_0, \kappa_1κ0​,κ1​ make the statement vacuous (take κ0\kappa_0κ0​ so large that (i) fails for every policy at t=2t = 2t=2). The proof on pp. 1159–1160 shows that any κ0\kappa_0κ0​ above a threshold works, that κ1\kappa_1κ1​ is arbitrary, and that the conditions are used only for large ttt. The Lean statement is that content, which implies the printed statement (take κ0=κ0′\kappa_0 = \kappa_0'κ0​=κ0′​, any κ1\kappa_1κ1​, t0=1t_0 = 1t0​=1). The sum in (ii) starts at s=1s = 1s=1, because b0b_0b0​ is defined only for greedy ILS; this weakens the hypothesis. bsb_sbs​ uses Lean's a/0=0a/0 = 0a/0=0 when J^s=0\hat J_s = 0J^s​=0, which under (i) can only happen for s<max⁡(t0,2)s < \max(t_0, 2)s<max(t0​,2). The constant CCC is chosen before the policy and the horizon, as on the page; it may depend on the model, the noise law, β\betaβ, κ0\kappa_0κ0​, κ1\kappa_1κ1​ and t0t_0t0​. The regret is for the fixed true slope β\betaβ, not the worst case (22).

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

open MeasureTheory ProbabilityTheory
Formal statement
namespace KeskinZeevi.IncumbentSufficient

/-- Keskin–Zeevi 2014, p. 1150, Theorem 4 (Sufficient Conditions for Asymptotic Optimality), in
the form its proof establishes (the printed "there exist κ₀, κ₁" makes a literal reading
vacuous): for `β ∈ 𝔅` with `ψ(β) ≠ 0` there is a threshold `κ₀' > 0` such that for every
`κ₀ ≥ κ₀'`, every `κ₁ > 0` and every start time `t₀ ≥ 1` there is a finite `C > 0` with the
following property. If a policy `π` satisfies, almost surely for all `t ≥ t₀`,
(i) `Ĵ_t ≥ κ₀ log t` and (ii) `Σ_{s=1}^t (ψ(b_s) - x_{s+1})² ≤ κ₁ log t`, then
`Δ^π_β(T) ≤ C log T` for all `T ≥ 3`. `C` does not depend on `π` or `T`. -/
theorem regret_log_upper_bound (M : Model) {Ω : Type*} [MeasurableSpace Ω]
    (P : Measure Ω) [IsProbabilityMeasure P] (ε : ℕ → Ω → ℝ) (σ : ℝ)
    (hε : LightTailedNoise P ε σ) (β : ℝ) (hβ : β ∈ M.B) (hψ : M.psi β ≠ 0) :
    ∃ κ₀' : ℝ, 0 < κ₀' ∧ ∀ κ₀ : ℝ, κ₀' ≤ κ₀ → ∀ κ₁ : ℝ, 0 < κ₁ → ∀ t₀ : ℕ, 1 ≤ t₀ →
      ∃ C : ℝ, 0 < C ∧ ∀ π : Policy M,
        (∀ᵐ ω ∂P, ∀ t : ℕ, t₀ ≤ t →
          κ₀ * Real.log t ≤ Jhat π β ε t ω ∧
            ∑ s ∈ Finset.Icc 1 t, (M.psi (truncEst π β ε s ω) - dev π β ε (s + 1) ω) ^ 2 ≤
              κ₁ * Real.log t) →
        ∀ T : ℕ, 3 ≤ T → regret π β ε P T ≤ C * Real.log T := by sorry

end KeskinZeevi.IncumbentSufficient
Source
Keskin and Zeevi, Dynamic Pricing with an Unknown Demand Model, Operations Research 62(5), 2014, p. 1150, Theorem 4 (proof pp. 1159-1160, Appendix A.3)
Read-back

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

Throughout, M\mathcal{M}M is a model of type Model. The objects Model, Policy, LightTailedNoise, Jhat, truncEst, dev and regret are defined in the imported files Definitions.Def_RobustBooking_Shared_Noise, Definitions.Def_KeskinZeevi_IncumbentSufficient_LeastSquares and Definitions.Def_KeskinZeevi_IncumbentSufficient_Regret. Those files are not shown, so their contents cannot be unfolded here. What the statement itself shows about them is below. The model M\mathcal{M}M has a set of reals B=M.B\mathcal{B} = \mathcal{M}.BB=M.B and a function ψ=M.ψ:R→R\psi = \mathcal{M}.\psi : \mathbb{R} \to \mathbb{R}ψ=M.ψ:R→R. A policy π\piπ ranges over the type Policy(M)\mathrm{Policy}(\mathcal{M})Policy(M). Given π\piπ, a parameter β\betaβ, a noise process ε\varepsilonε, a time ttt and an outcome ω\omegaω, there are real numbers J^tπ(ω)\hat J^{\pi}_{t}(\omega)J^tπ​(ω) (Jhat), b^sπ(ω)\hat b^{\pi}_{s}(\omega)b^sπ​(ω) (truncEst) and xsπ(ω)x^{\pi}_{s}(\omega)xsπ​(ω) (dev). There is also a real number Δβπ(T)\Delta^{\pi}_{\beta}(T)Δβπ​(T) (regret), which additionally depends on the measure PPP. The docstring gives an informal account of the source theorem. It is a comment, not part of what the code asserts.

Data and hypotheses. Fix the following:

  • a model M\mathcal{M}M;
  • a measurable space Ω\OmegaΩ with a probability measure PPP;
  • a real-valued process ε=(εn)n∈N\varepsilon = (\varepsilon_n)_{n \in \mathbb{N}}ε=(εn​)n∈N​, with εn:Ω→R\varepsilon_n : \Omega \to \mathbb{R}εn​:Ω→R;
  • a real number σ\sigmaσ, with no sign or other restriction imposed in this statement;
  • a real number β\betaβ.

Assume:

  • ε\varepsilonε satisfies LightTailedNoise with respect to PPP and parameter σ\sigmaσ (defined in an imported file, not shown);
  • β∈B\beta \in \mathcal{B}β∈B;
  • ψ(β)≠0\psi(\beta) \neq 0ψ(β)=0.

Conclusion. There is a real number κ0′>0\kappa_0' > 0κ0′​>0 with the following property. For every real κ0≥κ0′\kappa_0 \ge \kappa_0'κ0​≥κ0′​, every real κ1>0\kappa_1 > 0κ1​>0 and every natural number t0≥1t_0 \ge 1t0​≥1, there is a real constant C>0C > 0C>0 such that the following holds for every policy π\piπ of M\mathcal{M}M. Suppose that, for PPP-almost every ω\omegaω, the two conditions below hold simultaneously for all natural numbers t≥t0t \ge t_0t≥t0​:

κ0log⁡t  ≤  J^tπ(ω)and∑s=1t(ψ(b^sπ(ω))−xs+1π(ω))2  ≤  κ1log⁡t.\kappa_0 \log t \;\le\; \hat J^{\pi}_{t}(\omega) \qquad\text{and}\qquad \sum_{s=1}^{t} \Bigl(\psi\bigl(\hat b^{\pi}_{s}(\omega)\bigr) - x^{\pi}_{s+1}(\omega)\Bigr)^2 \;\le\; \kappa_1 \log t .κ0​logt≤J^tπ​(ω)ands=1∑t​(ψ(b^sπ​(ω))−xs+1π​(ω))2≤κ1​logt.

That is, there is a single PPP-null set outside of which both inequalities hold at every t≥t0t \ge t_0t≥t0​. Then for every natural number T≥3T \ge 3T≥3:

Δβπ(T)  ≤  Clog⁡T.\Delta^{\pi}_{\beta}(T) \;\le\; C \log T .Δβπ​(T)≤ClogT.

Here log⁡\loglog is the real natural logarithm applied to the natural number cast to R\mathbb{R}R. All of J^\hat JJ^, b^\hat bb^, xxx and Δ\DeltaΔ are evaluated with the fixed β\betaβ and ε\varepsilonε.

Order of quantifiers.

  • κ0′\kappa_0'κ0′​ may depend on M\mathcal{M}M, PPP, ε\varepsilonε, σ\sigmaσ and β\betaβ.
  • CCC may depend on all of those and also on κ0\kappa_0κ0​, κ1\kappa_1κ1​ and t0t_0t0​.
  • CCC is chosen before π\piπ and TTT, so one CCC serves every policy meeting the hypothesis and every horizon T≥3T \ge 3T≥3.
  • The statement only asserts that some κ0′\kappa_0'κ0′​ exists. It gives no bound on how large κ0′\kappa_0'κ0′​ is.
  • Raising κ0\kappa_0κ0​ makes the condition on π\piπ stronger, so the implication becomes weaker. Suppose that beyond some level no policy can meet κ0log⁡t≤J^tπ\kappa_0 \log t \le \hat J^{\pi}_tκ0​logt≤J^tπ​ almost surely. Then any larger κ0′\kappa_0'κ0′​ makes the conclusion hold vacuously. Whether that can happen depends on the definition of Jhat, which is not shown.

Degenerate and edge cases.

  • If B\mathcal{B}B is empty, or LightTailedNoise cannot be satisfied, or ψ\psiψ vanishes on all of B\mathcal{B}B, the statement is vacuous. Whether any of these happens depends on the imported definitions.
  • Ω\OmegaΩ is nonempty because PPP is a probability measure.
  • If Policy(M)\mathrm{Policy}(\mathcal{M})Policy(M) is empty, the claim about policies is vacuous.
  • Every ttt considered satisfies t≥t0≥1t \ge t_0 \ge 1t≥t0​≥1, so log⁡t≥0\log t \ge 0logt≥0.
  • At t=1t = 1t=1 we have log⁡1=0\log 1 = 0log1=0. So if t0=1t_0 = 1t0​=1, the hypothesis at t=1t = 1t=1 requires J^1π≥0\hat J^{\pi}_1 \ge 0J^1π​≥0 and (ψ(b^1π)−x2π)2≤0\bigl(\psi(\hat b^{\pi}_1) - x^{\pi}_2\bigr)^2 \le 0(ψ(b^1π​)−x2π​)2≤0. The second condition means ψ(b^1π)=x2π\psi(\hat b^{\pi}_1) = x^{\pi}_2ψ(b^1π​)=x2π​ almost surely.
  • The sum ∑s=1t\sum_{s=1}^{t}∑s=1t​ is never empty, since t≥1t \ge 1t≥1.
  • The conclusion says nothing about horizons T∈{0,1,2}T \in \{0, 1, 2\}T∈{0,1,2}.
  • For T≥3T \ge 3T≥3 we have log⁡T≥log⁡3>0\log T \ge \log 3 > 0logT≥log3>0, so the bound Clog⁡TC \log TClogT is strictly positive.
  • The regret Δβπ(T)\Delta^{\pi}_{\beta}(T)Δβπ​(T) is compared as a real number. Whether it can take a default value, for example 000 from the integral of a non-integrable function or from a supremum over an empty or unbounded set, depends on the regret definition, which is not shown.
  • Similarly, Jhat, truncEst and dev may involve division or truncation that returns a default value, such as division by zero giving 000. That cannot be seen from this statement.
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