Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1, p. 55 β€” Proposition 3(b) for an episode with a random 𝒒_{sβ‚€}-measurable estimate: E(R'_k) ≀ C′₃ log(Cβ€²β‚‚Tβ‚€)Tβ‚€^{2/3} + 4p_max L Tβ‚€ Eβ€–ΞΈΜ‚ βˆ’ θ₀‖₁

Proved
LuoSunLiu.DIP.proposition_3_conditional

by tianyipeng Β· Nov 4, 2026 Β· Mathlib 0df444a (Lean v4.33.1)

contextual-pricingdynamic-pricingregret

This is Proposition 3(b) applied to one episode of the DIP policy whose input estimate is random, as used in the proof of Theorem 1.

Let the standing assumptions of the contextual pricing model hold (βˆ₯ΞΈ0βˆ₯1≀W\|\theta_0\|_1 \le Wβˆ₯ΞΈ0​βˆ₯1​≀W, pmax⁑>0p_{\max} > 0pmax​>0, βˆ₯xβˆ₯βˆžβ‰€1\|x\|_\infty \le 1βˆ₯xβˆ₯βˆžβ€‹β‰€1 on X\mathcal XX, and pβˆ—(x)∈(0,pmax⁑)p^*(x) \in (0, p_{\max})pβˆ—(x)∈(0,pmax​) maximizes p↦p(1βˆ’F(pβˆ’x⊀θ0))p \mapsto p(1 - F(p - x^\top\theta_0))p↦p(1βˆ’F(pβˆ’x⊀θ0​)) over p>0p > 0p>0), let FFF be LLL-Lipschitz (Assumption 1), and let Assumption 2 hold with constant CAC_ACA​. Fix a discretization constant Cd∈NC_d \in \mathbb NCdβ€‹βˆˆN with pmax⁑+2W<Cd pmax⁑p_{\max} + 2W < C_d\,p_{\max}pmax​+2W<Cd​pmax​ and a regularization parameter Ξ»>0\lambda > 0Ξ»>0.

Then there are constants C2β€²,C3β€²>0C'_2, C'_3 > 0C2′​,C3′​>0 with the following property. Let (Ξ©,F,P)(\Omega, \mathcal F, \mathbb P)(Ξ©,F,P) be a probability space on a standard Borel space with a filtration (Gt)(\mathcal G_t)(Gt​), and let covariates xtx_txt​, prices ptp_tpt​ and noise ztz_tzt​ form a pricing environment (covariates and prices Gtβˆ’1\mathcal G_{t-1}Gtβˆ’1​-measurable, ztz_tzt​ Gt\mathcal G_tGt​-measurable with CDF FFF and independent of Gtβˆ’1\mathcal G_{t-1}Gtβˆ’1​). Consider an episode of T0β‰₯1T_0 \ge 1T0​β‰₯1 periods s0+1,…,s0+T0s_0 + 1, \dots, s_0 + T_0s0​+1,…,s0​+T0​ and a random estimate ΞΈ^\hat\thetaΞΈ^ that is Gs0\mathcal G_{s_0}Gs0​​-measurable with βˆ₯ΞΈ^βˆ₯1≀W\|\hat\theta\|_1 \le Wβˆ₯ΞΈ^βˆ₯1​≀W. Suppose that on every sample path the prices of the episode are a run of Inner Algorithm B with input ΞΈ^\hat\thetaΞΈ^, d=Cd⌈T01/6βŒ‰d = C_d\lceil T_0^{1/6}\rceild=Cdβ€‹βŒˆT01/6β€‹βŒ‰ grid points, confidence level Ξ΄=1/T0\delta = 1/T_0Ξ΄=1/T0​, confidence parameters Ξ²Ο„=Ξ²Ο„βˆ—\beta_\tau = \beta^*_\tauβτ​=Ξ²Ο„βˆ—β€‹ and regularization Ξ»\lambdaΞ». Then

E[βˆ‘t=s0+1s0+T0rt]≀C3β€²log⁑(C2β€²T0) T02/3+4pmax⁑L T0 Eβˆ₯ΞΈ^βˆ’ΞΈ0βˆ₯1,\mathbb E\Big[\sum_{t = s_0 + 1}^{s_0 + T_0} r_t\Big] \le C'_3\log(C'_2T_0)\,T_0^{2/3} + 4p_{\max}L\,T_0\,\mathbb E\|\hat\theta - \theta_0\|_1,E[t=s0​+1βˆ‘s0​+T0​​rt​]≀C3′​log(C2′​T0​)T02/3​+4pmax​LT0​Eβˆ₯ΞΈ^βˆ’ΞΈ0​βˆ₯1​,

where rtr_trt​ is the per-period regret (1).

