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₀
ProvedLuoSunLiu.DIP.proposition_3Let the standing assumptions of the pricing model hold, let be -Lipschitz (Assumption 1), and let Assumption 2 hold with constant . Consider one episode of Inner Algorithm B with , started at period , with an input estimate satisfying . Write for the regret (1).
- High-probability bound. There is a constant , depending only on the model and , such that for every such , every with , every , , and every run, with probability at least ,
- Expected bound. For every discretization constant with and every there are constants such that, with and , for every such , every and every run,
Applied to episode of DIP with , part 2 gives the per-episode bound from which Theorem 1 follows.
Formalization Note The printed statement uses the letter twice: for the continuous-part constant (, p. 53) and for the discretization constant in ; here they are and . The printed is pinned to , the form the proof derives (p. 54). Two hypotheses the proof uses are made explicit: (the input is a projection onto , p. 53) and (part of the standing assumptions). The grid hypothesis (, resp. ) makes every candidate set nonempty. All constants are chosen before , the probability space and ; this uniformity is what the proof gives and what Theorem 1 needs. Expectations are lower Lebesgue integrals of the nonnegative regret.
import Mathlib import Definitions.Def_LuoSunLiu_DIP_Model import Definitions.Def_LuoSunLiu_DIP_InnerB open MeasureTheory ProbabilityTheory NNReal
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.