Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3, pp. 22–23 — single-episode regret: w.p. ≥ 1 − δ bound, and E(R_{T₀}) ≤ C′₃ log(C′₂T₀)T₀^{2/3} + 4p_max L‖θ̂ − θ₀‖₁T₀

Proved
LuoSunLiu.DIP.proposition_3

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

discretizationdynamic-pricingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Let the standing assumptions of the pricing model hold, let FFF be LLL-Lipschitz (Assumption 1), and let Assumption 2 hold with constant CAC_ACA​. Consider one episode of Inner Algorithm B with βt=βt∗\beta_t = \beta^*_tβt​=βt∗​, started at period 111, with an input estimate θ^\hat\thetaθ^ satisfying ∥θ^∥1≤W\|\hat\theta\|_1 \le W∥θ^∥1​≤W. Write RT0=∑t=1T0rtR_{T_0} = \sum_{t=1}^{T_0} r_tRT0​​=∑t=1T0​​rt​ for the regret (1).

  1. High-probability bound. There is a constant C>0C > 0C>0, depending only on the model and CAC_ACA​, such that for every such θ^\hat\thetaθ^, every d≥1d \ge 1d≥1 with pmax⁡+2∥θ^∥1<d pmax⁡p_{\max} + 2\|\hat\theta\|_1 < d\,p_{\max}pmax​+2∥θ^∥1​<dpmax​, every λ>0\lambda > 0λ>0, δ∈(0,1)\delta \in (0, 1)δ∈(0,1), T0≥1T_0 \ge 1T0​≥1 and every run, with probability at least 1−δ1 - \delta1−δ,
RT0≤22dT0βT0∗log⁡dλ+T0pmax⁡2dλ+4pmax⁡L∥θ^−θ0∥1T0+CT0d2+2dpmax⁡.R_{T_0} \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 + C\frac{T_0}{d^2} + 2dp_{\max}.RT0​​≤22dT0​βT0​∗​logdλdλ+T0​pmax2​​​+4pmax​L∥θ^−θ0​∥1​T0​+Cd2T0​​+2dpmax​.
  1. Expected bound. For every discretization constant CdC_dCd​ with pmax⁡+2W<Cd pmax⁡p_{\max} + 2W < C_d\,p_{\max}pmax​+2W<Cd​pmax​ and every λ>0\lambda > 0λ>0 there are constants C2′,C3′>0C'_2, C'_3 > 0C2′​,C3′​>0 such that, with δ=1/T0\delta = 1/T_0δ=1/T0​ and d=Cd⌈T01/6⌉d = C_d\lceil T_0^{1/6}\rceild=Cd​⌈T01/6​⌉, for every such θ^\hat\thetaθ^, every T0≥1T_0 \ge 1T0​≥1 and every run,
E(RT0)≤C3′log⁡(C2′T0) T02/3+4pmax⁡L∥θ^−θ0∥1T0.\mathbb E(R_{T_0}) \le C'_3\log(C'_2T_0)\,T_0^{2/3} + 4p_{\max}L\|\hat\theta - \theta_0\|_1T_0 .E(RT0​​)≤C3′​log(C2′​T0​)T02/3​+4pmax​L∥θ^−θ0​∥1​T0​.

Applied to episode kkk of DIP with θ^=θ^k−1\hat\theta = \hat\theta_{k-1}θ^=θ^k−1​, part 2 gives the per-episode bound from which Theorem 1 follows.

