Lemmas C.29–C.30 (v1) — inverse local moments of the compensated process on a surviving window
ProvedIAFTRL.lemma_C_37_inv_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.
Fix a window and a threshold . Let be the indicator that the budget is not exceeded before and that for . Consider the compensated process
Assume , , , and the local thresholds and for . Then for every ,
On the surviving window, and the increments satisfy (C.198). The inverse moment controls small estimated gaps and hence the failure probability of the common good event (Lemma C.26).
Formalization Note is written ; the two agree on .
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
/-- **Inverse local moments.** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*,
arXiv:2611.01299v1, Lemmas C.29–C.30 ((C.198), (C.201)), for the abstract interface `C37.Iface`:
on the surviving window `I_s` (budget not exceeded, `F_j ≤ θ^P` for `m ≤ j ≤ s`) the compensated
process `Y_t = X_{t,a} − Σ_{i<t} e_{i,a} + 2C + 2θ` satisfies `E[I_t Y_t^{−P}] ≤ (4/(nΔ(a)))^P`,
provided `2(m+1) ≤ n = t + 1`, `θ ≥ 2(P+1)`, `P + 1 ≤ 2(m+1)` and the local thresholds
`3Bβ_{s+1} ≤ θ`, `20(P+1)β_{s+1}(s+1) ≤ θ²` hold on the window. -/
theorem lemma_C_37_inv_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 < θ) (ha : a ≠ jstar) (hmt : m ≤ t) (htT : t ≤ T)
(hmhalf : 2 * ((m : ℝ) + 1) ≤ (t : ℝ) + 1)
(hθP : 2 * ((C37.Pord K : ℝ) + 1) ≤ θ) (hmP : (C37.Pord K : ℝ) + 1 ≤ 2 * ((m : ℝ) + 1))
(hQ1 : ∀ s, m ≤ s → s < t → 3 * Bc K * beta d K (s + 1) ≤ θ)
(hQ2 : ∀ s, m ≤ s → s < t →
20 * ((C37.Pord K : ℝ) + 1) * beta d K (s + 1) * ((s : ℝ) + 1) ≤ θ ^ 2) :
∫ ω, C37.Ii C κ X m θ t ω * (1 / max θ (C37.Yc C θ X e t a ω)) ^ C37.Pord K ∂μ ≤
(4 / (((t : ℝ) + 1) * Δ a)) ^ C37.Pord K := by sorry
end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Lemma C.29 (C.197)–(C.200) and Lemma C.30 (C.201)–(C.205), pp.81–83