In the proof of Theorem 1 this is the step E(Rkβ€²βˆ£ΞΈ^kβˆ’1)≀C3β€²log⁑(C2β€²β„“k)β„“k2/3+4Lβˆ₯ΞΈ0βˆ’ΞΈ^kβˆ’1βˆ₯1pmax⁑ℓk\mathbb E(R'_k \mid \hat\theta_{k-1}) \le C'_3\log(C'_2\ell_k)\ell_k^{2/3} + 4L\|\theta_0 - \hat\theta_{k-1}\|_1p_{\max}\ell_kE(Rkβ€²β€‹βˆ£ΞΈ^kβˆ’1​)≀C3′​log(C2′​ℓk​)β„“k2/3​+4Lβˆ₯ΞΈ0β€‹βˆ’ΞΈ^kβˆ’1​βˆ₯1​pmax​ℓk​ followed by taking expectations: it is Proposition 3 (whose estimate is deterministic and whose episode starts at period 1) applied conditionally on the history up to the start of the episode. It is the only probabilistic input needed to sum the episode regrets of DIP into Theorem 1.

Formalization Note The constants are chosen exactly as in Proposition 3(b): after CdC_dCd​ and Ξ»\lambdaΞ» and before the probability space, the episode start s0s_0s0​, the length T0T_0T0​ and the estimate. Expectations are lower Lebesgue integrals of nonnegative quantities, written with ENNReal.ofReal.

Preamble
import Mathlib
import Definitions.Def_LuoSunLiu_DIP_Model
import Definitions.Def_LuoSunLiu_DIP_InnerB

open MeasureTheory ProbabilityTheory NNReal ENNReal
Formal statement
namespace LuoSunLiu.DIP

/-- Proposition 3(b) applied to an episode with a random, previously computed estimate (Luo, Sun
and Liu, arXiv:2109.07340v2, proof of Theorem 1, p. 55: "for the regret `R'_k` in episode
`2 ≀ k ≀ n`, we have by Proposition 3, `E(R'_k | ΞΈΜ‚_{k-1}) ≀ C′₃ log(Cβ€²β‚‚β„“_k)β„“_k^{2/3} +
4Lβ€–ΞΈβ‚€ - ΞΈΜ‚_{k-1}‖₁p_max β„“_k`; therefore `E(R'_k) ≀ C′₃ log(Cβ€²β‚‚β„“_k)β„“_k^{2/3} +
4p_max L Eβ€–ΞΈΜ‚_{k-1} - θ₀‖₁ β„“_k`"). For every discretization constant `C_d` with
`p_max + 2W < C_d p_max` and every `Ξ» > 0` there are constants `Cβ€²β‚‚, C′₃ > 0` such that: for every
pricing environment, every episode of `Tβ‚€ β‰₯ 1` periods `sβ‚€ + 1, …, sβ‚€ + Tβ‚€`, and every estimate
`ΞΈΜ‚` that is `𝒒_{sβ‚€}`-measurable with `‖θ̂‖₁ ≀ W`, if on every sample path the prices of the
episode are a run of Inner Algorithm B with input `ΞΈΜ‚`, `d = C_d⌈Tβ‚€^{1/6}βŒ‰`, `Ξ΄ = 1/Tβ‚€` and
`Ξ² = Ξ²*`, then the expected regret of the episode is at most
`C′₃ log(Cβ€²β‚‚Tβ‚€) Tβ‚€^{2/3} + 4p_max L Tβ‚€ Eβ€–ΞΈΜ‚ - θ₀‖₁`. -/
theorem proposition_3_conditional {d0 : β„•} (M : PricingModel d0) (hM : M.Standing) (L : ℝβ‰₯0)
    (hL : LipschitzWith L M.F) (CA : ℝ) (hA2 : Assumption2 M CA)
    (Cdisc : β„•) (hCdisc : M.pmax + 2 * M.W < Cdisc * M.pmax) (lam : ℝ) (hlam : 0 < lam) :
    βˆƒ C2' C3' : ℝ, 0 < C2' ∧ 0 < C3' ∧
      βˆ€ (Ξ© : Type*) (mΞ© : MeasurableSpace Ξ©) [StandardBorelSpace Ξ©]
        (P : Measure Ξ©) [IsProbabilityMeasure P] (𝒒 : Filtration β„• mΞ©)
        (x : β„• β†’ Ξ© β†’ Fin d0 β†’ ℝ) (z p : β„• β†’ Ξ© β†’ ℝ), IsPricingEnv M P 𝒒 x z p β†’
      βˆ€ (s0 T0 : β„•), 1 ≀ T0 β†’
      βˆ€ (ΞΈh : Ξ© β†’ Fin d0 β†’ ℝ), Measurable[𝒒 s0] ΞΈh β†’ (βˆ€ Ο‰, l1 (ΞΈh Ο‰) ≀ M.W) β†’
      (βˆ€ Ο‰, βˆƒ j : β„• β†’ Fin (Cdisc * ⌈(T0 : ℝ) ^ ((1 : ℝ) / 6)βŒ‰β‚Š),
        IsInnerBRun M.pmax (ΞΈh Ο‰) lam
          (betaStar M.pmax lam (Cdisc * ⌈(T0 : ℝ) ^ ((1 : ℝ) / 6)βŒ‰β‚Š) (1 / (T0 : ℝ))) s0 T0
          (fun t => x t Ο‰) j (fun t => p t Ο‰) (fun t => response M x z p t Ο‰)) β†’
      ∫⁻ Ο‰, ENNReal.ofReal (βˆ‘ t ∈ Finset.Icc (s0 + 1) (s0 + T0), perRegret M (x t Ο‰) (p t Ο‰)) βˆ‚P ≀
        ENNReal.ofReal (C3' * Real.log (C2' * T0) * (T0 : ℝ) ^ ((2 : ℝ) / 3)) +
          ENNReal.ofReal (4 * M.pmax * L * T0) *
            ∫⁻ Ο‰, ENNReal.ofReal (l1 (ΞΈh Ο‰ - M.ΞΈ0)) βˆ‚P := by sorry

end LuoSunLiu.DIP
Source
Luo, Sun and Liu, Distribution-free contextual dynamic pricing, arXiv:2109.07340v2, proof of Theorem 1, p. 55 (the step 'For the regret R'_k in episode 2 ≀ k ≀ n, we have by Proposition 3, E(R'_k | ΞΈΜ‚_{kβˆ’1}) ≀ ... Therefore, we obtain E(R'_k) ≀ ...'), applying Proposition 3 (pp. 22–23, proof pp. 52–54)

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