Lemmas C.36–C.37 (v1) — absolute -th moments of the difference interface after the burn-in
ProvedIAFTRL.lemma_C_37_abs_momentsbandit-algorithmslinear-banditsonline-learning
Throughout, 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 . If , where is the constant of Definition C.35, then
This is the universal absolute-moment bound of Lemma C.37 combined with the burn-in of Lemma C.36. It controls the initial values of the windows used for the local moment estimates and the initial negative moment in (C.221).
Preamble
import Mathlib import Definitions.Def_IAFTRL_beta import Definitions.Def_IAFTRL_Bc import Definitions.Def_IAFTRL_C37_scalar
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Absolute moments after the burn-in.** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*,
arXiv:2611.01299v1, Lemmas C.36–C.37 ((C.234)–(C.235)), for the abstract scalar difference interface
`C37.Iface` ((C.226)–(C.228) of Lemma C.34): with `G_t = Σ_a X_{t,a}^P`, `n = t + 1`,
`k = K^{1/P}`, once `n^{P/4} ≥ H_G`, `E[G_t] ≤ ((16k + 1) n)^P`. -/
theorem lemma_C_37_abs_moments {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 κ) (t : ℕ) (ht : t ≤ T)
(hburn : C37.HG d K ≤ ((t : ℝ) + 1) ^ ((C37.Pord K : ℝ) / 4)) :
∫ ω, C37.Gsum X t ω ∂μ ≤ ((16 * C37.kK K + 1) * ((t : ℝ) + 1)) ^ C37.Pord K := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Lemmas C.36–C.37, (C.229)–(C.240), pp.88–90