Master decomposition (G.3)–(G.5) of the GIA-FTRL regret against an atom
ProvedIAFTRL.lemma_G_masterbandit-algorithmslinear-banditsonline-learning
Setting. A GIA-FTRL run of rounds against an adaptive environment, any vector , and any atom of the reference measure , with .
Claim.
Here , , , and .
Proof idea.
- Unbiased loss differences give .
- The localized entropy identity (J.5) bounds the first sum by .
- The second sum splits as .
Preamble
import Mathlib import Definitions.Def_IAFTRL_LinEnv import Definitions.Def_IAFTRL_GIAFTRL import Definitions.Def_IAFTRL_GTerms
Formal statement
namespace IAFTRL
open MeasureTheory
/-- **The master decomposition (G.3)–(G.5) with the localized entropy identity (J.5).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version),
proof of Proposition G.1, pp.123–124: "`Reg_T(a*) = E[Σ_t ⟨q_t − δ_a*, ℓ̂_t⟩] + E[Σ_t ⟨p_t − q_t, Δ⟩] +
E[Σ_t ⟨p_t − q_t, xᵀc_t⟩] ≤ β₁h* + Σ_{t=2}^T (β_t − β_{t−1}) E[h* − D_KL(q_t, µ)] + Σ_t E[D_t] + …`"
(Lemma J.2, (J.5)).
For every execution of GIA-FTRL for `T ≥ 1` rounds, every vector `θ` and every atom `a*` of the
reference measure (`µ({a*}) > 0`, `h* = log(1/µ({a*}))`):
`Reg_T(a*) ≤ I₁ + I₂ + I₃ + I₄` with the sums of `IAFTRL_GTerms`. -/
theorem lemma_G_master {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 ℬ)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
(R : GRun d Ω) (hT : 1 ≤ T) (hR : IsGIAFTRLRun P 𝒜 ℬ e T R) (θ astar : Fin d → ℝ)
(hatom : 0 < refMu ℬ e {astar}) :
gRegretVs P T R astar ≤ penI1 P ℬ e T R astar + stabI2 P ℬ e T R +
exploI3 P ℬ e T R θ astar + corrI4 P ℬ e T R θ := 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.1.1, (G.3)–(G.5), and Lemma J.2 (J.5)