Formalization Note The printed statement uses the letter CCC twice: for the continuous-part constant (C=C2C32C = C_2C_3^2C=C2​C32​, p. 53) and for the discretization constant in d=C⌈T01/6⌉d = C\lceil T_0^{1/6}\rceild=C⌈T01/6​⌉; here they are CCC and CdC_dCd​. The printed O~(T02/3)\tilde O(T_0^{2/3})O~(T02/3​) is pinned to C3′log⁡(C2′T0)T02/3C'_3\log(C'_2T_0)T_0^{2/3}C3′​log(C2′​T0​)T02/3​, the form the proof derives (p. 54). Two hypotheses the proof uses are made explicit: ∥θ^∥1≤W\|\hat\theta\|_1 \le W∥θ^∥1​≤W (the input is a projection onto Θ\ThetaΘ, p. 53) and p∗(x)∈(0,pmax⁡)p^*(x) \in (0, p_{\max})p∗(x)∈(0,pmax​) (part of the standing assumptions). The grid hypothesis (pmax⁡+2∥θ^∥1<d pmax⁡p_{\max} + 2\|\hat\theta\|_1 < d\,p_{\max}pmax​+2∥θ^∥1​<dpmax​, resp. pmax⁡+2W<Cd pmax⁡p_{\max} + 2W < C_d\,p_{\max}pmax​+2W<Cd​pmax​) makes every candidate set nonempty. All constants are chosen before θ^\hat\thetaθ^, the probability space and T0T_0T0​; this uniformity is what the proof gives and what Theorem 1 needs. Expectations are lower Lebesgue integrals of the nonnegative regret.

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 3 (Luo, Sun and Liu, arXiv:2109.07340v2, pp. 22–23; proof pp. 52–54). Under
Assumptions 1–2, for a single episode run of Inner Algorithm B with `β_t = β*_t` and an input
estimate `θ̂` with `‖θ̂‖₁ ≤ W`:
(a) there is a constant `C` (depending only on the model and the constant of Assumption 2) such
that, whenever `p_max + 2‖θ̂‖₁ < d p_max`, `λ > 0`, `δ ∈ (0, 1)` and `T₀ ≥ 1`, with probability at
least `1 - δ`,
`R_{T₀} ≤ 2√(2dT₀β*_{T₀} log((dλ + T₀p²_max)/(dλ))) + 4p_max L‖θ̂ - θ₀‖₁T₀ + C T₀/d² + 2dp_max`;
(b) 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 with `δ = 1/T₀` and `d = C_d ⌈T₀^{1/6}⌉`,
`E(R_{T₀}) ≤ C′₃ log(C′₂T₀) T₀^{2/3} + 4p_max L‖θ̂ - θ₀‖₁T₀` for every `T₀ ≥ 1` (the `Õ` of the
printed statement, pinned from the proof, p. 54). -/
theorem proposition_3 {d0 : ℕ} (M : PricingModel d0) (hM : M.Standing) (L : ℝ≥0)
    (hL : LipschitzWith L M.F) (CA : ℝ) (hA2 : Assumption2 M CA) :
    (∃ Ccont : ℝ, 0 < Ccont ∧
      ∀ (θh : Fin d0 → ℝ), l1 θh ≤ M.W → ∀ (d : ℕ), 1 ≤ d → M.pmax + 2 * l1 θh < d * M.pmax →
      ∀ (lam δ : ℝ), 0 < lam → δ ∈ Set.Ioo (0 : ℝ) 1 →
      ∀ (Ω : Type*) (mΩ : MeasurableSpace Ω) [StandardBorelSpace Ω]
        (P : Measure Ω) [IsProbabilityMeasure P] (𝒢 : Filtration ℕ mΩ)
        (x : ℕ → Ω → Fin d0 → ℝ) (z p : ℕ → Ω → ℝ), IsPricingEnv M P 𝒢 x z p →
      ∀ (T0 : ℕ), 1 ≤ T0 →
      (∀ ω, ∃ 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, cumRegret M 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 + Ccont * T0 / (d : ℝ) ^ 2 +
          2 * d * M.pmax) ∧
    (∀ (Cdisc : ℕ), M.pmax + 2 * M.W < Cdisc * M.pmax → ∀ (lam : ℝ), 0 < lam →
      ∃ C2' C3' : ℝ, 0 < C2' ∧ 0 < C3' ∧
      ∀ (θh : Fin d0 → ℝ), l1 θh ≤ M.W →
      ∀ (Ω : Type*) (mΩ : MeasurableSpace Ω) [StandardBorelSpace Ω]
        (P : Measure Ω) [IsProbabilityMeasure P] (𝒢 : Filtration ℕ mΩ)
        (x : ℕ → Ω → Fin d0 → ℝ) (z p : ℕ → Ω → ℝ), IsPricingEnv M P 𝒢 x z p →
      ∀ (T0 : ℕ), 1 ≤ T0 →
      (∀ ω, ∃ j : ℕ → Fin (Cdisc * ⌈(T0 : ℝ) ^ ((1 : ℝ) / 6)⌉₊),
        IsInnerBRun M.pmax θh lam
          (betaStar M.pmax lam (Cdisc * ⌈(T0 : ℝ) ^ ((1 : ℝ) / 6)⌉₊) (1 / (T0 : ℝ))) 0 T0
          (fun t => x t ω) j (fun t => p t ω) (fun t => response M x z p t ω)) →
      ∫⁻ ω, ENNReal.ofReal (cumRegret M x p T0 ω) ∂P ≤
        ENNReal.ofReal (C3' * Real.log (C2' * T0) * (T0 : ℝ) ^ ((2 : ℝ) / 3) +
          4 * M.pmax * L * l1 (θh - M.θ0) * T0)) := by sorry

end LuoSunLiu.DIP
Source
Luo, Sun and Liu, arXiv:2109.07340v2, pp. 22–23, Proposition 3; proof pp. 52–54
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