Lemma G.9 — direct corruption contribution of GIA-FTRL
ProvedIAFTRL.lemma_G_9bandit-algorithmslinear-banditsonline-learning
Setting. A GIA-FTRL run of rounds in the corrupted regime with budget : , , and almost surely.
Claim.
The paper states the slightly smaller constant .
Proof idea.
- Marginal domination gives for a probability measure .
- On the range of is at most , where .
- With , it remains to show . Split at .
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL import Definitions.Def_IAFTRL_GTerms
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **Lemma G.9 (Direct corruption contribution).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Lemma G.9, p.137: "For
`κ_t = ‖c_t^vec‖_𝒜` with `0 ≤ κ_t ≤ 2` and `Σ_t κ_t ≤ C` almost surely,
`I₄ := Σ_t E[⟨p_t − q_t, xᵀc_t^vec⟩] ≤ 16√2 d √C`."
Stated with the slightly larger constant `32 d`: for every GIA-FTRL run of `T ≥ 1` rounds in the
corrupted regime with budget `C ≥ 0`, `I₄ ≤ 32 d √C`. -/
theorem lemma_G_9 {d : ℕ} (hd : 1 ≤ d) (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ)
(h𝒜 : IsCompact 𝒜) (hℬ : IsCompact ℬ) (hgen : IsGenerator 𝒜 ℬ)
(hball : ∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) (hspan : Submodule.span ℝ 𝒜 = ⊤) (hk : 1 ≤ kdim ℬ)
(θ : Fin d → ℝ) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(T : ℕ) (C : ℝ) (R : GRun d Ω) (hT : 1 ≤ T) (hC : 0 ≤ C) (hR : IsGIAFTRLRun P 𝒜 ℬ e T R)
(hcor : IsCorruptedG P 𝒜 θ C T R) :
corrI4 P ℬ e T R θ ≤ 32 * d * Real.sqrt C := by sorry
end IAFTRL
Source
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.5, Lemma G.9, (G.148)–(G.151)