Lemmas C.31, C.33, C.28 (v1) — stopped negative moments and the window failure probability
ProvedIAFTRL.lemma_C_37_windowThroughout, the processes satisfy the full-history scalar difference interface of Lemma C.34 (bundled as C37.Iface). There are actions with a distinguished action and gaps , . The processes satisfy , and , and with , and . The increments obey and , where . Here , , , , and is the paper's round.
Let be the remaining budget and the power sum of negative parts of the budget-shifted differences. Fix a start time with , and , a window with , and a level . Then
where and are the negative-moment constants (Definition C.32, with ).
The bound combines the shifted negative-moment recursion , its initialization , and the stopped process of Lemma C.28. It is the window-failure input of Lemma C.26.
Formalization Note The left side is , where is the indicator of (C37.sv).
import Mathlib import Definitions.Def_IAFTRL_beta import Definitions.Def_IAFTRL_Bc import Definitions.Def_IAFTRL_C37_scalar
namespace IAFTRL
open MeasureTheory
/-- **Window failure probability via stopped negative moments.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Lemmas C.31, C.33 and C.28 ((C.193)–(C.194)), for the abstract
interface `C37.Iface`: with `F_j = Σ_a (2b_j − X_{j,a})_+^P` (`b_j = C − Σ_{s<j} κ_s`), a start time
`t₀` after the burn-in with `C ≤ t₀ + 1`, a window `[m, t]` with `t₀ ≤ m`, and any level `L ≥ 0`,
`L · P(∃ j ∈ [m, t], F_j > L) ≤ H_0 n^ν + (64 n₀)^P (n/n₀)^q` where `n = t + 1`, `n₀ = t₀ + 1`. -/
theorem lemma_C_37_window {d K : ℕ} {jstar : Fin K} {Δ : Fin K → ℝ} {Δ₀ : ℝ} {Ω : Type*}
[mΩ : MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {F : ℕ → MeasurableSpace Ω}
{T : ℕ} {C : ℝ} {X D e : ℕ → Fin K → Ω → ℝ} {κ : ℕ → Ω → ℝ}
(I : C37.Iface d K jstar Δ Δ₀ μ F T C X D e κ) (t0 m t : ℕ) (L : ℝ)
(hL : 0 ≤ L) (ht0m : t0 ≤ m) (hmt : m ≤ t) (htT : t ≤ T)
(hburn : C37.HG d K ≤ ((t0 : ℝ) + 1) ^ ((C37.Pord K : ℝ) / 4)) (hCn : C ≤ (t0 : ℝ) + 1) :
L * ∫ ω, (1 - C37.sv C κ X m L (t + 1) ω) ∂μ ≤ C37.HN d K * ((t : ℝ) + 1) ^ C37.nuP K +
(64 * ((t0 : ℝ) + 1)) ^ C37.Pord K * (((t : ℝ) + 1) / ((t0 : ℝ) + 1)) ^ C37.qN K := by sorry
end IAFTRL