Lemma G.4 — relative-entropy stability contribution of GIA-FTRL
ProvedIAFTRL.lemma_G_4bandit-algorithmslinear-banditsonline-learning
Setting. The setting is that of Proposition G.1 (proposition_G_1_anc):
- a GIA-FTRL run on a compact generator of a compact spanning , with ;
- a sharp instance with and unique optimal action ;
- the corrupted regime almost surely.
The sums are those of the definition IAFTRL_GTerms.
Claim. There are constants , independent of , and the run, with
This is Lemma G.4, , combined with the weighted failure estimate.
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.4 (Relative-entropy stability contribution).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Lemma G.4, p.130:
"For `D_t = ⟨q_t, f̂_t⟩ + β_t log⟨q_t, e^{−f̂_t/β_t}⟩`, `I₂ := Σ_t E[D_t] ≤ 34e² A_L T*^{−9/2} + 2d E_T`",
combined with the weighted failure estimate (G.11)–(G.13) (Lemma G.26).
In the sharp corrupted setting there are instance constants `M, J` (independent of `T`, `C` and the
run) with `I₂ ≤ M + J √C log(e + C)`. -/
theorem lemma_G_4 {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 ℬ)
(he : Function.Surjective e) (θ astar : Fin d → ℝ) (hθ : setNorm 𝒜 θ ≤ 1)
(hastar : astar ∈ 𝒜) (huniq : ∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ)
(hsharp : IsSharp 𝒜 θ astar) :
∃ M J : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(T : ℕ) (C : ℝ) (R : GRun d Ω), 1 ≤ T → 0 ≤ C →
IsGIAFTRLRun P 𝒜 ℬ e T R → IsCorruptedG P 𝒜 θ C T R →
stabI2 P ℬ e T R ≤ M + J * Real.sqrt C * Real.log (Real.exp 1 + 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.3, Lemma G.4, and (G.11)–(G.13)