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βΞΈΜ β ΞΈβββ
ProvedLuoSunLiu.DIP.proposition_3_conditionalThis 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 (, , on , and maximizes over ), let be -Lipschitz (Assumption 1), and let Assumption 2 hold with constant . Fix a discretization constant with and a regularization parameter .
Then there are constants with the following property. Let be a probability space on a standard Borel space with a filtration , and let covariates , prices and noise form a pricing environment (covariates and prices -measurable, -measurable with CDF and independent of ). Consider an episode of periods and a random estimate that is -measurable with . Suppose that on every sample path the prices of the episode are a run of Inner Algorithm B with input , grid points, confidence level , confidence parameters and regularization . Then
where is the per-period regret (1).
In the proof of Theorem 1 this is the step 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 and and before the probability space, the episode start , the length and the estimate. Expectations are lower Lebesgue integrals of nonnegative quantities, written with ENNReal.ofReal.
import Mathlib import Definitions.Def_LuoSunLiu_DIP_Model import Definitions.Def_LuoSunLiu_DIP_InnerB open MeasureTheory ProbabilityTheory NNReal ENNReal
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