Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 4, p. 23 — w.p. ≥ 1 − δ, R_{T₀,1} ≤ 2√(2dT₀β*_{T₀} log((dλ + T₀p²_max)/(dλ))) + 4p_max L‖θ̂ − θ₀‖₁T₀ + 2dp_max

Proved
LuoSunLiu.DIP.proposition_4

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

dynamic-pricingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regretucb

Let FFF be LLL-Lipschitz (Assumption 1) and let the standing assumptions of the pricing model hold. Fix an estimate θ^\hat\thetaθ^ and d≥1d \ge 1d≥1 with pmax⁡+2∥θ^∥1<d pmax⁡p_{\max} + 2\|\hat\theta\|_1 < d\,p_{\max}pmax​+2∥θ^∥1​<dpmax​, and let λ>0\lambda > 0λ>0, δ∈(0,1)\delta \in (0, 1)δ∈(0,1) and T0≥1T_0 \ge 1T0​≥1. Suppose that on every sample path the prices of periods 1,…,T01, \dots, T_01,…,T0​ are a run of Inner Algorithm B (Algorithm 3) with estimate θ^\hat\thetaθ^ and βt=βt∗\beta_t = \beta^*_tβt​=βt∗​. Then with probability at least 1−δ1 - \delta1−δ the discrete-part regret satisfies

RT0,1≤22dT0βT0∗log⁡dλ+T0pmax⁡2dλ+4pmax⁡L∥θ^−θ0∥1T0+2dpmax⁡.R_{T_0,1} \le 2\sqrt{2dT_0\beta^*_{T_0}\log\frac{d\lambda + T_0p_{\max}^2}{d\lambda}} + 4p_{\max}L\|\hat\theta - \theta_0\|_1T_0 + 2dp_{\max}.RT0​,1​≤22dT0​βT0​∗​logdλdλ+T0​pmax2​​​+4pmax​L∥θ^−θ0​∥1​T0​+2dpmax​.

Here RT0,1=∑t=1T0(p~t∗(1−F(p~t∗−xt⊤θ0))−pt(1−F(pt−xt⊤θ0)))R_{T_0,1} = \sum_{t=1}^{T_0}\bigl(\tilde p^*_t(1 - F(\tilde p^*_t - x_t^\top\theta_0)) - p_t(1 - F(p_t - x_t^\top\theta_0))\bigr)RT0​,1​=∑t=1T0​​(p~​t∗​(1−F(p~​t∗​−xt⊤​θ0​))−pt​(1−F(pt​−xt⊤​θ0​))) and p~t∗\tilde p^*_tp~​t∗​ is the best price in the candidate set St\mathcal S_tSt​.

This is the regret against the best grid price; Proposition 3 adds the discretization error.

Formalization Note The hypothesis pmax⁡+2∥θ^∥1<d pmax⁡p_{\max} + 2\|\hat\theta\|_1 < d\,p_{\max}pmax​+2∥θ^∥1​<dpmax​ (grid step below pmax⁡p_{\max}pmax​) is added: it makes every candidate set St\mathcal S_tSt​ nonempty, without which Algorithm 3 cannot post a price. "With probability at least 1−δ1-\delta1−δ" is the inner-measure reading (a measurable event of probability at least 1−δ1-\delta1−δ). Covariates may be adaptive or adversarial, and G\mathcal GG is any filtration as in the model.

Preamble
import Mathlib
import Definitions.Def_LuoSunLiu_DIP_Model
import Definitions.Def_LuoSunLiu_DIP_InnerB

open MeasureTheory ProbabilityTheory NNReal
Formal statement
namespace LuoSunLiu.DIP

/-- Proposition 4 (Luo, Sun and Liu, arXiv:2109.07340v2, p. 23; proof pp. 46–49). Under
Assumption 1 (`F` is `L`-Lipschitz), for a single episode with fixed estimate `θ̂`, `d` grid
points with `p_max + 2‖θ̂‖₁ < d p_max`, `λ > 0` and `δ ∈ (0, 1)`, if on every sample path the
prices up to `T₀` are a run of Inner Algorithm B with `β_t = β*_t`, then with probability at least
`1 - δ` the discrete-part regret satisfies
`R_{T₀,1} ≤ 2√(2dT₀β*_{T₀} log((dλ + T₀p²_max)/(dλ))) + 4p_max L‖θ̂ - θ₀‖₁T₀ + 2dp_max`. -/
theorem proposition_4 {d0 : ℕ} (M : PricingModel d0) (hM : M.Standing) (L : ℝ≥0)
    (hL : LipschitzWith L M.F) (θh : Fin d0 → ℝ) (d : ℕ) (hd : 1 ≤ d)
    (hgrid : M.pmax + 2 * l1 θh < d * M.pmax) (lam δ : ℝ) (hlam : 0 < lam)
    (hδ : δ ∈ Set.Ioo (0 : ℝ) 1)
    {Ω : Type*} {mΩ : MeasurableSpace Ω} [StandardBorelSpace Ω]
    (P : Measure Ω) [IsProbabilityMeasure P] (𝒢 : Filtration ℕ mΩ)
    (x : ℕ → Ω → Fin d0 → ℝ) (z p : ℕ → Ω → ℝ) (hEnv : IsPricingEnv M P 𝒢 x z p)
    (T0 : ℕ) (hT0 : 1 ≤ T0)
    (hrun : ∀ ω, ∃ j : ℕ → Fin d, IsInnerBRun M.pmax θh lam (betaStar M.pmax lam d δ) 0 T0
      (fun t => x t ω) j (fun t => p t ω) (fun t => response M x z p t ω)) :
    ∃ E : Set Ω, MeasurableSet E ∧ ENNReal.ofReal (1 - δ) ≤ P E ∧
      ∀ ω ∈ E, discreteRegret M θh d x p T0 ω ≤
        2 * Real.sqrt (2 * d * T0 * betaStar M.pmax lam d δ T0 *
          Real.log ((d * lam + T0 * M.pmax ^ 2) / (d * lam))) +
        4 * M.pmax * L * l1 (θh - M.θ0) * T0 + 2 * d * M.pmax := by sorry

end LuoSunLiu.DIP
Source
Luo, Sun and Liu, arXiv:2109.07340v2, p. 23, Proposition 4; proof pp. 46–49
Human review
  • Endorsed by Shuze Chen · Oct 10, 2026

    Confirmed by the moderator at approval.

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