Lemma C.14 (v1) — positive local moments of the compensated process on a surviving window
ProvedIAFTRL.lemma_C_37_pos_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.
With the window , threshold , surviving-window indicator and compensated process as in Lemma C.30, assume:
- and for ;
- the initial moment satisfies with .
Then
This is the positive local moment bound behind the distortion factor of Lemma C.14. The linear term carries the drift , and the initial moment decays relative to because .
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
/-- **Positive local moments.** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*,
arXiv:2611.01299v1, Lemma C.14 ((C.120)–(C.123)), for the abstract interface `C37.Iface`: on the
surviving window, if `3Bβ_{s+1} ≤ θ` and `Δ(a) + 5(P−1)β_{s+1}/θ ≤ A` for `m ≤ s < t`, and the
initial moment satisfies `E[I_m Y_m^P] ≤ w₀^P`, then
`E[I_t Y_t^P] ≤ (A n/(1 − κ₀) + w₀ (n/(m+1))^{2κ₀})^P` with `n = t + 1`, `κ₀ = 2(P−1)/B`. -/
theorem lemma_C_37_pos_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 κ) (m : ℕ) (θ : ℝ) (t : ℕ) (a : Fin K)
(hθ : 0 < θ) (hmt : m ≤ t) (htT : t ≤ T)
(hQ1 : ∀ s, m ≤ s → s < t → 3 * Bc K * beta d K (s + 1) ≤ θ)
(A : ℝ) (hA0 : 0 ≤ A)
(hA : ∀ s, m ≤ s → s < t → Δ a + 5 * ((C37.Pord K : ℝ) - 1) * beta d K (s + 1) / θ ≤ A)
(w0 : ℝ) (hw0 : 0 < w0)
(hW0 : ∫ ω, C37.Ii C κ X m θ m ω * C37.Yc C θ X e m a ω ^ C37.Pord K ∂μ ≤ w0 ^ C37.Pord K) :
∫ ω, C37.Ii C κ X m θ t ω * C37.Yc C θ X e t a ω ^ C37.Pord K ∂μ ≤
(A * ((t : ℝ) + 1) / (1 - C37.kap0 K) + w0 * (((t : ℝ) + 1) / ((m : ℝ) + 1)) ^ (2 * C37.kap0 K)) ^
C37.Pord K := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Lemma C.14 (C.118)–(C.125), pp.66–68, with Lemma C.29