Killed positive moment of a scalar interface process with bounded drift
ProvedG26.SI.pos_momentbandit-algorithmslinear-banditsonline-learning
Throughout, is a probability space, are sub--algebras, is a process, are alive events with , and , , are reals. The scalar interface asks that and be -measurable, that be a.s. bounded, and that for (resp. ), almost surely on ,
Write (kpos). Assume holds, , , , , and that bounds the drift: a.s. on , for . Assume , for , and for some . With ,
This is the upper local moment used for the compensated normalized variables on the alive window: the per-step growth is at most linear in time plus a slowly growing contribution of the starting value.
Formalization Note Rounds are 0-based.
Preamble
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body
import Definitions.Def_IAFTRL_G26_run
import Definitions.Def_IAFTRL_G26_window
open MeasureTheory ProbabilityTheory Set
open G26
variable {Ω : Type*}
variable [mΩ : MeasurableSpace Ω] {μ : Measure Ω} {F : ℕ → MeasurableSpace Ω}
{Y : ℕ → Ω → ℝ} {I : ℕ → Set Ω} {m N : ℕ} {τ β : ℕ → ℝ} {B : ℝ}Formal statement
theorem G26.SI.pos_moment [IsProbabilityMeasure μ] (S : SI μ F Y I m N τ β B) {P : ℕ} (hP : 2 ≤ P)
(hPB : 8 * (P : ℝ) ≤ B) {t : ℕ} (hmt : m ≤ t) (htN : t ≤ N) {A : ℝ} (hA0 : 0 ≤ A)
(Dh : ℕ → ℝ) (hDh : ∀ s, 0 ≤ Dh s)
(hdr : ∀ n, m ≤ n → n < t → ∀ᵐ ω ∂μ, ω ∈ I n → μ[fun ω => Y (n + 1) ω - Y n ω | F n] ω ≤ Dh n)
(hA : ∀ s, m ≤ s → s < t → Dh s + 10 * ((P : ℝ) - 1) * β s / τ s ≤ A)
(hβ : ∀ n, 0 ≤ β n) {w0 : ℝ} (hw0 : 0 < w0) (hW0 : kpos μ Y I P m ≤ w0 ^ P) :
kpos μ Y I P t ≤ (A * ((t : ℝ) + 1) / (1 - 2 * ((P : ℝ) - 1) / B) +
w0 * (((t : ℝ) + 1) / ((m : ℝ) + 1)) ^ (2 * (2 * ((P : ℝ) - 1) / B))) ^ P := by sorrySource
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Appendix G, Lemma G.28 (p.178), second estimate of (G.568), abstracted